Cargo got some new tricks, but is it still correct!?

tools and infrastructure
1

TLDR:

Please try cargo +stable generate-lockfile and let us know if it is different than what you get with current nightly cargo +nightly generate-lockfile!

Long form:

I have been working with @alexcrichton to improve the resolver in Cargo.

For example we worked on error messages:

Before, there was little context about where deep in your dependencies Cargo had trouble:

>cargo +stable generate-lockfile

    Updating registry `https://github.com/rust-lang/crates.io-index`

error: failed to select a version for `kernel32-sys` (required by `named_pipe`):

all possible versions conflict with previously selected versions of `kernel32-sys`

  version 0.2.1 in use by kernel32-sys v0.2.1

  possible versions to select: 0.2.2

Now, a full path to the root:

>cargo +nightly generate-lockfile
    Updating registry `https://github.com/rust-lang/crates.io-index`
error: failed to select a version for `time`.
    ... required by package `chrono v0.3.0`
    ... which is depended on by `mysql v11.3.1`
    ... which is depended on by `rust v0.0.1 (file:///C:/.../speedtest2)`

versions that meet the requirements `^0.1.36` are: 0.1.39, 0.1.38, 0.1.37, 0.1.36
all possible versions conflict with previously selected packages.

  previously selected package `time v0.1.34`

    ... which is depended on by `rust v0.0.1 (file:///C:/.../speedtest2)`

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

PR’s: #5037, #5025, and #5126 in witch @gilescope reused the structure to improve the case package “depends on itself”

We also worked on making resolver recover from more errores. PR #5000 allows the resolver to backtrack if it finds an older version of a package that does not have a feature you asked for. PR #4978 allows the resolver to backtrack if you have two -sys crates that have the same links attribute. (For now this also requires that both the -sys crates be published with a recent nightly.) Currently, Cargo will generate a .lock file but then it won’t be able to build the project.

We worked with @klausi to implement the long awaited -Z minimal-versions PR #5200. This tells cargo to try to get as close as possible to the oldest version of your dependencies as your Cargo.toml allows. This is intended to be used during CI for a library to insure that it can be built with everything it claims to be able to build with. This feature is much awaited!

Last but not least, there were a lot of reported bugs where Cargo would hang apparently indefinitely on various sets of dependencies. One approach we tried was to watch it with a profiler and make it try candidates faster. PR’s #5157, #5150, #5147, #5121, #5132, #5118, #5112, #5044 this lead to going from 17,500 candidates/sec to 227,000 candidates/sec that is more than an order of magnitude improvement. The other approach we tried was to build on the work of @aidanhs to let Cargo try fewer candidates. This involved bringing ideas, mostly Conflict-Driven Clause Learning, from the established “SAT” solving community and finding a way to add them to the existing code without messing up the error messages. PR’s #5213, #5187, #5168, #4834 This involved “Backjumping”, making sure when we find a problem we backtrack far enough to have a chance of not hitting the same problem again, and Caching, making sure we do not try things that have proven not to work in this context. This has lead to every one of those issues being closed; as every single one completed in under a second on master.

BUT the resolver is a complicated and tricky beast. Many times in this process I have said things that I was absolutely sure were true, only to have them proven wrong. For example:

I am absolutely sure that all real use cases for Cargo generate-lockfile will complete rapidly with a current nightly. (It is an SAT solver and NP-complete so if you are a jerk you can get it to go slowly. Hence the “real”.) Also:

I am absolutely sure that if cargo +stable generate-lockfile works then cargo +nightly generate-lockfile will get the same result.

If you can show I am wrong Please file an Issue now so I can fix it before this goes into beta!

2

Cross link reddit and users

3

I was wondering, have you looked into plugging in a generic SAT solver to replace cargo’s one-off?

4

Yes, but there is a lot of things that need to be figured out to get it to work. We don’t just need A solution to your dependencies, we need the one with the newest version. So we don’t just need a generic SAT solver we need a MAX-SAT solver. Next, it has to run on all platforms that Cargo is built for. That means solvers in rust or solvers with a really straight forward build system. Next it needs to be able to add constraints lazaly. Otherwize we need to build out the problem in terms of all versions of all reachable dependencies in advance, witch is in most cases more work then solving the problem. Also the solver needs to handle strict OR conditions efficiently, most do but not all. Lastly we need to convert the unsuccessful output of the solver back into good error messages that talk about the domain, packages and versions and things.

All doable, but not as easy as it first appears.

5

Scanned my projects:

#!/bin/bash
for i in */Cargo.lock; do (
    cd $(dirname $i);
    pwd
    cargo +stable  generate-lockfile 2> /dev/null && cp Cargo.lock Cargo.lock.stable
    cargo +nightly generate-lockfile 2> /dev/null && cp Cargo.lock Cargo.lock.nightly
    cmp Cargo.lock.stable Cargo.lock.nightly
    rm Cargo.lock.{nightly,stable}
) done

No differences were found across about 20 directories.

$ cargo +stable --version
cargo 0.26.0 (41480f5cc 2018-02-26)
$ cargo +nightly --version
cargo 1.26.0-nightly (d63299b6e 2018-03-28)
6

Relevant to the “general solver” discussion: Natalie Weizenbaum just posted an interesting write-up of PubGrub, a new version constraint solver used in the “pub” package manager for the Dart language. Notably it includes the ability to generate detailed error explanations, like:

Because dropdown >=2.0.0 depends on icons >=2.0.0 and root depends
  on icons <2.0.0, dropdown >=2.0.0 is forbidden.

And because menu >=1.1.0 depends on dropdown >=2.0.0, menu >=1.1.0
  is forbidden.

And because menu <1.1.0 depends on dropdown >=1.0.0 <2.0.0 which
  depends on intl <4.0.0, every version of menu requires intl
  <4.0.0.

So, because root depends on both menu >=1.0.0 and intl >=5.0.0,
  version solving failed.
4 Likes
7

Thank you for that link! I opened an issue on cargo

8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.