# How uv-resolver Performs Dependency Resolution with PubGrub: A Technical Deep Dive

> Explore how uv-resolver performs dependency resolution with PubGrub. Learn about its three-layer architecture handling Python specifics like extras and markers for efficient solving.

- Repository: [Astral/uv](https://github.com/astral-sh/uv)
- Tags: deep-dive
- Published: 2026-03-01

---

**The `uv-resolver` crate implements Python dependency resolution by delegating the core solving algorithm to the `pubgrub-rs` library, wrapping it in a three-layer architecture that handles Python-specific concepts like extras, environment markers, and URL dependencies while orchestrating the resolution loop through unit propagation, fork handling, and batch prefetching.**

The `uv-resolver` crate in the `astral-sh/uv` repository provides a high-performance Python dependency resolver built on the proven PubGrub algorithm. This article examines how `uv-resolver` performs dependency resolution using PubGrub, detailing the architectural layers that bridge generic version solving with Python packaging semantics, the mechanics of the resolution loop, and the handling of environment-specific constraints.

## Architecture of the uv-resolver PubGrub Implementation

The implementation consists of three tightly-coupled layers that adapt the generic PubGrub solver to Python's packaging ecosystem.

### The Three-Layer Architecture

| Layer | Purpose | Key Implementation |
|-------|---------|-------------------|
| **PubGrub Model** | Lightweight representation of packages, version ranges, and incompatibilities | `PubGrubPackage`/`PubGrubPackageInner` in [`pubgrub/package.rs`](https://github.com/astral-sh/uv/blob/main/pubgrub/package.rs) (lines 34-96) |
| **Dependency Provider** | Supplies version lists and dependency edges to PubGrub | `UvDependencyProvider` in [`dependency_provider.rs`](https://github.com/astral-sh/uv/blob/main/dependency_provider.rs) |
| **Resolver Orchestration** | Drives the solver, handles prefetching, forking, and result extraction | `Resolver::solve` in [`resolver/mod.rs`](https://github.com/astral-sh/uv/blob/main/resolver/mod.rs) (lines 13-124) |

## Building the PubGrub Resolution Problem

Before the solving loop begins, `uv-resolver` constructs the initial state and converts Python requirements into PubGrub terms.

### Root Package Initialization

The resolver initializes PubGrub with a root package representing the project being resolved. In [`resolver/mod.rs`](https://github.com/astral-sh/uv/blob/main/resolver/mod.rs) at lines 33-38, the state is created:

```rust
let root = PubGrubPackage::from(PubGrubPackageInner::Root(self.project.clone()));
let pubgrub = State::init(root.clone(), MIN_VERSION.clone());

```

### Converting Python Requirements

Requirements, constraints, and overrides are transformed into `PubGrubDependency` objects. The `from_package` constructor in [`pubgrub/package.rs`](https://github.com/astral-sh/uv/blob/main/pubgrub/package.rs) (lines 98-134) handles marker simplification for extras:

```rust
let marker = marker.simplify_extras_with(|_| true);
if let Some(extra) = extra { … } else if …

```

This ensures that a package and its extra variant share version constraints while maintaining distinct dependency sets.

## The Resolution Loop: How uv-resolver Solves Dependencies

The core solving logic resides in `ResolverState::solve` within [`resolver/mod.rs`](https://github.com/astral-sh/uv/blob/main/resolver/mod.rs). This method orchestrates the PubGrub algorithm through eight distinct phases.

### 1. Unit Propagation

The solver repeatedly calls `unit_propagation` to derive implied constraints. At line 365 in [`resolver/mod.rs`](https://github.com/astral-sh/uv/blob/main/resolver/mod.rs):

```rust
let result = state.pubgrub.unit_propagation(state.next);

```

If propagation fails, the resulting `NoSolutionError` is converted to a human-readable `ResolveError`.

### 2. Parallel Prefetching

To minimize network latency, the resolver prefetches metadata for candidate packages before they are strictly needed. The `pre_visit` method (lines 88-101) identifies registry packages and initiates concurrent fetches:

```rust
Self::pre_visit( … )?;

```

### 3. Conflict Reprioritization

Packages accumulating many conflicts are bumped in priority to trigger earlier backtracking. This heuristic reduces the search space:

```rust
Self::reprioritize_conflicts(&mut state); // line 503

```

### 4. Package Selection

The highest-priority undecided package is selected using PubGrub's partial solution:

```rust
let (highest_priority_pkg, _) = state.pubgrub.partial_solution.pick_highest_priority_pkg( … );

```

### 5. Version Choice

The `choose_version` method (lines 1115-1135) handles three distinct cases:
- **URL-based requirements** via `choose_version_url`
- **Registry packages** via `choose_version_registry`, querying the `Index` for available versions
- **System/Python packages** handled as special cases

```rust
let version = self.choose_version( … )?; // lines 1115-1135

```

### 6. Fork Handling

When a version introduces environment marker forks (e.g., `python_version < "3.8"`), the solver creates separate `ForkState` instances. These are sorted by fork strategy (fewest forks vs. highest Python bound) and pushed onto the work-list:

```rust
let forked_states = self.version_forks_to_fork_states(state, forks);

```

This allows the resolver to generate multiple valid resolutions for different environment configurations.

### 7. Dependency Addition

Selected version dependencies are converted to `PubGrubDependency` objects and added to the state:

```rust
state.pubgrub.add_package_version_dependencies( … ); // line 3063

```

### 8. Loop Continuation

The loop continues until all packages are assigned (success) or an unresolvable conflict forces backtracking to a previous fork.

## Handling Python-Specific Constraints

The resolver extends PubGrub to handle Python packaging's unique features through specialized package variants.

### Extras and Dependency Groups

**Extras** are modeled as proxy `PubGrubPackage::Extra` packages that depend on both the base package and the extra-specific dependencies. This proxy pattern ensures that when an extra is requested, its variant must resolve to the exact same version as the base package. The implementation in [`pubgrub/package.rs`](https://github.com/astral-sh/uv/blob/main/pubgrub/package.rs) strips extra expressions from markers during package construction, allowing the solver to enforce version equality while maintaining separate dependency graphs for each extra.

**Groups** (PEP 735-style optional dependency groups) use the `Group` variant similarly, allowing unified resolution of development dependencies.

### Environment Markers and Universal Resolution

Environment markers become distinct `Marker` packages. When a dependency specifies environment markers (e.g., `python_version < "3.10"`), the resolver creates **forks**—separate resolution states for each possible evaluation of the marker. The `version_forks_to_fork_states` method in [`resolver/mod.rs`](https://github.com/astral-sh/uv/blob/main/resolver/mod.rs) generates these states, which are then prioritized and solved independently. This forking mechanism enables universal resolution, producing lockfiles that contain environment-specific dependencies while ensuring compatibility across different Python versions and platforms.

## Error Reporting and Derivation Chains

When resolution fails, `pubgrub::NoSolutionError` is transformed into a detailed `ResolveError` that includes a **derivation chain**. The `DerivationChainBuilder` in [`resolver/derivation.rs`](https://github.com/astral-sh/uv/blob/main/resolver/derivation.rs) traces backward through the incompatibilities recorded during solving, while [`pubgrub/report.rs`](https://github.com/astral-sh/uv/blob/main/pubgrub/report.rs) formats this chain into an explanation of why specific package versions conflict. This provides developers with actionable insights about dependency incompatibilities rather than opaque failure messages.

## Summary

- The `uv-resolver` crate implements Python dependency resolution by wrapping the `pubgrub-rs` library in a three-layer architecture.
- **PubGrub packages** are represented by `PubGrubPackage` variants that encode Python-specific concepts like extras, groups, and environment markers.
- The **resolution loop** in [`resolver/mod.rs`](https://github.com/astral-sh/uv/blob/main/resolver/mod.rs) orchestrates unit propagation, parallel prefetching, conflict reprioritization, and fork handling to efficiently explore the solution space.
- **Environment markers** trigger resolution forks, enabling universal lockfiles that work across Python versions and platforms.
- Failed resolutions produce detailed **derivation chains** that explain incompatibility sources.

## Frequently Asked Questions

### What is PubGrub and why does uv-resolver use it?

PubGrub is a version solving algorithm designed to handle complex dependency constraints efficiently. The `uv-resolver` uses the `pubgrub-rs` implementation because it provides deterministic, exhaustive search capabilities with excellent error reporting through derivation chains. This allows `uv` to resolve Python dependencies faster than traditional SAT solvers while maintaining correctness across complex version ranges and environment markers.

### How does uv-resolver handle optional dependencies like extras?

The resolver models extras as distinct `PubGrubPackage::Extra` variants that depend on both the base package and the extra-specific dependencies. This proxy pattern ensures that when an extra is requested, its variant must resolve to the exact same version as the base package. The implementation in [`pubgrub/package.rs`](https://github.com/astral-sh/uv/blob/main/pubgrub/package.rs) strips extra expressions from markers during package construction, allowing the solver to enforce version equality while maintaining separate dependency graphs for each extra.

### What happens when a dependency has environment markers?

When a dependency specifies environment markers (e.g., `python_version < "3.10"`), the resolver creates **forks**—separate resolution states for each possible evaluation of the marker. The `version_forks_to_fork_states` method in [`resolver/mod.rs`](https://github.com/astral-sh/uv/blob/main/resolver/mod.rs) generates these states, which are then prioritized and solved independently. This forking mechanism enables universal resolution, producing lockfiles that contain environment-specific dependencies while ensuring compatibility across different Python versions and platforms.

### How does uv-resolver report resolution failures?

When the PubGrub algorithm determines that no solution exists, the resolver converts the `NoSolutionError` into a detailed `ResolveError` that includes a **derivation chain**. The `DerivationChainBuilder` in [`resolver/derivation.rs`](https://github.com/astral-sh/uv/blob/main/resolver/derivation.rs) traces backward through the incompatibilities recorded during solving, while [`pubgrub/report.rs`](https://github.com/astral-sh/uv/blob/main/pubgrub/report.rs) formats this chain into an explanation of why specific package versions conflict. This provides developers with actionable insights about dependency incompatibilities rather than opaque failure messages.