Count uninstallable packages in "not upgraded"

If a first step of the solver can figure out that a package is
uninstallable it might reset the candidate so that later steps are
prevented from exploring this dead end. While that helps the resolver it
can confuse the display of the found solution as this will include an
incorrect count of packages not upgraded in this solution.

It was possible before, but happens a fair bit more with the April/May
resolver changes last year so finally doing proper counting is a good
idea.

Sadly this is a bit harder than just getting the number first and than
subtracting the packages we upgraded from it as the user can influence
candidates via the command line and a package which could be upgraded,
but is removed instead shouldn't count as not upgraded as we clearly did
something with it. So we keep a list of packages instead of a number
which also help in the upgrade cmds as those want to show the list.

Closes: #981535

9 files changed, 108 insertions, 42 deletions

diff --git a/apt-pkg/cacheset.cc b/apt-pkg/cacheset.cc
index 565a2b298..df750cb44 100644
--- a/apt-pkg/cacheset.cc
+++ b/apt-pkg/cacheset.cc
@@ -295,7 +295,8 @@ bool CacheSetHelper::PackageFromPackageName(PackageContainerInterface * const pc
 	pci->insert(Pkg);
 	return true;
 }
-
+									/*}}}*/
+// PackageFromPattern - Return all packages matching a specific pattern	/*{{{*/
 bool CacheSetHelper::PackageFromPattern(PackageContainerInterface *const pci, pkgCacheFile &Cache, std::string const &pattern)
 {
    if (pattern.size() < 1 || (pattern[0] != '?' && pattern[0] != '~'))
diff --git a/apt-private/private-install.cc b/apt-private/private-install.cc
index 0c26c4275..a88668b2a 100644
--- a/apt-private/private-install.cc
+++ b/apt-private/private-install.cc
@@ -100,7 +100,7 @@ static void RemoveDownloadNeedingItemsFromFetcher(pkgAcquire &Fetcher, bool &Tra
       I = Fetcher.ItemsBegin();
    }
 }
