Merging upstream version 2.9.3.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

39 files changed, 1770 insertions, 199 deletions

diff --git a/CMake/vendor_substitute.cmake b/CMake/vendor_substitute.cmake
index 71449c9..277cb3a 100644
--- a/CMake/vendor_substitute.cmake
+++ b/CMake/vendor_substitute.cmake
@@ -2,7 +2,8 @@ file(READ ${IN} input)
 foreach(variable ${VARS})
     execute_process(COMMAND ${PROJECT_SOURCE_DIR}/vendor/getinfo
                             --vendor ${CURRENT_VENDOR} ${variable}
-                    OUTPUT_VARIABLE value OUTPUT_STRIP_TRAILING_WHITESPACE)
+                    OUTPUT_VARIABLE value OUTPUT_STRIP_TRAILING_WHITESPACE
+                    COMMAND_ERROR_IS_FATAL ANY)
     string(REPLACE "&${variable};" "${value}" input "${input}")
 endforeach()
 file(WRITE ${OUT} "${input}")
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 00ba2e4..6b29984 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -206,22 +206,25 @@ endif()
 # Configure some variables like package, version and architecture.
 set(PACKAGE ${PROJECT_NAME})
 set(PACKAGE_MAIL "APT Development Team <deity@lists.debian.org>")
-set(PACKAGE_VERSION "2.9.2")
+set(PACKAGE_VERSION "2.9.3")
 string(REGEX MATCH "^[0-9.]+" PROJECT_VERSION ${PACKAGE_VERSION})
 
 if (NOT DEFINED DPKG_DATADIR)
   execute_process(COMMAND ${PERL_EXECUTABLE} -MDpkg -e "print $Dpkg::DATADIR;"
-                  OUTPUT_VARIABLE DPKG_DATADIR_CMD OUTPUT_STRIP_TRAILING_WHITESPACE)
+                  OUTPUT_VARIABLE DPKG_DATADIR_CMD OUTPUT_STRIP_TRAILING_WHITESPACE
+                  COMMAND_ERROR_IS_FATAL ANY)
   message(STATUS "Found dpkg data dir: ${DPKG_DATADIR_CMD}")
   set(DPKG_DATADIR "${DPKG_DATADIR_CMD}" CACHE PATH "dpkg data directory")
 endif()
 if (NOT DEFINED COMMON_ARCH)
   execute_process(COMMAND dpkg-architecture -qDEB_HOST_ARCH
-                  OUTPUT_VARIABLE COMMON_ARCH OUTPUT_STRIP_TRAILING_WHITESPACE)
+                  OUTPUT_VARIABLE COMMON_ARCH OUTPUT_STRIP_TRAILING_WHITESPACE
+                  COMMAND_ERROR_IS_FATAL ANY)
 endif()
 if (NOT DEFINED ROOT_GROUP)
   execute_process(COMMAND id -gn root
-                  OUTPUT_VARIABLE ROOT_GROUP OUTPUT_STRIP_TRAILING_WHITESPACE)
+                  OUTPUT_VARIABLE ROOT_GROUP OUTPUT_STRIP_TRAILING_WHITESPACE
+                  COMMAND_ERROR_IS_FATAL ANY)
   message(STATUS "Found root group: ${ROOT_GROUP}")
 endif()
 set(ROOT_GROUP "${ROOT_GROUP}" CACHE STRING "Group of root (e.g.: wheel or root)")
diff --git a/apt-pkg/CMakeLists.txt b/apt-pkg/CMakeLists.txt
index d13aed9..63052fa 100644
--- a/apt-pkg/CMakeLists.txt
+++ b/apt-pkg/CMakeLists.txt
@@ -3,7 +3,8 @@ include_directories(${PROJECT_BINARY_DIR}/include/apt-pkg)
 
 file(MAKE_DIRECTORY ${PROJECT_BINARY_DIR}/include/apt-pkg/)
 execute_process(COMMAND grep -v "^#" "${CMAKE_CURRENT_SOURCE_DIR}/tagfile-keys.list"
-		OUTPUT_FILE "${CMAKE_CURRENT_BINARY_DIR}/tagfile-keys.clean.list")
+		OUTPUT_FILE "${CMAKE_CURRENT_BINARY_DIR}/tagfile-keys.clean.list"
+		COMMAND_ERROR_IS_FATAL ANY)
 execute_process(COMMAND ${TRIEHASH_EXECUTABLE}
                         --ignore-case
                          --header ${PROJECT_BINARY_DIR}/include/apt-pkg/tagfile-keys.h
@@ -13,7 +14,8 @@ execute_process(COMMAND ${TRIEHASH_EXECUTABLE}
                          --function-name pkgTagHash
                          --include "<apt-pkg/tagfile.h>"
                          --include "<apt-pkg/header-is-private.h>"
-                         "${CMAKE_CURRENT_BINARY_DIR}/tagfile-keys.clean.list")
+                         "${CMAKE_CURRENT_BINARY_DIR}/tagfile-keys.clean.list"
+                COMMAND_ERROR_IS_FATAL ANY)
 set_property(DIRECTORY APPEND PROPERTY CMAKE_CONFIGURE_DEPENDS "tagfile-keys.list")
 set_source_files_properties("${CMAKE_CURRENT_BINARY_DIR}/tagfile-keys.cc" PROPERTIES COMPILE_DEFINITIONS APT_COMPILING_APT)
 
@@ -22,11 +24,13 @@ set_source_files_properties("${CMAKE_CURRENT_BINARY_DIR}/tagfile-keys.cc" PROPER
 execute_process(COMMAND awk -v ORS=. "/^\#define APT_PKG_M/ {print \$3}"
                 COMMAND sed "s/\\.\$//"
                 INPUT_FILE ${CMAKE_CURRENT_SOURCE_DIR}/contrib/macros.h
-                OUTPUT_VARIABLE MAJOR OUTPUT_STRIP_TRAILING_WHITESPACE)
+                OUTPUT_VARIABLE MAJOR OUTPUT_STRIP_TRAILING_WHITESPACE
+                COMMAND_ERROR_IS_FATAL ANY)
 execute_process(COMMAND grep "^#define APT_PKG_RELEASE"
                 COMMAND cut -d " " -f 3
                 INPUT_FILE ${CMAKE_CURRENT_SOURCE_DIR}/contrib/macros.h
-                OUTPUT_VARIABLE MINOR OUTPUT_STRIP_TRAILING_WHITESPACE)
+                OUTPUT_VARIABLE MINOR OUTPUT_STRIP_TRAILING_WHITESPACE
+                COMMAND_ERROR_IS_FATAL ANY)
 
 message(STATUS "Building libapt-pkg ${MAJOR} (release ${MINOR})")
 set(APT_PKG_MAJOR ${MAJOR} PARENT_SCOPE) # exporting for methods/CMakeLists.txt
diff --git a/apt-pkg/contrib/error.cc b/apt-pkg/contrib/error.cc
index 83e90a0..054435b 100644
--- a/apt-pkg/contrib/error.cc
+++ b/apt-pkg/contrib/error.cc
@@ -315,12 +315,14 @@ APT_HIDDEN std::ostream &operator<<(std::ostream &out, GlobalError::Item i)
       case GlobalError::FATAL:
       case GlobalError::ERROR:
       case GlobalError::WARNING:
-      case GlobalError::NOTICE:
-      case GlobalError::AUDIT:
 	 out << COLOR_RESET;
 	 if (out_ver >= 30)
 	    out << COLOR_BOLD;
 	 break;
+      case GlobalError::NOTICE:
+      case GlobalError::AUDIT:
+	 out << COLOR_RESET;
+	 break;
       default:
 	 break;
       }
diff --git a/apt-pkg/deb/deblistparser.cc b/apt-pkg/deb/deblistparser.cc
index 071189b..9177d54 100644
--- a/apt-pkg/deb/deblistparser.cc
+++ b/apt-pkg/deb/deblistparser.cc
@@ -887,7 +887,7 @@ bool debListParser::ParseProvides(pkgCache::VerIterator &Ver)
    bool const barbarianArch = not APT::Configuration::checkArchitecture(Arch);
    const char *Start;
    const char *Stop;
-   if (Section.Find(pkgTagSection::Key::Provides,Start,Stop) == true)
+   if (Section.Find(pkgTagSection::Key::Provides,Start,Stop) && Start != Stop)
    {
       StringView Package;
       StringView Version;
diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index 76a5c09..72cbf8d 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -1463,7 +1463,7 @@ static bool MarkInstall_RemoveConflictsIfNotUpgradeable(pkgDepCache &Cache, bool
    return not failedToRemoveSomething;
 }
 									/*}}}*/
-static bool MarkInstall_CollectReverseDepends(pkgDepCache &Cache, bool const DebugAutoInstall, pkgCache::VerIterator const &PV, unsigned long Depth, APT::PackageVector &toUpgrade) /*{{{*/
+static bool MarkInstall_CollectReverseDepends(pkgDepCache &Cache, bool const DebugAutoInstall, pkgCache::VerIterator const &PV, unsigned long Depth, APT::PackageVector &toUpgrade, APT::PackageVector const &delayedRemove) /*{{{*/
 {
    auto CurrentVer = PV.ParentPkg().CurrentVer();
    if (CurrentVer.end())
@@ -1474,6 +1474,9 @@ static bool MarkInstall_CollectReverseDepends(pkgDepCache &Cache, bool const Deb
       // Skip non-installed versions and packages already marked for upgrade
       if (ParentPkg.CurrentVer() != D.ParentVer() || Cache[ParentPkg].Install())
 	 continue;
+      // Skip rev-depends we already tagged for removal
+      if (Cache[ParentPkg].Delete() || std::find(delayedRemove.begin(), delayedRemove.end(), ParentPkg) != delayedRemove.end())
+	 continue;
       // We only handle important positive dependencies, RemoveConflictsIfNotUpgradeable handles negative
       if (not Cache.IsImportantDep(D) || D.IsNegative())
 	 continue;
@@ -1722,7 +1725,7 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg, bool AutoInst,
 	    return false;
 	 hasFailed = true;
       }
-      if (not MarkInstall_CollectReverseDepends(*this, DebugAutoInstall, PV, Depth, toUpgrade))
+      if (not MarkInstall_CollectReverseDepends(*this, DebugAutoInstall, PV, Depth, toUpgrade, delayedRemove))
       {
 	 if (failEarly)
 	    return false;
diff --git a/apt-pkg/edsp.cc b/apt-pkg/edsp.cc
index a02e400..5894008 100644
--- a/apt-pkg/edsp.cc
+++ b/apt-pkg/edsp.cc
@@ -19,6 +19,7 @@
 #include <apt-pkg/pkgsystem.h>
 #include <apt-pkg/prettyprinters.h>
 #include <apt-pkg/progress.h>
+#include <apt-pkg/solver3.h>
 #include <apt-pkg/string_view.h>
 #include <apt-pkg/strutl.h>
 #include <apt-pkg/tagfile.h>
@@ -765,6 +766,18 @@ static bool CreateDumpFile(char const * const id, char const * const type, FileF
 // EDSP::ResolveExternal - resolve problems by asking external for help	{{{*/
 bool EDSP::ResolveExternal(const char* const solver, pkgDepCache &Cache,
 			 unsigned int const flags, OpProgress *Progress) {
+   if (strcmp(solver, "3.0") == 0)
+   {
+      APT::Solver s(Cache.GetCache(), Cache.GetPolicy());
+      FileFd output;
+      if (not s.FromDepCache(Cache))
+	 return false;
+      if (not s.Solve())
+	 return false;
+      if (not s.ToDepCache(Cache))
+	 return false;
+      return true;
+   }
 	if (strcmp(solver, "internal") == 0)
 	{
 		FileFd output;
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
new file mode 100644
index 0000000..d43bd5b
--- /dev/null
+++ b/apt-pkg/solver3.cc
@@ -0,0 +1,960 @@
+/*
+ * solver3.cc - The APT 3.0 solver
+ *
+ * Copyright (c) 2023 Julian Andres Klode
+ * Copyright (c) 2023 Canonical Ltd
+ *
+ * SPDX-License-Identifier: GPL-2.0+
+ */
+
+#define APT_COMPILING_APT
+
+#include <config.h>
+
+#include <apt-pkg/algorithms.h>
+#include <apt-pkg/aptconfiguration.h>
+#include <apt-pkg/cachefilter.h>
+#include <apt-pkg/cacheset.h>
+#include <apt-pkg/error.h>
+#include <apt-pkg/macros.h>
+#include <apt-pkg/pkgsystem.h>
+#include <apt-pkg/solver3.h>
+#include <apt-pkg/version.h>
+
+#include <algorithm>
+#include <cassert>
+#include <sstream>
+
+// FIXME: Helpers stolen from DepCache, please give them back.
+struct CompareProviders3 /*{{{*/
+{
+   pkgCache &Cache;
+   pkgDepCache::Policy &Policy;
+   pkgCache::PkgIterator const Pkg;
+   bool upgrade{_config->FindB("APT::Solver::Upgrade", false)};
+
+   bool operator()(pkgCache::Version *AV, pkgCache::Version *BV)
+   {
+      return (*this)(pkgCache::VerIterator(Cache, AV), pkgCache::VerIterator(Cache, BV));
+   }
+   bool operator()(pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV)
+   {
+      pkgCache::PkgIterator const A = AV.ParentPkg();
+      pkgCache::PkgIterator const B = BV.ParentPkg();
+      // Compare versions for the same package. FIXME: Move this to the real implementation
+      if (A == B)
+      {
+	 if (AV == BV)
+	    return false;
+	 if (not upgrade && A->CurrentVer != 0 && A.CurrentVer() == AV)
+	    return true;
+	 if (Policy.GetPriority(AV) < Policy.GetPriority(BV))
+	    return false;
+
+	 return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0;
+      }
+      // Prefer MA:same packages if other architectures for it are installed
+      if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same ||
+	  (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
+      {
+	 bool instA = false;
+	 if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
+	 {
+	    pkgCache::GrpIterator Grp = A.Group();
+	    for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
+	       if (P->CurrentVer != 0)
+	       {
+		  instA = true;
+		  break;
+	       }
+	 }
+	 bool instB = false;
+	 if ((BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
+	 {
+	    pkgCache::GrpIterator Grp = B.Group();
+	    for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
+	    {
+	       if (P->CurrentVer != 0)
+	       {
+		  instB = true;
+		  break;
+	       }
+	    }
+	 }
+	 if (instA != instB)
+	    return instA;
+      }
+      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)
+      {
+	 if (A->Group == Pkg->Group && B->Group != Pkg->Group)
+	    return true;
+	 else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
+	    return false;
+      }
+      // we like essentials
+      if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
+      {
+	 if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+	    return true;
+	 else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+	    return false;
+      }
+      if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important))
+      {
+	 if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
+	    return true;
+	 else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
+	    return false;
+      }
+      // prefer native architecture
+      if (strcmp(A.Arch(), B.Arch()) != 0)
+      {
+	 if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
+	    return true;
+	 else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
+	    return false;
+	 std::vector<std::string> archs = APT::Configuration::getArchitectures();
+	 for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
+	    if (*a == A.Arch())
+	       return true;
+	    else if (*a == B.Arch())
+	       return false;
+      }
+      // higher priority seems like a good idea
+      if (AV->Priority != BV->Priority)
+	 return AV->Priority < BV->Priority;
+      if (auto NameCmp = strcmp(A.Name(), B.Name()))
+	 return NameCmp < 0;
+      // unable to decide…
+      return A->ID > B->ID;
+   }
+};
+
+/** \brief Returns \b true for packages matching a regular
+ *  expression in APT::NeverAutoRemove.
+ */
+class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc
+{
+   std::unique_ptr<APT::CacheFilter::Matcher> Kernels;
+
+   public:
+   DefaultRootSetFunc2(pkgCache *cache) : Kernels(APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(cache)){};
+   virtual ~DefaultRootSetFunc2(){};
+
+   bool InRootSet(const pkgCache::PkgIterator &pkg) APT_OVERRIDE { return pkg.end() == false && ((*Kernels)(pkg) || DefaultRootSetFunc::InRootSet(pkg)); };
+}; // FIXME: DEDUP with pkgDepCache.
+/*}}}*/
+
+APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy)
+    : cache(cache),
+      policy(policy),
+      pkgStates{cache.Head().PackageCount},
+      verStates{cache.Head().VersionCount}
+{
+   static_assert(sizeof(APT::Solver::State<pkgCache::PkgIterator>) == 3 * sizeof(int));
+   static_assert(sizeof(APT::Solver::State<pkgCache::VerIterator>) == 3 * sizeof(int));
+   static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer<pkgCache::Package>));
+   static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer<pkgCache::Version>));
+}
+
+// This function determines if a work item is less important than another.
+bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
+{
+   if (optional && b.optional && reason.empty() && b.reason.empty() && upgrade != b.upgrade)
+   {
+      // Assuming we have libfoo-dev=5.1 Depends libfoo5.1-dev upgrade to libfoo-dev=5.3 Depends libfoo5.3-dev,
+      // We schedule libfoo-dev=5.3|libfoo-dev=5.1, libfoo5.1-dev. The latter would be resolved first, resulting
+      // in libfoo-dev being kept back.
+      //
+      // However, if we schedule not libfoo5.1-dev but bar Recommends libfoo5.1-dev, we should not be breaking that
+      // Recommends, hence we need to ensure that if we order an upgrade before an optional package that this optional
+      // package was a top level package, i.e. b.reason is empty (or our reason in the reverse case).
+      //
+      // So if we are the upgrade, and b also Depends on one of our versions, we need to satisfy b after we
+      // have scheduled the upgrade.
+      if (upgrade)
+	 return std::any_of(b.solutions.begin(), b.solutions.end(), [this](auto bsol) -> bool
+			    { return std::find(solutions.begin(), solutions.end(), bsol) != solutions.end(); });
+      else
+	 return std::any_of(solutions.begin(), solutions.end(), [b](auto sol) -> bool
+			    { return std::find(b.solutions.begin(), b.solutions.end(), sol) != b.solutions.end(); });
+   }
+   // An optional item is less important than a required one.
+   if (optional != b.optional)
+      return optional;
+   // More solutions to explore are more expensive.
+   if (size != b.size)
+      return size > b.size;
+   // We enqueue common dependencies at the package level to avoid choosing versions, so let's solve package items first,
+   // this improves the implication graph as it now tells you that common dependencies were installed by the package.
+   if (reason.Pkg() != b.reason.Pkg())
+      return reason.Pkg() == 0;
+
+   return false;
+}
+
+void APT::Solver::Work::Dump(pkgCache &cache)
+{
+   if (dirty)
+      std::cerr << "Dirty ";
+   if (optional)
+      std::cerr << "Optional ";
+   std::cerr << "Item (" << size << "@" << depth << (upgrade ? "u" : "") << ") ";
+   if (auto Pkg = reason.Pkg(); Pkg != 0)
+      std::cerr << pkgCache::PkgIterator(cache, cache.PkgP + Pkg).FullName();
+   if (auto Ver = reason.Ver(); Ver != 0)
+      std::cerr << pkgCache::VerIterator(cache, cache.VerP + Ver).ParentPkg().FullName() << "=" << pkgCache::VerIterator(cache, cache.VerP + Ver).VerStr();
+   std::cerr << " -> ";
+   for (auto sol : solutions)
+   {
+      auto Ver = pkgCache::VerIterator(cache, sol);
+      std::cerr << " | " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr();
+   }
+}
+
+// Prints an implication graph part of the form A -> B -> C, possibly with "not"
+std::string APT::Solver::WhyStr(Reason reason)
+{
+   std::vector<std::string> out;
+
+   while (not reason.empty())
+   {
+      if (auto Pkg = pkgCache::PkgIterator(cache, cache.PkgP + reason.Pkg()); not Pkg.end())
+      {
+	 if ((*this)[Pkg].decision == Decision::MUSTNOT)
+	    out.push_back(std::string("not ") + Pkg.FullName());
+	 else
+	    out.push_back(Pkg.FullName());
+	 reason = (*this)[Pkg].reason;
+      }
+      if (auto Ver = pkgCache::VerIterator(cache, cache.VerP + reason.Ver()); not Ver.end())
+      {
+	 if ((*this)[Ver].decision == Decision::MUSTNOT)
+	    out.push_back(std::string("not ") + Ver.ParentPkg().FullName() + "=" + Ver.VerStr());
+	 else
+	    out.push_back(Ver.ParentPkg().FullName() + "=" + Ver.VerStr());
+	 reason = (*this)[Ver].reason;
+      }
+   }
+
+   std::string outstr;
+   for (auto I = out.rbegin(); I != out.rend(); ++I)
+   {
+      outstr += (outstr.size() == 0 ? "" : " -> ") + *I;
+   }
+   return outstr;
+}
+
+bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason)
+{
+   if ((*this)[Pkg].decision == Decision::MUST)
+      return true;
+
+   // Check conflicting selections
+   if ((*this)[Pkg].decision == Decision::MUSTNOT)
+      return _error->Error("Conflict: %s -> %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(Pkg)).c_str());
+
+   bool anyInstallable = false;
+   for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+      if ((*this)[ver].decision != Decision::MUSTNOT)
+	 anyInstallable = true;
+
+   if (not anyInstallable)
+   {
+      _error->Error("Conflict: %s -> %s but no versions are installable",
+		    WhyStr(reason).c_str(), Pkg.FullName().c_str());
+      for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+	 _error->Error("Uninstallable version: %s", WhyStr(Reason(ver)).c_str());
+      return false;
+   }
+
+   // Note decision
+   if (unlikely(debug >= 1))
+      std::cerr << "[" << depth() << "] Install:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n";
+   (*this)[Pkg] = {reason, depth(), Decision::MUST,};
+
+   // Insert the work item.
+   Work workItem{Reason(Pkg), depth()};
+   for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+      if (IsAllowedVersion(ver))
+	 workItem.solutions.push_back(ver);
+   std::sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg});
+   assert(workItem.solutions.size() > 0);
+
+   if (workItem.solutions.size() > 1 || workItem.optional)
+      AddWork(std::move(workItem));
+   else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), workItem.reason))
+      return false;
+
+   if (not EnqueueCommonDependencies(Pkg))
+      return false;
+
+   return true;
+}
+
+bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason)
+{
+   if ((*this)[Ver].decision == Decision::MUST)
+      return true;
+
+   if (unlikely(debug >= 1))
+      assert(IsAllowedVersion(Ver));
+
+   // Check conflicting selections
+   if ((*this)[Ver].decision == Decision::MUSTNOT)
+      return _error->Error("Conflict: %s -> %s but %s",
+			   WhyStr(reason).c_str(),
+			   (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+			   WhyStr(Reason(Ver)).c_str());
+   if ((*this)[Ver.ParentPkg()].decision == Decision::MUSTNOT)
+      return _error->Error("Conflict: %s -> %s but %s",
+			   WhyStr(reason).c_str(),
+			   (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+			   WhyStr(Reason(Ver.ParentPkg())).c_str());
+   for (auto otherVer = Ver.ParentPkg().VersionList(); not otherVer.end(); otherVer++)
+      if (otherVer->ID != Ver->ID && (*this)[otherVer].decision == Decision::MUST)
+	 return _error->Error("Conflict: %s -> %s but %s",
+			      WhyStr(reason).c_str(),
+			      (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+			      WhyStr(Reason(otherVer)).c_str());
+
+   // Note decision
+   if (unlikely(debug >= 1))
+      std::cerr << "[" << depth() << "] Install:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n";
+   (*this)[Ver] = {reason, depth(), Decision::MUST,};
+   if ((*this)[Ver.ParentPkg()].decision != Decision::MUST)
+      (*this)[Ver.ParentPkg()] = {Reason(Ver), depth(), Decision::MUST,};
+
+   for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV)
+   {
+      if (OV != Ver && not Reject(OV, Reason(Ver)))
+	 return false;
+   }
+
+   for (auto dep = Ver.DependsList(); not dep.end();)
+   {
+      // Compute a single dependency element (glob or)
+      pkgCache::DepIterator start;
+      pkgCache::DepIterator end;
+      dep.GlobOr(start, end); // advances dep
+
+      if (not policy.IsImportantDep(start))
+	 continue;
+      if (not EnqueueOrGroup(start, end, Reason(Ver)))
+	 return false;
+   }
+
+   return true;
+}
+
+bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason)
+{
+   if ((*this)[Pkg].decision == Decision::MUSTNOT)
+      return true;
+
+   // Check conflicting selections
+   for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+      if ((*this)[ver].decision == Decision::MUST)
+	 return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(ver)).c_str());
+   if ((*this)[Pkg].decision == Decision::MUST)
+      return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(Pkg)).c_str());
+
+   // Reject the package and its versions.
+   if (unlikely(debug >= 1))
+      std::cerr << "[" << depth() << "] Reject:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n";
+   (*this)[Pkg] = {reason, depth(), Decision::MUSTNOT,};
+   for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+      if (not Reject(ver, Reason(Pkg)))
+	 return false;
+
+   needsRescore = true;
+
+   return true;
+}
+
+// \brief Do not install this version
+bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason)
+{
+   if ((*this)[Ver].decision == Decision::MUSTNOT)
+      return true;
+
+   // Check conflicting choices.
+   if ((*this)[Ver].decision == Decision::MUST)
+      return _error->Error("Conflict: %s -> not %s but %s",
+			   WhyStr(reason).c_str(),
+			   (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+			   WhyStr(Reason(Ver)).c_str());
+
+   // Mark the package as rejected and propagate up as needed.
+   if (unlikely(debug >= 1))
+      std::cerr << "[" << depth() << "] Reject:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n";
+   (*this)[Ver] = {reason, depth(), Decision::MUSTNOT,};
+   if (auto pkg = Ver.ParentPkg(); (*this)[pkg].decision != Decision::MUSTNOT)
+   {
+      bool anyInstallable = false;
+      for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++)
+	 if (otherVer->ID != Ver->ID && (*this)[otherVer].decision != Decision::MUSTNOT)
+	    anyInstallable = true;
+
+      if (anyInstallable)
+	 ;
+      else if ((*this)[pkg].decision == Decision::MUST) // Must install, but none available
+      {
+	 _error->Error("Conflict: %s but no versions are installable",
+		       WhyStr(Reason(pkg)).c_str());
+	 for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++)
+	    if ((*this)[otherVer].decision == Decision::MUSTNOT)
+	       _error->Error("Uninstallable version: %s", WhyStr(Reason(otherVer)).c_str());
+	 return _error->Error("Uninstallable version: %s -> not %s",
+			      WhyStr(reason).c_str(),
+			      (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str());
+      }
+      else if ((*this)[Ver.ParentPkg()].decision != Decision::MUSTNOT) // Last installable invalidated
+	 (*this)[Ver.ParentPkg()] = {Reason(Ver), depth(), Decision::MUSTNOT};
+   }
+
+   if (not RejectReverseDependencies(Ver))
+      return false;
+
+   needsRescore = true;
+
+   return true;
+}
+
+bool APT::Solver::EnqueueCommonDependencies(pkgCache::PkgIterator Pkg)
+{
+   if (not _config->FindB("APT::Solver::Enqueue-Common-Dependencies", true))
+      return false;
+   for (auto dep = Pkg.VersionList().DependsList(); not dep.end();)
+   {
+      pkgCache::DepIterator start;
+      pkgCache::DepIterator end;
+      dep.GlobOr(start, end); // advances dep
+
+      bool allHaveDep = true;
+      for (auto ver = Pkg.VersionList()++; not ver.end(); ver++)
+      {
+	 bool haveDep = false;
+	 for (auto otherDep = ver.DependsList(); not haveDep && not otherDep.end(); otherDep++)
+	    haveDep = otherDep->DependencyData == start->DependencyData;
+	 if (!haveDep)
+	    allHaveDep = haveDep;
+      }
+      if (not allHaveDep)
+	 continue;
+      if (not policy.IsImportantDep(start))
+	 continue;
+      if (not EnqueueOrGroup(start, end, Reason(Pkg)))
+	 return false;
+   }
+
+   return true;
+}
+
+bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Reason reason)
+{
+   auto TgtPkg = start.TargetPkg();
+   auto Ver = start.ParentVer();
+   auto fixPolicy = _config->FindB("APT::Get::Fix-Policy-Broken");
+
+   if (unlikely(debug >= 3))
+      std::cerr << "Found dependency critical " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << start.TargetPkg().FullName() << "\n";
+
+   Work workItem{reason, depth(), not start.IsCritical() /* optional */};
+
+   do
+   {
+      auto begin = workItem.solutions.size();
+      auto all = start.AllTargets();
+
+      for (auto tgt = all; *tgt; ++tgt)
+      {
+	 pkgCache::VerIterator tgti(cache, *tgt);
+
+	 if (start.IsNegative())
+	 {
+	    if (unlikely(debug >= 3))
+	       std::cerr << "Reject: " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n";
+	    // FIXME: We should be collecting these and marking the heap only once.
+	    if (not Reject(pkgCache::VerIterator(cache, *tgt), Reason(Ver)))
+	       return false;
+	 }
+	 else
+	 {
+	    if (unlikely(debug >= 3))
+	       std::cerr << "Adding work to  item " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n";
+	    if (IsAllowedVersion(*tgt))
+	       workItem.solutions.push_back(*tgt);
+	 }
+      }
+      delete[] all;
+
+      // If we are fixing the policy, we need to sort each alternative in an or group separately
+      // FIXME: This is not really true, though, we should fix the CompareProviders to ignore the
+      // installed state
+      if (fixPolicy)
+	 std::sort(workItem.solutions.begin() + begin, workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg});
+
+      if (start == end)
+	 break;
+      ++start;
+   } while (1);
+
+   if (not fixPolicy)
+      std::sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg});
+
+   // Figure out if the reason is installed
+   bool reasonInstalled = false;
+   if (auto p = workItem.reason.Pkg())
+      reasonInstalled = pkgCache::PkgIterator(cache, cache.PkgP + p)->CurrentVer != 0;
+   else if (auto v = workItem.reason.Ver())
+      reasonInstalled = pkgCache::VerIterator(cache, cache.VerP + v).ParentPkg()->CurrentVer != 0;
+
+   // Try to perserve satisfied Recommends. FIXME: We should check if the Recommends was there in the installed version?
+   if (workItem.optional && reasonInstalled && not fixPolicy &&
+       not std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto ver)
+		       { return pkgCache::VerIterator(cache, ver).ParentPkg()->CurrentVer != 0; }))
+   {
+      if (unlikely(debug >= 3))
+      {
+	 std::cerr << "Ignoring currently unsatisfied Recommends ";
+	 workItem.Dump(cache);
+	 std::cerr << "\n";
+      }
+      return true;
+   }
+   if (not workItem.solutions.empty())
+   {
+      // std::sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, TgtPkg});
+      if (unlikely(debug >= 3 && workItem.optional))
+      {
+	 std::cerr << "Enqueuing currently satisfied Recommends ";
+	 workItem.Dump(cache);
+	 std::cerr << "\n";
+      }
+      if (workItem.optional || workItem.solutions.size() > 1)
+	 AddWork(std::move(workItem));
+      else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), reason))
+	 return false;
+   }
+   else if (start.IsCritical() && not start.IsNegative())
+   {
+      return _error->Error("Unsatisfiable dependency group %s=%s -> %s", Ver.ParentPkg().FullName().c_str(), Ver.VerStr(), TgtPkg.FullName().c_str());
+   }
+   return true;
+}
+
+// \brief Find the or group containing the given dependency.
+static void FindOrGroup(pkgCache::DepIterator const &D, pkgCache::DepIterator &start, pkgCache::DepIterator &end)
+{
+   for (auto dep = D.ParentVer().DependsList(); not dep.end();)
+   {
+      dep.GlobOr(start, end); // advances dep
+
+      for (auto member = start;;)
+      {
+	 if (member == D)
+	    return;
+	 if (member == end)
+	    break;
+	 member++;
+      }
+   }
+
+   _error->Fatal("Found a dependency that does not exist in its parent version");
+   abort();
+}
+
+// This is the opposite of EnqueueOrDependencies, it rejects the reverse dependencies of the
+// given version iterator.
+bool APT::Solver::RejectReverseDependencies(pkgCache::VerIterator Ver)
+{
+   // This checks whether an or group is still satisfiable.
+   auto stillPossible = [this](pkgCache::DepIterator start, pkgCache::DepIterator end)
+   {
+      while (1)
+      {
+	 std::unique_ptr<pkgCache::Version *[]> Ts{start.AllTargets()};
+	 for (size_t i = 0; Ts[i] != nullptr; ++i)
+	    if ((*this)[Ts[i]].decision != Decision::MUSTNOT)
+	       return true;
+
+	 if (start == end)
+	    return false;
+
+	 start++;
+      }
+   };
+
+   for (auto RD = Ver.ParentPkg().RevDependsList(); not RD.end(); ++RD)
+   {
+      auto RDV = RD.ParentVer();
+      if (RD.IsNegative() || not RD.IsCritical() || not RD.IsSatisfied(Ver))
+	 continue;
+
+      if ((*this)[RDV].decision == Decision::MUSTNOT)
+	 continue;
+
+      pkgCache::DepIterator start;
+      pkgCache::DepIterator end;
+      FindOrGroup(RD, start, end);
+
+      if (stillPossible(start, end))
+	 continue;
+
+      if (unlikely(debug >= 3))
+	 std::cerr << "Propagate NOT " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " to " << RDV.ParentPkg().FullName() << "=" << RDV.VerStr() << " for dependency group starting with" << start.TargetPkg().FullName() << std::endl;
+
+      if (not Reject(RDV, Reason(Ver)))
+	 return false;
+   }
+   return true;
+}
+
+bool APT::Solver::IsAllowedVersion(pkgCache::Version *V)
+{
+   pkgCache::VerIterator ver(cache, V);
+   if (not StrictPinning || ver.ParentPkg().CurrentVer() == ver || policy.GetCandidateVer(ver.ParentPkg()) == ver)
+      return true;
+
+   if (unlikely(debug >= 3))
+      std::cerr << "Ignoring: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "(neither candidate nor installed)\n";
+   return false;
+}
+
+void APT::Solver::Push(Work work)
+{
+   if (unlikely(debug >= 2))
+   {
+      std::cerr << "Trying choice for ";
+      work.Dump(cache);
+      std::cerr << "\n";
+   }
+   choices.push_back(std::move(work));
+   // Pop() will call MergeWithStack() when reverting to level 0, or RevertToStack after dumping to the debug log.
+   _error->PushToStack();
+}
+
+bool APT::Solver::Pop()
+{
+   auto depth = APT::Solver::depth();
+   if (depth == 0)
+      return false;
+
+   if (unlikely(debug >= 2))
+      for (std::string msg; _error->PopMessage(msg);)
+	 std::cerr << "Branch failed: " << msg << std::endl;
+
+   _error->RevertToStack();
+
+   depth--;
+
+   // Clean up the higher level states.
+   // FIXME: Do not override the hints here.
+   for (auto &state : pkgStates)
+      if (state.depth > depth)
+	 state = {};
+   for (auto &state : verStates)
+      if (state.depth > depth)
+	 state = {};
+
+   // This destroys the invariants that `work` must be a heap. But this is ok:
+   // we are restoring the invariant below, because rejecting a package always
+   // calls std::make_heap.
+   work.erase(std::remove_if(work.begin(), work.end(), [depth](Work &w) -> bool
+			     { return w.depth > depth || w.dirty; }),
+	      work.end());
+   std::make_heap(work.begin(), work.end());
+
+   // Go over the solved items, see if any of them need to be moved back or deleted.
+   solved.erase(std::remove_if(solved.begin(), solved.end(), [this, depth](Work &w) -> bool
+			       {
+				 if (w.depth > depth) // Deeper decision level is no longer valid.
+				    return true;
+				 // This item is still solved, keep it on the solved list.
+				 if (not std::any_of(w.solutions.begin(), w.solutions.end(), [this](auto ver)
+						     { return (*this)[ver].decision == Decision::MUST; }))
+				    return false;
+				 // We are not longer solved, move it back to work.
+				 AddWork(std::move(w));
+				 return true; }),
+		solved.end());
+
+   Work w = std::move(choices.back());
+   choices.pop_back();
+   if (unlikely(debug >= 2))
+   {
+      std::cerr << "Backtracking to choice ";
+      w.Dump(cache);
+      std::cerr << "\n";
+   }
+   if (unlikely(debug >= 4))
+   {
+      std::cerr << "choices: ";
+      for (auto &i : choices)
+      {
+	 std::cerr << pkgCache::VerIterator(cache, i.choice).ParentPkg().FullName(true) << "=" << pkgCache::VerIterator(cache, i.choice).VerStr();
+      }
+      std::cerr << std::endl;
+   }
+
+   assert(w.choice != nullptr);
+   // FIXME: There should be a reason!
+   if (not Reject(pkgCache::VerIterator(cache, w.choice), {}))
+      return false;
+
+   w.choice = nullptr;
+   AddWork(std::move(w));
+   return true;
+}
+
+void APT::Solver::AddWork(Work &&w)
+{
+   w.size = std::count_if(w.solutions.begin(), w.solutions.end(), [this](auto V)
+			  { return (*this)[V].decision != Decision::MUSTNOT; });
+   work.push_back(std::move(w));
+   std::push_heap(work.begin(), work.end());
+}
+
+void APT::Solver::RescoreWorkIfNeeded()
+{
+   if (not needsRescore)
+      return;
+
+   needsRescore = false;
+   std::vector<Work> resized;
+   for (auto &w : work)
+   {
+      if (w.dirty)
+	 continue;
+      size_t newSize = std::count_if(w.solutions.begin(), w.solutions.end(), [this](auto V)
+				     { return (*this)[V].decision != Decision::MUSTNOT; });
+
+      // Notably we only insert the work into the queue if it got smaller. Work that got larger
+      // we just move around when we get to it too early in Solve(). This reduces memory usage
+      // at the expense of counting each item we see in Solve().
+      if (newSize < w.size)
+      {
+	 Work newWork(w);
+	 newWork.size = newSize;
+	 resized.push_back(std::move(newWork));
+	 w.dirty = true;
+      }
+   }
+   if (unlikely(debug >= 2))
+      std::cerr << "Rescored: " << resized.size() << "items\n";
+   for (auto &w : resized)
+   {
+      work.push_back(std::move(w));
+      std::push_heap(work.begin(), work.end());
+   }
+}
+
+bool APT::Solver::Solve()
+{
+   while (not work.empty())
+   {
+      // Rescore the work if we need to
+      RescoreWorkIfNeeded();
+      // *NOW* we can pop the item.
+      std::pop_heap(work.begin(), work.end());
+
+      // This item has been replaced with a new one. Remove it.
+      if (work.back().dirty)
+      {
+	 work.pop_back();
+	 continue;
+      }
+
+      // If our size increased, queue again.
+      size_t newSize = std::count_if(work.back().solutions.begin(), work.back().solutions.end(), [this](auto V)
+				     { return (*this)[V].decision != Decision::MUSTNOT; });
+
+      if (newSize > work.back().size)
+      {
+	 work.back().size = newSize;
+	 std::push_heap(work.begin(), work.end());
+	 continue;
+      }
+      assert(newSize == work.back().size);
+
+      auto item = std::move(work.back());
+      work.pop_back();
+      solved.push_back(item);
+
+      if (std::any_of(item.solutions.begin(), item.solutions.end(), [this](auto ver)
+		      { return (*this)[ver].decision == Decision::MUST; }))
+      {
+	 if (unlikely(debug >= 2))
+	 {
+	    std::cerr << "ELIDED ";
+	    item.Dump(cache);
+	    std::cerr << "\n";
+	 }
+	 continue;
+      }
+
+      if (unlikely(debug >= 1))
+      {
+	 item.Dump(cache);
+	 std::cerr << "\n";
+      }
+
+      assert(item.solutions.size() > 1 || item.optional);
+
+      bool foundSolution = false;
+      for (auto &sol : item.solutions)
+      {
+	 pkgCache::VerIterator ver(cache, sol);
+	 if ((*this)[ver].decision == Decision::MUSTNOT)
+	 {
+	    if (unlikely(debug >= 3))
+	       std::cerr << "(existing conflict: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n";
+	    continue;
+	 }
+	 if (item.size > 1 || item.optional)
+	 {
+	    item.choice = ver;
+	    Push(item);
+	 }
+	 if (unlikely(debug >= 3))
+	    std::cerr << "(try it: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n";
+	 if (not Install(pkgCache::VerIterator(cache, ver), item.reason) && not Pop())
+	    return false;
+	 foundSolution = true;
+	 break;
+      }
+      if (not foundSolution && not item.optional)
+      {
+	 std::ostringstream dep;
+	 assert(item.solutions.size() > 0);
+	 for (auto &sol : item.solutions)
+	    dep << (dep.tellp() == 0 ? "" : " | ") << pkgCache::VerIterator(cache, sol).ParentPkg().FullName() << "=" << pkgCache::VerIterator(cache, sol).VerStr();
+	 _error->Error("Unsatisfiable dependency: %s -> %s", WhyStr(item.reason).c_str(), dep.str().c_str());
+	 for (auto &sol : item.solutions)
+	    if ((*this)[sol].decision == Decision::MUSTNOT)
+	       _error->Error("Not considered: %s=%s: %s", pkgCache::VerIterator(cache, sol).ParentPkg().FullName().c_str(),
+			     pkgCache::VerIterator(cache, sol).VerStr(),
+			     WhyStr(Reason(pkgCache::VerIterator(cache, sol))).c_str());
+	 if (not Pop())
+	    return false;
+      }
+   }
+
+   return true;
+}
+
+// \brief Apply the selections from the dep cache to the solver
+bool APT::Solver::FromDepCache(pkgDepCache &depcache)
+{
+   bool KeepAuto = not _config->FindB("APT::Get::AutomaticRemove");
+   bool AllowRemove = _config->FindB("APT::Solver::Remove", true);
+   bool AllowInstall = _config->FindB("APT::Solver::Install", true);
+   DefaultRootSetFunc2 rootSet(&cache);
+
+   for (auto P = cache.PkgBegin(); not P.end(); P++)
+   {
+      if (P->VersionList == nullptr)
+	 continue;
+
+      auto state = depcache[P];
+      auto maybeInstall = state.Install() || (state.Keep() && P->CurrentVer);
+      auto reject = state.Delete() || (depcache[P].Keep() && not P->CurrentVer && depcache[P].Protect());
+      if (P->SelectedState == pkgCache::State::Hold && not state.Protect())
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << "Hold " << P.FullName() << "\n";
+	 if (P->CurrentVer ? not Install(P.CurrentVer(), {}) : not Reject(P, {}))
+	    return false;
+      }
+      else if (reject)
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << "Delete " << P.FullName() << "\n";
+	 if (!Reject(P, {}))
+	    return false;
+      }
+      else if (maybeInstall && P->Flags & (pkgCache::Flag::Essential | pkgCache::Flag::Important))
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << "ESSENTIAL " << P.FullName() << "\n";
+	 if (depcache[P].Keep() ? not Install(P, {}) : not Install(depcache.GetCandidateVersion(P), {}))
+	    return false;
+      }
+      else if (maybeInstall && not(depcache[P].Flags & pkgCache::Flag::Auto))
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << "MANUAL " << P.FullName() << "\n";
+	 if (depcache[P].Keep() ? not Install(P, {}) : not Install(depcache.GetCandidateVersion(P), {}))
+	    return false;
+      }
+      else if (maybeInstall && (KeepAuto || rootSet.InRootSet(P)) && (depcache[P].Flags & pkgCache::Flag::Auto))
+      {
+	 auto Upgrade = depcache.GetCandidateVersion(P) != P.CurrentVer();
+	 if (unlikely(debug >= 1))
+	    std::cerr << "AUTOMATIC " << P.FullName() << (Upgrade ? " - upgrade" : "") << "\n";
+
+	 if (not AllowRemove)
+	 {
+	    if (depcache[P].Keep() ? not Install(P, {}) : not Install(depcache.GetCandidateVersion(P), {}))
+	       return false;
+	 }
+	 else
+	 {
+	    Work w{Reason(), depth(), true, Upgrade};
+	    for (auto V = P.VersionList(); not V.end(); ++V)
+	       if (IsAllowedVersion(V))
+		  w.solutions.push_back(V);
+	    std::sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P});
+	    AddWork(std::move(w));
+	 }
+      }
+      else if (P->CurrentVer == 0 && not AllowInstall)
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << "NOT ALLOWING INSTALL OF " << P.FullName() << "\n";
+	 if (not Reject(P, {}))
+	    return false;
+      }
+   }
+
+   return true;
+}
+
+bool APT::Solver::ToDepCache(pkgDepCache &depcache)
+{
+   pkgDepCache::ActionGroup group(depcache);
+   for (auto P = cache.PkgBegin(); not P.end(); P++)
+   {
+      if ((*this)[P].decision == Decision::MUST)
+      {
+	 for (auto V = P.VersionList(); not V.end(); V++)
+	 {
+	    if ((*this)[V].decision == Decision::MUST)
+	    {
+	       depcache.SetCandidateVersion(V);
+	       break;
+	    }
+	 }
+	 auto reason = (*this)[depcache.GetCandidateVersion(P)].reason;
+	 if (auto RP = reason.Pkg(); RP == P.MapPointer())
+	    reason = (*this)[P].reason;
+
+	 depcache.MarkInstall(P, false, 0, reason.empty());
+	 if (not P->CurrentVer)
+	    depcache.MarkAuto(P, not reason.empty());
+	 depcache[P].Marked = 1;
+	 depcache[P].Garbage = 0;
+      }
+      else if (P->CurrentVer)
+      {
+	 depcache.MarkDelete(P, false, 0, (*this)[P].reason.empty());
+	 depcache[P].Marked = 0;
+	 depcache[P].Garbage = 1;
+      }
+   }
+   return true;
+}
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
new file mode 100644
index 0000000..cf2fb2e
--- /dev/null
+++ b/apt-pkg/solver3.h
@@ -0,0 +1,286 @@
+/*
+ * solver3.h - The APT 3.0 solver
+ *
+ * Copyright (c) 2023 Julian Andres Klode
+ * Copyright (c) 2023 Canonical Ltd
+ *
+ * SPDX-License-Identifier: GPL-2.0+
+ */
+
+#include <vector>
+
+#include <apt-pkg/configuration.h>
+#include <apt-pkg/depcache.h>
+#include <apt-pkg/pkgcache.h>
+#include <apt-pkg/policy.h>
+
+namespace APT
+{
+
+/*
+ * \brief APT 3.0 solver
+ *
+ * This is a simple solver focused on understandability and sensible results, it
+ * will not generally find all solutions to the problem but will try to find the best
+ * ones.
+ *
+ * It is a brute force solver with heuristics, conflicts learning, and 2**32 levels
+ * of backtracking.
+ */
+class Solver
+{
+   enum class Decision : uint16_t;
+   enum class Hint : uint16_t;
+   struct Reason;
+   template <typename T>
+   struct State;
+   struct Work;
+
+   // \brief Type to record depth at. This may very well be a 16-bit
+   // unsigned integer, then change Solver::State::Decision to be a
+   // uint16_t class enum as well to get a more compact space.
+   using depth_type = unsigned int;
+
+   // Documentation
+   template <typename T>
+   using heap = std::vector<T>;
+
+   static_assert(sizeof(depth_type) >= sizeof(map_id_t));
+
+   // Cache is needed to construct Iterators from Version objects we see
+   pkgCache &cache;
+   // Policy is needed for determining candidate version.
+   pkgDepCache::Policy &policy;
+   // States for packages
+   std::vector<State<pkgCache::Package>> pkgStates{};
+   // States for versions
+   std::vector<State<pkgCache::Version>> verStates{};
+
+   // \brief Helper function for safe access to package state.
+   inline State<pkgCache::Package> &operator[](pkgCache::Package *P)
+   {
+      return pkgStates[P->ID];
+   }
+
+   // \brief Helper function for safe access to version state.
+   inline State<pkgCache::Version> &operator[](pkgCache::Version *V)
+   {
+      return verStates[V->ID];
+   }
+
+   // \brief Heap of the remaining work.
+   //
+   // We are using an std::vector with std::make_heap(), std::push_heap(),
+   // and std::pop_heap() rather than a priority_queue because we need to
+   // be able to iterate over the queued work and see if a choice would
+   // invalidate any work.
+   heap<Work> work{};
+   // \brief Whether RescoreWork() actually needs to rescore the work.
+   bool needsRescore{false};
+
+   // \brief Current decision level.
+   //
+   // Each time a decision needs to be made we can push the item under
+   // consideration to our backlog of choices made and then later we can
+   // restore it easily.
+   std::vector<Work> choices{};
+   // \brief Backlog of solved work.
+   //
+   // Solved work may become invalidated when backtracking, so store it
+   // here to revisit it later.
+   std::vector<Work> solved{};
+
+   /// Various configuration options
+   // \brief Debug level
+   int debug{_config->FindI("Debug::APT::Solver")};
+   // \brief If set, we try to keep automatically installed packages installed.
+   bool KeepAuto{not _config->FindB("APT::Get::AutomaticRemove")};
+   // \brief If set, removals are allowed.
+   bool AllowRemove{_config->FindB("APT::Solver::Remove", true)};
+   // \brief If set, installs are allowed.
+   bool AllowInstall{_config->FindB("APT::Solver::Install", true)};
+   // \brief If set, we use strict pinning.
+   bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)};
+
+   // \brief Enqueue dependencies shared by all versions of the package.
+   bool EnqueueCommonDependencies(pkgCache::PkgIterator Pkg);
+   // \brief Reject reverse dependencies. Must call std::make_heap() after.
+   bool RejectReverseDependencies(pkgCache::VerIterator Ver);
+   // \brief Enqueue a single or group
+   bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Reason reason);
+   // \brief Check if a version is allowed by policy.
+   bool IsAllowedVersion(pkgCache::Version *V);
+
+   // \brief Return the current depth (choices.size() with casting)
+   depth_type depth()
+   {
+      return static_cast<depth_type>(choices.size());
+   }
+
+   public:
+   // \brief Create a new decision level.
+   bool Pop();
+   // \brief Revert to the previous decision level.
+   void Push(Work work);
+   // \brief Add work to our work queue.
+   void AddWork(Work &&work);
+   // \brief Rescore the work after a reject or a pop
+   void RescoreWorkIfNeeded();
+
+   // \brief Basic solver initializer. This cannot fail.
+   Solver(pkgCache &Cache, pkgDepCache::Policy &Policy);
+
+   // \brief Mark the package for install. This is annoying as it incurs a decision
+   bool Install(pkgCache::PkgIterator Pkg, Reason reason);
+   // \brief Install a version.
+   bool Install(pkgCache::VerIterator Ver, Reason reason);
+   // \brief Do not install this package
+   bool Reject(pkgCache::PkgIterator Pkg, Reason reason);
+   // \brief Do not install this version.
+   bool Reject(pkgCache::VerIterator Ver, Reason reason);
+
+   // \brief Apply the selections from the dep cache to the solver
+   bool FromDepCache(pkgDepCache &depcache);
+   // \brief Apply the solver result to the depCache
+   bool ToDepCache(pkgDepCache &depcache);
+
+   // \brief Solve the dependencies
+   bool Solve();
+
+   // Print dependency chain
+   std::string WhyStr(Reason reason);
+};
+
+}; // namespace APT
+
+/**
+ * \brief Tagged union holding either a package, version, or nothing; representing the reason for installing something.
+ *
+ * We want to keep track of the reason why things are being installed such that
+ * we can have sensible debugging abilities.
+ *
+ * If the reason is empty, this means the package is automatically installed.
+ */
+struct APT::Solver::Reason
+{
+   uint32_t IsVersion : 1;
+   uint32_t MapPtr : 31;
+
+   Reason() : IsVersion(0), MapPtr(0) {}
+   explicit Reason(pkgCache::PkgIterator const &Pkg) : IsVersion(0), MapPtr(Pkg.MapPointer()) {}
+   explicit Reason(pkgCache::VerIterator const &Ver) : IsVersion(1), MapPtr(Ver.MapPointer()) {}
+
+   // \brief Return the package, if any, otherwise 0.
+   map_pointer<pkgCache::Package> Pkg() const
+   {
+      return IsVersion ? 0 : map_pointer<pkgCache::Package>{(uint32_t)MapPtr};
+   }
+   // \brief Return the version, if any, otherwise 0.
+   map_pointer<pkgCache::Version> Ver() const
+   {
+      return IsVersion ? map_pointer<pkgCache::Version>{(uint32_t)MapPtr} : 0;
+   }
+   // \brief Check if there is no reason.
+   bool empty() const
+   {
+      return IsVersion == 0 && MapPtr == 0;
+   }
+};
+
+/**
+ * \brief A single work item
+ *
+ * A work item is a positive dependency that still needs to be resolved. Work
+ * is ordered, by depth, length of solutions, and optionality.
+ *
+ * The work can always be recalculated from the state by iterating over dependencies
+ * of all packages in there, finding solutions to them, and then adding all dependencies
+ * not yet resolved to the work queue.
+ */
+struct APT::Solver::Work
+{
+   // \brief Reason for the work
+   Reason reason;
+   // \brief The depth at which the item has been added
+   depth_type depth;
+
+   // \brief Possible solutions to this task, ordered in order of preference.
+   std::vector<pkgCache::Version *> solutions{};
+
+   // This is a union because we only need to store the choice we made when adding
+   // to the choice vector, and we don't need the size of valid choices in there.
+   union
+   {
+      // The choice we took
+      pkgCache::Version *choice;
+      // Number of valid choices
+      size_t size;
+   };
+
+   // \brief Whether this is an optional work item, they will be processed last
+   bool optional;
+   // \brief Whether this is an ugprade
+   bool upgrade;
+   // \brief This item should be removed from the queue.
+   bool dirty;
+
+   bool operator<(APT::Solver::Work const &b) const;
+   // \brief Dump the work item to std::cerr
+   void Dump(pkgCache &cache);
+
+   inline Work(Reason reason, depth_type depth, bool optional = false, bool upgrade = false) : reason(reason), depth(depth), size(0), optional(optional), upgrade(upgrade), dirty(false) {}
+};
+
+// \brief This essentially describes the install state in RFC2119 terms.
+enum class APT::Solver::Decision : uint16_t
+{
+   // \brief We have not made a choice about the package yet
+   NONE,
+   // \brief We need to install this package
+   MUST,
+   // \brief We cannot install this package (need conflicts with it)
+   MUSTNOT,
+};
+
+// \brief Hints for the solver about the item.
+enum class APT::Solver::Hint : uint16_t
+{
+   // \brief We have not made a choice about the package yet
+   NONE,
+   // \brief This package was listed as a Recommends of a must package,
+   SHOULD,
+   // \brief This package was listed as a Suggests of a must-not package
+   MAY,
+};
+
+/**
+ * \brief The solver state
+ *
+ * For each version, the solver records a decision at a certain level. It
+ * maintains an array mapping from version ID to state.
+ */
+template <typename T>
+struct APT::Solver::State
+{
+   // \brief The reason for causing this state (invalid for NONE).
+   //
+   // Rejects may have been caused by a later state. Consider we select
+   // between x1 and x2 in depth = N. If we now find dependencies of x1
+   // leading to a conflict with a package in K < N, we will record all
+   // of them as REJECT in depth = K.
+   //
+   // You can follow the reason chain upwards as long as the depth
+   // doesn't increase to unwind.
+   //
+   // Reasons < 0 are package ID, reasons > 0 are version IDs.
+   Reason reason{};
+
+   // \brief The depth at which the decision has been taken
+   depth_type depth{0};
+
+   // \brief This essentially describes the install state in RFC2119 terms.
+   Decision decision{Decision::NONE};
+
+   // \brief Any hint.
+   Hint hint{Hint::NONE};
+};
diff --git a/apt-pkg/upgrade.cc b/apt-pkg/upgrade.cc
index fad4783..ac0b71c 100644
--- a/apt-pkg/upgrade.cc
+++ b/apt-pkg/upgrade.cc
@@ -312,6 +312,11 @@ bool pkgMinimizeUpgrade(pkgDepCache &Cache)
 // APT::Upgrade::Upgrade - Upgrade using a specific strategy		/*{{{*/
 bool APT::Upgrade::Upgrade(pkgDepCache &Cache, int mode, OpProgress * const Progress)
 {
+   _config->Set("APT::Solver::Upgrade", "true");
+   if (mode & FORBID_REMOVE_PACKAGES)
+      _config->Set("APT::Solver::Remove", "false");
+   if (mode & FORBID_INSTALL_NEW_PACKAGES)
+      _config->Set("APT::Solver::Install", "false");
    if (mode == ALLOW_EVERYTHING)
       return pkgDistUpgrade(Cache, Progress);
    else if ((mode & ~FORBID_REMOVE_PACKAGES) == 0)
diff --git a/apt-private/private-cmndline.cc b/apt-private/private-cmndline.cc
index b05ec89..592ebd9 100644
--- a/apt-private/private-cmndline.cc
+++ b/apt-private/private-cmndline.cc
@@ -190,6 +190,7 @@ static bool addArgumentsAPTGet(std::vector<CommandLine::Args> &Args, char const
       addArg(0, "auto-remove", "APT::Get::AutomaticRemove", 0);
       addArg(0, "reinstall", "APT::Get::ReInstall", 0);
       addArg(0, "solver", "APT::Solver", CommandLine::HasArg);
+      addArg(0, "strict-pinning", "APT::Solver::Strict-Pinning", 0);
       addArg(0, "planner", "APT::Planner", CommandLine::HasArg);
       addArg('U', "update", "APT::Update", 0);
       if (CmdMatches("upgrade"))
@@ -230,6 +231,7 @@ static bool addArgumentsAPTGet(std::vector<CommandLine::Args> &Args, char const
       addArg('P', "build-profiles", "APT::Build-Profiles", CommandLine::HasArg);
       addArg(0, "purge", "APT::Get::Purge", 0);
       addArg(0, "solver", "APT::Solver", CommandLine::HasArg);
+      addArg(0, "strict-pinning", "APT::Solver::Strict-Pinning", 0);
       if (CmdMatches("build-dep"))
       {
          addArg(0,"arch-only","APT::Get::Arch-Only",0);
@@ -580,6 +582,12 @@ std::vector<CommandLine::Dispatch> ParseCommandLine(CommandLine &CmdL, APT_CMD c
       _error->Warning(_("--force-yes is deprecated, use one of the options starting with --allow instead."));
    }
 
+   if (not _config->FindB("APT::Solver::Strict-Pinning", true) && _config->Find("APT::Solver", "internal") == "internal")
+   {
+      _config->Set("APT::Solver", "3.0");
+      _error->Notice("Automatically enabled --solver 3.0 for --no-strict-pinning");
+   }
+
    // See if the help should be shown
    if (_config->FindB("help") == true || _config->FindB("version") == true ||
 	 (CmdL.FileSize() > 0 && strcmp(CmdL.FileList[0], "help") == 0))
diff --git a/apt-private/private-install.cc b/apt-private/private-install.cc
index 9a2ed0b..4f71f18 100644
--- a/apt-private/private-install.cc
+++ b/apt-private/private-install.cc
@@ -20,6 +20,7 @@
 #include <apt-pkg/prettyprinters.h>
 #include <apt-pkg/strutl.h>
 #include <apt-pkg/upgrade.h>
+#include <apt-pkg/version.h>
 
 #include <algorithm>
 #include <cstdlib>
@@ -214,16 +215,6 @@ bool InstallPackages(CacheFile &Cache, APT::PackageVector &HeldBackPackages, boo
 	 return false;
    }
 
-   APT::PackageVector PhasingPackages;
-   APT::PackageVector NotPhasingHeldBackPackages;
-   for (auto const &Pkg : HeldBackPackages)
-   {
-      if (Cache->PhasingApplied(Pkg))
-	 PhasingPackages.push_back(Pkg);
-      else
-	 NotPhasingHeldBackPackages.push_back(Pkg);
-   }
-
    // Show all the various warning indicators
    if (_config->FindI("APT::Output-Version") < 30)
       ShowDel(c1out,Cache);
@@ -234,6 +225,16 @@ bool InstallPackages(CacheFile &Cache, APT::PackageVector &HeldBackPackages, boo
       ShowWeakDependencies(Cache);
    if (ShwKept == true)
    {
+      APT::PackageVector PhasingPackages;
+      APT::PackageVector NotPhasingHeldBackPackages;
+      for (auto const &Pkg : HeldBackPackages)
+      {
+	 if (Cache->PhasingApplied(Pkg))
+	    PhasingPackages.push_back(Pkg);
+	 else
+	    NotPhasingHeldBackPackages.push_back(Pkg);
+      }
+
       ShowPhasing(c1out, Cache, PhasingPackages);
       ShowKept(c1out, Cache, NotPhasingHeldBackPackages);
       if (not PhasingPackages.empty() && not NotPhasingHeldBackPackages.empty())
@@ -620,12 +621,14 @@ bool DoAutomaticRemove(CacheFile &Cache)
 	 for (APT::PackageSet::iterator Pkg = tooMuch.begin();
 	      Pkg != tooMuch.end(); ++Pkg)
 	 {
-	    APT::PackageSet too;
-	    too.insert(*Pkg);
-	    for (pkgCache::PrvIterator Prv = Cache[Pkg].CandidateVerIter(Cache).ProvidesList();
-		 Prv.end() == false; ++Prv)
-	       too.insert(Prv.ParentPkg());
-	    for (APT::PackageSet::const_iterator P = too.begin(); P != too.end(); ++P)
+	    auto const PkgCand = Cache[Pkg].CandidateVerIter(Cache);
+	    if (unlikely(PkgCand.end()))
+	       continue;
+	    std::vector<std::pair<pkgCache::PkgIterator, char const *>> too;
+	    too.emplace_back(*Pkg, PkgCand.VerStr());
+	    for (pkgCache::PrvIterator Prv = PkgCand.ProvidesList(); not Prv.end(); ++Prv)
+	       too.emplace_back(Prv.ParentPkg(), Prv.ProvideVersion());
+	    for (auto const &[P, PVerStr] : too)
 	    {
 	       for (pkgCache::DepIterator R = P.RevDependsList();
 		    R.end() == false; ++R)
@@ -650,6 +653,11 @@ bool DoAutomaticRemove(CacheFile &Cache)
 		 }
 		 else // ignore dependency from a non-candidate version
 		    continue;
+		 if (R->Version != 0)
+		 {
+		    if (not Cache->VS().CheckDep(PVerStr, R->CompareOp, R.TargetVer()))
+		       continue;
+		 }
 		 if (Debug == true)
 		    std::clog << "Save " << APT::PrettyPkg(Cache, Pkg) << " as another installed package depends on it: " << APT::PrettyPkg(Cache, RP) << std::endl;
 		 Cache->MarkInstall(Pkg, false, 0, false);
diff --git a/apt-private/private-output.cc b/apt-private/private-output.cc
index 09d03d3..2e81095 100644
--- a/apt-private/private-output.cc
+++ b/apt-private/private-output.cc
@@ -350,7 +350,7 @@ struct columnInfo
 void ShowWithColumns(ostream &out, vector<string> const &List, size_t Indent, size_t ScreenWidth)
 {
    constexpr size_t MinColumnWidth = 2;
-   constexpr size_t ColumnSpace = 1;
+   constexpr size_t ColumnSpace = 2;
 
    size_t const ListSize = List.size();
    size_t const MaxScreenCols = (ScreenWidth - Indent) /
@@ -740,7 +740,7 @@ bool ShowEssential(ostream &out,CacheFile &Cache)
    }
    return ShowList(out,_("WARNING: The following essential packages will be removed.\n"
 			 "This should NOT be done unless you know exactly what you are doing!"),
-	 pkglist, &AlwaysTrue, withdue, &EmptyString);
+	 pkglist, &AlwaysTrue, withdue, &EmptyString, "action::remove");
 }
 									/*}}}*/
 // Stats - Show some statistics						/*{{{*/
diff --git a/apt-private/private-show.cc b/apt-private/private-show.cc
index 4ae0430..ceef670 100644
--- a/apt-private/private-show.cc
+++ b/apt-private/private-show.cc
@@ -446,14 +446,22 @@ bool ShowSrcPackage(CommandLine &CmdL)					/*{{{*/
    std::set<std::string> seen;
    for (const char **I = CmdL.FileList + 1; *I != 0; I++)
    {
+      const char *pkgname = *I;
       SrcRecs.Restart();
 
       pkgSrcRecords::Parser *Parse;
       bool found_this = false;
-      while ((Parse = SrcRecs.Find(*I,false)) != 0) {
+      bool only_source = _config->FindB("APT::Cache::Only-Source", false);
+      if (APT::String::Startswith(pkgname, "src:"))
+      {
+	 only_source = true;
+	 pkgname += 4;
+      }
+      while ((Parse = SrcRecs.Find(pkgname, false)) != 0)
+      {
 	 // SrcRecs.Find() will find both binary and source names
-	 if (_config->FindB("APT::Cache::Only-Source", false) == true)
-	    if (Parse->Package() != *I)
+	 if (only_source)
+	    if (Parse->Package() != pkgname)
 	       continue;
          std::string sha1str = Sha1FromString(Parse->AsStr());
          if (std::find(seen.begin(), seen.end(), sha1str) == seen.end())
diff --git a/apt-private/private-source.cc b/apt-private/private-source.cc
index 9b9409c..6280b9f 100644
--- a/apt-private/private-source.cc
+++ b/apt-private/private-source.cc
@@ -77,7 +77,14 @@ static pkgSrcRecords::Parser *FindSrc(const char *Name,
    std::string ArchTag = "";
    std::string RelTag = _config->Find("APT::Default-Release");
    std::string TmpSrc = Name;
+   bool MatchSrcOnly = _config->FindB("APT::Get::Only-Source");
 
+   // Check if we should look by source package
+   if (APT::String::Startswith(TmpSrc, "src:"))
+   {
+      MatchSrcOnly = true;
+      TmpSrc = TmpSrc.substr(4);
+   }
    // extract release
    size_t found = TmpSrc.find_last_of("/");
    if (found != std::string::npos)
@@ -103,7 +110,6 @@ static pkgSrcRecords::Parser *FindSrc(const char *Name,
    /* Lookup the version of the package we would install if we were to
       install a version and determine the source package name, then look
       in the archive for a source package of the same name. */
-   bool MatchSrcOnly = _config->FindB("APT::Get::Only-Source");
    pkgCache::PkgIterator Pkg;
    if (ArchTag != "")
       Pkg = Cache.GetPkgCache()->FindPkg(TmpSrc, ArchTag);
diff --git a/cmdline/CMakeLists.txt b/cmdline/CMakeLists.txt
index 91bf9bb..28a14dd 100644
--- a/cmdline/CMakeLists.txt
+++ b/cmdline/CMakeLists.txt
@@ -54,6 +54,7 @@ install(TARGETS apt-dump-solver apt-internal-solver RUNTIME DESTINATION ${CMAKE_
 install(TARGETS apt-internal-planner RUNTIME DESTINATION ${CMAKE_INSTALL_LIBEXECDIR}/apt/planners)
 
 add_links(${CMAKE_INSTALL_LIBEXECDIR}/apt/planners ../solvers/dump planners/dump)
+add_links(${CMAKE_INSTALL_LIBEXECDIR}/apt/solvers apt solver3)
 
 # Install the not-to-be-compiled programs
 INSTALL(PROGRAMS ${CMAKE_CURRENT_BINARY_DIR}/apt-key DESTINATION ${CMAKE_INSTALL_BINDIR})
diff --git a/cmdline/apt-internal-solver.cc b/cmdline/apt-internal-solver.cc
index 094ed18..d596dcb 100644
--- a/cmdline/apt-internal-solver.cc
+++ b/cmdline/apt-internal-solver.cc
@@ -119,7 +119,10 @@ int main(int argc,const char *argv[])					/*{{{*/
 		_config->Set("Debug::EDSP::WriteSolution", true);
 
 	_config->Set("APT::System", "Debian APT solver interface");
-	_config->Set("APT::Solver", "internal");
+	if (strcmp(basename(argv[0]), "solver3") == 0)
+	   _config->Set("APT::Solver", "3.0");
+	else if (_config->Find("APT::Solver") != "3.0")
+	   _config->Set("APT::Solver", "internal");
 	_config->Set("edsp::scenario", "/nonexistent/stdin");
 	_config->Clear("Dir::Log");
 	FileFd output;
diff --git a/completions/bash/apt b/completions/bash/apt
index 7c4b44a..b18c2ed 100644
--- a/completions/bash/apt
+++ b/completions/bash/apt
@@ -81,7 +81,7 @@ _apt()
                   --ignore-hold
                   --force-yes
                   --trivial-only
-                  --reinstall --solver
+                  --reinstall --solver --no-strict-pinning
                   -t --target-release'"$GENERIC_APT_GET_OPTIONS" -- "$cur" ) )
                 return 0
                 ;;
@@ -151,7 +151,7 @@ _apt()
                     -s --simulate --dry-run
                     -P --build-profiles
                     -t --target-release
-                    --purge --solver
+                    --purge --solver --no-strict-pinning
                     '"$GENERIC_APT_GET_OPTIONS" -- "$cur" ) )
                 return 0
                 ;;
diff --git a/doc/apt-verbatim.ent b/doc/apt-verbatim.ent
index d19a376..aef0c3e 100644
--- a/doc/apt-verbatim.ent
+++ b/doc/apt-verbatim.ent
@@ -274,7 +274,7 @@
 ">
 
 <!-- this will be updated by 'prepare-release' -->
-<!ENTITY apt-product-version "2.9.2">
+<!ENTITY apt-product-version "2.9.3">
 
 <!-- (Code)names for various things used all over the place -->
 <!ENTITY debian-oldstable-codename "bullseye">
diff --git a/doc/examples/configure-index b/doc/examples/configure-index
index 981fe6f..c27a8f8 100644
--- a/doc/examples/configure-index
+++ b/doc/examples/configure-index
@@ -603,6 +603,7 @@ Debug
   SetupAPTPartialDirectory::AssumeGood "<BOOL>";
   Locking "<BOOL>";
   Phasing "<BOOL>";
+  APT::Solver "<INT">;
 };
 
 pkgCacheGen
@@ -720,6 +721,10 @@ apt::hashes::*::untrusted "<BOOL>";
 apt::list-cleanup "<BOOL>";
 apt::authentication::trustcdrom "<BOOL>";
 apt::solver::strict-pinning "<BOOL>";
+apt::solver::enqueue-common-dependencies "<BOOL>";
+apt::solver::upgrade "<BOOL>";
+apt::solver::remove "<BOOL>";
+apt::solver::install "<BOOL>";
 apt::keep-downloaded-packages "<BOOL>";
 apt::solver "<STRING>";
 apt::planner "<STRING>";
diff --git a/doc/po/apt-doc.pot b/doc/po/apt-doc.pot
index 2a63215..2578224 100644
--- a/doc/po/apt-doc.pot
+++ b/doc/po/apt-doc.pot
@@ -5,9 +5,9 @@
 #, fuzzy
 msgid ""
 msgstr ""
-"Project-Id-Version: apt-doc 2.9.2\n"
+"Project-Id-Version: apt-doc 2.9.3\n"
 "Report-Msgid-Bugs-To: APT Development Team <deity@lists.debian.org>\n"
-"POT-Creation-Date: 2024-04-22 17:39+0000\n"
+"POT-Creation-Date: 2024-05-14 11:16+0000\n"
 "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
 "Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
 "Language-Team: LANGUAGE <LL@li.org>\n"
diff --git a/doc/po/nl.po b/doc/po/nl.po
index 76c782f..0d45a86 100644
--- a/doc/po/nl.po
+++ b/doc/po/nl.po
@@ -4,10 +4,10 @@
 #
 msgid ""
 msgstr ""
-"Project-Id-Version: apt-doc 2.7.12\n"
+"Project-Id-Version: apt-doc 2.9.1\n"
 "Report-Msgid-Bugs-To: APT Development Team <deity@lists.debian.org>\n"
-"POT-Creation-Date: 2024-04-22 17:38+0000\n"
-"PO-Revision-Date: 2024-02-26 22:00+0100\n"
+"POT-Creation-Date: 2024-05-06 11:01+0000\n"
+"PO-Revision-Date: 2024-04-20 21:59+0200\n"
 "Last-Translator: Frans Spiesschaert <Frans.Spiesschaert@yucom.be>\n"
 "Language-Team: Debian Dutch l10n Team <debian-l10n-dutch@lists.debian.org>\n"
 "Language: nl\n"
@@ -1312,7 +1312,7 @@ msgid ""
 "Both of the version selection mechanisms can downgrade packages and must be "
 "used with care."
 msgstr ""
-"Beide versieselectiemechanismes kunnen pakketten degraderen en moeten met "
+"Beide versieselectiemechanismes kunnen pakketten downgraden en moeten met "
 "zorg gebruikt worden."
 
 #. type: Content of: <refentry><refsect1><variablelist><varlistentry><listitem><para>
@@ -1889,7 +1889,7 @@ msgid ""
 "Do not show a list of all packages that are to be upgraded.  Configuration "
 "Item: <literal>APT::Get::Show-Upgraded</literal>."
 msgstr ""
-"Geef geen lijst weer van alle pakketten die opgewaardeerd zullen worden. "
+"Geen lijst weergeven van alle pakketten die opgewaardeerd zullen worden. "
 "Configuratie-item: <literal>APT::Get::Show-Upgraded</literal>."
 
 #. type: Content of: <refentry><refsect1><variablelist><varlistentry><listitem><para>
@@ -1898,22 +1898,19 @@ msgid ""
 "Show full versions for upgraded and installed packages.  Configuration Item: "
 "<literal>APT::Get::Show-Versions</literal>."
 msgstr ""
-"Geef het volledige versienummer weer van opgewaardeerde en geïnstalleerde "
+"Het volledige versienummer weergeven van opgewaardeerde en geïnstalleerde "
 "pakketten. Configuratie-item: <literal>APT::Get::Show-Versions</literal>."
 
 #. type: Content of: <refentry><refsect1><variablelist><varlistentry><listitem><para>
 #: apt-get.8.xml
-#, fuzzy
-#| msgid ""
-#| "Re-install packages that are already installed and at the newest "
-#| "version.  Configuration Item: <literal>APT::Get::ReInstall</literal>."
 msgid ""
 "Display package lists without arranging them in columns. By default, package "
 "lists are printed in the style of the \"ls\" command.  Configuration Item: "
 "<literal>APT::Get::List-Columns</literal>."
 msgstr ""
-"Pakketten die reeds met hun nieuwste versie geïnstalleerd zijn, opnieuw "
-"installeren. Configuratie-item: <literal>APT::Get::ReInstall</literal>."
+"Pakketlijsten weergeven zonder deze in kolommen te rangschikken. Standaard "
+"worden pakketlijsten afgedrukt in de stijl van het commando \"ls\". "
+"Configuratie-item: <literal>APT::Get::List-Columns</literal>."
 
 #. type: Content of: <refentry><refsect1><variablelist><varlistentry><listitem><para>
 #: apt-get.8.xml
@@ -2029,7 +2026,7 @@ msgid ""
 "Item: <literal>APT::Get::allow-downgrades</literal>. Introduced in APT 1.1."
 msgstr ""
 "Dit is een gevaarlijke optie die er voor zorgt dat apt zonder vragen "
-"voortgaat als het degradaties doorvoert. U zou dit niet moeten gebruiken "
+"voortgaat als het downgradings doorvoert. U zou dit niet moeten gebruiken "
 "behalve in zeer bijzondere situaties. Dit gebruiken kan mogelijkerwijs tot "
 "de vernietiging van uw systeem leiden! Configuratie-item: <literal>APT::Get::"
 "allow-downgrades</literal>. Geïntroduceerd in APT 1.1."
@@ -6286,7 +6283,7 @@ msgstr ""
 "In Versie 2 bestaan regels in verband met een pakketactie uit vijf velden: "
 "pakketnaam (zonder architectuuropgave, zelfs indien niet-systeemeigen), oude "
 "versie, richting van de versiewijziging (&lt; voor opwaarderingen, &gt; voor "
-"degradaties, = voor geen wijziging), nieuwe versie, actie. De versievelden "
+"downgradings, = voor geen wijziging), nieuwe versie, actie. De versievelden "
 "zijn \"-\" voor helemaal geen versie (bijvoorbeeld wanneer een pakket voor "
 "het eerst geïnstalleerd wordt; geen versie wordt behandeld als ouder dan "
 "gelijk welke echte versie, waardoor het een opwaardering betreft, aangeduid "
@@ -7026,13 +7023,13 @@ msgid ""
 "exceeds 1000; such high priorities can only be set in the preferences file.  "
 "Note also that downgrading a package can be risky.)"
 msgstr ""
-"Nooit een degradatie uitvoeren tenzij de prioriteit van een beschikbaar "
-"pakket groter is dan 1000. (\"Degraderen\" (downgrading) betekent het "
-"installeren van een minder recente versie van een pakket ter vervanging van "
-"een recentere versie. Noteer dat geen enkele van de standaardprioriteiten "
-"die APT gebruikt, groter dan 1000 is. Dergelijke hoge prioriteiten kunnen "
-"enkel in het bestand preferences ingesteld worden. Merk ook op dat het "
-"degraderen van een pakket riskant kan zijn.)"
+"Nooit een downgrading uitvoeren tenzij de prioriteit van een beschikbaar "
+"pakket groter is dan 1000. (\"Downgrading\" betekent het installeren van een "
+"minder recente versie van een pakket ter vervanging van een recentere "
+"versie. Noteer dat geen enkele van de standaardprioriteiten die APT "
+"gebruikt, groter dan 1000 is. Dergelijke hoge prioriteiten kunnen enkel in "
+"het bestand preferences ingesteld worden. Merk ook op dat het downgraden van "
+"een pakket riskant kan zijn.)"
 
 #. type: Content of: <refentry><refsect1><refsect2><para><itemizedlist><listitem><simpara>
 #: apt_preferences.5.xml
@@ -7089,7 +7086,7 @@ msgstr ""
 "van een pakket <emphasis>recenter</emphasis> is dan welke andere beschikbare "
 "versie ook. Bij het uitvoeren van de opdracht apt-get install "
 "<command><replaceable>een-bepaald-pakket</replaceable></command> of "
-"<command>apt-get upgrade</command> zal het pakket dan niet gedegradeerd "
+"<command>apt-get upgrade</command> zal het pakket dan niet gedowngraded "
 "worden."
 
 #. type: Content of: <refentry><refsect1><refsect2><para>
@@ -7576,7 +7573,7 @@ msgid ""
 "package"
 msgstr ""
 "heeft de installatie van een versie tot gevolg ook al houdt dit een "
-"degradatie van het pakket in"
+"downgrading van het pakket in"
 
 #. type: Content of: <refentry><refsect1><refsect2><para><variablelist><varlistentry><term>
 #: apt_preferences.5.xml
@@ -7727,7 +7724,7 @@ msgstr ""
 "\"<literal>&good-perl;</literal>\". Indien er <emphasis>een of andere</"
 "emphasis> &good-perl;* versie van <literal>perl</literal> beschikbaar is en "
 "de geïnstalleerde versie is &bad-perl;*, dan zal <literal>perl</literal> "
-"gedegradeerd worden."
+"gedowngraded worden."
 
 #. type: Content of: <refentry><refsect1><refsect2><para><itemizedlist><listitem><simpara>
 #: apt_preferences.5.xml
@@ -14501,7 +14498,3 @@ msgstr "  # apt-get -o dir::cache::archives=\"/disc/\" dist-upgrade\n"
 msgid "Which will use the already fetched archives on the disc."
 msgstr ""
 "En dit zal gebruik maken van de reeds opgehaalde archieven op de schijf."
-
-#~ msgid "Describes the process of resolving build-dependencies in &apt-get;."
-#~ msgstr ""
-#~ "Beschrijft het proces van het oplossen van bouwvereisten door &apt-get;."
diff --git a/po/apt-all.pot b/po/apt-all.pot
index eb82c25..938b6d3 100644
--- a/po/apt-all.pot
+++ b/po/apt-all.pot
@@ -5,9 +5,9 @@
 #, fuzzy
 msgid ""
 msgstr ""
-"Project-Id-Version: apt 2.9.2\n"
+"Project-Id-Version: apt 2.9.3\n"
 "Report-Msgid-Bugs-To: APT Development Team <deity@lists.debian.org>\n"
-"POT-Creation-Date: 2024-04-22 17:39+0000\n"
+"POT-Creation-Date: 2024-05-14 11:16+0000\n"
 "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
 "Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
 "Language-Team: LANGUAGE <LL@li.org>\n"
diff --git a/po/nl.po b/po/nl.po
index 14d7019..8f32a70 100644
--- a/po/nl.po
+++ b/po/nl.po
@@ -13,10 +13,10 @@
 #
 msgid ""
 msgstr ""
-"Project-Id-Version: apt 2.7.12\n"
+"Project-Id-Version: apt 2.9.1\n"
 "Report-Msgid-Bugs-To: APT Development Team <deity@lists.debian.org>\n"
-"POT-Creation-Date: 2024-04-22 17:39+0000\n"
-"PO-Revision-Date: 2024-02-26 20:56+0100\n"
+"POT-Creation-Date: 2024-04-26 20:11+0000\n"
+"PO-Revision-Date: 2024-04-20 20:28+0200\n"
 "Last-Translator: Frans Spiesschaert <Frans.Spiesschaert@yucom.be>\n"
 "Language-Team: Debian Dutch l10n Team <debian-l10n-dutch@lists.debian.org>\n"
 "Language: nl\n"
@@ -2000,7 +2000,7 @@ msgstr ""
 #: apt-private/private-install.cc
 msgid "Packages were downgraded and -y was used without --allow-downgrades."
 msgstr ""
-"Er werden pakketten gedegradeerd en -y was gebruikt zonder --allow-"
+"Er werden pakketten gedowngraded en -y was gebruikt zonder --allow-"
 "downgrades."
 
 #: apt-private/private-install.cc
@@ -2022,10 +2022,9 @@ msgstr ""
 "org te mailen"
 
 #: apt-private/private-install.cc
-#, fuzzy, c-format
-#| msgid "Download Failed"
+#, c-format
 msgid "  Download size: %sB / %sB\n"
-msgstr "Ophalen mislukt"
+msgstr "  Downloadgrootte: %sB / %sB\n"
 
 #. TRANSLATOR: The required space between number and unit is already included
 #. in the replacement strings, so %sB will be correctly translate in e.g. 1,5 MB
@@ -2035,10 +2034,9 @@ msgid "Need to get %sB/%sB of archives.\n"
 msgstr "Er moeten %sB/%sB aan archieven opgehaald worden.\n"
 
 #: apt-private/private-install.cc
-#, fuzzy, c-format
-#| msgid "Download Failed"
+#, c-format
 msgid "  Download size: %sB\n"
-msgstr "Ophalen mislukt"
+msgstr "  Downloadgrootte: %sB\n"
 
 #. TRANSLATOR: The required space between number and unit is already included
 #. in the replacement string, so %sB will be correctly translate in e.g. 1,5 MB
@@ -2057,7 +2055,7 @@ msgstr "Na deze bewerking zal er %sB extra schijfruimte gebruikt worden.\n"
 #: apt-private/private-install.cc
 #, c-format
 msgid "Space needed: %sB / %sB available\n"
-msgstr ""
+msgstr "Benodigde ruimte: %sB / %sB beschikbaar\n"
 
 #. TRANSLATOR: The required space between number and unit is already included
 #. in the replacement string, so %sB will be correctly translate in e.g. 1,5 MB
@@ -2065,6 +2063,7 @@ msgstr ""
 #, c-format
 msgid "More space needed than available: %sB > %sB, installation may fail"
 msgstr ""
+"Meer ruimte nodig dan beschikbaar: %sB > %sB, de installatie kan mislukken"
 
 #. TRANSLATOR: The required space between number and unit is already included
 #. in the replacement string, so %sB will be correctly translate in e.g. 1,5 MB -
@@ -2074,7 +2073,7 @@ msgstr ""
 #: apt-private/private-install.cc
 #, c-format
 msgid "in %s:  %sB / %sB available\n"
-msgstr ""
+msgstr "in %s:  %sB / %sB beschikbaar\n"
 
 #. TRANSLATOR: The required space between number and unit is already included
 #. in the replacement string, so %sB will be correctly translate in e.g. 1,5 MB
@@ -2084,17 +2083,18 @@ msgstr ""
 msgid ""
 "More space needed in %s than available: %sB > %sB, installation may fail"
 msgstr ""
+"Meer ruimte nodig in %s dan beschikbaar: %sB > %sB, de installatie kan "
+"mislukken"
 
 #: apt-private/private-install.cc
 #, c-format
 msgid "Space needed: %sB\n"
-msgstr ""
+msgstr "Benodigde ruimte: %sB\n"
 
 #: apt-private/private-install.cc
-#, fuzzy, c-format
-#| msgid "Stored label: %s\n"
+#, c-format
 msgid "  Freed space: %sB\n"
-msgstr "Opgeslagen label: %s \n"
+msgstr "  Vrijgemaakte ruimte: %sB\n"
 
 #. TRANSLATOR: The required space between number and unit is already included
 #. in the replacement string, so %sB will be correctly translate in e.g. 1,5 MB
@@ -2117,11 +2117,11 @@ msgstr ""
 
 #: apt-private/private-install.cc
 msgid "Continue anyway?"
-msgstr ""
+msgstr "Toch doorgaan?"
 
 #: apt-private/private-install.cc
 msgid "Continue?"
-msgstr ""
+msgstr "Doorgaan?"
 
 #: apt-private/private-install.cc cmdline/apt-mark.cc
 msgid "Do you want to continue?"
@@ -2362,30 +2362,24 @@ msgid "The following packages have unmet dependencies:"
 msgstr "De volgende pakketten hebben niet-voldane vereisten:"
 
 #: apt-private/private-output.cc
-#, fuzzy
-#| msgid "satisfy dependency strings"
 msgid "Unsatisfied dependencies:"
-msgstr "voldoen aan vereistentekenreeksen"
+msgstr "Niet-voldane vereisten:"
 
 #: apt-private/private-output.cc
 msgid "The following NEW packages will be installed:"
 msgstr "De volgende NIEUWE pakketten zullen geïnstalleerd worden:"
 
 #: apt-private/private-output.cc
-#, fuzzy
-#| msgid "Installing %s"
 msgid "Installing:"
-msgstr "%s wordt geïnstalleerd"
+msgstr "Installeren:"
 
 #: apt-private/private-output.cc
-#, fuzzy
-#| msgid "Total dependencies: "
 msgid "Installing dependencies:"
-msgstr "Totaal aantal vereisten: "
+msgstr "Installeren van vereisten:"
 
 #: apt-private/private-output.cc
 msgid "REMOVING:"
-msgstr ""
+msgstr "VERWIJDEREN:"
 
 #: apt-private/private-output.cc
 msgid "The following packages will be REMOVED:"
@@ -2396,14 +2390,12 @@ msgid "The following upgrades have been deferred due to phasing:"
 msgstr "De volgende opwaarderingen zijn uitgesteld vanwege fasering:"
 
 #: apt-private/private-output.cc
-#, fuzzy
-#| msgid "The following upgrades have been deferred due to phasing:"
 msgid "Not upgrading yet due to phasing:"
-msgstr "De volgende opwaarderingen zijn uitgesteld vanwege fasering:"
+msgstr "Nog niet opgewaardeerd vanwege fasering:"
 
 #: apt-private/private-output.cc
 msgid "Not upgrading:"
-msgstr ""
+msgstr "Niet opgewaardeerd:"
 
 #: apt-private/private-output.cc
 msgid "The following packages have been kept back:"
@@ -2415,21 +2407,19 @@ msgstr "De volgende pakketten zullen opgewaardeerd worden:"
 
 #: apt-private/private-output.cc
 msgid "Upgrading:"
-msgstr ""
+msgstr "Opwaarderen:"
 
 #: apt-private/private-output.cc
 msgid "DOWNGRADING:"
-msgstr ""
+msgstr "DOWNGRADEN:"
 
 #: apt-private/private-output.cc
 msgid "The following packages will be DOWNGRADED:"
-msgstr "De volgende pakketten zullen GEDEGRADEERD worden:"
+msgstr "De volgende pakketten zullen GEDOWNGRADED worden:"
 
 #: apt-private/private-output.cc
-#, fuzzy
-#| msgid "Pinned packages:"
 msgid "Changing held packages:"
-msgstr "Vastgepinde pakketten:"
+msgstr "Veranderen vastgehouden pakketten:"
 
 #: apt-private/private-output.cc
 msgid "The following held packages will be changed:"
@@ -2450,7 +2440,7 @@ msgstr ""
 
 #: apt-private/private-output.cc
 msgid "Summary:"
-msgstr ""
+msgstr "Samenvatting:"
 
 #: apt-private/private-output.cc
 #, c-format
@@ -2458,10 +2448,9 @@ msgid "%lu upgraded, %lu newly installed, "
 msgstr "%lu opgewaardeerd, %lu nieuw geïnstalleerd, "
 
 #: apt-private/private-output.cc
-#, fuzzy, c-format
-#| msgid "Installing %s"
+#, c-format
 msgid "Upgrading: %lu, Installing: %lu, "
-msgstr "%s wordt geïnstalleerd"
+msgstr "Opwaarderen: %lu, Installeren: %lu, "
 
 #: apt-private/private-output.cc
 #, c-format
@@ -2469,20 +2458,19 @@ msgid "%lu reinstalled, "
 msgstr "%lu opnieuw geïnstalleerd, "
 
 #: apt-private/private-output.cc
-#, fuzzy, c-format
-#| msgid "Installing %s"
+#, c-format
 msgid "Reinstalling: %lu, "
-msgstr "%s wordt geïnstalleerd"
+msgstr "Opnieuw installeren: %lu, "
 
 #: apt-private/private-output.cc
 #, c-format
 msgid "%lu downgraded, "
-msgstr "%lu gedegradeerd, "
+msgstr "%lu gedowngraded, "
 
 #: apt-private/private-output.cc
 #, c-format
 msgid "Downgrading: %lu, "
-msgstr ""
+msgstr "Downgraden: %lu, "
 
 #: apt-private/private-output.cc
 #, c-format
@@ -2492,7 +2480,7 @@ msgstr "%lu te verwijderen en %lu niet opgewaardeerd.\n"
 #: apt-private/private-output.cc
 #, c-format
 msgid "Removing: %lu, Not Upgrading: %lu\n"
-msgstr ""
+msgstr "Verwijderen: %lu, Niet opwaarderen: %lu\n"
 
 #: apt-private/private-output.cc
 #, c-format
@@ -4087,7 +4075,7 @@ msgstr "Mislukking bij aanroepen van "
 #: methods/gpgv.cc
 #, c-format
 msgid "untrusted public key algorithm: %s"
-msgstr ""
+msgstr "niet-vertrouwd openbaar sleutelalgoritme: %s"
 
 #. TRANSLATORS: %s is a single techy word like 'NODATA'
 #: methods/gpgv.cc
@@ -4131,12 +4119,9 @@ msgstr ""
 
 #. TRANSLATORS: The second %s is the reason and is untranslated for repository owners.
 #: methods/gpgv.cc
-#, fuzzy, c-format
-#| msgid "Signature by key %s uses weak digest algorithm (%s)"
+#, c-format
 msgid "Signature by key %s uses weak algorithm (%s)"
-msgstr ""
-"De ondertekening door sleutel %s maakt gebruik van een zwak hash-algoritme "
-"(%s)"
+msgstr "Handtekening met sleutel %s gebruikt een zwak algoritme (%s)"
 
 #: methods/gpgv.cc
 msgid "The following signatures were invalid:\n"
@@ -4182,13 +4167,3 @@ msgstr "Verbinding werd voortijdig afgebroken"
 #: methods/store.cc
 msgid "Empty files can't be valid archives"
 msgstr "Lege bestanden kunnen geen geldige archieven zijn"
-
-#, fuzzy, c-format
-#~| msgid "  Installed: "
-#~ msgid "  Installed size: %sB\n"
-#~ msgstr "  Geïnstalleerd: "
-
-#, fuzzy
-#~| msgid "The following held packages will be changed:"
-#~ msgid "Changing held packages:Changing held packages:"
-#~ msgstr "De volgende gehandhaafde pakketten zullen gewijzigd worden:"
diff --git a/test/integration/framework b/test/integration/framework
index 147de98..9cb4081 100644
--- a/test/integration/framework
+++ b/test/integration/framework
@@ -324,6 +324,7 @@ setupenvironment() {
 	unset DEB_CHECK_COMMAND DEB_SIGN_KEYID DEB_BUILD_OPTIONS DEB_BUILD_PROFILES
 	unset DH_VERBOSE DH_QUIET DH_COMPAT DH_NO_ACT DH_OPTIONS DH_EXTRA_ADDONS
 	unset GREP_OPTIONS POSIXLY_CORRECT
+	unset SUDO_USER SUDO_UID SUDO_GID SUDO_COMMAND
 	unset http_proxy HTTP_PROXY https_proxy HTTPS_PROXY no_proxy
 	export GCOV_ERROR_FILE=/dev/null
 
@@ -881,8 +882,12 @@ buildsimplenativepackage() {
                     cp -ar "$FILE_TREE" "${BUILDDIR}/debian/tmp"
                 fi
 
-		(cd "${BUILDDIR}"; dpkg-gencontrol -DArchitecture=$arch)
-		(cd "${BUILDDIR}/debian/tmp"; md5sum $(find usr/ -type f) > DEBIAN/md5sums)
+		if [ ! -e "${BUILDDIR}/debian/tmp/DEBIAN/control" ]; then
+			(cd "${BUILDDIR}"; dpkg-gencontrol -DArchitecture=$arch)
+		fi
+		if [ ! -e "${BUILDDIR}/debian/tmp/DEBIAN/md5sums" ]; then
+			(cd "${BUILDDIR}/debian/tmp"; md5sum $(find usr/ -type f) > DEBIAN/md5sums)
+		fi
 		local LOG="${BUILDDIR}/../${NAME}_${VERSION}_${arch}.dpkg-deb.log"
 		# ensure the right permissions as dpkg-deb insists
 		chmod 755 "${BUILDDIR}/debian/tmp/DEBIAN"
@@ -1548,6 +1553,7 @@ downloadfile() {
 cleanup_output() {
 	cat "$1" | sed \
 		-e '/gpgv: WARNING: This key is not suitable for signing in --compliance=gnupg mode/ d' \
+		-e '/...$/ d' \
 		-e '/^profiling:/ d' \
 		| sed -e '/\.\.\.profiling:/ {N;s#\.\.\.profiling:.*\n#...#g}' \
 			>"$2"
diff --git a/test/integration/test-allow-scores-for-all-dependency-types b/test/integration/test-allow-scores-for-all-dependency-types
index 999efc0..0a527da 100755
--- a/test/integration/test-allow-scores-for-all-dependency-types
+++ b/test/integration/test-allow-scores-for-all-dependency-types
@@ -41,6 +41,7 @@ setupaptarchive
 
 insertinstalledpackage 'libdb-dev' 'amd64' '5.1.7' 'Depends: libdb5.1-dev'
 insertinstalledpackage 'libdb5.1-dev' 'amd64' '5.1.29-7'
+testsuccess aptmark auto ~i
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Calculating upgrade...
@@ -75,6 +76,7 @@ Conf libdb5.3-dev (5.3.28-3 versioned [amd64])' aptget dist-upgrade -st versione
 rm -f rootdir/var/lib/dpkg/status
 insertinstalledpackage 'foo' 'amd64' '1'
 insertinstalledpackage 'bar' 'amd64' '1'
+testsuccess aptmark auto ~i
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Calculating upgrade...
@@ -134,6 +136,7 @@ rm -f rootdir/var/lib/dpkg/status
 insertinstalledpackage 'gdm3' 'amd64' '1' 'Depends: libaudit0, libaudit0'
 insertinstalledpackage 'login' 'amd64' '1' 'Essential: yes'
 insertinstalledpackage 'libaudit0' 'amd64' '1'
+testsuccess aptmark auto ~i
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Calculating upgrade...
diff --git a/test/integration/test-apt-cache-showsrc b/test/integration/test-apt-cache-showsrc
index d3f61d9..0f0e21d 100755
--- a/test/integration/test-apt-cache-showsrc
+++ b/test/integration/test-apt-cache-showsrc
@@ -29,3 +29,9 @@ testsuccess grep "Package: unrelated" output.txt
 aptcache showsrc --only-source foo > output.txt
 testsuccess grep "Package: foo" output.txt
 testfailure grep "Package: unrelated" output.txt
+
+# by default apt-cache showsrc will look into "binary" and "source" names
+# and show all matches
+aptcache showsrc src:foo > output.txt
+testsuccess grep "Package: foo" output.txt
+testfailure grep "Package: unrelated" output.txt
diff --git a/test/integration/test-apt-get-autoremove b/test/integration/test-apt-get-autoremove
index 66257f4..9454df5 100755
--- a/test/integration/test-apt-get-autoremove
+++ b/test/integration/test-apt-get-autoremove
@@ -27,10 +27,6 @@ testdpkginstalled 'po-debconf' 'unrelated'
 echo 'unrelated purge' | dpkg --set-selections
 testdpkgstatus 'pi' '1' 'unrelated'
 
-AUTOREMOVE='apt autoremove'
-if [ -n "$SUDO_USER" ]; then
-	AUTOREMOVE="sudo $AUTOREMOVE"
-fi
 echo 'APT::NeverAutoRemove { "^debc.*nf$"; };' > rootdir/etc/apt/apt.conf.d/00autoremove
 testsuccessequal 'Reading package lists...
 Building dependency tree...
@@ -39,20 +35,28 @@ The following packages will be REMOVED:
   po-debconf
 0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
 Remv po-debconf [1.0.16]' aptget autoremove -s
-testequal "Reading package lists...
+for sudouser in '_apt' ''; do
+	if [ -n "$sudouser" ]; then
+		export SUDO_USER="$sudouser"
+		AUTOREMOVE='sudo apt autoremove'
+	else
+		unset SUDO_USER
+		AUTOREMOVE='apt autoremove'
+	fi
+	testequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 The following package was automatically installed and is no longer required:
   po-debconf
 Use '$AUTOREMOVE' to remove it.
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -s
-testequal "Reading package lists...
+	testequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 1 package was automatically installed and is no longer required.
 Use '$AUTOREMOVE' to remove it.
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -s -o APT::Get::HideAutoRemove=small
-testequal "Reading package lists...
+	testequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 Calculating upgrade...
@@ -60,6 +64,8 @@ The following package was automatically installed and is no longer required:
   po-debconf
 Use '$AUTOREMOVE' to remove it.
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget upgrade -s
+done
+
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Reading state information...
@@ -111,7 +117,7 @@ Reading state information...
 Calculating upgrade...
 The following package was automatically installed and is no longer required:
   po-debconf
-Use '$AUTOREMOVE' to remove it.
+Use 'apt autoremove' to remove it.
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget upgrade -s
 rm -f rootdir/etc/apt/apt.conf.d/autoremoval
 
@@ -163,13 +169,13 @@ Building dependency tree...
 Reading state information...
 The following packages were automatically installed and are no longer required:
   debhelper po-debconf
-Use '$AUTOREMOVE' to remove them.
+Use 'apt autoremove' to remove them.
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -s
 testequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 2 packages were automatically installed and are no longer required.
-Use '$AUTOREMOVE' to remove them.
+Use 'apt autoremove' to remove them.
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -s -o APT::Get::HideAutoRemove=small
 
 testsuccess aptmark hold debhelper
diff --git a/test/integration/test-apt-get-source-only b/test/integration/test-apt-get-source-only
new file mode 100755
index 0000000..93d8284
--- /dev/null
+++ b/test/integration/test-apt-get-source-only
@@ -0,0 +1,114 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+
+setupenvironment
+configarchitecture "amd64"
+
+
+# not-foo builds foo, but foo builds not-foo
+insertpackage 'stable' 'foo' 'amd64' '1.0' 'Source: not-foo'
+insertsource 'stable' 'not-foo' 'amd64' '1.0' 'Build-Depends: not-foo-bd' 'foo'
+
+insertpackage 'stable' 'not-foo' 'amd64' '1.0' 'Source: foo'
+insertsource 'stable' 'foo' 'amd64' '1.0' 'Build-Depends: foo-bd' 'not-foo'
+
+insertinstalledpackage 'build-essential' 'amd64' '1.0'
+
+setupaptarchive
+
+APTARCHIVE=$(readlink -f ./aptarchive)
+
+HEADER='Reading package lists...'
+DOWNLOADFOO="Need to get 0 B/25 B of source archives.
+'file:${APTARCHIVE}/foo_1.0.dsc' foo_1.0.dsc 11 SHA256:ed7c25c832596339bee13e4e7c45cf49f869b60d2bf57252f18191d75866c2a7
+'file:${APTARCHIVE}/foo_1.0.tar.gz' foo_1.0.tar.gz 14 SHA256:f3da8c6ebc62c8ef2dae439a498dddcdacc1a07f45ff67ad12f44b6e2353c239"
+DOWNLOADNOTFOO="Need to get 0 B/33 B of source archives.
+'file:${APTARCHIVE}/not-foo_1.0.dsc' not-foo_1.0.dsc 15 SHA256:db578a571c87d2555e90245732042845be4f481755f5b2f5786ac7a26bde9f4f
+'file:${APTARCHIVE}/not-foo_1.0.tar.gz' not-foo_1.0.tar.gz 18 SHA256:8701846f1cba0ca81c552ac0ec93e2a89ae113cf2872b9cd51b29b4a9ff6b122"
+
+BUILDDEPFOO="Reading package lists...
+Building dependency tree...
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ builddeps:foo : Depends: foo-bd but it is not installable
+E: Unable to correct problems, you have held broken packages."
+
+BUILDDEPNOTFOO="Reading package lists...
+Building dependency tree...
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ builddeps:not-foo : Depends: not-foo-bd but it is not installable
+E: Unable to correct problems, you have held broken packages."
+
+testsuccessequal "$HEADER
+Picking 'not-foo' as source package instead of 'foo'
+$DOWNLOADNOTFOO" aptget source -q --print-uris foo
+
+testsuccessequal "$HEADER
+Picking 'not-foo' as source package instead of 'foo'
+$DOWNLOADNOTFOO" aptget source -q --print-uris foo:amd64
+
+testsuccessequal "$HEADER
+$DOWNLOADNOTFOO" aptget source -q --print-uris --only-source not-foo
+
+testsuccessequal "$HEADER
+$DOWNLOADNOTFOO" aptget source -q --print-uris src:not-foo
+
+testsuccessequal "$HEADER
+Picking 'foo' as source package instead of 'not-foo'
+$DOWNLOADFOO" aptget source -q --print-uris not-foo
+
+testsuccessequal "$HEADER
+Picking 'foo' as source package instead of 'not-foo'
+$DOWNLOADFOO" aptget source -q --print-uris not-foo:amd64
+
+testsuccessequal "$HEADER
+$DOWNLOADFOO" aptget source -q --print-uris --only-source foo
+
+testsuccessequal "$HEADER
+$DOWNLOADFOO" aptget source -q --print-uris src:foo
+
+# Same dance with build-dep
+testequal "$HEADER
+Picking 'not-foo' as source package instead of 'foo'
+$BUILDDEPNOTFOO" aptget build-dep -q -s foo
+
+testequal "$HEADER
+Picking 'not-foo' as source package instead of 'foo'
+$BUILDDEPNOTFOO" aptget build-dep -q -s foo:amd64
+
+testequal "$HEADER
+$BUILDDEPNOTFOO" aptget build-dep -q -s --only-source not-foo
+
+testequal "$HEADER
+$BUILDDEPNOTFOO" aptget build-dep -q -s src:not-foo
+
+testequal "$HEADER
+Picking 'foo' as source package instead of 'not-foo'
+$BUILDDEPFOO" aptget build-dep -q -s not-foo
+
+testequal "$HEADER
+Picking 'foo' as source package instead of 'not-foo'
+$BUILDDEPFOO" aptget build-dep -q -s not-foo:amd64
+
+testequal "$HEADER
+$BUILDDEPFOO" aptget build-dep -q -s --only-source foo
+
+testequal "$HEADER
+$BUILDDEPFOO" aptget build-dep -q -s src:foo
+
+
+
diff --git a/test/integration/test-bug-1069874-working-with-not-normalized-packages b/test/integration/test-bug-1069874-working-with-not-normalized-packages
new file mode 100755
index 0000000..d45acee
--- /dev/null
+++ b/test/integration/test-bug-1069874-working-with-not-normalized-packages
@@ -0,0 +1,57 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+WORKDIR="${TMPWORKINGDIRECTORY}/badcontrol"
+mkdir -p "${WORKDIR}/DEBIAN"
+cat > "${WORKDIR}/DEBIAN/control" << EOF
+Package: perccli
+Version: 007.2616.0000.0000
+Section: perccli
+Priority: optional
+Architecture: all
+Depends: 
+Pre-Depends: 
+Recommends: 
+Suggests: 
+Installed-Size: 7000
+Maintainer: Jane Doe <foo@example.org>
+Conflicts: 
+Replaces: 
+Provides: 
+Description: Not a real package
+EOF
+buildsimplenativepackage 'perccli' 'all' '007.2616.0000.0000' 'stable' '' '' '' '' "${WORKDIR}/DEBIAN"
+cp -a "${WORKDIR}/DEBIAN/control" aptarchive/Packages
+rm -rf "$WORKDIR"
+
+setupaptarchive --no-update
+echo "deb [trusted=yes] file:${TMPWORKINGDIRECTORY}/aptarchive ./" > rootdir/etc/apt/sources.list.d/00badcontrol.list
+testsuccess apt update
+
+# uses the flat Packages file which includes the line ending spaces
+testsuccess aptcache show perccli
+cp -a rootdir/tmp/testsuccess.output perccli.show
+testsuccessequal '4' grep -c '^\(\(Pre-\|\)Depends\|Provides\|Replaces\): \+$' perccli.show
+
+testdpkgnotinstalled perccli
+testsuccess apt install perccli
+testdpkginstalled perccli
+
+testsuccess apt policy perccli
+cp -a rootdir/tmp/testsuccess.output perccli.policy
+testsuccessequal '3' grep -c '7\.2616\.' perccli.policy
+
+# apt-ftparchive outputs empty fields, but not the space ending
+testsuccess rm rootdir/var/lib/apt/lists/*_._Packages
+testsuccess aptcache show perccli/now
+cp -a rootdir/tmp/testsuccess.output perccli.show
+testsuccessequal '4' grep -c '^\(\(Pre-\|\)Depends\|Provides\|Replaces\):$' perccli.show
+
+testsuccess apt policy perccli
+cp -a rootdir/tmp/testsuccess.output perccli.policy
+testsuccessequal '3' grep -c '7\.2616\.' perccli.policy
diff --git a/test/integration/test-bug-604222-new-and-autoremove b/test/integration/test-bug-604222-new-and-autoremove
index 47da810..78a2882 100755
--- a/test/integration/test-bug-604222-new-and-autoremove
+++ b/test/integration/test-bug-604222-new-and-autoremove
@@ -17,26 +17,34 @@ insertpackage 'stable' 'libkf5kipi-bin' 'i386' '4:16.08.0-1'
 insertpackage 'stable' 'libkf5kipi-data' 'i386' '4:16.08.0-1' 'Breaks: libkipi-data'
 insertpackage 'stable' 'libkipi-data' 'i386' '4:15.08.0-1' '' 'important'
 
+insertpackage 'stable' 'libgphoto2-l10n' 'all' '2'
+insertpackage 'installed,stable' 'photoapp1' 'all' '1' 'Recommends: libgphoto2-l10n (= 1)'
+insertinstalledpackage 'photoapp2' 'all' '1'
+insertpackage 'stable' 'photoapp2' 'all' '2' 'Conflicts: photoapp1
+Recommends: libgphoto2-l10n (= 2)'
+
 setupaptarchive
 
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Calculating upgrade...
+The following packages have been kept back:
+  photoapp2
+0 upgraded, 0 newly installed, 0 to remove and 1 not upgraded.' apt upgrade -s
+
 insertinstalledpackage 'libvtk5.4' 'i386' '5.4.2-7'
 testsuccess aptmark markauto 'libvtk5.4'
 testmarkedauto 'libvtk5.4'
 
-AUTOREMOVE='apt autoremove'
-if [ -n "$SUDO_USER" ]; then
-	AUTOREMOVE="sudo $AUTOREMOVE"
-fi
-
 testsuccessequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 The following package was automatically installed and is no longer required:
   libvtk5.4
-Use '$AUTOREMOVE' to remove it.
+Use 'apt autoremove' to remove it.
 The following NEW packages will be installed:
   libavcodec52
-0 upgraded, 1 newly installed, 0 to remove and 1 not upgraded.
+0 upgraded, 1 newly installed, 0 to remove and 2 not upgraded.
 Inst libavcodec52 (4:0.5.2-6 stable [i386])
 Conf libavcodec52 (4:0.5.2-6 stable [i386])" aptget install libavcodec52 -s
 
@@ -44,10 +52,10 @@ testsuccessequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 1 package was automatically installed and is no longer required.
-Use '$AUTOREMOVE' to remove it.
+Use 'apt autoremove' to remove it.
 The following NEW packages will be installed:
   libavcodec52
-0 upgraded, 1 newly installed, 0 to remove and 1 not upgraded.
+0 upgraded, 1 newly installed, 0 to remove and 2 not upgraded.
 Inst libavcodec52 (4:0.5.2-6 stable [i386])
 Conf libavcodec52 (4:0.5.2-6 stable [i386])" aptget install libavcodec52 -s -o APT::Get::HideAutoRemove=small
 
@@ -56,12 +64,12 @@ Building dependency tree...
 Reading state information...
 The following package was automatically installed and is no longer required:
   libvtk5.4
-Use '$AUTOREMOVE' to remove it.
+Use 'apt autoremove' to remove it.
 The following additional packages will be installed:
   libavcodec52 libopenal-dev
 The following NEW packages will be installed:
   dummy-archive libavcodec52 libopenal-dev
-0 upgraded, 3 newly installed, 0 to remove and 1 not upgraded.
+0 upgraded, 3 newly installed, 0 to remove and 2 not upgraded.
 Need to get 0 B/126 B of archives.
 After this operation, 129 kB of additional disk space will be used.
 E: Trivial Only specified but this is not a trivial operation." aptget install dummy-archive --trivial-only
@@ -69,12 +77,12 @@ testequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 1 package was automatically installed and is no longer required.
-Use '$AUTOREMOVE' to remove it.
+Use 'apt autoremove' to remove it.
 The following additional packages will be installed:
   libavcodec52 libopenal-dev
 The following NEW packages will be installed:
   dummy-archive libavcodec52 libopenal-dev
-0 upgraded, 3 newly installed, 0 to remove and 1 not upgraded.
+0 upgraded, 3 newly installed, 0 to remove and 2 not upgraded.
 Need to get 0 B/126 B of archives.
 After this operation, 129 kB of additional disk space will be used.
 E: Trivial Only specified but this is not a trivial operation." aptget install dummy-archive --trivial-only -o APT::Get::HideAutoRemove=small
diff --git a/test/integration/test-bug-611729-mark-as-manual b/test/integration/test-bug-611729-mark-as-manual
index 63f8245..bd9af32 100755
--- a/test/integration/test-bug-611729-mark-as-manual
+++ b/test/integration/test-bug-611729-mark-as-manual
@@ -56,14 +56,8 @@ testdpkginstalled b c
 testmarkedauto 'b'
 
 sed -i rootdir/var/log/apt/history.log -e '/^Commandline: / d' -e '/^Start-Date: / d' -e '/^End-Date: / d'
-if [ -n "$SUDO_USER" ] && [ "$(id -u "$SUDO_USER")" -gt 0 ]; then
-	testfileequal 'rootdir/var/log/apt/history.log' "
-Requested-By: $SUDO_USER ($(id -u "$SUDO_USER"))
-Reinstall: b:i386 (1.0)"
-else
-	testfileequal 'rootdir/var/log/apt/history.log' '
+testfileequal 'rootdir/var/log/apt/history.log' '
 Reinstall: b:i386 (1.0)'
-fi
 
 testsuccessequal 'Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-613420-new-garbage-dependency b/test/integration/test-bug-613420-new-garbage-dependency
index 46c3d94..75a653c 100755
--- a/test/integration/test-bug-613420-new-garbage-dependency
+++ b/test/integration/test-bug-613420-new-garbage-dependency
@@ -16,17 +16,13 @@ setupaptarchive
 touch rootdir/var/lib/apt/extended_states
 testsuccess aptmark markauto openoffice.org-officebean
 testmarkedauto openoffice.org-officebean
-AUTOREMOVE='apt autoremove'
-if [ -n "$SUDO_USER" ]; then
-	AUTOREMOVE="sudo $AUTOREMOVE"
-fi
 
 testfailureequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 The following packages were automatically installed and are no longer required:
   libreoffice-officebean openoffice.org-officebean
-Use '$AUTOREMOVE' to remove them.
+Use 'apt autoremove' to remove them.
 The following additional packages will be installed:
   libreoffice-core libreoffice-officebean openoffice.org-officebean
 The following packages will be REMOVED:
@@ -43,7 +39,7 @@ testequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 2 packages were automatically installed and are no longer required.
-Use '$AUTOREMOVE' to remove them.
+Use 'apt autoremove' to remove them.
 The following additional packages will be installed:
   libreoffice-core libreoffice-officebean openoffice.org-officebean
 The following packages will be REMOVED:
diff --git a/test/integration/test-disappearing-packages b/test/integration/test-disappearing-packages
index f3fed04..f93e10e 100755
--- a/test/integration/test-disappearing-packages
+++ b/test/integration/test-disappearing-packages
@@ -60,23 +60,12 @@ all files have been overwritten by other packages:
 Note: This is done automatically and on purpose by dpkg.' tail -n 4 disappear.output
 
 sed -i rootdir/var/log/apt/history.log -e '/^Commandline: / d' -e '/^Start-Date: / d' -e '/^End-Date: / d' -e "s#:$(getarchitecture 'native') #:native #"
-if [ -n "$SUDO_USER" ] && [ "$(id -u "$SUDO_USER")" -gt 0  ]; then
-	testfileequal 'rootdir/var/log/apt/history.log' "
-Requested-By: $SUDO_USER ($(id -u "$SUDO_USER"))
-Install: old-pkg:native (1)
-
-Requested-By: $SUDO_USER ($(id -u "$SUDO_USER"))
-Install: new-pkg:native (2, automatic)
-Upgrade: old-pkg:native (1, 2)
-Disappeared: old-pkg (1)"
-else
-	testfileequal 'rootdir/var/log/apt/history.log' '
+testfileequal 'rootdir/var/log/apt/history.log' '
 Install: old-pkg:native (1)
 
 Install: new-pkg:native (2, automatic)
 Upgrade: old-pkg:native (1, 2)
 Disappeared: old-pkg (1)'
-fi
 
 testmarkedauto  # new-pkg should have get the manual flag from old-pkg
 
diff --git a/test/integration/test-external-dependency-solver-protocol b/test/integration/test-external-dependency-solver-protocol
index 485a770..ca6a5ae 100755
--- a/test/integration/test-external-dependency-solver-protocol
+++ b/test/integration/test-external-dependency-solver-protocol
@@ -113,17 +113,13 @@ Remv somestuff [1]
 Remv cool [1]
 Remv stuff [1]' aptget autoremove --solver apt somestuff -s
 
-AUTOREMOVE='apt autoremove'
-if [ -n "$SUDO_USER" ]; then
-	AUTOREMOVE="sudo $AUTOREMOVE"
-fi
 testsuccessequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 Execute external solver...
 The following package was automatically installed and is no longer required:
   stuff
-Use '$AUTOREMOVE' to remove it.
+Use 'apt autoremove' to remove it.
 The following packages will be REMOVED:
   cool* somestuff*
 0 upgraded, 0 newly installed, 2 to remove and 1 not upgraded.
diff --git a/test/integration/test-kernel-helper-autoremove b/test/integration/test-kernel-helper-autoremove
index 208bd14..20a0968 100755
--- a/test/integration/test-kernel-helper-autoremove
+++ b/test/integration/test-kernel-helper-autoremove
@@ -45,10 +45,6 @@ testprotected() {
 	testfailure --nomsg grep -e '^\^linux-image-amd64\$$' -e '^\^linux-image-686-pae\$$' -e ':i386' protected.list
 }
 
-AUTOREMOVE='apt autoremove'
-if [ -n "$SUDO_USER" ]; then
-	AUTOREMOVE="sudo $AUTOREMOVE"
-fi
 testsuccessequal "Reading package lists...
 Building dependency tree...
 Reading state information...
@@ -60,7 +56,7 @@ The following packages were automatically installed and are no longer required:
    ${CURRENTKERNEL}+variant (5-1)
    ${CURRENTKERNEL}-686-pae:i386 (5-1)
    ${CURRENTKERNEL}-dbg (5-1)
-Use '$AUTOREMOVE' to remove them.
+Use 'apt autoremove' to remove them.
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -sV -o APT::Protect-Kernels=0
 testsuccessequal "Reading package lists...
 Building dependency tree...
@@ -74,13 +70,13 @@ The following packages were automatically installed and are no longer required:
    ${CURRENTKERNEL}-686-pae:i386 (5-1)
    ${CURRENTKERNEL}-dbg (5-1)
    ${CURRENTKERNEL}-rt (5-1)
-Use '$AUTOREMOVE' to remove them.
+Use 'apt autoremove' to remove them.
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -sV --ignore-hold -o APT::Protect-Kernels=0
 testequal "Reading package lists...
 Building dependency tree...
 Reading state information...
 7 packages were automatically installed and are no longer required.
-Use '$AUTOREMOVE' to remove them.
+Use 'apt autoremove' to remove them.
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded." aptget install -s -o APT::Get::HideAutoRemove=small -o APT::Protect-Kernels=0
 testequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-not-upgrading-removed-depends b/test/integration/test-not-upgrading-removed-depends
new file mode 100755
index 0000000..54b2042
--- /dev/null
+++ b/test/integration/test-not-upgrading-removed-depends
@@ -0,0 +1,50 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertpackage 'unstable' 'untouchable-for-solving' 'all' '1' 'Conflicts: main'
+insertpackage 'installed' 'bad' 'all' '1' 'Depends: main (= 1)'
+insertpackage 'unstable' 'bad' 'all' '2' 'Depends: main (= 2), untouchable-for-solving'
+
+insertpackage 'installed' 'main' 'all' '1'
+insertpackage 'unstable' 'main' 'all' '2' 'Breaks: bad'
+
+insertpackage 'unstable' 'else' 'all' '1'
+insertpackage 'unstable' 'meta' 'all' '1' 'Depends: main (= 2) | else'
+
+setupaptarchive
+
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+The following packages will be REMOVED:
+  bad
+The following packages will be upgraded:
+  main
+1 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
+Remv bad [1]
+Inst main [1] (2 unstable [all])
+Conf main (2 unstable [all])' apt install -s main
+testsuccess apt install -s main -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 -o Debug::pkgDepCache::AutoInstall=1
+testfailure grep 'untouchable-for-solving' rootdir/tmp/testsuccess.output
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+The following additional packages will be installed:
+  main
+The following packages will be REMOVED:
+  bad
+The following NEW packages will be installed:
+  meta
+The following packages will be upgraded:
+  main
+1 upgraded, 1 newly installed, 1 to remove and 0 not upgraded.
+Remv bad [1]
+Inst main [1] (2 unstable [all])
+Inst meta (1 unstable [all])
+Conf main (2 unstable [all])
+Conf meta (1 unstable [all])' apt install -s meta
+testsuccess apt install -s meta -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 -o Debug::pkgDepCache::AutoInstall=1
+testfailure grep 'untouchable-for-solving' rootdir/tmp/testsuccess.output
diff --git a/test/integration/test-suggests-promoted-to-recommends b/test/integration/test-suggests-promoted-to-recommends
new file mode 100755
index 0000000..57497f7
--- /dev/null
+++ b/test/integration/test-suggests-promoted-to-recommends
@@ -0,0 +1,65 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertinstalledpackage 'oldrec' 'all' '1'
+insertinstalledpackage 'oldsug' 'all' '1'
+insertinstalledpackage 'instreg' 'all' '1'
+insertinstalledpackage 'instsug' 'all' '1'
+
+insertpackage 'unstable' 'unsatrec' 'all' '2'
+insertpackage 'unstable' 'unsatsug' 'all' '2'
+insertpackage 'unstable' 'newrec' 'all' '2'
+insertpackage 'unstable' 'newsug' 'all' '2'
+insertpackage 'unstable' 'promote' 'all' '2'
+
+insertinstalledpackage 'foo' 'all' '1' 'Recommends: oldrec, instrec, unsatrec
+Suggests: oldsug, instsug, unsatsug, promote'
+insertpackage 'unstable' 'foo' 'all' '2' 'Recommends: instrec, unsatrec, promote, newrec
+Suggests: instsug, unsatsug, newsug'
+
+setupaptarchive
+
+testsuccess aptmark auto oldrec instrec oldsug instsug
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Reading state information...
+Calculating upgrade...
+The following packages were automatically installed and are no longer required:
+  oldrec oldsug
+Use 'apt autoremove' to remove them.
+The following NEW packages will be installed:
+  newrec promote
+The following packages will be upgraded:
+  foo
+1 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst foo [1] (2 unstable [all])
+Inst newrec (2 unstable [all])
+Inst promote (2 unstable [all])
+Conf foo (2 unstable [all])
+Conf newrec (2 unstable [all])
+Conf promote (2 unstable [all])" apt full-upgrade -s
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Reading state information...
+Calculating upgrade...
+The following packages were automatically installed and are no longer required:
+  oldrec oldsug
+Use 'apt autoremove' to remove them.
+The following NEW packages will be installed:
+  newrec newsug
+The following packages will be upgraded:
+  foo
+1 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst foo [1] (2 unstable [all])
+Inst newrec (2 unstable [all])
+Inst newsug (2 unstable [all])
+Conf foo (2 unstable [all])
+Conf newrec (2 unstable [all])
+Conf newsug (2 unstable [all])" apt full-upgrade -s --install-suggests
diff --git a/vendor/CMakeLists.txt b/vendor/CMakeLists.txt
index f6d8869..615d282 100644
--- a/vendor/CMakeLists.txt
+++ b/vendor/CMakeLists.txt
@@ -1,7 +1,8 @@
 # Determine the current vendor, export to CURRENT_VENDOR
 if (NOT DEFINED CURRENT_VENDOR)
     execute_process(COMMAND ${CMAKE_CURRENT_SOURCE_DIR}/getinfo current
-                    OUTPUT_VARIABLE CURRENT_VENDOR_OUT OUTPUT_STRIP_TRAILING_WHITESPACE)
+                    OUTPUT_VARIABLE CURRENT_VENDOR_OUT OUTPUT_STRIP_TRAILING_WHITESPACE
+                    COMMAND_ERROR_IS_FATAL ANY)
 
     set(CURRENT_VENDOR "${CURRENT_VENDOR_OUT}" CACHE STRING "Select the system vendor")
     message(STATUS "Detected vendor: ${CURRENT_VENDOR_OUT}")