Module resolver

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:

1. Each crate can have any number of dependencies. Each dependency can declare a version range that it is compatible with.
2. 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.

Resolution is currently performed twice

1. With all features enabled (this is what gets saved to Cargo.lock)
2. With only the specific features the user selected on the command-line. Ideally this run will get removed in the future when transitioning to the new feature resolver.

A new feature-specific resolver was added in 2020 which adds more sophisticated feature resolution. It is located in the features module. The original dependency resolver still performs feature unification, as it can help reduce the dependencies it has to consider during resolution (rather than assuming every optional dependency of every package is enabled). Checking if a feature is enabled must go through the new feature resolver.

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

• conflict_cache 🔒
• context 🔒
• dep_cache 🔒
  There are 2 sources of facts for the resolver:
• encode 🔒
  Definition of how to encode a Resolve into a TOML Cargo.lock file
• errors 🔒
• features
  Resolves conditional compilation for features section in the manifest.
• resolve 🔒
• types 🔒
• version_prefs 🔒
  This module implements support for preferring some versions of a package over other versions.

Structs

• BacktrackFrame 🔒
• EncodableDependency
• EncodablePackageId
• EncodableResolve
  The Cargo.lock structure.
• RemainingCandidates 🔒
  A helper “iterator” used to extract candidates within a current Context of a dependency graph.
• Resolve
  Represents a fully-resolved package dependency graph. Each node in the graph is a package and edges represent dependencies between packages.
• ResolveError
  Error during resolution providing a path of PackageIds.
• ResolveOpts
  Options for how the resolve should work.
• VersionPreferences
  A collection of preferences for particular package versions.

Enums

• ActivateError
• ResolveBehavior
  Resolver behavior, used to opt-in to new behavior that is backwards-incompatible via the resolver field in the manifest.
• ResolveVersion
  A version to indicate how a Cargo.lock should be serialized.
• VersionOrdering

Functions

• activate 🔒
  Attempts to activate the summary candidate in the context cx.
• activate_deps_loop 🔒
  Recursively activates the dependencies for summaries, in depth-first order, backtracking across possible candidates for each dependency as necessary.
• check_cycles 🔒
• check_duplicate_pkgs_in_lockfile 🔒
  Checks that packages are unique when written to lock file.
• find_candidate 🔒
  Looks through the states in 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.
• generalize_conflicting 🔒
  Attempts to find a new conflict that allows a find_candidate better then the input one. It will add the new conflict to the cache if one is found.
• resolve
  Builds the list of all packages required to build the first argument.
• shortcircuit_max 🔒
  Returns Some of the largest item in the iterator. Returns None if any of the items are None or the iterator is empty.

Type Aliases

• ActivateResult
• Metadata