From eafc52e942d4daec30fb80e70c035ed935f31afb Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 27 May 2025 14:24:09 +0200 Subject: solver3: Merge intersecting dependencies If a package declares multiple dependencies that can be solved by the same packages we should use the common set of packages to solve them. A common example is requiring the same Debian source version, or the same upstream version as in our test case: git-ng Depends: git (>> 1:2.26.2), git (<< 1:2.26.2-.) The solver expands this to the concrete objects: git-ng Depends: "real git" (= 1:2.26.2-1) | chaos-actor, "real git" (= 1:2.26.2-1) | "real git" (= 1:2.25.1-1) When given an upgrade request, the solver would now choose chaos-actor to satisfy git (>> 1:2.26.2) "real git" (= 1:2.25.1-1) to satisfy git (<< 1:2.26.2-.) To satisfy the two constraints, which is not the intended outcome. Address this problem by introducing a concept of merged clauses: If two dependencies of a package have overlapping solutions, replace the dependency by the intersection, and record the merged clause instead, this leads to a single clause: Depends: git (>> 1:2.26.2) and git (<< 1:2.26.2-.) which expands to just the real git binary. The implementation is a bit finicky in that it removes the variables from the original clause which may not be helpful for debugging, but it records the clauses merged with, as seen in the test case, so the reasoning is clear. LP: #2111792 --- apt-pkg/solver3.cc | 50 +++++++++++++++++++++++++++++++++++++++++++++----- apt-pkg/solver3.h | 5 ++++- 2 files changed, 49 insertions(+), 6 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index be1576e98..c4c28b273 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -232,10 +232,11 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const return false; } -std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty) const +std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty, bool showMerged) const { std::string out; - out.append(reason.toString(cache)); + if (showMerged) + out.append(reason.toString(cache)); if (dep && pretty) { out.append(" ").append(pkgCache::DepIterator(cache, dep).DepType()).append(" "); @@ -266,6 +267,14 @@ std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty) const for (auto var : solutions) out.append(" | ").append(var.toString(cache)); } + if (showMerged && not merged.empty()) + { + for (auto &clause : merged) + { + out.append(" and"); + out.append(clause.toString(cache, pretty, false)); + } + } return out; } @@ -664,6 +673,37 @@ static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b) const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause) { auto &clauses = (*this)[clause.reason].clauses; + + if (not clause.negative) + { + // If we get multiple dependencies of the same class on related sets of packages, + // intersect them. In particular this deals with dependencies of the form + // Depends: pkg (>= 1-1), pkg (<= 1-1.1) + // which is a common pattern used to express dependencies on the same source version. + bool merged = false; + for (auto const &earlierClause : clauses) + { + if (earlierClause->negative || earlierClause->optional != clause.optional) + continue; + if (std::none_of(earlierClause->solutions.begin(), earlierClause->solutions.end(), [&clause](auto earlierSol) + { return std::find(clause.solutions.begin(), + clause.solutions.end(), + earlierSol) != clause.solutions.end(); })) + continue; + + std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol) + { return std::find(clause.solutions.begin(), + clause.solutions.end(), + earlierSol) == clause.solutions.end(); }); + + earlierClause->merged.push_front(clause); + merged = true; + } + + if (merged) + return nullptr; + } + clauses.push_back(std::make_unique(std::move(clause))); auto const &inserted = clauses.back(); for (auto var : inserted->solutions) @@ -1173,7 +1213,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) Clause w{Var(), Group, isOptional}; w.solutions.push_back(Var(P)); auto insertedW = RegisterClause(std::move(w)); - if (not AddWork(Work{insertedW, depth()})) + if (insertedW && not AddWork(Work{insertedW, depth()})) return false; if (not isAuto) @@ -1189,7 +1229,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) shortcircuit.solutions.push_back(Var(V)); std::stable_sort(shortcircuit.solutions.begin(), shortcircuit.solutions.end(), CompareProviders3{cache, policy, P, *this}); auto insertedShort = RegisterClause(std::move(shortcircuit)); - if (not AddWork(Work{insertedShort, depth()})) + if (insertedShort && not AddWork(Work{insertedShort, depth()})) return false; // Discovery here is needed so the shortcircuit clause can actually become unit. @@ -1208,7 +1248,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) if (unlikely(debug >= 1)) std::cerr << "Install essential package " << P << std::endl; auto inserted = RegisterClause(std::move(w)); - if (not AddWork(Work{inserted, depth()})) + if (inserted && not AddWork(Work{inserted, depth()})) return false; } } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 590b187cc..a333d684a 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -404,9 +404,12 @@ struct APT::Solver::Clause // \brief A negative clause negates the solutions, that is X->A|B you get X->!(A|B), aka X->!A&!B bool negative; + // Clauses merged with this clause + std::forward_list merged; + inline Clause(Var reason, Group group, bool optional = false, bool negative = false) : reason(reason), group(group), optional(optional), negative(negative) {} - std::string toString(pkgCache &cache, bool pretty = false) const; + std::string toString(pkgCache &cache, bool pretty = false, bool showMerged = true) const; }; /** -- cgit v1.2.3-70-g09d2 From 86c44166b470ecee5a192ffb434fb7931b7c0afd Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 27 May 2025 14:24:09 +0200 Subject: solver3: Merge Depends into Recommends Merge any hard clauses into optional clauses, such that optional clauses don't end up with more choices. For example if you have Depends: a | b Recommends: a | c This becomes: Depends: a | b Recommends: a We have simulated this with the chaos-actor in the test case and a Depends: git (not satisfied by chaos provider) Recommends: git (satisfied by chaos provider) and the latter constraint is limited to the former. --- apt-pkg/solver3.cc | 30 +++++++++++++++++----- ...st-ubuntu-bug-2111792-intersecting-dependencies | 13 ++++++++++ 2 files changed, 36 insertions(+), 7 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index c4c28b273..95cff96f3 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -683,7 +683,7 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause) bool merged = false; for (auto const &earlierClause : clauses) { - if (earlierClause->negative || earlierClause->optional != clause.optional) + if (earlierClause->negative) continue; if (std::none_of(earlierClause->solutions.begin(), earlierClause->solutions.end(), [&clause](auto earlierSol) { return std::find(clause.solutions.begin(), @@ -691,13 +691,29 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause) earlierSol) != clause.solutions.end(); })) continue; - std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol) - { return std::find(clause.solutions.begin(), - clause.solutions.end(), - earlierSol) == clause.solutions.end(); }); + if (earlierClause->optional == clause.optional) + { + std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol) + { return std::find(clause.solutions.begin(), + clause.solutions.end(), + earlierSol) == clause.solutions.end(); }); - earlierClause->merged.push_front(clause); - merged = true; + earlierClause->merged.push_front(clause); + merged = true; + } + else if (clause.optional) + { + // If say a Depends has fewer solution than a Recommends, remove the Recommend's extranous ones. + std::erase_if(clause.solutions, [&earlierClause, this](auto sol) + { return std::find(earlierClause->solutions.begin(), + earlierClause->solutions.end(), + sol) == earlierClause->solutions.end(); }); + + // Remove recursion here, such that we display correctly (if we ever display anywhere...) + auto earlierClauseCopy = *earlierClause; + clause.merged = std::move(earlierClauseCopy.merged); + clause.merged.push_front(earlierClauseCopy); + } } if (merged) diff --git a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies index 4f58893bf..86866b233 100755 --- a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies +++ b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies @@ -20,6 +20,8 @@ insertinstalledpackage 'git-cvs' 'amd64' '1:2.25.1-1' 'Depends: git (>> 1:2.25.1 insertpackage 'unstable' 'git' 'amd64,i386' '1:2.26.2-1' 'Multi-Arch: foreign' insertpackage 'unstable' 'git-cvs' 'amd64,i386' '1:2.26.2-1' 'Depends: git (>> 1:2.26.2), git (<< 1:2.26.2-.)' insertpackage 'unstable' 'git-ng' 'amd64,i386' '1:2.26.2-1' 'Depends: git (>> 1:2.26.2), git (<< 1:2.26.2-.)' +insertpackage 'unstable' 'git-rec-ng' 'amd64,i386' '1:2.26.2-1' 'Recommends: git (>> 1:2.26.2) +Depends: git (<< 1:2.26.2-.)' insertpackage 'unstable' 'chaos-actor' 'amd64,i386' '1' 'Provides: git (2:1)' setupaptarchive @@ -165,3 +167,14 @@ E: Unable to satisfy dependencies. Reached two conflicting decisions: 1. git:amd64=1:2.25.1-1 is selected for install as above 2. git:amd64 Conflicts git:i386' apt install git-ng -s +# The Recommends: git (>> 1:2.26.2-1) will be left unsatisfied rather than pulling in chaos-actor. +testsuccessequal 'Reading package lists... +Building dependency tree... +Solving dependencies... +Recommended packages: + git +The following NEW packages will be installed: + git-rec-ng +0 upgraded, 1 newly installed, 0 to remove and 2 not upgraded. +Inst git-rec-ng (1:2.26.2-1 unstable [amd64]) +Conf git-rec-ng (1:2.26.2-1 unstable [amd64])' apt install git-rec-ng -s -- cgit v1.2.3-70-g09d2