Yarn: Use SAT solver to resolve peer dependencies

[yunxing]

Imagine this case where we have:

{
  "name": "A",
  "version": "0.0.1"
  "peerDependencies": {
    "B": "0.0.1"
  }
}

{
  "name": "A",
  "version": "0.0.2"
  "peerDependencies": {
    "B": "0.0.2"
  }
}

{
  "name": "X",
  "version": "0.0.1"
  "dependencies": {
    "A": "*",
    "B": "0.0.1"
  }
}

With our current resolver, installing package "X" will pick [email protected] and [email protected], create a peer dependency conflict on B, as [email protected] requires [email protected].

A better resolving semantics here is to be smart about which version of A to pick, and pick [email protected] instead. This requires to use a SAT solver, which is what meteor is using.

[yunxing]

Had some discussion offline.

In a lot of situations, we really want to resolve a package with only one version, especially for the case of peerDeps.

Perfect dependency resolution is a np complete problem, but we can learn from what meteor is doing by wrapping a logic-solver with semver.

This however, changes npm semver semantics, which always fetches latest version that satisfies the constraints for each package. But I think fundamentally this is better than npm's current model.

@jordwalke

[jordwalke]

This however, changes npm semver semantics, which always fetches latest version that satisfies the constraints for each package. But I think fundamentally this is better than npm's current model.

I totally agree that it's better. It might not match the "latest" semantics, but at the same time it's _correct_ where npm is _incorrect_. There are cases where npm _incorrectly_ says "no solution" (to peerDeps) when there is a solution.

[dxu]

a small update in case anyone is interested, I've implemented a quick/dirty solution (that isn't integrated) that would be an example of what a solution using the logic solver might look like. It seems to be able to solve the possible dependency combinations on yunxing's small original test case. You can view the changes here (it's a PR into my own fork). The logic solver lives in package-constraint-solver.js, which contains some code (addPackage) for fetching all package metadata, and some code (solve and solvePackage) that builds up the logic primitives themselves.

Note that the branch will not actually install the packages - it just prints out the possible dependency combinations. Integrating it into the pipeline will require a lot more work, because it'll have to completely change how the package resolver -> package request -> registry resolvers pipeline works for flat installs (see more details below). Also, it doesn't yet have pricing heuristics on which dependency combination would work best (which is arguably more complex). However, it should give you a sense of how a logic solver approach would look.

Because of this, this test case will only work if you already have an existing package.json, because otherwise it'll error when you try to run yarn add, since I've temporarily broken the rest of the pipeline.

The original test case is as follows:

1. First create a package.json file with the following contents:

{
  "dependencies": {
    "@yunxing-test/c": "~0.0.1"
  }
}

1. Run yarn install --flat in the directory. You should see something along the following lines:

★ yarn install --flat
yarn install v0.15.1
info No lockfile found.
warning No license field
[1/4] 🔍  Resolving packages...
⡀ @yunxing-test/afinished solving dependency solutions
[ [ '@yunxing-test/a 0.0.1', '@yunxing-test/c 0.0.2' ],
  [ '@yunxing-test/a 0.0.1',
    '@yunxing-test/b 0.0.1',
    '@yunxing-test/c 0.0.3' ],
  [ '@yunxing-test/a 0.0.1',
    '@yunxing-test/b 0.0.1',
    '@yunxing-test/c 0.0.1' ],
  [ '@yunxing-test/a 0.0.1',
    '@yunxing-test/b 0.0.1',
    '@yunxing-test/c 0.0.2' ] ]
error An unexpected error occured, please open a bug report with the information provided in "/Users/dxu/code/fb/testSOlver2/yarn-error.log".
info Visit https://yarnpkg.com/en/docs/cli/install for documentation about this command.

Printed are the possible solutions. You can visually inspect the solutions by viewing the package metadata for yunxing-test here: c, b, a.

