| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
| |
When inspecting Recommends of installed packages, filter
them to the installed packages only, as we want to avoid
switching between alternatives of recommended packages.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
On recent armfhf and s390x builds in the PPA, the compiler seems to have
generated the destructor at the wrong point where the definitions where
not yet complete, and it does seem ill-advised to rely on a
default-constructed destructor in the solver for future ABI sake.
In file included from /usr/include/c++/14/vector:66,
from /<<PKGBUILDDIR>>/obj-arm-linux-gnueabihf/include/apt-pkg/cachefilter.h:14:
/usr/include/c++/14/bits/stl_vector.h: In instantiation of ‘constexpr std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = APT::Solver::Work; _Alloc = std::allocator<APT::Solver::Work>]’:
/usr/include/c++/14/bits/stl_vector.h:531:7: required from here
531 | vector() = default;
| ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:369:49: error: invalid use of incomplete type ‘struct APT::Solver::Work’
369 | _M_impl._M_end_of_storage - _M_impl._M_start);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /<<PKGBUILDDIR>>/apt-pkg/edsp.cc:22:
/<<PKGBUILDDIR>>/obj-arm-linux-gnueabihf/include/apt-pkg/solver3.h:87:11: note: forward declaration of ‘struct APT::Solver::Work’
87 | struct Work;
| ^~~~
/usr/include/c++/14/bits/stl_vector.h: In instantiation of ‘constexpr std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = APT::Solver::Solved; _Alloc = std::allocator<APT::Solver::Solved>]’:
/usr/include/c++/14/bits/stl_vector.h:531:7: required from here
531 | vector() = default;
| ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:369:49: error: invalid use of incomplete type ‘struct APT::Solver::Solved’
369 | _M_impl._M_end_of_storage - _M_impl._M_start);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
/<<PKGBUILDDIR>>/obj-arm-linux-gnueabihf/include/apt-pkg/solver3.h:88:11: note: forward declaration of ‘struct APT::Solver::Solved’
88 | struct Solved;
| ^~~~~~
|
| |
|
|
|
|
|
|
|
|
|
|
| |
In case a new version of the source package is published, we
check that if there's a newer binary for the same architecture
and then consider the binary obsoleted.
This logic did not properly account for Architecture: all packages
which are considered as native architecture package with an "All"
multi-arch flag set, and hence a native architecture package may
inadvertently be considered obsoleted by a package that only built
on Architecture: all.
|
| |
|
|
|
| |
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
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
If we have allowed the removal of manual packages, assume them
all before starting the solver. This should ensure that as long
as there is a solution that does not remove a manually installed
package, it is found.
This requires a sweeping set of changes in the test suite, but
ensures that we get "safe" behavior from the solver. We have
in particular seen that without asserting the installed packages,
several people ended up with ubuntu-minimal and perl removed in
a situation where that was not warranted, that is, they install
winehq, and then pull in some new perl packages in a newer version
than the installed one, and the solver chose to create a mismatched
version set, which then caused the main perl package to not be
installable.
Oops: 1b55173a-3526-11f0-b7ac-fa163e171f02
Oops: dbd5149e-36b9-11f0-bb74-fa163ec44ecd
|
| |
|
|
|
|
|
|
| |
If the user pushes Assumptions that fail, we could inadvertently
timeout during the Pop() as the variable was not initialized.
Always initialize it to 0, and if we haven't set an actual time
by the time we Pop() set it there.
|
| |
|
|
|
|
| |
This can be used to compare arbitrary packages in non-dependency
contexts. It remains to be seen whether this is a meaningful
approach.
|
| |
|
|
|
|
|
|
|
| |
We sometimes enqueue no choice as the choice, specifically when
an optional clause became unsat as we need to reenqueue it on
undo.
But of course, this breaks undoing stuff because now it tries to
insert !root and then solver breaks.
|
| |
|
|
|
|
|
|
|
|
|
| |
If an Assume() failed, we will have pushed the choices stack,
but not actually pushed anything to the solved stack.
This would cause a segmentation fault trying to read the referenced
entry that doesn't actually exists, namely solved[solved.size()].
Handle this by exiting early as there's nothing to do except
pop the entry back out of the array.
|
| |
|
|
|
|
|
|
|
|
|
|
| |
Instead of having the historic choice here, follow MiniSAT and
use the assigned variable from the tail. This should also make
the Assume() function work now, albeit we still need to actually
migrate to it.
This is a first step towards refactoring the Solve() loop to use
a propagate/find next literal/assume it kind of loop, albeit there
is a bit more to prepare there as we need to also reinsert work
items when backtracking.
|
| |
|
|
|
|
|
|
|
|
|
| |
These are implemented somewhat differently from aptitudes
why and why-not commands: They produce the actual solver
trace for why a particular decision has been taken.
For the why-not case, we need to explicitly discover our
specified package, as if nothing else depends on it in
our graph, it would otherwise always be undiscovered and
conflicts not detected (see e.g. level-3 in the test).
|
| |
|
|
|
|
|
|
|
|
| |
As a followup to the previous commit, restore the exact behavior
of the old solver to break the Suggests on upgrade here by erasing
any choices not previously installed.
This ensures that the Suggests never installs any new package, but
it will still retain previously installed packages when solver3 is
doing autoremove.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
In #2103556 we can see that avahi-daemon Suggests avahi-autoipd,
which is previously satisfied by dhcpcd-base due to a Provides;
that Provides has now been dropped; and solver3 keeps the update
back.
As in LP: #2102720 this is a Suggests and it seems wrong for the
Suggests to actually influence dependency choices and be able to
hold back updates.
Instead, satisfy previously satisfied Suggests at the end. For the
particular case in this bug report, this results in avahi-autoipd,
the real package, to be installed to keep the Suggests working
which needs further consideration whether that is the right choice
(we can argue either way), but in any case this is a better solution.
This in turn breaks the conkeror test which is a somewhat awkward
unrealistic test these days as it has no automatically installed
packages; because previously something must have had a Suggests
on say libdatrie1 or something that was processed first.
This would be fine before 5daf6dbfd272be2f8e3c59d4bab4be8c119b7aa1
but as of that commit we no longer rewrite
conkeror Depends xulrunner-1.9 | xulrunner-1.9.1
into
conkeror Depends xulrunner-1.9.1 | xulrunner-1.9
Because xulrunner-1.9 is manually installed. Mark xulrunner-1.9
as automatically installed to fix the test case.
The resulting behavior seems correct: If you manually want
xulrunner-1.9 specifically we should not replace it with
xulrunner-1.9.1; but if it's automatically installed we should.
LP: #2103556
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
When discovering packages we look at the manual flag to avoid
reordering obsolete manually installed packages last.
We inadvertently initialized that flag interlaced with discovering
packages so if we discovered packages depending on obsolete, but
manually installed, packages first, we were not aware they were
manually installed and demoted them.
I am struggling to come up with a test case for this as I can't
get the package objects in the cache to be in the right order for
the bug to trigger.
LP: #2102720
|
| |
|
|
|
|
|
|
| |
Particularly as Helmut pointed out we need to show which version we
selected for install if there is only one but there is a versioned
conflicts.
Reported-By: Helmut Grohne <helmut@subdivi.de> on IRC
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Reorder the if branches a bit to simplify the understanding
of the promotions, and allow us to keep track of which
dependency existed in the installed version.
Change the rule for promoting new recommends to only promote
new recommends to depends in *upgrade* and not *dist-upgrade*
per the test-resolve-by-keep-new-recommends test case.
This makes some sense: In a dist-upgrade, the solver could
otherwise decide to remove an installed package if both the
following hold:
(1) something needs the upgraded version | something else
(2) the upgraded version is not installable due to unsat recommends
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
We accidentally considered an Enhances a reason to keep
a package installed, which of course it is not, fix the
determination of "existing soft dependency" to only include
soft dependencies that should keep a package installed in
the autoremover to solve the issue.
This also fixes edsp/mantic-upgrade-rel-to-2024-05-29.edsp
to not install llvm-13-dev for clang-13 which is an installed
package with no upgrade.
Also ensure we stop after the first match; the DependsList()
is ordered by decreasing priority and we don't want to override
Recommends by Suggests in case a package declares both...
LP: #2101800
|
| |
|
|
|
|
| |
We incorrectly used the DependencyData of the first or group
member, however that only checked that the first or group member
was the same and that both either had a next member or not.
|
| |
|
|
| |
This is relevant when debugging common dependencies.
|
| |
|
|
| |
This only worked for version literals lol
|
| |
|
|
|
|
|
|
|
|
| |
Only move obsolete packages last that are automatically installed,
as we don't want to remove manually installed obsolete packages.
Add some missing const annotations to the operator[] arguments as
well that were needed.
LP: #2100247
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
| |
I marked exim4-daemon-light for install, which marked
exim4-daemon-heavy for not install, but now in
postfix Conflicts: mail-transport-agent
we saw "not exim4-daemon-heavy" as the reason for not installing
postfix. Oh noes.
|
| |
|
|
|
| |
This will print the underlying dependency which is nicer to
read.
|
| |
|
|
|
| |
This avoids relying on the inserted clause being at the back
of the clauses vector.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
| |
Pushing the stack in push and popping it in pop did not
really work correctly and is more complex than needed.
Instead, push the error stack at the start of the Solve()
method and revert at the end, such that we leave exactly
at the same error stack level we entered.
To handle error clearing on backtracking, just discard any
pending errors.
|
| |
|
|
|
| |
Implement the moving of the auto bit. The whole auto-bit management
is not entirely optimal yet, but this works.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
So far we only stored the last reason why something was decided,
for example, if "A depends B | C" and we assigned B=false, C=false,
we'd store "(not) C" as the reason for "(not) A".
This gives us only a partial implication graph; after all "C" was
not the *sole* reason for not installing A. This has two implications:
1. We cannot do conflict-driven clause learning
2. We cannot print excellent information about why packages cannot be
installed (or removed)
This commit is incomplete in addressing both; in particular, we always
store a clause as a reason for something that is not a root object;
whereas MiniSAT would only store a clause on propagation. That is,
if A depends B | C, and we install A, then we have to make a choice
between B|C. Let's say we pick B, we store 'A depends B|C' as the
reason whereas MiniSAT would not store a reason (because it picked
the "next best" unassigned literal).
Hopefully this is not going to be an issue. The reason is used to
calculate the assignments that caused the decision in MiniSAT, but
the idea is that we can just treat reason clauses with unassigned
values as "no reason".
The conflict explanation (WhyStr) has been changed to print the
strongest reason; which produces the same result as the previous
solution for the test suite. What does this mean?
If we look at A depends B|C, let's analyse:
Why not A?
We return the first assigned value for B|C, likely B.
We might have returned C here before as it was the
last assignment, but we might also return C here,
if B is not assigned.
Why B? We return A.
If we look at A conflicts B:
Why not A? Well B
Why not B? Well A
Thanks to the structure of the implication graph this is quite
simple, but also generalizing this to the CNF format should not
be hard.
A future version will extend clauses with backlinks to
pkgCache::Dependency*, allowing us to print useful information
to uses such as "A Depends B | C | D (>= 2)" in the real form, rather
than the expanded form which may be "A -> B | C | D=3 | D=2".
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
Instead of expensive rescoring of all outstanding items, use
unit propagation to find new units after conflicts.
We still count the items when adding them; but unless they are
0 or 1, which they should not be, they don't have any effect:
The size field is now effectively static.
If the size of an optional clause changed to 1, it is inserted
a second time, and then moves up to the top of the optional
items per the Work::operator< rules.
|
| |
|
|
|
| |
Use Var::toString() to print the variable, instead of duplicating
the code :D
|
| |
|
|
|
|
|
| |
This was a rather silly way to communicate state, and it was
in the wrong place. Notably also, multiple calls to the solver
had the options sticky, that is, if you run upgrade and then
it calls ResolveByKeep(), for example.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
We inadvertently performed a global ordering of all possible
solutions for the or group using CompareProviders3.
This however is not correct, as we lose the ordering of the
dependency group *too* much. Mostly this has no effect, but
you can see for example in test-explore-or-groups-in-markinstall
various instances of it.
Adjust said test case to work with the 3.0 solver to the extent
possible under the current design. The 3.0 solver does Recommends
after processing any manually installed packages; as such the
various Recommends test cases do not work: A `Recommends: okay|upgrade`
will not upgrade `upgrade` if it visited `upgrade` first.
This may change at a future time, but the correct semantics for
Recommends are not entirely clear. Notably, the existing solver
is not always consistent. You can see here where they matter,
but recently I added test-solver-recommends-depends in which
the Recommends do not influence the choice of other Depends.
|
| |
|
|
|
|
|
|
| |
Phased updates are ignored when strict pinning is on; such that
only the installed version will be available. By design of SAT
solvers, this means that the version selection clause is unit,
and hence the version can be directly propagated, i.e. that
choice is safe.
|
| |
|
|
|
|
|
|
|
|
| |
Already satisfied Recommends should be promoted to Depends; as well
as Recommends that are new, if the version they are from is an upgrade
(such that upgrading does not introduce unsat Recommends).
This only works for the case where the new Recommends actually
exist; test-resolve-by-keep-new-recommends is not yet implemented,
but this means the phasing tests will behave correctly.
|
| |
|
|
|
|
| |
This fixes the difference in test-unpack-different-version-unpacked,
but more importantly this is needed for phasing to be displayed
correctly once that is implemented.
|
| |
|
|
|
|
|
|
| |
This is a bit gnarly, but dist-upgrade is mapped to
is an upgrade + removals allowed + installs allowed
:D
|
| |
|
|
|
|
| |
Restore the depcache's MarkRequired logic for 3.0 solver; and
change the MarkInstall() call to pass a more correct value for
FromUser, to not override an existing automatic status.
|
| |
|
|
|
|
| |
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).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
| |
A SAT solver can run more or less forever, but that's not a good
user experience.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
When we have discovered all clauses for a version, discover
each possible solution for the clauses. This means that when
Discover(foo) is called _anything_ that could lead to foo becoming
uninstallable is translated; so we can extend this next by keeping
a list of reverse dependencies for each package and rejecting
those.
We limit the discovery to those variables that we did not already
enqueue as a negative fact at the root level, as those can never
become true.
We are utilizing a queue here which is not the most performant
solution possible, but where it excels is in producing usable
stack traces when debugging. Traversing the entire dependency
tree using recursion can easily produce thousand levels of
recursion.
The queue means that we discover packages in a breadth-first
manner compatible with the order in which we propagate dependencies,
which is helpful for consistency.
The queue did not appear as a bottleneck in benchmarking. If it did,
we could switch to a grow-only ring buffer (std::queue's underlying
deque also shrinks automatically which is suboptimal).
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
| |
operator[] is a bit annoying here, but oh well, what can we
do?
|
| |
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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
|
