place-dep.js

// Given a dep, a node that depends on it, and the edge representing that
// dependency, place the dep somewhere in the node's tree, and all of its
// peer dependencies.
//
// Handles all of the tree updating needed to place the dep, including
// removing replaced nodes, pruning now-extraneous or invalidated nodes,
// and saves a set of what was placed and what needs re-evaluation as
// a result.

const localeCompare = require('@isaacs/string-locale-compare')('en')
const { log } = require('proc-log')
const { redact } = require('@npmcli/redact')
const deepestNestingTarget = require('./deepest-nesting-target.js')
const CanPlaceDep = require('./can-place-dep.js')
const {
  KEEP,
  CONFLICT,
} = CanPlaceDep
const debug = require('./debug.js')

const Link = require('./link.js')
const gatherDepSet = require('./gather-dep-set.js')
const peerEntrySets = require('./peer-entry-sets.js')

class PlaceDep {
  constructor (options) {
    this.auditReport = options.auditReport
    this.dep = options.dep
    this.edge = options.edge
    this.explicitRequest = options.explicitRequest
    this.force = options.force
    this.installLinks = options.installLinks
    this.installStrategy = options.installStrategy
    this.legacyPeerDeps = options.legacyPeerDeps
    this.parent = options.parent || null
    this.preferDedupe = options.preferDedupe
    this.strictPeerDeps = options.strictPeerDeps
    this.updateNames = options.updateNames

    this.canPlace = null
    this.canPlaceSelf = null
    // XXX this only appears to be used by tests
    this.checks = new Map()
    this.children = []
    this.needEvaluation = new Set()
    this.peerConflict = null
    this.placed = null
    this.target = null

    this.current = this.edge.to
    this.name = this.edge.name
    this.top = this.parent?.top || this

    // nothing to do if the edge is fine as it is
    if (this.edge.to &&
        !this.edge.error &&
        !this.explicitRequest &&
        !this.updateNames.includes(this.edge.name) &&
        !this.auditReport?.isVulnerable(this.edge.to)) {
      return
    }

    // walk up the tree until we hit either a top/root node, or a place
    // where the dep is not a peer dep.
    const start = this.getStartNode()

    for (const target of start.ancestry()) {
      // if the current location has a peerDep on it, then we can't place here
      // this is pretty rare to hit, since we always prefer deduping peers,
      // and the getStartNode will start us out above any peers from the
      // thing that depends on it.  but we could hit it with something like:
      //
      // a -> (b@1, c@1)
      // +-- c@1
      // +-- b -> PEEROPTIONAL(v) (c@2)
      //     +-- c@2 -> (v)
      //
      // So we check if we can place v under c@2, that's fine.
      // Then we check under b, and can't, because of the optional peer dep.
      // but we CAN place it under a, so the correct thing to do is keep
      // walking up the tree.
      const targetEdge = target.edgesOut.get(this.edge.name)
      if (!target.isTop && targetEdge && targetEdge.peer) {
        continue
      }

      const cpd = new CanPlaceDep({
        dep: this.dep,
        edge: this.edge,
        // note: this sets the parent's canPlace as the parent of this
        // canPlace, but it does NOT add this canPlace to the parent's
        // children.  This way, we can know that it's a peer dep, and
        // get the top edge easily, while still maintaining the
        // tree of checks that factored into the original decision.
        parent: this.parent && this.parent.canPlace,
        target,
        preferDedupe: this.preferDedupe,
        explicitRequest: this.explicitRequest,
      })
      this.checks.set(target, cpd)

      // It's possible that a "conflict" is a conflict among the *peers* of
      // a given node we're trying to place, but there actually is no current
      // node.  Eg,
      // root -> (a, b)
      // a -> PEER(c)
      // b -> PEER(d)
      // d -> PEER(c@2)
      // We place (a), and get a peer of (c) along with it.
      // then we try to place (b), and get CONFLICT in the check, because
      // of the conflicting peer from (b)->(d)->(c@2).  In that case, we
      // should treat (b) and (d) as OK, and place them in the last place
      // where they did not themselves conflict, and skip c@2 if conflict
      // is ok by virtue of being forced or not ours and not strict.
      if (cpd.canPlaceSelf !== CONFLICT) {
        this.canPlaceSelf = cpd
      }

      // we found a place this can go, along with all its peer friends.
      // we break when we get the first conflict
      if (cpd.canPlace !== CONFLICT) {
        this.canPlace = cpd
      } else {
        break
      }

      // if it's a load failure, just plop it in the first place attempted,
      // since we're going to crash the build or prune it out anyway.
      // but, this will frequently NOT be a successful canPlace, because
      // it'll have no version or other information.
      if (this.dep.errors.length) {
        break
      }

      // nest packages like npm v1 and v2
      // very disk-inefficient
      if (this.installStrategy === 'nested') {
        break
      }

      // when installing globally, or just in global style, we never place
      // deps above the first level.
      if (this.installStrategy === 'shallow') {
        const rp = target.resolveParent
        if (rp && rp.isProjectRoot) {
          break
        }
      }
    }

    // if we can't find a target, that means that the last place checked,
    // and all the places before it, had a conflict.
    if (!this.canPlace) {
      // if not forced, and it's our dep, or strictPeerDeps is set, then
      // this is an ERESOLVE error.
      if (!this.force && (this.isMine || this.strictPeerDeps)) {
        return this.failPeerConflict()
      }

      // ok!  we're gonna allow the conflict, but we should still warn
      // if we have a current, then we treat CONFLICT as a KEEP.
      // otherwise, we just skip it.  Only warn on the one that actually
      // could not be placed somewhere.
      if (!this.canPlaceSelf) {
        this.warnPeerConflict()
        return
      }

      this.canPlace = this.canPlaceSelf
    }

    // now we have a target, a tree of CanPlaceDep results for the peer group,
    // and we are ready to go

    /* istanbul ignore next */
    if (!this.canPlace) {
      debug(() => {
        throw new Error('canPlace not set, but trying to place in tree')
      })
      return
    }

    const { target } = this.canPlace

    log.silly(
      'placeDep',
      target.location || 'ROOT',
      `${this.dep.name}@${this.dep.version}`,
      this.canPlace.description,
      `for: ${this.edge.from.package._id || this.edge.from.location}`,
      `want: ${redact(this.edge.spec || '*')}`
    )

    const placementType = this.canPlace.canPlace === CONFLICT
      ? this.canPlace.canPlaceSelf
      : this.canPlace.canPlace

    // if we're placing in the tree with --force, we can get here even though
    // it's a conflict.  Treat it as a KEEP, but warn and move on.
    if (placementType === KEEP) {
      // this was a peerConflicted peer dep
      if (this.edge.peer && !this.edge.valid) {
        this.warnPeerConflict()
      }

      // if we get a KEEP in a update scenario, then we MAY have something
      // already duplicating this unnecessarily!  For example:
      // ```
      // root (dep: y@1)
      // +-- x (dep: y@1.1)
      // |   +-- y@1.1.0 (replacing with 1.1.2, got KEEP at the root)
      // +-- y@1.1.2 (updated already from 1.0.0)
      // ```
      // Now say we do `reify({update:['y']})`, and the latest version is
      // 1.1.2, which we now have in the root.  We'll try to place y@1.1.2
      // first in x, then in the root, ending with KEEP, because we already
      // have it.  In that case, we ought to REMOVE the nm/x/nm/y node, because
      // it is an unnecessary duplicate.
      this.pruneDedupable(target)
      return
    }

    // we were told to place it here in the target, so either it does not
    // already exist in the tree, OR it's shadowed.
    // handle otherwise unresolvable dependency nesting loops by
    // creating a symbolic link
    // a1 -> b1 -> a2 -> b2 -> a1 -> ...
    // instead of nesting forever, when the loop occurs, create
    // a symbolic link to the earlier instance
    for (let p = target; p; p = p.resolveParent) {
      if (p.matches(this.dep) && !p.isTop) {
        this.placed = new Link({ parent: target, target: p })
        return
      }
    }

    // XXX if we are replacing SOME of a peer entry group, we will need to
    // remove any that are not being replaced and will now be invalid, and
    // re-evaluate them deeper into the tree.

    const virtualRoot = this.dep.parent
    this.placed = new this.dep.constructor({
      name: this.dep.name,
      pkg: this.dep.package,
      resolved: this.dep.resolved,
      integrity: this.dep.integrity,
      installLinks: this.installLinks,
      legacyPeerDeps: this.legacyPeerDeps,
      error: this.dep.errors[0],
      ...(this.dep.overrides ? { overrides: this.dep.overrides } : {}),
      ...(this.dep.isLink ? { target: this.dep.target, realpath: this.dep.realpath } : {}),
    })

    this.oldDep = target.children.get(this.name)
    if (this.oldDep) {
      this.replaceOldDep()
    } else {
      this.placed.parent = target
    }

    // if it's a peerConflicted peer dep, warn about it
    if (this.edge.peer && !this.placed.satisfies(this.edge)) {
      this.warnPeerConflict()
    }

    // If the edge is not an error, then we're updating something, and
    // MAY end up putting a better/identical node further up the tree in
    // a way that causes an unnecessary duplication.  If so, remove the
    // now-unnecessary node.
    if (this.edge.valid && this.edge.to && this.edge.to !== this.placed) {
      this.pruneDedupable(this.edge.to, false)
    }

    // in case we just made some duplicates that can be removed,
    // prune anything deeper in the tree that can be replaced by this
    for (const node of target.root.inventory.query('name', this.name)) {
      if (node.isDescendantOf(target) && !node.isTop) {
        this.pruneDedupable(node, false)
        // only walk the direct children of the ones we kept
        if (node.root === target.root) {
          for (const kid of node.children.values()) {
            this.pruneDedupable(kid, false)
          }
        }
      }
    }

    // also place its unmet or invalid peer deps at this location
    // loop through any peer deps from the thing we just placed, and place
    // those ones as well.  it's safe to do this with the virtual nodes,
    // because we're copying rather than moving them out of the virtual root,
    // otherwise they'd be gone and the peer set would change throughout
    // this loop.
    for (const peerEdge of this.placed.edgesOut.values()) {
      if (peerEdge.valid || !peerEdge.peer || peerEdge.peerConflicted) {
        continue
      }

      const peer = virtualRoot.children.get(peerEdge.name)

      // Note: if the virtualRoot *doesn't* have the peer, then that means
      // it's an optional peer dep.  If it's not being properly met (ie,
      // peerEdge.valid is false), then this is likely heading for an
      // ERESOLVE error, unless it can walk further up the tree.
      if (!peer) {
        continue
      }

      // peerConflicted peerEdge, just accept what's there already
      if (!peer.satisfies(peerEdge)) {
        continue
      }

      this.children.push(new PlaceDep({
        auditReport: this.auditReport,
        explicitRequest: this.explicitRequest,
        force: this.force,
        installLinks: this.installLinks,
        installStrategy: this.installStrategy,
        legacyPeerDeps: this.legaycPeerDeps,
        preferDedupe: this.preferDedupe,
        strictPeerDeps: this.strictPeerDeps,
        updateNames: this.updateName,
        parent: this,
        dep: peer,
        node: this.placed,
        edge: peerEdge,
      }))
    }
  }