-bool InstallPackages(CacheFile &Cache, bool ShwKept, bool Ask, bool Safety, std::string const &Hook, CommandLine const &CmdL)
+bool InstallPackages(CacheFile &Cache, APT::PackageVector &HeldBackPackages, bool ShwKept, bool Ask, bool Safety, std::string const &Hook, CommandLine const &CmdL)
 {
    if (not RunScripts("APT::Install::Pre-Invoke"))
       return false;
@@ -145,7 +145,21 @@ bool InstallPackages(CacheFile &Cache, bool ShwKept, bool Ask, bool Safety, std:
       if (Missing)
       {
 	 if (_config->FindB("APT::Get::Fix-Missing",false))
+	 {
 	    PM->FixMissing();
+	    SortedPackageUniverse Universe(Cache);
+	    APT::PackageVector NewHeldBackPackages;
+	    for (auto const &Pkg: Universe)
+	    {
+	       if (Pkg->CurrentVer == 0 || Cache[Pkg].Delete())
+		  continue;
+	       if (Cache[Pkg].Upgradable() && not Cache[Pkg].Upgrade())
+		  NewHeldBackPackages.push_back(Pkg);
+	       else if (std::find(HeldBackPackages.begin(), HeldBackPackages.end(), Pkg) != HeldBackPackages.end())
+		  NewHeldBackPackages.push_back(Pkg);
+	    }
+	    std::swap(NewHeldBackPackages, HeldBackPackages);
+	 }
 	 else
 	    return _error->Error(_("Unable to fetch some archives, maybe run apt-get update or try with --fix-missing?"));
       }
@@ -158,8 +172,8 @@ bool InstallPackages(CacheFile &Cache, bool ShwKept, bool Ask, bool Safety, std:
    ShowDel(c1out,Cache);
    ShowNew(c1out,Cache);
    if (ShwKept == true)
-      ShowKept(c1out,Cache);
-   bool const Hold = !ShowHold(c1out,Cache);
+      ShowKept(c1out,Cache, HeldBackPackages);
+   bool const Hold = not ShowHold(c1out,Cache);
    if (_config->FindB("APT::Get::Show-Upgraded",true) == true)
       ShowUpgraded(c1out,Cache);
    bool const Downgrade = !ShowDowngraded(c1out,Cache);
@@ -171,7 +185,7 @@ bool InstallPackages(CacheFile &Cache, bool ShwKept, bool Ask, bool Safety, std:
    if (not Hook.empty())
       RunJsonHook(Hook, "org.debian.apt.hooks.install.package-list", CmdL.FileList, Cache);
 
-   Stats(c1out,Cache);
+   Stats(c1out,Cache, HeldBackPackages);
    if (not Hook.empty())
       RunJsonHook(Hook, "org.debian.apt.hooks.install.statistics", CmdL.FileList, Cache);
 
@@ -578,19 +592,16 @@ bool DoAutomaticRemove(CacheFile &Cache)
 static const unsigned short MOD_REMOVE = 1;
 static const unsigned short MOD_INSTALL = 2;
 
-bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, CacheFile &Cache, int UpgradeMode)
-{
-   std::vector<PseudoPkg> VolatileCmdL;
-   return DoCacheManipulationFromCommandLine(CmdL, VolatileCmdL, Cache, UpgradeMode);
-}
-bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg> &VolatileCmdL, CacheFile &Cache, int UpgradeMode)
+bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg> &VolatileCmdL, CacheFile &Cache, int UpgradeMode,
+					APT::PackageVector &HeldBackPackages)
 {
    std::map<unsigned short, APT::VersionSet> verset;
    std::set<std::string> UnknownPackages;
-   return DoCacheManipulationFromCommandLine(CmdL, VolatileCmdL, Cache, verset, UpgradeMode, UnknownPackages);
+   return DoCacheManipulationFromCommandLine(CmdL, VolatileCmdL, Cache, verset, UpgradeMode, UnknownPackages, HeldBackPackages);
 }
 bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg> &VolatileCmdL, CacheFile &Cache,
-					std::map<unsigned short, APT::VersionSet> &verset, int UpgradeMode, std::set<std::string> &UnknownPackages)
+					std::map<unsigned short, APT::VersionSet> &verset, int UpgradeMode,
+					std::set<std::string> &UnknownPackages, APT::PackageVector &HeldBackPackages)
 {
    // Enter the special broken fixing mode if the user specified arguments
    bool BrokenFix = false;
@@ -663,6 +674,7 @@ bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg
 
   TryToInstall InstallAction(Cache, Fix.get(), BrokenFix);
   TryToRemove RemoveAction(Cache, Fix.get());
+  APT::PackageSet UpgradablePackages;
 
    // new scope for the ActionGroup
    {
@@ -677,6 +689,11 @@ bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg
 	    RemoveAction = std::for_each(verset[MOD_REMOVE].begin(), verset[MOD_REMOVE].end(), RemoveAction);
       }
 
+      {
+	 APT::CacheSetHelper helper;
+	 helper.PackageFrom(APT::CacheSetHelper::PATTERN, &UpgradablePackages, Cache, "?upgradable");
+      }
+
       if (Fix != NULL && _config->FindB("APT::Get::AutoSolving", true) == true)
       {
 	 InstallAction.propergateReleaseCandiateSwitching(helper.selectedByRelease, c0out);
@@ -732,6 +749,12 @@ bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg
        _config->FindB("APT::Get::Simulate",false) == false)
       Cache->writeStateFile(NULL);
 
+   SortedPackageUniverse Universe(Cache);
+   for (auto const &Pkg: Universe)
+      if (Pkg->CurrentVer != 0 && not Cache[Pkg].Upgrade() && not Cache[Pkg].Delete() &&
+	  UpgradablePackages.find(Pkg) != UpgradablePackages.end())
+	 HeldBackPackages.push_back(Pkg);
+
    return true;
 }
 									/*}}}*/
