apt/apt-pkg/solver3.h, branch 3.1.3

Include standard headers to fix clang compiler error

2025-06-18T14:03:24Z

This commit fixes the following compiler errors. apt-pkg/acquire.cc:833:51: error: no template named 'function' in namespace 'std' apt-pkg/contrib/error.cc:198:59: error: no member named 'front_inserter' in namespace 'std' apt-pkg/solver3.h:44:22: error: no template named 'is_trivially_constructible_v' in namespace 'std' methods/http.cc:1029:24: error: no member named 'inserter' in namespace 'std'

solver3: Avoid FTBFS with g++ 14.2 on arm{el,hf}

2025-06-10T18:51:09Z

With an explicit {} initialization, g++ 14.2 on armhf and armel seems to generate the default constructor for the vector too early, or in the first place, outside of solver3.cc where the constructor is defined. Without {}, this compiles again. 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: 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: 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

solver3: Initialize startTime if not set in Pop()

2025-05-26T10:43:24Z

If the user pushes Assumptions that fail, we could inadvertently timeout during the Pop() as the variable was not initialized. Always initialize it to 0, and if we haven't set an actual time by the time we Pop() set it there.

solver3: Remove Work::choice

2025-05-26T10:08:29Z

Instead of having the historic choice here, follow MiniSAT and use the assigned variable from the tail. This should also make the Assume() function work now, albeit we still need to actually migrate to it. This is a first step towards refactoring the Solve() loop to use a propagate/find next literal/assume it kind of loop, albeit there is a bit more to prepare there as we need to also reinsert work items when backtracking.

Introduce apt why, apt why-not

2025-05-19T15:20:09Z

These are implemented somewhat differently from aptitudes why and why-not commands: They produce the actual solver trace for why a particular decision has been taken. For the why-not case, we need to explicitly discover our specified package, as if nothing else depends on it in our graph, it would otherwise always be undiscovered and conflicts not detected (see e.g. level-3 in the test).

solver3: Handle previously satisfied Suggests last

2025-03-20T21:22:17Z

In #2103556 we can see that avahi-daemon Suggests avahi-autoipd, which is previously satisfied by dhcpcd-base due to a Provides; that Provides has now been dropped; and solver3 keeps the update back. As in LP: #2102720 this is a Suggests and it seems wrong for the Suggests to actually influence dependency choices and be able to hold back updates. Instead, satisfy previously satisfied Suggests at the end. For the particular case in this bug report, this results in avahi-autoipd, the real package, to be installed to keep the Suggests working which needs further consideration whether that is the right choice (we can argue either way), but in any case this is a better solution. This in turn breaks the conkeror test which is a somewhat awkward unrealistic test these days as it has no automatically installed packages; because previously something must have had a Suggests on say libdatrie1 or something that was processed first. This would be fine before 5daf6dbfd272be2f8e3c59d4bab4be8c119b7aa1 but as of that commit we no longer rewrite conkeror Depends xulrunner-1.9 | xulrunner-1.9.1 into conkeror Depends xulrunner-1.9.1 | xulrunner-1.9 Because xulrunner-1.9 is manually installed. Mark xulrunner-1.9 as automatically installed to fix the test case. The resulting behavior seems correct: If you manually want xulrunner-1.9 specifically we should not replace it with xulrunner-1.9.1; but if it's automatically installed we should. LP: #2103556

apt-pkg/solver3.h: avoid static_assert(false)

2025-03-14T08:29:23Z

With older compilers (g++ and clang from Bookworm), static_assert(false) will result in: /home/josch/git/apt/build/include/apt-pkg/solver3.h:52:24: error: static assertion failed: Cannot construct map for key type 52 | static_assert(false, "Cannot construct map for key type"); | ^~~~~ This commit implements the terrible but more valid workaround according to: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2593r0.html Original solution from here: https://stackoverflow.com/questions/14637356/static-assert-fails-compilation-even-though-template-function-is-called-nowhere/14637534#14637534 That way, apt will compile with compilers in Bookworm again.

solver3: Fix Recommends/Suggests vs Enhances confusion

2025-03-12T17:52:16Z

We accidentally considered an Enhances a reason to keep a package installed, which of course it is not, fix the determination of "existing soft dependency" to only include soft dependencies that should keep a package installed in the autoremover to solve the issue. This also fixes edsp/mantic-upgrade-rel-to-2024-05-29.edsp to not install llvm-13-dev for clang-13 which is an installed package with no upgrade. Also ensure we stop after the first match; the DependsList() is ordered by decreasing priority and we don't want to override Recommends by Suggests in case a package declares both... LP: #2101800