codekingpro/portable-devtools

1// Given a set of nodes in a tree, and a filter function to test
2// incoming edges to the dep set that should be ignored otherwise.
3//
4// find the set of deps that are only depended upon by nodes in the set, or
5// their dependencies, or edges that are ignored.
6//
7// Used when figuring out what to prune when replacing a node with a newer
8// version, or when an optional dep fails to install.
9
10const gatherDepSet = (set, edgeFilter) => {
11  const deps = new Set(set)
12
13  // add the full set of dependencies.  note that this loop will continue
14  // as the deps set increases in size.
15  for (const node of deps) {
16    for (const edge of node.edgesOut.values()) {
17      if (edge.to && edgeFilter(edge)) {
18        deps.add(edge.to)
19      }
20    }
21  }
22
23  // now remove all nodes in the set that have a dependent outside the set
24  // if any change is made, then re-check
25  // continue until no changes made, or deps set evaporates fully.
26  let changed = true
27  while (changed === true && deps.size > 0) {
28    changed = false
29    for (const dep of deps) {
30      for (const edge of dep.edgesIn) {
31        if (!deps.has(edge.from) && edgeFilter(edge)) {
32          changed = true
33          deps.delete(dep)
34          break
35        }
36      }
37    }
38  }
39
40  return deps
41}
42
43module.exports = gatherDepSet
44