don't install new deps of candidates for kept back pkgs

In effect this is an extension of the 6 years old commit
a8dfff90aa740889eb99d00fde5d70908d9fd88a which uses the autoremover to
remove packages again from the solution which are no longer needed to be
there. Commonly these are dependencies of packages we end up not
installed due to problem resolver decisions. Slightly less common is
the situation we deal with here: a package which we wanted to upgrade
sporting a new dependency, but ended up holding back.

The problem is that all versions of an installed reverse dependencies can
bring back a "garbage" package – we need to do this as there is
nothing inherently wrong in having garbage packages installed or upgrade
them, which itself would have garbage dependencies, so just blindly
killing all new garbage packages would prevent the upgrade (and actually
generate errors). What we should be doing is looking only at the version
we will have on the system, disregarding all old/new reverse dependencies.

Reported-By: Stuart Prescott (themill) on IRC
(cherry picked from commit 952171787a0b865c17d5c9476e272106383ae93a)
(cherry picked from commit 72ea04411b08bb9f25febdc4b4ca8d7b26206f2d)
(modified for 1.2.y by adjusting sections in test case)

4 files changed, 65 insertions, 103 deletions

diff --git a/apt-private/private-install.cc b/apt-private/private-install.cc
index a4917c5af..9716e6580 100644
--- a/apt-private/private-install.cc
+++ b/apt-private/private-install.cc
@@ -428,11 +428,11 @@ bool DoAutomaticRemove(CacheFile &Cache)
       {
 	 if(Pkg.CurrentVer() != 0 || Cache[Pkg].Install())
 	    if(Debug)
-	       std::cout << "We could delete %s" <<  Pkg.FullName(true).c_str() << std::endl;
+	       std::cout << "We could delete " <<  APT::PrettyPkg(Cache, Pkg) << std::endl;
 
 	 if (doAutoRemove)
 	 {
-	    if(Pkg.CurrentVer() != 0 && 
+	    if(Pkg.CurrentVer() != 0 &&
 	       Pkg->CurrentState != pkgCache::State::ConfigFiles)
 	       Cache->MarkDelete(Pkg, purgePkgs, 0, false);
 	    else
@@ -477,11 +477,25 @@ bool DoAutomaticRemove(CacheFile &Cache)
 		  if (R.IsNegative() == true ||
 		      Cache->IsImportantDep(R) == false)
 		     continue;
-		 pkgCache::PkgIterator N = R.ParentPkg();
-		 if (N.end() == true || (N->CurrentVer == 0 && (*Cache)[N].Install() == false))
+		 auto const RV = R.ParentVer();
+		 if (unlikely(RV.end() == true))
+		    continue;
+		 auto const RP = RV.ParentPkg();
+		 // check if that dependency comes from an interesting version
+		 if (RP.CurrentVer() == RV)
+		 {
+		    if ((*Cache)[RP].Keep() == false)
+		       continue;
+		 }
+		 else if (Cache[RP].CandidateVerIter(Cache) == RV)
+		 {
+		    if ((*Cache)[RP].NewInstall() == false && (*Cache)[RP].Upgrade() == false)
+		       continue;
+		 }
+		 else // ignore dependency from a non-candidate version
 		    continue;
 		 if (Debug == true)
-		    std::clog << "Save " << APT::PrettyPkg(Cache, Pkg) << " as another installed garbage package depends on it" << std::endl;
+		    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);
 		 if (hideAutoRemove == false)
 		    ++autoRemoveCount;
@@ -497,6 +511,8 @@ bool DoAutomaticRemove(CacheFile &Cache)
 	 }
       } while (Changed == true);
    }
+   // trigger marking now so that the package list below is correct
+   group.release();
 
    // Now see if we had destroyed anything (if we had done anything)
    if (Cache->BrokenCount() != 0)
diff --git a/test/integration/Packages-bug-604222-new-and-autoremove b/test/integration/Packages-bug-604222-new-and-autoremove
deleted file mode 100644
index fdff9d702..000000000
--- a/test/integration/Packages-bug-604222-new-and-autoremove
+++ /dev/null
@@ -1,68 +0,0 @@
-Package: dummy-archive
-Priority: extra
-Section: admin
-Installed-Size: 5984
-Maintainer: APT Development Team <deity@lists.debian.org>
-Architecture: i386
-Version: 0.invalid.0
-Source: dummy-archive
-Depends: libavcodec52, libvtk5-dev | libopenal-dev
-Filename: pool/main/d/dummy/dummy_5.4.2-8_i386.deb
-Size: 2280898
-MD5sum: 569719746f7ec4b96209a6152af20c00
-Description: some dummy package
-
-Package: libvtk5-dev
-Priority: optional
-Section: libdevel
-Installed-Size: 13812
-Maintainer: A. Maitland Bottoms <bottoms@debian.org>
-Architecture: i386
-Source: vtk
-Version: 5.4.2-8
-Depends: libvtk5.4 (= 5.4.2-8)
-Filename: pool/main/v/vtk/libvtk5-dev_5.4.2-8_i386.deb
-Size: 2280898
-MD5sum: 569719746f7ec4b96209a6152af20c00
-Description: VTK header files for building C++ code
-
-Package: libvtk5.4
-Priority: optional
-Section: libs
-Installed-Size: 39372
-Maintainer: A. Maitland Bottoms <bottoms@debian.org>
-Architecture: i386
-Source: vtk
-Version: 5.4.2-8
-Depends: libavcodec52 (>= 4:0.5.1-1)
-Filename: pool/main/v/vtk/libvtk5.4_5.4.2-8_i386.deb
-Size: 13070848
-MD5sum: 3ba7abc3d58ec44e35ae71879406563d
-Description: Visualization Toolkit - A high level 3D visualization library
-
-Package: libopenal-dev
-Priority: optional
-Section: libdevel
-Installed-Size: 140
-Maintainer: Debian Games Team <pkg-games-devel@lists.alioth.debian.org>
-Architecture: i386
-Source: openal-soft
-Version: 1:1.12.854-2
-Filename: pool/main/o/openal-soft/libopenal-dev_1.12.854-2_i386.deb
-Size: 21014
-MD5sum: e0bda4fbf5a3d38ef510a23a1642587f
-Description-de: Software-Implementierung der OpenAL-API (Entwicklungsdateien)
-
-Package: libavcodec52
-Priority: optional
-Section: libs
-Installed-Size: 10772
-Maintainer: Debian multimedia packages maintainers <pkg-multimedia-maintainers@lists.alioth.debian.org>
-Architecture: i386
-Source: ffmpeg
-Version: 4:0.5.2-6
-Conflicts: libvtk5-dev
-Filename: pool/main/f/ffmpeg/libavcodec52_0.5.2-6_i386.deb
-Size: 4001600
-MD5sum: a50aae4c8e8b9dd29612407e61bedc22
-Description-de: Ffmpeg-Codec-Bibliothek
diff --git a/test/integration/status-bug-604222-new-and-autoremove b/test/integration/status-bug-604222-new-and-autoremove
deleted file mode 100644
index 03cf4d307..000000000
--- a/test/integration/status-bug-604222-new-and-autoremove
+++ /dev/null
@@ -1,10 +0,0 @@
-Package: libvtk5.4
-Status: install ok installed
-Priority: optional
-Section: libs
-Installed-Size: 39372
-Maintainer: A. Maitland Bottoms <bottoms@debian.org>
-Architecture: i386
-Source: vtk
-Version: 5.4.2-7
-Description: Visualization Toolkit - A high level 3D visualization library
diff --git a/test/integration/test-bug-604222-new-and-autoremove b/test/integration/test-bug-604222-new-and-autoremove
index 48d79ea77..d7ff5cd0c 100755
--- a/test/integration/test-bug-604222-new-and-autoremove
+++ b/test/integration/test-bug-604222-new-and-autoremove
@@ -5,9 +5,22 @@ TESTDIR="$(readlink -f "$(dirname "$0")")"
 . "$TESTDIR/framework"
 setupenvironment
 configarchitecture "i386"
+
+insertpackage 'stable' 'dummy-archive' 'i386' '0.invalid.0' 'Depends: libavcodec52, libvtk5-dev | libopenal-dev'
+insertpackage 'stable' 'libavcodec52' 'i386' '4:0.5.2-6' 'Conflicts: libvtk5-dev'
+insertpackage 'stable' 'libopenal-dev' 'i386' '1:1.12.854-2'
+insertpackage 'stable' 'libvtk5-dev' 'i386' '5.4.2-8' 'Depends: libvtk5.4 (= 5.4.2-8)'
+insertpackage 'stable' 'libvtk5.4' 'i386' '5.4.2-8' 'Depends: libavcodec52 (>= 4:0.5.1-1)'
+
+insertpackage 'stable' 'gwenview' 'i386' '4:16.08.0-1' 'Depends: libkf5kipi-bin, libkf5kipi-data'
+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'
+
 setupaptarchive
 
-touch rootdir/var/lib/apt/extended_states
+cp -a rootdir/var/lib/dpkg/status rootdir/var/lib/dpkg/status.backup
+insertinstalledpackage 'libvtk5.4' 'i386' '5.4.2-7'
 testsuccess aptmark markauto 'libvtk5.4'
 testmarkedauto 'libvtk5.4'
 
