DOCSEARCHbyAlgolia
Submit Docs

pubgrub

repository·dev·Indexed 18 days ago

https://github.com/pubgrub-rs/pubgrub

A high-performance version resolution algorithm written in Rust. It finds compatible package versions that satisfy transitive dependency constraints and provides actionable error messages via DerivationTree and DefaultStringReporter when resolution fails. The library is generic over package types and version formats, and is used by tools like uv.

Tokens
9.4K
Snippets
17
Records
44
Agent score
62%

What's inside pubgrub

  1. Overview of PubGrub

    dev

    PubGrub is a high-performance version resolution algorithm designed to find a set of packages and versions that satisfy all constraints of a set of packages and their transitive dependencies. It is implemented in Rust and is highly flexible, allowing users to customize:

    • Package types: Supports generic package types, including virtual packages.
    • Version formats: Generic over the version format and version set used.
    • Prioritization: Users can control package and version prioritization (e.g., solving for highest or lowest versions).
    • Error rendering: Error message output can be customized.

    This implementation is used by tools like uv and is intended as a replacement for Cargo's solver.

  2. Understand `Ranges` equality limitations

    dev

    The equality implementation for Ranges<T> has limitations because it cannot account for the existence of values between coordinates in a discrete space.

    Two Ranges that cover the same set of versions may be reported as unequal if their internal segment representations differ. For example, in Ranges<u32>:

    • (Unbounded, Included(42u32)) is not equal to (Included(0), Included(42u32)) because the implementation cannot guarantee there are no versions between 0 and -inf.
    • (Included(1), Included(5)) is not equal to the union of (Included(1), Included(3)) and (Included(4), Included(5)) because the implementation cannot guarantee there is no version between 3 and 4.

  3. Getting started with PubGrub

    dev

    To begin using PubGrub, you can refer to the following resources:

  4. Configure package and version types

    dev

    PubGrub is generic over the types used for packages and versions:

    • Package Names: Any type implementing the Package trait. A type automatically implements Package if it implements Clone + Eq + Hash + Debug + Display. String is a common choice.
    • Version Requirements: Any type implementing the VersionSet trait. Ranges<V> is provided for cases where standard ordering and equality are sufficient.
    • Version Numbers: The type used within a VersionSet. It must implement Clone + Ord + Debug + Display. The library provides SemanticVersion for standard semantic versioning rules.

  5. Configure optional features for `version-ranges`

    dev

    The version-ranges crate provides optional features for extended functionality:

    • serde: Enables serialization and deserialization of Ranges. Note that the underlying version type T must also support serde.
    • proptest: Provides proptest strategies specifically for Ranges<u32> to facilitate property-based testing.

  6. Implement or use the VersionSet trait

    dev

    The VersionSet trait defines the mathematical operations required to manipulate sets of versions within the PubGrub algorithm. While you can implement this trait for your own version types, the library provides an optimized implementation via the Ranges<T> type.

    Key Concepts

    • Mathematical Contract: The solver relies on the mathematical properties of set operations (complement, intersection, union, etc.). It assumes all versions are possible, regardless of whether they actually exist in a registry.
    • Equality and Canonicalization: Implementations must ensure that Eq is strictly equivalent to structural equality. If two different representations describe the same set of versions (e.g., >=1,<4 || >=2,<5 and >=1,<5), they must be equal under Eq. This is critical for the solver to correctly determine relationships between sets.

    Core Operations

    Constructors

    • empty(): Returns a set containing no versions.
    • singleton(v: Self::V): Returns a set containing only the specified version v.
    • full(): Returns a set containing all possible versions (implemented as the complement of empty()).

    Set Operations

    • contains(&self, v: &Self::V) -> bool: Checks if a specific version is part of the set.
    • complement(&self) -> Self: Returns the set of all versions not in the current set.
    • intersection(&self, other: &Self) -> Self: Returns the set of versions present in both sets.
    • union(&self, other: &Self) -> Self: Returns the set of versions present in either or both sets.

    Relationship Queries

    • is_disjoint(&self, other: &Self) -> bool: Returns true if the two sets have no overlapping segments.
    • subset_of(&self, other: &Self) -> bool: Returns true if all versions in self are also contained in other.

  7. Handle unavailable dependencies with `Dependencies` enum

    dev

    When implementing get_dependencies, you must return a Dependencies enum. This distinguishes between a package that truly has no dependencies and one where dependencies could not be retrieved.

    • Dependencies::Available(DependencyConstraints<P, VS>): The package has a known set of dependencies.
    • Dependencies::Unavailable(M): The dependencies could not be fetched. M is a custom type used to explain why (e.g., network error, missing cache, or unsupported format). This allows PubGrub to treat the unavailability as a reason for conflict in the resolution process.

  8. Understand DerivationTree incompatibilities

    dev

    A DerivationTree is a binary tree representing the reasons why a solution could not be found. The nodes in the tree are categorized into two types:

    • External Incompatibilities: These are base facts independent of the algorithm, such as:
      • dependencies: A specific package version requires a specific range of another package.
      • missing dependencies: A package's dependencies are unavailable.
      • absence of version: No version of a package exists within a required range.
    • Derived Incompatibilities: These are logical deductions made by the algorithm during execution (e.g., if A depends on B and B depends on C, then A depends on C).

  9. Understand the DerivationTree for dependency resolution failures

    dev

    When dependency resolution fails, PubGrub produces a DerivationTree. This tree represents the chain of incompatibilities that led to the failure. It is composed of two types of nodes:

    1. External Incompatibilities: These are root causes not derived from other incompatibilities. They include:
      • NotRoot: The initial attempt to pick the root package.
      • NoVersions: No versions exist for a specific package in the given set.
      • FromDependencyOf: An incompatibility arising from a package's dependencies.
      • Custom: A user-defined reason for unusability.
    2. Derived Incompatibilities: These are incompatibilities inferred from two other causes (cause1 and cause2). They represent logical conclusions drawn from existing constraints.

    You can use .packages() on a DerivationTree to retrieve a Set of all packages involved in the failure chain.

    let packages = derivation_tree.packages();

  10. Generate error reports using DefaultStringReporter

    dev

    To convert a DerivationTree into a human-readable string explaining why resolution failed, use the DefaultStringReporter. This reporter recursively traverses the tree and produces a multi-line explanation, often using line references (e.g., (1)) to avoid repeating complex sub-trees.

    If you are working in an environment where some versions might be missing (like an offline mode), you can call .collapse_no_versions() on your DerivationTree before reporting. This merges NoVersions incompatibilities into other constraints to create a cleaner, more logical report.

    use pubgrub::report::{DerivationTree, DefaultStringReporter, Reporter};