  replaceOldDep () {
    const target = this.oldDep.parent

    // XXX handle replacing an entire peer group?
    // what about cases where we need to push some other peer groups deeper
    // into the tree?  all the tree updating should be done here, and track
    // all the things that we add and remove, so that we can know what
    // to re-evaluate.

    // if we're replacing, we should also remove any nodes for edges that
    // are now invalid, and where this (or its deps) is the only dependent,
    // and also recurse on that pruning.  Otherwise leaving that dep node
    // around can result in spurious conflicts pushing nodes deeper into
    // the tree than needed in the case of cycles that will be removed
    // later anyway.
    const oldDeps = []
    for (const [name, edge] of this.oldDep.edgesOut.entries()) {
      if (!this.placed.edgesOut.has(name) && edge.to) {
        oldDeps.push(...gatherDepSet([edge.to], e => e.to !== edge.to))
      }
    }

    // gather all peer edgesIn which are at this level, and will not be
    // satisfied by the new dependency.  Those are the peer sets that need
    // to be either warned about (if they cannot go deeper), or removed and
    // re-placed (if they can).
    const prunePeerSets = []
    for (const edge of this.oldDep.edgesIn) {
      if (this.placed.satisfies(edge) ||
          !edge.peer ||
          edge.from.parent !== target ||
          edge.peerConflicted) {
        // not a peer dep, not invalid, or not from this level, so it's fine
        // to just let it re-evaluate as a problemEdge later, or let it be
        // satisfied by the new dep being placed.
        continue
      }
      for (const entryEdge of peerEntrySets(edge.from).keys()) {
        // either this one needs to be pruned and re-evaluated, or marked
        // as peerConflicted and warned about.  If the entryEdge comes in from
        // the root or a workspace, then we have to leave it alone, and in that
        // case, it will have already warned or crashed by getting to this point
        const entryNode = entryEdge.to
        const deepestTarget = deepestNestingTarget(entryNode)
        if (deepestTarget !== target &&
            !(entryEdge.from.isProjectRoot || entryEdge.from.isWorkspace)) {
          prunePeerSets.push(...gatherDepSet([entryNode], e => {
            return e.to !== entryNode && !e.peerConflicted
          }))
        } else {
          this.warnPeerConflict(edge, this.dep)
        }
      }
    }

    this.placed.replace(this.oldDep)
    this.pruneForReplacement(this.placed, oldDeps)
    for (const dep of prunePeerSets) {
      for (const edge of dep.edgesIn) {
        this.needEvaluation.add(edge.from)
      }
      dep.root = null
    }
  }

