Resolve RPM packages with resolvo (based on libsolv)

[wolfv]

We've been working on a new Rust library called resolvo that works quite similarly to libsolv which is famously used in dnf and friends.

We're considering to add some RPM support as well, so that one could ingest repository data from e.g. Fedora and resolve to compatible matching packages.

There are a few features that we haven't implemented in resolvo yet, that RPM makes use of, such as:

• weak dependencies (recommends, suggests, supplements, enhances)
• the notion of obsoletes (replacing a package name with another package name)
• the "provides" to have more than a 1-1 mapping of package name to provider

However, we are confident that one can build an interesting prototype with what resolvo currently offers and it should be feasible to extend resolvo to also provide the features mentioned above if we see community interest.

So I am testing the waters and I am curious to hear what people think!

PS: resolvo is also a bit faster than libsolv at this point for complicated problems in the conda ecosystem because we recently tuned the order of evaluations.

[dralley]

Very interesting! @korewaChino

At one point I was interested in trying to get libsolv bindings for Rust, but it seemed to be more pain than I was willing to expend. But a pure-Rust alternative would be excellent.

Resolvo implements a fast package resolution algorithm based on CDCL SAT solving. If resolvo is unable to find a solution it outputs a human-readable error message:

:chefs_kiss:

[dralley]

PS: resolvo is also a bit faster than libsolv at this point for complicated problems in the conda ecosystem because we recently conda/rattler#349.

Correct me if I'm wrong but it looks like that PR is still using libsolv (the perf comparison is between two versions of libsolv-rs) and the optimizations themselves might be in the client code using the solver library, not in the solver library?

[baszalmstra]

You are not wrong but yesterday we renamed libsolv-rs to resolvo and moved it to its own repository. The libsolv column is using C bindings to libsolv, the libsolv-rs columns are versions of resolvo. The main one is the latest.

[dralley]

BTW if anyone does plan on creating a full client, don't reimplement the XML parsing, work with me on https://github.com/dralley/rpmrepo_metadata/

[wolfv]

Hey @dralley thanks for the note! The rpmrepo_metadata repository sounds like an excellent starting point to build a full client, indeed.

[wolfv]

@dralley thanks to rpmrepo_metadata I was able to build a POC for the RPM resolver pretty easily: https://github.com/prefix-dev/resolvo-rpm

It includes a little utility to fetch repodata from a URL. It then instantiates a resolvo DependencyProvider with all the packages & dependencies.

One thing that I noted for rpmrepo_metadata is that some structs do not derive Hash, Clone, Eq / PartialEq and a few of those.

Anyways, would love some feedback / community contributions on resolvo-rpm. It could also be a fun exercise to download & install the packages if someone is up for it!

[dralley]

@ignatenkobrain You may find this interesting!

[dralley]

How difficult would it be to write a "repoclosure"-like tool that would check if a repository (or set of repositories) is dependency-closed, and spit out a list of missing dependencies if it is not?

[wolfv]

@dralley interesting idea. maybe @baszalmstra wants to chime in. This would be like resolving for each package and figuring out if it's resolvable, right? I don't think it would be difficult, but could definitely be slow :)

For a simple test one might also get away without the actual SAT solving (and just check if all dependencies are available for the specified version range). That might still leave some conflicts undetected though.

[baszalmstra]

@dralley Would that tool report if there are packages that are not solvable? Or more simply if a package is missing direct dependencies. I guess we could reuse the solver in between runs. That would save the learned rules in between solves. Would be interesting to try!

[korewaChino]

This looks cool. Maybe it would pave the way for an even faster alternative to DNF

[dralley]

Maybe it would pave the way for an even faster alternative to DNF

I don't know about faster because the slow parts of DNF (metadata downloading and lack of parallelism, which are addressed in DNF 5) are mostly unrelated to dependency solving, but it's definitely very cool.