Lockfile concerns

I wanted to open up this issue as a discussion item. I don't think there's anything blockery about this concern (more below), but I do think that the structure of the lockfile will become problematic in the long term.

First, here's a quick example of one of the consequences of the problem, from Yarn's own lockfile:

wordwrap@~0.0.2:
  version "0.0.3"
  resolved "https://registry.npmjs.org/wordwrap/-/wordwrap-0.0.3.tgz#a3d5da6cd5c0bc0008d37234bbaf1bed63059107"
[email protected]:
  version "0.0.2"
  resolved "https://registry.npmjs.org/wordwrap/-/wordwrap-0.0.2.tgz#b79669bb42ecb409f83d583cad52ca17eaa1643f"

There are two dependencies described here (wordwrap ~0.0.2 and wordwrap =0.0.2). Both of them are satisfied by wordwrap 0.0.2, but instead we get two different packages.

This doesn't always happen; there is some code that tries to "dedup" packages:

xtend@^4.0.0, "xtend@>=4.0.0 <4.1.0-0", xtend@~4.0.0:
  version "4.0.1"
  resolved "https://registry.npmjs.org/xtend/-/xtend-4.0.1.tgz#a5c6d532be656e23db820efb943a1f04998d63af"

But it's hardly the only example:

rimraf@^2.2.8, rimraf@^2.4.3, rimraf@^2.4.4, rimraf@^2.5.0, rimraf@~2.5.0, rimraf@~2.5.1, rimraf@2:
  version "2.5.4"
  resolved "https://registry.npmjs.org/rimraf/-/rimraf-2.5.4.tgz#96800093cbf1a0c86bd95b4625467535c29dfa04"
  dependencies:
    glob "^7.0.5"
rimraf@~2.2.6:
  version "2.2.8"
  resolved "https://registry.npmjs.org/rimraf/-/rimraf-2.2.8.tgz#e439be2aaee327321952730f99a8929e4fc50582"

The rimraf ^2.2.8 dependency could unify with rimraf ~2.2.6, but it doesn't.

Worse:

recast@^0.10.0, recast@^0.10.10:
  version "0.10.43"
  resolved "https://registry.npmjs.org/recast/-/recast-0.10.43.tgz#b95d50f6d60761a5f6252e15d80678168491ce7f"
  dependencies:
    ast-types "0.8.15"
    esprima-fb "~15001.1001.0-dev-harmony-fb"
    private "~0.1.5"
    source-map "~0.5.0"
[email protected]:
  version "0.10.33"
  resolved "https://registry.npmjs.org/recast/-/recast-0.10.33.tgz#942808f7aa016f1fa7142c461d7e5704aaa8d697"
  dependencies:
    ast-types "0.8.12"
    esprima-fb "~15001.1001.0-dev-harmony-fb"
    private "~0.1.5"
    source-map "~0.5.0"

All of these versions of recast could unify to recast =0.10.33, but instead we get two copies of recast.

Another example:

once@^1.3.0, [email protected]:
  version "1.4.0"
  resolved "https://registry.npmjs.org/once/-/once-1.4.0.tgz#583b1aa775961d4b113ac17d9c50baef9dd76bd1"
  dependencies:
    wrappy "1"
once@~1.3.0, once@~1.3.3:
  version "1.3.3"
  resolved "https://registry.npmjs.org/once/-/once-1.3.3.tgz#b2e261557ce4c314ec8304f3fa82663e4297ca20"
  dependencies:
    wrappy "1"

All of these patterns can unify to once 1.3.3, but we get two copies.

Hopefully I've made my point

The current yarn strategy successfully unifies dependencies opportunistically, but doesn't have any backtracking mechanism, which is necessary for the unification opportunities described above. It also doesn't provide any way for resolvers to participate in the necessary backtracking. This means that even if we successfully unify the graph we have now via post-processing, there are likely even better opportunities that we'll miss.

The major change in the lockfile format I propose is that the lockfile represents a graph of packages, where the entries are exact package identifiers. This is a change from the current format, where the lockfile is a list of patterns and associated packages.

The reason I think the current status isn't an urgent priority is that a list of seen patterns and associated packages is still deterministic, which is the number one priority of the lockfile. Lower priorities, like conservative updating (yarn update some-pkg changes the minimal necessary subgraph) depend on a more traditional lockfile, but we can work on it over time.

Ultimately, I think a simplified version of the Cargo strategy (the Cargo strategy supports a nice optional dependency mechanism called "features" which we don't support, and which complicates the algorithm somewhat) is the right way to go. The Cargo strategy is a refined version of the Bundler strategy, which was also used (and further refined) by Cocoapods. The Cargo strategy adds support for package duplication, which is necessary (and desired) in the Node ecosystem.

This would mean version-bumping the Yarn lockfile, but the good news is that Yarn's lockfile is already versioned, so this should be fine.

The Rough Strategy

Here's a rough description of the algorithm. (it's slightly modified from Cargo and Bundler's algorithm because of the amount of duplication expected as a matter of course in the npm ecosystem).

Dependency resolution always starts with a top-level package.json, which has a list of dependencies.

Each dependency (once@~1.3.0) expands to a set of possible packages, determined by querying all of the available registries. If a dependency describes a non-registry source (a git repo or tarball, for example), the dependency expands to a set of just one package (in bundler, this is called a "pinned" dependency).

The first step in the algorithm adds a list of all dependencies in the top-level package.json to a remaining dependencies list as a tuple of (dependency, candidate-list).

Initialize an all packages Map whose keys are package names and whose values are Sets of all available packages with that name.

Repeatedly activate a dependency by popping a dependency from the list of remaining dependencies:

• if a dependency is already satisfied by the existing set of activated packages, continue
• otherwise, pick a candidate for the dependency;
  • restrict the set of all packages with the name of the dependency to the set of packages that match the dependency.
  • add it to the set of activated packages
  • link the activated package in the graph to the parent package the dependency came from
  • recursively activate it

If a dependency cannot be unified with an existing instance of the same package, consider backtracking if:

• the set of all packages still available contains packages that could satisfy the dependency
• the dependency is a peer dependency
• the package is marked flat

If the --flat flag was passed to yarn, always backtrack if a dependency cannot be satisfied with an existing package with the same name in the set of activated packages. This will effectively turn the algorithm into Bundler, which guarantees the "highlander rule" ("there can be only one" package per name in the graph).

Keep going until the set of remaining dependencies is empty. At this point, a complete graph of unique packages will exist, and be ready to be written out to a lockfile.

A note about backtracking: because dependency graphs with thousands of packages are common, it is not advisable to use recursion when implementing this algorithm in a language with limited stack depth. Instead, we would maintain a side stack (see the same algorithm in Cargo) that allows us to implement the recursive algorithm without blowing the stack.