  pruneForReplacement (node, oldDeps) {
    // gather up all the now-invalid/extraneous edgesOut, as long as they are
    // only depended upon by the old node/deps
    const invalidDeps = new Set([...node.edgesOut.values()]
      .filter(e => e.to && !e.valid).map(e => e.to))
    for (const dep of oldDeps) {
      const set = gatherDepSet([dep], e => e.to !== dep && e.valid)
      for (const dep of set) {
        invalidDeps.add(dep)
      }
    }

    // ignore dependency edges from the node being replaced, but
    // otherwise filter the set down to just the set with no
    // dependencies from outside the set, except the node in question.
    const deps = gatherDepSet(invalidDeps, edge =>
      edge.from !== node && edge.to !== node && edge.valid)

    // now just delete whatever's left, because it's junk
    for (const dep of deps) {
      dep.root = null
    }
  }

  // prune all the nodes in a branch of the tree that can be safely removed
  // This is only the most basic duplication detection; it finds if there
  // is another satisfying node further up the tree, and if so, dedupes.
  // Even in installStategy is nested, we do this amount of deduplication.
  pruneDedupable (node, descend = true) {
    if (node.canDedupe(this.preferDedupe)) {
      // gather up all deps that have no valid edges in from outside
      // the dep set, except for this node we're deduping, so that we
      // also prune deps that would be made extraneous.
      const deps = gatherDepSet([node], e => e.to !== node && e.valid)
      for (const node of deps) {
        node.root = null
      }
      return
    }
    if (descend) {
      // sort these so that they're deterministically ordered
      // otherwise, resulting tree shape is dependent on the order
      // in which they happened to be resolved.
      const nodeSort = (a, b) => localeCompare(a.location, b.location)

      const children = [...node.children.values()].sort(nodeSort)
      for (const child of children) {
        this.pruneDedupable(child)
      }
      const fsChildren = [...node.fsChildren].sort(nodeSort)
      for (const topNode of fsChildren) {
        const children = [...topNode.children.values()].sort(nodeSort)
        for (const child of children) {
          this.pruneDedupable(child)
        }
      }
    }
  }

