From 55158daa5b13e2f61658a1678288e5848bd2927a Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Tue, 14 May 2024 21:18:39 +0200 Subject: Merging upstream version 2.9.3. Signed-off-by: Daniel Baumann --- apt-pkg/CMakeLists.txt | 12 +- apt-pkg/contrib/error.cc | 6 +- apt-pkg/deb/deblistparser.cc | 2 +- apt-pkg/depcache.cc | 7 +- apt-pkg/edsp.cc | 13 + apt-pkg/solver3.cc | 960 +++++++++++++++++++++++++++++++++++++++++++ apt-pkg/solver3.h | 286 +++++++++++++ apt-pkg/upgrade.cc | 5 + 8 files changed, 1282 insertions(+), 9 deletions(-) create mode 100644 apt-pkg/solver3.cc create mode 100644 apt-pkg/solver3.h (limited to 'apt-pkg') 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 "" --include "" - "${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 #include #include +#include #include #include #include @@ -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 + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include + +// 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 archs = APT::Configuration::getArchitectures(); + for (std::vector::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 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) == 3 * sizeof(int)); + static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int)); + static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer)); + static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer)); +} + +// 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 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 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 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 + +#include +#include +#include +#include + +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 + 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 + using heap = std::vector; + + 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> pkgStates{}; + // States for versions + std::vector> verStates{}; + + // \brief Helper function for safe access to package state. + inline State &operator[](pkgCache::Package *P) + { + return pkgStates[P->ID]; + } + + // \brief Helper function for safe access to version state. + inline State &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{}; + // \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 choices{}; + // \brief Backlog of solved work. + // + // Solved work may become invalidated when backtracking, so store it + // here to revisit it later. + std::vector 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(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 Pkg() const + { + return IsVersion ? 0 : map_pointer{(uint32_t)MapPtr}; + } + // \brief Return the version, if any, otherwise 0. + map_pointer Ver() const + { + return IsVersion ? map_pointer{(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 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 +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) -- cgit v1.2.3