Abort crate resolution if too many candidates have been tried

[alexcrichton]

We should have a hard limit for the number of steps the resolution algorithm can take before it just hard aborts and exits saying "this probably isn't gonna work".

Right now the crate resolution algorithm will only return an error if it proves that literally every possible crate resolution graph is not workable. This can take quite a long time for some larger graphs! Ideally we'd also abort with nice error messages "these tended to conflict a lot" etc, but at the very least Cargo shouldn't look like it's infinite looping.

[brson]

I also see this with https://github.com/koute/cargo-web

This is a new development that I have not seen before and it has caused cargobomb to stop working because it hangs when building the lockfile for that crate.

[brson]

cc @koute

[brson]

I'm not sure on how this behavior would have begun to appear on stable between the last cargobomb and this cargobomb run. Both should have run the generate-lockfiles phase using the same stable compiler.

Hm...

[brson]

Oh cargobomb should kill this process after a lengthy timeout. I probably just need to wait 10 minutes or so. So maybe cargobomb is still working and this is not a new behavior for cargo.

[brson]

cargobomb doesn't seem to be timing out. Just hanging forever.

[alexcrichton]

@brson does this reproduce on cargo-web? O rwas this related to something else?

[koute]

@alexcrichton If you try to do cargo build in cargo-web it just hangs indefinitely.

It looks like upgrading hyper-rustls from 0.3 to at least 0.5 fixes the issue. (It starts to compile properly again.) Also, if in my Cargo.toml I change:

hyper-rustls = "0.3"

into:

hyper-rustls = "0.3.3"

it also fixes the hanging and instead spews out this error:

error: no matching version `^0.10` found for package `webpki` (required by `rustls`)
location searched: registry https://github.com/rust-lang/crates.io-index
versions found: 0.12.1

I've already pushed a fix to master, but in case you'd want to reproduce this issue again you can use commit 3b17eff93402bfd160ee944932aedb45298a0421.

[alexcrichton]

@koute I think that's an example of an un-resolvable resolution graph again as well (what this issue is). All versions of webpki but the most recent are yanked, so if you need to update a dependency on webpki there's nothing to choose from.

[drandreaskrueger]

Is this related? cargo install parity needs 4 hours ... to find out it can't.

[alexcrichton]

@drandreaskrueger ah yeah unfortunately that's this issue :(

[drandreaskrueger]

thx, @alexcrichton ... 6 hours now ;-)

[sunshowers]

Just chiming in here a little bit -- FB has been hitting this problem for a couple of months now. This prevents us from updating our pseudocrate which contains all our third-party dependencies.

Has there been any discussion around using a SAT or SMT solver like Z3 for dependency resolution? I found #2064 which has some brief discussion, but the only substantive thing there appears to be Graydon's test which shows how to offload semver optimization to Z3.

(I generally believe that people should be reaching for SAT solvers far more often than they do today.)

[alexcrichton]

@Sid0 there's been discussion of "we should probably do it" but no serious design of how it would actually be done yet.

Also to be clear, this issue is primarily about "this crate graph is not resolvable, and Cargo isn't quickly telling you that". In more cases than not we've found today that if there's a resolvable graph Cargo will reach it quickly-ish. Not true for all cases, but true for most. We likely want a different issue for "this crate graph can be resolved can Cargo can take forever to conclude that"

[sunshowers]

Hmm, interesting. Is it possible for a Cargo.toml that just has a bunch of * dependencies like in https://gist.github.com/sid0/064738981955029054d74de50c90c49f to lead to an unresolvable graph?

[alexcrichton]

IIRC last I investigate an apparent deadlock w/ y'alls Cargo.toml it was a case of "cargo takes too long to reach the right solution" rather than "there is no solution", so you'd fall in the category of "we'd benefit from a SAT solver" for sure! (my memory may be hazy though)

[sunshowers]

Yeah -- that matches my understanding as well.

FWIW I've had a cargo update running on our Cargo.toml for the last 90 minutes or so. Still hasn't completed :)

[alexcrichton]

Heh you may have more luck with ctrl-c :) (in that each time Cargo resolves it may take different paths, so new resolutions may complete quicker).

Note though that the crate graph may still be unresolvable for whatever reason, it's not guaranteed to be resolvable even with * dependencies.

[alexcrichton]

why do we not pull in multiple semver-compatible versions of a crate if necessary? I think that if it's a private dependency (as defined in #2064) it should be safe.

You're 100% correct! Right now the thinking is that we're "somewhat in the middle" between the npm strategy of duplicate everything and the rubygems strategy of "only one version of anything". That is, we were initially wary to go the npm route of allowing duplicates everywhere because of binary size blowup concerns, but we wanted to be more flexible than rubygems by allowing multiple version to coexist.

Additionally, though, up to this point we haven't actually had the knowledge of public/private dependencies. My hope is that as soon as we have public/private dependencies we can lift the restriction here and allow semver-compatible duplicates in a dependency graph, so long as the public/shared types all have the same version number.

This is an ecosystem change that would need to be carefully communicated and managed, but hopefully it will make upstreams more careful and the crates.io ecosystem healthier overall.

Yeah I don't think we've done a great job discouraging usage of the ~ operator and encouraging "semver compatible", I think we can definitely do better here!

[jacwah]

Natalie Weizenbaum talked about how they intend to solve this same problem in the Dart package manager on a recent episode of The Manifest. I'll drop a link if anyone is interested: https://manifest.fm/5. It sound like it is in early research stages, but boils down to using a version of DPLL.

[fenollp]

Hopefully the solution to this issue will be concurrent. It can take ages and also uses only one of my many cores! Is it taunting me? :)

EDIT: happening while building git@github.com:gnunicorn/clippy-service.git with cargo 0.24.0-nightly (5bb478a51 2017-11-29).
EDIT: no progress after 59 hours (haha)

[Eh2406]

This I think would just involve changing:

cargo/src/cargo/core/resolver/mod.rs

Line 684 in 0be926d

if config.shell().is_err_tty() && !printed && ticks % 1000 == 0

to bail if ticks gets to big. Extra credit to make to big an argument up to the user.

I am still learning cargo internals, but I would be willing to help someone who wanted to take this on!

[Eh2406]

@dwijnand want to pick this one off next :-)

[dwijnand]

Alright, I'll have a go.

[dwijnand]

Ok, I've tried about 4-5 different reproduction in or linked to here and everything's either succeeded or failed fast. 😄 Probably due to the related fixed that have landed.

Does anyone have a reproduction that fails with recent cargo?

[Eh2406]

Sorry, I should have clarified that. I don't know of any that are currently slow. I think I have gone thru every bug report to look for them, I was unable to reproduce or have fixed the resolver for each. (Mostly by reading up on suggestions made in hear.) Then I spent several days fuzzing to find them, nothing over 40 second and then only because I disable one of the Fixes by accident.

So at this point anything that takes more then say a minute, and more than 5_000_000 ticks is something I would like to see! So I'd like there to be cargo to stop and report "It is always possible that this is valid but taking a long time, but It is probably a bug so please report it".

The reason for the message is that legitimately I want to know and fix if anyone hits a new bad case in use.
The reason to stop is that it will probably come up in a CI/Build Server type context and I want people to see it. Including the tests for the fixes I have made, currently if you comment out any of the fixes then the test sweet hangs, it would be better for it to error.

[dwijnand]

Ah, right, I see! I'll have a look at those tests and try and work off those. Thanks for the info.

[Eh2406]

#5921 added something like this with hard coded stops that is using debug_asserts. So this would now involve making them configurable and return an error.