  get isMine () {
    const { edge } = this.top
    const { from: node } = edge

    if (node.isWorkspace || node.isProjectRoot) {
      return true
    }

    if (!edge.peer) {
      return false
    }

    // re-entry case.  check if any non-peer edges come from the project,
    // or any entryEdges on peer groups are from the root.
    let hasPeerEdges = false
    for (const edge of node.edgesIn) {
      if (edge.peer) {
        hasPeerEdges = true
        continue
      }
      if (edge.from.isWorkspace || edge.from.isProjectRoot) {
        return true
      }
    }
    if (hasPeerEdges) {
      for (const edge of peerEntrySets(node).keys()) {
        if (edge.from.isWorkspace || edge.from.isProjectRoot) {
          return true
        }
      }
    }

    return false
  }

  warnPeerConflict (edge, dep) {
    edge = edge || this.edge
    dep = dep || this.dep
    edge.peerConflicted = true
    const expl = this.explainPeerConflict(edge, dep)
    log.warn('ERESOLVE', 'overriding peer dependency', expl)
  }

  failPeerConflict (edge, dep) {
    edge = edge || this.top.edge
    dep = dep || this.top.dep
    const expl = this.explainPeerConflict(edge, dep)
    throw Object.assign(new Error('could not resolve'), expl)
  }

  explainPeerConflict (edge, dep) {
    const { from: node } = edge
    const curNode = node.resolve(edge.name)

    // XXX decorate more with this.canPlace and this.canPlaceSelf,
    // this.checks, this.children, walk over conflicted peers, etc.
    const expl = {
      code: 'ERESOLVE',
      edge: edge.explain(),
      dep: dep.explain(edge),
      force: this.force,
      isMine: this.isMine,
      strictPeerDeps: this.strictPeerDeps,
    }

    if (this.parent) {
      // this is the conflicted peer
      expl.current = curNode && curNode.explain(edge)
      expl.peerConflict = this.current && this.current.explain(this.edge)
    } else {
      expl.current = curNode && curNode.explain()
      if (this.canPlaceSelf && this.canPlaceSelf.canPlaceSelf !== CONFLICT) {
        // failed while checking for a child dep
        const cps = this.canPlaceSelf
        for (const peer of cps.conflictChildren) {
          if (peer.current) {
            expl.peerConflict = {
              current: peer.current.explain(),
              peer: peer.dep.explain(peer.edge),
            }
            break
          }
        }
      } else {
        expl.peerConflict = {
          current: this.current && this.current.explain(),
          peer: this.dep.explain(this.edge),
        }
      }
    }

    return expl
  }

  getStartNode () {
    // if we are a peer, then we MUST be at least as shallow as the peer
    // dependent
    const from = this.parent?.getStartNode() || this.edge.from
    return deepestNestingTarget(from, this.name)
  }

  // XXX this only appears to be used by tests
  get allChildren () {
    const set = new Set(this.children)
    for (const child of set) {
      for (const grandchild of child.children) {
        set.add(grandchild)
      }
    }
    return [...set]
  }
}

module.exports = PlaceDep