@@ -837,8 +860,9 @@ bool DoInstall(CommandLine &CmdL)
 
    std::map<unsigned short, APT::VersionSet> verset;
    std::set<std::string> UnknownPackages;
+   APT::PackageVector HeldBackPackages;
 
-   if (!DoCacheManipulationFromCommandLine(CmdL, VolatileCmdL, Cache, verset, 0, UnknownPackages))
+   if (not DoCacheManipulationFromCommandLine(CmdL, VolatileCmdL, Cache, verset, 0, UnknownPackages, HeldBackPackages))
    {
       RunJsonHook("AptCli::Hooks::Install", "org.debian.apt.hooks.install.fail", CmdL.FileList, Cache, UnknownPackages);
       return false;
@@ -949,9 +973,9 @@ bool DoInstall(CommandLine &CmdL)
    // See if we need to prompt
    // FIXME: check if really the packages in the set are going to be installed
    if (Cache->InstCount() == verset[MOD_INSTALL].size() && Cache->DelCount() == 0)
-      result = InstallPackages(Cache, false, false, true, "AptCli::Hooks::Install", CmdL);
+      result = InstallPackages(Cache, HeldBackPackages, false, false, true, "AptCli::Hooks::Install", CmdL);
    else
-      result = InstallPackages(Cache, false, true, true, "AptCli::Hooks::Install", CmdL);
+      result = InstallPackages(Cache, HeldBackPackages, false, true, true, "AptCli::Hooks::Install", CmdL);
 
    if (result)
       result = RunJsonHook("AptCli::Hooks::Install", "org.debian.apt.hooks.install.post", CmdL.FileList, Cache);
diff --git a/apt-private/private-install.h b/apt-private/private-install.h
index 52f055963..20b585d15 100644
--- a/apt-private/private-install.h
+++ b/apt-private/private-install.h
@@ -1,6 +1,7 @@
 #ifndef APT_PRIVATE_INSTALL_H
 #define APT_PRIVATE_INSTALL_H
 
+#include <apt-pkg/depcache.h>
 #include <apt-pkg/cachefile.h>
 #include <apt-pkg/cacheset.h>
 #include <apt-pkg/configuration.h>
@@ -32,11 +33,14 @@ bool AddVolatileBinaryFile(pkgSourceList *const SL, PseudoPkg &&pkg, std::vector
 bool AddVolatileSourceFile(pkgSourceList *const SL, PseudoPkg &&pkg, std::vector<PseudoPkg> &VolatileCmdL);
 
 bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg> &VolatileCmdL, CacheFile &Cache,
-					std::map<unsigned short, APT::VersionSet> &verset, int UpgradeMode, std::set<std::string> &UnknownPackages);
-bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg> &VolatileCmdL, CacheFile &Cache, int UpgradeMode);
-bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, CacheFile &Cache, int UpgradeMode);
+					std::map<unsigned short, APT::VersionSet> &verset, int UpgradeMode,
+					std::set<std::string> &UnknownPackages, APT::PackageVector &HeldBackPackages);
+bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg> &VolatileCmdL, CacheFile &Cache, int UpgradeMode,
+					APT::PackageVector &HeldBackPackages);
 
-APT_PUBLIC bool InstallPackages(CacheFile &Cache, bool ShwKept, bool Ask = true,
+APT_PUBLIC bool InstallPackages(CacheFile &Cache,
+				APT::PackageVector &HeldBackPackages,
+				bool ShwKept, bool Ask = true,
 				bool Safety = true,
 				std::string const &Hook = "",
 				CommandLine const &CmdL = {});
diff --git a/apt-private/private-output.cc b/apt-private/private-output.cc
index eb9a34abe..d07ecc0ce 100644
--- a/apt-private/private-output.cc
+++ b/apt-private/private-output.cc
@@ -491,17 +491,11 @@ void ShowDel(ostream &out,CacheFile &Cache)
 }
 									/*}}}*/
 // ShowKept - Show kept packages					/*{{{*/
