Debians commandline package manager https://git.kalnischkies.de/apt/atom?h=main 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-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. 2025-03-08T22:18:05Z Julian Andres Klode julian.klode@canonical.com 2025-03-06T19:07:30Z urn:sha1:3967b75ae4a10d0d79560dfecb8eb210aad4f4f2 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. 2025-02-14T18:08:45Z Julian Andres Klode julian.klode@canonical.com 2025-02-05T19:37:12Z urn:sha1:943562a4ed2ddc80b84466d85e821037937f8b5c 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. 2025-01-30T13:50:15Z Julian Andres Klode julian.klode@canonical.com 2024-11-02T12:55:39Z urn:sha1:3523efb15d48ce3c6f9212f50dfc892497ba9dcb Instead of directly propagating in a recursive fashion, queue propagations in a queue and work on them in a loop per the miniSAT paper. We call Propagate() only at the end of the FromDepCache() function and then in the Solve loop. Delaying the initial propagation means that we get a stronger reasoning: Assume you have x->a->b->c, y->c and you install x,y: - Previously we traversed: x, y, x->a, a->b, b->c, (y->c) - but now we traverse: x, y, x->a, y->c, a->b, (b->c) Notably c now has the implication y->c instead of x->a->b->c. Inside the solver we need to call Propagate in a loop: Propagating facts can fail and we then backtrack. If backtracking is succesful, we have gained a new fact to propagate. 2024-05-24T15:01:35Z Julian Andres Klode julian.klode@canonical.com 2024-05-19T18:04:47Z urn:sha1:b5997949909ee9d5e9981c8311aea97c7b2620fd Highlights: - test-bug-618848-always-respect-user-requests: (Do not) Support 3.0 solver A manually installed package is never removed just because we request the removal of its dependency in solver3. - test-bug-657695-resolver-breaks-on-virtuals: Support 3.0 solver For manually installed packages, solver 3.0 would require some new xserver-xorg-video-driver to Conflict+Replace+Provides the old one (once the logic is implemented), but that does seem reasonable. - test-bug-720597-build-dep-purge: Support 3.0 solver This needs a simple aptmark auto because pkga is removed by the build-dep. But further adjustments are necessary because it weirdly tested for no autoremovable packages before installing pkgc. - test-bug-960705-*: Support 3.0 solver Bit awkward to deal with; notably the protect to conflict doesn't actually work anymore and that is a feature these days. 2021-06-10T17:25:17Z David Kalnischkies david@kalnischkies.de 2021-06-10T16:06:14Z urn:sha1:8083d4019844f764058efa2a950ed16975178bff If we call dpkg inside a chroot we have to ensure that the temporary directory we construct to call dpkg --recursive is inside the chroot and that we strip the path to the chroot from the directory name we pass to dpkg. Note that the added test succeeds before and (hopefully) after as we can't really chroot here or fiddle with the needed settings as we are already setting up apt to work with a quasi-chroot. The test perhaps helps in ensuring we don't break it too much in the future though. (Broken five years (and one day) ago this seems to have an immense user base at the moment, but it might in the future via mmdebstrap) References: f495992428a396e0f98886c9a761a804aa161c68 Reported-By: Johannes Schauer Marin Rodrigues on IRC Tested-By: Johannes Schauer Marin Rodrigues 2021-06-04T14:43:41Z David Kalnischkies david@kalnischkies.de 2021-06-04T11:06:34Z urn:sha1:149b23c2b9697bc262c0af1934c7a3f6114d903f Keeping URIs encoded in the acquire system depends on having them encoded in the first place. While many other places got the encoding 2 out of 3 ArchiveURI implementations were missed which are in practice responsible for nearly all of the URI building, just that index filename do not contain characters to escape and the Filename fields in Packages files usually aren't. Usually. Except if you happen to have e.g. an epoch featuring package with the colon encoded in the filename. On the upside, in most repositories the epoch isn't part of the filename. Reported-By: Johannes 'josch' Schauer on IRC References: e6c55283d235aa9404395d30f2db891f36995c49 2021-02-02T18:56:46Z David Kalnischkies david@kalnischkies.de 2020-12-02T14:51:09Z urn:sha1:f2c087449286812823d06d1b560fa947e438fa0d Explicitly opening a tar member is a bit harder than it needs to be as you have to remove the compressor extension so that it can be guessed here gain potentially choosing the wrong member. Doesn't really matter for deb packages of course as the member count is pretty low and strongly defined, but testing is easier this way. It also finally fixes an incorrectly formatted error message. 2020-03-21T07:35:26Z David Kalnischkies david@kalnischkies.de 2020-03-21T07:14:15Z urn:sha1:bf46e09f0e4b52b3c71ac20bb11e7511fc16179f While merging apt-pkg and apt-inst libraries the codepath of handling deb files in apt-pkg was adapted to use the 'old' code from apt-inst instead of fork&exec of dpkg-deb -I. The information we get this way forms the main part of the package stanza, but we add a few semi-optional fields to the stanza to make it look and work more like a stanza we got from a repository. Just be careful with the area where these two parts touch as if, hypothetically, we would stip all newlines around the parts, but forget to add a newline between them later, the two lines around the merge would stick a bit too close together forming one which could result in fun parsing errors if this merged line was previously e.g. a well-formed Depends line and has now extra fluff attached. This codepath has a history with too many newlines (#802553) though, so how likely is it really that it will some day lack one you may ask. References: 6089a4b17c61ef30b2efc00e270b0907f51f352a