(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

5 files changed, 374 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)
diff --git a/doc/examples/configure-index b/doc/examples/configure-index
index ce51153c3..07feea4dc 100644
--- a/doc/examples/configure-index
+++ b/doc/examples/configure-index
@@ -105,6 +105,7 @@ APT
      Upgrade-Allow-New "<BOOL>";
      Always-Include-Phased-Updates "<BOOL>";
      Never-Include-Phased-Updates "<BOOL>";
+     Phase-Policy "<BOOL>"; // internal
      Purge "<BOOL>";
      ReInstall "<BOOL>";
      Compile "<BOOL>";
diff --git a/test/integration/test-phased-updates b/test/integration/test-phased-updates
index c06d6f5a1..d505b52d9 100755
--- a/test/integration/test-phased-updates
+++ b/test/integration/test-phased-updates
@@ -6,6 +6,7 @@ TESTDIR="$(readlink -f "$(dirname "$0")")"
 
 setupenvironment
 echo 'Debug::Phasing "1";' > rootdir/etc/apt/apt.conf.d/debug-phasing
+echo 'APT::Get::Phase-Policy "1";' > rootdir/etc/apt/apt.conf.d/debug-phasing
 configarchitecture 'i386' 'armel'
 
 
diff --git a/test/integration/test-phased-updates-upgrade b/test/integration/test-phased-updates-upgrade
new file mode 100755
index 000000000..ab39681de
--- /dev/null
+++ b/test/integration/test-phased-updates-upgrade
@@ -0,0 +1,256 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+
+setupenvironment
+echo 'Debug::Phasing "1";' > rootdir/etc/apt/apt.conf.d/debug-phasing
+configarchitecture 'i386' 'armel'
+
+
+
+# Test case phased: The package is installed and has a phased update available
+insertinstalledpackage 'phased' 'all' '1'
+insertpackage 'unstable-updates' 'phased' 'all' '3' 'Phased-Update-Percentage: 0'
+
+# Test case phased-security: A phased package is in security and will be installed
+insertinstalledpackage 'phased-security' 'all' '1'
+insertpackage 'unstable-security' 'phased-security' 'all' '2'
+insertpackage 'unstable-updates' 'phased-security' 'all' '3' 'Phased-Update-Percentage: 0'
+
+# Test case phased-dep: A released update depends on the phased dependency phased-dep
+insertinstalledpackage 'phased-dep' 'all' '1'
+insertinstalledpackage 'depends-phased-dep' 'all' '1'
+insertpackage 'unstable-updates' 'phased-dep' 'all' '3' 'Phased-Update-Percentage: 0'
+insertpackage 'unstable-updates' 'depends-phased-dep' 'all' '3' 'Depends: phased-dep (= 3)'
+
+# Test case phased-new: A release update depends on a new package that's phasing
+insertinstalledpackage 'depends-phased-new' 'all' '1'
+insertpackage 'unstable-updates' 'phased-new' 'all' '3' 'Phased-Update-Percentage: 0'
+insertpackage 'unstable-updates' 'depends-phased-new' 'all' '3' 'Depends: phased-new (= 3)'
+
+setupaptarchive
+
+msgmsg "Testing with default (upgrade-based) implementation"
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following NEW packages will be installed:
+  phased-new
+The following packages have been kept back:
+  depends-phased-dep phased phased-dep
+The following packages will be upgraded:
+  depends-phased-new phased-security
+2 upgraded, 1 newly installed, 0 to remove and 3 not upgraded.
+Inst phased-new (3 unstable-updates [all])
+Inst depends-phased-new [1] (3 unstable-updates [all])
+Inst phased-security [1] (3 unstable-updates [all])
+Conf phased-new (3 unstable-updates [all])
+Conf depends-phased-new (3 unstable-updates [all])
+Conf phased-security (3 unstable-updates [all])" aptget dist-upgrade -s -q
+
+for always in APT::Get::Always-Include-Phased-Updates Update-Manager::Always-Include-Phased-Updates; do
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following NEW packages will be installed:
+  phased-new
+The following packages will be upgraded:
+  depends-phased-dep depends-phased-new phased phased-dep phased-security
+5 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
+Inst phased-dep [1] (3 unstable-updates [all])
+Inst depends-phased-dep [1] (3 unstable-updates [all])
+Inst phased-new (3 unstable-updates [all])
+Inst depends-phased-new [1] (3 unstable-updates [all])
+Inst phased [1] (3 unstable-updates [all])
+Inst phased-security [1] (3 unstable-updates [all])
+Conf phased-dep (3 unstable-updates [all])
+Conf depends-phased-dep (3 unstable-updates [all])
+Conf phased-new (3 unstable-updates [all])
+Conf depends-phased-new (3 unstable-updates [all])
+Conf phased (3 unstable-updates [all])
+Conf phased-security (3 unstable-updates [all])" aptget dist-upgrade -s -q -o $always=1
+done
+
+SOURCE_DATE_EPOCH=1 testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following NEW packages will be installed:
+  phased-new
+The following packages will be upgraded:
+  depends-phased-dep depends-phased-new phased phased-dep phased-security
+5 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
+Inst phased-dep [1] (3 unstable-updates [all])
+Inst depends-phased-dep [1] (3 unstable-updates [all])
+Inst phased-new (3 unstable-updates [all])
+Inst depends-phased-new [1] (3 unstable-updates [all])
+Inst phased [1] (3 unstable-updates [all])
+Inst phased-security [1] (3 unstable-updates [all])
+Conf phased-dep (3 unstable-updates [all])
+Conf depends-phased-dep (3 unstable-updates [all])
+Conf phased-new (3 unstable-updates [all])
+Conf depends-phased-new (3 unstable-updates [all])
+Conf phased (3 unstable-updates [all])
+Conf phased-security (3 unstable-updates [all])" aptget dist-upgrade -s -q -o with-source-date-epoch=1
+
+for never in APT::Get::Never-Include-Phased-Updates Update-Manager::Never-Include-Phased-Updates; do
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following NEW packages will be installed:
+  phased-new
+The following packages have been kept back:
+  depends-phased-dep phased phased-dep
+The following packages will be upgraded:
+  depends-phased-new phased-security
+2 upgraded, 1 newly installed, 0 to remove and 3 not upgraded.
+Inst phased-new (3 unstable-updates [all])
+Inst depends-phased-new [1] (3 unstable-updates [all])
+Inst phased-security [1] (3 unstable-updates [all])
+Conf phased-new (3 unstable-updates [all])
+Conf depends-phased-new (3 unstable-updates [all])
+Conf phased-security (3 unstable-updates [all])" aptget dist-upgrade -s -q -o $never=1
+done
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following NEW packages will be installed:
+  phased-new
+The following packages have been kept back:
+  depends-phased-dep phased phased-dep
+The following packages will be upgraded:
+  depends-phased-new phased-security
+2 upgraded, 1 newly installed, 0 to remove and 3 not upgraded.
+Inst phased-new (3 unstable-updates [all])
+Inst depends-phased-new [1] (3 unstable-updates [all])
+Inst phased-security [1] (3 unstable-updates [all])
+Conf phased-new (3 unstable-updates [all])
+Conf depends-phased-new (3 unstable-updates [all])
+Conf phased-security (3 unstable-updates [all])" aptget upgrade -s -q --with-new-pkgs
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following packages have been kept back:
+  depends-phased-dep depends-phased-new phased phased-dep
+The following packages will be upgraded:
+  phased-security
+1 upgraded, 0 newly installed, 0 to remove and 4 not upgraded.
+Inst phased-security [1] (3 unstable-updates [all])
+Conf phased-security (3 unstable-updates [all])" aptget upgrade -s -q
+
+
+msgmsg "Testing with policy based implementation"
+echo 'APT::Get::Phase-Policy "1";' > rootdir/etc/apt/apt.conf.d/phase-by-policy
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following NEW packages will be installed:
+  phased-new
+The following packages have been kept back:
+  depends-phased-dep
+The following packages will be upgraded:
+  depends-phased-new phased-security
+2 upgraded, 1 newly installed, 0 to remove and 1 not upgraded.
+Inst phased-new (3 unstable-updates [all])
+Inst depends-phased-new [1] (3 unstable-updates [all])
+Inst phased-security [1] (2 unstable-security [all])
+Conf phased-new (3 unstable-updates [all])
+Conf depends-phased-new (3 unstable-updates [all])
+Conf phased-security (2 unstable-security [all])" aptget dist-upgrade -s -q
+
+for always in APT::Get::Always-Include-Phased-Updates Update-Manager::Always-Include-Phased-Updates; do
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following NEW packages will be installed:
+  phased-new
+The following packages will be upgraded:
+  depends-phased-dep depends-phased-new phased phased-dep phased-security
+5 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
+Inst phased-dep [1] (3 unstable-updates [all])
+Inst depends-phased-dep [1] (3 unstable-updates [all])
+Inst phased-new (3 unstable-updates [all])
+Inst depends-phased-new [1] (3 unstable-updates [all])
+Inst phased [1] (3 unstable-updates [all])
+Inst phased-security [1] (3 unstable-updates [all])
+Conf phased-dep (3 unstable-updates [all])
+Conf depends-phased-dep (3 unstable-updates [all])
+Conf phased-new (3 unstable-updates [all])
+Conf depends-phased-new (3 unstable-updates [all])
+Conf phased (3 unstable-updates [all])
+Conf phased-security (3 unstable-updates [all])" aptget dist-upgrade -s -q -o $always=1
+done
+
+# In the policy implementation, we can update security
+for never in APT::Get::Never-Include-Phased-Updates Update-Manager::Never-Include-Phased-Updates; do
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following NEW packages will be installed:
+  phased-new
+The following packages have been kept back:
+  depends-phased-dep
+The following packages will be upgraded:
+  depends-phased-new phased-security
+2 upgraded, 1 newly installed, 0 to remove and 1 not upgraded.
+Inst phased-new (3 unstable-updates [all])
+Inst depends-phased-new [1] (3 unstable-updates [all])
+Inst phased-security [1] (2 unstable-security [all])
+Conf phased-new (3 unstable-updates [all])
+Conf depends-phased-new (3 unstable-updates [all])
+Conf phased-security (2 unstable-security [all])" aptget dist-upgrade -s -q -o $never=1
+done
+
+SOURCE_DATE_EPOCH=1 testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following NEW packages will be installed:
+  phased-new
+The following packages will be upgraded:
+  depends-phased-dep depends-phased-new phased phased-dep phased-security
+5 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
+Inst phased-dep [1] (3 unstable-updates [all])
+Inst depends-phased-dep [1] (3 unstable-updates [all])
+Inst phased-new (3 unstable-updates [all])
+Inst depends-phased-new [1] (3 unstable-updates [all])
+Inst phased [1] (3 unstable-updates [all])
+Inst phased-security [1] (3 unstable-updates [all])
+Conf phased-dep (3 unstable-updates [all])
+Conf depends-phased-dep (3 unstable-updates [all])
+Conf phased-new (3 unstable-updates [all])
+Conf depends-phased-new (3 unstable-updates [all])
+Conf phased (3 unstable-updates [all])
+Conf phased-security (3 unstable-updates [all])" aptget dist-upgrade -s -q -o with-source-date-epoch=1
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following NEW packages will be installed:
+  phased-new
+The following packages have been kept back:
+  depends-phased-dep
+The following packages will be upgraded:
+  depends-phased-new phased-security
+2 upgraded, 1 newly installed, 0 to remove and 1 not upgraded.
+Inst phased-new (3 unstable-updates [all])
+Inst depends-phased-new [1] (3 unstable-updates [all])
+Inst phased-security [1] (2 unstable-security [all])
+Conf phased-new (3 unstable-updates [all])
+Conf depends-phased-new (3 unstable-updates [all])
+Conf phased-security (2 unstable-security [all])" aptget upgrade -s -q --with-new-pkgs
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following packages have been kept back:
+  depends-phased-dep depends-phased-new
+The following packages will be upgraded:
+  phased-security
+1 upgraded, 0 newly installed, 0 to remove and 2 not upgraded.
+Inst phased-security [1] (2 unstable-security [all])
+Conf phased-security (2 unstable-security [all])" aptget upgrade -s -q