Debians commandline package manager https://git.kalnischkies.de/apt/atom?h=3.1.15 2026-01-31T16:30:20Z 2026-01-31T16:30:20Z Julian Andres Klode jak@debian.org 2025-12-29T17:47:15Z urn:sha1:1fbb857b6b2cbddcea9e8b03aa0c766c72e91f34 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 2026-01-31T14:10:14Z Julian Andres Klode jak@debian.org 2025-12-29T21:20:29Z urn:sha1:267fd0117a057afd88bc15bfb4f4d688804a9ab4 2026-01-31T14:08:29Z Julian Andres Klode jak@debian.org 2026-01-06T10:45:16Z urn:sha1:ceca5e8d0f9e1a1c5297ed79f00ca76c61e2140c Quite a convenient way since we need exactly lifted bool semantics 2026-01-20T13:07:15Z Julian Andres Klode jak@debian.org 2026-01-20T13:04:20Z urn:sha1:34876ed2e5cdf504e2a4f9721486d279ae5f3be6 Refactor code into a doOne helper lambda, and then add loop over the providers to use it. This fixes a crash seen by Benjamin in a nice way than just failing :) Reported-by: Benjamin Drung 2026-01-05T21:20:24Z Julian Andres Klode jak@debian.org 2025-12-29T20:26:24Z urn:sha1:62fa3858d12f163de7db81f6e2be770e39783238 Where applicable 2026-01-05T21:20:24Z Julian Andres Klode jak@debian.org 2025-12-29T15:47:20Z urn:sha1:f02f90021c255ef3aa578e00758cbc62e7fc82dd I do not know why I don't hit this 2026-01-05T21:20:24Z Julian Andres Klode jak@debian.org 2025-05-20T11:13:45Z urn:sha1:f8dd5ea23c6a7fccf643329c50ae1f11f48b1a09 This method is no longer needed technically speaking, we should use Assume() instead. It turns out that there is a slight bug in the propagation and some clauses that are unit end up on the heap rather than having been propagated away, so we temporarily need to keep an if for that around. To accomodate the switch from Push() to Assume() we need to make sure that the work item is pushed to our trail *after* we have assumed it, such that reverting pushes it back to the work heap. Refactor the code to consistently use Assume() rather than supporting Enqueue(), this vastly simplifies things. This is not fully accurate in the current model and leads to unnecessary decision levels, since sometimes we seem to be reaching unit clauses here. This preserves traversal order by first removing the item from the heap and then adding it back if we need to solve it again. 2026-01-05T21:20:24Z Julian Andres Klode jak@debian.org 2025-12-28T20:42:32Z urn:sha1:d0643f993d3c6c42ea10d5ce3a02d964b7693a7f We can just re-use Enqueue() here to produce our conflict message why am I being silly and duplicate this. 2026-01-05T21:20:24Z Julian Andres Klode jak@debian.org 2025-12-28T15:59:17Z urn:sha1:ee82f420e7a303b5d92302134401e465b386de94 Matches the rename of depth() to decisionLevel() at a shorter name. 2026-01-05T21:20:24Z Julian Andres Klode jak@debian.org 2025-12-28T15:56:28Z urn:sha1:21d099878ed8c34f3b13747bcec380e0402e57a3 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.