codekingpro/portable-devtools

1// a tree representing the difference between two trees
2// A Diff node's parent is not necessarily the parent of
3// the node location it refers to, but rather the highest level
4// node that needs to be either changed or removed.
5// Thus, the root Diff node is the shallowest change required
6// for a given branch of the tree being mutated.
7
8const { depth } = require('treeverse')
9const { existsSync } = require('node:fs')
10
11const ssri = require('ssri')
12
13class Diff {
14  constructor ({ actual, ideal, filterSet, shrinkwrapInflated, omit }) {
15    this.omit = omit
16    this.filterSet = filterSet
17    this.shrinkwrapInflated = shrinkwrapInflated
18    this.children = []
19    this.actual = actual
20    this.ideal = ideal
21    if (this.ideal) {
22      this.resolved = this.ideal.resolved
23      this.integrity = this.ideal.integrity
24    }
25    this.action = getAction(this)
26    this.parent = null
27    // the set of leaf nodes that we rake up to the top level
28    this.leaves = []
29    // the set of nodes that don't change in this branch of the tree
30    this.unchanged = []
31    // the set of nodes that will be removed in this branch of the tree
32    this.removed = []
33  }
34
35  static calculate ({
36    actual,
37    ideal,
38    filterNodes = [],
39    shrinkwrapInflated = new Set(),
40    omit = new Set(),
41  }) {
42    // if there's a filterNode, then:
43    // - get the path from the root to the filterNode.  The root or
44    //   root.target should have an edge either to the filterNode or
45    //   a link to the filterNode.  If not, abort.  Add the path to the
46    //   filterSet.
47    // - Add set of Nodes depended on by the filterNode to filterSet.
48    // - Anything outside of that set should be ignored by getChildren
49    const filterSet = new Set()
50    const extraneous = new Set()
51    for (const filterNode of filterNodes) {
52      const { root } = filterNode
53      if (root !== ideal && root !== actual) {
54        throw new Error('invalid filterNode: outside idealTree/actualTree')
55      }
56      const rootTarget = root.target
57      const edge = [...rootTarget.edgesOut.values()].filter(e => {
58        return e.to && (e.to === filterNode || e.to.target === filterNode)
59      })[0]
60      filterSet.add(root)
61      filterSet.add(rootTarget)
62      filterSet.add(ideal)
63      filterSet.add(actual)
64      if (edge && edge.to) {
65        filterSet.add(edge.to)
66        filterSet.add(edge.to.target)
67      }
68      filterSet.add(filterNode)
69
70      depth({
71        tree: filterNode,
72        visit: node => filterSet.add(node),
73        getChildren: node => {
74          const orig = node
75          node = node.target
76          const loc = node.location
77          const idealNode = ideal.inventory.get(loc)
78          const ideals = !idealNode ? []
79            : [...idealNode.edgesOut.values()].filter(e => e.to).map(e => e.to)
80          const actualNode = actual.inventory.get(loc)
81          const actuals = !actualNode ? []
82            : [...actualNode.edgesOut.values()].filter(e => e.to).map(e => e.to)
83          if (actualNode) {
84            for (const child of actualNode.children.values()) {
85              if (child.extraneous) {
86                extraneous.add(child)
87              }
88            }
89          }
90
91          const result = ideals.concat(actuals)
92          // Include link targets so store entries end up in filterSet
93          if (orig.isLink) {
94            result.push(node)
95          }
96          return result
97        },
98      })
99    }
100    for (const extra of extraneous) {
101      filterSet.add(extra)
102    }
103
104    return depth({
105      tree: new Diff({ actual, ideal, filterSet, shrinkwrapInflated, omit }),
106      getChildren,
107      leave,
108    })
109  }
110}
111
112const getAction = ({ actual, ideal }) => {
113  if (!ideal) {
114    return 'REMOVE'
115  }
116
117  // bundled meta-deps are copied over to the ideal tree when we visit it,
118  // so they'll appear to be missing here.  There's no need to handle them
119  // in the diff, though, because they'll be replaced at reify time anyway
120  // Otherwise, add the missing node.
121  if (!actual) {
122    return ideal.inDepBundle ? null : 'ADD'
123  }
124
125  // always ignore the root node
126  if (ideal.isRoot && actual.isRoot) {
127    return null
128  }
129
130  // if the versions don't match, it's a change no matter what
131  if (ideal.version !== actual.version) {
132    return 'CHANGE'
133  }
134
135  const binsExist = ideal.binPaths.every((path) => existsSync(path))
136
137  // top nodes, links, and git deps won't have integrity, but do have resolved
138  // if neither node has integrity, the bins exist, and either (a) neither
139  // node has a resolved value or (b) they both do and match, then we can
140  // leave this one alone since we already know the versions match due to
141  // the condition above.  The "neither has resolved" case (a) cannot be
142  // treated as a 'mark CHANGE and refetch', because shrinkwraps, bundles,
143  // and link deps may lack this information, and we don't want to try to
144  // go to the registry for something that isn't there.
145  const noIntegrity = !ideal.integrity && !actual.integrity
146  const noResolved = !ideal.resolved && !actual.resolved
147  const resolvedMatch = ideal.resolved && ideal.resolved === actual.resolved
148  if (noIntegrity && binsExist && (resolvedMatch || noResolved)) {
149    return null
150  }
151
152  // otherwise, verify that it's the same bits
153  // note that if ideal has integrity, and resolved doesn't, we treat
154  // that as a 'change', so that it gets re-fetched and locked down.
155  const integrityMismatch = !ideal.integrity || !actual.integrity ||
156    !ssri.parse(ideal.integrity).match(actual.integrity)
157  if (integrityMismatch || !binsExist) {
158    return 'CHANGE'
159  }
160
161  return null
162}
163
164const allChildren = node => {
165  if (!node) {
166    return new Map()
167  }
168
169  // if the node is root, and also a link, then what we really
170  // want is to traverse the target's children
171  if (node.isRoot && node.isLink) {
172    return allChildren(node.target)
173  }
174
175  const kids = new Map()
176  for (const n of [node, ...node.fsChildren]) {
177    for (const kid of n.children.values()) {
178      kids.set(kid.path, kid)
179    }
180  }
181  return kids
182}
183
184// functions for the walk options when we traverse the trees
185// to create the diff tree
186const getChildren = diff => {
187  const children = []
188  const {
189    actual,
190    ideal,
191    unchanged,
192    removed,
193    filterSet,
194    shrinkwrapInflated,
195    omit,
196  } = diff
197
198  // Note: we DON'T diff fsChildren themselves, because they are either
199  // included in the package contents, or part of some other project, and
200  // will never appear in legacy shrinkwraps anyway.  but we _do_ include the
201  // child nodes of fsChildren, because those are nodes that we are typically
202  // responsible for installing.
203  const actualKids = allChildren(actual)
204  const idealKids = allChildren(ideal)
205
206  if (ideal && ideal.hasShrinkwrap && !shrinkwrapInflated.has(ideal)) {
207    // Guaranteed to get a diff.leaves here, because we always
208    // be called with a proper Diff object when ideal has a shrinkwrap
209    // that has not been inflated.
210    diff.leaves.push(diff)
211    return children
212  }
213
214  const paths = new Set([...actualKids.keys(), ...idealKids.keys()])
215  for (const path of paths) {
216    const actual = actualKids.get(path)
217    const ideal = idealKids.get(path)
218    diffNode({
219      actual,
220      ideal,
221      children,
222      unchanged,
223      removed,
224      filterSet,
225      shrinkwrapInflated,
226      omit,
227    })
228  }
229
230  if (diff.leaves && !children.length) {
231    diff.leaves.push(diff)
232  }
233
234  return children
235}
236
237const diffNode = ({
238  actual,
239  ideal,
240  children,
241  unchanged,
242  removed,
243  filterSet,
244  shrinkwrapInflated,
245  omit,
246}) => {
247  if (filterSet.size && !(filterSet.has(ideal) || filterSet.has(actual))) {
248    return
249  }
250
251  if (ideal?.shouldOmit?.(omit)) {
252    ideal.inert = true
253  }
254
255  // Treat inert nodes as undefined for the purposes of diffing.
256  if (ideal?.inert) {
257    ideal = undefined
258  }
259  if (!actual && !ideal) {
260    return
261  }
262
263  const action = getAction({ actual, ideal })
264
265  // if it's a match, then get its children
266  // otherwise, this is the child diff node
267  if (action || (!shrinkwrapInflated.has(ideal) && ideal.hasShrinkwrap)) {
268    if (action === 'REMOVE') {
269      removed.push(actual)
270    }
271    children.push(new Diff({ actual, ideal, filterSet, shrinkwrapInflated, omit }))
272  } else {
273    unchanged.push(ideal)
274    // !*! Weird dirty hack warning !*!
275    //
276    // Bundled deps aren't loaded in the ideal tree, because we don't know
277    // what they are going to be without unpacking.  Swap them over now if
278    // the bundling node isn't changing, so we don't prune them later.
279    //
280    // It's a little bit dirty to be doing this here, since it means that
281    // diffing trees can mutate them, but otherwise we have to walk over
282    // all unchanging bundlers and correct the diff later, so it's more
283    // efficient to just fix it while we're passing through already.
284    //
285    // Note that moving over a bundled dep will break the links to other
286    // deps under this parent, which may have been transitively bundled.
287    // Breaking those links means that we'll no longer see the transitive
288    // dependency, meaning that it won't appear as bundled any longer!
289    // In order to not end up dropping transitively bundled deps, we have
290    // to get the list of nodes to move, then move them all at once, rather
291    // than moving them one at a time in the first loop.
292    const bd = ideal.package.bundleDependencies
293    if (actual && bd && bd.length) {
294      const bundledChildren = []
295      for (const node of actual.children.values()) {
296        if (node.inBundle) {
297          bundledChildren.push(node)
298        }
299      }
300      for (const node of bundledChildren) {
301        node.parent = ideal
302      }
303    }
304    children.push(...getChildren({
305      actual,
306      ideal,
307      unchanged,
308      removed,
309      filterSet,
310      shrinkwrapInflated,
311      omit,
312    }))
313  }
314}
315
316// set the parentage in the leave step so that we aren't attaching
317// child nodes only to remove them later.  also bubble up the unchanged
318// nodes so that we can move them out of staging in the reification step.
319const leave = (diff, children) => {
320  children.forEach(kid => {
321    kid.parent = diff
322    diff.leaves.push(...kid.leaves)
323    diff.unchanged.push(...kid.unchanged)
324    diff.removed.push(...kid.removed)
325  })
326  diff.children = children
327  return diff
328}
329
330module.exports = Diff
331