PubGrub version solving algorithm implemented in Rust
PubGrub version solving algorithm implemented in Rust
PubGrub is a high performance version resolution algorithm with good error messages, it finds a set of packages and versions that satisfy all the constraints of a set of packages and their transitive dependencies. This rust implementation is used by uv and as designated replacement for cargo's solver, while other PubGrub implementations are used by dart, bundler and poetry.
This rust implementation of PubGrub is highly flexible. It is generic over the package type (including virtual packages), the version format and version set used, the user controls package and version prioritization (including highest and lowest version solving) and the error rendering can be customized.
The best way to get started with PubGrub are the guide and the algorithm's introductory blog post. There are also some runnable examples in the examples folder. More details are available in the stable API documentation and the development API documentation from the main branch.
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. A detailed explanation of the algorithm is available on GitHub, and complemented by our internals guide. The foundation of the algorithm is based on Answer Set Programming (ASP), and the book "Answer Set Solving in Practice" by Martin Gebser, Roland Kaminski, Benjamin Kaufmann and Torsten Schaub.
While traditional SAT solvers can find a solution fast, they don't provide an understable explanation when they didn't find a solution. PubGrub is both very fast and can explain errors more clearly than the alternatives.
An error message from the blog post:
Because dropdown >=2.0.0 depends on icons >=2.0.0 and
root depends on icons =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.0.0 =1.0.0 and intl >=5.0.0,
version solving failed.Two examples from uv:
× No solution found when resolving dependencies:
╰─▶ Because project[extra2] depends on sortedcontainers==2.4.0 and project[extra1] depends on sortedcontainers==2.3.0, we can conclude that project[extra1] and project[extra2] are incompatible.
And because your project requires project[extra1] and project[extra2], we can conclude that your project's requirements are unsatisfiable.…Discussion and development happens here on GitHub and on our Zulip stream. Please join in!
Remember to always be considerate of others, who may have different native languages, cultures and experiences. We want everyone to feel welcomed, let us know with a private message on Zulip if you don't feel that way.
No open issues yet, or sync has not completed.