PubGrub version solving algorithm, in Rust

At Packaging Con 2021, we presented a rewrite from scratch of a recent algorithm called PubGrub, as a Rust library aiming at great performance and flexibility for reuse.

Version solving consists in efficiently finding a set of packages and versions that satisfy all the constraints of a given project dependencies. In addition, when that is not possible, PubGrub tries to provide a very human-readable and clear explanation as to why that failed. The introductory blog post about PubGrub presents one such example of failure explanation:

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.

This pubgrub crate provides a Rust implementation of PubGrub. It is generic and works for any type of dependency system as long as packages (P) and versions (V) implement the provided Package and Version traits.

Using the pubgrub crate

A guide with both high-level explanations and in-depth algorithm details is available online. The API documentation is available on docs.rs. A version of the API docs for the unreleased functionality from dev branch is also accessible for convenience.

Contributing

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.

PubGrub

PubGrub is a version solving algorithm, written in 2018 by Natalie Weizenbaum for the Dart package manager. It is supposed to be very fast and to explain errors more clearly than the alternatives. An introductory blog post was published on Medium by its author.

The detailed explanation of the algorithm is provided on GitHub, and complemented by the "Internals" section of our guide. The foundation of the algorithm is based on ASP (Answer Set Programming), and a book called "Answer Set Solving in Practice" by Martin Gebser, Roland Kaminski, Benjamin Kaufmann and Torsten Schaub.