From 3d5f8042c64c30497a65e522c6e402eb4bab10c3 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 6 Feb 2025 10:44:34 +0100 Subject: solver3: Use a package clause for optional roots Instead of iterating over the version here and picking it, just enqueue the package as well, which should allow us to select the version at a later time. This also causes a funny inverse problem now, though, as was evidenced in one of the test cases: To summarize, if our optional roots are all single items, they will be considered soft-unit, causing them to be processed in order. However it can be that an optional root has a specific version selected because another version was rejected. Consider X Conflicts A (= 1) A, B have 2 versions: '2' available, '1' installed B (= n) Depends A (= n) Run `apt install X`. The expected result is for A and B to be upgraded to version 2. With only a package root, if B appears in the cache before A however, we will get: Install X Reject A (= 1) Install B Install B (= 1) # keep it installed Reject A (= 2) => A is being removed as both versions are rejected Hence we do also need to re-introduce the additional version clause, now we get: Install X Reject A (= 1) Install A (= 2) # it got "promoted" to a 'stronger' soft-unit Install B Fail B (= 1) # keep it installed Install B (= 2) Introduce a root state to hold all the clauses that don't have another owner. moo --- apt-pkg/solver3.cc | 24 ++++++++++++++++++++---- 1 file changed, 20 insertions(+), 4 deletions(-) (limited to 'apt-pkg/solver3.cc') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 01d93a6e3..4ebc085a5 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -197,6 +197,7 @@ class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) : cache(cache), policy(policy), + rootState(new State), pkgStates(cache.Head().PackageCount), verStates(cache.Head().VersionCount), pkgObsolete(cache.Head().PackageCount), @@ -205,6 +206,8 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) { static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); + // Root state is "true". + rootState->decision = Decision::MUST; } // This function determines if a work item is less important than another. @@ -218,7 +221,8 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const return clause.group > b.clause.group; if ((size < 2) != (b.size < 2)) return b.size < 2; - + if (size == 1 && b.size == 1) // Special case: 'shortcircuit' optional packages + return clause->solutions.size() < b.clause->solutions.size(); return false; } @@ -966,10 +970,22 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) else { Clause w{Var(), Group, isOptional}; + w.solutions.push_back(Var(P)); + RegisterClause(std::move(w)); + if (not AddWork(Work{*rootState->clauses.back(), depth()})) + return false; + + // Given A->A2|A1, B->B1|B2; Bn->An, if we select `not A1`, we + // should try to install A2 before trying B so we end up with + // A2, B2, instead of removing A1 to keep B1 installed. This + // requires some special casing in Work::operator< above. + // Compare test-bug-712116-dpkg-pre-install-pkgs-hook-multiarch + Clause shortcircuit{Var(), Group, isOptional}; for (auto V = P.VersionList(); not V.end(); ++V) - w.solutions.push_back(Var(V)); - std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this}); - if (not AddWork(Work{std::move(w), depth()})) + shortcircuit.solutions.push_back(Var(V)); + std::stable_sort(shortcircuit.solutions.begin(), shortcircuit.solutions.end(), CompareProviders3{cache, policy, P, *this}); + RegisterClause(std::move(shortcircuit)); + if (not AddWork(Work{rootState->clauses.back().get(), depth()})) return false; } } -- cgit v1.2.3-70-g09d2