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.

3 files changed, 54 insertions, 8 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index e86353e43..dc70adbde 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -26,11 +26,12 @@
 #include <sstream>
 
 // FIXME: Helpers stolen from DepCache, please give them back.
-struct CompareProviders3 /*{{{*/
+struct APT::Solver::CompareProviders3 /*{{{*/
 {
    pkgCache &Cache;
    pkgDepCache::Policy &Policy;
    pkgCache::PkgIterator const Pkg;
+   APT::Solver &Solver;
    bool upgrade{_config->FindB("APT::Solver::Upgrade", false)};
 
    bool operator()(pkgCache::Version *AV, pkgCache::Version *BV)
@@ -60,6 +61,11 @@ struct CompareProviders3 /*{{{*/
 
 	 return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0;
       }
+      // Try obsolete choices only after exhausting non-obsolete choices such that we install
+      // packages replacing them and don't keep back upgrades depending on the replacement to
+      // keep the obsolete package installed.
+      if (auto obsoleteAV = Solver.Obsolete(AV), obsoleteBV = Solver.Obsolete(BV); obsoleteAV != obsoleteBV)
+	 return obsoleteBV;
       // Prefer MA:same packages if other architectures for it are installed
       if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same ||
 	  (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
@@ -158,8 +164,9 @@ class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc
 APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy)
     : cache(cache),
       policy(policy),
-      pkgStates{cache.Head().PackageCount},
-      verStates{cache.Head().VersionCount}
+      pkgStates(cache.Head().PackageCount),
+      verStates(cache.Head().VersionCount),
+      verObsolete(cache.Head().VersionCount)
 {
    static_assert(sizeof(APT::Solver::State<pkgCache::PkgIterator>) == 3 * sizeof(int));
    static_assert(sizeof(APT::Solver::State<pkgCache::VerIterator>) == 3 * sizeof(int));
@@ -239,6 +246,26 @@ std::string APT::Solver::WhyStr(Reason reason)
    return outstr;
 }
 
+bool APT::Solver::Obsolete(pkgCache::VerIterator ver)
+{
+   if (verObsolete[ver->ID] != 0)
+      return verObsolete[ver->ID] == 2;
+   for (auto bin = ver.Cache()->FindGrp(ver.SourcePkgName()).VersionsInSource(); not bin.end(); bin = bin.NextInSource())
+      if (bin != ver && bin.ParentPkg()->Arch == ver.ParentPkg()->Arch && bin->ParentPkg != ver->ParentPkg && policy.GetCandidateVer(bin.ParentPkg()) == bin && _system->VS->CmpVersion(bin.SourceVerStr(), ver.SourceVerStr()) > 0)
+      {
+	 verObsolete[ver->ID] = 2;
+	 return true;
+      }
+   for (auto file = ver.FileList(); !file.end(); file++)
+      if ((file.File()->Flags & pkgCache::Flag::NotSource) == 0)
+      {
+	 verObsolete[ver->ID] = 1;
+	 return false;
+      }
+   verObsolete[ver->ID] = 2;
+   return true;
+}
+
 bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason, Group group)
 {
    if ((*this)[Pkg].decision == Decision::MUST)
@@ -272,7 +299,7 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason, Group group)
    for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
       if (IsAllowedVersion(ver))
 	 workItem.solutions.push_back(ver);
-   std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg});
+   std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg, *this});
    assert(workItem.solutions.size() > 0);
 
    if (workItem.solutions.size() > 1 || workItem.optional)
@@ -490,7 +517,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera
       // FIXME: This is not really true, though, we should fix the CompareProviders to ignore the
       // installed state
       if (fixPolicy)
-	 std::stable_sort(workItem.solutions.begin() + begin, workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg});
+	 std::stable_sort(workItem.solutions.begin() + begin, workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this});
 
       if (start == end)
 	 break;
@@ -498,8 +525,14 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera
    } while (1);
 
    if (not fixPolicy)
-      std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg});
-
+      std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this});
+
+   if (std::all_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto V) -> auto
+		   { return pkgCache::VerIterator(cache, V).ParentPkg()->CurrentVer == 0; }))
+      workItem.group = Group::SatisfyNew;
+   if (std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto V) -> auto
+		   { return Obsolete(pkgCache::VerIterator(cache, V)); }))
+      workItem.group = Group::SatisfyObsolete;
    // Try to perserve satisfied Recommends. FIXME: We should check if the Recommends was there in the installed version?
    if (workItem.optional && start.ParentPkg()->CurrentVer)
    {
@@ -936,7 +969,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	    for (auto V = P.VersionList(); not V.end(); ++V)
 	       if (IsAllowedVersion(V))
 		  w.solutions.push_back(V);
-	    std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P});
+	    std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this});
 	    AddWork(std::move(w));
 	 }
       }
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(),
diff --git a/test/integration/test-resolver-provider-exchange b/test/integration/test-resolver-provider-exchange
index 45d936978..2874b88e4 100755
--- a/test/integration/test-resolver-provider-exchange
+++ b/test/integration/test-resolver-provider-exchange
@@ -8,6 +8,7 @@ allowremovemanual
 configarchitecture 'amd64'
 
 insertinstalledpackage 'fuse' 'all' '2'
+insertpackage 'unstable' 'fuse' 'all' '2'
 insertpackage 'unstable' 'fuse3' 'all' '3' 'Conflicts: fuse
 Provides: fuse'