1// Perform a depth-first walk of a tree.
2//
3// `visit(node)` is called when the node is first encountered.
4// `leave(node, children)` is called when all of the node's children
5// have been left or (in the case of cyclic graphs) visited.
6//
7// Only one of visit or leave is required.  (Technically both are optional,
8// but if you don't provide at least one, the tree is just walked without
9// doing anything, which is a bit pointless.)  If visit is provided, and
10// leave is not, then this is a root->leaf traversal.  If leave is provided,
11// and visit is not, then it's leaf->root.  Both can be provided for a
12// map-reduce operation.
13//
14// If either visit or leave return a Promise for any node, then the
15// walk returns a Promise.
16
17const depthDescent = require('./depth-descent.js')
18const depth = ({
19  visit,
20  leave,
21  filter = () => true,
22  seen = new Map(),
23  getChildren,
24  tree,
25}) => {
26  if (!leave) {
27    return depthDescent({ visit, filter, getChildren, tree })
28  }
29
30  if (seen.has(tree)) {
31    return seen.get(tree)
32  }
33
34  seen.set(tree, null)
35
36  const visitNode = () => {
37    const res = visit ? visit(tree) : tree
38    if (isPromise(res)) {
39      const fullResult = res.then(resThen => {
40        seen.set(tree, resThen)
41        return kidNodes()
42      })
43      seen.set(tree, fullResult)
44      return fullResult
45    } else {
46      seen.set(tree, res)
47      return kidNodes()
48    }
49  }
50
51  const kidNodes = () => {
52    const kids = getChildren(tree, seen.get(tree))
53    return isPromise(kids) ? kids.then(processKids) : processKids(kids)
54  }
55
56  const processKids = nodes => {
57    const kids = (nodes || []).filter(filter).map(kid =>
58      depth({ visit, leave, filter, seen, getChildren, tree: kid }))
59    return kids.some(isPromise)
60      ? Promise.all(kids).then(leaveNode)
61      : leaveNode(kids)
62  }
63
64  const leaveNode = kids => {
65    const res = leave(seen.get(tree), kids)
66    seen.set(tree, res)
67    // if it's a promise at this point, the caller deals with it
68    return res
69  }
70
71  return visitNode()
72}
73
74const isPromise = p => p && typeof p.then === 'function'
75
76module.exports = depth
77