// DFS performs a depth first traversal calling f for each node starting from u.
// If f returns true, traversal stops and DFS returns true.
344327
func DFS(t Traversal, f Iter, u T) bool {
	lifo := NewLIFO(u)
	for lifo.Size() > 0 {
		next, _ := lifo.Pop()
		if t.Visited(next) {
			continue
		}
		if f(next) {
			return true
		}
		for _, v := range t.Edges(next) {
			lifo.Push(v)
		}
	}
	return false
}
683340
func containsNode(node, x ast.Node) (found bool) {
	ast.Walk(funcVisitor(func(n ast.Node) bool {
		if !found {
			found = n == x
		}
		return !found
	}),
		node)
	return
}
734063
func (pc *PyramidChunker) depth() (d int) {
	for _, l := range pc.chunkLevel {
		if l == nil {
			return
		}
		d++
	}
	return
}
1182972
func Walk(n Node, f func(Node) bool) {
	if !f(n) {
		return
	}

	// TODO(adonovan): opt: order cases using profile data.
	switch n := n.(type) {
	case *File:
		walkStmts(n.Stmts, f)

	case *ExprStmt:
		Walk(n.X, f)

	case *BranchStmt:
		// no-op

	case *IfStmt:
		Walk(n.Cond, f)
		walkStmts(n.True, f)
		walkStmts(n.False, f)

	case *AssignStmt:
		Walk(n.RHS, f)
		Walk(n.LHS, f)

	case *DefStmt:
		Walk(n.Name, f)
		for _, param := range n.Function.Params {
			Walk(param, f)
		}
		walkStmts(n.Function.Body, f)

	case *ForStmt:
		Walk(n.Vars, f)
		Walk(n.X, f)
		walkStmts(n.Body, f)

	case *ReturnStmt:
		if n.Result != nil {
			Walk(n.Result, f)
		}

	case *LoadStmt:
		Walk(n.Module, f)
		for _, from := range n.From {
			Walk(from, f)
		}
		for _, to := range n.To {
			Walk(to, f)
		}

	case *Ident, *Literal:
		// no-op

	case *ListExpr:
		for _, x := range n.List {
			Walk(x, f)
		}

	case *ParenExpr:
		Walk(n.X, f)

	case *CondExpr:
		Walk(n.Cond, f)
		Walk(n.True, f)
		Walk(n.False, f)

	case *IndexExpr:
		Walk(n.X, f)
		Walk(n.Y, f)

	case *DictEntry:
		Walk(n.Key, f)
		Walk(n.Value, f)

	case *SliceExpr:
		Walk(n.X, f)
		if n.Lo != nil {
			Walk(n.Lo, f)
		}
		if n.Hi != nil {
			Walk(n.Hi, f)
		}
		if n.Step != nil {
			Walk(n.Step, f)
		}

	case *Comprehension:
		for _, clause := range n.Clauses {
			Walk(clause, f)
		}
		Walk(n.Body, f)

	case *IfClause:
		Walk(n.Cond, f)

	case *ForClause:
		Walk(n.Vars, f)
		Walk(n.X, f)

	case *TupleExpr:
		for _, x := range n.List {
			Walk(x, f)
		}

	case *DictExpr:
		for _, entry := range n.List {
			entry := entry.(*DictEntry)
			Walk(entry.Key, f)
			Walk(entry.Value, f)
		}

	case *UnaryExpr:
		Walk(n.X, f)

	case *BinaryExpr:
		Walk(n.X, f)
		Walk(n.Y, f)

	case *DotExpr:
		Walk(n.X, f)
		Walk(n.Name, f)

	case *CallExpr:
		Walk(n.Fn, f)
		for _, arg := range n.Args {
			Walk(arg, f)
		}

	case *LambdaExpr:
		for _, param := range n.Function.Params {
			Walk(param, f)
		}
		walkStmts(n.Function.Body, f)

	default:
		panic(n)
	}

	f(nil)
}
1289089
func (s *ExplainService) Df(df string) *ExplainService {
	s.df = df
	return s
}
963419
func (t *tree) FindAll(f func(v interface{}) (bool, error)) []Changer {
	ns, err := t.container.root.findAll(func(fn *node) (bool, error) {
		return f(fn.content.value())
	})
	if err != nil {
		return []Changer{&changer{nil, err}}
	}
	var cs []Changer
	for _, n := range ns {
		cs = append(cs, &changer{n, nil})
	}
	return cs
}
672790
func (g *Globber) filepaths(list []string, dir string, tree bool) (r []string) {
	var dirsep string
	if dir != "" {
		dirsep = dir + string(g.config.Separator)
		i := sort.SearchStrings(list, dirsep)
		if i >= len(list) {
			return
		}
		list = list[i:]
	}
	found := map[string]struct{}{}
	for _, path := range list {
		if dirsep != "" && !strings.HasPrefix(path, dirsep) {
			break
		}
		for j := len(dirsep); j < len(path); j++ {
			for j < len(path) && path[j] != g.config.Separator {
				j++
			}
			path := path[:j]
			if _, ok := found[path]; !ok {
				found[path] = struct{}{}
				r = append(r, path)
			}
			if !tree {
				break
			}
		}
	}
	return
}
695835
func (ncs *nodeCacheStandard) AllNodes() (nodes []Node) {
	ncs.lock.RLock()
	defer ncs.lock.RUnlock()
	nodes = make([]Node, 0, len(ncs.nodes))
	for _, entry := range ncs.nodes {
		nodes = append(nodes, ncs.makeNodeStandardForEntryLocked(entry))
	}
	return nodes
}
889404
func (n *node) findAll(f func(fn *node) (bool, error)) ([]*node, error) {
	var allFound []*node
	hasFound, err := f(n)
	if err != nil {
		return nil, errors.Annotate(err, ErrNodeFindAll, errorMessages)
	}
	if hasFound {
		allFound = append(allFound, n)
	}
	for _, child := range n.children {
		found, err := child.findAll(f)
		if err != nil {
			return nil, errors.Annotate(err, ErrNodeFindAll, errorMessages)
		}
		if found != nil {
			allFound = append(allFound, found...)
		}
	}
	return allFound, nil
}
1315636
func (n *TreeNode) CollapseAll() *TreeNode {
	n.Walk(func(node, parent *TreeNode) bool {
		n.expanded = false
		return true
	})
	return n
}
189817
func BFS(t Traversal, f Iter, u T) bool {
	fifo := NewFIFO(u)
	for fifo.Size() > 0 {
		next, _ := fifo.Pop()
		if t.Visited(next) {
			continue
		}
		if f(next) {
			return true
		}
		for _, v := range t.Edges(next) {
			fifo.Push(v)
		}
	}
	return false
}
1002118
func (f *FDBBackend) decDirsRefcount(tr fdb.Transaction, path string) error {
	pathElements := strings.Split(strings.TrimRight(path, "/"), "/")

	dirsTodo := make([]DirsDecTodo, 0, len(pathElements)*2)

	for i := len(pathElements) - 1; i != 0; i-- {
		dPath, err := decoratePath(strings.Join(pathElements[:i], "/") + "/")
		if err != nil {
			return errwrap.Wrapf("error decrementing directories refcount: {{err}}", err)
		}

		metaFKey := fdb.Key(concat(f.metaKeysSpace.Bytes(), dPath...))
		dirsTodo = append(dirsTodo, DirsDecTodo{
			fkey:   metaFKey,
			future: tr.Get(metaFKey),
		})

		dataFKey := fdb.Key(concat(f.dataSpace.Bytes(), dPath...))
		dirsTodo = append(dirsTodo, DirsDecTodo{
			fkey:   dataFKey,
			future: tr.Get(dataFKey),
		})
	}

	for _, todo := range dirsTodo {
		value, err := todo.future.Get()
		if err != nil {
			return errwrap.Wrapf("error getting directory refcount while decrementing: {{err}}", err)
		}

		// The directory entry does not exist; this is not expected
		if value == nil {
			return fmt.Errorf("non-existent directory while decrementing directory refcount")
		}

		var count int64
		err = binary.Read(bytes.NewReader(value), binary.LittleEndian, &count)
		if err != nil {
			return errwrap.Wrapf("error reading directory refcount while decrementing: {{err}}", err)
		}

		if count > 1 {
			// Atomic -1
			tr.Add(todo.fkey, atomicArgMinusOne)
		} else {
			// Directory is empty, remove it
			tr.Clear(todo.fkey)
		}
	}

	return nil
}
32221
func (h *overlay) FS() ctxvfs.FileSystem {
	return ctxvfs.Sync(&h.mu, ctxvfs.Map(h.m))
}
359682
func (rfs *RootFS) Chroot(_ string) (newFS billy.Filesystem, err error) {
	// Don't allow chroot'ing anywhere outside of the root FS since we
	// haven't yet implemented folderlist browsing.
	return nil, errors.New("RootFS cannot chroot")
}
555778
func (t Tree) Walk(f func(*exphtml.Node)) {
	WalkNodes(t.n, f)
}
70206
func HashFS(h hash.Hash, fs FS, gs GetSetter) FS {
	return &hashFS{
		h:  h,
		fs: fs,
		gs: gs,
	}
}
41744
func (c SimpleFSClient) SimpleFSListRecursiveToDepth(ctx context.Context, __arg SimpleFSListRecursiveToDepthArg) (err error) {
	err = c.Cli.Call(ctx, "keybase.1.SimpleFS.simpleFSListRecursiveToDepth", []interface{}{__arg}, nil)
	return
}