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
Resolve
into a TOML Cargo.lock
fileStructs
Cargo.lock
structure.Context
of
a dependency graph.PackageId
s.Enums
resolver
field in the manifest.Cargo.lock
should be serialized.Functions
candidate
in the context cx
.summaries
, in depth-first order,
backtracking across possible candidates for each dependency as necessary.backtrack_stack
for dependencies with
remaining candidates. For each one, also checks if rolling back
could change the outcome of the failed resolution that caused backtracking
in the first place. Namely, if we’ve backtracked past the parent of the
failed dep, or any of the packages flagged as giving us trouble in
conflicting_activations
.find_candidate
feather then the input one.
It will add the new conflict to the cache if one is found.