Cargo fails to find minimal satisfiable set of dependencies

[SergioBenitez]

I'm currently experiencing an issue where Cargo selects two different versions of a -sys crate when one version of the -sys crate is enough to satisfy dependency constraints. In my particular case, my Cargo.toml [dependencies] look like:

[dependencies]
rusqlite = "0.13"
diesel = { version = "1.0", features = ["sqlite"] }

Both crates depend on libsqlite3-sys. Here's what they list in their dependency section:

// diesel 1.0
libsqlite3-sys = { version = ">=0.8.0, <0.10.0", optional = true, features = ["min_sqlite_version_3_7_16"] }

// rusqlite 0.13
[dependencies.libsqlite3-sys]
version = "0.9"

Here's what Cargo decides for these constraints:

[dependencies]
├── diesel v1.0.0
│   └── libsqlite3-sys v0.8.1
└── rusqlite v0.13.0
    └─── libsqlite3-sys v0.9.1

Or, as seen from Cargo.lock:

[[package]]
name = "diesel"
version = "1.0.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
dependencies = [
 "libsqlite3-sys 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
]

[[package]]
name = "libsqlite3-sys"
version = "0.8.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
dependencies = [
 "pkg-config 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
 "vcpkg 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
]

[[package]]
name = "libsqlite3-sys"
version = "0.9.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
dependencies = [
 "pkg-config 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
 "vcpkg 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
]

[[package]]
name = "rusqlite"
version = "0.13.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
dependencies = [
 "libsqlite3-sys 0.9.1 (registry+https://github.com/rust-lang/crates.io-index)",
]

This is a suboptimal choice. What's worse, because this is a -sys dependency, this causes compilation to fail needlessly. The optimal, correct decision is to choose libsqlite3-sys 0.9.1 for both dependencies.

[karuna]

package `libsqlite3-sys v0.8.1`
    ... which is depended on by `diesel v1.0.0`
    ... which is depended on by `rocket_contrib v0.4.0-dev (file:///home/karuna/workspace/rocket/contrib)`
    ... which is depended on by `uuid v0.1.0 (file:///home/karuna/workspace/rocket/examples/uuid)`
links to native library `sqlite3`

package `libsqlite3-sys v0.9.1`
    ... which is depended on by `rusqlite v0.13.0`
    ... which is depended on by `rocket_contrib v0.4.0-dev (file:///home/karuna/workspace/rocket/contrib)`
    ... which is depended on by `uuid v0.1.0 (file:///home/karuna/workspace/rocket/examples/uuid)`
also links to native library `sqlite3`

@SergioBenitez are we working on the same issue (pooling) ? lol

[alexcrichton]

Thanks for the report @SergioBenitez! Right now I think this is two bugs in Cargo playing into effect:

• First and foremost, the "only one sys crate" restriction only happens in later stages in Cargo. Notably crate graph resolution does not take this into account. (but it should!) As a result Cargo isn't making any resolution/version selection decisions based on links.

• Next up Cargo also doesn't attempt (currently) to optimize the crate graph. Cargo does a greedy search with a few heuristics and basically returns the crate graph as soon as it finds anything that matches. We could certainly (I think) have a pass to postprocess a crate graph to attempt to minimize it or otherwise add this to various heuristics.

[SergioBenitez]

@alexcrichton Have you considered removing all heuristics from Cargo in exchange for using an optimizing SMT solver to get an optimal set of dependencies? I read in some other issue that z3 was proposed long ago, but I didn't see that discussion develop further.

I would be open to leading the implementation of such an overhaul, though I won't have the necessary bandwidth for some time.

[alexcrichton]

@SergioBenitez yes it's been discussed from time to time but never too seriously. I'm mostly of the opinion that it appears like a panacea and yet is likely to take quite a bit of effort to reach feature/speed parity with the current algortihm. Additionally I don't think it'd actually affect this issue. The problem here is that a constraint isn't encoded into resolution, not that we can't encode it into resolution. A real sat solver AFAIK would only bring a possible benefit of speed in degenerate cases Cargo hits today.

[SergioBenitez]

@alexcrichton Using an optimizing SMT solver would solve this issue as the optimal set of dependencies is the correct one. There wouldn't be a special case here, nor a need to encode a specific constraint.

