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, 5 insertions, 0 deletions

diff --git a/doc/examples/configure-index b/doc/examples/configure-index
index 981fe6f93..c27a8f862 100644
--- a/doc/examples/configure-index
+++ b/doc/examples/configure-index
@@ -603,6 +603,7 @@ Debug
   SetupAPTPartialDirectory::AssumeGood "<BOOL>";
   Locking "<BOOL>";
   Phasing "<BOOL>";
+  APT::Solver "<INT">;
 };
 
 pkgCacheGen
@@ -720,6 +721,10 @@ apt::hashes::*::untrusted "<BOOL>";
 apt::list-cleanup "<BOOL>";
 apt::authentication::trustcdrom "<BOOL>";
 apt::solver::strict-pinning "<BOOL>";
+apt::solver::enqueue-common-dependencies "<BOOL>";
+apt::solver::upgrade "<BOOL>";
+apt::solver::remove "<BOOL>";
+apt::solver::install "<BOOL>";
 apt::keep-downloaded-packages "<BOOL>";
 apt::solver "<STRING>";
 apt::planner "<STRING>";