-void ShowKept(ostream &out,CacheFile &Cache)
+void ShowKept(ostream &out,CacheFile &Cache, APT::PackageVector const &HeldBackPackages)
 {
    SortedPackageUniverse Universe(Cache);
-   ShowList(out,_("The following packages have been kept back:"), Universe,
-	 [&Cache](pkgCache::PkgIterator const &Pkg)
-	 {
-	    return Cache[Pkg].Upgrade() == false &&
-		   Cache[Pkg].Upgradable() == true &&
-		   Pkg->CurrentVer != 0 &&
-		   Cache[Pkg].Delete() == false;
-	 },
+   ShowList(out,_("The following packages have been kept back:"), HeldBackPackages,
+	 &AlwaysTrue,
 	 &PrettyFullName,
 	 CurrentToCandidateVersion(&Cache));
 }
@@ -623,7 +617,7 @@ bool ShowEssential(ostream &out,CacheFile &Cache)
 // Stats - Show some statistics						/*{{{*/
 // ---------------------------------------------------------------------
 /* */
-void Stats(ostream &out,pkgDepCache &Dep)
+void Stats(ostream &out, pkgDepCache &Dep, APT::PackageVector const &HeldBackPackages)
 {
    unsigned long Upgrade = 0;
    unsigned long Downgrade = 0;
@@ -655,7 +649,7 @@ void Stats(ostream &out,pkgDepCache &Dep)
       ioprintf(out,_("%lu downgraded, "),Downgrade);
 
    ioprintf(out,_("%lu to remove and %lu not upgraded.\n"),
-	    Dep.DelCount(),Dep.KeepCount());
+	    Dep.DelCount(), HeldBackPackages.size());
    
    if (Dep.BadCount() != 0)
       ioprintf(out,_("%lu not fully installed or removed.\n"),
@@ -784,7 +778,15 @@ std::function<std::string(pkgCache::PkgIterator const &)> CandidateVersion(pkgCa
 }
 std::string CurrentToCandidateVersion(pkgCacheFile * const Cache, pkgCache::PkgIterator const &Pkg)
 {
-   return std::string((*Cache)[Pkg].CurVersion) + " => " + (*Cache)[Pkg].CandVersion;
+   std::string const CurVer = (*Cache)[Pkg].CurVersion;
+   std::string CandVer = (*Cache)[Pkg].CandVersion;
+   if (CurVer == CandVer)
+   {
+      auto const CandVerIter = Cache->GetPolicy()->GetCandidateVer(Pkg);
+      if (not CandVerIter.end())
+	 CandVer = CandVerIter.VerStr();
+   }
+   return  CurVer + " => " + CandVer;
 }
 std::function<std::string(pkgCache::PkgIterator const &)> CurrentToCandidateVersion(pkgCacheFile * const Cache)
 {
@@ -798,4 +800,3 @@ std::string EmptyString(pkgCache::PkgIterator const &)
 {
    return std::string();
 }
-
diff --git a/apt-private/private-output.h b/apt-private/private-output.h
index c20cc9e17..0e06bf072 100644
--- a/apt-private/private-output.h
+++ b/apt-private/private-output.h
@@ -1,6 +1,7 @@
 #ifndef APT_PRIVATE_OUTPUT_H
 #define APT_PRIVATE_OUTPUT_H
 
+#include <apt-pkg/cacheset.h>
 #include <apt-pkg/configuration.h>
 #include <apt-pkg/macros.h>
 #include <apt-pkg/pkgcache.h>
@@ -91,14 +92,14 @@ template<class Container, class PredicateC, class DisplayP, class DisplayV> bool
 
 void ShowNew(std::ostream &out,CacheFile &Cache);
 void ShowDel(std::ostream &out,CacheFile &Cache);
-void ShowKept(std::ostream &out,CacheFile &Cache);
+void ShowKept(std::ostream &out,CacheFile &Cache, APT::PackageVector const &HeldBackPackages);
 void ShowUpgraded(std::ostream &out,CacheFile &Cache);
 bool ShowDowngraded(std::ostream &out,CacheFile &Cache);
 bool ShowHold(std::ostream &out,CacheFile &Cache);
 
 bool ShowEssential(std::ostream &out,CacheFile &Cache);
 
-void Stats(std::ostream &out, pkgDepCache &Dep);
+void Stats(std::ostream &out, pkgDepCache &Dep, APT::PackageVector const &HeldBackPackages);
 
 // prompting
 APT_PUBLIC bool YnPrompt(char const *const Question, bool Default = true);
diff --git a/apt-private/private-source.cc b/apt-private/private-source.cc
index 9b47ce31f..125cb1591 100644
--- a/apt-private/private-source.cc
+++ b/apt-private/private-source.cc
@@ -818,6 +818,7 @@ bool DoBuildDep(CommandLine &CmdL)
       return false;
    pkgProblemResolver Fix(Cache.GetDepCache());
 
+   APT::PackageSet UpgradablePackages;
    APT::PackageVector removeAgain;
    {
       pkgDepCache::ActionGroup group(Cache);
@@ -843,6 +844,11 @@ bool DoBuildDep(CommandLine &CmdL)
 	 InstallAction(Cache[Pkg].CandidateVerIter(Cache));
 	 removeAgain.push_back(Pkg);
       }
+
+      {
+	 APT::CacheSetHelper helper;
+	 helper.PackageFrom(APT::CacheSetHelper::PATTERN, &UpgradablePackages, Cache, "?upgradable");
+      }
       InstallAction.doAutoInstall();
 
       OpTextProgress Progress(*_config);
@@ -883,8 +889,15 @@ bool DoBuildDep(CommandLine &CmdL)
 	 Cache->MarkDelete(pkg, false, 0, true);
    }
 
+   APT::PackageVector HeldBackPackages;
+   SortedPackageUniverse Universe(Cache);
+   for (auto const &Pkg: Universe)
+      if (Pkg->CurrentVer != 0 && not Cache[Pkg].Upgrade() && not Cache[Pkg].Delete() &&
+	  UpgradablePackages.find(Pkg) != UpgradablePackages.end())
+	 HeldBackPackages.push_back(Pkg);
+
    pseudoPkgs.clear();
-   if (_error->PendingError() || InstallPackages(Cache, false, true) == false)
+   if (_error->PendingError() || not InstallPackages(Cache, HeldBackPackages, false, true))
       return _error->Error(_("Failed to process build dependencies"));
    return true;
 }
diff --git a/apt-private/private-upgrade.cc b/apt-private/private-upgrade.cc
index c41e4d2f3..3423db525 100644
--- a/apt-private/private-upgrade.cc
+++ b/apt-private/private-upgrade.cc
@@ -2,6 +2,7 @@
 #include <config.h>
 
 #include <apt-pkg/cmndline.h>
+#include <apt-pkg/cacheset.h>
 #include <apt-pkg/configuration.h>
 #include <apt-pkg/error.h>
 #include <apt-pkg/upgrade.h>
@@ -28,13 +29,14 @@ static bool UpgradeHelper(CommandLine &CmdL, int UpgradeFlags)
 
    std::map<unsigned short, APT::VersionSet> verset;
    std::set<std::string> UnknownPackages;
-   if (!DoCacheManipulationFromCommandLine(CmdL, VolatileCmdL, Cache, verset, UpgradeFlags, UnknownPackages))
+   APT::PackageVector HeldBackPackages;
+   if (not DoCacheManipulationFromCommandLine(CmdL, VolatileCmdL, Cache, verset, UpgradeFlags, UnknownPackages, HeldBackPackages))
    {
       RunJsonHook("AptCli::Hooks::Upgrade", "org.debian.apt.hooks.install.fail", CmdL.FileList, Cache, UnknownPackages);
       return false;
    }
    RunJsonHook("AptCli::Hooks::Upgrade", "org.debian.apt.hooks.install.pre-prompt", CmdL.FileList, Cache);
-   if (InstallPackages(Cache, true, true, true, "AptCli::Hooks::Upgrade", CmdL))
+   if (InstallPackages(Cache, HeldBackPackages, true, true, true, "AptCli::Hooks::Upgrade", CmdL))
       return RunJsonHook("AptCli::Hooks::Upgrade", "org.debian.apt.hooks.install.post", CmdL.FileList, Cache);
    else
       return RunJsonHook("AptCli::Hooks::Upgrade", "org.debian.apt.hooks.install.fail", CmdL.FileList, Cache);
diff --git a/cmdline/apt-get.cc b/cmdline/apt-get.cc
index efb5cfd73..010021991 100644
--- a/cmdline/apt-get.cc
+++ b/cmdline/apt-get.cc
@@ -206,8 +206,13 @@ static bool DoDSelectUpgrade(CommandLine &)
       ShowBroken(c1out,Cache,false);
       return _error->Error(_("Internal error, problem resolver broke stuff"));
    }
