summaryrefslogtreecommitdiff
path: root/apt-pkg/solver3.h
Commit message (Collapse)AuthorAgeFilesLines
* solver3: Follow installed Suggests earlierJulian Andres Klode2026-05-171-3/+3
| | | | | | | We accidentally followed "keepauto" and friends earlier, breaking `apt why` for suggested packages. Reported-By: uau on IRC
* solver3: Upgrade by source packageJulian Andres Klode2026-02-171-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | 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 placesJulian Andres Klode2026-02-101-37/+37
| | | | | | | | | | | | | | | | | | | 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: Cache straight pointers in candidate cacheJulian Andres Klode2026-02-101-3/+3
| | | | | This reduces its memory usage by half and turns it into a fast map - no destructors needed (and 0 initialization).
* solver3: Mark DependencySolver as finalJulian Andres Klode2026-02-101-1/+1
|
* solver3: Use classical watchers for propagationJulian Andres Klode2026-01-311-2/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 anymoreJulian Andres Klode2026-01-311-3/+0
|
* solver3: Use LiftedBool for Obsolete stateJulian Andres Klode2026-01-311-1/+1
| | | | Quite a convenient way since we need exactly lifted bool semantics
* solver3: Ensure rule-of-3 memory safety for ContiguousCacheMapJulian Andres Klode2026-01-051-0/+4
|
* solver3: Modernize std::find() to std::ranges::containsJulian Andres Klode2026-01-051-4/+4
| | | | Where applicable
* solver3: Remove Push() and refactor Solve()Julian Andres Klode2026-01-051-2/+0
| | | | | | | | | | | | | | | | | | | | | 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.
* solver3: Rename depth to levelJulian Andres Klode2026-01-051-16/+16
| | | | | Matches the rename of depth() to decisionLevel() at a shorter name.
* solver3: Rename decision to assignmentJulian Andres Klode2026-01-051-11/+10
| | | | | | | 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.
* solver3: Reorder the source codeJulian Andres Klode2026-01-051-2/+1
| | | | | Move the DependencySolver methods and their helpers to the end of the file.
* solver3: Extract DependencySolverJulian Andres Klode2026-01-051-70/+84
| | | | Extract almost all dependency logic into a subclass
* solver3: Refactor to use a namespaceJulian Andres Klode2026-01-051-210/+204
| | | | | | | 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
* solver3: Rename key concepts to MiniSAT namesJulian Andres Klode2026-01-051-28/+29
| | | | | This should make it easier for people with MiniSAT knowledge to onboard themselves to the solver.
* solver3: Rename Decision to LiftedBoolJulian Andres Klode2026-01-051-16/+16
| | | | | MUST becomes True, MUSTNOT becomes False, and NONE becomes Undefined.
* solver3: Implement value(Lit) and use itJulian Andres Klode2026-01-051-1/+18
|
* solver3: Refactor Assume(), Enqueue() from Var to LitJulian Andres Klode2026-01-051-3/+3
| | | | This simplifies the code _slightly_
* solver3: Introduce a Lit type to hold literalsJulian Andres Klode2026-01-051-0/+48
|
* solver3: Allow removing manually installed packagesJulian Andres Klode2025-10-251-1/+1
|
* solver3: Do not lose notion that we backtrackedJulian Andres Klode2025-10-251-0/+2
| | | | | | | | | 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
* solver3: Eagerly satisfy previously satisfied RecommendsJulian Andres Klode2025-10-251-1/+4
| | | | | | | | | | | | | | | | | | 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
* Include standard headers to fix clang compiler errorBiswapriyo Nath2025-06-181-0/+1
| | | | | | | | This commit fixes the following compiler errors. apt-pkg/acquire.cc:833:51: error: no template named 'function' in namespace 'std' apt-pkg/contrib/error.cc:198:59: error: no member named 'front_inserter' in namespace 'std' apt-pkg/solver3.h:44:22: error: no template named 'is_trivially_constructible_v' in namespace 'std' methods/http.cc:1029:24: error: no member named 'inserter' in namespace 'std'
* solver3: Avoid FTBFS with g++ 14.2 on arm{el,hf}Julian Andres Klode2025-06-101-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | With an explicit {} initialization, g++ 14.2 on armhf and armel seems to generate the default constructor for the vector too early, or in the first place, outside of solver3.cc where the constructor is defined. Without {}, this compiles again. 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; | ^~~~~~
* solver3: Explicitly declare and define ~SolverJulian Andres Klode2025-06-101-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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; | ^~~~~~
* solver3: Merge intersecting dependenciesJulian Andres Klode2025-05-271-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* solver3: Initialize startTime if not set in Pop()Julian Andres Klode2025-05-261-1/+1
| | | | | | | | 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.
* solver3: Remove Work::choiceJulian Andres Klode2025-05-261-10/+3
| | | | | | | | | | | | 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.
* Introduce apt why, apt why-notJulian Andres Klode2025-05-191-0/+3
| | | | | | | | | | | 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).
* solver3: Handle previously satisfied Suggests lastJulian Andres Klode2025-03-201-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* apt-pkg/solver3.h: avoid static_assert(false)Johannes Schauer Marin Rodrigues2025-03-141-1/+3
| | | | | | | | | | | | | | | | | With older compilers (g++ and clang from Bookworm), static_assert(false) will result in: /home/josch/git/apt/build/include/apt-pkg/solver3.h:52:24: error: static assertion failed: Cannot construct map for key type 52 | static_assert(false, "Cannot construct map for key type"); | ^~~~~ This commit implements the terrible but more valid workaround according to: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2593r0.html Original solution from here: https://stackoverflow.com/questions/14637356/static-assert-fails-compilation-even-though-template-function-is-called-nowhere/14637534#14637534 That way, apt will compile with compilers in Bookworm again.
* solver3: Fix Recommends/Suggests vs Enhances confusionJulian Andres Klode2025-03-121-0/+5
| | | | | | | | | | | | | | | | | | 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
* solver3: Do not prefer new installs over manually installed obsoletesJulian Andres Klode2025-03-091-5/+8
| | | | | | | | | | 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
* solver3: Verbose error messagesJulian Andres Klode2025-03-081-0/+22
| | | | | | | | | | | | | | | | | | | | | | 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.
* solver3: Support pretty printing clausesJulian Andres Klode2025-03-061-1/+1
| | | | | This will print the underlying dependency which is nicer to read.
* solver3: cleanup operators for VarJulian Andres Klode2025-03-061-8/+3
| | | | Particularly, use single line and implement operator!=
* solver3: refactor: Return inserted Clause in AddWork()Julian Andres Klode2025-03-061-1/+1
| | | | | This avoids relying on the inserted clause being at the back of the clauses vector.
* solver3: Simplify Var pointer taggingJulian Andres Klode2025-03-061-15/+16
| | | | | | | | Use an integer and tag the lowest bit manually. This makes it much easier to next convert this into a literal. Add some constexpr and remove an unnecessary assertion on CastPkg().
* Add missing #include <memory>Julian Andres Klode2025-02-151-0/+1
|
* solver3: Store clauses as the reasons for decisionsJulian Andres Klode2025-02-141-4/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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".
* solver3: Remove work rescoring in favor of unit propagationJulian Andres Klode2025-02-141-4/+0
| | | | | | | | | | | | | 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.
* solver3: Pass EDSP flags directly rather than via configJulian Andres Klode2025-02-141-4/+6
| | | | | | | 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.
* solver3: Defer 3.0 'deep' autoremoval to 3.1, fix autoremoveJulian Andres Klode2025-02-141-1/+2
| | | | | | 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.
* solver3: Reject reverse dependencies nativelyJulian Andres Klode2025-02-141-4/+2
| | | | | | | | | | | | | | | | | | 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.
* solver3: Implement a timeout, default 10sJulian Andres Klode2025-02-141-0/+5
| | | | | A SAT solver can run more or less forever, but that's not a good user experience.
* solver3: Discover recursive dependenciesJulian Andres Klode2025-02-141-0/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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).
* solver3: Defer version selection where possibleJulian Andres Klode2025-02-141-0/+2
| | | | | | | | | | | | | 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.
* solver3: Avoid std::vector for statically sized arraysJulian Andres Klode2025-02-071-15/+59
| | | | | | | | | | 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.
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-07-18 05:18:12 +0000