Module pubgrub::solver

PubGrub version solving algorithm.

It 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, PubGrub tries to provide a very human-readable and clear explanation as to why that failed. Below is an example of explanation present in the introductory blog post about PubGrub

Because dropdown >=2.0.0 depends on icons >=2.0.0 and
  root depends on icons <2.0.0, dropdown >=2.0.0 is forbidden.

And because menu >=1.1.0 depends on dropdown >=2.0.0,
  menu >=1.1.0 is forbidden.

And because menu <1.1.0 depends on dropdown >=1.0.0 <2.0.0
  which depends on intl <4.0.0, every version of menu
  requires intl <4.0.0.

So, because root depends on both menu >=1.0.0 and intl >=5.0.0,
  version solving failed.

The algorithm is generic and works for any type of dependency system as long as packages (P) and versions (V) implement the Package and Version traits. Package is strictly equivalent and automatically generated for any type that implement Clone + Eq + Hash + Debug + Display. Version simply states that versions are ordered, that there should be a minimal lowest version (like 0.0.0 in semantic versions), and that for any version, it is possible to compute what the next version closest to this one is (bump). For semantic versions, bump corresponds to an increment of the patch number.

API

let solution = resolve(&dependency_provider, package, version)?;

Where dependency_provider supplies the list of available packages and versions, as well as the dependencies of every available package by implementing the DependencyProvider trait. The call to resolve for a given package at a given version will compute the set of packages and versions needed to satisfy the dependencies of that package and version pair. If there is no solution, the reason will be provided as clear as possible.

Structs

OfflineDependencyProvider

A basic implementation of DependencyProvider.

Enums

Dependencies

An enum used by DependencyProvider that holds information about package dependencies. For each Package there is a Range of concrete versions it allows as a dependency.

Traits

DependencyProvider

Trait that allows the algorithm to retrieve available packages and their dependencies. An implementor needs to be supplied to the resolve function.

Functions

choose_package_with_fewest_versions

This is a helper function to make it easy to implement DependencyProvider::choose_package_version. It takes a function list_available_versions that takes a package and returns an iterator of the available versions in preference order. The helper finds the package from the packages argument with the fewest versions from list_available_versions contained in the constraints. Then takes that package and finds the first version contained in the constraints.

resolve

Main function of the library. Finds a set of packages satisfying dependency bounds for a given package + version pair.

Type Definitions

DependencyConstraints

Subtype of Dependencies which holds information about all possible versions a given package can accept. There is a difference in semantics between an empty Map<P, Range> inside DependencyConstraints and Dependencies::Unknown: the former means the package has no dependencies and it is a known fact, while the latter means they could not be fetched by DependencyProvider.