astral-sh/uv

uv-resolver

crates/uv-resolver/ is the dependency resolver — uv's most distinguishing technical asset. It implements a universal, PubGrub-based solver that produces a single lockfile working across all supported Python versions and platforms, plus the lockfile read/write code that turns the solution into a stable on-disk format.

Purpose

Given a set of requirements (requests==2.31.0), constraints (urllib3<2), and overrides, plus a Requires-Python range, plus the relevant indexes and a build context, produce a resolution graph and a lockfile that pin every transitive dependency in a way that can be installed deterministically on any supported platform.

The resolver has to handle:

Universal resolution across Python versions (>=3.8) and operating-system / arch combinations.
Marker-conditional dependencies (requests[security]; python_version < "3.10").
Forking: when dependencies disagree across markers, the resolver explores each marker subspace separately and joins the results.
Conflict markers: when extras or dependency groups conflict, the lockfile annotates entries so an installer can pick the right subset.
Pre-releases, yanks, and --exclude-newer cutoffs.
Hash strategy: locking acceptable hashes per file.
Source distributions: building them in-process to read metadata when wheels aren't available.
Source URLs (file://, git+https://, direct URLs).

Directory layout

crates/uv-resolver/src/
├── lib.rs                   # Re-exports of public API
├── manifest.rs              # Manifest: the input to a resolution (requirements + overrides + ...)
├── options.rs               # Options: resolver knobs (resolution mode, fork strategy, prerelease)
├── candidate_selector.rs    # Picks the next version to try, weighing strategy + prereleases
├── dependency_mode.rs       # Direct vs. transitive dependencies
├── dependency_provider.rs   # PubGrub's dependency-provider trait wrapper (UvDependencyProvider)
├── error.rs                 # 58 KB of typed errors and "no solution found" formatting
├── exclude_newer.rs         # --exclude-newer / --exclude-newer-package
├── exclusions.rs            # Excluded packages
├── flat_index.rs            # Flat-directory index handling
├── fork_indexes.rs          # Per-fork index pinning
├── fork_strategy.rs         # `fewest` vs. `requires-python` fork strategies
├── fork_urls.rs             # Per-fork URL pinning
├── graph_ops.rs             # Operations on the resolution graph
├── marker.rs                # Marker manipulation (intersection, simplification)
├── pins.rs                  # File pins for hash strategy
├── preferences.rs           # Existing lockfile preferences carried into a re-resolution
├── prerelease.rs            # PrereleaseMode
├── pubgrub/                 # PubGrubPackage / PubGrubPython / PubGrubPriorities
├── python_requirement.rs    # PythonRequirement: target vs. exact
├── redirect.rs              # HTTP redirects to alternate index URLs
├── resolution/              # ResolverOutput: the resolved graph + display
├── resolution_mode.rs       # ResolutionMode (highest, lowest, lowest-direct)
├── resolver/                # The actual solver (4268 lines in mod.rs)
│   ├── mod.rs               # Resolver and ResolverState orchestration
│   ├── availability.rs      # UnavailablePackage / UnavailableVersion accounting
│   ├── batch_prefetch.rs    # BatchPrefetcher to overlap metadata fetches
│   ├── derivation.rs        # DerivationChainBuilder for explanations
│   ├── environment.rs       # ResolverEnvironment: forks, marker-disjoint subspaces
│   ├── fork_map.rs          # Per-fork state container
│   ├── index.rs             # InMemoryIndex of metadata
│   ├── indexes.rs           # Combined view of configured indexes
│   ├── provider.rs          # ResolverProvider trait, DefaultResolverProvider
│   ├── reporter.rs          # Progress callbacks
│   ├── system.rs            # System dependencies (e.g., GIL flag)
│   └── urls.rs              # Per-fork URL handling
├── universal_marker.rs      # UniversalMarker: PEP 508 marker + ConflictMarker
├── upgrade.rs               # UpgradePackages: "upgrade these packages, freeze others"
├── version_map.rs           # VersionMap: ordered candidate list per package
├── lock/                    # Lockfile read/write (uv.lock + Pylock TOML)
│   ├── mod.rs               # 273 KB: the entire lockfile format and serialization
│   ├── installable.rs       # Lock + InstallTarget + InstalledPackagesProvider integration
│   ├── tree.rs              # Tree rendering for `uv tree`
│   ├── map.rs               # PackageMap: keyed map of resolved packages
│   ├── export/              # RequirementsTxtExport, CycloneDX SBOM export
│   └── snapshots/           # insta snapshots for the lock format
└── yanks.rs                 # AllowedYanks policy

Key abstractions

Type	File	Role
`Manifest`	`manifest.rs`	Input to a resolution: requirements, constraints, overrides, exclusions, preferences, project, workspace members.
`Options` / `OptionsBuilder`	`options.rs`	Resolver knobs assembled from settings: `ResolutionMode`, `PrereleaseMode`, fork strategy, exclude-newer, dependency mode, flexibility.
`Resolver<Provider, InstalledPackages>`	`resolver/mod.rs`	The orchestrator. Owns a `ResolverState` and a `ResolverProvider`; spawns a fetcher future and a PubGrub solver thread.
`ResolverState`	`resolver/mod.rs`	Per-resolution state: index, capabilities, selector, environment, conflicts, current snapshot of unavailable/incomplete packages.
`ResolverEnvironment`	`resolver/environment.rs`	The set of platforms and Python versions the resolver targets. Implements forking by splitting the environment along disjoint markers.
`ResolverProvider`	`resolver/provider.rs`	Trait for fetching package versions, metadata, and wheel metadata. The default implementation calls into `uv-distribution`.
`InMemoryIndex`	`resolver/index.rs`	Concurrent map of `PackageName` → `OnceMap<Versions>` and `PackageName, Version` → `OnceMap<Metadata>` so concurrent forks share fetches.
`BatchPrefetcher`	`resolver/batch_prefetch.rs`	Overlaps metadata downloads with PubGrub's depth-first search. Looks ahead at likely-next-versions and warms the cache.
`CandidateSelector`	`candidate_selector.rs`	Given a package and a constraint, pick the next version to try. Honors `ResolutionMode`, `PrereleaseMode`, preferences, and yanks.
`UniversalMarker`	`universal_marker.rs`	Conjunction of a PEP 508 `MarkerTree` and a `ConflictMarker` (extras / dependency-group disambiguation).
`Lock`	`lock/mod.rs`	The lockfile data model (`uv.lock`).
`PylockToml`	`lock/mod.rs`	The PEP 751 export format.
`RequirementsTxtExport`	`lock/export/`	`requirements.txt` export.
`Preferences`	`preferences.rs`	"Pinned versions from a previous lock that should be reused if compatible."
`Exclusions`	`exclusions.rs`	Packages or extras to drop from the result.
`UpgradePackages`	`upgrade.rs`	The `--upgrade` / `--upgrade-package` selector — which packages should ignore preferences.
`ResolverOutput` / `DisplayResolutionGraph`	`resolution/`	The resolved graph (a petgraph DAG) and its renderer.
`NoSolutionError` / `NoSolutionHeader` / `ErrorTree`	`error.rs`	The typed error returned when PubGrub gives up, and the human-readable explanation tree.
`ResolveError`	`error.rs`	Top-level error type.

How it works

flowchart LR
    subgraph runtime[Resolution at runtime]
        manifest[Manifest<br/>requirements + constraints + overrides] --> resolver
        options[Options<br/>resolution mode, prereleases, etc] --> resolver
        env[ResolverEnvironment<br/>target Python versions + platforms] --> resolver
        provider[ResolverProvider<br/>fetches versions + metadata] --> resolver
        resolver[Resolver]
        resolver -- spawn solver thread --> solver[PubGrub solver loop]
        resolver -- spawn fetcher future --> fetcher[Async metadata fetcher]
        solver -- needs metadata --> channel((mpsc channel))
        channel --> fetcher
        fetcher -- fills --> index[InMemoryIndex]
        solver -- reads --> index
        solver -- emits --> output[ResolverOutput / Lock]
    end

The dual-thread model

Resolver::resolve (crates/uv-resolver/src/resolver/mod.rs) splits the work between an async fetcher and a synchronous PubGrub solver:

// A channel to fetch package metadata
let (request_sink, request_stream) = mpsc::channel(300);

// Run the fetcher.
let requests_fut = state.clone().fetch(provider.clone(), request_stream).fuse();

// Spawn the PubGrub solver on a dedicated thread.
thread::Builder::new()
    .name("uv-resolver".into())
    .spawn(move || {
        let result = solver.solve(&request_sink);
        let _ = tx.send(result);
    })
    .unwrap();

let resolve_fut = async move { rx.await.map_err(|_| ResolveError::ChannelClosed) };

// Wait for both to complete.
let ((), resolution) = tokio::try_join!(requests_fut, resolve_fut)?;

The solver is synchronous because PubGrub is — but it never blocks on I/O. When it needs package versions or metadata it sends a request through the channel and reads from the shared InMemoryIndex. Each entry is a OnceMap so concurrent forks deduplicate fetches.

Forking

The most novel part of the algorithm is ResolverEnvironment (resolver/environment.rs). PubGrub assumes a single dependency provider, so it can't directly express "package A wants urllib3<2 on Python 3.7 but urllib3>=2 on Python 3.10." uv handles this by forking: detecting marker-disjoint dependency choices and recursively resolving each one in its own ResolverEnvironment. Each fork carries a UniversalMarker describing which markers must be true for that fork's solution to apply.

When all forks complete, the results are joined into a single resolution where each node carries the marker conjunction under which it's installed. The fork_strategy setting (fewest vs. requires-python) controls the heuristics for splitting; the solver only forks when markers are truly disjoint (a long-standing correctness fix from #4135).

The lockfile

Lock and LockVersion in crates/uv-resolver/src/lock/mod.rs define the on-disk uv.lock format. The file is one of the most stability-sensitive parts of uv: a lock written by today's uv must remain installable by future versions.

The format uses TOML with arrays of [[package]] tables, each annotated with markers, extras, dependency groups, and per-distribution hashes. The 273 KB mod.rs covers parsing, validation (SatisfiesResult), reading installable subsets (Installable), and producing the several export formats (RequirementsTxtExport, PylockToml, cyclonedx_json).

Errors

crates/uv-resolver/src/error.rs (~58 KB) is dedicated to producing useful "No solution" explanations. PubGrub's incompatibilities are translated into a tree of human-readable causes (ErrorTree) and rendered with hints when a particular fix is obvious (e.g., "consider relaxing requires-python").

Integration points

Inputs. The resolver takes a ResolverProvider (typically DefaultResolverProvider, which calls into uv-distribution), a BuildContext (from uv-types), and a MarkerEnvironment (from uv-pep508).
Outputs. A ResolverOutput (graph) or a Lock (full lockfile). Downstream consumers are uv-installer (for installation) and the binary crate uv (for printing/exporting).
Concurrency primitives. OnceMap from uv-once-map, DashMap for unavailable-package tracking, tokio::sync::mpsc for solver↔fetcher communication.
Source distributions. When the resolver needs metadata for an sdist that no index has served as PEP 658 metadata, it calls back through the BuildContext into uv-build-frontend.

Entry points for modification

Add a new resolution knob — extend Options and OptionsBuilder in options.rs, plumb it through ResolverState, then expose it in uv-cli and uv-settings.
Change the lockfile format — bump LockVersion in lock/mod.rs, write the new variant, and add a forwards-compatibility check in the deserializer. The integration tests in crates/uv/tests/it/lock.rs (35,569 lines) will tell you if you broke any snapshot.
Tune fork heuristics — fork_strategy.rs and resolver/environment.rs together decide when and how to split.
Improve a "No solution" explanation — error.rs is the place; the ErrorTree formatter is the customer-facing output.

Key source files

File	Purpose
`crates/uv-resolver/src/resolver/mod.rs`	The 4268-line solver loop.
`crates/uv-resolver/src/resolver/environment.rs`	Forking and `ResolverEnvironment`.
`crates/uv-resolver/src/lock/mod.rs`	The lockfile format.
`crates/uv-resolver/src/universal_marker.rs`	`UniversalMarker` and `ConflictMarker`.
`crates/uv-resolver/src/error.rs`	Typed errors and `NoSolutionError` rendering.
`crates/uv-resolver/src/candidate_selector.rs`	Version selection.
`crates/uv-resolver/src/preferences.rs`	Carrying the previous lock forward.
`crates/uv-resolver/src/options.rs`	Resolver options.