Current report

Dependencies for crates today can be separated into two categories: those that are implementation details and those whose types are present in the public API of the crate. Cargo does not support distinguishing these two cases today, but it can often be crucial for dependency management.

If a dependency is an implementation detail (i.e. no types are exposed) then it can be easily duplicated in the dependency graph without worry (other than concerns like binary size). In other words, Cargo's safe to have multiple semver-incompatible versions of this dependency because they won't talk with one another.

If a dependency is part of the public API, however, then it's critical that any crate which can share this type it needs to all be of the same version. In other words, Cargo's logic of allowing multiple semver-incompatible versions is almost always guaranteed to go awry.

If Cargo were to understand a distinction between these private/public (or internal/exposed) dependencies then it could solve problems like:

• Provide much nicer resolution error messages rather than relying on the compiler to figure this out.
• Restructure the crate DAG to ensure that dependencies which work with multiple major versions end up working with other crates that only require one major version.
• Ensure that crate resolution never picks too many versions of a crate and instead forces common dependencies to all have the same version.

Original report

Cargo is overeager to pull in multiple copies of a crate

Say we have a crate with the following Cargo.toml:

[package]
name = "foo"
version = "0.1.0"
authors = ["Steven Fackler <sfackler@gmail.com>"]

[dependencies]
postgres = "0.9"
r2d2_postgres = "0.9"

r2d2_postgres version 0.9.3 depends on postgres version 0.10, while version 0.9.2 and lower depend on postgres version 0.9. Cargo would ideally pick r2d2_postgres version 0.9.2 and postgres version 0.9.6, but it instead picks r2d2_postgres version 0.9.3, which pulls in postgres version 0.10, as well as postgres version 0.9.6. This ends up totally blocking any use of these dependencies.

This issue rather significantly impedes crates' abilities to upgrade their dependencies.

It seems like Cargo's resolution logic should have the property that if there exists a resolved dependency graph with no more than one copy of each dependency, it should never pull in more than one copy of a dependency. Unfortunately, questions like "does such a resolved dependency graph exist" are NP-complete, but I suspect that it's tractable in practice (we don't expect crates to be randomly permuting their dependencies every minor version, for example).

In the meantime before someone has a chance to integrate a SAT solver into Cargo, I think there are some things we can do to help users correct Cargo when it fails to resolve things "properly". For example, cargo update could warn whenever it has to pull in multiple copies of a crate, identifying the portion of the object graph that forced that to happen. This should provide users an easier starting point to poking the graph into shape with cargo update --precise.