PubGrub in Rust: a version solver that explains itself

The problem: find versions that satisfy every constraint

PubGrub is a high performance version resolution algorithm with good error messages, and it finds a set of packages and versions that satisfy all the constraints of a set of packages and their transitive dependencies.

That is the whole job, and it is harder than it sounds, because the constraints come from everywhere. A package declares a range, another package declares a range on that one, and the ranges have to be reconciled against what is actually available. The interesting case is when they cannot be reconciled, and then the question becomes not just whether a solution exists but how to explain that it does not.

That second question is where this algorithm earns its place, and the README makes the comparison directly. While traditional SAT solvers can find a solution fast, they do not provide an understandable explanation when they did not find one. PubGrub is both very fast and can explain errors more clearly than the alternatives.

The Rust implementation is used by uv, and is the designated replacement for Cargo's solver, while other PubGrub implementations are used by the Dart package manager, by Bundler and by Poetry. That is a striking amount of adoption for one algorithm, and it happened because the algorithm and the error messages were designed together rather than the messages being bolted on afterwards.

The project is Rust, licensed MPL-2.0, on the main branch, with the last push on 2026-10-17. The releases are v0.2.1 in June 2021, described as mostly performance improvements, v0.3.0 in February 2025 and v0.4.0 in April 2026.

Genericity is the design, and the price is yours to pay

The README says the Rust implementation is highly flexible, and then lists the three axes along which it is generic.

It is generic over the package type, including virtual packages, over the version format, and over the version set used. On top of that, the user controls package and version prioritisation, including highest and lowest version solving, and the error rendering can be customised.

Each of those is a decision that a conventional solver makes for you. A solver that knows about semver and crates.io can be fast and precise, but it is a solver for one ecosystem, and the day you need to resolve something else you are back to writing one. A solver that is generic over the package type lets you model a virtual package, which is how you express a capability that several real packages provide, and the prioritisation control is what lets you answer the highest and lowest version questions, which are different problems with different answers.

The cost is that the semantics move to the caller. You decide what a version means, how a range is compared, and how the failure is phrased. That is a real amount of work, and it is why the README points at the guide and the introductory blog post as the way in rather than at an API reference.

The other consequence is that this is a library, not a tool. Nothing here downloads anything or reads a manifest. The examples in the repository are the closest thing to a worked application, and they are the place to see what the interface costs in practice.

Underneath: a SAT solver with conflict-driven clause learning

The algorithm section is short and settles the question of what the thing actually is.

PubGrub was introduced in 2018 in a blog post by Natalie Weizenbaum, who developed it for the Dart package manager. Algorithmically, it is a SAT solver using conflict-driven clause learning.

The foundation of the algorithm is based on Answer Set Programming, and the README points at the book Answer Set Solving in Practice by Martin Gebser, Roland Kaminski, Benjamin Kaufmann and Torsten Schaub, which is where the theory is written down properly.

That lineage is worth a sentence for a general engineer. A SAT solver works by encoding a problem as a boolean formula and then searching for a satisfying assignment, and conflict-driven clause learning is the part where the solver remembers what made the last attempt fail so it does not repeat it. PubGrub applies that machinery to version constraints, and the interesting result is that the explanation machinery of a SAT solver, which normally produces an assignment, can be turned into a sentence a human can read. That is what produces the error messages.

The detailed explanation of the algorithm is available on GitHub, and there is an internals guide that complements it, so the source for the theory is a public document rather than a paper behind a paywall.

The error message is the product

The README shows an error message from the original blog post, and it is worth reading slowly, because it is the clearest statement of what this library is for.

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.

Read that as a proof. Each step derives a consequence from the previous one, and the last line states the contradiction. A user who hits an unsatisfiable requirement in a real project gets this shape of explanation, and the shape is the argument that the tool is not lying to them.

The README also shows two examples from uv, which uses this implementation, and they show the same structure with the modern formatting, a tree of consequences ending in a statement that the requirements are unsatisfiable, and in the second case a longer derivation that also uses the available version of a proxy package to derive an incompatibility, then combines it with the workspace requirements.

So if you are evaluating a version solver, the thing to compare is not the speed on a benchmark but the quality of the failure, because the failure is what your users will actually read.

The crate, the workspace and the toolchain

The manifest describes a small, careful crate.

