Merge branch 'pu/autoremove' into 'main'

Mark only provides from protected versioned kernel packages

See merge request apt-team/apt!168

14 files changed, 288 insertions, 94 deletions

diff --git a/apt-pkg/cachefile.cc b/apt-pkg/cachefile.cc
index 5355994d3..4c3cc9586 100644
--- a/apt-pkg/cachefile.cc
+++ b/apt-pkg/cachefile.cc
@@ -42,6 +42,7 @@
 struct pkgCacheFile::Private
 {
    bool WithLock = false;
+   bool InhibitActionGroups = false;
 };
 
 // CacheFile::CacheFile - Constructor					/*{{{*/
@@ -199,6 +200,8 @@ bool pkgCacheFile::BuildDepCache(OpProgress *Progress)
    DCache.reset(new pkgDepCache(Cache,Policy));
    if (_error->PendingError() == true)
       return false;
+   if (d->InhibitActionGroups)
+      DCache->IncreaseActionGroupLevel();
    if (DCache->Init(Progress) == false)
       return false;
 
@@ -376,3 +379,7 @@ void pkgCacheFile::Close()
    SrcList = NULL;
 }
 									/*}}}*/
+void pkgCacheFile::InhibitActionGroups(bool const yes)
+{
+   d->InhibitActionGroups = yes;
+}
diff --git a/apt-pkg/cachefile.h b/apt-pkg/cachefile.h
index b24908216..4e26e6dab 100644
--- a/apt-pkg/cachefile.h
+++ b/apt-pkg/cachefile.h
@@ -69,6 +69,8 @@ class APT_PUBLIC pkgCacheFile
    void Close();
 
    bool AddIndexFile(pkgIndexFile * const File);
+   // Starts DepCache with a claim of one ActionGroup already active
+   void InhibitActionGroups(bool yes);
 
    inline pkgCache* GetPkgCache() { BuildCaches(NULL, false); return Cache; };
    inline pkgDepCache* GetDepCache() { BuildDepCache(); return DCache; };
diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index d025942af..2c3c6d01d 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -12,6 +12,7 @@
 #include <apt-pkg/algorithms.h>
 #include <apt-pkg/aptconfiguration.h>
 #include <apt-pkg/cachefile.h>
+#include <apt-pkg/cachefilter.h>
 #include <apt-pkg/cacheset.h>
 #include <apt-pkg/configuration.h>
 #include <apt-pkg/depcache.h>
@@ -28,10 +29,13 @@
 
 #include <algorithm>
 #include <iostream>
+#include <memory>
+#include <sstream>
 #include <iterator>
 #include <list>
 #include <set>
 #include <string>
+#include <unordered_map>
 #include <utility>
 #include <vector>
 #include <stdio.h>
@@ -84,31 +88,35 @@ ConfigValueInSubTree(const char* SubTree, const char *needle)
 pkgDepCache::ActionGroup::ActionGroup(pkgDepCache &cache) :		/*{{{*/
   d(NULL), cache(cache), released(false)
 {
-  ++cache.group_level;
+  cache.IncreaseActionGroupLevel();
 }
 
 void pkgDepCache::ActionGroup::release()
 {
-  if(!released)
-    {
-      if(cache.group_level == 0)
-	std::cerr << "W: Unbalanced action groups, expect badness" << std::endl;
-      else
-	{
-	  --cache.group_level;
-
-	  if(cache.group_level == 0)
-	    cache.MarkAndSweep();
-	}
-
-      released = true;
-    }
+  if(released)
+     return;
+  released = true;
+  if (cache.DecreaseActionGroupLevel() == 0)
+     cache.MarkAndSweep();
 }
 
 pkgDepCache::ActionGroup::~ActionGroup()
 {
   release();
 }
+int pkgDepCache::IncreaseActionGroupLevel()
+{
+   return ++group_level;
+}
+int pkgDepCache::DecreaseActionGroupLevel()
+{
+   if(group_level == 0)
+   {
+      std::cerr << "W: Unbalanced action groups, expect badness\n";
+      return -1;
+   }
+   return --group_level;
+}
 									/*}}}*/
 // DepCache::pkgDepCache - Constructors					/*{{{*/
 // ---------------------------------------------------------------------
@@ -117,6 +125,8 @@ pkgDepCache::ActionGroup::~ActionGroup()
 struct pkgDepCache::Private
 {
    std::unique_ptr<InRootSetFunc> inRootSetFunc;
+   std::vector<bool> fullyExplored;
+   std::unique_ptr<APT::CacheFilter::Matcher> IsAVersionedKernelPackage, IsProtectedKernelPackage;
 };
 pkgDepCache::pkgDepCache(pkgCache *const pCache, Policy *const Plcy) : group_level(0), Cache(pCache), PkgState(0), DepState(0),
 								       iUsrSize(0), iDownloadSize(0), iInstCount(0), iDelCount(0), iKeepCount(0),
@@ -2230,6 +2240,7 @@ bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
       PkgState[i].Marked  = false;
       PkgState[i].Garbage = false;
    }
+   d->fullyExplored = std::vector<bool>(PackagesCount, false);
    if (debug_autoremove)
       for(PkgIterator p = PkgBegin(); !p.end(); ++p)
 	 if(PkgState[p->ID].Flags & Flag::Auto)
@@ -2268,7 +2279,7 @@ bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
 	 MarkPackage(P, P.CurrentVer(),
 	       follow_recommends, follow_suggests, reason);
    }
-
+   d->fullyExplored.clear();
    return true;
 }
 									/*}}}*/
@@ -2279,26 +2290,32 @@ void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &Pkg,
 			      bool const &follow_suggests,
 			      const char *reason)
 {
-   {
-      pkgDepCache::StateCache &state = PkgState[Pkg->ID];
-      // if we are marked already we are done
-      if(state.Marked || unlikely(Ver.end()))
-	 return;
-      state.Marked=true;
-   }
+   if (Ver.end() || (d->fullyExplored[Pkg->ID] && PkgState[Pkg->ID].Marked))
+      return;
 
    if (IsPkgInBoringState(Pkg, PkgState))
+   {
+      d->fullyExplored[Pkg->ID] = true;
       return;
+   }
 
+   PkgState[Pkg->ID].Marked = true;
    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
    if(debug_autoremove)
       std::clog << "Marking: " << Pkg.FullName() << " " << Ver.VerStr()
 		<< " (" << reason << ")" << std::endl;
 
-   for (auto D = Ver.DependsList(); D.end() == false; ++D)
+   auto const sort_by_source_version = [](pkgCache::VerIterator const &A, pkgCache::VerIterator const &B) {
+      auto const verret = A.Cache()->VS->CmpVersion(A.SourceVerStr(), B.SourceVerStr());
+      if (verret != 0)
+	 return verret > 0;
+      return A->ID < B->ID;
+   };
+
+   for (auto D = Ver.DependsList(); not D.end(); ++D)
    {
       auto const T = D.TargetPkg();
-      if (PkgState[T->ID].Marked)
+      if (T.end() || d->fullyExplored[T->ID])
 	 continue;
 
       if (D->Type != Dep::Depends &&
@@ -2307,65 +2324,88 @@ void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &Pkg,
 	    (follow_suggests == false || D->Type != Dep::Suggests))
 	 continue;
 
-      // handle the virtual part first
-      APT::VersionVector providers;
-      for(auto Prv = T.ProvidesList(); Prv.end() == false; ++Prv)
+      bool unsatisfied_choice = false;
+      std::unordered_map<std::string, APT::VersionVector> providers_by_source;
+      // collect real part
+      if (not IsPkgInBoringState(T, PkgState))
       {
-	 auto PP = Prv.OwnerPkg();
+	 auto const TV = (PkgState[T->ID].Install()) ? PkgState[T->ID].InstVerIter(*this) : T.CurrentVer();
+	 if (likely(not TV.end()))
+	 {
+	    if (not D.IsSatisfied(TV))
+	       unsatisfied_choice = true;
+	    else
+	       providers_by_source[TV.SourcePkgName()].push_back(TV);
+	 }
+      }
+      if (providers_by_source.empty() && not unsatisfied_choice)
+	 PkgState[T->ID].Marked = true;
+      // collect virtual part
+      for (auto Prv = T.ProvidesList(); not Prv.end(); ++Prv)
+      {
+	 auto const PP = Prv.OwnerPkg();
 	 if (IsPkgInBoringState(PP, PkgState))
 	    continue;
 
 	 // we want to ignore provides from uninteresting versions
 	 auto const PV = (PkgState[PP->ID].Install()) ?
 	    PkgState[PP->ID].InstVerIter(*this) : PP.CurrentVer();
-	 if (unlikely(PV.end()) || PV != Prv.OwnerVer() || D.IsSatisfied(Prv) == false)
+	 if (unlikely(PV.end()) || PV != Prv.OwnerVer())
 	    continue;
 
-	 providers.emplace_back(PV);
+	 if (not D.IsSatisfied(Prv))
+	    unsatisfied_choice = true;
+	 else
+	    providers_by_source[PV.SourcePkgName()].push_back(PV);
+      }
+      // only latest binary package of a source package is marked instead of all
+      for (auto &providers : providers_by_source)
+      {
+	 std::sort(providers.second.begin(), providers.second.end(), sort_by_source_version);
+	 auto const highestSrcVer = (*providers.second.begin()).SourceVerStr();
+	 auto notThisVer = std::find_if_not(providers.second.begin(), providers.second.end(), [&](auto const &V) { return strcmp(highestSrcVer, V.SourceVerStr()) == 0; });
+	 if (notThisVer != providers.second.end())
+	    providers.second.erase(notThisVer, providers.second.end());
+	 // if the provider is a versioned kernel package mark them only for protected kernels
+	 if (providers.second.size() == 1)
+	    continue;
+	 if (not d->IsAVersionedKernelPackage)
+	    d->IsAVersionedKernelPackage = [&]() -> std::unique_ptr<APT::CacheFilter::Matcher> {
+	       auto const patterns = _config->FindVector("APT::VersionedKernelPackages");
+	       if (patterns.empty())
+		  return std::make_unique<APT::CacheFilter::FalseMatcher>();
+	       std::ostringstream regex;
+	       regex << '^';
+	       std::copy(patterns.begin(), patterns.end() - 1, std::ostream_iterator<std::string>(regex, "-.*$|^"));
+	       regex << patterns.back() << "-.*$";
+	       return std::make_unique<APT::CacheFilter::PackageNameMatchesRegEx>(regex.str());
+	    }();
+	 if (not std::all_of(providers.second.begin(), providers.second.end(), [&](auto const &Prv) { return (*d->IsAVersionedKernelPackage)(Prv.ParentPkg()); }))
+	    continue;
+	 // … if there is at least one for protected kernels installed
+	 if (not d->IsProtectedKernelPackage)
+	    d->IsProtectedKernelPackage = APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(Cache);
+	 if (not std::any_of(providers.second.begin(), providers.second.end(), [&](auto const &Prv) { return (*d->IsProtectedKernelPackage)(Prv.ParentPkg()); }))
+	    continue;
+	 providers.second.erase(std::remove_if(providers.second.begin(), providers.second.end(),
+					       [&](auto const &Prv) { return not((*d->IsProtectedKernelPackage)(Prv.ParentPkg())); }),
+				providers.second.end());
       }
-      if (providers.empty() == false)
+
+      if (not unsatisfied_choice)
+	 d->fullyExplored[T->ID] = true;
+      for (auto const &providers : providers_by_source)
       {
-	 // sort providers by source version so that only the latest versioned
-	 // binary package of a source package is marked instead of all
-	 std::sort(providers.begin(), providers.end(),
-	    [](pkgCache::VerIterator const &A, pkgCache::VerIterator const &B) {
-	       auto const nameret = strcmp(A.SourcePkgName(), B.SourcePkgName());
-	       if (nameret != 0)
-	          return nameret < 0;
-	       auto const verret = A.Cache()->VS->CmpVersion(A.SourceVerStr(), B.SourceVerStr());
-	       if (verret != 0)
-	          return verret > 0;
-	       return strcmp(A.ParentPkg().Name(), B.ParentPkg().Name()) < 0;
-	 });
-	 auto const prvsize = providers.size();
-	 providers.erase(std::unique(providers.begin(), providers.end(),
-	    [](pkgCache::VerIterator const &A, pkgCache::VerIterator const &B) {
-	       return strcmp(A.SourcePkgName(), B.SourcePkgName()) == 0 &&
-	          strcmp(A.SourceVerStr(), B.SourceVerStr()) != 0;
-	    }), providers.end());
-	 for (auto && PV: providers)
+	 for (auto const &PV : providers.second)
 	 {
 	    auto const PP = PV.ParentPkg();
 	    if (debug_autoremove)
 	       std::clog << "Following dep: " << APT::PrettyDep(this, D)
-		  << ", provided by " << PP.FullName() << " " << PV.VerStr()
-		  << " (" << providers.size() << "/" << prvsize << ")"<< std::endl;
-	    MarkPackage(PP, PV, follow_recommends, follow_suggests, "Provider");
+			 << ", provided by " << PP.FullName() << " " << PV.VerStr()
+			 << " (" << providers_by_source.size() << "/" << providers.second.size() << ")\n";
+	    MarkPackage(PP, PV, follow_recommends, follow_suggests, "Dependency");
 	 }
       }
-
-      // now deal with the real part of the package
-      if (IsPkgInBoringState(T, PkgState))
-	 continue;
-
-      auto const TV = (PkgState[T->ID].Install()) ?
-	 PkgState[T->ID].InstVerIter(*this) : T.CurrentVer();
-      if (unlikely(TV.end()) || D.IsSatisfied(TV) == false)
-	 continue;
-
-      if (debug_autoremove)
-	 std::clog << "Following dep: " << APT::PrettyDep(this, D) << std::endl;
-      MarkPackage(T, TV, follow_recommends, follow_suggests, "Dependency");
    }
 }
 									/*}}}*/
diff --git a/apt-pkg/depcache.h b/apt-pkg/depcache.h
index 9a6019092..e0c5c4069 100644
--- a/apt-pkg/depcache.h
+++ b/apt-pkg/depcache.h
@@ -298,7 +298,10 @@ class APT_PUBLIC pkgDepCache : protected pkgCache::Namespace
    int group_level;
 
    friend class ActionGroup;
-     
+   public:
+   int IncreaseActionGroupLevel();
+   int DecreaseActionGroupLevel();
+
    protected:
 
    // State information
diff --git a/apt-private/private-install.cc b/apt-private/private-install.cc
index 0c26c4275..414a00b9f 100644
--- a/apt-private/private-install.cc
+++ b/apt-private/private-install.cc
@@ -80,6 +80,16 @@ bool CheckNothingBroken(CacheFile &Cache)				/*{{{*/
 // ---------------------------------------------------------------------
 /* This displays the informative messages describing what is going to 
    happen and then calls the download routines */
+class SimulateWithActionGroupInhibited : public pkgSimulate
+{
+public:
+      SimulateWithActionGroupInhibited(CacheFile &Cache) : pkgSimulate(Cache) { Sim.IncreaseActionGroupLevel(); }
+      SimulateWithActionGroupInhibited(SimulateWithActionGroupInhibited const &Cache) = delete;
+      SimulateWithActionGroupInhibited(SimulateWithActionGroupInhibited &&Cache) = delete;
+      SimulateWithActionGroupInhibited& operator=(SimulateWithActionGroupInhibited const &Cache) = delete;
+      SimulateWithActionGroupInhibited& operator=(SimulateWithActionGroupInhibited &&Cache) = delete;
+      ~SimulateWithActionGroupInhibited() = default;
+};
 static void RemoveDownloadNeedingItemsFromFetcher(pkgAcquire &Fetcher, bool &Transient)
 {
    for (pkgAcquire::ItemIterator I = Fetcher.ItemsBegin(); I < Fetcher.ItemsEnd();)
@@ -208,7 +218,7 @@ bool InstallPackages(CacheFile &Cache, bool ShwKept, bool Ask, bool Safety, std:
    // Run the simulator ..
    if (_config->FindB("APT::Get::Simulate") == true)
    {
-      pkgSimulate PM(Cache);
+      SimulateWithActionGroupInhibited PM(Cache);
 
       APT::Progress::PackageManager *progress = APT::Progress::PackageManagerProgressFactory();
       pkgPackageManager::OrderResult Res = PM.DoInstall(progress);
@@ -420,7 +430,6 @@ bool DoAutomaticRemove(CacheFile &Cache)
       kernelAutoremovalMatcher = APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(Cache, true);
    }
 
-   pkgDepCache::ActionGroup group(*Cache);
    if(Debug)
       std::cout << "DoAutomaticRemove()" << std::endl;
 
@@ -431,6 +440,7 @@ bool DoAutomaticRemove(CacheFile &Cache)
 		 "AutoRemover") << std::endl;
       return false;
    }
+   Cache->MarkAndSweep();
 
    bool purgePkgs = _config->FindB("APT::Get::Purge", false);
    bool smallList = (hideAutoRemove == false &&
@@ -529,8 +539,6 @@ 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)
@@ -550,6 +558,8 @@ bool DoAutomaticRemove(CacheFile &Cache)
    {
       if (smallList == false)
       {
+	 // trigger marking now so that the package list is correct
+	 Cache->MarkAndSweep();
 	 SortedPackageUniverse Universe(Cache);
 	 ShowList(c1out, P_("The following package was automatically installed and is no longer required:",
 	          "The following packages were automatically installed and are no longer required:",
@@ -664,9 +674,7 @@ bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg
   TryToInstall InstallAction(Cache, Fix.get(), BrokenFix);
   TryToRemove RemoveAction(Cache, Fix.get());
 
-   // new scope for the ActionGroup
    {
-      pkgDepCache::ActionGroup group(Cache);
       unsigned short const order[] = { MOD_REMOVE, MOD_INSTALL, 0 };
 
       for (unsigned short i = 0; order[i] != 0; ++i)
@@ -828,6 +836,7 @@ struct PkgIsExtraInstalled {
 bool DoInstall(CommandLine &CmdL)
 {
    CacheFile Cache;
+   Cache.InhibitActionGroups(true);
    auto VolatileCmdL = GetPseudoPackages(Cache.GetSourceList(), CmdL, AddVolatileBinaryFile, "");
 
    // then open the cache
diff --git a/apt-private/private-source.cc b/apt-private/private-source.cc
index 9b47ce31f..5d1db5a50 100644
--- a/apt-private/private-source.cc
+++ b/apt-private/private-source.cc
@@ -652,6 +652,7 @@ bool DoBuildDep(CommandLine &CmdL)
    std::string const pseudoArch = hostArch.empty() ? nativeArch : hostArch;
 
    CacheFile Cache;
+   Cache.InhibitActionGroups(true);
    auto VolatileCmdL = GetPseudoPackages(Cache.GetSourceList(), CmdL, AddVolatileSourceFile, pseudoArch);
    auto AreDoingSatisfy = strcasecmp(CmdL.FileList[0], "satisfy") == 0;
 
@@ -820,7 +821,6 @@ bool DoBuildDep(CommandLine &CmdL)
 
    APT::PackageVector removeAgain;
    {
-      pkgDepCache::ActionGroup group(Cache);
       TryToInstall InstallAction(Cache, &Fix, false);
       std::list<std::pair<pkgCache::VerIterator, std::string>> candSwitch;
       for (auto const &pkg: pseudoPkgs)
@@ -856,7 +856,6 @@ bool DoBuildDep(CommandLine &CmdL)
       return false;
 
    {
-      pkgDepCache::ActionGroup group(Cache);
       if (_config->FindB(AreDoingSatisfy ? "APT::Get::Satisfy-Automatic" : "APT::Get::Build-Dep-Automatic", false) == false)
       {
 	 for (auto const &pkg: removeAgain)
diff --git a/cmdline/apt-internal-solver.cc b/cmdline/apt-internal-solver.cc
index d22eb75b4..23af6dab7 100644
--- a/cmdline/apt-internal-solver.cc
+++ b/cmdline/apt-internal-solver.cc
@@ -146,6 +146,7 @@ int main(int argc,const char *argv[])					/*{{{*/
 	EDSP::WriteProgress(5, "Read scenario…", output);
 
 	pkgCacheFile CacheFile;
+	CacheFile.InhibitActionGroups(true);
 	if (CacheFile.Open(NULL, false) == false)
 		DIE("Failed to open CacheFile!");
 
@@ -202,6 +203,7 @@ int main(int argc,const char *argv[])					/*{{{*/
 
 	EDSP::WriteProgress(95, "Write solution…", output);
 
+	CacheFile->MarkAndSweep();
 	if (WriteSolution(CacheFile, output) == false)
 		DIE("Failed to output the solution!");
 
diff --git a/test/integration/test-apt-get-autoremove-kernel-module-providers b/test/integration/test-apt-get-autoremove-kernel-module-providers
new file mode 100755
index 000000000..76c003051
--- /dev/null
+++ b/test/integration/test-apt-get-autoremove-kernel-module-providers
@@ -0,0 +1,103 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertinstalledpackage 'old-kernel-modules-0.8' 'all' '1' 'Depends: linux-image-0.8
+Provides: old-module
+Source: kernel-module'
+insertinstalledpackage 'old-kernel-modules-0.9' 'all' '1' 'Depends: linux-image-0.9
+Provides: old-module
+Source: kernel-module'
+insertinstalledpackage 'kernel-modules-1.0' 'all' '1' 'Depends: linux-image-1.0
+Provides: module
+Source: kernel-module'
+insertinstalledpackage 'kernel-modules-1.1' 'all' '2' 'Depends: linux-image-1.1
+Provides: module
+Source: kernel-module'
+insertinstalledpackage 'kernel-modules-1.2' 'all' '2' 'Depends: linux-image-1.2
+Provides: module
+Source: kernel-module'
+insertinstalledpackage 'kernel-modules-2.0' 'all' '2' 'Depends: linux-image-2.0
+Provides: module
+Source: kernel-module'
+insertinstalledpackage 'kernel-modules-2.1' 'all' '2' 'Depends: linux-image-2.1
+Provides: module
+Source: kernel-module'
+insertinstalledpackage 'texteditor-gtk' 'all' '2' 'Provides: editor
+Source: texteditor'
+insertinstalledpackage 'texteditor-kde' 'all' '2' 'Provides: editor
+Source: texteditor'
+
+insertinstalledpackage 'linux-image-0.8' 'all' '0.8' 'Provides: linux-image
+Source: linux-image'
+insertinstalledpackage 'linux-image-0.9' 'all' '0.9' 'Provides: linux-image
+Source: linux-image'
+insertinstalledpackage 'linux-image-1.0' 'all' '1.0' 'Provides: linux-image
+Source: linux-image'
+insertinstalledpackage 'linux-image-1.1' 'all' '1.1' 'Provides: linux-image
+Source: linux-image'
+insertinstalledpackage 'linux-image-1.2' 'all' '1.2' 'Provides: linux-image
+Source: linux-image'
+insertinstalledpackage 'linux-image-2.0' 'all' '2.0' 'Provides: linux-image
+Source: linux-image'
+insertinstalledpackage 'linux-image-2.1' 'all' '2.1' 'Provides: linux-image
+Source: linux-image'
+insertinstalledpackage 'has-needs' 'all' '1' 'Depends: editor, module, linux-image'
+insertinstalledpackage 'old-needs' 'all' '1' 'Depends: old-module'
+
+testsuccess aptmark auto 'linux-image-*' 'old-kernel-modules-*' 'kernel-modules-*' 'texteditor-*'
+testsuccessequal 'kernel-modules-1.0
+kernel-modules-1.1
+kernel-modules-1.2
+kernel-modules-2.0
+kernel-modules-2.1
+linux-image-0.8
+linux-image-0.9
+linux-image-1.0
+linux-image-1.1
+linux-image-1.2
+linux-image-2.0
+linux-image-2.1
+old-kernel-modules-0.8
+old-kernel-modules-0.9
+texteditor-gtk
+texteditor-kde' aptmark showauto
+
+testsuccess aptget check -s
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Reading state information...
+The following packages will be REMOVED:
+  kernel-modules-1.0 kernel-modules-1.1 kernel-modules-1.2 linux-image-1.0
+  linux-image-1.1 linux-image-1.2
+0 upgraded, 0 newly installed, 6 to remove and 0 not upgraded.
+Remv kernel-modules-1.0 [1]
+Remv kernel-modules-1.1 [2]
+Remv kernel-modules-1.2 [2]
+Remv linux-image-1.0 [1.0]
+Remv linux-image-1.1 [1.1]
+Remv linux-image-1.2 [1.2]' apt autoremove -s
+
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Reading state information...
+The following packages will be REMOVED:
+  kernel-modules-1.0 kernel-modules-1.1 kernel-modules-1.2 linux-image-0.8
+  linux-image-0.9 linux-image-1.0 linux-image-1.1 linux-image-1.2
+  old-kernel-modules-0.8 old-kernel-modules-0.9 old-needs
+0 upgraded, 0 newly installed, 11 to remove and 0 not upgraded.
+Remv kernel-modules-1.0 [1]
+Remv kernel-modules-1.1 [2]
+Remv kernel-modules-1.2 [2]
+Remv old-needs [1]
+Remv old-kernel-modules-0.8 [1]
+Remv linux-image-0.8 [0.8]
+Remv old-kernel-modules-0.9 [1]
+Remv linux-image-0.9 [0.9]
+Remv linux-image-1.0 [1.0]
+Remv linux-image-1.1 [1.1]
+Remv linux-image-1.2 [1.2]' apt autoremove -s old-needs-
diff --git a/test/integration/test-apt-get-autoremove-real-virtual-provider b/test/integration/test-apt-get-autoremove-real-virtual-provider
new file mode 100755
index 000000000..4940ab5ff
--- /dev/null
+++ b/test/integration/test-apt-get-autoremove-real-virtual-provider
@@ -0,0 +1,32 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertinstalledpackage 'needs' 'all' '1'
+insertinstalledpackage 'needs-provider1' 'all' '1' 'Provides: needs (= 1)'
+insertinstalledpackage 'needs-provider2' 'all' '1' 'Provides: needs (= 2)'
+insertinstalledpackage 'needs-provider3' 'all' '1' 'Provides: needs (= 3)'
+insertinstalledpackage 'needs-provider4' 'all' '1' 'Provides: needs (= 4)'
+
+insertinstalledpackage 'foo' 'all' '1' 'Depends: needs (= 1), needs (= 2), needs (= 3)'
+
+testsuccess aptmark auto 'needs*'
+testsuccessequal 'needs
+needs-provider1
+needs-provider2
+needs-provider3
+needs-provider4' aptmark showauto
+
+testsuccess aptget check -s
+
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Reading state information...
+The following packages will be REMOVED:
+  needs-provider4
+0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
+Remv needs-provider4 [1]' aptget autoremove -s
diff --git a/test/integration/test-bug-604222-new-and-autoremove b/test/integration/test-bug-604222-new-and-autoremove
index aaeac09a8..534c50b80 100755
--- a/test/integration/test-bug-604222-new-and-autoremove
+++ b/test/integration/test-bug-604222-new-and-autoremove
@@ -88,8 +88,6 @@ Building dependency tree...
     MarkInstall libopenal-dev:i386 < none -> 1:1.12.854-2 @un puN > FU=0
   Ignore MarkGarbage of libopenal-dev:i386 < none -> 1:1.12.854-2 @un puN > as its mode (Install) is protected
   Ignore MarkGarbage of libavcodec52:i386 < none -> 4:0.5.2-6 @un puN > as its mode (Install) is protected
-  Ignore MarkGarbage of libopenal-dev:i386 < none -> 1:1.12.854-2 @un puN > as its mode (Install) is protected
-  Ignore MarkGarbage of libavcodec52:i386 < none -> 4:0.5.2-6 @un puN > as its mode (Install) is protected
 The following additional packages will be installed:
   libavcodec52 libopenal-dev
 The following NEW packages will be installed:
diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests
index 1e144f1ee..f77c384c2 100755
--- a/test/integration/test-bug-618848-always-respect-user-requests
+++ b/test/integration/test-bug-618848-always-respect-user-requests
@@ -15,11 +15,11 @@ setupaptarchive
 
 testsuccessequal "Reading package lists...
 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
+  MarkDelete libdb4.8:i386 < 1.0 @ii pK > FU=1
+  MarkDelete exim4-daemon-light:i386 < 1.0 @ii K Ib > FU=0
     MarkInstall exim4-daemon-heavy:i386 < none -> 1.0 @un uN Ib > FU=0
-      exim4-daemon-heavy:i386 Depends on libdb4.8:i386 < 1.0 @ii pmR > can't be satisfied! (dep)
-  MarkDelete exim4:i386 < 1.0 @ii mK Ib > FU=0
+      exim4-daemon-heavy:i386 Depends on libdb4.8:i386 < 1.0 @ii pR > can't be satisfied! (dep)
+  MarkDelete exim4:i386 < 1.0 @ii K Ib > FU=0
 The following packages will be REMOVED:
   exim4 exim4-daemon-light libdb4.8
   MarkDelete exim4:i386 < 1.0 @ii K > FU=1
diff --git a/test/integration/test-bug-960705-propagate-protected-to-satisfied-conflict b/test/integration/test-bug-960705-propagate-protected-to-satisfied-conflict
index ad1501b66..824851278 100755
--- a/test/integration/test-bug-960705-propagate-protected-to-satisfied-conflict
+++ b/test/integration/test-bug-960705-propagate-protected-to-satisfied-conflict
@@ -18,24 +18,24 @@ setupaptarchive
 testsuccessequal "Reading package lists...
 Building dependency tree...
    Removing: systemd-sysv:amd64 as upgrade is not an option for runit-init:amd64 (1)
-    MarkDelete systemd-sysv:amd64 < 1 @ii mK > FU=0
+    MarkDelete systemd-sysv:amd64 < 1 @ii K > FU=0
   MarkInstall runit-init:amd64 < none -> 1 @un puN > FU=1
 Starting pkgProblemResolver with broken count: 1
 Starting 2 pkgProblemResolver with broken count: 1
-Investigating (0) init:amd64 < 1 @ii mK Ib >
-Broken init:amd64 PreDepends on systemd-sysv:amd64 < 1 @ii pmR >
+Investigating (0) init:amd64 < 1 @ii K Ib >
+Broken init:amd64 PreDepends on systemd-sysv:amd64 < 1 @ii pR >
   Considering systemd-sysv:amd64 0 as a solution to init:amd64 5100
   Added systemd-sysv:amd64 to the remove list
 Broken init:amd64 PreDepends on sysvinit-core:amd64 < none @un pH >
   Considering sysvinit-core:amd64 0 as a solution to init:amd64 5100
-  Ignore MarkKeep of systemd-sysv:amd64 < 1 @ii pmR > as its mode (Delete) is protected
-Investigating (1) init:amd64 < 1 @ii mK Ib >
-Broken init:amd64 PreDepends on systemd-sysv:amd64 < 1 @ii pmR >
+  Ignore MarkKeep of systemd-sysv:amd64 < 1 @ii pR > as its mode (Delete) is protected
+Investigating (1) init:amd64 < 1 @ii K Ib >
+Broken init:amd64 PreDepends on systemd-sysv:amd64 < 1 @ii pR >
   Considering systemd-sysv:amd64 5100 as a solution to init:amd64 5100
 Broken init:amd64 PreDepends on sysvinit-core:amd64 < none @un pH >
   Considering sysvinit-core:amd64 0 as a solution to init:amd64 5100
   Or group remove for init:amd64
-  MarkDelete init:amd64 < 1 @ii mK Ib > FU=0
+  MarkDelete init:amd64 < 1 @ii K Ib > FU=0
 Done
 The following packages will be REMOVED:
   init systemd-sysv
diff --git a/test/integration/test-dpkg-i-apt-install-fix-broken b/test/integration/test-dpkg-i-apt-install-fix-broken
index 8d800ffb7..0b75b5fb1 100755
--- a/test/integration/test-dpkg-i-apt-install-fix-broken
+++ b/test/integration/test-dpkg-i-apt-install-fix-broken
@@ -14,7 +14,7 @@ setupaptarchive
 testfailure dpkg -i incoming/autopkgtest-*.deb
 testsuccessequal 'Reading package lists...
 Building dependency tree...
-Correcting dependencies...  MarkInstall autopkgtest-satdep:amd64 < 1 @iU mK Nb Ib > FU=0
+Correcting dependencies...  MarkInstall autopkgtest-satdep:amd64 < 1 @iU K Nb Ib > FU=0
     MarkInstall debhelper:amd64 < none -> 1 @un uN > FU=0
 Starting pkgProblemResolver with broken count: 0
 Starting 2 pkgProblemResolver with broken count: 0
diff --git a/test/integration/test-resolver-delays-remove-decisions b/test/integration/test-resolver-delays-remove-decisions
index d8dfd7c9a..8f0c7daa5 100755
--- a/test/integration/test-resolver-delays-remove-decisions
+++ b/test/integration/test-resolver-delays-remove-decisions
@@ -53,7 +53,7 @@ Building dependency tree...
     MarkInstall foo:amd64 < none -> 1 @un uN Ib > FU=0
     Installing foo-dep:amd64 as Depends of foo:amd64
       MarkInstall foo-dep:amd64 < none -> 1 @un uN > FU=0
-    MarkDelete stuff:amd64 < 1 @ii mK > FU=0
+    MarkDelete stuff:amd64 < 1 @ii K > FU=0
 Starting pkgProblemResolver with broken count: 0
 Starting 2 pkgProblemResolver with broken count: 0
 Done
@@ -79,16 +79,15 @@ Building dependency tree...
   MarkInstall foobar:amd64 < none -> 1 @un puN Ib > FU=1
   Installing foo:amd64 as Depends of foobar:amd64
      Removing: stuff:amd64 as upgrade is not an option for foo:amd64 (1)
-      MarkDelete stuff:amd64 < 1 @ii mK > FU=0
+      MarkDelete stuff:amd64 < 1 @ii K > FU=0
     MarkInstall foo:amd64 < none -> 1 @un puN Ib > FU=0
     Installing foo-dep:amd64 as Depends of foo:amd64
       MarkInstall foo-dep:amd64 < none -> 1 @un puN > FU=0
-        MarkInstall uninstallable:amd64 < 1 @ii pmK > FU=0
+        MarkInstall uninstallable:amd64 < 1 @ii pK > FU=0
 Starting pkgProblemResolver with broken count: 0
 Starting 2 pkgProblemResolver with broken count: 0
 Done
   Ignore MarkGarbage of foo:amd64 < none -> 1 @un puN > as its mode (Install) is protected
-  Ignore MarkGarbage of foo:amd64 < none -> 1 @un puN > as its mode (Install) is protected
 Package 'bar' is not installed, so not removed
 The following additional packages will be installed:
   foo foo-dep