apt/apt-pkg/solver3.cc, branch 2.9.28Debians commandline package managerhttps://git.kalnischkies.de/apt/atom?h=2.9.282025-02-07T19:59:43Zsolver3: Avoid std::vector for statically sized arrays2025-02-07T19:59:43ZJulian Andres Klodejulian.klode@canonical.com2025-02-06T11:40:01Zurn:sha1:cce96b85691fac0bbbbb84a501c6f39a0c9125c0
The bounds checking on the vector accesses is killing performance,
so switch from vector to a basic array, given that we don't actually
need _any_ functionality from vector...
Of course while we are at it, let us define a safe wrapper around
it so we cannot accidentally index arrays for package IDs with
version IDs and whatnot.
solver3: Add const where helpful2025-02-07T19:59:43ZJulian Andres Klodejulian.klode@canonical.com2025-02-06T11:28:57Zurn:sha1:8f4c09bb58b047a73328f935b9abeb4fe0b03ae1
operator[] is a bit annoying here, but oh well, what can we
do?
solver3: Point to stored clauses, do not copy them2025-02-07T19:59:43ZJulian Andres Klodejulian.klode@canonical.com2025-02-06T10:28:07Zurn:sha1:ecb1399ca5f4917286d354b00dadb91c8075db1d
This makes Work trivially destructible, and in turn solved, allowing
their queues to be destructed without running destructors, and avoiding
the copy should have a nice performance improvement.
solver3: Use a package clause for optional roots2025-02-07T19:59:43ZJulian Andres Klodejulian.klode@canonical.com2025-02-06T09:44:34Zurn:sha1:3d5f8042c64c30497a65e522c6e402eb4bab10c3
Instead of iterating over the version here and picking it, just
enqueue the package as well, which should allow us to select the
version at a later time.
This also causes a funny inverse problem now, though, as was evidenced
in one of the test cases: To summarize, if our optional roots are all
single items, they will be considered soft-unit, causing them to be
processed in order.
However it can be that an optional root has a specific version
selected because another version was rejected. Consider
X Conflicts A (= 1)
A, B have 2 versions: '2' available, '1' installed
B (= n) Depends A (= n)
Run `apt install X`. The expected result is for A and B to be
upgraded to version 2. With only a package root, if B appears
in the cache before A however, we will get:
Install X
Reject A (= 1)
Install B
Install B (= 1) # keep it installed
Reject A (= 2)
=> A is being removed as both versions are rejected
Hence we do also need to re-introduce the additional version
clause, now we get:
Install X
Reject A (= 1)
Install A (= 2) # it got "promoted" to a 'stronger' soft-unit
Install B
Fail B (= 1) # keep it installed
Install B (= 2)
Introduce a root state to hold all the clauses that don't have
another owner.
moo
solver3: Refactor Dump() to toString()2025-02-07T19:59:43ZJulian Andres Klodejulian.klode@canonical.com2025-02-05T20:56:04Zurn:sha1:601af4e8adac4cdd57a031db5d073f61fc1033dc
This vastly simplifies the code at the expense of performance,
lol.
solver3: Support comparing packages and versions2025-02-07T19:59:43ZJulian Andres Klodejulian.klode@canonical.com2025-02-05T19:48:28Zurn:sha1:9b482fb51ed28ac75b6d4847729f72717f2ea431
When comparing packages, we compare the best version for the
package. To determine the best version, the rules for comparisons
are applied normally.
This allows us to mix packages and versions in a clause as the
solutions for a dependency, which means we'll be able to defer
the selection of a particular version of a package to a later
time.
solver3: Replace PropagateInstall() with Discover()2025-02-07T19:59:43ZJulian Andres Klodejulian.klode@canonical.com2025-02-05T15:29:37Zurn:sha1:efedf5c4700bcdd22841cf6885485677a93cc31c
Just propagate the stored clauses after we have discovered them;
this is quite straightforward. We now more reliably discover common
dependencies at the package level, adjust the test case accordingly.
The next step is to make discovery recursive, or iterative, to build
an entire recursive tree from all roots, and then we can reject reverse
dependencies based on it.
A bunch of refactorings are needed in the process. We remove the
useless Hint enumeration and insert a flags struct into the State,
such that we can record whether a package/version has been
discovered, to avoid spending double time on discovery.
solver3: Extract TranslateOrGroup() out of EnqueueOrGroup()2025-02-07T19:59:43ZJulian Andres Klodejulian.klode@canonical.com2025-02-04T11:42:17Zurn:sha1:dd691af845421e6e9c6f43e51e907dd54e505604
This is not *purely* a refactoring, we accidentally used the
version of the dependency when enqueuing conflicts rather than
the reason, so the conflict string in the test case is different;
the logging had the same issue.
solver3: Extract Clause out of Work2025-02-07T19:59:43ZJulian Andres Klodejulian.klode@canonical.com2025-02-04T09:18:32Zurn:sha1:762d12f0ac9dd10325cae09816e5e918b7e5b039
Extract clause into a separate struct and embed a copy of it in
our Work class.
solver3: Simplify WhyStr()2025-02-07T19:59:43ZJulian Andres Klodejulian.klode@canonical.com2025-02-04T08:52:59Zurn:sha1:a41d4ba65bc0841a28ea9c8e9fd13f2c4e00ce86
Reuse the generic variable rendering