I've run into quite a few cases over the years where Cargo makes an incorrect or suboptimal choice; using an SMT solver would bring my fears that Cargo is liable to do that to rest. It's possible that using something like z3 would slow things down, but z3 has been heavily tuned over the years, so it's at least worth a shot, in my opinion.

[alexcrichton]

Actually moving to someting like a real solver is a pretty huge investment, so I'm not really the one to make such a decision. It would be @rust-lang/cargo which would weigh in on such a decision.

[wycats]

@alexcrichton the biggest issue with using an off-the-shelf solver, in my experience, is getting good error messages when something goes wrong. My second biggest concern is making sure whatever we take a dependency on is reliable and not something we're going to regret down the road.

Before committing to using an off-the-shelf solution, I would want to see a prototype that handled strictly more cases than Cargo correctly, and produced actionable error messages. I would also want some confidence that we could continue to refine and improve the error messages over time.

[Eh2406]

First and foremost, the "only one sys crate" restriction only happens in later stages in Cargo. Notably crate graph resolution does not take this into account. (but it should!) As a result Cargo isn't making any resolution/version selection decisions based on links.

What is involved in adding this? If we can make the info available during resolution then I think it is just adding the test to resolve RemainingCandidates::next. But I don't know how to make the info available.

[alexcrichton]

@Eh2406 unfortunately it's not a very trivial change at this point. The index is all Cargo has during crate graph resolution and the index doesn't encode the links manifest key, so Cargo doesn't actually have this information for any crates from crates.io. That'd be the first thing to fix and the next would be editing src/cargo/core/resolver/mod.rs to take this into account, but that's also unfortunately not an easy task.

[Eh2406]

Is it possible to add info to the index in a backwards compatible way? If so we can add that info for crates published into the future. Older -sys crates would still have the current broken behavior, but new ones can opt into better resolution.

I think I understand src/cargo/core/resolver/mod.rs to prevent resolving two crates with the same links attribute.

[alexcrichton]

Yeah we'd in general just have to assume that anything missing such a key in the index doesn't have it, and it'd act as if it does today. If we feel the need we could retroactively fill the registry but we probably wouldn't do that to start out.

[Eh2406]

If we add a key to the index will old versions of cargo stop working? Specifically will they return an error when the json is not the shape it has always been?

[alexcrichton]

@Eh2406 nah in general Cargo's relatively lenient about parsing the registry, if there's a key it doesn't undrestand in the blobs it'd just ignore the key. So long as we're additive in what's inserted it shouldn't be a problem!

[wycats]

cc @joshtriplett re: new key leniency

[joshtriplett]

Thanks, @wycats.

I've had mixed experiences with adding new keys in the Cargo registry and having older versions choke. Please test this explicitly, including with both old and current versions of Cargo. If you add it in the right place, it shouldn't cause issues; if you add it in the wrong place, Cargo will break even if it doesn't care about that crate version.

[stale]

As there hasn't been any activity here in over 6 months I've marked this as stale and if no further activity happens for 7 days I will close it.

I'm a bot so this may be in error! If this issue should remain open, could someone (the author, a team member, or any interested party) please comment to that effect?

The team would be especially grateful if such a comment included details such as:

• Is this still relevant?
• If so, what is blocking it?
• Is it known what could be done to help move this forward?

Thank you for contributing!

(The cargo team is currently evaluating the use of Stale bot, and using #6035 as the tracking issue to gather feedback.)

If you're reading this comment from the distant future, fear not if this was closed automatically. If you believe it's still an issue please leave a comment and a team member can reopen this issue. Opening a new issue is also acceptable!

[Eh2406]

Thanks stale bot for bringing this to my attention. I will close it now. This issue has 3 parts.

1. The resolver will include 2 sys crates even though it is not going to be able to build the result. This was resolved in Only allow one of each links attribute in resolver #4978
2. The resolver does not optimize for minimum number of crates. That is true, and intentional, the resolver optimizes to get the most recent version for each dependency. This will only get more cleare if the private dependency RFC gets implemented.
3. The resolver uses heuristics instead of a out of the box SAT solver. This is not as easy as it first appears. Some of the issues are discussed above, more are in other discussions. While I will continue to follow all progress towards having a SAT solver crate we can just use, it does not look likely to happen.