apt/test/integration/test-multiarch-allowed, branch 3.0.0

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: Reject reverse conflicts on install

2025-02-14T18:04:56Z

We forgot this in the previous iteration. This makes the reasoning in the test cases much nicer and apt-test's mantic-to-noble-jak.edsp now finishes rather than running into the timeout (potentially forever).

solver3: Reject reverse dependencies natively

2025-02-14T18:04:56Z

Instead of utilizing the reverse depends functionality of the cache and marking all possible reverse dependencies for removal, mark them ourselves by keeping track of reverse-implication-clauses. Notably, this improves the reverse dependency rejection substantially: The previous RejectReverseDependencies() function did not handle Provides. For this to work correctly right now, we need to discover optional clauses too when queuing them. This is somewhat suboptimal as we technically we don't care if they become unsat, we just waste time tracking them. The tests get a bit awkward, but oh well, we use what we can use.

solver3: Defer version selection where possible

2025-02-14T18:04:56Z

If a dependency can be satisfied by all versions of a package, add the package to the clause instead of the version object. This works only if there are no providers for the package: Providers are quite hard to enumerate over and make sure that all versions of a package satisfy the provider dependency. Implement arbitrary selection between packages and versions for the CompareProviders class: We pick the best version for each package and then pit them against each other.

solver3: Use a propagation queue

2025-01-30T13:50:15Z

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.

test: Support the 3.0 solver in most existing test cases

2024-05-24T15:01:35Z

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.

Respect users pkg order on `apt install` for resolving

2022-09-02T21:37:58Z

The command line is evaluated in two steps: First all packages given are marked for install and as a second step the resolver is started on all of them in turn to get their dependencies installed. This is done so a user can provide a non-default choice on the command line and have it respected regardless of where on the command line it appears. On the other hand, the order in which dependencies are resolved can matter, so instead of using a "random" order, we now do this in the order given on the command line, so if you e.g. have a meta package pulling in non-default choices and mention it first the choices are respected predictably instead of depending on first appearance of the package name while creating the binary cache. I might have "broken" this more than a decade ago while introducing the reworked command line parsing for Multi-Arch, which also brought in the split into the two steps mentioned above which was the far more impactful 'respect user choice' change. This one should hardly matter in practice, but as the tests show, order can have surprising side effects.

Mark broken reverse depends for upgrade

2022-07-11T14:37:33Z

Currently the solver handles cases where a Breaks b (<< 1) and if we install that a, upgrades b. However, where b Depends a (= 1), b was removed again. This addresses the problem by iterating over installed reverse dependencies of upgrades and upgrading them so that both cases work roughly similarly. LP: #1974196

Do not make provides of M-A:allowed implicit M-A:foreign

2021-09-04T13:35:15Z

As we don't know which architectures we will deal with and to avoid creating many "unneeded" packages (and provides) the cache generation uses a scheme of on-demand creation (see ecc138f858). This assumed a particular handling of :any which got changed later (3addaba1ff) making this code path not only no longer needed for M-A:allowed, but actually wrong as it would go on and create provides for the explicit Provides of a package as if the package would be M-A:foreign. The result was that a package A:amd64 providing B tagged as M-A:allowed would satisfy a "C:armel depends on B". Note that this bug does NOT effect "C:armel depends on A" which is (correctly) not satisfied as before. References: ecc138f858, 3addaba1ff