cargo: Cargo fails to find minimal satisfiable set of dependencies

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.

About this issue

Original URL
State: closed
Created 6 years ago
Reactions: 1
Comments: 17 (15 by maintainers)

Commits related to this issue

Auto merge of #4978 - Eh2406:master, r=alexcrichton Only allow one of each links attribute in resolver This is a start on fixing the `links` part of #4902. It needs code that adds the links attribut... — committed to rust-lang/cargo by bors 6 years ago

Most upvoted comments

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

The resolver will include 2 sys crates even though it is not going to be able to build the result. This was resolved in #4978
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.
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.

Eh2406 on Sep 17, 2018

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.

alexcrichton on Jan 5, 2018