The package is pubgrub at version 0.4.0, with the authors Matthieu Pizenberg, Alex Tokarev and Jacob Finkelman, edition 2024, a minimum Rust version of 1.92, the MIT-style MPL-2.0 licence, the category algorithms, and keywords for dependency, pubgrub, semver, solver and version. The published contents are deliberately narrow, the Cargo.toml, the licence, the readme, the sources, the tests, the examples and the benchmarks, which keeps the crate itself free of anything that is only needed to run the test suite.

There is a workspace with one member, version-ranges, and that member is a path dependency of the main crate at version 0.1.4. Splitting the version range type into its own crate is what lets a caller with an existing version type use their own, and the two crates are released in step.

The runtime dependencies are few: an index map, the log crate for debug output in the tests, a priority queue, a fast hasher, an optional serde with derive, thiserror for the error types, and the version-ranges crate. Serde is a feature rather than a hard dependency, and the optional dependency is what the serde feature switches on, so the default build stays small.

The development dependencies are where the testing story shows: a Criterion benchmark harness, in the codspeed compatibility form, a logger for the tests, a C compiler with a comment explaining it is a lower-bound guard in the minimal-versions CI job, proptest for property tests, ron for a serialisation format, and varisat, which is a SAT solver used to check the solver.

Tests, examples and three benchmarks

The repository listing shows how the project tests itself, and there is a separate directory of runnable examples that doubles as documentation.

The examples are named after what they demonstrate rather than after what they are called. branching_error_reporting.rs and linear_error_reporting.rs are the two shapes of error derivation. caching_dependency_provider.rs shows the dependency provider being cached. unsat_root_message_no_version.rs is about the root message in an unsatisfiable case with no version to point at. And there are three doc_interface files, one for the interface itself, one for its errors and one for its semantics, which is a sign that the public interface is treated as something with a contract that has to be demonstrated.

The benchmarks are three, and the names describe the cases rather than the code. backtracking covers the solver backing out of a wrong branch, large_case is a big instance that requires the serde feature because the input has to be read, and sudoku is the small, dense, heavily constrained problem where a solver either finds the answer or cannot. All three are declared with the Criterion harness turned off, because they are benchmarks rather than tests.

There is also a version-ranges directory at the top level, which is the workspace member, and a test-examples directory, which is the mechanism for compiling the examples as part of the test suite so that they cannot rot.

The standard Rust tooling surrounds all of it: Cargo.lock is committed, there is a changelog, and a commitlint configuration, which is a small signal that the project follows the conventional Rust community norms for commit messages.

Where to read next, and how the project is run

The README is explicit that the best way to get started is the guide and the algorithm's introductory blog post, and that there are runnable examples in the examples folder. More details are in the stable API documentation and in the development API documentation generated from the main branch, which is the arrangement for a library that is still moving.

There is also an internals guide, and the two together, the guide for the user and the internals guide for the algorithm, are the project's real documentation. The API references on docs.rs and on the project's own site are the third stop, and the introductory blog post is the one to read first if you want to understand why the error messages look the way they do.

Development happens on GitHub and on the project's Zulip stream, which is the Rust community's chat, and the README asks people to join in. It closes with a note about being considerate of others, who may have different native languages, cultures and experiences, and asks that anyone who does not feel welcome say so by private message on Zulip. That is an unusually explicit code of conduct paragraph to find in a solver library's README, and it tells you something about the room the project wants to have.

The one piece of missing context in the README is a comparison of the Rust implementation with the other PubGrub implementations. The Dart, Ruby and Python ones are linked, and uv's internals page is linked, but the README does not say whether they are interchangeable or how their APIs differ. If you are choosing between them, that is the question to ask.

Editorial conclusion

Adopt the Rust PubGrub implementation if you are writing a package manager, a lockfile tool or anything else that has to answer the question of which set of versions satisfies a set of constraints, because the library is generic over package types and version formats and its error reporting is the part everyone copies. Do not adopt it expecting a ready-made resolver for a particular ecosystem, because the flexibility is a cost, since the caller has to supply the semantics of a package, a version and a version set. Before you build on it, read the guide and the introductory blog post, and look at the error message rendering in the examples, because that is the part of the design you will spend the most time on and the part your users will read.

Frequently asked questions

Official sources

1. License: MPL-2.0
2. Project website
3. pubgrub-rs/pubgrub on GitHub
4. README
5. Releases