1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
// SPDX-License-Identifier: MPL-2.0
//! 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.
//!
//! # Package and Version traits
//!
//! All the code in this crate is manipulating packages and versions, and for this to work
//! we defined a [Package](package::Package) trait
//! that is used as bounds on most of the exposed types and functions.
//!
//! Package identifiers needs to implement our [Package](package::Package) trait,
//! which is automatic if the type already implements
//! [Clone] + [Eq] + [Hash] + [Debug] + [Display](std::fmt::Display).
//! So things like [String] will work out of the box.
//!
//! TODO! This is all wrong. Need to talk about VS, not Version.
//! Our Version trait requires
//! [Clone] + [Ord] + [Debug] + [Display](std::fmt::Display).
//! For convenience, this library provides [SemanticVersion](version::SemanticVersion)
//! that implements semantic versioning rules.
//!
//! # 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
//! ```
//! # use pubgrub::solver::{OfflineDependencyProvider, resolve};
//! # use pubgrub::range::Range;
//!
//! type NumVS = Range<u32>;
//!
//! let mut dependency_provider = OfflineDependencyProvider::<&str, NumVS>::new();
//!
//! dependency_provider.add_dependencies(
//! "root", 1u32, [("menu", Range::full()), ("icons", Range::full())],
//! );
//! dependency_provider.add_dependencies("menu", 1u32, [("dropdown", Range::full())]);
//! dependency_provider.add_dependencies("dropdown", 1u32, [("icons", Range::full())]);
//! dependency_provider.add_dependencies("icons", 1u32, []);
//!
//! // Run the algorithm.
//! let solution = resolve(&dependency_provider, "root", 1u32).unwrap();
//! ```
//!
//! # DependencyProvider trait
//!
//! In our previous example we used the
//! [OfflineDependencyProvider](solver::OfflineDependencyProvider),
//! which is a basic implementation of the [DependencyProvider](solver::DependencyProvider) trait.
//!
//! But we might want to implement the [DependencyProvider](solver::DependencyProvider)
//! trait for our own type.
//! Let's say that we will use [String] for packages,
//! and [SemanticVersion](version::SemanticVersion) for versions.
//! This may be done quite easily by implementing the three following functions.
//! ```
//! # use pubgrub::solver::{DependencyProvider, Dependencies};
//! # use pubgrub::version::SemanticVersion;
//! # use pubgrub::range::Range;
//! # use pubgrub::type_aliases::Map;
//! # use std::error::Error;
//! # use std::borrow::Borrow;
//! # use std::convert::Infallible;
//! #
//! # struct MyDependencyProvider;
//! #
//! type SemVS = Range<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) -> Self::Priority {
//! unimplemented!()
//! }
//!
//! fn get_dependencies(
//! &self,
//! package: &String,
//! version: &SemanticVersion,
//! ) -> Result<Dependencies<String, SemVS>, Infallible> {
//! unimplemented!()
//! }
//!
//! type Err = Infallible;
//! type P = String;
//! type V = SemanticVersion;
//! type VS = SemVS;
//! }
//! ```
//!
//! The first method
//! [choose_version](crate::solver::DependencyProvider::choose_version)
//! chooses a version compatible with the provided range for a package.
//! The second method
//! [prioritize](crate::solver::DependencyProvider::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](crate::solver::DependencyProvider::get_dependencies)
//! aims at retrieving the dependencies of a given package at a given version.
//! Returns [None] if dependencies are unknown.
//!
//! 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](solver::DependencyProvider) implementation.
//! How exactly this could be achieved is shown in `CachingDependencyProvider`
//! (see `examples/caching_dependency_provider.rs`).
//! You could also use the [OfflineDependencyProvider](solver::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
//! [SelectedDepedencies<P, V>](type_aliases::SelectedDependencies).
//! But sometimes there is no solution because dependencies are incompatible.
//! In such cases, [resolve(...)](solver::resolve) returns a
//! [PubGrubError::NoSolution(derivation_tree)](error::PubGrubError::NoSolution),
//! 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 unknown
//! - 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](crate::report::Reporter) trait, with an associated
//! [Output](crate::report::Reporter::Output) type and a single method.
//! ```
//! # use pubgrub::package::Package;
//! # use pubgrub::version_set::VersionSet;
//! # use pubgrub::report::DerivationTree;
//! #
//! pub trait Reporter<P: Package, VS: VersionSet> {
//! type Output;
//!
//! fn report(derivation_tree: &DerivationTree<P, VS>) -> Self::Output;
//! }
//! ```
//! Implementing a [Reporter](crate::report::Reporter) may involve a lot of heuristics
//! to make the output human-readable and natural.
//! For convenience, we provide a default implementation
//! [DefaultStringReporter](crate::report::DefaultStringReporter)
//! that outputs the report as a [String].
//! You may use it as follows:
//! ```
//! # use pubgrub::solver::{resolve, OfflineDependencyProvider};
//! # use pubgrub::report::{DefaultStringReporter, Reporter};
//! # use pubgrub::error::PubGrubError;
//! # use pubgrub::range::Range;
//! #
//! # type NumVS = Range<u32>;
//! #
//! # let dependency_provider = OfflineDependencyProvider::<&str, NumVS>::new();
//! # let root_package = "root";
//! # let root_version = 1u32;
//! #
//! 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()](crate::report::DerivationTree::collapse_no_versions) above.
//! This method simplifies the derivation tree to get rid of the
//! [NoVersions](crate::report::External::NoVersions)
//! external incompatibilities in the derivation tree.
//! So instead of seeing things like this in the report:
//! ```txt
//! 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:
//! ```txt
//! 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.
#![warn(missing_docs)]
pub mod error;
pub mod package;
pub mod range;
pub mod report;
pub mod solver;
pub mod term;
pub mod type_aliases;
pub mod version;
pub mod version_set;
mod internal;