codekingpro/portable-devtools

1// Perform a breadth-first walk of a tree, either logical or physical
2// This one only visits, it doesn't leave.  That's because
3// in a breadth-first traversal, children may be visited long
4// after their parent, so the "exit" pass ends up being just
5// another breadth-first walk.
6//
7// Breadth-first traversals are good for either creating a tree (ie,
8// reifying a dep graph based on a package.json without a node_modules
9// or package-lock), or mutating it in-place.  For a map-reduce type of
10// walk, it doesn't make a lot of sense, and is very expensive.
11const breadth = ({
12  visit,
13  filter = () => true,
14  getChildren,
15  tree,
16}) => {
17  const queue = []
18  const seen = new Map()
19
20  const next = () => {
21    while (queue.length) {
22      const node = queue.shift()
23      const res = visitNode(node)
24      if (isPromise(res)) {
25        return res.then(() => next())
26      }
27    }
28    return seen.get(tree)
29  }
30
31  const visitNode = (visitTree) => {
32    if (seen.has(visitTree)) {
33      return seen.get(visitTree)
34    }
35
36    seen.set(visitTree, null)
37    const res = visit ? visit(visitTree) : visitTree
38    if (isPromise(res)) {
39      const fullResult = res.then(resThen => {
40        seen.set(visitTree, resThen)
41        return kidNodes(visitTree)
42      })
43      seen.set(visitTree, fullResult)
44      return fullResult
45    } else {
46      seen.set(visitTree, res)
47      return kidNodes(visitTree)
48    }
49  }
50
51  const kidNodes = (kidTree) => {
52    const kids = getChildren(kidTree, seen.get(kidTree))
53    return isPromise(kids) ? kids.then(processKids) : processKids(kids)
54  }
55
56  const processKids = (kids) => {
57    kids = (kids || []).filter(filter)
58    queue.push(...kids)
59  }
60
61  queue.push(tree)
62  return next()
63}
64
65const isPromise = p => p && typeof p.then === 'function'
66
67module.exports = breadth
68