-
Notifications
You must be signed in to change notification settings - Fork 2.7k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Use SAT solver to resolve peer dependencies #422
Comments
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. |
I totally agree that it's better. It might not match the "latest" semantics, but at the same time it's correct where |
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 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 Because of this, this test case will only work if you already have an existing The original test case is as follows:
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. |
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:
Some findings:
|
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. |
This is stopping me from using yarn in production, which is very sad because it's really great in pretty much every other way! |
Well help us to get this feature in. |
|
Imagine this case where we have:
With our current resolver, installing package "X" will pick A@0.0.2 and B@0.0.1, create a peer dependency conflict on B, as A@0.0.2 requires B@0.0.2.
A better resolving semantics here is to be smart about which version of A to pick, and pick A@0.0.1 instead. This requires to use a SAT solver, which is what meteor is using.
The text was updated successfully, but these errors were encountered: