Cooperation with PubGrub-rs.

[Eh2406]

Hello again! I am a maintainer of pubgrub-rs, which is a different dependency resolution algorithm written in Rust. It would be lovely if our projects found ways to support each other!

I have worked hard on the performance of pubgrub. I would love to work on the performance of resolvo. Do you have benchmarks? It would be really cool to have a shared set of benchmarks. For each benchmark case, whichever algorithm is slower I know that it can be solved faster so time to get to work.

As part of our benchmarking work we have collected some real world resolution problems. It would be cool to do differential testing, checking that our algorithms agree on whether there is a valid resolution. If you have a different set of real-world examples, I would love to add them to our benchmark collection!

Such a differential testing suite could also be used with fuzzed input. We have worked hard to develop a proptest random input generator, that currently compares to a SAT solver. Comparing two different implementations with each other is a great case for differential fuzzing.

I know there are design constraints that work better for one algorithm or the other. I would love to add explanations to pubgrub's documentation about when you're algorithm is a better choice. (And work to improve the kinds of problems pubgrub can solve.)

[baszalmstra]

Hi @Eh2406 ! pubgrub-rs has been a massive inspiration for us.

resolvo stems from the rattler projects which implements algorithms and data structures to interact with the conda ecosystem from rust. This includes solving conda environments. resolvo was initially a port/fork of libsolv. We also use the same solver now to solve Pypi packages in the rip project.

Over time resolvo dramatically diverged from the libsolv implementation. Although libsolv supports more use-cases, for our limited feature set resolve is significantly faster. resolvo is also (optionally) incremental (similar to pubgrub) in the sense that you can add information as the solver is working.

I've tried for a while to use pubgrub-rs for conda, I left a number of PRs, issues, and comments. In the end, pubgrub-rs wasn't the right solution for conda for a number of reasons. The biggest one is that version ranges in conda (matchspecs) are non-continuous and set operations can become hard to proof (they can contain regexes for instance).

resolvo (and libsolv) take a different approach where the VersionSet does not represent a mathematical set but instead contains a concrete number of "package versions".

Our biggest test set and benchmarks currently reside in the rattler project where you can also find the conda implementation. We compare the solutions and performance against an alternative implementation that uses libsolv directly.

I would love to work together but Im not really sure where to start! What would you suggest? Do you think it would be possible to share some of the same benchmarks / tests?

Im sure there are still many possibilities to optimize the algorithm! :)

[Eh2406]

I've tried for a while to use pubgrub-rs for conda ... In the end, pubgrub-rs wasn't the right solution for conda for a number of reasons.

I fondly remember your contributions to pubgrub-rs!. I wish it had been an easy fit, but I am excited to see that you had found a way to make forward progress!

I would love to work together but Im not really sure where to start! What would you suggest? Do you think it would be possible to share some of the same benchmarks / tests?

It seems like the functionality of resolvo is a superset of pubgrub-rs. It seems like it should be possible to copy over any of the tests or benchmarks from pubgrub and see how they run on resolvo. That might be a lot of copy and pasted code. Alternatively, we could create a project that uses the code I have developed to generate test cases and runs them on an SAT, resolvo, and pubgrub. If one of them disagrees with the other two it's got a bug.

[baszalmstra]

We also copied the Range struct from pubgrub. Would it make sense to move this (and possibly some other code) to a separate crate? Code that is not tied to any particular resolver?

[Eh2406]

Moving code to a shared dependency allows for more scrutiny and shared improvements. I would love to see Kani or Creusot apply do Range without requiring the rest of our solvers to be proven correct. It will also require more coordination to make sure changes work well for both projects. Everything in life is a trade-off.

[wolfv]

By the way, we'll be at PackagingCon - are you going to be there as well @Eh2406? :) Would be cool to chat more & maybe hack on this during sprints.

[Eh2406]

At this time I'm only planning to attend virtually. Which does seem ashamed, this sounds like a lot of fun.

[Eh2406]

By the way, I'm holding office hours every Wednesday at 4est. If that's a convenient time to chat. If not let me know and I can try make other time available.

[wolfv]

Hey @Eh2406 we're all in the european timezone and it's at 10 PM so most of us are close to hitting the bed.
A couple hours earlier would be much more convenient and I'd be happy to join from time to time (and @baszalmstra probably as well).

[Eh2406]

Office hours have moved three hours earlier to better accommodate. https://github.com/rust-lang/cargo/wiki/Office-Hours has been updated.

[Eh2406]

We also copied the Range struct from pubgrub. Would it make sense to move this (and possibly some other code) to a separate crate? Code that is not tied to any particular resolver?

Sorry for the delay, we finally published this Range code to a separate crate. It already includes several big improvements we've made for our use cases, with more on the way. We would also love to include any improvements you've made! https://docs.rs/version-ranges/0.1.0/version_ranges/