Crate pubgrub

Expand description

PubGrub version solving algorithm.

Version solving consists in efficiently finding a set of packages and versions that satisfy all the constraints of a given project dependencies. In addition, when that is not possible, we should try to provide a very human-readable and clear explanation as to why that failed.

§Basic example

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:

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

We can model that scenario with this library as follows


type NumVS = Ranges<u32>;

let mut dependency_provider = OfflineDependencyProvider::<&str, NumVS>::new();

dependency_provider.add_dependencies(
    "root",
    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, "root", 1u32).unwrap();

§Package and Version flexibility

The OfflineDependencyProvider used in that example is generic over the way package names, version requirements, and version numbers are represented.

The first bound is the type of package names. It can be anything that implements our Package trait. The Package trait is automatic if the type already implements Clone + Eq + Hash + Debug + Display. So things like String will work out of the box.

The second bound is the type of package requirements. It can be anything that implements our VersionSet trait. This trait is used to figure out how version requirements are combined. If the normal Ord/PartialEq operations are all that is needed for requirements, our Ranges type will work.

The chosen VersionSet in turn specifies what can be used for version numbers. This type needs to at least implement Clone + Ord + Debug + Display. For convenience, this library provides SemanticVersion that implements the basics of semantic versioning rules.

§DependencyProvider trait

In our previous example we used the OfflineDependencyProvider, which is a basic implementation of the DependencyProvider trait.

But we might want to implement the DependencyProvider trait for our own type. Let’s say that we will use String for packages, and SemanticVersion for versions. This may be done quite easily by implementing the three following functions.

type SemVS = Ranges<SemanticVersion>;

impl DependencyProvider for MyDependencyProvider {
    fn choose_version(&self, package: &String, range: &SemVS) -> Result<Option<SemanticVersion>, Infallible> {
        unimplemented!()
    }

    type Priority = usize;
    fn prioritize(&self, package: &String, range: &SemVS, conflicts_counts: &PackageResolutionStatistics) -> Self::Priority {
        unimplemented!()
    }

    fn get_dependencies(
        &self,
        package: &String,
        version: &SemanticVersion,
    ) -> Result<Dependencies<String, SemVS, Self::M>, Infallible> {
        Ok(Dependencies::Available(DependencyConstraints::default()))
    }

    type Err = Infallible;
    type P = String;
    type V = SemanticVersion;
    type VS = SemVS;
    type M = String;
}

The first method choose_version chooses a version compatible with the provided range for a package. The second method prioritize in which order different packages should be chosen. Usually prioritizing packages with the fewest number of compatible versions speeds up resolution. But in general you are free to employ whatever strategy suits you best to pick a package and a version.

The third method get_dependencies aims at retrieving the dependencies of a given package at a given version.

In a real scenario, these two methods may involve reading the file system or doing network request, so you may want to hold a cache in your DependencyProvider implementation. How exactly this could be achieved is shown in CachingDependencyProvider (see examples/caching_dependency_provider.rs). You could also use the OfflineDependencyProvider type defined by the crate as guidance, but you are free to use whatever approach makes sense in your situation.

§Solution and error reporting

When everything goes well, the algorithm finds and returns the complete set of direct and indirect dependencies satisfying all the constraints. The packages and versions selected are returned as SelectedDependencies<P, V>. But sometimes there is no solution because dependencies are incompatible. In such cases, resolve(…) returns a PubGrubError::NoSolution(derivation_tree), where the provided derivation tree is a custom binary tree containing the full chain of reasons why there is no solution.

All the items in the tree are called incompatibilities and may be of two types, either “external” or “derived”. Leaves of the tree are external incompatibilities, and nodes are derived. External incompatibilities have reasons that are independent of the way this algorithm is implemented such as

dependencies: “package_a” at version 1 depends on “package_b” at version 4
missing dependencies: dependencies of “package_a” are unavailable
absence of version: there is no version of “package_a” in the range [3.1.0 4.0.0[

Derived incompatibilities are obtained during the algorithm execution by deduction, such as if “a” depends on “b” and “b” depends on “c”, “a” depends on “c”.

This crate defines a Reporter trait, with an associated Output type and a single method.

pub trait Reporter<P: Package, VS: VersionSet, M: Eq + Clone + Debug + Display> {
    type Output;

    fn report(derivation_tree: &DerivationTree<P, VS, M>) -> Self::Output;
}

Implementing a Reporter may involve a lot of heuristics to make the output human-readable and natural. For convenience, we provide a default implementation DefaultStringReporter that outputs the report as a String. You may use it as follows:

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 may have directly:

foo 1.0.0 <= v < 2.0.0 depends on bar 2.0.0 <= v < 3.0.0.

Beware though that if you are using some kind of offline mode with a cache, you may want to know that some versions do not exist in your cache.

Structs§

DefaultStringReportFormatter: Default formatter for the default reporter.
DefaultStringReporter: Default reporter able to generate an explanation as a String.
Derived: Incompatibility derived from two others.
OfflineDependencyProvider: A basic implementation of DependencyProvider.
PackageResolutionStatistics: Statistics on how often a package conflicted with other packages.
Range: Ranges represents multiple intervals of a continuous range of monotone increasing values.
Ranges: Ranges represents multiple intervals of a continuous range of monotone increasing values.
SemanticVersion: Type for semantic versions: major.minor.patch.

Enums§

Dependencies: An enum used by DependencyProvider that holds information about package dependencies. For each Package there is a set of versions allowed as a dependency.
DerivationTree: Derivation tree resulting in the impossibility to solve the dependencies of our root package.
External: Incompatibility that is not derived from other incompatibilities.
PubGrubError: Errors that may occur while solving dependencies.
Term: A positive or negative expression regarding a set of versions.
VersionParseError: Error creating SemanticVersion from String.

Traits§

DependencyProvider: Trait that allows the algorithm to retrieve available packages and their dependencies. An implementor needs to be supplied to the resolve function.
Package: Trait for identifying packages. Automatically implemented for types already implementing Clone + Eq + Hash + Debug + Display.
ReportFormatter: Trait for formatting outputs in the reporter.
Reporter: Reporter trait.
VersionSet: A set of versions.

Functions§

resolve: Finds a set of packages satisfying dependency bounds for a given package + version pair.

Type Aliases§

DependencyConstraints: Holds information about all possible versions a given package can accept. There is a difference in semantics between an empty map inside DependencyConstraints and Dependencies::Unavailable: the former means the package has no dependency and it is a known fact, while the latter means they could not be fetched by the DependencyProvider.
Map: Map implementation used by the library.
NoSolutionError: There is no solution for this set of dependencies.
SelectedDependencies: Concrete dependencies picked by the library during resolve from DependencyConstraints.
Set: Set implementation used by the library.

Crate pubgrubCopy item path