From ce454ac0189fab0619feba728764927d975ccc90 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Thu, 13 Jun 2024 21:31:39 +0200 Subject: Merging upstream version 2.9.5. Signed-off-by: Daniel Baumann --- apt-pkg/edsp/edsplistparser.cc | 15 ++++- apt-pkg/solver3.cc | 127 ++++++++++++++++++++++++----------------- apt-pkg/solver3.h | 52 +++++++++++++++-- apt-pkg/tagfile-keys.list | 1 + 4 files changed, 136 insertions(+), 59 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/edsp/edsplistparser.cc b/apt-pkg/edsp/edsplistparser.cc index 5419069..183ace6 100644 --- a/apt-pkg/edsp/edsplistparser.cc +++ b/apt-pkg/edsp/edsplistparser.cc @@ -44,7 +44,20 @@ edspListParser::edspListParser(FileFd * const File) : edspLikeListParser(File) bool edspLikeListParser::NewVersion(pkgCache::VerIterator &Ver) { _system->SetVersionMapping(Ver->ID, Section.FindI("APT-ID", Ver->ID)); - return debListParser::NewVersion(Ver); + if (not debListParser::NewVersion(Ver)) + return false; + + // Patch up the source version, it is stored in the Source-Version field in EDSP. + if (APT::StringView version = Section.Find(pkgTagSection::Key::Source_Version); not version.empty()) + { + if (version != Ver.VerStr()) + { + map_stringitem_t const idx = StoreString(pkgCacheGenerator::VERSIONNUMBER, version); + Ver->SourceVerStr = idx; + } + } + + return true; } /*}}}*/ // ListParser::Description - Return the description string /*{{{*/ diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 9831f7e..dc70adb 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)); @@ -170,33 +177,15 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) // 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(); }); - } + if ((not optional && size < 2) != (not b.optional && b.size < 2)) + return not b.optional && b.size < 2; + if (group != b.group) + return group > b.group; if (optional && b.optional && reason.empty() != b.reason.empty()) return reason.empty(); // 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()) @@ -211,7 +200,7 @@ void APT::Solver::Work::Dump(pkgCache &cache) std::cerr << "Dirty "; if (optional) std::cerr << "Optional "; - std::cerr << "Item (" << size << "@" << depth << (upgrade ? "u" : "") << ") "; + std::cerr << "Item (" << ssize_t(size <= solutions.size() ? size : -1) << "@" << 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) @@ -257,7 +246,27 @@ std::string APT::Solver::WhyStr(Reason reason) return outstr; } -bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason) +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) return true; @@ -286,16 +295,16 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason) (*this)[Pkg] = {reason, depth(), Decision::MUST,}; // Insert the work item. - Work workItem{Reason(Pkg), depth()}; + Work workItem{Reason(Pkg), depth(), 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) AddWork(std::move(workItem)); - else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), workItem.reason)) + else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), workItem.reason, group)) return false; if (not EnqueueCommonDependencies(Pkg)) @@ -304,7 +313,7 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason) return true; } -bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason) +bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason, Group group) { if ((*this)[Ver].decision == Decision::MUST) return true; @@ -339,7 +348,7 @@ bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason) for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV) { - if (OV != Ver && not Reject(OV, Reason(Ver))) + if (OV != Ver && not Reject(OV, Reason(Ver), group)) return false; } @@ -357,7 +366,7 @@ bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason) return true; } -bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason) +bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason, Group group) { if ((*this)[Pkg].decision == Decision::MUSTNOT) return true; @@ -374,7 +383,7 @@ bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason) 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))) + if (not Reject(ver, Reason(Pkg), group)) return false; needsRescore = true; @@ -383,8 +392,10 @@ bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason) } // \brief Do not install this version -bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason) +bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason, Group group) { + (void) group; + if ((*this)[Ver].decision == Decision::MUSTNOT) return true; @@ -473,7 +484,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera 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 */}; + Work workItem{reason, depth(), Group::Satisfy, not start.IsCritical() /* optional */}; do { @@ -489,7 +500,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera 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))) + if (not Reject(pkgCache::VerIterator(cache, *tgt), Reason(Ver), Group::HoldOrDelete)) return false; } else @@ -506,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; @@ -514,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) { @@ -560,6 +577,8 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera return true; } } + else if (workItem.optional && start.ParentPkg()->CurrentVer == 0) + workItem.group = Group::NewUnsatRecommends; if (not workItem.solutions.empty()) { @@ -572,7 +591,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera } if (workItem.optional || workItem.solutions.size() > 1) AddWork(std::move(workItem)); - else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), reason)) + else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), reason, workItem.group)) return false; } else if (start.IsCritical() && not start.IsNegative()) @@ -643,7 +662,7 @@ bool APT::Solver::RejectReverseDependencies(pkgCache::VerIterator Ver) 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))) + if (not Reject(RDV, Reason(Ver), Group::HoldOrDelete)) return false; } return true; @@ -738,7 +757,7 @@ bool APT::Solver::Pop() assert(w.choice != nullptr); // FIXME: There should be a reason! - if (not Reject(pkgCache::VerIterator(cache, w.choice), {})) + if (not Reject(pkgCache::VerIterator(cache, w.choice), {}, Group::HoldOrDelete)) return false; w.choice = nullptr; @@ -857,7 +876,7 @@ bool APT::Solver::Solve() } 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()) + if (not Install(pkgCache::VerIterator(cache, ver), item.reason, Group::Satisfy) && not Pop()) return false; foundSolution = true; break; @@ -905,48 +924,52 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) { if (unlikely(debug >= 1)) std::cerr << "Hold " << P.FullName() << "\n"; - if (P->CurrentVer ? not Install(P.CurrentVer(), {}) : not Reject(P, {})) + if (P->CurrentVer ? not Install(P.CurrentVer(), {}, Group::HoldOrDelete) : not Reject(P, {}, Group::HoldOrDelete)) return false; } else if (reject) { if (unlikely(debug >= 1)) std::cerr << "Delete " << P.FullName() << "\n"; - if (!Reject(P, {})) + if (!Reject(P, {}, Group::HoldOrDelete)) 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), {})) + if (depcache[P].Keep() ? not Install(P, {}, Group::InstallManual) : not Install(depcache.GetCandidateVersion(P), {}, Group::InstallManual)) return false; } else if (maybeInstall && not isOptional) { + auto Upgrade = depcache.GetCandidateVersion(P) != P.CurrentVer(); + auto Group = (Upgrade ? Group::UpgradeManual : Group::InstallManual); if (unlikely(debug >= 1)) std::cerr << "MANUAL " << P.FullName() << "\n"; - if (depcache[P].Keep() ? not Install(P, {}) : not Install(depcache.GetCandidateVersion(P), {})) + if (depcache[P].Keep() ? not Install(P, {}, Group) : not Install(depcache.GetCandidateVersion(P), {}, Group)) return false; } else if (maybeInstall && isOptional && (KeepAuto || rootSet.InRootSet(P) || not isAuto)) { auto Upgrade = depcache.GetCandidateVersion(P) != P.CurrentVer(); + auto Group = isAuto ? (Upgrade ? Group::UpgradeAuto : Group::KeepAuto) + : (Upgrade ? Group::UpgradeManual : Group::InstallManual); 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), {})) + if (depcache[P].Keep() ? not Install(P, {}, Group) : not Install(depcache.GetCandidateVersion(P), {}, Group)) return false; } else { - Work w{Reason(), depth(), true, Upgrade}; + Work w{Reason(), depth(), Group, true, Upgrade}; 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)); } } @@ -954,7 +977,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) { if (unlikely(debug >= 1)) std::cerr << "NOT ALLOWING INSTALL OF " << P.FullName() << "\n"; - if (not Reject(P, {})) + if (not Reject(P, {}, Group::HoldOrDelete)) return false; } } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index cf2fb2e..9a9d67a 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -32,10 +32,46 @@ class Solver enum class Decision : uint16_t; enum class Hint : uint16_t; struct Reason; + struct CompareProviders3; template struct State; struct Work; + // \brief Groups of works, these are ordered. + // + // Later items will be skipped if they are optional, or we will when backtracking, + // try a different choice for them. + enum class Group : uint8_t + { + 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 + // that newer packages guide resolution of dependencies for older ones, they + // may have more stringent dependencies, like a (>> 2) whereas an obsolete + // package may have a (>> 1), for example. + UpgradeManual, + InstallManual, + ObsoleteManual, + + // Automatically installed packages must come last in the group, this allows + // us to see if they were installed as a dependency of a manually installed package, + // allowing a simple implementation of an autoremoval code. + UpgradeAuto, + KeepAuto, + ObsoleteAuto + }; + // \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. @@ -68,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(), @@ -131,13 +170,13 @@ class Solver 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); + bool Install(pkgCache::PkgIterator Pkg, Reason reason, Group group); // \brief Install a version. - bool Install(pkgCache::VerIterator Ver, Reason reason); + bool Install(pkgCache::VerIterator Ver, Reason reason, Group group); // \brief Do not install this package - bool Reject(pkgCache::PkgIterator Pkg, Reason reason); + bool Reject(pkgCache::PkgIterator Pkg, Reason reason, Group group); // \brief Do not install this version. - bool Reject(pkgCache::VerIterator Ver, Reason reason); + bool Reject(pkgCache::VerIterator Ver, Reason reason, Group group); // \brief Apply the selections from the dep cache to the solver bool FromDepCache(pkgDepCache &depcache); @@ -203,7 +242,8 @@ struct APT::Solver::Work Reason reason; // \brief The depth at which the item has been added depth_type depth; - + // \brief The group we are in + Group group; // \brief Possible solutions to this task, ordered in order of preference. std::vector solutions{}; @@ -228,7 +268,7 @@ struct APT::Solver::Work // \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) {} + inline Work(Reason reason, depth_type depth, Group group, bool optional = false, bool upgrade = false) : reason(reason), depth(depth), group(group), size(0), optional(optional), upgrade(upgrade), dirty(false) {} }; // \brief This essentially describes the install state in RFC2119 terms. diff --git a/apt-pkg/tagfile-keys.list b/apt-pkg/tagfile-keys.list index 4b57e46..d198ea0 100644 --- a/apt-pkg/tagfile-keys.list +++ b/apt-pkg/tagfile-keys.list @@ -80,3 +80,4 @@ Vcs-Mtn Vcs-Svn Version ### APPEND BELOW, sort in with next ABI break ### +Source-Version -- cgit v1.2.3