(Temporarily) Rewrite phased updates using a keep-back approach

This is a lot closer to the original implementation in update-manager,
but still has a couple of differences that might cause bugs:

- When checking whether a version is a security update, we only
  check versions in between and not any later version. This happens
  mostly because we do not know the suite, so we just check if there
  is any version between the installed version and our target that
  is a security update

- We only keep already installed packages, as we run before the
  resolver. update-manager first runs the resolver, and then marks
  for keep all packages that were upgraded or newly installed that
  are phasing (afaict).

This approach has a significant caveat that if you have version 1
installed from a release pocket, version 2 is in security, and version
3 is phasing in updates, that it installs version 3 rather than 2
from security as the policy based implementation does.

It also means that apt install does not respect phasing and would
always install version 3 in such a scenario.

LP: #1979244

2 files changed, 116 insertions, 2 deletions

diff --git a/apt-pkg/policy.cc b/apt-pkg/policy.cc
index b30eddb37..fcb7299f4 100644
--- a/apt-pkg/policy.cc
+++ b/apt-pkg/policy.cc
@@ -288,6 +288,10 @@ void pkgPolicy::CreatePin(pkgVersionMatch::MatchType Type,string Name,
 // Returns true if this update is excluded by phasing.
 static inline bool ExcludePhased(std::string machineID, pkgCache::VerIterator const &Ver)
 {
+   // FIXME: We have migrated to a legacy implementation until LP: #1929082 is fixed
+   if (not _config->FindB("APT::Get::Phase-Policy", false))
+      return false;
+
    // The order and fallbacks for the always/never checks come from update-manager and exist
    // to preserve compatibility.
    if (_config->FindB("APT::Get::Always-Include-Phased-Updates",
diff --git a/apt-pkg/upgrade.cc b/apt-pkg/upgrade.cc
index 06c3751e0..a7e18026b 100644
--- a/apt-pkg/upgrade.cc
+++ b/apt-pkg/upgrade.cc
@@ -2,19 +2,117 @@
 #include <config.h>
 
 #include <apt-pkg/algorithms.h>
+#include <apt-pkg/aptconfiguration.h>
 #include <apt-pkg/configuration.h>
 #include <apt-pkg/depcache.h>
 #include <apt-pkg/edsp.h>
 #include <apt-pkg/error.h>
 #include <apt-pkg/pkgcache.h>
 #include <apt-pkg/progress.h>
+#include <apt-pkg/strutl.h>
 #include <apt-pkg/upgrade.h>
 
+#include <random>
 #include <string>
 
 #include <apti18n.h>
 									/*}}}*/
 
+struct PhasedUpgrader
+{
+   std::string machineID;
+   bool isChroot;
+
+   PhasedUpgrader()
+   {
+      machineID = APT::Configuration::getMachineID();
+   }
+
+   // See if this version is a security update. This also checks, for installed packages,
+   // if any of the previous versions is a security update
+   bool IsSecurityUpdate(pkgCache::VerIterator const &Ver)
+   {
+      auto Pkg = Ver.ParentPkg();
+      auto Installed = Pkg.CurrentVer();
+
+      auto OtherVer = Pkg.VersionList();
+
+      // Advance to first version < our version
+      while (OtherVer->ID != Ver->ID)
+	 ++OtherVer;
+      ++OtherVer;
+
+      // Iterate over all versions < our version
+      for (; !OtherVer.end() && (Installed.end() || OtherVer->ID != Installed->ID); OtherVer++)
+      {
+	 for (auto PF = OtherVer.FileList(); !PF.end(); PF++)
+	    if (PF.File() && PF.File().Archive() != nullptr && APT::String::Endswith(PF.File().Archive(), "-security"))
+	       return true;
+      }
+      return false;
+   }
+
+   // Check if this version is a phased update that should be ignored
+   bool IsIgnoredPhasedUpdate(pkgCache::VerIterator const &Ver)
+   {
+      if (_config->FindB("APT::Get::Phase-Policy", false))
+	 return false;
+
+      // The order and fallbacks for the always/never checks come from update-manager and exist
+      // to preserve compatibility.
+      if (_config->FindB("APT::Get::Always-Include-Phased-Updates",
+			 _config->FindB("Update-Manager::Always-Include-Phased-Updates", false)))
+	 return false;
+
+      if (_config->FindB("APT::Get::Never-Include-Phased-Updates",
+			 _config->FindB("Update-Manager::Never-Include-Phased-Updates", false)))
+	 return true;
+
+      if (machineID.empty()			    // no machine-id
+	  || getenv("SOURCE_DATE_EPOCH") != nullptr // reproducible build - always include
+	  || APT::Configuration::isChroot())
+	 return false;
+
+      std::string seedStr = std::string(Ver.SourcePkgName()) + "-" + Ver.SourceVerStr() + "-" + machineID;
+      std::seed_seq seed(seedStr.begin(), seedStr.end());
+      std::minstd_rand rand(seed);
+      std::uniform_int_distribution<unsigned int> dist(0, 100);
+
+      return dist(rand) > Ver.PhasedUpdatePercentage();
+   }
+
+   bool ShouldKeep(pkgDepCache &Cache, pkgCache::PkgIterator Pkg)
+   {
+      if (Pkg->CurrentVer == 0)
+	 return false;
+      if (Cache[Pkg].InstallVer == 0)
+	 return false;
+      if (Cache[Pkg].InstVerIter(Cache).PhasedUpdatePercentage() == 100)
+	 return false;
+      if (IsSecurityUpdate(Cache[Pkg].InstVerIter(Cache)))
+	 return false;
+      if (!IsIgnoredPhasedUpdate(Cache[Pkg].InstVerIter(Cache)))
+	 return false;
+
+      return true;
+   }
+
+   // Hold back upgrades to phased versions of already installed packages, unless
+   // they are security updates
+   void HoldBackIgnoredPhasedUpdates(pkgDepCache &Cache, pkgProblemResolver *Fix)
+   {
+      for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+      {
+	 if (not ShouldKeep(Cache, I))
+	    continue;
+
+	 Cache.MarkKeep(I, false, false);
+	 if (Fix != nullptr)
+	    Fix->Protect(I);
+      }
+   }
+};
+
 // DistUpgrade - Distribution upgrade					/*{{{*/
 // ---------------------------------------------------------------------
 /* This autoinstalls every package and then force installs every 
@@ -115,6 +213,8 @@ static bool pkgDistUpgrade(pkgDepCache &Cache, OpProgress * const Progress)
       }
    }
 
+   PhasedUpgrader().HoldBackIgnoredPhasedUpdates(Cache, &Fix);
+
    bool const success = Fix.ResolveInternal(false);
    if (Progress != NULL)
       Progress->Done();
@@ -134,7 +234,7 @@ static bool pkgAllUpgradeNoNewPackages(pkgDepCache &Cache, OpProgress * const Pr
 
    pkgDepCache::ActionGroup group(Cache);
    pkgProblemResolver Fix(&Cache);
-
+   PhasedUpgrader phasedUpgrader;
    // Upgrade all installed packages
    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
    {
@@ -144,7 +244,10 @@ static bool pkgAllUpgradeNoNewPackages(pkgDepCache &Cache, OpProgress * const Pr
       if (_config->FindB("APT::Ignore-Hold",false) == false)
 	 if (I->SelectedState == pkgCache::State::Hold)
 	    continue;
-      
+
+      if (phasedUpgrader.ShouldKeep(Cache, I))
+	 continue;
+
       if (I->CurrentVer != 0 && Cache[I].InstallVer != 0)
 	 Cache.MarkInstall(I, false, 0, false);
    }
@@ -152,6 +255,8 @@ static bool pkgAllUpgradeNoNewPackages(pkgDepCache &Cache, OpProgress * const Pr
    if (Progress != NULL)
       Progress->Progress(50);
 
+   phasedUpgrader.HoldBackIgnoredPhasedUpdates(Cache, &Fix);
+
    // resolve remaining issues via keep
    bool const success = Fix.ResolveByKeepInternal();
    if (Progress != NULL)
@@ -178,6 +283,7 @@ static bool pkgAllUpgradeWithNewPackages(pkgDepCache &Cache, OpProgress * const
 
    pkgDepCache::ActionGroup group(Cache);
    pkgProblemResolver Fix(&Cache);
+   PhasedUpgrader phasedUpgrader;
 
    // provide the initial set of stuff we want to upgrade by marking
    // all upgradable packages for upgrade
@@ -188,6 +294,8 @@ static bool pkgAllUpgradeWithNewPackages(pkgDepCache &Cache, OpProgress * const
          if (_config->FindB("APT::Ignore-Hold",false) == false)
             if (I->SelectedState == pkgCache::State::Hold)
                continue;
+	 if (phasedUpgrader.ShouldKeep(Cache, I))
+	    continue;
 
 	 Cache.MarkInstall(I, false, 0, false);
       }
@@ -212,6 +320,8 @@ static bool pkgAllUpgradeWithNewPackages(pkgDepCache &Cache, OpProgress * const
    if (Progress != NULL)
       Progress->Progress(60);
 
+   phasedUpgrader.HoldBackIgnoredPhasedUpdates(Cache, &Fix);
+
    // resolve remaining issues via keep
    bool const success = Fix.ResolveByKeepInternal();
    if (Progress != NULL)