Dependency conflict resolution contains false positives

[FredKSchott]

kpm's current semver resolution logic leads to false positives in transitive dependencies, requiring unnecessary user interaction. Conflict resolution may no longer be needed once dependent parents have been resolved out of the dependency graph. However these conflicts are still bubbled up to the user to be resolved, potentially incorrectly.

Contrived Example 🍎 🍰

"dependencies": {
  "apple-pie": "^2.0.0",
  "pie-crust": "^1.0.0"
}

$ kpm i --flat
kpm install v0.11.2
info No lockfile found.
[1/4] 🚚  Resolving and fetching packages...
We found a version in package pie-crust that we couldn't resolve
1. 1.0.0
2. 2.0.0
Please select a version you'd like to use?: 2
We found a version in package flour that we couldn't resolve
1. 1.0.0
2. 2.0.0
Please select a version you'd like to use?: 2
We found a version in package sugar that we couldn't resolve
1. 1.0.0
2. 2.0.0
Please select a version you'd like to use?: 2 
We found a version in package butter that we couldn't resolve
1. 2.0.0
2. 1.0.0
Please select a version you'd like to use?: 2
[2/4] 🔗  Linking dependencies...
[3/4] 📃  Building fresh packages...
[4/4] ♻️  Cleaning modules...
success Saved lockfile to kpm.lock
✨  Done in 19.10s.

Based on a True Story

Here's an actual example of two conflicting npm dependencies with conflicting transitive dependencies if you'd like to see this in action. The above was contrived from this setup.

-─┬ @polymer/paper-behaviors@0.0.3 
  ├─┬ @polymer/iron-behaviors@0.0.3 
  │ └── @polymer/iron-a11y-keys-behavior@0.0.3 
  ├─┬ @polymer/iron-checked-element-behavior@0.0.3 
  │ ├── @polymer/iron-form-element-behavior@0.0.3 
  │ └─┬ @polymer/iron-validatable-behavior@0.0.3 
  │   └── @polymer/iron-meta@0.0.3 
  └── @polymer/paper-ripple@0.0.3 

"dependencies": {
  "@polymer/paper-behaviors": "^0.0.3",
  "@polymer/iron-checked-element-behavior": "0.0.1"
}

What Happened?

• top level dependency pie-crust requires v1.x.x versions of its dependencies all the way down
• top level dependency apple-pie requires v2.x.x versions of its dependencies all the way down, including pie-crust@v2.x.x
• A full dependency tree was resolved for each top level dependency
• All unresolvable conflicts (4) between those two trees were detected
• The user was asked to resolve each of them

Expected user resolution prompts: pie-crust
Actual user resolution prompts: pie-crust, flour, sugar, butter

This is bad because only the top level resolution was needed/expected. Once pie-crust was resolved to either v1.0.0 or v2.0.0, all of its dependencies would have been transitively resolved as well. Resolving each of these manually can be tedious and potentially dangerous if the user accidentally resolves a constraint to a version that is no longer referenced anywhere in the flattened dependency graph. (ex: pie-crust@v2.0.0 & flour@v1.0.0).

kpm will also display these conflicts in an undefined order, which can add to the confusion (user has to resolve a transitive dependency conflict before seeing the parent dependency conflict that caused it).

[sebmck]

We can fix this by iterating over conflicting dependencies in topological order and then filtering them out if their existence was invalidated by a previous selection and they've been pruned from the tree.

[sebmck]

What are the expected and actual resolution prompts for your polymer dependency example?

[FredKSchott]

The kpm output for the real life example is similar to the contrived example, just with real package names.

$ kpm i --flat
kpm install v0.11.2
info No lockfile found.
[1/4] 🚚  Resolving and fetching packages...
We found a version in package @polymer/iron-form-element-behavior that we couldn't resolve
1. 0.0.1
2. 0.0.3
Please select a version you'd like to use?: 2
We found a version in package @polymer/iron-meta that we couldn't resolve
1. 0.0.1
2. 0.0.3
Please select a version you'd like to use?: 2
We found a version in package @polymer/iron-validatable-behavior that we couldn't resolve
1. 0.0.1
2. 0.0.3
Please select a version you'd like to use?: 2
We found a version in package @polymer/iron-checked-element-behavior that we couldn't resolve
1. 0.0.1
2. 0.0.3
Please select a version you'd like to use?: 2
[2/4] 🔗  Linking dependencies...
[3/4] 📃  Building fresh packages...
[4/4] ♻️  Cleaning modules...
success Saved lockfile to kpm.lock
✨  Done in 32.03s.

Instead of asking for all 4 resolutions, I'd expect to only be asked for the resolution to iron-checked-element-behavior. Resolving that constrain resolves the other 3 by association.

[FredKSchott]

I think filtering is a great start, but there will still be a risk of false positives. A resolution made at the end of the process could simplify the graph in a way that automatically resolves a previous conflict.

Example:

1. The version constraint for top level dependency A (A1) conflicts with another constraint (A2) found "lower" in the graph.
2. User is asked to resolve this.
3. Later in the process, A2's dependent is resolved out of the graph (either through user resolution or automatic resolution) in favor of a different version that doesn't have constraint A2.
4. A2 no longer exists in the dependency graph, which means the first user resolution was unnecessary (and the user could have chosen incorrectly).

So this kind of false positive will appear if there are resolutions that depend on future resolutions. You would be able to reproduce this in the OP examples if sugar or @polymer/iron-meta were added as top level dependencies.

FWIW, bower doesn't handle this scenario either. I just realized the screenshot below doesn't actually illustrate the issue because iron-checked-element-behavior#v1.0.0 satisfies paper-behaviors constraint instead of conflicting. Instead the false positives are because bower isn't attempting to auto-resolve based on previous resolutions. Interesting...

// bower.json
"dependencies": {
  "paper-behaviors": "PolymerElements/paper-behaviors#1.0.12",
  "iron-meta": "PolymerElements/iron-meta#0.8.2",
  "iron-checked-element-behavior": "PolymerElements/iron-checked-element-behavior#1.0.0"
},

[sebmck]

Reopening, didn't really solve this. I think there's a way to make this nicer by having special ordering of dependencies to ensure that the ones that will have the most impact/relevance to the user are shown at the top.