// Assuming `tree` is a DerivationTree<P, VS, M>
let report = DefaultStringReporter::report(&tree);
println!("{report}");

  11. Report dependency resolution errors with DefaultStringReporter

    dev

    When resolve returns a PubGrubError::NoSolution, you receive a DerivationTree. To turn this tree into a human-readable error message, use the DefaultStringReporter.

    It is recommended to call derivation_tree.collapse_no_versions() before reporting. This simplifies the output by removing NoVersions external incompatibilities, making the explanation more direct (e.g., instead of saying 'there is no version of foo in range X', it simply shows the dependency chain that led to the conflict).

    use pubgrub::{resolve, OfflineDependencyProvider, DefaultStringReporter, Reporter, PubGrubError, Ranges};

// ... setup dependency_provider ...

match resolve(&dependency_provider, "root", 1u32) {
    Ok(solution) => println!("{:?}", solution),
    Err(PubGrubError::NoSolution(mut derivation_tree)) => {
        // Simplify the tree to remove 'no version' noise
        derivation_tree.collapse_no_versions();
        // Print human-readable error
        eprintln!("{}", DefaultStringReporter::report(&derivation_tree));
    }
    Err(err) => panic!("{:?}", err),
}

  12. Perform operations on version ranges

    dev

    Once constructed, you can use several optimized methods to manipulate or query Ranges objects:

    • contains(v): Checks if a specific version is within the range.
    • contains_many(iter): Checks if multiple versions are within the range.
    • union(other): Combines two ranges.
    • intersection(other): Finds the overlap between two ranges.
    • complement(): Returns the set of all versions not in the current range.
    • is_disjoint(other): Checks if two ranges have no overlap.
    • subset_of(other): Checks if one range is entirely contained within another.