apt/apt-pkg/solver3.cc, branch mainDebians commandline package managerhttps://git.kalnischkies.de/apt/atom?h=main2026-04-08T10:40:55Zapt: push to emplace C++11 if possible2026-04-08T10:40:55ZHerman SemenoffGermanAizek@yandex.ru2026-04-08T08:51:08Zurn:sha1:ef70431f02e2ec13ecedab7ac342574e52d1877b
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
solver3: Upgrade by source package2026-02-17T09:28:17ZJulian Andres Klodejak@debian.org2026-02-17T09:28:17Zurn:sha1:9f3ecca2b32e4fe56a05811392e01416092f85fa
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.
solver3: Use constexpr and noexcept in most places2026-02-10T19:59:03ZJulian Andres Klodejak@debian.org2026-02-06T14:50:04Zurn:sha1:42dab6a46748ac80f0217212932b74af1af94017
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
solver3: Minor style refactorings2026-02-10T19:59:03ZJulian Andres Klodejak@debian.org2026-02-01T08:25:31Zurn:sha1:8e1750a22ef8be521bdb0542a78438f8d8abc54e
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
solver3: Avoid manual delete[] in favor of RAII2026-02-10T19:59:03ZJulian Andres Klodejak@debian.org2026-01-31T21:41:04Zurn:sha1:e7c1adda00abd16285f5eb53c48587855f2a2992solver3: Fix off-by-one missing optimization2026-02-10T19:59:03ZJulian Andres Klodejak@debian.org2026-01-31T21:33:40Zurn:sha1:7d84e1f830727ca5008566113e7dfd35df049bd6
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)
solver3: Refactor Propagate() using lazy head/tail2026-02-10T19:59:03ZJulian Andres Klodejak@debian.org2026-01-31T20:59:32Zurn:sha1:7d5ec84c13227290cfb1bb83d27ae354200bcb02
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.
solver3: Remove dead code2026-02-10T19:59:03ZJulian Andres Klodejak@debian.org2026-01-31T20:04:02Zurn:sha1:5cbf75ac2e4845b9ed1026f1d11af129e54aaf5b
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)`.
solver3: Use classical watchers for propagation2026-01-31T16:30:20ZJulian Andres Klodejak@debian.org2025-12-29T17:47:15Zurn:sha1:1fbb857b6b2cbddcea9e8b03aa0c766c72e91f34
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
Erased items do not exist anymore2026-01-31T14:10:14ZJulian Andres Klodejak@debian.org2025-12-29T21:20:29Zurn:sha1:267fd0117a057afd88bc15bfb4f4d688804a9ab4