solver3: Order obsolete choices last

This has two aspects:

1. For a dependency A | B | C we order the obsolete packages last,
   that is, if A is obsolete, this gets reordered to B | C | A,
   such that we try to pick non-obsolete packages first to ease
   upgrade calculation.

2. When comparing two dependencies, we order dependencies into three
   groups: First we satisfy dependencies mentioning only non-installed
   (NEW) packages, then we satisfy "normal" dependencies, and finally
   we satisfy any dependencies mentioning obsolete packages.

   This means for example if you have obsolete libfoo1 and a new
   libfoo1t64, that we will see Depends: libfoo1t64 before any
   Depends: libfoo1 (which may expand to libfoo1 | libfoo1t64),
   so we effectively will have selected "replacement" packages
   this way already before getting to older packages where we
   would have to choose between the obsolete package and its
   replacement.

1 files changed, 12 insertions, 0 deletions

diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index c3f191b18..9a9d67a02 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -32,6 +32,7 @@ class Solver
    enum class Decision : uint16_t;
    enum class Hint : uint16_t;
    struct Reason;
+   struct CompareProviders3;
    template <typename T>
    struct State;
    struct Work;
@@ -44,7 +45,15 @@ class Solver
    {
       HoldOrDelete,
       NewUnsatRecommends,
+
+      // Satisfying dependencies on entirely new packages first is a good idea because
+      // it may contain replacement packages like libfoo1t64 whereas we later will see
+      // Depends: libfoo1 where libfoo1t64 Provides libfoo1 and we'd have to choose.
+      SatisfyNew,
       Satisfy,
+      // On a similar note as for SatisfyNew, if the dependency contains obsolete packages
+      // try it last.
+      SatisfyObsolete,
 
       // My intuition tells me that we should try to schedule upgrades first, then
       // any non-obsolete installed packages, and only finally obsolete ones, such
@@ -95,6 +104,9 @@ class Solver
       return verStates[V->ID];
    }
 
+   std::vector<char> verObsolete;
+   bool Obsolete(pkgCache::VerIterator ver);
+
    // \brief Heap of the remaining work.
    //
    // We are using an std::vector with std::make_heap(), std::push_heap(),