diff options
| -rw-r--r-- | apt-pkg/solver3.cc | 66 | ||||
| -rw-r--r-- | apt-pkg/solver3.h | 5 | ||||
| -rwxr-xr-x | test/integration/test-bug-961266-hold-means-hold | 10 | ||||
| -rwxr-xr-x | test/integration/test-ubuntu-bug-2111792-intersecting-dependencies | 180 |
4 files changed, 250 insertions, 11 deletions
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index be1576e98..95cff96f3 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,53 @@ 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) + 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; + + 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; + } + 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) + return nullptr; + } + clauses.push_back(std::make_unique<Clause>(std::move(clause))); auto const &inserted = clauses.back(); for (auto var : inserted->solutions) @@ -1173,7 +1229,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 +1245,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 +1264,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<Clause> 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; }; /** diff --git a/test/integration/test-bug-961266-hold-means-hold b/test/integration/test-bug-961266-hold-means-hold index c97aa0839..750d32968 100755 --- a/test/integration/test-bug-961266-hold-means-hold +++ b/test/integration/test-bug-961266-hold-means-hold @@ -91,7 +91,7 @@ The following packages have unmet dependencies: git-ng : Depends: git (> 1:2.26.2) E: Unable to satisfy dependencies. Reached two conflicting decisions: 1. git-ng:amd64=1:2.26.2-1 is selected for install - 2. git-ng:amd64 Depends git (> 1:2.26.2) + 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) but none of the choices are installable: - git:amd64=1:2.26.2-1 is not selected for install because: 1. git:amd64=1:2.25.1-1 is selected for install @@ -138,16 +138,16 @@ The following packages have unmet dependencies: E: Unable to satisfy dependencies. Reached two conflicting decisions: 1. git:amd64=1:2.26.2-1 is selected as an upgrade because: 1. git-ng:amd64=1:2.26.2-1 is selected for install - 2. git-ng:amd64 Depends git (> 1:2.26.2) + 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) [selected git-ng:amd64] For context, additional choices that could not be installed: - * In git-ng:amd64 Depends git (> 1:2.26.2): + * In git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.): - git:i386=1:2.26.2-1 is not selected for install because: 1. git:amd64 is selected for install 2. git:amd64 Conflicts git:i386 2. git:amd64=1:2.26.2-1 is not selected for install because: 1. git-cvs:amd64=1:2.25.1-1 is selected for install - 2. git-cvs:amd64=1:2.25.1-1 Depends git (< 1:2.25.1-.) + 2. git-cvs:amd64=1:2.25.1-1 Depends git (> 1:2.25.1) and Depends git (< 1:2.25.1-.) 3. git:amd64=1:2.25.1-1 conflicts with other versions of itself' apt install git-ng -s --solver 3.0 @@ -186,7 +186,7 @@ The following packages have unmet dependencies: git-ng : Depends: git (> 1:2.26.2) E: Unable to satisfy dependencies. Reached two conflicting decisions: 1. git-ng:amd64=1:2.26.2-1 is selected for install - 2. git-ng:amd64 Depends git (> 1:2.26.2) + 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) but none of the choices are installable: - git:amd64=1:2.26.2-1 is not selected for install because: 1. git:amd64=1:2.25.1-1 is selected for install diff --git a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies new file mode 100755 index 000000000..86866b233 --- /dev/null +++ b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies @@ -0,0 +1,180 @@ +#!/bin/sh +# This is the same test as test-bug-961266-hold-means-hold with a chaos actor +# introduced that provides a version of git that satisfies all >> constraints, +# to reproduce the same issue with gpgv and gpgv-from-sq in the Ubuntu bug. +set -e + +TESTDIR="$(readlink -f "$(dirname "$0")")" +. "$TESTDIR/framework" + +# This only works with the 3.0 solver. The classic solver does not intersect +# dependencies and will cause the chaos actor to be installed, so force it. +export APT_SOLVER=3.0 + +setupenvironment +configarchitecture 'amd64' 'i386' + +insertinstalledpackage 'git' 'amd64' '1:2.25.1-1' 'Multi-Arch: foreign' +insertinstalledpackage 'git-cvs' 'amd64' '1:2.25.1-1' 'Depends: git (>> 1:2.25.1), 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 + +msgmsg 'The setup is' 'fine' +UPGRADE='Reading package lists... +Building dependency tree... +Calculating upgrade... +The following packages will be upgraded: + git git-cvs +2 upgraded, 0 newly installed, 0 to remove and 0 not upgraded. +Inst git-cvs [1:2.25.1-1] (1:2.26.2-1 unstable [amd64]) [] +Inst git [1:2.25.1-1] (1:2.26.2-1 unstable [amd64]) +Conf git-cvs (1:2.26.2-1 unstable [amd64]) +Conf git (1:2.26.2-1 unstable [amd64])' +testsuccessequal "$UPGRADE" apt upgrade -s +testsuccessequal "$UPGRADE" aptget upgrade -s +testsuccessequal "$UPGRADE" apt full-upgrade -s +testsuccessequal "$UPGRADE" aptget dist-upgrade -s + +testsuccessequal 'Reading package lists... +Building dependency tree... +The following additional packages will be installed: + git git-cvs +The following NEW packages will be installed: + git-ng +The following packages will be upgraded: + git git-cvs +2 upgraded, 1 newly installed, 0 to remove and 0 not upgraded. +Inst git-cvs [1:2.25.1-1] (1:2.26.2-1 unstable [amd64]) [] +Inst git [1:2.25.1-1] (1:2.26.2-1 unstable [amd64]) +Inst git-ng (1:2.26.2-1 unstable [amd64]) +Conf git-cvs (1:2.26.2-1 unstable [amd64]) +Conf git (1:2.26.2-1 unstable [amd64]) +Conf git-ng (1:2.26.2-1 unstable [amd64])' apt install git-ng -s + + +msgmsg 'Now mix it up by' 'holding git' +testsuccessequal 'git set on hold.' aptmark hold git +testsuccessequal 'git' aptmark showholds + +NOUPGRADE='Reading package lists... +Building dependency tree... +Calculating upgrade... +The following packages have been kept back: + git git-cvs +0 upgraded, 0 newly installed, 0 to remove and 2 not upgraded.' + +testsuccessequal "$NOUPGRADE" apt upgrade -s +testsuccessequal "$NOUPGRADE" apt full-upgrade -s +testsuccessequal "$NOUPGRADE" aptget dist-upgrade -s +testsuccessequal "$NOUPGRADE" aptget upgrade -s + +testfailureequal 'Reading package lists... +Building dependency tree... +Solving dependencies... +Some packages could not be installed. This may mean that you have +requested an impossible situation or if you are using the unstable +distribution that some required packages have not yet been created +or been moved out of Incoming. +The following information may help to resolve the situation: + +The following packages have unmet dependencies: + git-ng : Depends: git (> 1:2.26.2) +E: Unable to satisfy dependencies. Reached two conflicting decisions: + 1. git-ng:amd64=1:2.26.2-1 is selected for install + 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) + but none of the choices are installable: + - git:amd64=1:2.26.2-1 is not selected for install because: + 1. git:amd64=1:2.25.1-1 is selected for install + 2. git:amd64=1:2.25.1-1 conflicts with other versions of itself + - git:i386=1:2.26.2-1 is not selected for install because: + 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 + + +msgmsg 'Now mix it up by' 'holding git-cvs' +testsuccessequal 'Canceled hold on git.' aptmark unhold git +testsuccessequal 'git-cvs set on hold.' aptmark hold git-cvs +testsuccessequal 'git-cvs' aptmark showholds + +testsuccessequal "$NOUPGRADE" apt upgrade -s +testsuccessequal "$NOUPGRADE" apt full-upgrade -s +testsuccessequal "$NOUPGRADE" aptget upgrade -s +testsuccessequal "$NOUPGRADE" aptget dist-upgrade -s + +testfailureequal 'Reading package lists... +Building dependency tree... +Solving dependencies... +Some packages could not be installed. This may mean that you have +requested an impossible situation or if you are using the unstable +distribution that some required packages have not yet been created +or been moved out of Incoming. +The following information may help to resolve the situation: + +The following packages have unmet dependencies: + git-ng : Depends: git (> 1:2.26.2) +E: Unable to satisfy dependencies. Reached two conflicting decisions: + 1. git:amd64=1:2.26.2-1 is selected as an upgrade because: + 1. git-ng:amd64=1:2.26.2-1 is selected for install + 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) + [selected git-ng:amd64] + For context, additional choices that could not be installed: + * In git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.): + - git:i386=1:2.26.2-1 is not selected for install because: + 1. git:amd64 is selected for install + 2. git:amd64 Conflicts git:i386 + 2. git:amd64=1:2.26.2-1 is not selected for install because: + 1. git-cvs:amd64=1:2.25.1-1 is selected for install + 2. git-cvs:amd64=1:2.25.1-1 Depends git (> 1:2.25.1) and Depends git (< 1:2.25.1-.) + 3. git:amd64=1:2.25.1-1 conflicts with other versions of itself' apt install git-ng -s + + +msgmsg 'Now mix it up by' 'holding both' +testsuccessequal 'git set on hold.' aptmark hold git +testsuccessequal 'git +git-cvs' aptmark showholds + +testsuccessequal "$NOUPGRADE" apt upgrade -s +testsuccessequal "$NOUPGRADE" apt full-upgrade -s +testsuccessequal "$NOUPGRADE" aptget upgrade -s +testsuccessequal "$NOUPGRADE" aptget dist-upgrade -s + +testfailureequal 'Reading package lists... +Building dependency tree... +Solving dependencies... +Some packages could not be installed. This may mean that you have +requested an impossible situation or if you are using the unstable +distribution that some required packages have not yet been created +or been moved out of Incoming. +The following information may help to resolve the situation: + +The following packages have unmet dependencies: + git-ng : Depends: git (> 1:2.26.2) +E: Unable to satisfy dependencies. Reached two conflicting decisions: + 1. git-ng:amd64=1:2.26.2-1 is selected for install + 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) + but none of the choices are installable: + - git:amd64=1:2.26.2-1 is not selected for install because: + 1. git:amd64=1:2.25.1-1 is selected for install + 2. git:amd64=1:2.25.1-1 conflicts with other versions of itself + - git:i386=1:2.26.2-1 is not selected for install because: + 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 |