solver3.cc

#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();

   public:
   Solver();

   // \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
      NONE,
      // \brief We need to install this package
      NEED,
      // \brief We cannot install this package (need conflicts with it)
      REJECT,
      // \brief This package was listed as a Recommends of a needs package.
      SHOULD,
      // \brief This package was listed as a Suggests of a needs package
      MAY,
   } decision = Decision::NONE;

   // \brief The depth at which the decision has been taken
   unsigned int depth = 0;
};

void APT::Solver::Push()
{
   depth++;
}
void APT::Solver::Pop()
{
   static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int));
   depth--;
   for (auto &state : states)
   {
      if (state.depth > depth)
	 state = {};
   }
}