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 +++++++++++------------------------------------------ 1 file changed, 26 insertions(+), 106 deletions(-) (limited to 'apt-pkg/solver3.cc') 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)); } } } -- cgit v1.2.3-70-g09d2