Initial implementation of the 3.0 solver

This is a simple backtracking brute-force solver with heurisitcs,
this initial version has the following known gaps:

- Errors are not kept from branches, the error reporting after
  backtracking isn't particularly useful.
- We cannot show automatically removed packages
- We cannot replace packages with others
- We do not have conflict-driven clause learning yet

Untested:

- Multi-arch

This solver is fundamentally different in key aspects:

- It solves smaller dependency groups before larger ones, leading
  us to avoid installing A in A|B if B is installed more often and
  more consistently.

- It only keeps the automatic packages reachable via the strongest
  path. Currently it only implements autoremoval, but not display
  of autoremoval as we simply enqueue all automatically installed
  packages at the end when not doing automatic removal.

  This will need some translation where we Solve() first, and then
  Solve() again with the automatically installed packages added such
  that we can mark them as Garbage for display purposes.

- It does not remove manually installed packages.

Hook the solver in via the EDSP framework, this allows us to achieve
easy initial integration without lots of issues.

A lot of this work was planned and executed in my free time and then
some leaked into work time I suppose.

Implementation notes:

- Restore the full backlog of items

  The annoying thing is that we record only when an item was enqueued
  and not the level at which it was installed, so when going back a
  decision level we might have to reinstall packages that were queued
  at an earlier decision level because they were only installed at a
  later decision level.

- When picking one version, reject the others

- Propagate conflicts up to reverse dependencies

  This will recursively mark every reverse dependency that can
  no longer be satisfied as MUSTNOT.

  Also make sure to recursively call Reject(Ver) from Reject(Pkg)
  to make sure we trigger the Rejections there.

  This means we now end up having Recursion in the algorithm. An
  alternative approach would be to push *reject* items to the heap
  and then do them, but this is not entirely straight forward and
  it may simply not be necessary.

-  Sort upgrades before other optional installs containing subsets

  If I want to upgrade a package A, I schedule A3|A2|A1; if another
  thing depends specifically on A1; we'd not be installed. Hence we
  need to sort upgrades first.

  This only is needed for optional packages; manual packages will
  figure this out naturally.

- Rescoring is lazily implemented. Instead of calling make_heap()
  after rescoring items, we just mark the items as dirty and reinsert
  them. We also only rescore from the main solve loop, Reject() marks
  the heap as needing a rescore due to a Conflict (as some versions will
  no longer be installable), and RescoreWorkIfNeeded() then will do the
  rescoring.

- Recursive unit propagation: Install() and Reject() recursively call
  each other to promote decisions across single-version dependencies
  (or across not-anymore satisfiable reverse-depends).

- Make Reason constructors explicit, this enhances readability

  This makes calls like the one in here be

    Reject(object, Reason(otherObject))

  Ensuring that it's clear that the 2nd argument is a reason at the
  caller side.

- Split Decision into Decision and Hint vs. first draft

  When branching/deciding, we do not want to override SHOULD and MAY.
  We do not actually use them yet, and we do actually clean them when
  backtracking, but let's at least keep the data structure correct.

  Convert the enum to a 16-bit integer so we can still fit in the same
  space as before.

1 files changed, 286 insertions, 0 deletions

diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
new file mode 100644
index 000000000..cf2fb2ecc
--- /dev/null
+++ b/apt-pkg/solver3.h
@@ -0,0 +1,286 @@
+/*
+ * solver3.h - The APT 3.0 solver
+ *
+ * Copyright (c) 2023 Julian Andres Klode
+ * Copyright (c) 2023 Canonical Ltd
+ *
+ * SPDX-License-Identifier: GPL-2.0+
+ */
+
+#include <vector>
+
+#include <apt-pkg/configuration.h>
+#include <apt-pkg/depcache.h>
+#include <apt-pkg/pkgcache.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
+{
+   enum class Decision : uint16_t;
+   enum class Hint : uint16_t;
+   struct Reason;
+   template <typename T>
+   struct State;
+   struct Work;
+
+   // \brief Type to record depth at. This may very well be a 16-bit
+   // unsigned integer, then change Solver::State::Decision to be a
+   // uint16_t class enum as well to get a more compact space.
+   using depth_type = unsigned int;
+
+   // Documentation
+   template <typename T>
+   using heap = std::vector<T>;
+
+   static_assert(sizeof(depth_type) >= sizeof(map_id_t));
+
+   // Cache is needed to construct Iterators from Version objects we see
+   pkgCache &cache;
+   // Policy is needed for determining candidate version.
+   pkgDepCache::Policy &policy;
+   // States for packages
+   std::vector<State<pkgCache::Package>> pkgStates{};
+   // States for versions
+   std::vector<State<pkgCache::Version>> verStates{};
+
+   // \brief Helper function for safe access to package state.
+   inline State<pkgCache::Package> &operator[](pkgCache::Package *P)
+   {
+      return pkgStates[P->ID];
+   }
+
+   // \brief Helper function for safe access to version state.
+   inline State<pkgCache::Version> &operator[](pkgCache::Version *V)
+   {
+      return verStates[V->ID];
+   }
+
+   // \brief Heap of the remaining work.
+   //
+   // We are using an std::vector with std::make_heap(), std::push_heap(),
+   // and std::pop_heap() rather than a priority_queue because we need to
+   // be able to iterate over the queued work and see if a choice would
+   // invalidate any work.
+   heap<Work> work{};
+   // \brief Whether RescoreWork() actually needs to rescore the work.
+   bool needsRescore{false};
+
+   // \brief Current decision level.
+   //
+   // Each time a decision needs to be made we can push the item under
+   // consideration to our backlog of choices made and then later we can
+   // restore it easily.
+   std::vector<Work> choices{};
+   // \brief Backlog of solved work.
+   //
+   // Solved work may become invalidated when backtracking, so store it
+   // here to revisit it later.
+   std::vector<Work> solved{};
+
+   /// Various configuration options
+   // \brief Debug level
+   int debug{_config->FindI("Debug::APT::Solver")};
+   // \brief If set, we try to keep automatically installed packages installed.
+   bool KeepAuto{not _config->FindB("APT::Get::AutomaticRemove")};
+   // \brief If set, removals are allowed.
+   bool AllowRemove{_config->FindB("APT::Solver::Remove", true)};
+   // \brief If set, installs are allowed.
+   bool AllowInstall{_config->FindB("APT::Solver::Install", true)};
+   // \brief If set, we use strict pinning.
+   bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)};
+
+   // \brief Enqueue dependencies shared by all versions of the package.
+   bool EnqueueCommonDependencies(pkgCache::PkgIterator Pkg);
+   // \brief Reject reverse dependencies. Must call std::make_heap() after.
+   bool RejectReverseDependencies(pkgCache::VerIterator Ver);
+   // \brief Enqueue a single or group
+   bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Reason reason);
+   // \brief Check if a version is allowed by policy.
+   bool IsAllowedVersion(pkgCache::Version *V);
+
+   // \brief Return the current depth (choices.size() with casting)
+   depth_type depth()
+   {
+      return static_cast<depth_type>(choices.size());
+   }
+
+   public:
+   // \brief Create a new decision level.
+   bool Pop();
+   // \brief Revert to the previous decision level.
+   void Push(Work work);
+   // \brief Add work to our work queue.
+   void AddWork(Work &&work);
+   // \brief Rescore the work after a reject or a pop
+   void RescoreWorkIfNeeded();
+
+   // \brief Basic solver initializer. This cannot fail.
+   Solver(pkgCache &Cache, pkgDepCache::Policy &Policy);
+
+   // \brief Mark the package for install. This is annoying as it incurs a decision
+   bool Install(pkgCache::PkgIterator Pkg, Reason reason);
+   // \brief Install a version.
+   bool Install(pkgCache::VerIterator Ver, Reason reason);
+   // \brief Do not install this package
+   bool Reject(pkgCache::PkgIterator Pkg, Reason reason);
+   // \brief Do not install this version.
+   bool Reject(pkgCache::VerIterator Ver, Reason reason);
+
+   // \brief Apply the selections from the dep cache to the solver
+   bool FromDepCache(pkgDepCache &depcache);
+   // \brief Apply the solver result to the depCache
+   bool ToDepCache(pkgDepCache &depcache);
+
+   // \brief Solve the dependencies
+   bool Solve();
+
+   // Print dependency chain
+   std::string WhyStr(Reason reason);
+};
+
+}; // namespace APT
+
+/**
+ * \brief Tagged union holding either a package, version, or nothing; representing the reason for installing something.
+ *
+ * We want to keep track of the reason why things are being installed such that
+ * we can have sensible debugging abilities.
+ *
+ * If the reason is empty, this means the package is automatically installed.
+ */
+struct APT::Solver::Reason
+{
+   uint32_t IsVersion : 1;
+   uint32_t MapPtr : 31;
+
+   Reason() : IsVersion(0), MapPtr(0) {}
+   explicit Reason(pkgCache::PkgIterator const &Pkg) : IsVersion(0), MapPtr(Pkg.MapPointer()) {}
+   explicit Reason(pkgCache::VerIterator const &Ver) : IsVersion(1), MapPtr(Ver.MapPointer()) {}
+
+   // \brief Return the package, if any, otherwise 0.
+   map_pointer<pkgCache::Package> Pkg() const
+   {
+      return IsVersion ? 0 : map_pointer<pkgCache::Package>{(uint32_t)MapPtr};
+   }
+   // \brief Return the version, if any, otherwise 0.
+   map_pointer<pkgCache::Version> Ver() const
+   {
+      return IsVersion ? map_pointer<pkgCache::Version>{(uint32_t)MapPtr} : 0;
+   }
+   // \brief Check if there is no reason.
+   bool empty() const
+   {
+      return IsVersion == 0 && MapPtr == 0;
+   }
+};
+
+/**
+ * \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 Reason for the work
+   Reason reason;
+   // \brief The depth at which the item has been added
+   depth_type depth;
+
+   // \brief Possible solutions to this task, ordered in order of preference.
+   std::vector<pkgCache::Version *> solutions{};
+
+   // This is a union because we only need to store the choice we made when adding
+   // to the choice vector, and we don't need the size of valid choices in there.
+   union
+   {
+      // The choice we took
+      pkgCache::Version *choice;
+      // Number of valid choices
+      size_t size;
+   };
+
+   // \brief Whether this is an optional work item, they will be processed last
+   bool optional;
+   // \brief Whether this is an ugprade
+   bool upgrade;
+   // \brief This item should be removed from the queue.
+   bool dirty;
+
+   bool operator<(APT::Solver::Work const &b) const;
+   // \brief Dump the work item to std::cerr
+   void Dump(pkgCache &cache);
+
+   inline Work(Reason reason, depth_type depth, bool optional = false, bool upgrade = false) : reason(reason), depth(depth), size(0), optional(optional), upgrade(upgrade), dirty(false) {}
+};
+
+// \brief This essentially describes the install state in RFC2119 terms.
+enum class APT::Solver::Decision : uint16_t
+{
+   // \brief We have not made a choice about the package yet
+   NONE,
+   // \brief We need to install this package
+   MUST,
+   // \brief We cannot install this package (need conflicts with it)
+   MUSTNOT,
+};
+
+// \brief Hints for the solver about the item.
+enum class APT::Solver::Hint : uint16_t
+{
+   // \brief We have not made a choice about the package yet
+   NONE,
+   // \brief This package was listed as a Recommends of a must package,
+   SHOULD,
+   // \brief This package was listed as a Suggests of a must-not package
+   MAY,
+};
+
+/**
+ * \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.
+ */
+template <typename T>
+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.
+   //
+   // Reasons < 0 are package ID, reasons > 0 are version IDs.
+   Reason reason{};
+
+   // \brief The depth at which the decision has been taken
+   depth_type depth{0};
+
+   // \brief This essentially describes the install state in RFC2119 terms.
+   Decision decision{Decision::NONE};
+
+   // \brief Any hint.
+   Hint hint{Hint::NONE};
+};