Arborist.buildIdealTree refactor and overrides exploration

[isaacs]

Epic

• Move _canPlace and _canPlaceDep methods to their own classes.

  This is already done, but included for context.

• Move _nodeFromEdge, _nodeFromSpec, and all "virtual root" handling to a new class that handles creating a new node in a temporary tree (maybe "temp tree" is better naming than "virtual root", since "virtual" means "loaded from shrinkwrap"?)

• Write some docs and draw some pictures to figure out the algorithm for tracking and implementing overrides. Some thoughts and likely direction, which is not a spec and may not match where it actually ends:

  • Overrides can extend through the dependency graph, which impacts what can be deduped against what. So for example, {"foo@1": {".": "2.0.0","bar@1":"1.2.3"},"bar@1":"2.3.4"} would override all versions of bar that are a dependency (or transitive dep) of a foo@1 node that gets changed to [email protected]. Any other version of bar@1 is overridden to [email protected]. If the root package and foo both depend on baz, which depends on bar@1, then we cannot dedupe foo's baz against the root's baz, because they have to get different versions of bar. This is the sort of thing that has to be considered when implementing the algorithm for it.
  • Once some of this theoretical exploration has been done, and documented, the implementation will likely need to track the override data on the node and edge classes somehow, so that things like node.satisfies(edge) and node.canReplace(otherNode) still do the right thing, to minimize the overall scope of what has to be changed.
  • The application of "should this override apply to this node" will have to happen in the _nodeFromEdge/_nodeFromSpec code paths described above, because we have to resolve the thing to know if it would be a match to whatever override is applying at the given spot in the ideal tree resolution.
  • We also have to apply overrides to specs in the loadActual and loadVirtual flows, so that npm ls can show when overrides are not properly respected, and buildIdealTree can see those edges as improper matches and fix them.

• implement overrides