From f870bd44522d195199987b0e073d495eed060495 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 5 Feb 2025 20:11:35 +0100 Subject: solver3: Defer version selection where possible If a dependency can be satisfied by all versions of a package, add the package to the clause instead of the version object. This works only if there are no providers for the package: Providers are quite hard to enumerate over and make sure that all versions of a package satisfy the provider dependency. Implement arbitrary selection between packages and versions for the CompareProviders class: We pick the best version for each package and then pit them against each other. --- test/integration/test-apt-never-markauto-sections | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'test/integration/test-apt-never-markauto-sections') diff --git a/test/integration/test-apt-never-markauto-sections b/test/integration/test-apt-never-markauto-sections index 33b790871..e60a6e648 100755 --- a/test/integration/test-apt-never-markauto-sections +++ b/test/integration/test-apt-never-markauto-sections @@ -49,7 +49,7 @@ Remv foreignpkg:i386 [1] Remv nosection [1] Remv texteditor [1]' aptget autoremove mydesktop -s -testfailuremsg 'E: Conflict: not texteditor:amd64 -> not texteditor:amd64=1 -> not mydesktop-core:amd64=1 but mydesktop:amd64 -> mydesktop-core:amd64=1' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 +testfailuremsg 'E: Conflict: not texteditor:amd64 -> not texteditor:amd64=1 -> not mydesktop-core:amd64=1 but mydesktop:amd64 -> mydesktop-core:amd64 -> mydesktop-core:amd64=1' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 testsuccessequal 'Reading package lists... Building dependency tree... Reading state information... -- cgit v1.2.3-70-g09d2 From b8918cb89ada945d92c720446177f1ef5185b5a5 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 5 Feb 2025 21:31:53 +0100 Subject: solver3: Reject reverse dependencies natively Instead of utilizing the reverse depends functionality of the cache and marking all possible reverse dependencies for removal, mark them ourselves by keeping track of reverse-implication-clauses. Notably, this improves the reverse dependency rejection substantially: The previous RejectReverseDependencies() function did not handle Provides. For this to work correctly right now, we need to discover optional clauses too when queuing them. This is somewhat suboptimal as we technically we don't care if they become unsat, we just waste time tracking them. The tests get a bit awkward, but oh well, we use what we can use. --- apt-pkg/solver3.cc | 132 ++++----------------- apt-pkg/solver3.h | 6 +- test/integration/test-apt-get-build-dep-barbarian | 6 +- test/integration/test-apt-never-markauto-sections | 2 +- .../test-bug-618848-always-respect-user-requests | 2 +- test/integration/test-multiarch-allowed | 12 +- .../test-prefer-higher-priority-providers | 5 +- 7 files changed, 37 insertions(+), 128 deletions(-) (limited to 'test/integration/test-apt-never-markauto-sections') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index d363cdee7..2d9e92c99 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -383,8 +383,25 @@ bool APT::Solver::Propagate() if (not AddWork(Work{clause.get(), depth()})) return false; } - else if ((*this)[var].decision == Decision::MUSTNOT && not PropagateReject(var)) - return false; + else if ((*this)[var].decision == Decision::MUSTNOT) + { + for (auto rclause : (*this)[var].rclauses) + { + if (rclause->negative || rclause->reason.empty() || rclause->optional || + std::any_of(rclause->solutions.begin(), rclause->solutions.end(), [this](auto var) + { return (*this)[var].decision != Decision::MUSTNOT; })) + continue; + + if ((*this)[rclause->reason].decision == Decision::MUSTNOT) + continue; + + if (unlikely(debug >= 3)) + std::cerr << "Propagate NOT " << var.toString(cache) << " to " << rclause->reason.toString(cache) << " for dep " << const_cast(rclause)->toString(cache) << std::endl; + + if (not Enqueue(rclause->reason, false, var)) // Last version invalidated + return false; + } + } } return true; } @@ -393,6 +410,9 @@ void APT::Solver::RegisterClause(Clause &&clause) { auto &clauses = (*this)[clause.reason].clauses; clauses.push_back(std::make_unique(std::move(clause))); + auto const &inserted = clauses.back(); + for (auto var : inserted->solutions) + (*this)[var].rclauses.push_back(inserted.get()); } void APT::Solver::Discover(Var var) @@ -460,43 +480,6 @@ void APT::Solver::Discover(Var var) } } -bool APT::Solver::PropagateReject(Var var) -{ - if (auto Pkg = var.Pkg(cache); not Pkg.end()) - { - for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - if (not Enqueue(Var(ver), false, Var(Pkg))) - return false; - } - else if (auto Ver = var.Ver(cache); not Ver.end()) - { - 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(Var(pkg)).c_str()); - for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++) - if ((*this)[otherVer].decision == Decision::MUSTNOT) - _error->Error("Uninstallable version: %s", WhyStr(Var(otherVer)).c_str()); - return _error->Error("Uninstallable version: %s", WhyStr(Var(Ver)).c_str()); - } - else if (not Enqueue(Var(Ver.ParentPkg()), false, Var(Ver))) // Last version invalidated - return false; - } - if (not RejectReverseDependencies(Ver)) - return false; - } - return true; -} - void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg) { for (auto dep = Pkg.VersionList().DependsList(); not dep.end();) @@ -618,73 +601,6 @@ APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, p return clause; } -// \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 Enqueue(Var(RDV), false, Var(Ver))) - return false; - } - return true; -} - void APT::Solver::Push(Work work) { if (unlikely(debug >= 2)) @@ -1019,6 +935,10 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) RegisterClause(std::move(shortcircuit)); if (not AddWork(Work{rootState->clauses.back().get(), depth()})) return false; + + // Discovery here is needed so the shortcircuit clause can actually become unit. + if (P.VersionList() && P.VersionList()->NextVer) + Discover(Var(P)); } } } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index da75179d5..91b852c98 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -248,14 +248,10 @@ class Solver // \brief Enqueue dependencies shared by all versions of the package. void RegisterCommonDependencies(pkgCache::PkgIterator Pkg); - // \brief Reject reverse dependencies. Must call std::make_heap() after. - [[nodiscard]] bool RejectReverseDependencies(pkgCache::VerIterator Ver); // \brief Translate an or group into a clause object [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); // \brief Propagate all pending propagations [[nodiscard]] bool Propagate(); - // \brief Propagate a rejection of a variable - [[nodiscard]] bool PropagateReject(Var var); // \brief Return the current depth (choices.size() with casting) depth_type depth() @@ -470,6 +466,8 @@ struct APT::Solver::State // \brief Clauses owned by this package/version std::vector> clauses; + // \brief Reverse clauses, that is dependencies (or conflicts) from other packages on this one + std::vector rclauses; }; /** diff --git a/test/integration/test-apt-get-build-dep-barbarian b/test/integration/test-apt-get-build-dep-barbarian index b8ab1211b..e070e96ca 100755 --- a/test/integration/test-apt-get-build-dep-barbarian +++ b/test/integration/test-apt-get-build-dep-barbarian @@ -83,7 +83,7 @@ testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep cool-foo -s testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-foo -s -a i386 testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep bad-armel-foo -s -a i386 testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-armel-foo -s -a i386 -testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-foo:i386=1 -> not foo:i386=1 -> not builddeps:bad-amd64-i386-foo:i386=1 but builddeps:bad-amd64-i386-foo:i386=1' apt build-dep bad-amd64-i386-foo -s -a i386 --solver 3.0 +testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-foo:i386=1 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-foo:i386=1 but builddeps:bad-amd64-i386-foo:i386=1' apt build-dep bad-amd64-i386-foo -s -a i386 --solver 3.0 testfailureequal 'Reading package lists... Reading package lists... Building dependency tree... @@ -96,7 +96,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: builddeps:bad-amd64-i386-foo:i386 : Depends: foo:i386 E: Unable to correct problems, you have held broken packages.' apt build-dep bad-amd64-i386-foo -s -a i386 --solver internal -testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-armel-foo:i386=1 -> not foo:i386=1 -> not builddeps:bad-amd64-i386-armel-foo:i386=1 but builddeps:bad-amd64-i386-armel-foo:i386=1' apt build-dep bad-amd64-i386-armel-foo -s -a i386 --solver 3.0 +testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-armel-foo:i386=1 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:i386=1 but builddeps:bad-amd64-i386-armel-foo:i386=1' apt build-dep bad-amd64-i386-armel-foo -s -a i386 --solver 3.0 testfailureequal 'Reading package lists... Reading package lists... Building dependency tree... @@ -115,7 +115,7 @@ testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-fo testsuccessequal "$(installsfoosamey 'amd64' 'armel')" apt build-dep bad-armel-foo -s -a armel testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-armel-foo -s -a armel testsuccessequal "$(installsfoosamey 'armel' 'armel')" apt build-dep bad-amd64-i386-foo -s -a armel -FAILUREMSG="E: Conflict: builddeps:bad-amd64-i386-armel-foo:armel=1 -> not foo:armel=1 -> not builddeps:bad-amd64-i386-armel-foo:armel=1 but builddeps:bad-amd64-i386-armel-foo:armel=1" +FAILUREMSG="E: Conflict: builddeps:bad-amd64-i386-armel-foo:armel=1 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:armel=1 but builddeps:bad-amd64-i386-armel-foo:armel=1" FAILURE='Reading package lists... Building dependency tree... Some packages could not be installed. This may mean that you have diff --git a/test/integration/test-apt-never-markauto-sections b/test/integration/test-apt-never-markauto-sections index e60a6e648..4d7324b02 100755 --- a/test/integration/test-apt-never-markauto-sections +++ b/test/integration/test-apt-never-markauto-sections @@ -49,7 +49,7 @@ Remv foreignpkg:i386 [1] Remv nosection [1] Remv texteditor [1]' aptget autoremove mydesktop -s -testfailuremsg 'E: Conflict: not texteditor:amd64 -> not texteditor:amd64=1 -> not mydesktop-core:amd64=1 but mydesktop:amd64 -> mydesktop-core:amd64 -> mydesktop-core:amd64=1' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 +testfailuremsg 'E: Conflict: not texteditor:amd64 -> not bad-texteditor:amd64 -> not mydesktop-core:amd64 but mydesktop:amd64 -> mydesktop-core:amd64' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 testsuccessequal 'Reading package lists... Building dependency tree... Reading state information... diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests index 8ba750b44..d59491af6 100755 --- a/test/integration/test-bug-618848-always-respect-user-requests +++ b/test/integration/test-bug-618848-always-respect-user-requests @@ -14,7 +14,7 @@ insertpackage 'unstable' 'exim4-daemon-heavy' 'all' '1.0' 'Depends: libdb4.8' setupaptarchive # This does not work in 3.0 solver: We do not remove manually installed packages. -testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> libdb4.8:i386 but not libdb4.8:i386" aptget remove libdb4.8 --solver 3.0 -s +testfailuremsg "E: Conflict: not libdb4.8:i386 -> not exim4-daemon-light:i386 but exim4-daemon-light:i386" aptget remove libdb4.8 --solver 3.0 -s allowremovemanual testsuccessequal "Reading package lists... Building dependency tree... diff --git a/test/integration/test-multiarch-allowed b/test/integration/test-multiarch-allowed index 9fc49275a..fb8cb653d 100755 --- a/test/integration/test-multiarch-allowed +++ b/test/integration/test-multiarch-allowed @@ -64,24 +64,18 @@ Inst needsfoo:i386 (1 unstable [i386]) Conf foo:i386 (1 unstable [i386]) Conf needsfoo:i386 (1 unstable [i386])' aptget install needsfoo:i386 -s # FIXME: same problem, but two different unmet dependency messages depending on install order -testfailuremsg "E: Conflict: needsfoo:i386=1 -> foo:i386 but no versions are installable -E: Uninstallable version: foo:amd64=1 -> not foo:i386=1 -E: Uninstallable version: foo:amd64=1 -> not foo:i386=1" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0 +testfailuremsg "E: Conflict: foo:amd64=1 -> not foo:i386=1 -> not foo:i386 but needsfoo:i386=1 -> foo:i386" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0 testfailureequal "$BADPREFIX The following packages have unmet dependencies: foo : Conflicts: foo:i386 but 1 is to be installed foo:i386 : Conflicts: foo but 1 is to be installed E: Unable to correct problems, you have held broken packages." aptget install needsfoo:i386 foo:amd64 -s --solver internal -testfailuremsg "E: Conflict: needsfoo:i386=1 -> foo:i386 but no versions are installable -E: Uninstallable version: foo:amd64=1 -> not foo:i386=1 -E: Uninstallable version: foo:amd64=1 -> not foo:i386=1" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0 +testfailuremsg "E: Conflict: foo:amd64=1 -> not foo:i386=1 -> not foo:i386 but needsfoo:i386=1 -> foo:i386" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0 testfailureequal "$BADPREFIX The following packages have unmet dependencies: needsfoo:i386 : Depends: foo:i386 but it is not installable E: Unable to correct problems, you have held broken packages." aptget install foo:amd64 needsfoo:i386 -s --solver internal -testfailuremsg "E: Conflict: needsfoo:amd64=1 -> foo:amd64 but no versions are installable -E: Uninstallable version: foo:i386=1 -> not foo:amd64=1 -E: Uninstallable version: foo:i386=1 -> not foo:amd64=1" aptget install needsfoo foo:i386 -s --solver 3.0 +testfailuremsg "E: Conflict: foo:i386=1 -> not foo:amd64=1 -> not foo:amd64 but needsfoo:amd64=1 -> foo:amd64" aptget install needsfoo foo:i386 -s --solver 3.0 testfailureequal "$BADPREFIX The following packages have unmet dependencies: foo : Conflicts: foo:i386 but 1 is to be installed diff --git a/test/integration/test-prefer-higher-priority-providers b/test/integration/test-prefer-higher-priority-providers index 5fed20a59..76a03b3fb 100755 --- a/test/integration/test-prefer-higher-priority-providers +++ b/test/integration/test-prefer-higher-priority-providers @@ -91,10 +91,7 @@ Inst awesome (1 unstable [all]) Conf baz (1 unstable [all]) Conf awesome (1 unstable [all])" aptget install awesome foo- bar- -s -testfailuremsg "E: Unsatisfiable dependency: awesome:$native=1 -> foo:$native=1 | bar:$native=1 | baz:$native=1 -E: Not considered: foo:$native=1: not foo:$native -> not foo:$native=1 -E: Not considered: bar:$native=1: not bar:$native -> not bar:$native=1 -E: Not considered: baz:$native=1: not baz:$native -> not baz:$native=1" aptget install awesome foo- bar- baz- -s --solver 3.0 +testfailuremsg "E: Conflict: awesome:$native=1 -> baz:$native=1 -> baz:$native but not baz:$native" aptget install awesome foo- bar- baz- -s --solver 3.0 testfailureequal "Reading package lists... Building dependency tree... Package 'foo' is not installed, so not removed -- cgit v1.2.3-70-g09d2 From 2050ecb34a9e18cf1d8edbff8c52d456a7229162 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 12 Feb 2025 20:39:33 +0100 Subject: solver3: Remove work rescoring in favor of unit propagation Instead of expensive rescoring of all outstanding items, use unit propagation to find new units after conflicts. We still count the items when adding them; but unless they are 0 or 1, which they should not be, they don't have any effect: The size field is now effectively static. If the size of an optional clause changed to 1, it is inserted a second time, and then moves up to the top of the optional items per the Work::operator< rules. --- apt-pkg/solver3.cc | 82 +++++++--------------- apt-pkg/solver3.h | 4 -- test/integration/test-apt-never-markauto-sections | 2 +- .../integration/test-bug-604222-new-and-autoremove | 1 - ...960705-propagate-protected-to-satisfied-depends | 1 - test/integration/test-bug-961266-hold-means-hold | 2 +- 6 files changed, 28 insertions(+), 64 deletions(-) (limited to 'test/integration/test-apt-never-markauto-sections') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 06008fb5d..945d912db 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -365,9 +365,6 @@ bool APT::Solver::Enqueue(Var var, bool decision, Var reason) solved.push_back(Solved{var, std::nullopt}); propQ.push(var); - if (not decision) - needsRescore = true; - return true; } @@ -397,14 +394,36 @@ bool APT::Solver::Propagate() { for (auto rclause : (*this)[var].rclauses) { - if (rclause->negative || rclause->reason.empty() || rclause->optional || - std::any_of(rclause->solutions.begin(), rclause->solutions.end(), [this](auto var) - { return (*this)[var].decision != Decision::MUSTNOT; })) + if (rclause->negative || rclause->reason.empty()) continue; - if ((*this)[rclause->reason].decision == Decision::MUSTNOT) continue; + auto count = std::count_if(rclause->solutions.begin(), rclause->solutions.end(), [this](auto var) + { return (*this)[var].decision != Decision::MUSTNOT; }); + + if (count == 1 && (*this)[rclause->reason].decision == Decision::MUST) + { + if (unlikely(debug >= 3)) + std::cerr << "Propagate NOT " << var.toString(cache) << " to unit clause " << rclause->toString(cache); + if (rclause->optional) + { + // Enqueue duplicated item, this will ensure we see it at the correct time + if (not AddWork(Work{rclause, depth()})) + return false; + } + else + { + // Find the variable that must be chosen and enqueue it as a fact + for (auto sol : rclause->solutions) + if ((*this)[sol].decision == Decision::NONE && not Enqueue(sol, true, rclause->reason)) + return false; + } + continue; + } + if (count >= 1 || rclause->optional) + continue; + if (unlikely(debug >= 3)) std::cerr << "Propagate NOT " << var.toString(cache) << " to " << rclause->reason.toString(cache) << " for dep " << const_cast(rclause)->toString(cache) << std::endl; @@ -740,40 +759,6 @@ bool APT::Solver::AddWork(Work &&w) return true; } -void APT::Solver::RescoreWorkIfNeeded() -{ - if (not needsRescore) - return; - - needsRescore = false; - std::vector resized; - for (auto &w : work) - { - if (w.erased) - continue; - size_t newSize = std::count_if(w.clause->solutions.begin(), w.clause->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.erased = 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() { startTime = time(nullptr); @@ -788,8 +773,6 @@ bool APT::Solver::Solve() if (work.empty()) break; - // Rescore the work if we need to - RescoreWorkIfNeeded(); // *NOW* we can pop the item. std::pop_heap(work.begin(), work.end()); @@ -799,19 +782,6 @@ bool APT::Solver::Solve() work.pop_back(); continue; } - - // If our size increased, queue again. - size_t newSize = std::count_if(work.back().clause->solutions.begin(), work.back().clause->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(Solved{Var(), item}); diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 796f198b1..d4a584f2d 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -193,8 +193,6 @@ class Solver // 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 Backlog of solved work. // @@ -271,8 +269,6 @@ class Solver void UndoOne(); // \brief Add work to our work queue. [[nodiscard]] bool 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, EDSP::Request::Flags requestFlags); diff --git a/test/integration/test-apt-never-markauto-sections b/test/integration/test-apt-never-markauto-sections index 4d7324b02..95ba47553 100755 --- a/test/integration/test-apt-never-markauto-sections +++ b/test/integration/test-apt-never-markauto-sections @@ -49,7 +49,7 @@ Remv foreignpkg:i386 [1] Remv nosection [1] Remv texteditor [1]' aptget autoremove mydesktop -s -testfailuremsg 'E: Conflict: not texteditor:amd64 -> not bad-texteditor:amd64 -> not mydesktop-core:amd64 but mydesktop:amd64 -> mydesktop-core:amd64' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 +testfailuremsg 'E: Conflict: not texteditor:amd64 -> not bad-texteditor:amd64 but mydesktop:amd64 -> mydesktop-core:amd64 -> bad-texteditor:amd64' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 testsuccessequal 'Reading package lists... Building dependency tree... Reading state information... diff --git a/test/integration/test-bug-604222-new-and-autoremove b/test/integration/test-bug-604222-new-and-autoremove index 1bd7c5101..8f464ae15 100755 --- a/test/integration/test-bug-604222-new-and-autoremove +++ b/test/integration/test-bug-604222-new-and-autoremove @@ -103,7 +103,6 @@ Solving dependencies...MANUAL dummy-archive:i386 [0] Install:libavcodec52:i386=4:0.5.2-6 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386) [0] Reject:libvtk5-dev:i386=5.4.2-8 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386) [0] Reject:libvtk5-dev:i386 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386 -> not libvtk5-dev:i386=5.4.2-8) -Item (1@0) dummy-archive:i386=0.invalid.0 -> | libvtk5-dev:i386 | libopenal-dev:i386 [0] Install:libopenal-dev:i386 (dummy-archive:i386=0.invalid.0) [0] Install:libopenal-dev:i386=1:1.12.854-2 (dummy-archive:i386=0.invalid.0 -> libopenal-dev:i386) diff --git a/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends index 1e59967e4..2f82e9df0 100755 --- a/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends +++ b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends @@ -31,7 +31,6 @@ Solving dependencies...Install foobar:amd64 () [0] Reject:conflicts-foo:amd64 (foobar:amd64=1 -> requires-foo:amd64 -> foo:amd64 -> foo:amd64=1) [0] Reject:conflicts-foo:amd64=1 (foobar:amd64=1 -> requires-foo:amd64 -> foo:amd64 -> foo:amd64=1) [0] Install:foo-depends:amd64=1 (foobar:amd64=1 -> requires-foo:amd64 -> foo:amd64 -> foo-depends:amd64) -Item (1@0) foobar:amd64=1 -> | conflicts-foo:amd64 | fine-foo:amd64 [0] Install:fine-foo:amd64 (foobar:amd64=1) [0] Install:fine-foo:amd64=1 (foobar:amd64=1 -> fine-foo:amd64) diff --git a/test/integration/test-bug-961266-hold-means-hold b/test/integration/test-bug-961266-hold-means-hold index 7713760d6..b33a5aca7 100755 --- a/test/integration/test-bug-961266-hold-means-hold +++ b/test/integration/test-bug-961266-hold-means-hold @@ -126,7 +126,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: git-ng : Depends: git (> 1:2.26.2) -E: Conflict: git-cvs:amd64=1:2.25.1-1 -> git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 -> not git-ng:amd64=1:2.26.2-1 but git-ng:amd64=1:2.26.2-1' apt install git-ng -s --solver 3.0 +E: Conflict: git-cvs:amd64=1:2.25.1-1 -> git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 but git-ng:amd64=1:2.26.2-1 -> git:amd64=1:2.26.2-1' apt install git-ng -s --solver 3.0 msgmsg 'Now mix it up by' 'holding both' -- cgit v1.2.3-70-g09d2