Expand description
Resolution of the entire dependency graph for a crate.
This module implements the core logic in taking the world of crates and constraints and creating a resolved graph with locked versions for all crates and their dependencies. This is separate from the registry module which is more worried about discovering crates from various sources, this module just uses the Registry trait as a source to learn about crates from.
Actually solving a constraint graph is an NP-hard problem. This algorithm is basically a nice heuristic to make sure we get roughly the best answer most of the time. The constraints that we’re working with are:
- Each crate can have any number of dependencies. Each dependency can declare a version range that it is compatible with.
- Crates can be activated with multiple version (e.g., show up in the dependency graph twice) so long as each pairwise instance have semver-incompatible versions.
The algorithm employed here is fairly simple, we simply do a DFS, activating the “newest crate” (highest version) first and then going to the next option. The heuristics we employ are:
- Never try to activate a crate version which is incompatible. This means we only try crates which will actually satisfy a dependency and we won’t ever try to activate a crate that’s semver compatible with something else activated (as we’re only allowed to have one) nor try to activate a crate that has the same links attribute as something else activated.
- Always try to activate the highest version crate first. The default
dependency in Cargo (e.g., when you write
foo = "0.1.2") is semver-compatible, so selecting the highest version possible will allow us to hopefully satisfy as many dependencies at once.
Beyond that, what’s implemented below is just a naive backtracking version which should in theory try all possible combinations of dependencies and versions to see if one works. The first resolution that works causes everything to bail out immediately and return success, and only if nothing works do we actually return an error up the stack.
Performance
Note that this is a relatively performance-critical portion of Cargo. The data that we’re processing is proportional to the size of the dependency graph, which can often be quite large (e.g., take a look at Servo). To make matters worse the DFS algorithm we’re implemented is inherently quite inefficient. When we add the requirement of backtracking on top it means that we’re implementing something that probably shouldn’t be allocating all over the place.
Re-exports
pub use self::features::CliFeatures;pub use self::features::ForceAllTargets;pub use self::features::HasDevUnits;Modules
Structs
Cargo.lock structure.PackageIds.Enums
resolver field in the manifest.Cargo.lock should be serialized. Currently
V2 is the default when creating a new lockfile. If a V1 lockfile already
exists, it will stay as V1.