codekingpro/portable-devtools
114k
1// Internal methods used by buildIdealTree.
2// Answer the question: "can I put this dep here?"
3//
4// IMPORTANT: *nothing* in this class should *ever* modify or mutate the tree
5// at all. The contract here is strictly limited to read operations. We call
6// this in the process of walking through the ideal tree checking many
7// different potential placement targets for a given node. If a change is made
8// to the tree along the way, that can cause serious problems!
9//
10// In order to enforce this restriction, in debug mode, canPlaceDep() will
11// snapshot the tree at the start of the process, and then at the end, will
12// verify that it still matches the snapshot, and throw an error if any changes
13// occurred.
14//
15// The algorithm is roughly like this:
16// - check the node itself:
17// - if there is no version present, and no conflicting edges from target,
18// OK, provided all peers can be placed at or above the target.
19// - if the current version matches, KEEP
20// - if there is an older version present, which can be replaced, then
21// - if satisfying and preferDedupe? KEEP
22// - else: REPLACE
23// - if there is a newer version present, and preferDedupe, REPLACE
24// - if the version present satisfies the edge, KEEP
25// - else: CONFLICT
26// - if the node is not in conflict, check each of its peers:
27// - if the peer can be placed in the target, continue
28// - else if the peer can be placed in a parent, and there is no other
29// conflicting version shadowing it, continue
30// - else CONFLICT
31// - If the peers are not in conflict, return the original node's value
32//
33// An exception to this logic is that if the target is the deepest location
34// that a node can be placed, and the conflicting node can be placed deeper,
35// then we will return REPLACE rather than CONFLICT, and Arborist will queue
36// the replaced node for resolution elsewhere.
37
38const localeCompare = require('@isaacs/string-locale-compare')('en')
39const semver = require('semver')
40const debug = require('./debug.js')
41const peerEntrySets = require('./peer-entry-sets.js')
42const deepestNestingTarget = require('./deepest-nesting-target.js')
43
44const CONFLICT = Symbol('CONFLICT')
45const OK = Symbol('OK')
46const REPLACE = Symbol('REPLACE')
47const KEEP = Symbol('KEEP')
48
49class CanPlaceDep {
50 // dep is a dep that we're trying to place. it should already live in
51 // a virtual tree where its peer set is loaded as children of the root.
52 // target is the actual place where we're trying to place this dep
53 // in a node_modules folder.
54 // edge is the edge that we're trying to satisfy with this placement.
55 // parent is the CanPlaceDep object of the entry node when placing a peer.
56 constructor (options) {
57 const {
58 dep,
59 target,
60 edge,
61 preferDedupe,
62 parent = null,
63 peerPath = [],
64 explicitRequest = false,
65 } = options
66
67 debug(() => {
68 if (!dep) {
69 throw new Error('no dep provided to CanPlaceDep')
70 }
71
72 if (!target) {
73 throw new Error('no target provided to CanPlaceDep')
74 }
75
76 if (!edge) {
77 throw new Error('no edge provided to CanPlaceDep')
78 }
79
80 this._treeSnapshot = JSON.stringify([...target.root.inventory.entries()]
81 .map(([loc, { packageName, version, resolved }]) => {
82 return [loc, packageName, version, resolved]
83 }).sort(([a], [b]) => localeCompare(a, b)))
84 })
85
86 // the result of whether we can place it or not
87 this.canPlace = null
88 // if peers conflict, but this one doesn't, then that is useful info
89 this.canPlaceSelf = null
90
91 this.dep = dep
92 this.target = target
93 this.edge = edge
94 this.explicitRequest = explicitRequest
95
96 // preventing cycles when we check peer sets
97 this.peerPath = peerPath
98 // we always prefer to dedupe peers, because they are trying
99 // a bit harder to be singletons.
100 this.preferDedupe = !!preferDedupe || edge.peer
101 this.parent = parent
102 this.children = []
103
104 this.isSource = target === this.peerSetSource
105 this.name = edge.name
106 this.current = target.children.get(this.name)
107 this.targetEdge = target.edgesOut.get(this.name)
108 this.conflicts = new Map()
109
110 // check if this dep was already subject to a peerDep override while
111 // building the peerSet.
112 this.edgeOverride = !dep.satisfies(edge)
113
114 this.canPlace = this.checkCanPlace()
115 if (!this.canPlaceSelf) {
116 this.canPlaceSelf = this.canPlace
117 }
118
119 debug(() => {
120 const treeSnapshot = JSON.stringify([...target.root.inventory.entries()]
121 .map(([loc, { packageName, version, resolved }]) => {
122 return [loc, packageName, version, resolved]
123 }).sort(([a], [b]) => localeCompare(a, b)))
124 /* istanbul ignore if */
125 if (this._treeSnapshot !== treeSnapshot) {
126 throw Object.assign(new Error('tree changed in CanPlaceDep'), {
127 expect: this._treeSnapshot,
128 actual: treeSnapshot,
129 })
130 }
131 })
132 }
133
134 checkCanPlace () {
135 const { target, targetEdge, current, dep } = this
136
137 // if the dep failed to load, we're going to fail the build or
138 // prune it out anyway, so just move forward placing/replacing it.
139 if (dep.errors.length) {
140 return current ? REPLACE : OK
141 }
142
143 // cannot place peers inside their dependents, except for tops
144 if (targetEdge && targetEdge.peer && !target.isTop) {
145 return CONFLICT
146 }
147
148 // skip this test if there's a current node, because we might be able
149 // to dedupe against it anyway
150 if (!current &&
151 targetEdge &&
152 !dep.satisfies(targetEdge) &&
153 targetEdge !== this.edge) {
154 return CONFLICT
155 }
156
157 return current ? this.checkCanPlaceCurrent() : this.checkCanPlaceNoCurrent()
158 }
159
160 // we know that the target has a dep by this name in its node_modules
161 // already. Can return KEEP, REPLACE, or CONFLICT.
162 checkCanPlaceCurrent () {
163 const { preferDedupe, explicitRequest, current, target, edge, dep } = this
164
165 if (dep.matches(current)) {
166 if (current.satisfies(edge) || this.edgeOverride) {
167 return explicitRequest ? REPLACE : KEEP
168 }
169 }
170
171 const { version: curVer } = current
172 const { version: newVer } = dep
173 const tryReplace = curVer && newVer && semver.gte(newVer, curVer)
174 if (tryReplace && dep.canReplace(current)) {
175 // It's extremely rare that a replaceable node would be a conflict, if
176 // the current one wasn't a conflict, but it is theoretically possible
177 // if peer deps are pinned. In that case we treat it like any other
178 // conflict, and keep trying.
179 const cpp = this.canPlacePeers(REPLACE)
180 if (cpp !== CONFLICT) {
181 return cpp
182 }
183 }
184
185 // ok, can't replace the current with new one, but maybe current is ok?
186 if (current.satisfies(edge) && (!explicitRequest || preferDedupe)) {
187 return KEEP
188 }
189
190 // if we prefer deduping, then try replacing newer with older
191 if (preferDedupe && !tryReplace && dep.canReplace(current)) {
192 const cpp = this.canPlacePeers(REPLACE)
193 if (cpp !== CONFLICT) {
194 return cpp
195 }
196 }
197
198 // Check for interesting cases!
199 // First, is this the deepest place that this thing can go, and NOT the
200 // deepest place where the conflicting dep can go? If so, replace it,
201 // and let it re-resolve deeper in the tree.
202 const myDeepest = this.deepestNestingTarget
203
204 // ok, i COULD be placed deeper, so leave the current one alone.
205 if (target !== myDeepest) {
206 return CONFLICT
207 }
208
209 // if we are not checking a peerDep, then we MUST place it here, in the
210 // target that has a non-peer dep on it.
211 if (!edge.peer && target === edge.from) {
212 return this.canPlacePeers(REPLACE)
213 }
214
215 // if we aren't placing a peer in a set, then we're done here.
216 // This is ignored because it SHOULD be redundant, as far as I can tell,
217 // with the deepest target and target===edge.from tests. But until we
218 // can prove that isn't possible, this condition is here for safety.
219 /* istanbul ignore if - allegedly impossible */
220 if (!this.parent && !edge.peer) {
221 return CONFLICT
222 }
223
224 // check the deps in the peer group for each edge into that peer group
225 // if ALL of them can be pushed deeper, or if it's ok to replace its
226 // members with the contents of the new peer group, then we're good.
227 let canReplace = true
228 for (const [entryEdge, currentPeers] of peerEntrySets(current)) {
229 if (entryEdge === this.edge || entryEdge === this.peerEntryEdge) {
230 continue
231 }
232
233 // First, see if it's ok to just replace the peerSet entirely.
234 // we do this by walking out from the entryEdge, because in a case like
235 // this:
236 //
237 // v -> PEER(a@1||2)
238 // a@1 -> PEER(b@1)
239 // a@2 -> PEER(b@2)
240 // b@1 -> PEER(a@1)
241 // b@2 -> PEER(a@2)
242 //
243 // root
244 // +-- v
245 // +-- a@2
246 // +-- b@2
247 //
248 // Trying to place a peer group of (a@1, b@1) would fail to note that
249 // they can be replaced, if we did it by looping 1 by 1. If we are
250 // replacing something, we don't have to check its peer deps, because
251 // the peerDeps in the placed peerSet will presumably satisfy.
252 const entryNode = entryEdge.to
253 const entryRep = dep.parent.children.get(entryNode.name)
254 if (entryRep) {
255 if (entryRep.canReplace(entryNode, dep.parent.children.keys())) {
256 continue
257 }
258 }
259
260 let canClobber = !entryRep
261 if (!entryRep) {
262 const peerReplacementWalk = new Set([entryNode])
263 OUTER: for (const currentPeer of peerReplacementWalk) {
264 for (const edge of currentPeer.edgesOut.values()) {
265 if (!edge.peer || !edge.valid) {
266 continue
267 }
268 const rep = dep.parent.children.get(edge.name)
269 if (!rep) {
270 if (edge.to) {
271 peerReplacementWalk.add(edge.to)
272 }
273 continue
274 }
275 if (!rep.satisfies(edge)) {
276 canClobber = false
277 break OUTER
278 }
279 }
280 }
281 }
282 if (canClobber) {
283 continue
284 }
285
286 // ok, we can't replace, but maybe we can nest the current set deeper?
287 let canNestCurrent = true
288 for (const currentPeer of currentPeers) {
289 if (!canNestCurrent) {
290 break
291 }
292
293 // still possible to nest this peerSet
294 const curDeep = deepestNestingTarget(entryEdge.from, currentPeer.name)
295 if (curDeep === target || target.isDescendantOf(curDeep)) {
296 canNestCurrent = false
297 canReplace = false
298 }
299 if (canNestCurrent) {
300 continue
301 }
302 }
303 }
304
305 // if we can nest or replace all the current peer groups, we can replace.
306 if (canReplace) {
307 return this.canPlacePeers(REPLACE)
308 }
309
310 return CONFLICT
311 }
312
313 checkCanPlaceNoCurrent () {
314 const { target, peerEntryEdge, dep, name } = this
315
316 // check to see what that name resolves to here, and who may depend on
317 // being able to reach it by crawling up past the parent. we know
318 // that it's not the target's direct child node, and if it was a direct
319 // dep of the target, we would have conflicted earlier.
320 const current = target !== peerEntryEdge.from && target.resolve(name)
321 if (current) {
322 for (const edge of current.edgesIn.values()) {
323 if (edge.from.isDescendantOf(target) && edge.valid) {
324 if (!dep.satisfies(edge)) {
325 return CONFLICT
326 }
327 }
328 }
329 }
330
331 // no objections, so this is fine as long as peers are ok here.
332 return this.canPlacePeers(OK)
333 }
334
335 get deepestNestingTarget () {
336 const start = this.parent ? this.parent.deepestNestingTarget
337 : this.edge.from
338 return deepestNestingTarget(start, this.name)
339 }
340
341 get conflictChildren () {
342 return this.allChildren.filter(c => c.canPlace === CONFLICT)
343 }
344
345 get allChildren () {
346 const set = new Set(this.children)
347 for (const child of set) {
348 for (const grandchild of child.children) {
349 set.add(grandchild)
350 }
351 }
352 return [...set]
353 }
354
355 get top () {
356 return this.parent ? this.parent.top : this
357 }
358
359 // check if peers can go here. returns state or CONFLICT
360 canPlacePeers (state) {
361 this.canPlaceSelf = state
362 if (this._canPlacePeers) {
363 return this._canPlacePeers
364 }
365
366 // TODO: represent peerPath in ERESOLVE error somehow?
367 const peerPath = [...this.peerPath, this.dep]
368 let sawConflict = false
369 for (const peerEdge of this.dep.edgesOut.values()) {
370 if (!peerEdge.peer || !peerEdge.to || peerPath.includes(peerEdge.to)) {
371 continue
372 }
373 const peer = peerEdge.to
374 // it may be the case that the *initial* dep can be nested, but a peer
375 // of that dep needs to be placed shallower, because the target has
376 // a peer dep on the peer as well.
377 const target = deepestNestingTarget(this.target, peer.name)
378 const cpp = new CanPlaceDep({
379 dep: peer,
380 target,
381 parent: this,
382 edge: peerEdge,
383 peerPath,
384 // always place peers in preferDedupe mode
385 preferDedupe: true,
386 })
387 /* istanbul ignore next */
388 debug(() => {
389 if (this.children.some(c => c.dep === cpp.dep)) {
390 throw new Error('checking same dep repeatedly')
391 }
392 })
393 this.children.push(cpp)
394
395 if (cpp.canPlace === CONFLICT) {
396 sawConflict = true
397 }
398 }
399
400 this._canPlacePeers = sawConflict ? CONFLICT : state
401 return this._canPlacePeers
402 }
403
404 // what is the node that is causing this peerSet to be placed?
405 get peerSetSource () {
406 return this.parent ? this.parent.peerSetSource : this.edge.from
407 }
408
409 get peerEntryEdge () {
410 return this.top.edge
411 }
412
413 static get CONFLICT () {
414 return CONFLICT
415 }
416
417 static get OK () {
418 return OK
419 }
420
421 static get REPLACE () {
422 return REPLACE
423 }
424
425 static get KEEP () {
426 return KEEP
427 }
428
429 get description () {
430 const { canPlace } = this
431 return canPlace && canPlace.description ||
432 /* istanbul ignore next - old node affordance */ canPlace
433 }
434}
435
436module.exports = CanPlaceDep
437