RFC — Towards a new solver for `libmamba`

Context

libsolv has been used since the creation of mamba.

While libsolv is a fundamental dependency of libmamba, its maintenance comes with challenges for mamba but also for conda-forge generally (for instance, see https://github.com/conda-forge/libsolv-feedstock/issues/92 and https://github.com/conda-forge/openmpi-feedstock/issues/153).

[!NOTE]
For more context, see those notes.

Proposed solution

Redesign part of the architecture of mamba so that an alternative solver can be used
Introduce mamba-org/resolvo which, from a socio-technical perspective, seems to be the most relevant candidate.

Based on a POC, which shows that resolvo have more or less the same performance as libsolv.

Proposed plan

[!NOTE]
This plan gives the general direction but is not exhaustive. It might evolve overtime.

Architecture redesign: inheriting classes

Motivation:

Solver and DataBase are exposed to Python thanks to pybind11
we could have a common interface and use std::variant but pybind11 does not work properly with std::variant unfortunately
pybind11 correctly handles inheritance

Schematically, currently we have:

before

Then we would have: after

In this order:

[ ] move some abstractions from mamba::solver::libsolv to mamba::solver, namely:
- [ ] https://github.com/mamba-org/mamba/pull/3378
- [ ] https://github.com/mamba-org/mamba/pull/3385
- [ ] https://github.com/mamba-org/mamba/pull/3380 for libmambapy, this will introduce new imports paths but the current python import paths must work but be deprecated
[ ] create solver::{Solver,DataBase} base classes
- [ ] remove template methods from solver::DataBase
  - [ ] https://github.com/mamba-org/mamba/pull/3382
- [ ] unify the API and the tests
- [ ] adapt the final existing solver::libsolv::{Solver,DataBase} classes accordingly
[ ] adapt libmamba's internals so that they use solver::{Solver,DataBase}
[ ] adapt (micro)mamba's internals (especially the install codepath first)
[ ] introduce final (a priori named) solver::resolvo::{Solver,DataBase} classes
- [ ] introduce the solver::resolvo::DataBase class (WIP in jjerphan/mamba:alt-solver branch)
  - [ ] take the currently installed package into account
  - [ ] adapt resolvo's result in to mamba::solver::Solution
- [ ] introduce the solver::resolvo::Solver class
- [ ] adapt python bindings, either:
  - [ ] introduce libmambapy.bindings.solver.resolvo.{Solver,DataBase}
  - [ ] introduce libmambapy.bindings.solver.{Solver,DataBase} and expose an option to select "libsolv" or "resolvo"
[ ] document all the changes for libmamba and libmambapy public APIs, especially changes in UX and deprecated import paths

Alternative solver

[ ] Correct the UNSAT reports from https://github.com/mamba-org/resolvo/pull/37 and merge it
[ ] Adapt the decide function; several different non-exclusive options exist:
- [ ] Introduce an heuristic à la VSIDS (for instance MiniSAT's VSIDS AKA MVSIDS) (being experimented on jjerphan/resolvo:mvsids)
- [ ] Explore other (more complex) heuristics such the Mapple SAT solvers' or SBAV which is the SOTA (AFAIK)

The general plan seems legit broadly speaking.

Regarding the Database, we could use a base class as you suggested, or try and isolate the parts specific to libsolv in a specific class to use inside Database (because resolvo's API could be very different) but at least Database is already connected to the rest of mamba and hopefully we won't need to change much.
Instead of moving everything in mamba::solver::libsolv to mamba::solver, we may want to leave it as it is and try in the same way to isolate what's related to libsolv and what would be common with resolvo. Unsolvable for example seems to be tightly linked with libsolv internals so that would be a class specific to libsolv and we should maybe wrap it into another one alongside something else for resolvo (we may need to define its API first to know what to do, I don't know if that work has been done yet). So maybe just a renaming would be enough to make it clear it's libsolv specific, or actually keep the same names and just have two namespaces libsolv and resolvo
Same for repo_info
parameters seem general enough, but maybe some classes/structs are specific to libsolv (no equivalent in resolvo, semantically speaking)
Why detemplate Database::add_repo_from_packages? It seems ok to me

Regarding the Database, we could use a base class as you suggested, or try and isolate the parts specific to libsolv in a specific class to use inside Database (because resolvo's API could be very different) but at least Database is already connected to the rest of mamba and hopefully we won't need to change much.

I should have mentioned that resolvo's public API exposes a DependencyProvider (similar to a Database) and a Solver. Based on the initial POC, I am quite confident that we could have similar abstractions for resolvo.

Most of the design points are mostly based on the assumption that introducing bases classes is the right pathway and that the current other abstractions than Database and Solver can be decoupled from libsolv, but we need to validate that this is the right approach (I am pretty sure there are other designs which would avoid having a set of base classes and solver-specific sets of concrete classes).

Edit: For alternatives, I wonder whether template classes with a common template type parameter for the solver could help.

The overall plan looks good, I have some minor concerns, partially because I don't know very well this part of mamba (so some of my concerns might be irrelevant or redundant):

From what I remember from our discussions with Antoine, everything in the solver::libsolv namespace was very specific to libsolv, does Resolvo have exactly the same representations for RepoInfo, parameters and unsolvable ? (more or less same question as Hind).
Depending on the answer to the previous question, it might be easier / more efficient to identify a common API from the bottom, i.e. have both implementations ready (even if not plugged yet) and figure out what is common rather than from the top (i.e. decide a public API, and then figure out how to adapt the existing implementations). You might have already done that work, so do not hesitate to drop this if you're confident in the APIs.
The constraints on DataBase / RepoInfo / Solver must be encoded somehow. My understanding is that Resolvo accepts different implementations of Database, but are the DataBase and the RepoInfo totally decoupled? Same question for RepoInfo and Solver
Why do you need to detemplate add_repo_from_packages ? I guess it's because this will become a virtual function? Having it as a template brings flexibility (instead of imposing to work with std::vector) and will allow to work with ranges when we migrate to C++20.
It might be interesting to have a factory for building the different implementations. This way you only need to bind the base classes, the factory function and an enum to Python

IIRC, resolvo does not have the equivalent of a RepoInfo
This was started on this branch: https://github.com/jjerphan/mamba/tree/alt-solver
Resolvo exposes a DependencyProvider, which can be implemented to have something close to a DataBase but the RepoInfo isn't actually totally decoupled. My intuition is that it will be decoupleable.
For virtuality, yes. Migrating to C++20 is not trivial because bits of the std have been removed in this last version of C++.
Yes, we need to think about this together. I am wondering how to best adapt the Python API, then.

mamba-org / mamba