Prefer upgrading installed orgroup members

In normal upgrade scenarios this is no problem as the orgroup member
will be marked for upgrade already, but on a not fully upgraded system
(or while you operate on a different target release) we would go with our
usual "first come first serve" approach which might lead us to install
another provider who comes earlier – bad if the providers conflict.

3 files changed, 75 insertions, 57 deletions

diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index 03fc58f69..2254a9b5d 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -27,6 +27,7 @@
 
 #include <algorithm>
 #include <iostream>
+#include <iterator>
 #include <list>
 #include <set>
 #include <string>
@@ -1018,52 +1019,52 @@ struct CompareProviders							/*{{{*/
 	    }
 	 }
 	 if (instA != instB)
-	    return instA == false;
+	    return instA;
       }
       if ((A->CurrentVer == 0 || B->CurrentVer == 0) && A->CurrentVer != B->CurrentVer)
-	 return A->CurrentVer == 0;
+	 return A->CurrentVer != 0;
       // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
       if (A->Group != B->Group)
       {
 	 if (A->Group == Pkg->Group && B->Group != Pkg->Group)
-	    return false;
-	 else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
 	    return true;
+	 else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
+	    return false;
       }
       // we like essentials
       if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
       {
 	 if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
-	    return false;
-	 else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 	    return true;
+	 else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+	    return false;
       }
       if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important))
       {
 	 if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
-	    return false;
-	 else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
 	    return true;
+	 else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
+	    return false;
       }
       // prefer native architecture
       if (strcmp(A.Arch(), B.Arch()) != 0)
       {
 	 if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
-	    return false;
-	 else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
 	    return true;
+	 else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
+	    return false;
 	 std::vector<std::string> archs = APT::Configuration::getArchitectures();
 	 for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
 	    if (*a == A.Arch())
-	       return false;
-	    else if (*a == B.Arch())
 	       return true;
+	    else if (*a == B.Arch())
+	       return false;
       }
       // higher priority seems like a good idea
       if (AV->Priority != BV->Priority)
-	 return AV->Priority > BV->Priority;
+	 return AV->Priority < BV->Priority;
       // unable to decide…
-      return A->ID < B->ID;
+      return A->ID > B->ID;
    }
 };
 									/*}}}*/
@@ -1257,52 +1258,49 @@ bool pkgDepCache::MarkInstall_InstallDependencies(PkgIterator const &Pkg, unsign
 	 }
       }
 
-      bool foundSolution = false;
-      bool thereIsOnlyOne1 = Start == End;
+      pkgCacheFile CacheFile{this};
+      APT::PackageVector toUpgrade, toNewInstall;
       do
       {
 	 if ((DepState[Start->ID] & DepCVer) != DepCVer)
 	    continue;
 
-	 pkgCacheFile CacheFile(this);
-	 APT::VersionList verlist = APT::VersionList::FromDependency(CacheFile, Start, APT::CacheSetHelper::CANDIDATE);
-	 CompareProviders comp(Start);
-	 bool thereIsOnlyOne2 = thereIsOnlyOne1 && verlist.size() == 1;
-
-	 do
+	 APT::VersionVector verlist = APT::VersionVector::FromDependency(CacheFile, Start, APT::CacheSetHelper::CANDIDATE);
+	 std::sort(verlist.begin(), verlist.end(), CompareProviders{Start});
+	 for (auto const &Ver : verlist)
 	 {
-	    APT::VersionList::iterator InstVer = std::max_element(verlist.begin(), verlist.end(), comp);
-	    if (InstVer == verlist.end())
-	       break;
+	    auto P = Ver.ParentPkg();
+	    if (P->CurrentVer != 0)
+	       toUpgrade.emplace_back(std::move(P));
+	    else
+	       toNewInstall.emplace_back(std::move(P));
+	 }
+      } while (Start++ != End);
 
