Major-open semver range does not properly unify with closed semver ranges

[CAD97]

Problem

If a dependency's version is constrained to cover multiple semver-incompatible releases, the version selected does not unify with more specific restrictions from elsewhere in the build graph. E.g. a requirement for >=0.0.0, <0.9.0 and a requirement for ^0.4.0 results in both version 0.4.x and 0.8.y being pulled in (or 0.4.x and 0.1.0 with -Zminimal-versions), rather than unifying both versions to just 0.4.x.

Manually adjusting the lockfile to use 0.4.x in both cases works as expected; this is just an issue with the "find the best solution" codepath, not the "check the lockfile satisfies" codepath.

Originally reported by @MaximilianKoestler on URLO: https://users.rust-lang.org/t/crate-interoperability-and-3rd-party-types-in-interfaces/53431

Steps

Repro from @MaximilianKoestler : https://github.com/MaximilianKoestler/crate-version-testing

Using the rgb crate as our target, this is exemplified using just the three packages:

[package]
name = "lib_a"

[dependencies]
rgb = ">=0.4.0, <0.5.0"

[package]
name = "lib_b"

[dependencies]
rgb = ">=0.0.0, <0.9.0"

[package]
name = "bin_c"

[dependencies]
lib_a = { path = "../lib_a" }
lib_b = { path = "../lib_b" }

The generated lockfile:

# irrelevant parts removed and reordered
[[package]]
name = "lib_a"
dependencies = [
 "rgb 0.4.0",
]

[[package]]
name = "lib_b"
dependencies = [
 "rgb 0.8.25",
]

[[package]]
name = "bin_c"
dependencies = [
 "lib_a",
 "lib_b",
]

[[package]]
name = "rgb"
version = "0.4.0"
source = "registry+https://github.com/rust-lang/crates.io-index"

[[package]]
name = "rgb"
version = "0.8.25"
source = "registry+https://github.com/rust-lang/crates.io-index"

Possible Solution(s)

Ideally, if all constraints overlap, only a single version should be selected. Otherwise, maintaining support for old semver-incompatible versions of public dependencies (when the subset you're using didn't change) is almost meaningless, as cargo won't unify the dependency off of the most recent semver-compatible range (or first with -Zminimal-versions).

Notes

Output of cargo version: cargo 1.50.0-nightly (75d5d8cff 2020-12-22) (also occurs on stable)

[Eh2406]

Thank you for the clear description and reproducible example!
Cargos resolver (with in the one-per-major constraints) attempts to optimize for "getting everyone the most recent they can use" and does not optimize for "have the fewest versions".
I can not think of how to make the current resolver flexible over this optimization target. If pubgrub gets incorporated into Cargo things may be more flexible.

It may be possible to make an iterative optimization procedure.

[CAD97]

Cargos resolver (with in the one-per-major constraints) attempts to optimize for "getting everyone the most recent they can use" and does not optimize for "have the fewest versions".

Understandable, and almost certainly the correct target for private dependencies. Just very unfortunate for public dependencies, where it's not so much wanting to "have the fewest versions" as wanting not to "expected type rgb::RGBA, found type rgb::RGBA".

Perhaps this is another thing that could/should be tied to public/private dependencies. Currently, marking the dependencies as public panics on unimplemented ConflictReason::PublicDependency.

[Eh2406]

Yes, public/private dependencies would be a good more general solution for this problem. If you hit that panic then there is not solution for those constraints or there is a bug in resolving public/private dependencies ( which would not be surprising, there is a reason it is unstable).

[CAD97]

Definitely some bugs remaining; manually creating a lockfile with just rgb:0.4.0 works just fine.

[wpd]

I wonder if this issue could be addressed by extending the [patch] feature of Cargo.
Maybe something like this? (for the example above)

[patch.crates.io]
lib_a.dependencies.rgb = "=0.4.0"
lib_b.dependencies.rgb = "=0.4.0"

This would patch the rgb dependency in the lib_a crate to say "force the version to 0.4.0". Similar for lib_b's dependency on rgb. I like this approach because it is clear that the programmer is patching something that has already been published, and therefore the programmer is taking responsibility for ensuring that the lib_a and lib_b crates function properly in her/his application.

[pkgw]

Perhaps this should be a different issue, but the Dependency Resolver section of the Cargo Book doesn't mention this aspect of the current resolver, which led me to be very confused about another instance of the behavior described here. Since it seems like this behavior will continue to happen for a while, it "would be nice"™ if the book discussed it.

[Eh2406]

As the one who was just looking for this information, and having trouble finding it, you are in the best position to guide us on how to improve the documentation.
Where would you expect this section to go? What would you expect it to say?
If you have the time, documentation PR's are always welcome.

[pkgw]

PR submitted as #11604.