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 --- test/integration/test-bug-961266-hold-means-hold | 10 +- ...st-ubuntu-bug-2111792-intersecting-dependencies | 167 +++++++++++++++++++++ 2 files changed, 172 insertions(+), 5 deletions(-) create mode 100755 test/integration/test-ubuntu-bug-2111792-intersecting-dependencies (limited to 'test') 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..4f58893bf --- /dev/null +++ b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies @@ -0,0 +1,167 @@ +#!/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' '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 + -- cgit v1.2.3-70-g09d2