Skip to content

Instantly share code, notes, and snippets.

Created July 10, 2023 09:40
Show Gist options
  • Save julian-klode/5e7b9e8e9d78eb9bc1b506011680a04b to your computer and use it in GitHub Desktop.
Save julian-klode/5e7b9e8e9d78eb9bc1b506011680a04b to your computer and use it in GitHub Desktop.
#include <list>
#include <queue>
#include <vector>
#include <apt-pkg/pkgcache.h>
#include <apt-pkg/depcache.h>
#include <apt-pkg/policy.h>
namespace APT
* \brief APT 3.0 solver
* This is a simple solver focused on understandability and sensible results, it
* will not generally find all solutions to the problem but will try to find the best
* ones.
* It is a brute force solver with heuristics, conflicts learning, and 2**32 levels
* of backtracking.
class Solver
struct State;
struct Work;
// Policy
pkgPolicy *policy;
std::vector<State> states;
std::priority_queue<Work> work;
int depth;
void Pop();
void Push();
// \brief Mark the package for install. This is annoying as it incurs a decision
void Install(pkgCache::PkgIterator Pkg);
// \brief Install a version.
void Install(pkgCache::VerIterator Ver);
// \brief Do not install this package
void Reject(pkgCache::PkgIterator Pkg);
// \brief Do not install this version
void Reject(pkgCache::VerIterator Ver);
// \brief Apply the selections from the dep cache to the solver
bool FromDepCache(pkgDepCache *Cache);
// \brief Apply the solver result to the depCache
bool ToDepCache(pkgDepCache *Cache);
// \brief Solve the dependencies
bool Solve();
// \brief Solve
bool Solve(pkgCache::VerIterator Choice);
}; // namespace APT
* \brief A single work item
* A work item is a positive dependency that still needs to be resolved. Work
* is ordered, by depth, length of solutions, and optionality.
* The work can always be recalculated from the state by iterating over dependencies
* of all packages in there, finding solutions to them, and then adding all dependencies
* not yet resolved to the work queue.
struct APT::Solver::Work
// \brief Issuer of the work
map_pointer<State> issuer;
// \brief The depth at which the item has been added
int depth;
// \brief Whether this is an optional work item, they will be processed last
bool optional;
// \brief Possible solutions to this task, ordered in order of preference
std::list<pkgCache::Version *> solutions;
* \brief The solver state
* For each version, the solver records a decision at a certain level. It
* maintains an array mapping from version ID to state.
struct APT::Solver::State
// \brief The reason for causing this state (invalid for NONE).
// Rejects may have been caused by a later state. Consider we select
// between x1 and x2 in depth = N. If we now find dependencies of x1
// leading to a conflict with a package in K < N, we will record all
// of them as REJECT in depth = K.
// You can follow the reason chain upwards as long as the depth
// doesn't increase to unwind.
map_pointer<State> reason = 0;
enum class Decision
// \brief We have not made a choice about the package yet
// \brief We need to install this package
// \brief We cannot install this package (need conflicts with it)
// \brief This package was listed as a Recommends of a needs package.
// \brief This package was listed as a Suggests of a needs package
} decision = Decision::NONE;
// \brief The depth at which the decision has been taken
unsigned int depth = 0;
void APT::Solver::Push()
void APT::Solver::Pop()
static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int));
for (auto &state : states)
if (state.depth > depth)
state = {};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment