Introduce tolower_ascii_unsafe() and use it for hashing

[apt.git] / apt-pkg / depcache.cc

diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index e466cba2815ff15e6762d9edb2f73b1bea7b5ec7..3925d2e7ccc3b00c25d6af7c1e2a43ca871043e8 100644 (file)
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -12,8 +12,8 @@
 
 #include <apt-pkg/depcache.h>
 #include <apt-pkg/versionmatch.h>
 
 #include <apt-pkg/depcache.h>
 #include <apt-pkg/versionmatch.h>

+#include <apt-pkg/version.h>

 #include <apt-pkg/error.h>
 #include <apt-pkg/error.h>

-#include <apt-pkg/sptr.h>

 #include <apt-pkg/fileutl.h>
 #include <apt-pkg/strutl.h>
 #include <apt-pkg/configuration.h>
 #include <apt-pkg/fileutl.h>
 #include <apt-pkg/strutl.h>
 #include <apt-pkg/configuration.h>


@@ -23,6 +23,7 @@
 #include <apt-pkg/cacheset.h>
 #include <apt-pkg/pkgcache.h>
 #include <apt-pkg/cacheiterators.h>
 #include <apt-pkg/cacheset.h>
 #include <apt-pkg/pkgcache.h>
 #include <apt-pkg/cacheiterators.h>

+#include <apt-pkg/prettyprinters.h>

 #include <apt-pkg/cachefile.h>
 #include <apt-pkg/macros.h>
 
 #include <apt-pkg/cachefile.h>
 #include <apt-pkg/macros.h>
 


@@ -154,7 +155,7 @@ bool pkgDepCache::Init(OpProgress * const Prog)
       State.iFlags = 0;
 
       // Figure out the install version
       State.iFlags = 0;
 
       // Figure out the install version

-      State.CandidateVer = GetCandidateVer(I);
+      State.CandidateVer = LocalPolicy->GetCandidateVer(I);

       State.InstallVer = I.CurrentVer();
       State.Mode = ModeKeep;
 
       State.InstallVer = I.CurrentVer();
       State.Mode = ModeKeep;
 


@@ -273,23 +274,27 @@ bool pkgDepCache::writeStateFile(OpProgress * const /*prog*/, bool const Install
            continue;
         StateCache const &P = PkgState[pkg->ID];
         bool newAuto = (P.Flags & Flag::Auto);
            continue;
         StateCache const &P = PkgState[pkg->ID];
         bool newAuto = (P.Flags & Flag::Auto);

-        // skip not installed or now-removed ones if requested
+        // reset to default (=manual) not installed or now-removed ones if requested

         if (InstalledOnly && (
             (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
             (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
         if (InstalledOnly && (
             (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
             (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))

+           newAuto = false;
+        if (newAuto == false)

         {
            // The section is obsolete if it contains no other tag
         {
            // The section is obsolete if it contains no other tag

-           unsigned int const count = section.Count();
+           auto const count = section.Count();

            if (count < 2 ||
                (count == 2 && section.Exists("Auto-Installed")) ||
                (count == 3 && section.Exists("Auto-Installed") && section.Exists("Architecture")))
            if (count < 2 ||
                (count == 2 && section.Exists("Auto-Installed")) ||
                (count == 3 && section.Exists("Auto-Installed") && section.Exists("Architecture")))

+           {
+              if(debug_autoremove)
+                 std::clog << "Drop obsolete section with " << count << " fields for " << APT::PrettyPkg(this, pkg) << std::endl;

               continue;
               continue;

-           else
-              newAuto = false;
+           }

         }
         }

-        if(_config->FindB("Debug::pkgAutoRemove",false))
-           std::clog << "Update existing AutoInstall info: " 
-                     << pkg.FullName() << std::endl;
+
+        if(debug_autoremove)
+           std::clog << "Update existing AutoInstall to " << newAuto << " for " << APT::PrettyPkg(this, pkg) << std::endl;

 
         std::vector<pkgTagSection::Tag> rewrite;
         rewrite.push_back(pkgTagSection::Tag::Rewrite("Architecture", pkg.Arch()));
 
         std::vector<pkgTagSection::Tag> rewrite;
         rewrite.push_back(pkgTagSection::Tag::Rewrite("Architecture", pkg.Arch()));


@@ -306,7 +311,7 @@ bool pkgDepCache::writeStateFile(OpProgress * const /*prog*/, bool const Install
       if(P.Flags & Flag::Auto) {
         if (pkgs_seen.find(pkg.FullName()) != pkgs_seen.end()) {
            if(debug_autoremove)
       if(P.Flags & Flag::Auto) {
         if (pkgs_seen.find(pkg.FullName()) != pkgs_seen.end()) {
            if(debug_autoremove)

-              std::clog << "Skipping already written " << pkg.FullName() << std::endl;
+              std::clog << "Skipping already written " << APT::PrettyPkg(this, pkg) << std::endl;

            continue;
         }
         // skip not installed ones if requested
            continue;
         }
         // skip not installed ones if requested


@@ -314,19 +319,21 @@ bool pkgDepCache::writeStateFile(OpProgress * const /*prog*/, bool const Install
             (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
             (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
            continue;
             (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
             (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
            continue;

-        const char* const pkgarch = pkg.Arch();
-        if (strcmp(pkgarch, "all") == 0)
-           continue;

         if(debug_autoremove)
         if(debug_autoremove)

-           std::clog << "Writing new AutoInstall: " << pkg.FullName() << std::endl;
+           std::clog << "Writing new AutoInstall: " << APT::PrettyPkg(this, pkg) << std::endl;

         std::string stanza = "Package: ";
         stanza.append(pkg.Name())
         std::string stanza = "Package: ";
         stanza.append(pkg.Name())

-             .append("\nArchitecture: ").append(pkgarch)
+             .append("\nArchitecture: ").append(pkg.Arch())

              .append("\nAuto-Installed: 1\n\n");
         if (OutFile.Write(stanza.c_str(), stanza.length()) == false)
            return false;
       }
    }
              .append("\nAuto-Installed: 1\n\n");
         if (OutFile.Write(stanza.c_str(), stanza.length()) == false)
            return false;
       }
    }

+   if (StateFile.Failed())
+   {
+      OutFile.OpFail();
+      return false;
+   }

    if (OutFile.Close() == false)
       return false;
    chmod(state.c_str(), 0644);
    if (OutFile.Close() == false)
       return false;
    chmod(state.c_str(), 0644);


@@ -792,7 +799,7 @@ bool pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 #endif
 
    if (DebugMarker == true)
 #endif
 
    if (DebugMarker == true)

-      std::clog << OutputInDepth(Depth) << "MarkKeep " << Pkg << " FU=" << FromUser << std::endl;
+      std::clog << OutputInDepth(Depth) << "MarkKeep " << APT::PrettyPkg(this, Pkg) << " FU=" << FromUser << std::endl;

 
    RemoveSizes(Pkg);
    RemoveStates(Pkg);
 
    RemoveSizes(Pkg);
    RemoveStates(Pkg);


@@ -836,8 +843,43 @@ bool pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
 
    ActionGroup group(*this);
 
 
    ActionGroup group(*this);
 

+   if (FromUser == false)
+   {
+      VerIterator const PV = P.InstVerIter(*this);
+      if (PV.end() == false)
+      {
+        // removed metapackages mark their dependencies as manual to prevent in "desktop depends browser, texteditor"
+        // the removal of browser to suggest the removal of desktop and texteditor.
+        // We ignore the auto-bit here as we can't deal with metapackage cascardes otherwise.
+        // We do not check for or-groups here as we don't know which package takes care of
+        // providing the feature the user likes e.g.:  browser1 | browser2 | browser3
+        // Temporary removals are effected by this as well, which is bad, but unlikely in practice
+        bool const PinNeverMarkAutoSection = (PV->Section != 0 && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", PV.Section()));
+        if (PinNeverMarkAutoSection)
+        {
+           for (DepIterator D = PV.DependsList(); D.end() != true; ++D)
+           {
+              if (D.IsMultiArchImplicit() == true || D.IsNegative() == true || IsImportantDep(D) == false)
+                 continue;
+
+              pkgCacheFile CacheFile(this);
+              APT::VersionList verlist = APT::VersionList::FromDependency(CacheFile, D, APT::CacheSetHelper::INSTALLED);
+              for (auto const &V : verlist)
+              {
+                 PkgIterator const DP = V.ParentPkg();
+                 if(DebugAutoInstall == true)
+                    std::clog << OutputInDepth(Depth) << "Setting " << DP.FullName(false) << " NOT as auto-installed (direct "
+                       << D.DepType() << " of " << Pkg.FullName(false) << " which is in APT::Never-MarkAuto-Sections)" << std::endl;
+
+                 MarkAuto(DP, false);
+              }
+           }
+        }
+      }
+   }
+

    if (DebugMarker == true)
    if (DebugMarker == true)

-      std::clog << OutputInDepth(Depth) << (rPurge ? "MarkPurge " : "MarkDelete ") << Pkg << " FU=" << FromUser << std::endl;
+      std::clog << OutputInDepth(Depth) << (rPurge ? "MarkPurge " : "MarkDelete ") << APT::PrettyPkg(this, Pkg) << " FU=" << FromUser << std::endl;

 
    RemoveSizes(Pkg);
    RemoveStates(Pkg);
 
    RemoveSizes(Pkg);
    RemoveStates(Pkg);


@@ -873,7 +915,7 @@ bool pkgDepCache::IsDeleteOkProtectInstallRequests(PkgIterator const &Pkg,
       if (P.InstallVer != 0 && P.Status == 2 && (P.Flags & Flag::Auto) != Flag::Auto)
       {
         if (DebugMarker == true)
       if (P.InstallVer != 0 && P.Status == 2 && (P.Flags & Flag::Auto) != Flag::Auto)
       {
         if (DebugMarker == true)

-           std::clog << OutputInDepth(Depth) << "Manual install request prevents MarkDelete of " << Pkg << std::endl;
+           std::clog << OutputInDepth(Depth) << "Manual install request prevents MarkDelete of " << APT::PrettyPkg(this, Pkg) << std::endl;

         return false;
       }
    }
         return false;
       }
    }


@@ -923,7 +965,7 @@ bool pkgDepCache::IsModeChangeOk(ModeList const mode, PkgIterator const &Pkg,
    {
       if (unlikely(DebugMarker == true))
         std::clog << OutputInDepth(Depth) << "Ignore Mark" << PrintMode(mode)
    {
       if (unlikely(DebugMarker == true))
         std::clog << OutputInDepth(Depth) << "Ignore Mark" << PrintMode(mode)

-                  << " of " << Pkg << " as its mode (" << PrintMode(P.Mode)
+                  << " of " << APT::PrettyPkg(this, Pkg) << " as its mode (" << PrintMode(P.Mode)

                   << ") is protected" << std::endl;
       return false;
    }
                   << ") is protected" << std::endl;
       return false;
    }


@@ -933,7 +975,7 @@ bool pkgDepCache::IsModeChangeOk(ModeList const mode, PkgIterator const &Pkg,
    {
       if (unlikely(DebugMarker == true))
         std::clog << OutputInDepth(Depth) << "Hold prevents Mark" << PrintMode(mode)
    {
       if (unlikely(DebugMarker == true))
         std::clog << OutputInDepth(Depth) << "Hold prevents Mark" << PrintMode(mode)

-                  << " of " << Pkg << std::endl;
+                  << " of " << APT::PrettyPkg(this, Pkg) << std::endl;

       return false;
    }
 
       return false;
    }
 


@@ -982,6 +1024,8 @@ struct CompareProviders {
         if (instA != instB)
            return instA == false;
       }
         if (instA != instB)
            return instA == false;
       }

+      if ((A->CurrentVer == 0 || B->CurrentVer == 0) && A->CurrentVer != B->CurrentVer)
+        return A->CurrentVer == 0;

       // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
       if (A->Group != B->Group)
       {
       // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
       if (A->Group != B->Group)
       {


@@ -1091,12 +1135,28 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
       return true;
 
    if (DebugMarker == true)
       return true;
 
    if (DebugMarker == true)

-      std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
+      std::clog << OutputInDepth(Depth) << "MarkInstall " << APT::PrettyPkg(this, Pkg) << " FU=" << FromUser << std::endl;

 
 

+   bool MoveAutoBitToDependencies = false;

    VerIterator const PV = P.InstVerIter(*this);
    if (unlikely(PV.end() == true))
       return false;
    VerIterator const PV = P.InstVerIter(*this);
    if (unlikely(PV.end() == true))
       return false;

-   bool const PinNeverMarkAutoSection = (PV->Section != 0 && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", PV.Section()));
+   else if (PV->Section != 0 && (P.Flags & Flag::Auto) != Flag::Auto)
+   {
+      VerIterator const CurVer = Pkg.CurrentVer();
+      if (CurVer.end() == false && CurVer->Section != 0 && strcmp(CurVer.Section(), PV.Section()) != 0)
+      {
+        bool const CurVerInMoveSection = ConfigValueInSubTree("APT::Move-Autobit-Sections", CurVer.Section());
+        bool const InstVerInMoveSection = ConfigValueInSubTree("APT::Move-Autobit-Sections", PV.Section());
+        MoveAutoBitToDependencies = (CurVerInMoveSection == false && InstVerInMoveSection == true);
+        if (MoveAutoBitToDependencies == true)
+        {
+           if(DebugAutoInstall == true)
+              std::clog << OutputInDepth(Depth) << "Setting " << Pkg.FullName(false) << " as auto-installed, moving manual to its dependencies" << std::endl;
+           MarkAuto(Pkg, true);
+        }
+      }
+   }

 
    DepIterator Dep = PV.DependsList();
    for (; Dep.end() != true;)
 
    DepIterator Dep = PV.DependsList();
    for (; Dep.end() != true;)


@@ -1131,7 +1191,7 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 
       /* unsatisfiable dependency: IsInstallOkDependenciesSatisfiableByCandidates
          would have prevented us to get here if not overridden, so just skip
 
       /* unsatisfiable dependency: IsInstallOkDependenciesSatisfiableByCandidates
          would have prevented us to get here if not overridden, so just skip

-        over the problem here as the frontend will know what it is doing */
+        over the problem here as the front-end will know what it is doing */

       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer && Start.IsNegative() == false)
         continue;
 
       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer && Start.IsNegative() == false)
         continue;
 


@@ -1210,14 +1270,17 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
               verlist.erase(InstVer);
               continue;
            }
               verlist.erase(InstVer);
               continue;
            }

+

            // now check if we should consider it a automatic dependency or not
            // now check if we should consider it a automatic dependency or not

-           if(InstPkg->CurrentVer == 0 && PinNeverMarkAutoSection)
+           if(InstPkg->CurrentVer == 0 && MoveAutoBitToDependencies)

            {
               if(DebugAutoInstall == true)
            {
               if(DebugAutoInstall == true)

-                 std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
-                            << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
+                 std::clog << OutputInDepth(Depth) << "Setting " << InstPkg.FullName(false) << " NOT as auto-installed (direct "
+                    << Start.DepType() << " of " << Pkg.FullName(false) << " which is manual and in APT::Move-Autobit-Sections)" << std::endl;

               MarkAuto(InstPkg, false);
            }
               MarkAuto(InstPkg, false);
            }

+
+

            break;
         } while(true);
         continue;
            break;
         } while(true);
         continue;


@@ -1227,9 +1290,9 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
         Otherwise we remove the offender if needed */
       else if (Start.IsNegative() == true && Start->Type != pkgCache::Dep::Obsoletes)
       {
         Otherwise we remove the offender if needed */
       else if (Start.IsNegative() == true && Start->Type != pkgCache::Dep::Obsoletes)
       {

-        SPtrArray<Version *> List = Start.AllTargets();
+        std::unique_ptr<Version *[]> List(Start.AllTargets());

         pkgCache::PkgIterator TrgPkg = Start.TargetPkg();
         pkgCache::PkgIterator TrgPkg = Start.TargetPkg();

-        for (Version **I = List; *I != 0; I++)
+        for (Version **I = List.get(); *I != 0; I++)

         {
            VerIterator Ver(*this,*I);
            PkgIterator Pkg = Ver.ParentPkg();
         {
            VerIterator Ver(*this,*I);
            PkgIterator Pkg = Ver.ParentPkg();


@@ -1305,7 +1368,7 @@ bool pkgDepCache::IsInstallOkMultiArchSameVersionSynced(PkgIterator const &Pkg,
       // not having a candidate or being in sync
       // (simple string-compare as stuff like '1' == '0:1-0' can't happen here)
       VerIterator CV = PkgState[P->ID].CandidateVerIter(*this);
       // not having a candidate or being in sync
       // (simple string-compare as stuff like '1' == '0:1-0' can't happen here)
       VerIterator CV = PkgState[P->ID].CandidateVerIter(*this);

-      if (CV.end() == true || strcmp(Pkg.CandVersion(), CV.VerStr()) == 0)
+      if (CV.end() == true || strcmp(CandVer.VerStr(), CV.VerStr()) == 0)

         continue;
 
       // packages losing M-A:same can be out-of-sync
         continue;
 
       // packages losing M-A:same can be out-of-sync


@@ -1318,9 +1381,9 @@ bool pkgDepCache::IsInstallOkMultiArchSameVersionSynced(PkgIterator const &Pkg,
 
       PkgState[Pkg->ID].iFlags |= AutoKept;
       if (unlikely(DebugMarker == true))
 
       PkgState[Pkg->ID].iFlags |= AutoKept;
       if (unlikely(DebugMarker == true))

-        std::clog << OutputInDepth(Depth) << "Ignore MarkInstall of " << Pkg
-           << " as it is not in sync with its M-A:same sibling " << P
-           << " (" << Pkg.CandVersion() << " != " << CV.VerStr() << ")" << std::endl;
+        std::clog << OutputInDepth(Depth) << "Ignore MarkInstall of " << APT::PrettyPkg(this, Pkg)
+           << " as it is not in sync with its M-A:same sibling " << APT::PrettyPkg(this, P)
+           << " (" << CandVer.VerStr() << " != " << CV.VerStr() << ")" << std::endl;

       return false;
    }
 
       return false;
    }
 


@@ -1361,12 +1424,20 @@ bool pkgDepCache::IsInstallOkDependenciesSatisfiableByCandidates(PkgIterator con
       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer)
       {
         if (DebugAutoInstall == true)
       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer)
       {
         if (DebugAutoInstall == true)

-           std::clog << OutputInDepth(Depth) << Start << " can't be satisfied!" << std::endl;
+           std::clog << OutputInDepth(Depth) << APT::PrettyDep(this, Start) << " can't be satisfied!" << std::endl;

 
         // the dependency is critical, but can't be installed, so discard the candidate
         // as the problemresolver will trip over it otherwise trying to install it (#735967)
         if (Pkg->CurrentVer != 0 && (PkgState[Pkg->ID].iFlags & Protected) != Protected)
 
         // the dependency is critical, but can't be installed, so discard the candidate
         // as the problemresolver will trip over it otherwise trying to install it (#735967)
         if (Pkg->CurrentVer != 0 && (PkgState[Pkg->ID].iFlags & Protected) != Protected)

+         {

            SetCandidateVersion(Pkg.CurrentVer());
            SetCandidateVersion(Pkg.CurrentVer());

+            StateCache &State = PkgState[Pkg->ID];
+           if (State.Mode != ModeDelete)
+           {
+              State.Mode = ModeKeep;
+              State.Update(Pkg, *this);
+           }
+         }

         return false;
       }
    }
         return false;
       }
    }


@@ -1414,6 +1485,11 @@ void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
    }
 }
                                                                        /*}}}*/
    }
 }
                                                                        /*}}}*/

+pkgCache::VerIterator pkgDepCache::GetCandidateVersion(PkgIterator const &Pkg)/*{{{*/
+{
+   return PkgState[Pkg->ID].CandidateVerIter(*this);
+}
+                                                                       /*}}}*/

 // DepCache::SetCandidateVersion - Change the candidate version                /*{{{*/
 // ---------------------------------------------------------------------
 /* */
 // DepCache::SetCandidateVersion - Change the candidate version                /*{{{*/
 // ---------------------------------------------------------------------
 /* */


@@ -1635,11 +1711,7 @@ void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
    CurVersion = "";
    if (Pkg->CurrentVer != 0)
       CurVersion = Pkg.CurrentVer().VerStr();
    CurVersion = "";
    if (Pkg->CurrentVer != 0)
       CurVersion = Pkg.CurrentVer().VerStr();

-   
-   // Strip off the epochs for display
-   CurVersion = StripEpoch(CurVersion);
-   CandVersion = StripEpoch(CandVersion);
-   
+

    // Figure out if its up or down or equal
    Status = Ver.CompareVer(Pkg.CurrentVer());
    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
    // Figure out if its up or down or equal
    Status = Ver.CompareVer(Pkg.CurrentVer());
    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)


@@ -1726,6 +1798,8 @@ bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep) const
 // Policy::GetPriority - Get the priority of the package pin           /*{{{*/
 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgIterator const &/*Pkg*/)
 { return 0; }
 // Policy::GetPriority - Get the priority of the package pin           /*{{{*/
 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgIterator const &/*Pkg*/)
 { return 0; }

+APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::VerIterator const &/*Ver*/, bool /*ConsiderFiles*/)
+{ return 0; }

 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgFileIterator const &/*File*/)
 { return 0; }
                                                                        /*}}}*/
 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgFileIterator const &/*File*/)
 { return 0; }
                                                                        /*}}}*/


@@ -1752,6 +1826,20 @@ bool pkgDepCache::MarkFollowsSuggests()
 }
 
 // pkgDepCache::MarkRequired - the main mark algorithm                 /*{{{*/
 }
 
 // pkgDepCache::MarkRequired - the main mark algorithm                 /*{{{*/

+static bool IsPkgInBoringState(pkgCache::PkgIterator const &Pkg, pkgDepCache::StateCache const * const PkgState)
+{
+   if (Pkg->CurrentVer == 0)
+   {
+      if (PkgState[Pkg->ID].Keep())
+        return true;
+   }
+   else
+   {
+      if (PkgState[Pkg->ID].Delete())
+        return true;
+   }
+   return false;
+}

 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
 {
    if (_config->Find("APT::Solver", "internal") != "internal")
 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
 {
    if (_config->Find("APT::Solver", "internal") != "internal")


@@ -1760,8 +1848,8 @@ bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 
    // init the states
    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 
    // init the states

-   map_id_t const PackagesCount = Head().PackageCount;
-   for(map_id_t i = 0; i < PackagesCount; ++i)
+   auto const PackagesCount = Head().PackageCount;
+   for(auto i = decltype(PackagesCount){0}; i < PackagesCount; ++i)

    {
       PkgState[i].Marked  = false;
       PkgState[i].Garbage = false;
    {
       PkgState[i].Marked  = false;
       PkgState[i].Garbage = false;


@@ -1775,152 +1863,131 @@ bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
    bool const follow_suggests   = MarkFollowsSuggests();
 
    // do the mark part, this is the core bit of the algorithm
    bool const follow_suggests   = MarkFollowsSuggests();
 
    // do the mark part, this is the core bit of the algorithm

-   for(PkgIterator p = PkgBegin(); !p.end(); ++p)
+   for (PkgIterator P = PkgBegin(); !P.end(); ++P)

    {
    {

-      if(!(PkgState[p->ID].Flags & Flag::Auto) ||
-         (p->Flags & Flag::Essential) ||
-         (p->Flags & Flag::Important) ||
-         userFunc.InRootSet(p) ||
-         // be nice even then a required package violates the policy (#583517)
-         // and do the full mark process also for required packages
-         (p.CurrentVer().end() != true &&
-          p.CurrentVer()->Priority == pkgCache::State::Required) ||
-         // packages which can't be changed (like holds) can't be garbage
-         (IsModeChangeOk(ModeGarbage, p, 0, false) == false))
-      {
-        // the package is installed (and set to keep)
-        if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
-           MarkPackage(p, p.CurrentVer(),
-                       follow_recommends, follow_suggests);
-        // the package is to be installed 
-        else if(PkgState[p->ID].Install())
-           MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
-                       follow_recommends, follow_suggests);
-      }
+      if (PkgState[P->ID].Marked || IsPkgInBoringState(P, PkgState))
+        continue;
+
+      if ((PkgState[P->ID].Flags & Flag::Auto) == 0)
+        ;
+      else if ((P->Flags & Flag::Essential) || (P->Flags & Flag::Important))
+        ;
+      // be nice even then a required package violates the policy (#583517)
+      // and do the full mark process also for required packages
+      else if (P->CurrentVer != 0 && P.CurrentVer()->Priority == pkgCache::State::Required)
+        ;
+      else if (userFunc.InRootSet(P))
+        ;
+      // packages which can't be changed (like holds) can't be garbage
+      else if (IsModeChangeOk(ModeGarbage, P, 0, false) == false)
+        ;
+      else
+        continue;
+
+      if (PkgState[P->ID].Install())
+        MarkPackage(P, PkgState[P->ID].InstVerIter(*this),
+              follow_recommends, follow_suggests);
+      else
+        MarkPackage(P, P.CurrentVer(),
+              follow_recommends, follow_suggests);

    }
 
    return true;
 }
                                                                        /*}}}*/
 // MarkPackage - mark a single package in Mark-and-Sweep               /*{{{*/
    }
 
    return true;
 }
                                                                        /*}}}*/
 // MarkPackage - mark a single package in Mark-and-Sweep               /*{{{*/

-void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
-                             const pkgCache::VerIterator &ver,
+void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &Pkg,
+                             const pkgCache::VerIterator &Ver,

                              bool const &follow_recommends,
                              bool const &follow_suggests)
 {
                              bool const &follow_recommends,
                              bool const &follow_suggests)
 {

-   pkgDepCache::StateCache &state = PkgState[pkg->ID];
+   {
+      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 we are marked already we are done
-   if(state.Marked)
+   if (IsPkgInBoringState(Pkg, PkgState))

       return;
 
       return;
 

-   VerIterator const currver = pkg.CurrentVer();
-   VerIterator const instver = state.InstVerIter(*this);
-
-#if 0
-   VerIterator const candver = state.CandidateVerIter(*this);
+   bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
+   if(debug_autoremove)
+      std::clog << "Marking: " << Pkg.FullName() << " " << Ver.VerStr() << std::endl;

 
 

-   // If a package was garbage-collected but is now being marked, we
-   // should re-select it 
-   // For cases when a pkg is set to upgrade and this trigger the
-   // removal of a no-longer used dependency.  if the pkg is set to
-   // keep again later it will result in broken deps
-   if(state.Delete() && state.RemoveReason = Unused) 
+   for (auto D = Ver.DependsList(); D.end() == false; ++D)

    {
    {

-      if(ver==candver)
-        mark_install(pkg, false, false, NULL);
-      else if(ver==pkg.CurrentVer())
-        MarkKeep(pkg, false, false);
-      
-      instver=state.InstVerIter(*this);
-   }
-#endif
+      auto const T = D.TargetPkg();
+      if (PkgState[T->ID].Marked)
+        continue;

 
 

-   // For packages that are not going to be removed, ignore versions
-   // other than the InstVer.  For packages that are going to be
-   // removed, ignore versions other than the current version.
-   if(!(ver == instver && !instver.end()) &&
-      !(ver == currver && instver.end() && !ver.end()))
-      return;
+      if (D->Type != Dep::Depends &&
+           D->Type != Dep::PreDepends &&
+           (follow_recommends == false || D->Type != Dep::Recommends) &&
+           (follow_suggests == false || D->Type != Dep::Suggests))
+        continue;

 
 

-   bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
+      // handle the virtual part first
+      APT::VersionVector providers;
+      for(auto Prv = T.ProvidesList(); Prv.end() == false; ++Prv)
+      {
+        auto PP = Prv.OwnerPkg();
+        if (IsPkgInBoringState(PP, PkgState))
+           continue;

 
 

-   if(debug_autoremove)
-     {
-       std::clog << "Marking: " << pkg.FullName();
-       if(!ver.end())
-        std::clog << " " << ver.VerStr();
-       if(!currver.end())
-        std::clog << ", Curr=" << currver.VerStr();
-       if(!instver.end())
-        std::clog << ", Inst=" << instver.VerStr();
-       std::clog << std::endl;
-     }
+        // 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)
+           continue;
+
+        providers.emplace_back(PV);
+      }
+      if (providers.empty() == false)
+      {
+        // 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)
+        {
+           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);
+        }
+      }

 
 

-   state.Marked=true;
+      // now deal with the real part of the package
+      if (IsPkgInBoringState(T, PkgState))
+        continue;

 
 

-   if(ver.end() == true)
-      return;
+      auto const TV = (PkgState[T->ID].Install()) ?
+        PkgState[T->ID].InstVerIter(*this) : T.CurrentVer();
+      if (unlikely(TV.end()) || D.IsSatisfied(TV) == false)
+        continue;

 
 

-     for(DepIterator d = ver.DependsList(); !d.end(); ++d)
-     {
-       if(d->Type == Dep::Depends ||
-          d->Type == Dep::PreDepends ||
-          (follow_recommends &&
-           d->Type == Dep::Recommends) ||
-          (follow_suggests &&
-           d->Type == Dep::Suggests))
-        {
-          // Try all versions of this package.
-          for(VerIterator V = d.TargetPkg().VersionList(); 
-              !V.end(); ++V)
-          {
-             if(d.IsSatisfied(V))
-             {
-               if(debug_autoremove)
-                 {
-                   std::clog << "Following dep: " << d.ParentPkg().FullName()
-                             << " " << d.ParentVer().VerStr() << " "
-                             << d.DepType() << " " << d.TargetPkg().FullName();
-                   if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
-                     {
-                       std::clog << " (" << d.CompType() << " "
-                                 << d.TargetVer() << ")";
-                     }
-                   std::clog << std::endl;
-                 }
-                MarkPackage(V.ParentPkg(), V,
-                            follow_recommends, follow_suggests);
-             }
-          }
-          // Now try virtual packages
-          for(PrvIterator prv=d.TargetPkg().ProvidesList(); 
-              !prv.end(); ++prv)
-          {
-             if(d.IsSatisfied(prv))
-             {
-               if(debug_autoremove)
-                 {
-                   std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
-                             << d.ParentVer().VerStr() << " "
-                             << d.DepType() << " " << d.TargetPkg().FullName() << " ";
-                   if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
-                     {
-                       std::clog << " (" << d.CompType() << " "
-                                 << d.TargetVer() << ")";
-                     }
-                   std::clog << ", provided by "
-                             << prv.OwnerPkg().FullName() << " "
-                             << prv.OwnerVer().VerStr()
-                             << std::endl;
-                 }
-
-                MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
-                            follow_recommends, follow_suggests);
-             }
-          }
-       }
-     }
+      if (debug_autoremove)
+        std::clog << "Following dep: " << APT::PrettyDep(this, D) << std::endl;
+      MarkPackage(T, TV, follow_recommends, follow_suggests);
+   }

 }
                                                                        /*}}}*/
 bool pkgDepCache::Sweep()                                              /*{{{*/
 }
                                                                        /*}}}*/
 bool pkgDepCache::Sweep()                                              /*{{{*/


@@ -1956,7 +2023,7 @@ bool pkgDepCache::MarkAndSweep(InRootSetFunc &rootFunc)
 }
 bool pkgDepCache::MarkAndSweep()
 {
 }
 bool pkgDepCache::MarkAndSweep()
 {

-   std::auto_ptr<InRootSetFunc> f(GetRootSetFunc());
+   std::unique_ptr<InRootSetFunc> f(GetRootSetFunc());

    if(f.get() != NULL)
       return MarkAndSweep(*f.get());
    else
    if(f.get() != NULL)
       return MarkAndSweep(*f.get());
    else