| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
| |
References:
- https://www.reddit.com/r/cpp_questions/comments/pm63yx/why_clangtidy_says_use_emplace_back_instead_of/
- https://clang.llvm.org/extra/clang-tidy/checks/modernize/use-emplace.html
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Implement the "APT::Get::Upgrade-By-Source-Package" option as
the classic solver does.
Here this is equally straight forward now: We enqueue optional, but
eager, clauses of the form
foo=2 -> foo-data=2
for each sibling in the source version, assuming they are currently
installed, and the selection is not the current version.
This softly enforces upgrades of already installed siblings, but
in non-strict-pinning mode it will not affect the selection of
new packages to be installed.
A more complete solution to version selection by source package
also seems feasible, where we change the "priority" of versions
in the solver dynamically - currently they are statically evaluated.
Such that, when you select foo=2, and something installs foo-data,
foo-data would be installed in version 2 even if version 3 were its
candidate.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Aside from Clause, which initializes an std::vector
and an std::forward_list, which do not have constexpr
constructors in C++17, we can turn our inline functions
constexpr.
Using `constexpr` implies `inline`, so simplify that
accordingly where needed.
Adding noexcept to the function allows STL components
to utilize more optimized code paths.
Marking SameOrGroup as constexpr significantly improves
performance due to being in the hot path and it now being
inlined - removing branching by 10%.
iolveiolver
|
| |
|
|
|
|
|
| |
The for loop with if(foo) continue; return false; was highly
unusual as were the bunch of uses of `!` instead of `not`.
Gbp-dch: ignore
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
We were trying to compare the dependencies in the first version
with the dependencies in later version, but our loop started
at the first version as well due to an oversight in the use
of the increment operator.
Change the increment from postfix to prefix such that we start
iterating with the 2nd version in the list only.
This should yield minute performance optimizations:
before:
12: 17.80% 0.00% apt libapt-pkg.so.7.0.0 [.] EDSP::ResolveExternal(char const*, pkgDepCache&, unsigned int, OpProgress*)
14: --17.80%--EDSP::ResolveExternal(char const*, pkgDepCache&, unsigned int, OpProgress*)
20: | | |--6.34%--APT::Solver::DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator)
44: | | --0.85%--APT::Solver::DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator)
after:
12: 16.98% 0.00% apt libapt-pkg.so.7.0.0 [.] EDSP::ResolveExternal(char const*, pkgDepCache&, unsigned int, OpProgress*)
14: --16.98%--EDSP::ResolveExternal(char const*, pkgDepCache&, unsigned int, OpProgress*)
20: | | |--5.65%--APT::Solver::DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator)
42: | | --0.70%--APT::Solver::DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator)
|
| |
|
|
|
|
|
|
|
| |
Calculate the head and the tail of the clause in Propagate() and
check based on that if the clause is conflict/unit/undecided.
Special care has been taken to avoid the calculation of tail
when it is not necessary by placing it inside a helper lambda;
as well as skipping the calculation when the clause is inactive.
|
| |
|
|
|
|
|
| |
It used to be that we reached conflict clauses from the Solve()
loop, however that is no longer the case, so remove the else
branch, and turn the `else if (item.clause->optional)` into
a new `else` with an `assert(item.clause->optional)`.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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
|
| | |
|
| |
|
|
| |
Quite a convenient way since we need exactly lifted bool semantics
|
| |
|
|
|
|
|
|
|
|
| |
Refactor code into a doOne helper lambda, and then add loop
over the providers to use it.
This fixes a crash seen by Benjamin in a nice way than just
failing :)
Reported-by: Benjamin Drung
|
| |
|
|
| |
Where applicable
|
| |
|
|
| |
I do not know why I don't hit this
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This method is no longer needed technically speaking, we should
use Assume() instead. It turns out that there is a slight bug in
the propagation and some clauses that are unit end up on the heap
rather than having been propagated away, so we temporarily need
to keep an if for that around.
To accomodate the switch from Push() to Assume() we need to make
sure that the work item is pushed to our trail *after* we
have assumed it, such that reverting pushes it back to the work
heap.
Refactor the code to consistently use Assume() rather than supporting
Enqueue(), this vastly simplifies things. This is not fully accurate
in the current model and leads to unnecessary decision levels, since
sometimes we seem to be reaching unit clauses here.
This preserves traversal order by first removing the item from the
heap and then adding it back if we need to solve it again.
|
| |
|
|
|
| |
We can just re-use Enqueue() here to produce our conflict
message why am I being silly and duplicate this.
|
| |
|
|
|
| |
Matches the rename of depth() to decisionLevel() at a shorter
name.
|
| |
|
|
|
|
|
| |
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.
|
| |
|
|
|
| |
Move the DependencySolver methods and their helpers to the end of
the file.
|
| |
|
|
| |
Extract almost all dependency logic into a subclass
|
| |
|
|
|
|
|
| |
This removes the need for the forward references, thus fixing part
of the libc++ issues pointed out in [merge-511].
[merge-511] https://salsa.debian.org/apt-team/apt/-/merge_requests/511/diffs
|
| |
|
|
|
| |
This should make it easier for people with MiniSAT knowledge
to onboard themselves to the solver.
|
| |
|
|
|
| |
MUST becomes True, MUSTNOT becomes False, and NONE becomes
Undefined.
|
| | |
|
| |
|
|
| |
This simplifies the code _slightly_
|
| |
|
|
|
|
|
|
|
| |
Record a silly string if we backtracked such that we are aware
of it. We need to handle this in a broader fashion, but
this was at least breaking test-apt-never-markauto-sections
with remove-manual
LP: #2129819
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
When a user ran `apt install gpg`, the solver decided to remove
`gnupg` and `seahorse` because `seahorse` was only pulled in as
a Recommends of ubuntu-desktop and Recommends were resolved after
all other dependencies.
Solve this to most extent by introducing eager optionality: These
dependencies, while they do not take part in classic unit propagation,
are otherwise treated like hard dependencies and resolved as soon
as possible rather than after any hard dependencies.
This ensures that the Recommends of ubuntu-desktop on seahorse
is retained correctly, and as a result, gnupg is updated to the
latest version.
Oops: 6c8e32eb-665d-11f0-a985-fa163ec8ca8c
|
| |
|
|
|
|
|
|
|
|
|
|
| |
Lots of people have pinned an older version that is no longer
installable, or more common yesterday, we saw a lot of people
who seemingly manually installed a newer version of a deb than
in the repositories, causing the package to be considered obsolete,
which does not make much sense.
Oops: 4c39d922-410f-11f0-bbf9-fa163ec44ecd
Oops: a64054f6-4140-11f0-bbfd-fa163ec44ecd
Oops: a32196c1-661d-11f0-a97c-fa163ec8ca8c
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Instead of inadvertently sorting dependency targets against
the first alternative in an or group, sort them against the
current alternative as we should.
Otherwise we ended up sorting
gnome-shell | notification-daemon
With
Package: notification-daemon
Package: awesome
Provides: notification-daemon
into
gnome-shell | awesome | notification-daemon
<-we sorted this part wrongly->
This fixes a minor difference in test-release-candidate-switching
in one case, but not the other where the difference was actually
caused by the loss of install argument ordering information in
the new solver, so just flip the arguments so both solvers produce
the same outcome.
|
| |
|
|
|
|
| |
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.
|