-	    pkgCache::PkgIterator InstPkg = InstVer.ParentPkg();
-	    if (DebugAutoInstall)
-	       std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
-			 << " as " << Start.DepType() << " of " << Pkg.Name() << '\n';
-	    if (thereIsOnlyOne2 && PkgState[Pkg->ID].Protect() && IsCriticalDep)
-	    {
-	       if (not MarkInstall(InstPkg, false, Depth + 1, false, ForceImportantDeps))
-	       {
-		  verlist.erase(InstVer);
-		  continue;
-	       }
-	       MarkProtected(InstPkg);
-	    }
-	    if (not MarkInstall(InstPkg, true, Depth + 1, false, ForceImportantDeps))
-	    {
-	       verlist.erase(InstVer);
+      std::move(toNewInstall.begin(), toNewInstall.end(), std::back_inserter(toUpgrade));
+      bool foundSolution = false;
+      for (auto const &InstPkg : toUpgrade)
+      {
+	 if (PkgState[InstPkg->ID].CandidateVer == nullptr || PkgState[InstPkg->ID].CandidateVer == InstPkg.CurrentVer())
+	    continue;
+	 if (DebugAutoInstall)
+	    std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.FullName()
+		      << " as " << End.DepType() << " of " << Pkg.FullName() << '\n';
+	 if (IsCriticalDep && toUpgrade.size() == 1 && PkgState[Pkg->ID].Protect())
+	 {
+	    if (not MarkInstall(InstPkg, false, Depth + 1, false, ForceImportantDeps))
 	       continue;
-	    }
+	    MarkProtected(InstPkg);
+	 }
+	 if (not MarkInstall(InstPkg, true, Depth + 1, false, ForceImportantDeps))
+	    continue;
 
-	    if (toMoveAuto != nullptr && InstPkg->CurrentVer == 0)
-	       toMoveAuto->push_back(InstPkg);
+	 if (toMoveAuto != nullptr && InstPkg->CurrentVer == 0)
+	    toMoveAuto->push_back(InstPkg);
 
-	    foundSolution = true;
-	    break;
-	 } while (true);
-	 if (foundSolution)
-	    break;
-      } while (Start++ != End);
+	 foundSolution = true;
+	 break;
+      }
       if (not foundSolution && IsCriticalDep)
       {
 	 StateCache &State = PkgState[Pkg->ID];
diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests
index c2e62b834..230683a99 100755
--- a/test/integration/test-bug-618848-always-respect-user-requests
+++ b/test/integration/test-bug-618848-always-respect-user-requests
@@ -18,7 +18,6 @@ Building dependency tree...
   MarkDelete libdb4.8:i386 < 1.0 @ii pmK > FU=1
   MarkDelete exim4-daemon-light:i386 < 1.0 @ii mK Ib > FU=0
     MarkInstall exim4-daemon-heavy:i386 < none -> 1.0 @un uN Ib > FU=0
-      Ignore MarkInstall of libdb4.8:i386 < 1.0 @ii pmR > as its mode (Delete) is protected
   MarkDelete exim4:i386 < 1.0 @ii mK Ib > FU=0
 The following packages will be REMOVED:
   exim4 exim4-daemon-light libdb4.8
diff --git a/test/integration/test-explore-or-groups-in-markinstall b/test/integration/test-explore-or-groups-in-markinstall
index db97574bb..259155854 100755
--- a/test/integration/test-explore-or-groups-in-markinstall
+++ b/test/integration/test-explore-or-groups-in-markinstall
@@ -7,16 +7,28 @@ setupenvironment
 configarchitecture 'amd64'
 
 insertpackage 'unstable' 'okay' 'all' '1'
+insertpackage 'unstable' 'upgrade' 'all' '2'
 insertpackage 'unstable' 'unneeded' 'all' '1'
 insertpackage 'unstable' 'later' 'all' '1'
 
 insertpackage 'unstable' 'bad-level0' 'all' '1' 'Depends: unneeded, unknown'
 insertpackage 'unstable' 'bad-level1' 'all' '1' 'Depends: bad-level0'
+insertpackage 'unstable' 'bad-upgrade-level0' 'all' '2' 'Depends: unneeded, unknown'
+insertpackage 'unstable' 'bad-upgrade-level1' 'all' '2' 'Depends: bad-upgrade-level0 (>= 2)'
+
+insertinstalledpackage 'upgrade' 'all' '1'
+insertinstalledpackage 'bad-upgrade' 'all' '1'
+insertinstalledpackage 'bad-upgrade-level0' 'all' '1'
+insertinstalledpackage 'bad-upgrade-level1' 'all' '1'
 
 insertfoos() {
-	insertpackage 'unstable' "foo-${1}-level0" 'all' '1' "${2}: unknown | okay | later"
-	insertpackage 'unstable' "foo-${1}-level1" 'all' '1' "${2}: bad-level0 | okay | later"
-	insertpackage 'unstable' "foo-${1}-level2" 'all' '1' "${2}: bad-level1 | okay | later"
+	insertpackage 'unstable' "foo-${1}-level0" 'all' '1' "${2}: unknown | unknown | okay | later"
+	insertpackage 'unstable' "foo-${1}-level1" 'all' '1' "${2}: bad-level0 | bad-level0 | okay | later"
+	insertpackage 'unstable' "foo-${1}-level2" 'all' '1' "${2}: bad-level1 | bad-level1 | okay | later"
+
+	insertpackage 'unstable' "foo-${1}-upgrade-level0" 'all' '1' "${2}: bad-upgrade (>= 2) | okay | upgrade (>= 2) | later"
+	insertpackage 'unstable' "foo-${1}-upgrade-level1" 'all' '1' "${2}: bad-upgrade-level0 (>= 2) | bad-upgrade-level0 (>= 2) | bad-level0 | okay | upgrade (>= 2) | later"
+	insertpackage 'unstable' "foo-${1}-upgrade-level2" 'all' '1' "${2}: bad-upgrade-level1 (>= 2) | bad-upgrade-level1 (>= 2) | bad-level1 | okay | upgrade (>= 2) | later"
 }
 insertfoos 'd' 'Depends'
 insertfoos 'r' 'Recommends'
@@ -35,14 +47,23 @@ testsuccessheadequal() {
 }
 checkfoos() {
 	msgmsg 'Install checks with foos dependency type' "$2"
-	for i in 0 1 2; do
+	for level in 0 1 2; do
 		testsuccessheadequal 7 "Reading package lists...
 Building dependency tree...
 The following additional packages will be installed:
   okay
 The following NEW packages will be installed:
-  foo-${1}-level${i} okay
-0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded." apt install foo-${1}-level${i} -s
+  foo-${1}-level${level} okay
+0 upgraded, 2 newly installed, 0 to remove and 3 not upgraded." apt install foo-${1}-level${level} -s
+		testsuccessheadequal 9 "Reading package lists...
+Building dependency tree...
+The following additional packages will be installed:
+  upgrade
+The following NEW packages will be installed:
+  foo-${1}-upgrade-level${level}
+The following packages will be upgraded:
+  upgrade
+1 upgraded, 1 newly installed, 0 to remove and $((2-${level})) not upgraded." apt install foo-${1}-upgrade-level${level} -s
 	done
 }
 checkfoos 'd' 'Depends'