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


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 ``

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 ``
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!


Cross link reddit and internals

I had a situation that got stuck on "Resolving dependency graph..." for minutes and I don't even know if it would ever solve. In nightly it solves pretty quickly, so congratulations!

Also I just hit a different situation where the resolver would error and in nightly it works.

Thanks for testing it out. I am glad it is helping!

If "pretty quickly" is slow enough for me to throw a profiler on it I'd love to take a look.

For the other situation what error is stable hitting? I just want to be sure we have test to make sure your real use does not regress.

I've put both cases up in a repo, hope they are useful!