Match version constraints before saving garbage packages

We remove new garbage packages from the solution if we can as installing
a new package which is at the same time considered garbage looks silly,
but it could also be a new dependency of another garbage package, so we
have a second round trying to save such packages. In this round we
weren't considering versioned constraints on dependency relations through
so even an unsatisfied old recommends could save which it shouldn't.

2 files changed, 31 insertions, 10 deletions

diff --git a/apt-private/private-install.cc b/apt-private/private-install.cc
index 8d1bc74f0..4f71f18c4 100644
--- a/apt-private/private-install.cc
+++ b/apt-private/private-install.cc
@@ -20,6 +20,7 @@
 #include <apt-pkg/prettyprinters.h>
 #include <apt-pkg/strutl.h>
 #include <apt-pkg/upgrade.h>
+#include <apt-pkg/version.h>
 
 #include <algorithm>
 #include <cstdlib>
@@ -620,12 +621,14 @@ bool DoAutomaticRemove(CacheFile &Cache)
 	 for (APT::PackageSet::iterator Pkg = tooMuch.begin();
 	      Pkg != tooMuch.end(); ++Pkg)
 	 {
-	    APT::PackageSet too;
-	    too.insert(*Pkg);
-	    for (pkgCache::PrvIterator Prv = Cache[Pkg].CandidateVerIter(Cache).ProvidesList();
-		 Prv.end() == false; ++Prv)
-	       too.insert(Prv.ParentPkg());
-	    for (APT::PackageSet::const_iterator P = too.begin(); P != too.end(); ++P)
+	    auto const PkgCand = Cache[Pkg].CandidateVerIter(Cache);
+	    if (unlikely(PkgCand.end()))
+	       continue;
+	    std::vector<std::pair<pkgCache::PkgIterator, char const *>> too;
+	    too.emplace_back(*Pkg, PkgCand.VerStr());
+	    for (pkgCache::PrvIterator Prv = PkgCand.ProvidesList(); not Prv.end(); ++Prv)
+	       too.emplace_back(Prv.ParentPkg(), Prv.ProvideVersion());
+	    for (auto const &[P, PVerStr] : too)
 	    {
 	       for (pkgCache::DepIterator R = P.RevDependsList();
 		    R.end() == false; ++R)
@@ -650,6 +653,11 @@ bool DoAutomaticRemove(CacheFile &Cache)
 		 }
 		 else // ignore dependency from a non-candidate version
 		    continue;
+		 if (R->Version != 0)
+		 {
+		    if (not Cache->VS().CheckDep(PVerStr, R->CompareOp, R.TargetVer()))
+		       continue;
+		 }
 		 if (Debug == true)
 		    std::clog << "Save " << APT::PrettyPkg(Cache, Pkg) << " as another installed package depends on it: " << APT::PrettyPkg(Cache, RP) << std::endl;
 		 Cache->MarkInstall(Pkg, false, 0, false);
diff --git a/test/integration/test-bug-604222-new-and-autoremove b/test/integration/test-bug-604222-new-and-autoremove
index 47da810c6..adb2c26d3 100755
--- a/test/integration/test-bug-604222-new-and-autoremove
+++ b/test/integration/test-bug-604222-new-and-autoremove
@@ -17,8 +17,21 @@ insertpackage 'stable' 'libkf5kipi-bin' 'i386' '4:16.08.0-1'
 insertpackage 'stable' 'libkf5kipi-data' 'i386' '4:16.08.0-1' 'Breaks: libkipi-data'
 insertpackage 'stable' 'libkipi-data' 'i386' '4:15.08.0-1' '' 'important'
 
+insertpackage 'stable' 'libgphoto2-l10n' 'all' '2'
+insertpackage 'installed,stable' 'photoapp1' 'all' '1' 'Recommends: libgphoto2-l10n (= 1)'
+insertinstalledpackage 'photoapp2' 'all' '1'
+insertpackage 'stable' 'photoapp2' 'all' '2' 'Conflicts: photoapp1
+Recommends: libgphoto2-l10n (= 2)'
+
 setupaptarchive
 
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following packages have been kept back:
+  photoapp2
+0 upgraded, 0 newly installed, 0 to remove and 1 not upgraded.' apt upgrade -s
+
 insertinstalledpackage 'libvtk5.4' 'i386' '5.4.2-7'
 testsuccess aptmark markauto 'libvtk5.4'
 testmarkedauto 'libvtk5.4'
@@ -36,7 +49,7 @@ The following package was automatically installed and is no longer required:
 Use '$AUTOREMOVE' to remove it.
 The following NEW packages will be installed:
   libavcodec52
-0 upgraded, 1 newly installed, 0 to remove and 1 not upgraded.
+0 upgraded, 1 newly installed, 0 to remove and 2 not upgraded.
 Inst libavcodec52 (4:0.5.2-6 stable [i386])
 Conf libavcodec52 (4:0.5.2-6 stable [i386])" aptget install libavcodec52 -s
 
@@ -47,7 +60,7 @@ Reading state information...
 Use '$AUTOREMOVE' to remove it.
 The following NEW packages will be installed:
   libavcodec52
-0 upgraded, 1 newly installed, 0 to remove and 1 not upgraded.
+0 upgraded, 1 newly installed, 0 to remove and 2 not upgraded.
 Inst libavcodec52 (4:0.5.2-6 stable [i386])
 Conf libavcodec52 (4:0.5.2-6 stable [i386])" aptget install libavcodec52 -s -o APT::Get::HideAutoRemove=small
 
@@ -61,7 +74,7 @@ The following additional packages will be installed:
   libavcodec52 libopenal-dev
 The following NEW packages will be installed:
   dummy-archive libavcodec52 libopenal-dev
-0 upgraded, 3 newly installed, 0 to remove and 1 not upgraded.
+0 upgraded, 3 newly installed, 0 to remove and 2 not upgraded.
 Need to get 0 B/126 B of archives.
 After this operation, 129 kB of additional disk space will be used.
 E: Trivial Only specified but this is not a trivial operation." aptget install dummy-archive --trivial-only
@@ -74,7 +87,7 @@ The following additional packages will be installed:
   libavcodec52 libopenal-dev
 The following NEW packages will be installed:
   dummy-archive libavcodec52 libopenal-dev
-0 upgraded, 3 newly installed, 0 to remove and 1 not upgraded.
+0 upgraded, 3 newly installed, 0 to remove and 2 not upgraded.
 Need to get 0 B/126 B of archives.
 After this operation, 129 kB of additional disk space will be used.
 E: Trivial Only specified but this is not a trivial operation." aptget install dummy-archive --trivial-only -o APT::Get::HideAutoRemove=small