From 6708203296911800caf94bb94ce204d3a39af0bd Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 6 Jun 2024 11:19:04 +0200 Subject: solver3: Order obsolete choices last This has two aspects: 1. For a dependency A | B | C we order the obsolete packages last, that is, if A is obsolete, this gets reordered to B | C | A, such that we try to pick non-obsolete packages first to ease upgrade calculation. 2. When comparing two dependencies, we order dependencies into three groups: First we satisfy dependencies mentioning only non-installed (NEW) packages, then we satisfy "normal" dependencies, and finally we satisfy any dependencies mentioning obsolete packages. This means for example if you have obsolete libfoo1 and a new libfoo1t64, that we will see Depends: libfoo1t64 before any Depends: libfoo1 (which may expand to libfoo1 | libfoo1t64), so we effectively will have selected "replacement" packages this way already before getting to older packages where we would have to choose between the obsolete package and its replacement. --- apt-pkg/solver3.cc | 49 +++++++++++++++++++++++++++++++++++++++++-------- apt-pkg/solver3.h | 12 ++++++++++++ 2 files changed, 53 insertions(+), 8 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index e86353e43..dc70adbde 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -26,11 +26,12 @@ #include // FIXME: Helpers stolen from DepCache, please give them back. -struct CompareProviders3 /*{{{*/ +struct APT::Solver::CompareProviders3 /*{{{*/ { pkgCache &Cache; pkgDepCache::Policy &Policy; pkgCache::PkgIterator const Pkg; + APT::Solver &Solver; bool upgrade{_config->FindB("APT::Solver::Upgrade", false)}; bool operator()(pkgCache::Version *AV, pkgCache::Version *BV) @@ -60,6 +61,11 @@ struct CompareProviders3 /*{{{*/ return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0; } + // Try obsolete choices only after exhausting non-obsolete choices such that we install + // packages replacing them and don't keep back upgrades depending on the replacement to + // keep the obsolete package installed. + if (auto obsoleteAV = Solver.Obsolete(AV), obsoleteBV = Solver.Obsolete(BV); obsoleteAV != obsoleteBV) + return obsoleteBV; // 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) @@ -158,8 +164,9 @@ class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) : cache(cache), policy(policy), - pkgStates{cache.Head().PackageCount}, - verStates{cache.Head().VersionCount} + pkgStates(cache.Head().PackageCount), + verStates(cache.Head().VersionCount), + verObsolete(cache.Head().VersionCount) { static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int)); static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int)); @@ -239,6 +246,26 @@ std::string APT::Solver::WhyStr(Reason reason) return outstr; } +bool APT::Solver::Obsolete(pkgCache::VerIterator ver) +{ + if (verObsolete[ver->ID] != 0) + return verObsolete[ver->ID] == 2; + for (auto bin = ver.Cache()->FindGrp(ver.SourcePkgName()).VersionsInSource(); not bin.end(); bin = bin.NextInSource()) + if (bin != ver && bin.ParentPkg()->Arch == ver.ParentPkg()->Arch && bin->ParentPkg != ver->ParentPkg && policy.GetCandidateVer(bin.ParentPkg()) == bin && _system->VS->CmpVersion(bin.SourceVerStr(), ver.SourceVerStr()) > 0) + { + verObsolete[ver->ID] = 2; + return true; + } + for (auto file = ver.FileList(); !file.end(); file++) + if ((file.File()->Flags & pkgCache::Flag::NotSource) == 0) + { + verObsolete[ver->ID] = 1; + return false; + } + verObsolete[ver->ID] = 2; + return true; +} + bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason, Group group) { if ((*this)[Pkg].decision == Decision::MUST) @@ -272,7 +299,7 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason, Group group) for (auto ver = Pkg.VersionList(); not ver.end(); ver++) if (IsAllowedVersion(ver)) workItem.solutions.push_back(ver); - std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg}); + std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg, *this}); assert(workItem.solutions.size() > 0); if (workItem.solutions.size() > 1 || workItem.optional) @@ -490,7 +517,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera // FIXME: This is not really true, though, we should fix the CompareProviders to ignore the // installed state if (fixPolicy) - std::stable_sort(workItem.solutions.begin() + begin, workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg}); + std::stable_sort(workItem.solutions.begin() + begin, workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); if (start == end) break; @@ -498,8 +525,14 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera } while (1); if (not fixPolicy) - std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg}); - + std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); + + if (std::all_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto V) -> auto + { return pkgCache::VerIterator(cache, V).ParentPkg()->CurrentVer == 0; })) + workItem.group = Group::SatisfyNew; + if (std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto V) -> auto + { return Obsolete(pkgCache::VerIterator(cache, V)); })) + workItem.group = Group::SatisfyObsolete; // Try to perserve satisfied Recommends. FIXME: We should check if the Recommends was there in the installed version? if (workItem.optional && start.ParentPkg()->CurrentVer) { @@ -936,7 +969,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) for (auto V = P.VersionList(); not V.end(); ++V) if (IsAllowedVersion(V)) w.solutions.push_back(V); - std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P}); + std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this}); AddWork(std::move(w)); } } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index c3f191b18..9a9d67a02 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -32,6 +32,7 @@ class Solver enum class Decision : uint16_t; enum class Hint : uint16_t; struct Reason; + struct CompareProviders3; template struct State; struct Work; @@ -44,7 +45,15 @@ class Solver { HoldOrDelete, NewUnsatRecommends, + + // Satisfying dependencies on entirely new packages first is a good idea because + // it may contain replacement packages like libfoo1t64 whereas we later will see + // Depends: libfoo1 where libfoo1t64 Provides libfoo1 and we'd have to choose. + SatisfyNew, Satisfy, + // On a similar note as for SatisfyNew, if the dependency contains obsolete packages + // try it last. + SatisfyObsolete, // My intuition tells me that we should try to schedule upgrades first, then // any non-obsolete installed packages, and only finally obsolete ones, such @@ -95,6 +104,9 @@ class Solver return verStates[V->ID]; } + std::vector verObsolete; + bool Obsolete(pkgCache::VerIterator ver); + // \brief Heap of the remaining work. // // We are using an std::vector with std::make_heap(), std::push_heap(), -- cgit v1.2.3-70-g09d2