Also, the error is expected, since all this does is solve and print out the possible solutions. I haven't tested it further, but even if there's an error in my logic, it should be fairly simple to model a dependency graph in terms of logical relationships. The actual code for setting up the logic is surprisingly simple.

I've annotated it a bit, but please ask if you see problems or can't follow it. I've created a pull request into my own fork for easier commenting.

[Disclaimer] - the code isn't completely flow-ified, it's fairly hacked up so spacing, style, declarations, etc. will not be perfect, though it shouldn't be hard to follow. There is a decent amount of integration work to be done for this to actually work. You have to frontload all the metadata requests in order to precompute the dependency graph prior to actually using in the logic solver. Currently, this implementation just short-circuits the entire package request -> registry/exotic resolver flow, adds some package metadata fetching code, and just hard codes the NPM resolver so I could test the logic solver.

I attempted multiple times to integrate into the current flow, but the logic was getting too convoluted because the original algorithm fetches package metadata as it traverses the dependency tree. It seemed like it would be too messy to try to reuse the flow, and there was no guarantee that we would be able to prevent unnecessary individual package requests.

[dxu]

Some progress has been made on the above fork. It currently is mostly integrated, and works with simple repos.

There is still possibly a fair amount of work left. Things that need to be done for certain:

1. Handle devdependencies - currently it's only flattening the dependencies. Should be as simple as just calling solve on the different parts of the original package.json within the package-resolver.find() method.
2. Fix a small bug with the cost heuristic - integers that become to large cause an integer overflow, which causes the cost to be negative, which the solver can't handle. Just need to modify the cost function to not be exponential, or add a max weight
3. There are a number of failing test cases, included in a zip file on the above fork.
   
   
   
   1. There are a few test cases that generate a "missing manifest" error during the hoisting phase. I probably missed something during the integration that is causing issues down the line.
   
   
   2. There are some test cases that are just unable to find solutions. For some of them, I've often narrowed it down to groups of maybe 10 or less packages (often out of thousands) that merely fail because there are conflicting explicit versions.
   
   
   3. Some test cases fail to find solutions, but theoretically (???) should work. One example is the opam-alpha/ocaml package, which is included in folder 13 of the zip file. According to Yunxing, this should be a valid package, so I don't know why it doesn't work at this point in time, and I also don't entirely know how it's calculating its dependencies.
   
   
4. I've only really tested npm out of all top level resolvers, and git, out of all exotic resolvers. Hopefully we can roll this out in waves of support, first prioritizing npm and the corresponding exotic resolvers, since I imagine flatten should be a fairly niche use case, at least at this point in time.
5. A lot of TODO's in the code itself, reminders for myself to clean up or implement new things.
6. Flowify everything. I wanted to get something working asap to test this, so i unfortunately wasn't as careful with types, as some of this work will involve modifying core types.
7. Tests.

Some findings:

1. lots of repos specify explicit versions, which causes the solver to fail. This happens quite often, even with seemingly small repos, because of their dependencies.
2. The cost heuristic needs tuning, and probably a larger discussion on what is valued. Currently, I take into account (very simply) levels in the dependency graph, and recency of package in relation to each package's total set of versions. Even with just two metrics, there are a number of nuances to think about.

[josephecombs]

For whatever it's worth, deleting yarn.lock and deleting all the compiled node_modules (and then, since I am using webpack, deleting the webpack build folder) resolved this issue for me. Obviously this is just treating a symptom.

[reem]

This is stopping me from using yarn in production, which is very sad because it's really great in pretty much every other way!

[bestander]

Well help us to get this feature in.
The logic is a bit spread between classes but you can start herehttps://github.com/yarnpkg/yarn/blob/master/src/package-resolver.js#L396.
Another good start is writing a test and submitting a PR with expectation how it should work

[jedwards1211]

@yunxing

This requires to use a SAT solver, which is what meteor is using.
Interesting, do you mean for installing meteor packages or for installing npm packages?