apt/apt-pkg/solver3.cc, branch 3.1.12

solver3: Do not lose notion that we backtracked

2025-10-25T20:16:54Z

Record a silly string if we backtracked such that we are aware of it. We need to handle this in a broader fashion, but this was at least breaking test-apt-never-markauto-sections with remove-manual LP: #2129819

solver3: Eagerly satisfy previously satisfied Recommends

2025-10-25T16:10:32Z

When a user ran `apt install gpg`, the solver decided to remove `gnupg` and `seahorse` because `seahorse` was only pulled in as a Recommends of ubuntu-desktop and Recommends were resolved after all other dependencies. Solve this to most extent by introducing eager optionality: These dependencies, while they do not take part in classic unit propagation, are otherwise treated like hard dependencies and resolved as soon as possible rather than after any hard dependencies. This ensures that the Recommends of ubuntu-desktop on seahorse is retained correctly, and as a result, gnupg is updated to the latest version. Oops: 6c8e32eb-665d-11f0-a985-fa163ec8ca8c

solver3: Allow any downloadable version to mark a package as not obsolete

2025-08-26T11:41:35Z

Lots of people have pinned an older version that is no longer installable, or more common yesterday, we saw a lot of people who seemingly manually installed a newer version of a deb than in the repositories, causing the package to be considered obsolete, which does not make much sense. Oops: 4c39d922-410f-11f0-bbf9-fa163ec44ecd Oops: a64054f6-4140-11f0-bbfd-fa163ec44ecd Oops: a32196c1-661d-11f0-a97c-fa163ec8ca8c

solver3: Sort dependency targets against current alternative

2025-08-26T11:41:35Z

Instead of inadvertently sorting dependency targets against the first alternative in an or group, sort them against the current alternative as we should. Otherwise we ended up sorting gnome-shell | notification-daemon With Package: notification-daemon Package: awesome Provides: notification-daemon into gnome-shell | awesome | notification-daemon <-we sorted this part wrongly-> This fixes a minor difference in test-release-candidate-switching in one case, but not the other where the difference was actually caused by the loss of install argument ordering information in the new solver, so just flip the arguments so both solvers produce the same outcome.

solver3: Filter installed Recommends

2025-06-10T14:27:36Z

When inspecting Recommends of installed packages, filter them to the installed packages only, as we want to avoid switching between alternatives of recommended packages.

solver3: Explicitly declare and define ~Solver

2025-06-10T14:27:36Z

On recent armfhf and s390x builds in the PPA, the compiler seems to have generated the destructor at the wrong point where the definitions where not yet complete, and it does seem ill-advised to rely on a default-constructed destructor in the solver for future ABI sake. In file included from /usr/include/c++/14/vector:66, from /<>/obj-arm-linux-gnueabihf/include/apt-pkg/cachefilter.h:14: /usr/include/c++/14/bits/stl_vector.h: In instantiation of ‘constexpr std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = APT::Solver::Work; _Alloc = std::allocator]’: /usr/include/c++/14/bits/stl_vector.h:531:7: required from here 531 | vector() = default; | ^~~~~~ /usr/include/c++/14/bits/stl_vector.h:369:49: error: invalid use of incomplete type ‘struct APT::Solver::Work’ 369 | _M_impl._M_end_of_storage - _M_impl._M_start); | ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~ In file included from /<>/apt-pkg/edsp.cc:22: /<>/obj-arm-linux-gnueabihf/include/apt-pkg/solver3.h:87:11: note: forward declaration of ‘struct APT::Solver::Work’ 87 | struct Work; | ^~~~ /usr/include/c++/14/bits/stl_vector.h: In instantiation of ‘constexpr std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = APT::Solver::Solved; _Alloc = std::allocator]’: /usr/include/c++/14/bits/stl_vector.h:531:7: required from here 531 | vector() = default; | ^~~~~~ /usr/include/c++/14/bits/stl_vector.h:369:49: error: invalid use of incomplete type ‘struct APT::Solver::Solved’ 369 | _M_impl._M_end_of_storage - _M_impl._M_start); | ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~ /<>/obj-arm-linux-gnueabihf/include/apt-pkg/solver3.h:88:11: note: forward declaration of ‘struct APT::Solver::Solved’ 88 | struct Solved; | ^~~~~~

solver3: Ignore Architecture: all for obsoleted-by

2025-06-10T14:27:36Z

In case a new version of the source package is published, we check that if there's a newer binary for the same architecture and then consider the binary obsoleted. This logic did not properly account for Architecture: all packages which are considered as native architecture package with an "All" multi-arch flag set, and hence a native architecture package may inadvertently be considered obsoleted by a package that only built on Architecture: all.

solver3: Only merge dependencies on the same package

2025-05-28T11:58:04Z

Avoid or groups and dependencies on different (virtual) packages, to avoid some common pitfalls like the added xorg test case.

solver3: Merge Depends into Recommends

2025-05-27T14:06:06Z

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.

solver3: Merge intersecting dependencies

2025-05-27T13:56:55Z

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