Version solving

Version solving consists in finding a set of packages and versions that satisfy all the constraints of a given project dependencies. In Rust, it is the package manager Cargo that takes the dependencies specified in the Cargo.toml file and deduces the complete list of exact versions of packages needed for your code to run. That includes direct dependencies but also indirect ones, which are dependencies of your dependencies. Packages and versions are not restricted to code libraries though. In fact they could refer to anything where "packages" act as a general name for things, and "versions" describe the evolution of those things. Such things could be office documents, laws, cooking recipes etc. Though if you version cooking recipes, well you are a very organized person.

Semantic versioning

The most common form of versioning scheme for dependencies is called semantic versioning. The base idea of semantic versioning is to provide versions as triplets of the form Major.Minor.Patch such as 2.4.1. The "semantic" term comes from the meaning of each part of the versioning system. Publishing a new patch version, for example from 2.4.1 to 2.4.2 means no interface has changed in the provided API of the library. That may be the case for documentation changes, or internal performance improvements for example. Increasing the minor number, for example from 2.4.1 to 2.5.0, means that things have been added to the API, but nothing was changed in the pre-existing API provided by the library. Finally, increasing the major number, such as from 2.4.1 to 3.0.0, means that some parts of the API have changed and thus may be incompatible with how we are currently using the previous version.

In Rust, packages are called crates and use semantic versioning. In fact, if you specify a dependency of the form package = "2.4.1", cargo will interpret that as the version constraint 2.4.1 <= v < 3.0.0 for that package. It does so based on the fact that any version in that range should not break our code according to the rules of semantic versioning. For more information on dependencies specifications in Cargo.toml you can read the Cargo reference book.

Side note on semantic versioning

Some people think that the granularity of semantic versioning is too broad in the case of major version changes. Instead, versions should never be breaking, but use new namespaces for things that change. It brings the same benefits in the large, that what choosing immutability as default brings in the small. For more information on this point of view, I highly recommend "Spec-ulation" by Rich Hickey, creator of the Clojure programming language.

Using the pubgrub crate

We will start with a simple example using the OfflineDependencyProvider, then show how to use the full DependencyProvider features step-by-step.

Basic example with OfflineDependencyProvider

Let's imagine that we are building a user interface with a menu containing dropdowns with some icons, icons that we are also directly using in other parts of the interface. For this scenario our direct dependencies are menu and icons, but the complete set of dependencies looks like follows.

user_interface depends on menu and icons
menu depends on dropdown
dropdown depends on icons
icons has no dependency

We can model that scenario as follows.

#![allow(unused)]
fn main() {
use pubgrub::{resolve, OfflineDependencyProvider, Ranges};

// Initialize a dependency provider.
let mut dependency_provider = OfflineDependencyProvider::<&str, Ranges<u32>>::new();

// Add all known dependencies.
dependency_provider.add_dependencies(
    "user_interface",
    1u32,
    [("menu", Ranges::full()), ("icons", Ranges::full())],
);
dependency_provider.add_dependencies("menu", 1u32, [("dropdown", Ranges::full())]);
dependency_provider.add_dependencies("dropdown", 1u32, [("icons", Ranges::full())]);
dependency_provider.add_dependencies("icons", 1u32, []);

// Run the algorithm.
let solution = resolve(&dependency_provider, "user_interface", 1u32).unwrap();
}

The key function of the PubGrub version solver is resolve. Besides the dependency provider, it takes the root package and its version as ("user_interface" at version 1) as arguments.

The resolve function gets package metadata from the DependencyProvider trait defined in this crate. That trait defines methods that the resolver can call when looking for packages and versions to try in the solver loop. For convenience and for testing purposes, we already provide an implementation of a dependency provider called OfflineDependencyProvider. As the names suggest, it doesn't do anything fancy and you have to pre-register all known dependencies with calls to add_dependencies(package, version, vec_of_dependencies) before being able to use it in the resolve function.

In the OfflineDependencyProvider, dependencies are specified with Ranges, defining version constraints. In most cases, you would use Range::between(v1, v2) which means any version higher or equal to v1 and strictly lower than v2. In the previous example, we just used Range::full() which means that any version is acceptable.

Implementing a dependency provider

The OfflineDependencyProvider is very useful for testing and playing with the API, but is not sufficient in complex setting such as Cargo. In those cases, a dependency provider may need to retrieve package information from caches, from the disk or from network requests.

PubGrub is generic over all its internal types. You need:

A package type P that implements Clone + Eq + Hash + Debug + Display, for example String
A version type V that implements Debug + Display + Clone + Ord, for example SemanticVersion

A version set type VS that implements VersionSet + Debug + Display + Clone + Eq, for example version_ranges::Ranges. VersionSet is defined as:

#![allow(unused)]
fn main() {
pub trait VersionSet: Debug + Display + Clone + Eq {
  type V: Debug + Display + Clone + Ord;

  // Constructors

  /// An empty set containing no version.
  fn empty() -> Self;

  /// A set containing only the given version.
  fn singleton(v: Self::V) -> Self;

  // Operations

  /// The set of all version that are not in this set.
  fn complement(&self) -> Self;

  /// The set of all versions that are in both sets.
  fn intersection(&self, other: &Self) -> Self;

  /// Whether the version is part of this set.
  fn contains(&self, v: &Self::V) -> bool;
}
}

