resolver error messages as good as PubGrub

[Eh2406]

On internals I was informed about the great blog post introducing PubGrub.

We have an ad hoc implementation of most of the conflict clause parts. The learning parts are questionable do to the "sudoku" problem, it is often faster to prove something is wrong by trying it then by rigorous argument.

But PubGrub uses its data structures to report much more in its error messages. Getting grate error messages that are inspired by are best competition is one of rusts great strengths.
We should get our error messages to be as good as PubGrub's, if we need to by using their algorithm (as the blog post suggested.)

[matklad]

PubGrub docs: https://github.com/dart-lang/pub/blob/4947e0b3cb3ec77e4e8fe0d3141ce4dc60f43256/doc/solver.md

Should we .... rewrite it in Rust? :-)

[killercup]

Hm, glancing over the post it looks like their algorithm requires at most one version per dependency in the tree? If that's the case I'm not sure it works well for cargo, where you can depend on 4 different versions of nom if you so desire.

[Eh2406]

Well yes that does make the docs hard to read. But, an algorithm for one version per name can be converted to a more flexible algorithm by append the major version number to the name.

[killercup]

@Eh2406, well… here's a counter example:

• A 1.0 depends on B ^1.2.2
• C 1.0 depends on B =1.0.1

But anyway, I absolutely agree that we should make cargo's error messages and its resolution algorithm in general easier to comprehend.

[matklad]

@killercup I believe your example won't be resolved by current Cargo as well. I haven’t checked that though, so I might be wrong here :-)

In today’s Cargo, there is a restriction that the dependency graph can’t contain semver-compatible duplicates. That is, you can’t have both foo 1.2 and foo 1.3, however it is perfectly fine to have foo 1.2 and foo 2.5.

I think the way this is implemented in Cargo is by treating semver incompatible versions the same as different packages. That is, Cargo has the exact same restriction as Pubgrub.

And this is not exactly what we want here, actually! Ideally, Cargo should be aware about different major versions, and should be able to minimize the total number of packages!

That is, if, today, one of your dependencies depends on foo 1.0, and another needs foo >= 1.0, <= 2.0 (that is, it is compatible with two major versions), Cargo will pull in both 1.0 and 2.0, while only 1.0 should be enough.

[killercup]

Interesting. You're right, @matklad!

$ cargo new cargo-resolve-test
$ cd cargo-resolve-test
$ cargo new --lib a
$ cd a
$ cargo add serde
$ cd ..
$ cargo new --lib b
$ cd b
$ cargo add serde --vers "=1.0.1"
$ cd ..
$ cargo add a --path a
$ cargo add b --path b
$ cargo check
    Updating registry `https://github.com/rust-lang/crates.io-index`
error: failed to select a version for `serde`.
    ... required by package `b v0.1.0 (file:///Users/pascal/Projekte/cargo-resolve/b)`
    ... which is depended on by `cargo-resolve v0.1.0 (file:///Users/pascal/Projekte/cargo-resolve)`
versions that meet the requirements `= 1.0.1` are: 1.0.1

all possible versions conflict with previously selected packages.

  previously selected package `serde v1.0.37`
    ... which is depended on by `a v0.1.0 (file:///Users/pascal/Projekte/cargo-resolve/a)`
    ... which is depended on by `cargo-resolve v0.1.0 (file:///Users/pascal/Projekte/cargo-resolve)`

failed to select a version for `serde` which could resolve this conflict

[Eh2406]

By the way progress is being made on a Rust rewrite! Discussion at:

• https://rust-lang.zulipchat.com/#narrow/stream/260232-t-cargo.2FPubGrub and
• https://rust-lang.zulipchat.com/#narrow/stream/246057-t-cargo/topic/PubGrub.20algorithm.20discussion

and the code is at:

• https://github.com/pubgrub-rs/pubgrub