apt/test/integration/test-bug-961266-hold-means-hold, branch main

solver3: Use classical watchers for propagation

2026-01-31T16:30:20Z

Instead of tracking dependencies and reverse dependencies, install classical watchers. This vastly streamlines the propagation code and allows us to easily switch to literals in the next step. This implementation watches _all_ solutions rather than using the modern 2-watched literals scheme or the intermediate head/tail watchers. Ultimately a more effective watcher scheme would be interesting but not a significant priority seeing as most of the solver runtime is spent not in propagation but in problem translation. decision trees -------------- The new watchers produce slightly different decision trees, sometimes subtly changing solutions. Notably in various observed examples in Ubuntu 25.04, courier was installed as an MTA instead of postfix: The old decision tree was: apcupsd:amd64 -> mailutils:amd64=1:3.18-1 -> mailutils:amd64 -> postfix:amd64=3.9.1-10ubuntu1 The new decision tree is: lsb:amd64 -> lsb-core:amd64 -> courier-mta:amd64=1.3.13-1 The difference here being that lsb-core declares a mail-transport-agent dependency whereas mailutils depends on `default-mta | mail-transport-agency`; but both are effectively subject to selection at similar time. Further work is needed to optimize selection. A notable choice may also be to deal with broken packages like lsb-core that declare dependencies solely on a virtual package by reconstructing the default provider for that package utilizing default-* dependencies or similar notions. Likewise in the test suite, explanations are different in some uninstallable cases. backtracking ~~~~~~~~~~~~ The following major changes were observed in the 25.04 test suite: -tmp/regression-remove/07f0a068-36c2-11f0-b7c1-fa163e171f02:18 +tmp/regression-remove/07f0a068-36c2-11f0-b7c1-fa163e171f02:3 -tmp/regression-remove/32078f70-3734-11f0-a75a-fa163ec8ca8c:64 +tmp/regression-remove/32078f70-3734-11f0-a75a-fa163ec8ca8c:19 Other test cases showed little deviation, +/- 1, generally the same amount of backtracking. performance ~~~~~~~~~~~ Running Ubuntu's regression test suite resulted in no significant performance difference being observable. Before: 290s user time; 16.66% solver After: 299s user time; 17.36% solver Tests where run with make -j 8 and solver performance extracted perf report --symbol-filter=ResolveExternal --stdio

solver3: Rename decision to assignment

2026-01-05T21:20:24Z

The previous use of decision here conflicted with the use of decision level and the general notion of having made a decision, because the assignment might have been propagated as a matter of fact.

solver3: Allow removing manually installed packages

2025-10-25T20:16:54Z

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: Verbose error messages

2025-03-08T22:18:05Z

Introduce a new function, LongWhyStr() that returns a longer reason for why something is being installed (or not). This does the same path walk as the other function does, but it renders the clauses at each level, and one per line, so the whole output is a lot more informative. It is a separate function to keep the existing debug messages use the simple single line implication graph We remove the other special case in AddWork() for empty solutions to mke use of the general case in Solve() instead, and then adapt the case in Solve() to the same case as in Enqueue(). This also happens to fix the bug that when we encountered an empty clause we just printed the clause had no solution, but not how we got to install the package with the clause. Adapt the test suite for the changes which is an annoying amount of paperwork.

solver3: Only enqueue shared dependencies at the package level

2025-02-14T18:08:45Z

Dependencies shared by all versions are enqueued at the package level, so avoid enqueuing duplicates at the version level. This presumably has no meaningful impact on performance, potentially a negative performance impact on some workloads as we now need to find the duplicates again; it can become useful when there is a lot of backtracking. More importantly though this improves error messages, because now we can say that "all versions of foo depend on X", rather than saying "foo=1 depends on X" and you are left wondering why we did not select "foo=2". In this commit though, improved error messages are not implemented, they depend on redesigning the reason tracking to use clauses. Also the rationale tracking includes a lot more dependencies of the form "pkg:arch=version -> pkg:arch" which are annoying. Improved error messages should fold them into one node.

solver3: Remove work rescoring in favor of unit propagation

2025-02-14T18:08:45Z

Instead of expensive rescoring of all outstanding items, use unit propagation to find new units after conflicts. We still count the items when adding them; but unless they are 0 or 1, which they should not be, they don't have any effect: The size field is now effectively static. If the size of an optional clause changed to 1, it is inserted a second time, and then moves up to the top of the optional items per the Work::operator< rules.

test: Fix 7 test cases for 3.0 solver, annotate others

2025-02-14T18:08:45Z

Fix the test cases we can fix directly; add annotations where we know what work is needed, next we'll look at the other bugs.

Keep status number if candidate is discarded for kept back display

2020-05-23T15:59:19Z

It looks like hack and therefore I wanted this to be a very isolated commit so we can find it & revert it easily if need be, but for now it seems to work. The idea is that Status is telling us how the candidate is in relation to the current installed version which is used to figure out if a package is "kept back" by the algorithm or not, but by discarding the candidate version we loose this information. Ideally we would keep better tabs on what we do to a package and why, but for now that seems okayish. It will cause the wrong version to be displayed though as if the package is installed the installed version becomes the candidate and hence (installed => installed) is displayed.

Reset candidate version explicitly for internal state-keeping

2020-05-23T15:58:42Z

For a (partially) installed package like the one MarkInstall operates on at the moment we want to discard the candidate from, we have to first remove the package from the internal state keeping to have proper broken counts and such and only then reset the candidate version which is a trivial operation in comparison. Take a look at the testcase: Now, what is the problem? Correct, git:i386. Didn't see that coming, right? It is M-A:foreign so apt tries to switch the architecture of git here (which is pointless, it knows that this won't work, but lets fix that in another commit) will eventually realize that it can't install it and wants to discard the candidate of git:i386 first removing the broken indication like it should, removing the install flag and then reapplies the broken indication: Expect it doesn't as it wants to do that over the candidate version which the package no longer had so seemingly nothing is broken. It is a bit of a hairball to figure out which commit it is exactly that is wrong here as they are all influencing each other a bit, but >= 2.1 is an acceptable ballpark. Bisect says 57df273 but that is mostly a lie. Closes: #961266