// StartsWithBackstep checks if the given path starts with a backstep segment
551053
func StartsWithBackstep(rel string) bool {
	// normalize to / and check for ../
	return rel == ".." || strings.HasPrefix(filepath.ToSlash(rel), "../")
}
1222847
func (lg *Linear) WithStep(step float64) *Linear {
	lg.step = step
	return lg
}
480631
func StartPath(qs graph.QuadStore, nodes ...quad.Value) *Path {
	return newPath(qs, isMorphism(nodes...))
}
1120364
func (r *NodeAuthorizer) hasPathFrom(nodeName string, startingType vertexType, startingNamespace, startingName string) (bool, error) {
	r.graph.lock.RLock()
	defer r.graph.lock.RUnlock()

	nodeVertex, exists := r.graph.getVertex_rlocked(nodeVertexType, "", nodeName)
	if !exists {
		return false, fmt.Errorf("unknown node %q cannot get %s %s/%s", nodeName, vertexTypes[startingType], startingNamespace, startingName)
	}

	startingVertex, exists := r.graph.getVertex_rlocked(startingType, startingNamespace, startingName)
	if !exists {
		return false, fmt.Errorf("node %q cannot get unknown %s %s/%s", nodeName, vertexTypes[startingType], startingNamespace, startingName)
	}

	// Fast check to see if we know of a destination edge
	if r.graph.destinationEdgeIndex[startingVertex.ID()].has(nodeVertex.ID()) {
		return true, nil
	}

	found := false
	traversal := &traverse.VisitingDepthFirst{
		EdgeFilter: func(edge graph.Edge) bool {
			if destinationEdge, ok := edge.(*destinationEdge); ok {
				if destinationEdge.DestinationID() != nodeVertex.ID() {
					// Don't follow edges leading to other nodes
					return false
				}
				// We found an edge leading to the node we want
				found = true
			}
			// Visit this edge
			return true
		},
	}
	traversal.Walk(r.graph.graph, startingVertex, func(n graph.Node) bool {
		if n.ID() == nodeVertex.ID() {
			// We found the node we want
			found = true
		}
		// Stop visiting if we've found the node we want
		return found
	})
	if !found {
		return false, fmt.Errorf("node %q cannot get %s %s/%s, no relationship to this object was found in the node authorizer graph", nodeName, vertexTypes[startingType], startingNamespace, startingName)
	}
	return true, nil
}
593543
func (b *buffer) wordBackward() (err error) {
	for start := false; ; {
		start, err = b.backward()
		if start == true || err != nil || b.data[b.pos-1] == 32 {
			return
		}
	}
}
746118
func StartPathNodes(qs graph.QuadStore, nodes ...graph.Value) *Path {
	return newPath(qs, isNodeMorphism(nodes...))
}
1161727
func StartWith(input string, appName string) error {
	return openWith(input, appName).Start()
}
109706
func RetryWithBackoff(backoff wait.Backoff, condition func() (bool, error)) (bool, error) {
	duration := backoff.Duration
	i := 0
	for {
		if i != 0 {
			adjusted := duration
			if backoff.Jitter > 0.0 {
				adjusted = wait.Jitter(duration, backoff.Jitter)
			}
			time.Sleep(adjusted)
			duration = time.Duration(float64(duration) * backoff.Factor)
		}

		i++

		done, err := condition()
		if done {
			return done, err
		}
		noMoreRetries := i >= backoff.Steps
		if !noMoreRetries && err != nil {
			glog.V(2).Infof("retrying after error %v", err)
		}

		if noMoreRetries {
			glog.Infof("hit maximum retries %d with error %v", i, err)
			return done, err
		}
	}
}
631666
func PathLsNType(basePath string, depth int, filetypes []string) (map[int]string, error) {
	return doPathWalk(basePath, depth, filetypes, true)
}
651143
func (g *AcyclicGraph) ReverseDepthFirstWalk(start []Vertex, f DepthWalkFunc) error {
	defer g.debug.BeginOperation(typeReverseDepthFirstWalk, "").End("")

	seen := make(map[Vertex]struct{})
	frontier := make([]*vertexAtDepth, len(start))
	for i, v := range start {
		frontier[i] = &vertexAtDepth{
			Vertex: v,
			Depth:  0,
		}
	}
	for len(frontier) > 0 {
		// Pop the current vertex
		n := len(frontier)
		current := frontier[n-1]
		frontier = frontier[:n-1]

		// Check if we've seen this already and return...
		if _, ok := seen[current.Vertex]; ok {
			continue
		}
		seen[current.Vertex] = struct{}{}

		// Add next set of targets in a consistent order.
		targets := AsVertexList(g.UpEdges(current.Vertex))
		sort.Sort(byVertexName(targets))
		for _, t := range targets {
			frontier = append(frontier, &vertexAtDepth{
				Vertex: t,
				Depth:  current.Depth + 1,
			})
		}

		// Visit the current node
		if err := f(current.Vertex, current.Depth); err != nil {
			return err
		}
	}

	return nil
}
384364
func partitionDeps(deps []string, rootDir string, blacklist []string) (partitionedDeps, error) {
	fsView, err := common.NewFilesystemView(rootDir, blacklist)
	if err != nil {
		return partitionedDeps{}, err
	}

	walker := partitioningWalker{fsView: fsView, seen: stringset.New(1024)}
	for _, dep := range deps {
		// Try to walk dep. If dep is a file (or symlink), the inner function is called exactly once.
		if err := filepath.Walk(filepath.Clean(dep), walker.walkFn); err != nil {
			return partitionedDeps{}, err
		}
	}
	return walker.parts, nil
}
268739
func WithPath(path string) OptionFunc {
	return func(c *CommitLog) error {
		if path == "" {
			return ErrEmptyPath
		}
		c.path = path
		return nil
	}
}
232091
func (p *Path) Except(path *Path) *Path {
	np := p.clone()
	np.stack = append(np.stack, exceptMorphism(path))
	return np
}
627228
func pathMatch(pattern, path string) bool {
	if len(pattern) == 0 {
		// should not happen
		return false
	}
	n := len(pattern)
	if pattern[n-1] != '/' {
		return pattern == path
	}
	return len(path) >= n && path[0:n] == pattern
}
796513
func (lg *Linear) WithStart(start float64) *Linear {
	lg.start = start
	return lg
}
1335161
func Restart(targets []string, b backend.Backend) error {

	// act as if the user called "stop" and then "start"
	if err := Stop(targets, b); err != nil {
		return err
	}

	return Start(targets, b)
}
1140805
func (s *solver) backtrack() bool {
	if len(s.vqs) == 0 {
		// nothing to backtrack to
		return false
	}

	s.mtr.push("backtrack")
	for {
		for {
			if len(s.vqs) == 0 {
				// no more versions, nowhere further to backtrack
				return false
			}
			if s.vqs[len(s.vqs)-1].failed {
				break
			}

			s.vqs, s.vqs[len(s.vqs)-1] = s.vqs[:len(s.vqs)-1], nil

			// Pop selections off until we get to a project.
			var proj bool
			var awp atomWithPackages
			for !proj {
				awp, proj = s.unselectLast()
				s.traceBacktrack(awp.bmi(), !proj)
			}
		}

		// Grab the last versionQueue off the list of queues
		q := s.vqs[len(s.vqs)-1]

		// Walk back to the next project
		awp, proj := s.unselectLast()
		if !proj {
			panic("canary - *should* be impossible to have a pkg-only selection here")
		}

		if !q.id.eq(awp.a.id) {
			panic("canary - version queue stack and selected project stack are misaligned")
		}

		// Advance the queue past the current version, which we know is bad
		// TODO(sdboyer) is it feasible to make available the failure reason here?
		if q.advance(nil) == nil && !q.isExhausted() {
			// Search for another acceptable version of this failed dep in its queue
			s.traceCheckQueue(q, awp.bmi(), true, 0)
			if s.findValidVersion(q, awp.pl) == nil {
				// Found one! Put it back on the selected queue and stop
				// backtracking

				// reusing the old awp is fine
				awp.a.v = q.current()
				s.selectAtom(awp, false)
				break
			}
		}

		s.traceBacktrack(awp.bmi(), false)
		//s.traceInfo("no more versions of %s, backtracking", q.id.errString())

		// No solution found; continue backtracking after popping the queue
		// we just inspected off the list
		// GC-friendly pop pointer elem in slice
		s.vqs, s.vqs[len(s.vqs)-1] = s.vqs[:len(s.vqs)-1], nil
	}

	s.mtr.pop()
	// Backtracking was successful if loop ended before running out of versions
	if len(s.vqs) == 0 {
		return false
	}
	s.attempts++
	return true
}