| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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
|
| |
|
|
|
|
|
| |
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.
|
| | |
|
| |
|
|
|
| |
Avoid or groups and dependencies on different (virtual) packages,
to avoid some common pitfalls like the added xorg test case.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Merge any hard clauses into optional clauses, such that
optional clauses don't end up with more choices.
For example if you have
Depends: a | b
Recommends: a | c
This becomes:
Depends: a | b
Recommends: a
We have simulated this with the chaos-actor in the test case
and a
Depends: git (not satisfied by chaos provider)
Recommends: git (satisfied by chaos provider)
and the latter constraint is limited to the former.
|
|
|
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
|