-   
-   return InstallPackages(Cache,false);
+
+   APT::PackageVector HeldBackPackages;
+   for (pkgCache::PkgIterator Pkg = Cache->PkgBegin(); not Pkg.end(); ++Pkg)
+      if (Pkg->CurrentVer != 0 && Cache[Pkg].Upgradable() && not Cache[Pkg].Upgrade() && not Cache[Pkg].Delete())
+	 HeldBackPackages.push_back(Pkg);
+
+   return InstallPackages(Cache, HeldBackPackages, false);
 }
 									/*}}}*/
 // DoCheck - Perform the check operation				/*{{{*/
diff --git a/test/integration/test-explore-or-groups-in-markinstall b/test/integration/test-explore-or-groups-in-markinstall
index ba3376cf6..b88105b6b 100755
--- a/test/integration/test-explore-or-groups-in-markinstall
+++ b/test/integration/test-explore-or-groups-in-markinstall
@@ -70,7 +70,6 @@ The following additional packages will be installed:
 The following NEW packages will be installed:
   foo-${1}-level${level} okay
 0 upgraded, 2 newly installed, 0 to remove and 3 not upgraded." apt install foo-${1}-level${level} -s
-		if [ "$level" = '0' ]; then NOT=2; else NOT=1; fi
 		testsuccessheadequal 9 "Reading package lists...
 Building dependency tree...
 The following additional packages will be installed:
