codekingpro/portable-devtools

1// Perform a depth-first walk of a tree, ONLY doing the descent (visit)
2//
3// This uses a stack rather than recursion, so that it can handle deeply
4// nested trees without call stack overflows.  (My kingdom for proper TCO!)
5//
6// This is only used for cases where leave() is not specified.
7//
8// a
9// +-- b
10// |   +-- 1
11// |   +-- 2
12// +-- c
13//     +-- 3
14//     +-- 4
15//
16// Expect:
17// visit a
18// visit b
19// visit 1
20// visit 2
21// visit c
22// visit 3
23// visit 4
24//
25// stack.push(tree)
26// while stack not empty
27//   pop T from stack
28//   VISIT(T)
29//   get children C of T
30//   push each C onto stack
31
32const depth = ({
33  visit,
34  filter,
35  getChildren,
36  tree,
37}) => {
38  const stack = []
39  const seen = new Map()
40
41  const next = () => {
42    while (stack.length) {
43      const node = stack.pop()
44      const res = visitNode(node)
45      if (isPromise(res)) {
46        return res.then(() => next())
47      }
48    }
49    return seen.get(tree)
50  }
51
52  const visitNode = (visitTree) => {
53    if (seen.has(visitTree)) {
54      return seen.get(visitTree)
55    }
56
57    seen.set(visitTree, null)
58    const res = visit ? visit(visitTree) : visitTree
59    if (isPromise(res)) {
60      const fullResult = res.then(resThen => {
61        seen.set(visitTree, resThen)
62        return kidNodes(visitTree)
63      })
64      seen.set(visitTree, fullResult)
65      return fullResult
66    } else {
67      seen.set(visitTree, res)
68      return kidNodes(visitTree)
69    }
70  }
71
72  const kidNodes = (kidTree) => {
73    const kids = getChildren(kidTree, seen.get(kidTree))
74    return isPromise(kids) ? kids.then(processKids) : processKids(kids)
75  }
76
77  const processKids = (kids) => {
78    kids = (kids || []).filter(filter)
79    stack.push(...kids)
80  }
81
82  stack.push(tree)
83  return next()
84}
85
86const isPromise = p => p && typeof p.then === 'function'
87
88module.exports = depth
89