From bfb9f2124b8f9da48b53d279278de3f8f0a00b82 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 6 Jun 2024 11:40:14 +0200 Subject: Make the failure mode for non-executable tests stronger When a test-* file is created but not executable, we'd ignore the argument and then our subprocess would run the entire test suite itself, sequentially. Silly. Let's just see if the file exists instead, then the test will fail. --- test/integration/run-tests | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/test/integration/run-tests b/test/integration/run-tests index 3100e8e05..331adfcfa 100755 --- a/test/integration/run-tests +++ b/test/integration/run-tests @@ -31,7 +31,7 @@ while [ -n "$1" ]; do elif [ "$1" = '--only' ]; then TESTLIST="$2" shift - elif [ -x "$1" ]; then + elif [ -e "$1" ]; then TESTTORUN="$1" else echo >&2 "WARNING: Unknown parameter »$1« will be ignored" -- cgit v1.2.3-70-g09d2 From 5502c0bc5754499e82a1e03ca5a24779adb6f485 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sat, 25 May 2024 13:46:52 +0200 Subject: solver3: Do not dump sizes that are clearly pointers We use a union here, but we don't know if we last stored a pointer, so let's just reject clearly non-sizes. Generally this will work fine -- you will not have enough choices in a dependency that you can construct a valid pointer to a Version*, especially given that any Version * > sizeof(pkgCache::Header) already, given it is in the cache. --- apt-pkg/solver3.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 9831f7e14..f851a98b8 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -211,7 +211,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) -- cgit v1.2.3-70-g09d2 From 102017ecaa01a733a0860a62edae60cb0ab0220e Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sat, 25 May 2024 09:45:39 +0200 Subject: solver3: Group work items Our backtracking is chronological, so we will first try alternative choices or skip optional items in later groups. So installing manually installed packages before automatically installed ones allows manually installed packages to remove automatically installed packages easily. If we did automatic packages first, we'd keep back upgrades for manual packages or change choices for their dependencies, or would have to backtrack harder to get back to the right decision level. That's silly. Ordering automatically installed packages last also allows us to calculate autoremovable packages. Since we will have installed all dependencies from manually installed packages by the point where we get to automatically installed packages, everything that will be installed in those Auto groups is inherently garbage. --- apt-pkg/solver3.cc | 54 +++++++++++++++++++++++++++++++++--------------------- apt-pkg/solver3.h | 40 ++++++++++++++++++++++++++++++++++------ 2 files changed, 67 insertions(+), 27 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index f851a98b8..336a24a2d 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -170,6 +170,10 @@ 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 ((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() && upgrade != b.upgrade) { // Assuming we have libfoo-dev=5.1 Depends libfoo5.1-dev upgrade to libfoo-dev=5.3 Depends libfoo5.3-dev, @@ -257,7 +261,7 @@ std::string APT::Solver::WhyStr(Reason reason) return outstr; } -bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason) +bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason, Group group) { if ((*this)[Pkg].decision == Decision::MUST) return true; @@ -286,7 +290,7 @@ 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); @@ -295,7 +299,7 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason) 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 +308,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 +343,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 +361,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 +378,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 +387,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 +479,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 +495,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 @@ -560,6 +566,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 +580,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 +651,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 +746,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 +865,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,44 +913,48 @@ 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); @@ -954,7 +966,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 cf2fb2ecc..c3f191b18 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -36,6 +36,33 @@ class Solver 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, + Satisfy, + + // 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. @@ -131,13 +158,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 +230,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 +256,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. -- cgit v1.2.3-70-g09d2 From 3b5379e547dfb655d764f7eb1ac7eaa5b2d34d6d Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 6 Jun 2024 11:17:09 +0200 Subject: solver3: Remove no longer necessary comparisons Comparing the size of work items is not strictly needed; we check if items have a single or no solution and propagate them early on, but it doesn't matter much if we solve A|B or C|D|E first. This will allow us to get rid of all the resizing business later on, and switch to using literal watching where we only watch one of the literals on the right hand side. Likewise, the upgrade case mattered initially in testing, but seems to have resolved itself. --- apt-pkg/solver3.cc | 22 ---------------------- 1 file changed, 22 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 336a24a2d..e86353e43 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -174,33 +174,11 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const return not b.optional && b.size < 2; if (group != b.group) return group > b.group; - 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 (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()) -- cgit v1.2.3-70-g09d2 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 ++++++ test/integration/test-resolver-provider-exchange | 1 + 3 files changed, 54 insertions(+), 8 deletions(-) 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(), diff --git a/test/integration/test-resolver-provider-exchange b/test/integration/test-resolver-provider-exchange index 45d936978..2874b88e4 100755 --- a/test/integration/test-resolver-provider-exchange +++ b/test/integration/test-resolver-provider-exchange @@ -8,6 +8,7 @@ allowremovemanual configarchitecture 'amd64' insertinstalledpackage 'fuse' 'all' '2' +insertpackage 'unstable' 'fuse' 'all' '2' insertpackage 'unstable' 'fuse3' 'all' '3' 'Conflicts: fuse Provides: fuse' -- cgit v1.2.3-70-g09d2