@@ -79,7 +78,7 @@ The following NEW packages will be installed:
   foo-${1}-upgrade-level${level}
 The following packages will be upgraded:
   upgrade
-1 upgraded, 1 newly installed, 0 to remove and $NOT not upgraded." apt install foo-${1}-upgrade-level${level} -s
+1 upgraded, 1 newly installed, 0 to remove and 2 not upgraded." apt install foo-${1}-upgrade-level${level} -s
 	done
 
 	testsuccessheadequal 7 "Reading package lists...
@@ -93,6 +92,22 @@ The following NEW packages will be installed:
 checkfoos 'd' 'Depends'
 checkfoos 'r' 'Recommends'
 
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following NEW packages will be installed:
+   foo-d-upgrade-level2 (1)
+The following packages have been kept back:
+   bad-upgrade-level0 (1 => 2)
+   bad-upgrade-level1 (1 => 2)
+The following packages will be upgraded:
+   upgrade (1 => 2)
+1 upgraded, 1 newly installed, 0 to remove and 2 not upgraded.
+Inst upgrade [1] (2 unstable [all])
+Inst foo-d-upgrade-level2 (1 unstable [all])
+Conf upgrade (2 unstable [all])
+Conf foo-d-upgrade-level2 (1 unstable [all])' apt full-upgrade foo-d-upgrade-level2 -sV
+
 TEST_WITH_APTITUDE=false
 msgtest 'Check if aptitude is available for additional tests'
 if dpkg-checkbuilddeps -d 'aptitude' /dev/null >/dev/null 2>&1; then