@@ -25,8 +38,8 @@ 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.
-Inst libavcodec52 (4:0.5.2-6 localhost [i386])
-Conf libavcodec52 (4:0.5.2-6 localhost [i386])" aptget install libavcodec52 -s
+Inst libavcodec52 (4:0.5.2-6 stable [i386])
+Conf libavcodec52 (4:0.5.2-6 stable [i386])" aptget install libavcodec52 -s
 
 testsuccessequal "Reading package lists...
 Building dependency tree...
@@ -36,8 +49,8 @@ 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.
-Inst libavcodec52 (4:0.5.2-6 localhost [i386])
-Conf libavcodec52 (4:0.5.2-6 localhost [i386])" aptget install libavcodec52 -s -o APT::Get::HideAutoRemove=small
+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
 
 testfailureequal "Reading package lists...
 Building dependency tree...
@@ -52,8 +65,7 @@ The following NEW packages will be installed:
 The following packages will be upgraded:
   libvtk5.4
 1 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
-Need to get 0 B/19.4 MB of archives.
-After this operation, 17.3 MB of additional disk space will be used.
+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
 testequal "Reading package lists...
 Building dependency tree...
@@ -67,31 +79,43 @@ The following NEW packages will be installed:
 The following packages will be upgraded:
   libvtk5.4
 1 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
-Need to get 0 B/19.4 MB of archives.
-After this operation, 17.3 MB of additional disk space will be used.
+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
 
-echo -n > rootdir/var/lib/dpkg/status
-rm rootdir/var/lib/apt/extended_states
+cp rootdir/var/lib/dpkg/status.backup rootdir/var/lib/dpkg/status
+rm -f rootdir/var/lib/apt/extended_states
 
 CONFLICTING='Reading package lists...
 Building dependency tree...
-  MarkInstall dummy-archive [ i386 ] < none -> 0.invalid.0 > ( admin ) FU=1
-    MarkInstall libavcodec52 [ i386 ] < none -> 4:0.5.2-6 > ( libs ) FU=0
-    MarkInstall libvtk5-dev [ i386 ] < none -> 5.4.2-8 > ( libdevel ) FU=0
-      MarkInstall libvtk5.4 [ i386 ] < none -> 5.4.2-8 > ( libs ) FU=0
-  MarkKeep libvtk5-dev [ i386 ] < none -> 5.4.2-8 > ( libdevel ) FU=0
-  MarkKeep libvtk5-dev [ i386 ] < none -> 5.4.2-8 > ( libdevel ) FU=0
-  MarkDelete libvtk5.4 [ i386 ] < none -> 5.4.2-8 > ( libs ) FU=0
+  MarkInstall dummy-archive [ i386 ] < none -> 0.invalid.0 > ( other ) FU=1
+    MarkInstall libavcodec52 [ i386 ] < none -> 4:0.5.2-6 > ( other ) FU=0
+    MarkInstall libvtk5-dev [ i386 ] < none -> 5.4.2-8 > ( other ) FU=0
+      MarkInstall libvtk5.4 [ i386 ] < none -> 5.4.2-8 > ( other ) FU=0
+  MarkKeep libvtk5-dev [ i386 ] < none -> 5.4.2-8 > ( other ) FU=0
+  MarkKeep libvtk5-dev [ i386 ] < none -> 5.4.2-8 > ( other ) FU=0
+  MarkDelete libvtk5.4 [ i386 ] < none -> 5.4.2-8 > ( other ) FU=0
 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 0 not upgraded.
-Need to get 0 B/6304 kB of archives.
-After this operation, 17.3 MB of additional disk space will be used.
+After this operation, 129 kB of additional disk space will be used.
 E: Trivial Only specified but this is not a trivial operation.'
 
 testfailureequal "$CONFLICTING" aptget install dummy-archive --trivial-only -o Debug::pkgDepCache::Marker=1 -o APT::Get::HideAutoRemove=0
 testfailureequal "$CONFLICTING" aptget install dummy-archive --trivial-only -o Debug::pkgDepCache::Marker=1 -o APT::Get::HideAutoRemove=1
 testfailureequal "$CONFLICTING" aptget install dummy-archive --trivial-only -o Debug::pkgDepCache::Marker=1 -o APT::Get::HideAutoRemove=small
+
+insertinstalledpackage 'my-metapackage' 'i386' '1' 'Depends: gwenview'
+insertinstalledpackage 'gwenview' 'i386' '4:15.08.0-1' 'Depends: libkipi-data
+Recommends: foobar' # trigger policy brokenness to avoid optimisation
+insertinstalledpackage 'libkipi-data' 'i386' '4:15.08.0-1' '' 'important'
+testsuccess aptmark markauto 'gwenview'
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Reading state information...
+Calculating upgrade...
+The following packages have been kept back:
+  gwenview
+0 upgraded, 0 newly installed, 0 to remove and 1 not upgraded." apt dist-upgrade -s