A package priority Priority that implements Ord + Clone, for example usize`
A type for custom incompatibilities Incompatibility that implements Eq + Clone + Debug + Display, for example String
The error type returned from the DependencyProvider implements Error + 'static, for example anyhow::Error

While PubGrub is generic to encourage bringing your own types tailored to your use, it also provides some convenience types. For versions, we provide the SemanticVersion and the version_ranges::Ranges types. SemanticVersion implements Version for versions expressed as Major.Minor.Patch. u32 also fulfills all requirements of a version. Ranges represents multiple intervals of a continuous ranges with inclusive or exclusive bounds, e.g. >=1.3.0,<2 || >4,<=6 || >=7.1.

DependencyProvider requires implementing three functions:

#![allow(unused)]
fn main() {
pub trait DependencyProvider<P: Package, V: Version> {
  fn prioritize(
    &self,
    package: &Self::P,
    range: &Self::VS,
    package_conflicts_counts: &PackageResolutionStatistics,
  ) -> Self::Priority;

  fn choose_version(
    &self,
    package: &Self::P,
    range: &Self::VS,
  ) -> Result<Option<Self::V>, Self::Err>;

  fn get_dependencies(
    &self,
    package: &Self::P,
    version: &Self::V,
  ) -> Result<Dependencies<Self::P, Self::VS, Self::Incompatibility>, Self::Err>;

}
}

prioritize determines the order in which versions are chosen for packages.

Decisions are always made for the highest priority package first. The order of decisions determines which solution is chosen and can drastically change the performances of the solver. If there is a conflict between two package versions, the package with the higher priority is preserved and the lower priority gets discarded. Usually, you want to decide more certain packages (e.g. those with a single version constraint) and packages with more conflicts first. This function has potentially the highest impact on resolver performance.

Example:

The root package depends on A and B
A 2 depends on C 2
B 2 depends on C 1
A 1 has no dependencies
B 1 has no dependencies

If we always try the highest version first, prioritization determines the solution: If A has higher priority, the solution will be A 2, B 1, if B has higher priority, the solution will be A 1, B 2.

The package_conflicts_counts argument provides access to some other heuristics that are production users have found useful. Although the exact meaning/efficacy of those arguments may change.

The function is called once for each new package and then cached until we detect a (potential) change to range, otherwise it is cached, assuming that the priority only depends on the arguments to this function.

If two packages have the same priority, PubGrub will bias toward a breadth first search.

Once the highest priority package has been determined, we want to make a decision for it and need a version. choose_version returns the next version for to try for this package, which in the current partial solution is constrained by range. If you are trying to solve for the latest version, return the highest version of the package contained in range.

Finally, the solver needs to know the dependency of that version to determine which packages to try next or if there are any conflicts. get_dependencies returns the dependencies of a given package version. Usually, you return Ok(Dependencies::Available(rustc_hash::FxHashMap::from(...))), where the map is the list of dependencies with their version ranges. You can also return Dependencies::Unavailable if the dependencies could not be retrieved, but you consider this error non-fatal, for example because the version use an unsupported metadata format.

Aside from the required methods, there is an optional should_cancel method. This method is regularly called in the solver loop, currently once per decision, and defaults to doing nothing. If needed, you can override it to provide custom behavior, such as giving some feedback, or stopping early to prevent ddos. Any useful behavior would require mutability of self, and that is possible thanks to interior mutability. Read on the next section for more info on that!

Caching dependencies in a DependencyProvider

A dependency provider can be reused for multiple resolutions, usually of the same package and thus asking for the same dependencies. Since dependencies are generally immutable, caching them is a valid strategy to avoid slow operations that may be needed such as fetching remote data. But caching data in a dependency provider while computing the result of get_dependencies would require &mut self instead of &self. We wanted to encode in the type that the resolve function cannot mutate on its own a dependency provider so that's why we chose &self. But if the dependency provider wants to mutate itself there is a pattern called interior mutability enabling exactly that. We will now setup a simple example of how to do that. If by the end you think the trade-off is not worth it and we should use &mut self in the method signature, please let us know with an issue in pubgrub repository.

Let DependencyCache be our cache for dependencies, with existing methods to fetch them over the network,

#![allow(unused)]
fn main() {
struct DependencyCache<P: Package, V: Version> {
    cache: Map<P, BTreeMap<V, DependencyConstraints<P, V>>>,
}

impl<P: Package, V: Version> DependencyCache<P, V> {
    /// Initialize cached dependencies.
    pub fn new() -> Self { ... }
    /// Fetch dependencies of a given package on the network and store them in the cache.
    pub fn fetch(&mut self, package: &P, version: &V) -> Result<(), Box<dyn Error>> { ... }
    /// Extract dependencies of a given package from the cache.
    pub fn get(&self, package: &P, version: &V) -> Dependencies { ... }
}
}

We can implement the DependencyProvider trait in the following way, using RefCell for interior mutability in order to cache dependencies.

#![allow(unused)]
fn main() {
pub struct CachingDependencyProvider<P: Package, V: Version> {
    cached_dependencies: RefCell<DependencyCache>,
}

impl<P: Package, V: Version> DependencyProvider<P, V> for CachingDependencyProvider<P, V> {
    fn choose_version(&self, package: &DP::P, ranges: &DP::VS) -> Result<Option<DP::V>, DP::Err> {
        ...
    }

    fn get_dependencies(
        &self,
        package: &P,
        version: &V,
    ) -> Result<Dependencies<P, V>, Box<dyn Error>> {
        match self.cached_dependencies.get(package, version) {
            deps @ Dependencies::Kown(_) => Ok(deps),
            Dependencies::Unknown => {
                self.cached_dependencies.borrow_mut().fetch(package, version)?;
                Ok(self.cached_dependencies.get(package, version))
            }
        }
    }
}
}

An example of caching based on the OfflineDependencyProvider is available in examples/caching_dependency_provider.rs.

Strategical decision making in a DependencyProvider

In PubGrub, decision making is the process of choosing the next package and version that will be appended to the solution being built. Every time such a decision must be made, potential valid packages are preselected with corresponding valid ranges of versions. Then, there is some freedom regarding which of those package versions to choose.

The strategy employed to choose such package and version cannot change the existence of a solution or not, but can drastically change the performance of the solver, or the properties of the solution.

In our implementation of PubGrub, decision making responsibility is divided into two pieces. The resolver takes care of making a preselection for potential packages and corresponding ranges of versions. Then it's the dependency provider that has the freedom of employing the strategy of picking a single package version through prioritize and choose_version.

Picking a package

Potential packages basically are packages that appeared in the dependencies of a package we've already added to the solution. So once a package appear in potential packages, it will continue to be proposed as such until we pick it, or a conflict shows up and the solution is backtracked before needing it.

Imagine that one such potential package is limited to a range containing no existing version, we are heading directly to a conflict! So we are better dealing with that conflict as soon as possible, instead of delaying it for later since we will have to backtrack anyway. Consequently, we always want to pick first a conflictual potential package with no valid version. Similarly, potential packages with only one valid version give us no choice and limit options going forward, so we might want to pick such potential packages before others with more version choices. Generalizing this strategy to picking the potential package with the lowest number of valid versions is a rather good heuristic performance-wise. This strategy is the one employed by the OfflineDependencyProvider. You can use the PackageResolutionStatistics passed into prioritize for a heuristic for conflicting-ness: The more conflict a package had, the higher its priority should be.

Picking a version

In general, letting the dependency provider choose a version in choose_version provides a great deal of flexibility and enables things like

choosing the newest versions,
choosing the oldest versions,
choosing already downloaded versions,
choosing versions specified in a lock file,

and many other desirable behaviors for the resolver, controlled directly by the dependency provider.

Solution and error reporting

When everything goes well, the algorithm finds and returns a set of packages and versions satisfying all the constraints of direct and indirect dependencies. Sometimes however, there is no solution because dependencies are incompatible. In such cases, the algorithm returns a PubGrubError::NoSolution(derivation_tree) where the provided derivation tree is a binary tree containing the chain of reasons why there is no solution.

The items in the tree are called incompatibilities and may be either external. Leaves of the tree are external and custom incompatibilities, and nodes are derived. External incompatibilities express facts that are independent of the way this algorithm is implemented such as package "a" at version 1 depends on package "b" at version 4, or that there is no version of package "a" higher than version 5. Custom incompatibilities are a user provided generic type parameter that can express missing versions, such as that dependencies of package "a" are not in cache, but the user requested an offline resolution.

In contrast, derived incompatibilities are obtained during the algorithm execution by deduction, such as if "a" depends on "b" and "b" depends on "c", then "a" depends on "c".

Processing a derivation tree in a custom way to generate a failure report that is human-friendly is not an easy task. For convenience, this crate provides a DefaultStringReporter able to convert a derivation tree into a human-friendly String explanation of the failure. You may use it as follows.

#![allow(unused)]
fn main() {
use pubgrub::{resolve, DefaultStringReporter, PubGrubError, Reporter};

match resolve(&dependency_provider, root_package, root_version) {
    Ok(solution) => println!("{:?}", solution),
    Err(PubGrubError::NoSolution(mut derivation_tree)) => {
        derivation_tree.collapse_no_versions();
        eprintln!("{}", DefaultStringReporter::report(&derivation_tree));
    }
    Err(err) => panic!("{:?}", err),
};
}

Notice that we also used collapse_no_versions() above. This method simplifies the derivation tree to get rid of the NoVersions external incompatibilities in the derivation tree. So instead of seeing things like this in the report:

Because there is no version of foo in 1.0.1 <= v < 2.0.0
and foo 1.0.0 depends on bar 2.0.0 <= v < 3.0.0,
foo 1.0.0 <= v < 2.0.0 depends on bar 2.0.0 <= v < 3.0.0.
...

You will directly see something like:

Because foo 1.0.0 <= v < 2.0.0 depends on bar 2.0.0,
...

Writing your own error reporting logic

The DerivationTree is a custom binary tree where leaves are external incompatibilities, defined as follows,

#![allow(unused)]
fn main() {
pub enum External<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> {
    /// Initial incompatibility aiming at picking the root package for the first decision.
    NotRoot(P, VS::V),
    /// There are no versions in the given set for this package.
    NoVersions(P, VS),
    /// Incompatibility coming from the dependencies of a given package.
    FromDependencyOf(P, VS, P, VS),
    /// The package is unusable for reasons outside pubgrub.
    Custom(P, VS, M),
}
}

and nodes are derived incompatibilities, defined as follows.

#![allow(unused)]
fn main() {
#[derive(Debug, Clone)]
pub struct Derived<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> {
    /// Terms of the incompatibility.
    pub terms: Map<P, Term<VS>>,
    /// Indicate if the incompatibility is present multiple times in the derivation tree.
    ///
    /// If that is the case, the number is a unique id. We may want to only explain this
    /// incompatibility once, then refer to the explanation for the other times.
    pub shared_id: Option<usize>,
    /// First cause.
    pub cause1: Arc<DerivationTree<P, VS, M>>,
    /// Second cause.
    pub cause2: Arc<DerivationTree<P, VS, M>>,
}
}

The terms hashmap contains the version sets of the derived incompatibility. The rule is that terms of an incompatibility are terms that cannot be all true at the same time. So a dependency can for example be expressed with an incompatibility containing a positive term, and a negative term. For example, "root" at version 1 depends on "a" at version 4, can be expressed by the incompatibility {root: 1, a: not 4}. A missing version can be expressed by an incompatibility with a single term. So for example, if version 4 of package "a" is missing, it can be expressed with the incompatibility {a: 4} which forbids that version. If you want to write your own reporting logic, we recommend reading first the section of this book on internals of the PubGrub algorithm to understand the internals of incompatibilities.

The root of the derivation tree is a derived incompatibility containing a single term such as {"root": 1} if we were trying to solve dependencies for package "root" at version 1. Imagine we had one simple dependency on "a" at version 4, but somehow that version does not exist. Then version solving would fail and return a derivation tree looking like follows.

Derived { root: 1 }
	├─ External dependency { root: 1, a: not 4 }
	└─ External no version { a: 4 }

The goal of error reporting is to transform that tree into a friendly human-readable output. It could be something like:

This project depends on version 4 of package a which does not exist
so version solving failed.

One of the subtleties of error reporting is that the binary derivation tree is actually a DAG (directed acyclic graph). Occasionally, an incompatibility may cause multiple derived incompatibilities in the same derivation tree such as below, where the incompatibility 2 is used to derive both incompatibilities 4 and 5.

                          +----------+        +----------+
                 +------->|incompat 4|------->|incompat 1|
                 |        +----------+        +----------+
                 |                |
          +----------+            |           +----------+
  (root)  |incompat 6|            +---------->|incompat 2|  (shared)
          +----------+            |           +----------+
                 |                |
                 |        +----------+        +----------+
                 +------->|incompat 5|------->|incompat 3|
                          +----------+        +----------+

For ease of processing, the DerivationTree duplicates such nodes in the tree, but their shared_id attribute will hold a Some(id) variant. In error reporting, you may want to check if you already gave an explanation for a shared derived incompatibility, and in such cases maybe use line references instead of re-explaining the same thing.

Advanced usage and limitations

By design, the current implementation of PubGrub is rather well suited to handle a dependency system with the following constraints:

Packages are uniquely identified.
Versions are in a discrete set, with a total order.
Dependencies of a package version are fixed.
Exactly one version must be selected per package depended on.

The fact that packages are uniquely identified (1) is perhaps the only constraint that makes sense for all common dependency systems. But for the rest of the constraints, they are all inadequate for some common real-world dependency systems. For example, it's possible to have dependency systems where order is not required for versions (2). In such systems, dependencies must be specified with exact sets of compatible versions, and bounded ranges make no sense. Having fixed dependencies (3) is also not followed in programming languages allowing optional dependencies. In Rust packages, optional dependencies are called "features" for example. Finally, restricting solutions to only one version per package (4) is also too constraining for dependency systems allowing breaking changes. In cases where packages A and B both depend on different ranges of package C, we sometimes want to be able to have a solution where two versions of C are present, and let the compiler decide if their usages of C in the code are compatible.

In the following subsections, we try to show how we can circumvent those limitations with clever usage of dependency providers.

Optional dependencies

Sometimes, we want the ability to express that some functionalities are optional. Since those functionalities may depend on other packages, we also want the ability to mark those dependencies optional.

Let's imagine a simple scenario in which we are developing package "A" and depending on package "B", itself depending on "C". Now "B" just added new functionalities, very convenient but also very heavy. For architectural reasons, they decided to release them as optional features of the same package instead of in a new package. To enable those features, one has to activate the "heavy" option of package "B", bringing a new dependency to package "H". We will mark optional features in dependencies with a slash separator "/". So we have now "A" depends on "B/heavy" instead of previously "A" depends on "B". And the complete dependency resolution is thus now ["A", "B/heavy", "C", "H"].

But what happens if our package "A" start depending on another package "D", which depends on "B" without the "heavy" option? We would now have ["A", "B", "B/heavy", "C", "D", "H"]. Is this problematic? Can we conciliate the fact that both "B" and "B/heavy" are in the dependencies?

Strictly additive optional dependencies

The most logical solution to this situation is to require that optional features and dependencies are strictly additive. Meaning "B/heavy" is entirely compatible with "B" and only brings new functions and dependencies. "B/heavy" cannot change dependencies of "B" only adding new ones. Once this hypothesis is valid for our dependency system, we can model "B/heavy" as a different package entirely, depending on both "B" and "H", leading to the solution ["A", "B", "B/heavy", "C", "D", "H"]. Whatever new optional features that get added to "B" can similarly be modeled by a new package "B/new-feat", also depending on "B" and on its own new dependencies. When dependency resolution ends, we can gather all features of "B" that were added to the solution and compile "B" with those.

Dealing with versions

In the above example, we eluded versions and only talked about packages. Adding versions to the mix actually does not change anything, and solves the optional dependencies problem very elegantly. The key point is that an optional feature package, such as "B/heavy", would depend on its base package, "B", exactly at the same version. So if the "heavy" option of package "B" at version v = 3 brings a dependency to "H" at v >= 2, then we can model dependencies of "B/heavy" at v = 3 by ["B" @ v = 3, "H" @ v >= 2].

Example implementation

A complete example implementation is available in the optional-deps crate of the advanced_dependency_providers repository. Let's give an explanation of that implementation. For the sake of simplicity, we will consider packages of type String and versions of type NumberVersion, which is just a newtype around u32 implementing the Version trait.

Defining an index of packages

We define an Index, storing all dependencies (Deps) of every package version in a double map, first indexed by package, then by version.

#![allow(unused)]
fn main() {
/// Each package is identified by its name.
pub type PackageName = String;

/// Global registry of known packages.
pub struct Index {
    /// Specify dependencies of each package version.
    pub packages: Map<PackageName, BTreeMap<u32, Deps>>,
}
}

Dependencies listed in the Index include both mandatory and optional dependencies. Optional dependencies are identified, grouped, and gated by an option called a "feature".

#![allow(unused)]
fn main() {
pub type Feature = String;

pub struct Deps {
    /// The regular, mandatory dependencies.
    pub mandatory: Map<PackageName, Dep>,
    /// The optional, feature-gated dependencies.
    pub optional: Map<Feature, Map<PackageName, Dep>>,
}
}

Finally, each dependency is specified with a version range, and with a set of activated features.

#![allow(unused)]
fn main() {
pub struct Dep {
    /// The range dependended upon.
    pub range: Range<Version>,
    /// The activated features for that dependency.
    pub features: Set<Feature>,
}
}

For convenience, we added the add_deps and add_feature functions to help building an index in the tests.

#![allow(unused)]
fn main() {
let mut index = Index::new();
// Add package "a" to the index at version 0 with no dependency.
index.add_deps("a", 0, &[]);
// Add package "a" at version 1 with a dependency to "b" at version "v >= 1".
index.add_deps("a", 1, &[("b", 1.., &[])]);
// Add package "c" at version 1 with a dependency to "d" at version "v < 4" with the feature "feat".
index.add_deps("c", 1, &[("d", ..4, &["feat"])]);
// Add feature "feat" to package "d" at version 1 with the optional dependency to "f" at version "v >= 1".
// If "d" at version 1 does not exist yet in the index, this also adds it with no mandatory dependency,
// as if we had called index.add_deps("d", 1, &[]).
index.add_feature("d", 1, "feat", &[("f", 1.., &[])]);
}

Implementing a dependency provider for the index

Now that our Index is ready, let's implement the DependencyProvider trait on it. As we explained before, we'll need to differenciate optional features from base packages, so we define a new Package type.

#![allow(unused)]
fn main() {
/// A package is either a base package like "a",
/// or a feature package, corresponding to a feature associated to a base package.
pub enum Package {
    Base(String),
    Feature { base: String, feature: String },
}
}

We'll ignore prioritize for this example.

Let's implement the second function required by a dependency provider, choose_version. For that we defined the base_pkg() method on a Package that returns the string of the base package, and the available_versions() method on an Index to list existing versions of a given package in descending order.

#![allow(unused)]
fn main() {
fn choose_version(
    &self,
    package: &Self::P,
    range: &Self::VS,
) -> Result<Option<Self::V>, Self::Err> {
    Ok(self.available_versions(p.base_pkg()).find(|version| range.contains(version)).cloned())
}
}

This was very straightforward. Implementing the second function, get_dependencies, requires just a bit more work but is also quite easy. The exact complete version is available in the code, but again, for the sake of simplicity and readability, let's just deal with the happy path.

#![allow(unused)]
fn main() {
fn get_dependencies(
    &self,
    package: &Package,
    version: &Version,
) -> Result<Dependencies<Package, Version>, ...> {
    // Retrieve the dependencies in the index.
    let deps =
        self.packages
            .get(package.base_pkg()).unwrap()
            .get(version).unwrap();

    match package {
        // If we asked for a base package, we simply return the mandatory dependencies.
        Package::Base(_) => Ok(Dependencies::Available(from_deps(&deps.mandatory))),
        // Otherwise, we concatenate the feature deps with a dependency to the base package.
        Package::Feature { base, feature } => {
            let feature_deps = deps.optional.get(feature).unwrap();
            let mut all_deps = from_deps(feature_deps);
            all_deps.insert(
                Package::Base(base.to_string()),
                Range::exact(version.clone()),
            );
            Ok(Dependencies::Available(all_deps))
        },
    }
}
}

Quite easy right? The helper function from_deps is where each dependency is transformed from its String form into its Package form. In pseudo-code (not compiling, but you get how it works) it looks like follows.

#![allow(unused)]
fn main() {
/// Helper function to convert Index deps into what is expected by the dependency provider.
fn from_deps(deps: &Map<String, Dep>) -> DependencyConstraints<Package, Version> {
    deps.iter().map(create_feature_deps)
        .flatten()
        .collect()
}

fn create_feature_deps(
    (base_pkg, dep): (&String, &Dep)
) -> impl Iterator<Item = (Package, Range<Version>)> {
    if dep.features.is_empty() {
        // If the dependency has no optional feature activated,
        // we simply add a dependency to the base package.
        std::iter::once((Package::Base(base_pkg), dep.range))
    } else {
        // Otherwise, we instead add one dependency per activated feature,
        // but not to the base package itself (we could but no need).
        dep.features.iter().map(|feat| {
            (Package::Feature { base: base_pkg, feature: feat }, dep.range)
        })
    }
}
}

We now have implemented the DependencyProvider trait. The only thing left is testing it with example dependencies. For that, we setup few helper functions and we wrote some tests, that you can run with a call to cargo test --lib. Below is one of those tests.

#![allow(unused)]
fn main() {
#[test]
fn success_when_multiple_features() {
    let mut index = Index::new();
    index.add_deps("a", 0, &[("b", .., &["feat1", "feat2"])]);
    index.add_feature("b", 0, "feat1", &[("f1", .., &[])]);
    index.add_feature("b", 0, "feat2", &[("f2", .., &[])]);
    index.add_deps::<R>("f1", 0, &[]);
    index.add_deps::<R>("f2", 0, &[]);
    assert_map_eq(
        &resolve(&index, "a", 0).unwrap(),
        &select(&[
            ("a", 0),
            ("b", 0),
            ("b/feat1", 0),
            ("b/feat2", 0),
            ("f1", 0),
            ("f2", 0),
        ]),
    );
}
}

Allowing multiple versions of a package

One of the main goals of PubGrub is to pick one version per package depended on, under the assumption that at most one version per package is allowed. Enforcing this assumption has two advantages. First, it prevents data and functions interactions of the same library at different, potentially incompatible versions. Second, it reduces the code size and therefore also the disk usage and the compilation times.

However, under some circonstances, we may relax the "single version allowed" constraint. Imagine that our package "a" depends on "b" and "c", and "b" depends on "d" @ 1, and "c" depends on "d" @ 2, with versions 1 and 2 of "d" incompatible with each other. With the default rules of PubGrub, that system has no solution and we cannot build "a". Yet, if our usages of "b" and "c" are independant with regard to "d", we could in theory build "b" with "d" @ 1 and build "c" with "d" @ 2.

Such situation is sufficiently common that most package managers allow multiple versions of a package. In Rust for example, multiple versions are allowed as long as they cross a major frontier, so 0.7 and 0.8 or 2.0 and 3.0. So the question now is can we circumvent this fundamental restriction of PubGrub? The short answer is yes, with buckets and proxies.

Buckets

We saw that implementing optional dependencies required the creation of on-demand feature packages, which are virtual packages created for each optional feature. In order to allow for multiple versions of the same package to coexist, we are also going to play smart with packages. Indeed, if we want two versions to coexist, there is only one possibility, which is that they come from different packages. And so we introduce the concept of buckets. A package bucket is a set of versions of the same package that cannot coexist in the solution of a dependency system, basically just like before. So for Rust crates, we can define one bucket per major frontier, such as one bucket for 0.1, one for 0.2, ..., one for 1.0, one for 2.0, etc. As such, versions 0.7.0 and 0.7.3 would be in the same bucket, but 0.7.0 and 0.8.0 would be in different buckets and could coexist.

Are buckets enought? Not quite, since once we introduce buckets, we also need a way to depend on multiple buckets alternatively. Indeed, most packages should have dependencies on a single bucket, because it doesn't make sense to depend on potentially incompatible versions at the same time. But rarely, dependencies are written such that they can depend on multiple buckets, such as if one write v >= 2.0. Then, any version from the 2.0 bucket would satisfy it, as well as any version from the 3.0 or any other later bucket. Thus, we cannot write "a depends on b in bucket 2.0". So how do we write dependencies of "a"? That's where we introduce the concept of proxies.

Proxies

A proxy package is an intermediate on-demand package, placed just between one package and one of its dependencies. So if we need to express that package "a" has a dependency on package "b" for different buckets, we create the intermediate proxy package "a->b". Then we can say instead that package "a" depends on any version of the proxy package "a->b". And then, we create one proxy version for each bucket. So if there exists the following five buckets for "b", 0.1, 0.2, 1.0, 2.0, 3.0, we create five corresponding versions for the proxy package "a->b". And since our package "a" depends on any version of the proxy package "a->b", it will be satisfied as soon as any bucket of "b" has a version picked.

Example

We will consider versions in the form major.minor with a major component starting at 1, and a minor component starting at 0. The smallest version is 1.0, and each major component represents a bucket.

Note that we could start versions at 0.0, but since different dependency system tends to interpret versions before 1.0 differently, we will simply avoid that problem by saying versions start at 1.0.

For convenience, we will use a string notation for proxies and buckets. Buckets will be indicated by a "#", so "a#1" is the 1.0 bucket of package "a", and "a#2" is the 2.0 bucket of package "a". And we will use "@" to denote exact versions, so "a" @ 1.0 means package "a" at version 1.0. Proxies will be represented by the arrow "->" as previously mentioned. Since a proxy is tied to a specific version of the initial package, we also use the "@" symbol in the name of the proxy package. For example, if "a" @ 1.4 depends on "b", we create the proxy package "a#1@1.4->b". It's a bit of a mouthful, but once you learn how to read it, it makes sense.

Note that we might be tempted to just remove the version part of the proxy, so "a#1->b" instead of "a#1@1.4->b". However, we might have "a" @ 1.4 depending on "b" in range v >= 2.2 and have "a" @ 1.5 depending on "b" in range v >= 2.6. Both dependencies would map to the same "a#1->b" proxy package, but we would not know what to put in the dependency of "a#1->b" to the "b#2" bucket. Should it be "2.2 <= v < 3.0" as in "a" @ 1.4, or should it be "2.6 <= v < 3.0" as in "a" @ 1.5? That is why each proxy package is tied to an exact version of the source package.

Let's consider the following example, with "a" being our root package.

"a" @ 1.4 depends on "b" in range 1.1 <= v < 2.9
"b" @ 1.3 depends on "c" at version 1.1
"b" @ 2.7 depends on "d" at version 3.1

Using buckets and proxies, we can rewrite this dependency system as follows.

"a#1" @ 1.4 depends on "a#1@1.4->b" at any version (we use the proxy).
"a#1@1.4->b" proxy exists in two versions, one per bucket of "b".
"a#1@1.4->b" @ 1.0 depends on "b#1" in range 1.1 <= v < 2.0 (the first bucket intersected with the dependency range).
"a#1@1.4->b" @ 2.0 depends on "b#2" in range 2.0 <= v < 2.9 (the second bucket intersected with the dependency range).
"b#1" @ 1.3 depends on "c#1" at version 1.1.
"b#2" @ 2.7 depends on "d#3" at version 3.1.

There are potentially two solutions to that system. The one with the newest versions is the following.

"a#1" @ 1.4
"a#1@1.4->b" @ 2.0
"b#2" @ 2.7
"d#3" @ 3.1

Finally, if we want to express the solution in terms of the original packages, we just have to remove the proxy packages from the solution.

Example implementation

A complete example implementation of this extension allowing multiple versions is available in the allow-multiple-versions crate of the advanced_dependency_providers repository. In that example, packages are of the type String and versions of the type SemanticVersion defined in pubgrub, which does not account for pre-releases, just the (Major, Minor, Patch) format of versions.

Defining an index of packages

Inside the index.rs module, we define a very basic Index, holding all packages known, as well as a helper function add_deps easing the writing of tests.

#![allow(unused)]
fn main() {
/// Each package is identified by its name.
pub type PackageName = String;
/// Alias for dependencies.
pub type Deps = Map<PackageName, Range<SemVer>>;

/// Global registry of known packages.
pub struct Index {
    /// Specify dependencies of each package version.
    pub packages: Map<PackageName, BTreeMap<SemVer, Deps>>,
}

// Initialize an empty index.
let mut index = Index::new();
// Add package "a" to the index at version 1.0.0 with no dependency.
index.add_deps::<R>("a", (1, 0, 0), &[]);
// Add package "a" to the index at version 2.0.0 with a dependency to "b" at versions >= 1.0.0.
index.add_deps("a", (2, 0, 0), &[("b", (1, 0, 0)..)]);
}

Implementing a dependency provider for the index

Since our Index is ready, we now have to implement the DependencyProvider trait for it. As explained previously, we'll need to differenciate packages representing buckets and proxies, so we define the following new Package type.

#![allow(unused)]
fn main() {
/// A package is either a bucket, or a proxy between a source and a target package.
pub enum Package {
    /// "a#1"
    Bucket(Bucket),
    /// source -> target
    Proxy {
        source: (Bucket, SemVer),
        target: String,
    },
}

/// A bucket corresponds to a given package, and match versions
/// in a range identified by their major component.
pub struct Bucket {
    pub name: String, // package name
    pub bucket: u32, // 1 maps to the range 1.0.0 <= v < 2.0.0
}
}

In order to implement the first required method, choose_package_version, we simply reuse the choose_package_with_fewest_versions helper function provided by pubgrub. That one requires a list of available versions for each package, so we have to create that list. As explained previously, listing the existing (virtual) versions depend on if the package is a bucket or a proxy. For a bucket package, we simply need to retrieve the original versions and filter out those outside of the bucket.

#![allow(unused)]
fn main() {
match package {
    Package::Bucket(p) => {
        let bucket_range = Range::between((p.bucket, 0, 0), (p.bucket + 1, 0, 0));
        self.available_versions(&p.name)
            .filter(|v| bucket_range.contains(*v))
    }
    ...
}

If the package is a proxy however, there is one version per bucket in the target of the proxy.

#![allow(unused)]
fn main() {
match package {
    Package::Proxy { target, .. } => {
        bucket_versions(self.available_versions(&target))
    }
    ...
}

/// Take a list of versions, and output a list of the corresponding bucket versions.
/// So [1.1, 1.2, 2.3] -> [1.0, 2.0]
fn bucket_versions(
    versions: impl Iterator<Item = SemVer>
) -> impl Iterator<Item = SemVer> { ... }
}

Additionally, we can filter out buckets that are outside of the dependency range in the original dependency leading to that proxy package. Otherwise it will add wastefull computation to the solver, but we'll leave that out of this walkthrough.

The get_dependencies method is slightly hairier to implement, so instead of all the code, we will just show the structure of the function in the happy path, with its comments.

#![allow(unused)]
fn main() {
fn get_dependencies(
    &self,
    package: &Package,
    version: &SemVer,
) -> Result<Dependencies<Package, SemVer>, ...> {
    let all_versions = self.packages.get(package.pkg_name());
    ...
    match package {
        Package::Bucket(pkg) => {
            // If this is a bucket, we convert each original dependency into
            // either a dependency to a bucket package if the range is fully contained within one bucket,
            // or a dependency to a proxy package at any version otherwise.
            let deps = all_versions.get(version);
            ...
            let pkg_deps = deps.iter().map(|(name, range)| {
                    if let Some(bucket) = single_bucket_spanned(range) {
                        ...
                        (Package::Bucket(bucket_dep), range.clone())
                    } else {
                        ...
                        (proxy, Range::any())
                    }
                })
                .collect();
            Ok(Dependencies::Available(pkg_deps))
        }
        Package::Proxy { source, target } => {
            // If this is a proxy package, it depends on a single bucket package, the target,
            // at a range of versions corresponding to the bucket range of the version asked,
            // intersected with the original dependency range.
            let deps = all_versions.get(&source.1);
            ...
            let mut bucket_dep = Map::default();
            bucket_dep.insert(
                Package::Bucket(Bucket {
                    name: target.clone(),
                    bucket: target_bucket,
                }),
                bucket_range.intersection(target_range),
            );
            Ok(Dependencies::Available(bucket_dep))
        }
    }
}

/// If the range is fully contained within one bucket,
/// this returns that bucket identifier, otherwise, it returns None.
fn single_bucket_spanned(range: &Range<SemVer>) -> Option<u32> { ... }
}

That's all! The implementation also contains tests, with helper functions to build them. Here is the test corresponding to the example we presented above.

#![allow(unused)]
fn main() {
#[test]
/// Example in guide.
fn success_when_simple_version() {
    let mut index = Index::new();
    index.add_deps("a", (1, 4, 0), &[("b", (1, 1, 0)..(2, 9, 0))]);
    index.add_deps("b", (1, 3, 0), &[("c", (1, 1, 0)..(1, 1, 1))]);
    index.add_deps("b", (2, 7, 0), &[("d", (3, 1, 0)..(3, 1, 1))]);
    index.add_deps::<R>("c", (1, 1, 0), &[]);
    index.add_deps::<R>("d", (3, 1, 0), &[]);
    assert_map_eq(
        &resolve(&index, "a#1", (1, 4, 0)).unwrap(),
        &select(&[("a#1", (1, 4, 0)), ("b#2", (2, 7, 0)), ("d#3", (3, 1, 0))]),
    );
}
}

Implementing a dependency provider allowing both optional dependencies and multiple versions per package is left to the reader as an exercise (I've always wanted to say that).

Public and Private packages

We just saw in the previous section that it was possible to have multiple versions of the same package, as long as we create independant virtual packages called buckets. Oftentimes, creating buckets with fixed version boundaries and which are shared among the whole dependency system can cause versions mismatches in dependency chains. This is for example the case with a chain of packages publicly re-exporting types of their dependencies and interacting with each other. Concretely, let's say that we depend on two packages "a" and "b", with "a" also depending on "b" but at a different version.

"root" depends on "a" @ 1
"root" depends on "b" @ 1
"a" @ 1 depends on "b" @ 2

Without buckets, there is no solution since "b" is depended on at two different versions. If we introduce buckets with boundaries at major versions, we have a solution since "root" depends on "b#1" while "a#1" depends on bucket "b#2".

But, what if package "a" re-exports in its public interface a type coming from its "b" dependency? If we feed a function of "a" with a type from "b#1", compilation will fail, complaining about the argument being of the wrong type. Currently in the rust compiler, this creates cryptic error messages of the kind "Expected type T, found type T", where "T" is exactly the same thing. Of course, those compiler errors should be improved, but there is a way of preventing that situation entirely at the time of solving dependencies instead of at compilation time. We can call that the public/private scheme. It consists in marking dependencies with re-exported types as "public", while other dependencies are considered "private" since they don't leak their types. So instead of saying that "a" depends on "b", we say that "a" publicly depends on "b". Therefore public dependencies must be unique even across multiple major versions.

Note that there is one inconvenience though, which is that we could have false positives, i.e. reject situations that the compiler would have accepted to compile. Indeed, it's not because "a" has public types of "b" exposed that we are necessarily using them! Now let's detail a bit more the public/private scheme and how it could be implemented with PubGrub.

Public subgraph

Two versions of a package can only conflict with each other if they interact through a chain of publicly connected dependencies. This means that any private dependency can cut the chain of public dependencies. If "a" privately depends on "b", dependencies of "b" are guaranteed to be independant (usage wise) of the rest of the dependency graph above package "a". This means that there is not one list of public packages, but rather multiple subgraphs of publicly connected packages, which start either at the root, or at a private dependency frontier. And in each public subgraph, there can only be one version of each package.

Seed markers

Since dependencies form a directed graph, each public subgraph can be uniquely identified by a root package, that we will call the "seed" of the public subgraph. This "seed" is in fact the source package of a private dependency link, and all publicly connected packages following the target package of the private dependency link can be marked with that seed. In addition, all packages behind a private link can only be accessed by the source package of that private dependency, so all seed markers existing previous to the private link can be cleared, leaving only seed marker of the source package. The diagram below provides a visual example of dependency graphs where seed markers are annotated next to each package.

In fact, as soon as a package has at least one private dependency, all dependency branches must be marked with the seed marker of the source package. This is because all branches contain code that is used by the source package. As a result, if a package has both a private dependency and a public dependency, the public dependency will inherit all markers of the source package plus a new seed marker for the source package itself. Therefore, the number of seed markers along a public dependency chain grows with the number of branches that also contain private dependencies, as visible in the diagram below.

Example

Let's consider the previous branching example where "b" is depended on both by our root package and by our dependency "a". If we note seed markers with a dollar symbol "$" that example can be adapted to the following system.

"root" depends on "a$root" @ 1
"root" depends on "b$root" @ 1
"a$root" @ 1 depends privately on "b$a@1" @ 2

Seed markers must correspond to an exact package version because multiple versions of a given package will have different dependency graphs, and we don't want to wrongly assume that all subgraphs are the same for all versions. Here, since "a" depends privately on "b", "b" is marked with the seed "$a@1". Thus, this system has the following solution.

"a$root" @ 1
"b$root" @ 1
"b$a@1" @ 2

If instead of a private dependency, "a" had a public dependency on "b", there would be no new seed marker and it would read:

"a$root" @ 1 depends publicly on "b$root" @ 2

Leading to no solution, since the package "b$root" is now required both at version 1 and 2.

Example implementation

The seed markers scheme presented above can easily be implemented with pubgrub by keeping seed markers together with package names in the Package type involved in the DependencyProvider. A complete example implementation of this extension allowing public and private dependencies is available in the public-private crate of the advanced_dependency_providers repository. In that example, packages are of the type String and versions of the type SemanticVersion defined in pubgrub, which does not account for pre-releases, just the (Major, Minor, Patch) format of versions.

Defining an index of packages

Inside the index.rs module, we define a very basic Index, holding all packages known, as well as a helper function add_deps easing the writing of tests.

#![allow(unused)]
fn main() {
/// Each package is identified by its name.
pub type PackageName = String;
/// Alias for dependencies.
pub type Deps = Map<PackageName, (Privacy, Range<SemVer>)>;
/// Privacy indicates if a dependency is public or private.
pub enum Privacy { Public, Private }

/// Global registry of known packages.
pub struct Index {
    /// Specify dependencies of each package version.
    pub packages: Map<PackageName, BTreeMap<SemVer, Deps>>,
}

// Initialize an empty index.
let mut index = Index::new();
// Add package "a" to the index at version 1.0.0 with no dependency.
index.add_deps::<R>("a", (1, 0, 0), &[]);
// Add package "a" to the index at version 2.0.0 with a private dependency to "b" at versions >= 1.0.0.
index.add_deps("a", (2, 0, 0), &[("b", Private, (1, 0, 0)..)]);
// Add package "a" to the index at version 3.0.0 with a public dependency to "b" at versions >= 1.0.0.
index.add_deps("a", (3, 0, 0), &[("b", Public, (1, 0, 0)..)]);
}

Implementing a dependency provider for the index

Since our Index is ready, we now have to implement the DependencyProvider trait for it. As explained previously, we need to identify which public subgraphs a given dependency belongs to. That is why each package also holds seed markers, which are the identifiers of the "seed" packages at the origin of each public subgraph this package belongs to. Since we need a unique hash for each package for each seed, and there can be multiple seed markers, the PkgSeeds type is actually an enum where a Markers variant will have exactly one dependency to a Constraint variant per seed listed in its markers, in addition to the dependencies registered in the index. And as its name suggests, the Constraint variant of a PkgSeeds package is only there to make sure that the "1-version-per-seed" constraint is satisfied and does not have any dependency. Thanks to that, we guarantee that there can only be one version of each package per public subgraph.

#![allow(unused)]
fn main() {
/// A package is identified by its name and by the public subgraphs
/// it belongs to, themselves identified by "seeds".
pub struct Package {
    name: String,
    seeds: PkgSeeds,
}

/// Each public subgraph is identified by a seed,
/// and some packages belong to multiple public subgraphs
/// and can thus have multiple seed markers.
/// Since we also need to have a unique hash per package, per public subgraph,
/// Each `Markers` variant of a package will also have a dependency on
/// one `Constraint` variant per seed, resulting in one unique identifier
/// per public subgraph that PubGrub can use to check constraints on versions.
///
/// Remark: `Markers.pkgs` is just an implementation detail to prevent cycles
/// with seeds of different versions and same package,
/// which is impossible since we cannot pick two different versions
/// of the same package in the same public subgraph.
pub enum PkgSeeds {
    Constraint(Seed),
    Markers {
        seed_markers: Set<Seed>,
        pkgs: Set<String>,
    },
}

/// A seed is the identifier associated with the private package
/// at the origin of a public subgraph.
pub struct Seed {
    /// Seed package identifier
    pub name: String,
    /// Seed version identifier
    pub version: SemVer,
}
}

Implementing choose_package_version is trivial if we simply use the function choose_package_with_fewest_versions provided by pubgrub. Implementing get_dependencies is slightly more complicated. Have a look at the complete implementation if needed, the main ideas are the following.

#![allow(unused)]
fn main() {
fn get_dependencies(&self, package: &Package, version: &SemVer)
-> Result<Dependencies<Package, SemVer>, ...> {
    match &package.seeds {
        // A Constraint variant does not have any dependency
        PkgSeeds::Constraint(_) => Ok(Dependencies::Available(Map::default())),
        // A Markers variant has dependencies to:
        // - one Constraint variant per seed marker
        // - one Markers variant per original dependency
        PkgSeeds::Markers { seed_markers, pkgs } => {
            // Seed constraints, one per seed for this package@version.
            let seed_constraints = ...;
            // Figure out if there are private dependencies.
            let has_private = ...;
            Ok(Dependencies::Available(
                // Chain the seed constraints with actual dependencies.
                seed_constraints
                    .chain(index_deps.iter().map(|(p, (privacy, r))| {
                        let seeds = if privacy == &Privacy::Private {
                            // make a singleton seed package
                        } else if has_private {
                            // this is public but there is also a private dep,
                            // so add the source package to the seed markers
                        } else {
                            // simply reuse the parent seed markers
                        };
                        ( Package { name: p, seeds }, r )
                    }))
                    .collect(),
            ))
        }
    }
}
}

Pre-release versions

Pre-releasing is a very common pattern in the world of versioning. It is however one of the worst to take into account in a dependency system, and I highly recommend that if you can avoid introducing pre-releases in your package manager, you should.

In the context of pubgrub, pre-releases break the fundamental properties of the solver that there is or isn't a version between two versions "x" and "x+1", that there cannot be a version "(x+1).alpha.1" depending on whether an input version had a pre-release specifier.

Pre-releases are often semantically linked to version constraints written by humans, interpreted differently depending on context. For example, "2.0.0-beta" is meant to exist previous to version "2.0.0". Yet, in many versioning schemes it is not supposed to be contained in the set described by 1.0.0 <= v < 2.0.0, and only within sets where one of the bounds contains a pre-release marker such as 2.0.0-alpha <= v < 2.0.0. This poses a problem to the dependency solver because of backtracking. Indeed, the PubGrub algorithm relies on knowledge accumulated all along the propagation of the solver front. And this knowledge is composed of facts, that are thus never removed even when backtracking happens. Those facts are called incompatibilities and more info about those is available in the "Internals" section of the guide. The problem is that if a fact recalls that there is no version within the 1.0.0 <= v < 2.0.0 range, backtracking to a situation where we ask for a version within 2.0.0-alpha <= v < 2.0.0 will return nothing even without checking if a pre-release exists in that range. And this is one of the fundamental mechanisms of the algorithm, so we should not try to alter it.

Playing again with packages?

In the light of the "bucket" and "proxies" scheme we introduced in the section about allowing multiple versions per package, I'm wondering if we could do something similar for pre-releases. Normal versions and pre-release versions would be split into two subsets, each attached to a different bucket. In order to make this work, we would need a way to express negative dependencies. For example, we would want to say: "a" depends on "b" within the (2.0, 3.0) range and is incompatible with any pre-release version of "b". The tool to express such dependencies is already available in the form of Term which can be a Positive range or a Negative one. We would have to adjust the API for the get_dependencies method to return terms instead of a ranges. This may have consequences on other parts of the algorithm and should be thoroughly tested.

One issue is that the proxy and bucket scheme would allow for having both a normal and a pre-release version of the same package in dependencies. We do not want that, so instead of proxy packages, we might have "frontend" packages. The difference being that a proxy links a source to a target, while a frontend does not care about the source, only the target. As such, only one frontend version can be selected, thus followed by either a normal version or a pre-release version but not both.

Another issue would be that the proxy and bucket scheme breaks strategies depending on ordering of versions. Since we have two proxy versions, one targetting the normal bucket, and one targetting the pre-release bucket, a strategy aiming at the newest versions will lean towards normal or pre-release depending if the newest proxy version is the one for the normal or pre-release bucket. Mitigating this issue seems complicated, but hopefully, we are also exploring alternative API changes that could enable pre-releases.

Multi-dimensional ranges

Building on top of the Ranges API, we could implement a custom VersionSet of multi-dimensional ranges:

#![allow(unused)]
fn main() {
pub struct DoubleRange<V1: Version, V2: Version> {
    normal_range: Range<V1>,
    prerelease_range: Range<V2>,
}
}

With multi-dimensional ranges we could match the semantics of version constraints in ways that do not introduce alterations of the core of the algorithm. For example, the constraint 2.0.0-alpha <= v < 2.0.0 could be matched to:

#![allow(unused)]
fn main() {
DoubleRange {
    normal_range: Ranges::empty(),
    prerelease_range: Ranges::between("2.0.0-alpha", "2.0.0"),
}
}

And the constraint 2.0.0-alpha <= v < 2.1.0 would have the same prerelease_range but would have 2.0.0 <= v < 2.1.0 for the normal range. Those constraints could also be interpreted differently since not all pre-release systems work the same. But the important property is that this enables a separation of the dimensions that do not behave consistently with regard to the mathematical properties of the sets manipulated.

All this needs more experimentation, to try reaching a sweet spot API-wise and performance-wise. If you are eager to experiment with all the extensions and limitations mentioned in this section of the guide for your dependency provider, don't hesitate to reach out to us in our zulip stream or in GitHub issues to let us know how it went!

Internals of the PubGrub algorithm

For an alternative / complementary explanation of the PubGrub algorithm, you can read the detailed description of the solver provided by the original PubGrub author in the GitHub repository of the dart package manager pub.

PubGrub is an algorithm inspired by conflict-driven nogood learning (CDNL-ASP), an approach presented by Gabser, Kaufmann and Schaub in 2012. The approach consists in iteratively taking decisions (here picking a package and version) until reaching a conflict. At that point it records a nogood (an "incompatibility" in PubGrub terminology) describing the root cause of the conflict and backtracks to a state previous to the decision leading to that conflict. CDNL has many similarities with CDCL (conflict-driven clause learning) with the difference that nogoods are conjunctions while clauses are disjunctions of literals. More documentation of their approach is available on their website.

At any moment, the PubGrub algorithm holds a state composed of two things, (1) a partial solution and (2) a set of incompatibilities. The partial solution (1) is a chronological list of "assignments", which are either decisions taken or version constraints for packages where no decision was made yet. The set of incompatibilities (2) is an ever-growing collection of incompatibilities. We will describe them in more details later but simply put, an incompatibility describes packages that are dependent or incompatible, that is packages that must be present at the same time or that cannot be present at the same time in the solution.

Incompatibilities express facts, and as such are always valid. Therefore, the set of incompatibilities is never backtracked, only growing and recording new knowledge along the way. In contrast, the partial solution contains decisions and deductions (called "derivations" in PubGrub terminology), that are dependent on every decision made. Therefore, PubGrub needs to be able to backtrack the partial solution to an older state when there is a conflict.

Overview of the algorithm

Solver main loop

The solver runs in a loop with the following steps:

Perform unit propagation on the currently selected package.
Make a decision: pick a new package and version compatible with the current state of the partial solution.
Retrieve dependencies for the newly selected package and transform those into incompatibilities.

At any point within the loop, the algorithm may fail due to an impossibility to solve a conflict or an error occuring while trying to retrieve dependencies. When there is no more decision to be made, the algorithm returns the decisions from the partial solution.

Unit propagation overview

Unit propagation is the core mechanism of the algorithm. For the currently selected package, unit propagation aims at deriving new constraints (called "terms" in PubGrub and "literals" in CDNL terminology), from all incompatibilities referring to that package. For example, if an incompatibility specifies that packages a and b are incompatible, and if we just made a decision for package a, then we can derive a term specifying that package b should not appear in the solution.

While browsing incompatibilities, we may stumble upon one that is already "satisfied" by the current state of the partial solution. In our previous example, that would be the case if we had previously already made a decision for package b (in practice that exact situation could not happen but let's leave that subtlety for later). If an incompatibility is satisfied, we call that a conflict and must perform conflict resolution to backtrack the partial solution to a state previous to that conflict. Details on conflict resolution are presented in its dedicated section.

Terms

Dependency solving is a complex task where intuition may not be correct or scale to complex situations. We therefore anchor this task in sound mathematics and logic primitive. In turn, this demands precise notation and translations between the primitives of an application layer (Cargo.toml, requirements.txt, ...) and those of the underlying mathematics (CDCL, CDNL, ...). We introduce some of that notation here.

Definition

For any given package, we describe a set of possible versions as a range. For example, a range may correspond to a single version, the set of versions higher than 2 and lower than 5, the set containing every possible version or even the set containing no version at all. And once we have ranges, we can build terms, defined as either positive or negative ranges.

#![allow(unused)]
fn main() {
pub enum Term<V> {
    Positive(Range<V>),
    Negative(Range<V>),
}
}

A term is a literal evaluated either true or false depending on the evaluation context. A positive term is evaluated true if and only if a version contained in its range was selected. A negative term is evaluated true if and only if a version not contained in its range was selected, or no version was selected.

Remark on negative terms:

A negative term is different than the positive one with its complement range. Indeed, saying "a version was picked in the complement of this range", is different than saying "no version was picked or a version was picked in the complement of this range".

In this guide, for any given range $r$, we will note $[r]$ its associated positive term, and $\neg [r]$ its associated negative term. And for any term $T$, whether positive or negative range, we will note $\overline{T}$ the negation of that term, transforming a positive range into an negative one and vice versa. Therefore we have the following notation rules,

\[\begin{eqnarray} \overline{[r]} &=& \neg [r], \nonumber \\ \overline{\neg [r]} &=& [r]. \nonumber \\ \end{eqnarray}\]

Remark on notation:

To keep the notation precise, we only use the $\neg$ symbol in front of ranges, such as $\neg[r]$. So we know when seeing it that we are talking about a negative term. In contrast, we use the overline symbol generically, so we can't make the assumption that the presence, or absence, of overline describes a positive or negative term. So for a generic term $T$, we will not write $\neg T$, but $\overline{T}$, and for a range $r$, we will not write $\neg \neg [r]$, but $\overline{\neg [r]}$ which is also directly $[r]$.

Special terms

Provided that we have defined an empty range of versions $\varnothing$, there are two terms with special behavior which are $[\varnothing]$ and $\neg [\varnothing]$. By definition, $[\varnothing]$ is evaluated true if and only if a version contained in the empty range is selected. This is impossible and as such the term $[\varnothing]$ is always evaluated false. And by negation, the term $\neg [\varnothing]$ is always evaluated true.

Intersection of terms

We define the "intersection" of two terms as the conjunction of those two terms (a logical AND). Therefore, if any of the terms is positive, the intersection also is a positive term. Given any two ranges of versions $r_1$ and $r_2$, the intersection of terms based on those ranges is defined as follows,

\[\begin{eqnarray} [r_1] \land [r_2] &=& [r_1 \cap r_2], \nonumber \\ [r_1] \land \neg [r_2] &=& [r_1 \cap r_2^C], \nonumber \\ \neg [r_1] \land \neg [r_2] &=& \neg [r_1 \cup r_2]. \nonumber \\ \end{eqnarray}\]

Where $\cap$ and $\cup$ are the notations for set intersections and unions of version ranges, and $r_2^C$ is the complement set of the one defined by the range $r_2$.

For any two terms $T_1$ and $T_2$, their union and intersection are related by De Morgan's rule:

\[ \overline{T_1 \lor T_2} = \overline{T_1} \land \overline{T_1}. \]

Relation between terms

We say that a term $T_1$ is satisfied by another term $T_2$ if $T_2$ implies $T_1$, i.e. when $T_2$ is evaluated true then $T_1$ must also be true. This is equivalent to saying that $T_2$ is a subset of $T_1$, which is verified if $ T_2 \land T_1 = T_2 $.

Note on comparability of terms:

Checking if a term is satisfied by another term is accomplished in the code by verifying if the intersection of the two terms equals the second term. It is thus very important that terms have unique representations, and by consequence also that ranges have a unique representation.

In the provided Range type, ranges are implemented as an ordered vec of non-intersecting semi-open intervals. It is thus important that they are always reduced to their canonical form. For example, the range 2 <= v < 2 is actually empty and thus should not be represented by vec![(2, Some(2))] but by the empty vec![]. This requires special care when implementing range intersection.

Incompatibilities

Definition

Incompatibilities are called "nogoods" in CDNL-ASP terminology. An incompatibility is a conjunction of package terms that must be evaluated false, meaning at least one package term must be evaluated false. Otherwise we say that the incompatibility has been "satisfied". Satisfied incompatibilities represent conflicts and thus the goal of the PubGrub algorithm is to build a solution such that none of the produced incompatibilities are ever satisfied. If one incompatibility becomes satisfied at some point, the algorithm finds the root cause of it and backtracks the partial solution before the decision at the origin of that root cause.

Remark: incompatibilities (nogoods) are the opposite of clauses in traditional conflict-driven clause learning (CDCL) which are disjunctions of literals that must be evaluated true, so have at least one literal evaluated true.

The gist of CDCL is that it builds a solution to satisfy a conjunctive normal form (conjunction of clauses) while CDNL builds a solution to unsatisfy a disjunctive normal form (disjunction of nogoods).

In addition, PubGrub is a lazy CDNL algorithm since the disjunction of nogoods (incompatibilities) is built on the fly with the solution.

In this guide, we will note incompatibilities with curly braces. An incompatibility containing one term $T_a$ for package $a$ and one term $T_b$ for package $b$ will be noted

\[ \{ a: T_a, b: T_b \}. \]

Remark: in a more "mathematical" setting, we would probably have noted $ T_a \land T_b $, but the chosen notation maps well with the representation of incompatibilities as hash maps.

Properties

Packages only appear once in an incompatibility. Since an incompatibility is a conjunction, multiple terms for the same package are merged with the intersection of those terms.

Terms that are always satisfied can be removed from an incompatibility. We previously explained that the term $ \neg [\varnothing] $ is always evaluated true. As a consequence, it can safely be removed from the conjunction of terms that is the incompatibility.

\[ \{ a: T_a, b: T_b, c: \neg [\varnothing] \} = \{ a: T_a, b: T_b \} \]

Dependencies can be expressed as incompatibilities. Saying that versions in range $ r_a $ of package $ a $ depend on versions in range $ r_b $ of package $ b $ can be expressed by the incompatibility

\[ \{ a: [r_a], b: \neg [r_b] \}. \]

Unit propagation

If all terms but one of an incompatibility are satisfied by a partial solution, we can deduce that the remaining unsatisfied term must be evaluated false. We can thus derive a new unit term for the partial solution which is the negation of the remaining unsatisfied term of the incompatibility. For example, if we have the incompatibility $ \{ a: T_a, b: T_b, c: T_c \} $ and if $ T_a $ and $ T_b $ are satisfied by terms in the partial solution then we can derive that the term $ \overline{T_c} $ can be added for package $ c $ in the partial solution.

Rule of resolution

Intuitively, we are able to deduce things such as if package $ a $ depends and package $ b $ which depends on package $ c $, then $ a $ depends on $ c $. With incompatibilities, we would note

\[ \{ a: T_a, b: \overline{T_b} \}, \quad \{ b: T_b, c: \overline{T_c} \} \quad \Rightarrow \quad \{ a: T_a, c: \overline{T_c} \}. \]

This is the simplified version of the rule of resolution. For the generalization, let's reuse the "more mathematical" notation of conjunctions for incompatibilities $ T_a \land T_b $ and the above rule would be

\[ T_a \land \overline{T_b}, \quad T_b \land \overline{T_c} \quad \Rightarrow \quad T_a \land \overline{T_c}. \]

In fact, the above rule can also be expressed as follows

\[ T_a \land \overline{T_b}, \quad T_b \land \overline{T_c} \quad \Rightarrow \quad T_a \land (\overline{T_b} \lor T_b) \land \overline{T_c} \]

since for any term $ T $, the disjunction $ T \lor \overline{T} $ is always true. In general, for any two incompatibilities $ T_a^1 \land T_b^1 \land \cdots \land T_z^1 $ and $ T_a^2 \land T_b^2 \land \cdots \land T_z^2 $ we can deduce a third, called the resolvent whose expression is

\[ (T_a^1 \lor T_a^2) \land (T_b^1 \land T_b^2) \land \cdots \land (T_z^1 \land T_z^2). \]

In that expression, only one pair of package terms is regrouped as a union (a disjunction), the others are all intersected (conjunction). If a term for a package does not exist in one incompatibility, it can safely be replaced by the term $ \neg [\varnothing] $ in the expression above as we have already explained before.

Partial solution

The partial solution is the part of PubGrub state holding all the decisions taken and the derivations computed from unit propagation on almost satisfied incompatibilities. We regroup decisions and derivations under the term "assignment".

The partial solution must be backtrackable when conflicts are detected. For this reason all assignments are recorded with their associated decision level. The decision level of an assignment is a counter for the number of decisions that have already been taken (including that one if it is a decision). If we represent all assignments as a chronological vec, they would look like follows:

[
  (0, root_derivation),
  (1, root_decision),
  (1, derivation_1a),
  (1, derivation_1b),
  ...,
  (2, decision_2),
  (2, derivation_2a),
  ...,
]

The partial solution must also enable efficient evaluation of incompatibilities in the unit propagation loop. For this, we need to have efficient access to all assignments referring to the packages present in an incompatibility.

Conflict resolution

As stated before, a conflict is a satisfied incompatibility that we detected in the unit propagation loop. The goal of conflict resolution is to backtrack the partial solution such that we have the following guarantees:

The root cause incompatibility of the conflict is almost satisfied (such that we can continue unit propagation).
The following derivations will be different than before conflict resolution.

Let the "satisfier" be the earliest assignment in the partial solution making the incompatibility fully satisfied by the partial solution up to that point. We know that we want to backtrack the partial solution at least previous to that assignment. Backtracking only makes sense if done at decision levels frontiers. As such the conflictual incompatibility can only become "almost satisfied" if there is only one package term related to incompatibility satisfaction at the decision level of that satisfier. When the satisfier is a decision this is trivial since all previous assignments are of lower decision levels. When the satisfier is a derivation however we need to check that property. We do that by computing the "previous satisfier" decision level. The previous satisfier is (if it exists) the earliest assignment previous to the satisfier such that the partial solution up to that point, plus the satisfier, makes the incompatibility satisfied. Once we found it, we know that property (1) is guaranteed as long as we backtrack to a decision level between the one of the previous satisfier and the one of the satisfier, as long as these are different.

If the satisfier and previous satisfier decisions levels are the same, we cannot guarantee (1) for that incompatibility after backtracking. Therefore, the key of conflict resolution is to derive a new incompatibility for which we will be able to guarantee (1). And we have seen how to do that with the rule of resolution. We will derive a new incompatibility called the "prior cause" as the resolvent of the current incompatibility and the incompatibility which is the cause of the satisfier. If necessary, we repeat that procedure until finding an incompatibility, called the "root cause" for which we can guarantee that it will be almost satisfied after backtracking (1).

Now the question is where do we cut? Is there a reason we cut at the previous satisfier decision level? Is it to guarantee (2)? Would that not be guaranteed if we picked another decision level? Is it because backtracking further back will reduce the number of potential conflicts?

Building a report tree

Terminal incompatibility

Whenever we build an incompatibility that will always be satisfied, version solving has failed. The empty incompatibility, for example is an incompatibility for which terms of all packages are $ \neg [\varnothing] $ and thus all terms are satisfied. Another terminal incompatibility is an incompatibility containing a single package term, satisfied by picking the package and version at the root of the solution, the one for which we want to resolve dependencies.

Derivation tree to report tree

Incompatibilities are either external or derived. External incompatibilities are the one expressing facts independent of the solver deductions capabilities, such as dependencies, unavailable dependencies, missing versions etc. In contrast, derived incompatibilities are the one obtained through the rule of resolution when computing prior causes. Every derived incompatibility keeps a reference to the two incompatibilities that were used to derive it. As a consequence, a chain of derived incompatibilities defines a binary tree, that we call the derivation tree.

When version solving failed, it is thus possible to take the derivation tree of the terminal incompatibility to build a complete explanation of why it failed. That derivation tree however is using incompatibilities whose shape are dependent on internal implementation details. The purpose of the report tree is then to transform the derivation tree into a data structure easily usable for reporting.

Report tree type

In order to provide information in the most detailed way, the report tree uses enum types that try to be as self-explanatory as possible. I'm not sure the current design, based on a recursive (boxed) enum is the best one but it has the advantage of presenting the binary report tree in a very straightforward manner, easy to process.

Duplicate nodes

Though it has the shape of a binary tree, and can be represented as a binary tree, the derivation tree is actually a derivation graph. Indeed, even if every derived incompatibility was built from two others, some incompatibilities may have been used to derive multiple new incompatibilities.

TODO: ascii representations similar to the ones in the error reporting section of pub solver.md.

There is still much API exploration work to be done on error reporting.

Testing and benchmarking

Any non-trivial software is flawed and it is a programmer's goal to make it correct, readable and fast. Testing helps getting correct programs, and benchmarking helps making them faster. In this section we present the approach and tools used to test and benchmark pubgrub.

Note on reproducibility:

"Insanity is doing the same thing over and over again, but expecting different results". Einstein probably didn't came up with that one but this is still very much the definition of non-reproducibility, and it can drive us mad when chasing heisenbugs. For this reason we try to avoid everything that would make pubgrub non reproducible, such that every failed test can be reproduced and fixed.

Property testing

To test pubgrub, we employ a mix of unit tests, integration tests and property tests. Some unit tests are present for example in the version module to validate that the parsing of semantic versions is correct. Integration tests are located in the tests/ directory. Property tests are co-located both with unit tests and integration tests depending on required access to some private implementation details.

version_ranges additionally exposes version_ranges::proptest_strategy to help testing both pubgrub and user code.

Examples

We have multiple example cases inside tests/examples.rs. Those mainly come from dart documentation of the solver and are simple end-to-end examples for which we know the expected results. The first example called no_conflict is a simple case where the root package depends on one package which itself has a dependency to another package. The tests there compare the expected result with the solution of the solver for each of those examples. These were very useful when making progress on PubGrub implementation and can now also be referred to as example usage of the API.

Unit property testing

Property testing consists in defining invariants, generating random valid inputs for the tested functions, and verifying that the invariants hold for the results. Here are some examples extracted from the range module.

#![allow(unused)]
fn main() {
proptest! {
    #[test]
    fn negate_is_different(range in strategy()) {
        assert_ne!(range.negate(), range);
    }

    #[test]
    fn double_negate_is_identity(range in strategy()) {
        assert_eq!(range.negate().negate(), range);
    }

    #[test]
    fn negate_contains_opposite(range in strategy(), version in version_strat()) {
        assert_ne!(range.contains(&version), range.negate().contains(&version));
    }
}
}

As you can see, the input of the testing function is specified in an unusual manner, using a function called a "strategy". This is the terminology used by the proptest crate and it simply is a way to describe how are randomly generated the values used as inputs to those property tests. Don't hesitate to have a look at the corresponding strategy() function defined just above the extracted code if you want to know more about that.

End-to-end property testing

Defining and testing properties for small units of code like ranges implementation is rather easy. Coming up with interesting properties for end-to-end testing such as results of full resolution is different. But the most difficult part is probably finding a "strategy" to generate random but valid registries of packages and dependencies. This is the work that has been done in tests/proptest.rs for the registry_strategy() function.

The simplest implementation of registry_strategy() would be any::<Map<P, Map<V, Map<P, Range<V>>>>(), with some machinery to convert to an OfflineDependencyProvider. While this works, it would almost certainly generate unsolvable dependencies. Indeed random package names in dependencies have an almost null probability of being the same than existing package names.

Let's defer picking the dependencies until we have a list of available names. Luckily proptest has an Index type for this use case of picking something out of a list that has not yet been generated. This leaves us with any::Map<P, Map<V, Map<Index, Range<V>>>(), with more machinery to get the P for each index. While this works, the generated versions have very low probability of being the same than existing versions for a given package.

Let's also use Index to ensure our Ranges are relevant. To identify each Index we will name Ip the one for package names, and Ia and Ib the ones to define version ranges. This leaves us with any::Map<P, Map<V, Map<Ip, (Ia, Ib)>>(). The conversion from Map<Ip, (Ia, Ib)> to Map<P, Range<V>> is done by first picking a dependency P using Ip and then picking up two versions for that package with the Ia and Ib indices. We can then call Range::between(versions[Ia], versions[Ib].bump()) to build a range. If versions[Ib] < versions[Ia], we use Range::between(versions[Ib], versions[Ia].bump()) instead.

Now we finally have something that makes interesting registries! But not particularly realistic ones since almost all of them end up with packages that indirectly depend on themselves. PubGrub is designed to solve dependencies with at most one version per package, so that kind of circular dependencies will very often end up unsolvable.

To fix this lets make sure that we have a DAG, by having each package only depend on packages with a lower index. One solution is to represent dependencies in a side list Vec<(Ip, Id, (Ia, Ib))>. If Ip < Id then we switch them to maintain the acyclic nature of the graph. This is currently how we generate registries of dependencies, suggestions to improve are welcome!

Generating random registries of packages may produce cases where dependency resolution would take too long. For this reason, we introduced in the DependencyProvider trait definition a function called should_cancel which is called in the solver loop. By default it does nothing but can be overwritten such as in TimeoutDependencyProvider (defined in tests/proptest.rs), where the solver is stopped after a certain amount of time.

Once all this is setup, we have to come up with good properties. Here are some of these:

The solver should return the same result on multiple runs with the same input. That may seem trivial, but thinks like hashmaps do add some randomness. So that test ensures that we configured properly everything that could prevent reproducibility of the solver.
Changing the order in which valid package versions are tried should not change the existence of a solution or not. Indeed, some freedom is available for the dependency provider to pick which package and version to choose next. We must ensure that it cannot change the existence of solution for our implementation of the solver algorithm.
Removing a dependency cannot prevent existence of a solution. If a solution was found in a given situation, removing a dependency cannot get us in a situation where the solver does not find a solution anymore. Only adding dependencies should impact that.
Removing a package that does not appear in a solution cannot break that solution. Just as before, it should not impact the existence of a solution.

Comparison with a SAT solver

The SAT problem aims at answering if there exist a set of Boolean variables assignments satisfying a given Boolean expression. So if we can formulate dependencies as a Boolean expression, we can use these well tested tools to compare the result of pubgrub with the one of a SAT solver. SAT solvers usually work with Boolean expressions in a conjunctive normal form (CNF) meaning a conjunction of clauses, an "AND of ORs". So our goal is to convert the following rules of dependency solving into a set of clauses.

There must be only one version per package.
Dependencies of a package must be present if that package is present.
The root package must be present in the solution.

Each package version $(p,v)$ is associated to a unique Boolean variable $b_{p,v}$ that can be true or false. For a given package $p$ and its set of existing versions $V_p$, the property (1) can be expressed by the set of clauses

\[ \{ \neg b_{p,v_1} \lor \neg b_{p,v_2} \ | \ (v_1, v_2) \in V_p^2, v_1 \neq v_2 \}. \]

Each one of these clauses specifies that $v_1$ or $v_2$ is not present in the solution for package $p$. These clauses are generated by the sat_at_most_one function in the testing code. A more efficent approach is used when a package has 4 or more versions but the idea is the same. For a given package version $(p,v)$ depending on another package $d$ at versions $(v_1, v_2, \cdots, v_k)$, the property (2) can be encoded by the clause

\[ \neg b_{p,v} \lor b_{d,v_1} \lor b_{d,v_2} \lor \cdots \lor b_{d,v_k} \]

specifying that either $(p,v)$ is not present in the solution, or at least one of versions $(v_1, v_2, \cdots, v_k)$ of package $d$ is present in the solution. Finally, the last constraint of version solving (3) is encoded with the following unit clause,

\[ b_{r,v_r} \]

where $(r, v_r)$ is the root package version for which we are solving dependencies.

Once the conversion to the SAT formulation is done, we can combine it with property testing, and verify the following properties:

If pubgrub finds a solution, the SAT solver is also satisfied by that solution.
If pubgrub does not find a solution, neither does the SAT solver.

Benchmarking

If you are interested in performance optimization for pubgrub, we suggest reading The Rust Performance Book. Microbenchmarks generally do not represent real world performance, so it's best to start with a slow case in uv or cargo and look at a profile, e.g. with samply.

A first step is optimizing IO/network requests, caching and type size in the downstream code, which is usually the bottleneck over the pubgrub algorithm. Using Arc and splitting types into large and small variants often helps a lot. The next step is to optimize prioritization, to reduce the amount of work that pubgrub has to do, here pubgrub should give better information to make this easier for users. These usually need to be done before pubgrub itself becomes a bottleneck.

Side note about code layout and performance

I highly recommend watching the talk "Performance Matters" by Emery Berger presented at strangeloop 2019 for more information on "sound performance analysis" and "effective performance profiling". There is an issue in criterion about the "stabilizer" tool. And for causal profiling, it seems possible to directly use coz for rust programs.

How can I contribute? Here are some ideas

Use it! Indeed there is quite some work left for custom dependency providers. So just using the crate, building you own dependency provider for your favorite programming language and letting us know how it turned out would be amazing feedback already!
Non failing extension for multiple versions. Currently, the solver works by allowing only one version per package. In some contexts however, we may want to not fail if multiple versions are required, and return instead multiple versions per package. Such situations may be for example allowing multiple major versions of the same crate. But it could be more general than that exact scenario.

PubGrub Guide