summaryrefslogtreecommitdiff
path: root/apt-pkg
Commit message (Collapse)AuthorAgeFilesLines
* 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-052-13/+10
| | | | Where applicable
* solver3: Add a strange assertionJulian Andres Klode2026-01-051-0/+2
| | | | I do not know why I don't hit this
* solver3: Remove Push() and refactor Solve()Julian Andres Klode2026-01-052-52/+24
| | | | | | | | | | | | | | | | | | | | | 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.
* macros: Introduce must_succeed() macroJulian Andres Klode2026-01-051-0/+8
| | | | | This is like assert() but never compiled out so can be used with function calls that have side effects.
* solver3: Re-use existing error message code in Solve()Julian Andres Klode2026-01-051-7/+4
| | | | | We can just re-use Enqueue() here to produce our conflict message why am I being silly and duplicate this.
* solver3: Rename depth to levelJulian Andres Klode2026-01-052-23/+23
| | | | | Matches the rename of depth() to decisionLevel() at a shorter name.
* solver3: Rename decision to assignmentJulian Andres Klode2026-01-052-47/+46
| | | | | | | 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-052-442/+438
| | | | | Move the DependencySolver methods and their helpers to the end of the file.
* solver3: Extract DependencySolverJulian Andres Klode2026-01-053-88/+116
| | | | Extract almost all dependency logic into a subclass
* solver3: Refactor to use a namespaceJulian Andres Klode2026-01-053-241/+239
| | | | | | | 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-052-55/+56
| | | | | This should make it easier for people with MiniSAT knowledge to onboard themselves to the solver.
* solver3: Rename Decision to LiftedBoolJulian Andres Klode2026-01-052-47/+47
| | | | | MUST becomes True, MUSTNOT becomes False, and NONE becomes Undefined.
* solver3: Implement value(Lit) and use itJulian Andres Klode2026-01-052-19/+41
|
* solver3: Refactor Assume(), Enqueue() from Var to LitJulian Andres Klode2026-01-052-25/+26
| | | | This simplifies the code _slightly_
* solver3: Introduce a Lit type to hold literalsJulian Andres Klode2026-01-051-0/+48
|
* weakptr: Simplify destructor to use range-based forJulian Andres Klode2025-11-101-3/+2
| | | | Explicit iterators considered harmful :)
* Correctly copy provided version in m-a lazy-initJulian Andres Klode2025-11-101-1/+1
| | | | | | | | When a provides was copied, we inadvertently copied the package version instead of the provided version. Copy the provided version instead. Closes: #1120463
* Revert "depcache: Allow changing multi-arch versions for removed siblings"Julian Andres Klode2025-10-261-4/+0
| | | | | | | | | | | | | | | | This reverts commit 74636b64a7ee56637a3ce4ddc1d060ca9f8b77e1. Adjust the test case accordingly, as it is no longer possible to install libgcc-s1:s390x. We need to sort this out in the ToDepCache translation layer at a later time. Sadly the depcache rejects valid solutions like this; solving this isn't trivial. Technically we need to split up the FromUser and auto-bit handling to solve this, but even then, MarkDelete() with FromUser=0 moves the auto-bit on metapackages; this doesn't happen when doing FromUser=1, so we can't always do FromUser=1. Fixes: a3fca052ca21ad222ac7f2fdd7f3fe84b44beb60
* solver3: Allow removing manually installed packagesJulian Andres Klode2025-10-251-1/+1
|
* solver3: Do not lose notion that we backtrackedJulian Andres Klode2025-10-252-1/+7
| | | | | | | | | 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
* depcache: Allow changing multi-arch versions for removed siblingsJulian Andres Klode2025-10-251-0/+4
| | | | | Do not prevent us from changing the version of a foreign package because a sibling that is being removed has a different candidate.
* Implement architecture variantsJulian Andres Klode2025-10-2512-3/+242
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Architecture variants are children of an architecture that share the same ABI but are optimized for different ISA levels. They are available in Ubuntu 25.10 and newer, and not supported in Debian or other distributions. A deb built for a variant contains the Architecture-Variant field, and the Architecture field points to the baseline, for example: Architecture: amd64 Architecture-Variant: amd64v3 However, the apt-get indextargets command reports the variant in the Architecture: field, and most of the code in APT presents the variant as the architecture. There are two types of variants: 1. Standalone variants are recorded in the Architectures field of the Release file as if they were a real architecture: Architectures: amd64 amd64v3 Standalone architecture variants only fetch the standalone architecture variant's Packages file. To do this, this patch changes the code such that the variants indextargets "supplant" the base targets. This may have complicated outcomes on the apt-get indextargets command. 2. Other variants can only be identified by their files being recorded with hashes in the Release file. APT fetches both the base architecture's as well as the variant's Packages file. Variants are configured in the APT::Architecture-Variants list. Image builders may want to build specific variant images using APT::Architecture-Variants { "amd64v3"; } But this commit also implements an automatic discovery mechanism using the varianttable and /proc/cpuinfo. APT::Architecture-Variants "auto";
* Move split() to APT::String::Split()Julian Andres Klode2025-10-253-15/+14
| | | | This splits based upon contiguous whitespace as separators
* solver3: Eagerly satisfy previously satisfied RecommendsJulian Andres Klode2025-10-252-3/+9
| | | | | | | | | | | | | | | | | | 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
* configuration: Add MoveSubTree with overwrite=falseJulian Andres Klode2025-10-252-3/+13
|
* Correctly append or remove FD_CLOEXECJulian Andres Klode2025-10-202-4/+10
| | | | | Rather than just setting the flags to 0 or FD_CLOEXEC, read the current value and append or remove as needed.
* ExecFork: Simplify closing and make it safeJulian Andres Klode2025-10-201-31/+19
| | | | | | | | | Implement a wrapper around FD_CLOEXEC and use it in place of the raw fcntl(). This wrapper _Exit()s the child if the operation failed. Restructure the close_range() handling to simply mark all fds for closing first and then "reopen" the ones we should keep.
* Add some comments and tests around Keep-Fd orderingJulian Andres Klode2025-10-201-0/+1
|
* ExecFork: Use close_range() if availableJulian Andres Klode2025-10-201-2/+32
| | | | | | | | | | | | | Use close_range() if we have it in preference to iterating over /proc/self/fd and falling back to closing all possible fds. This builds sets of ranges to close that take into account the APT::Keep-Fds vector, and a test case is provided to ensure correctness of the splitting logic. Preference is given to close_range() over /proc as in the optimal case, this results in a single system call!
* Move "Tried to start delayed item […], but failed" to debuggingJulian Andres Klode2025-10-041-4/+2
| | | | | | | | We don't quite know why a stuck queue cannot get unstuck here, and it's possible that this is causing the queue to stall, but shrug. Closes: #1111554
* Add history undo, redo, and rollback featuresSimon Johnsson2025-10-022-11/+51
|
* History Command and ParsingSimon Johnsson2025-09-262-0/+270
|
* edsp: Do not skip lines (fixes Architecture reading)Julian Andres Klode2025-08-261-31/+31
| | | | | | | | | | | | | | | We skipped the Architecture: line because when the outer loop got to it, the inner loop started and read the next line after it. Get rid of the nested loop instead, and first run a loop to find the request line, and then a second loop to parse the request flags. An alternative would be to use a combined loop that supports non-compliant protocol implementations, but that's harder to read and we don't expect there to be any especially on the request side.
* edsp: Clear architecture cacheJulian Andres Klode2025-08-261-0/+4
| | | | We need to actually use the architecture values we set
* Fix indentation compiler warning with clangBiswapriyo Nath2025-08-261-2/+5
| | | | | | This commit fixes the following compiler warning. cacheiterators.h:423:54: warning: misleading indentation; statement is not part of the previous 'if' [-Wmisleading-indentation]
* debListParser: Cache `essential` and `myArch` moreJulian Andres Klode2025-08-262-13/+10
| | | | | | | | | | | | | | | | | | | Lookup these variables in the constructor once, rather than once per package. This requires a bit of care as debListParser::UsePackage() defaults to "all" for essential when unset, hence we simply change its == "all" comparisons to == "all" || .empty().# This removes any per-paragraph configuration lookups from the file parser. Also parse myArch from ParseProvides down to ParseDepends() as that call ended up causing it to query APT::Architecture *again* since the function we call is static. Together, the removed config lookups safe about 2.3% of cache generation runtime.
* solver3: Allow any downloadable version to mark a package as not obsoleteJulian Andres Klode2025-08-261-3/+8
| | | | | | | | | | | | 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
* solver3: Sort dependency targets against current alternativeJulian Andres Klode2025-08-261-4/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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.
* Fix stuck acquire queues on partial server errorsJulian Andres Klode2025-06-241-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | When a server responds with two InRelease files, but one is good, and the other indicates a temporary error, we queued the other indices from the good repository for downloading and then queued the retry. The resulting queue ended up with items having fetchAfter=0 before the item with fetchAfter=<something>, causing the Run() loop to not detect a stuck queue. Change the order of the queue such that the highest retry-after items comes first; this ensures that we always see stuck queues. This of course changes the behavior of retries in that if one file fails temporarily we block the entire server. This does seem more beneficial in the common case - if one file fails, probably all of them fail, and there's no point bombarding the server with requests for indices from good repositories until all have failed. The actual root cause is more that the remaining items are Enqueued like this: 1. Enqueue jammy/InRelease (delayed) 2. Enqueue jammy-updates/main all Packages The resulting queue ended up being: jammy-updates/main all Packages jammy/InRelease (delayed) But Enqueue() only calls Cycle() when there are no items in the queue already - after all, any item that is already running will call Cycle() eventually. Or so was the case until we added the retry-after handling. It's unclear why we don't Cycle() all the time when enqueuing a new item, given that our pipeline might not be filled yet, and we could send the request to the server while waiting for data on a running item. Trying to always Cycle() however led to regressions that still need investigating. Given that, this solution certainly is the more easy to reason about one. LP: #2003851
* Include standard headers to fix clang compiler errorBiswapriyo Nath2025-06-183-0/+3
| | | | | | | | 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; | ^~~~~~
* Avoid cast alignment warning in cache string viewJulian Andres Klode2025-06-101-1/+1
| | | | | | | | | | | | | | | | | | The cache allocates strings as uint16_t size; char content[]; char zero; Aligned to the uint16_t. When doing the casting, this causes a warning on some architectures that cannot do unaligned loads, such as armhf. Use __builtin_assume_aligned() to explictly say that the pointer is aligned to 16 bits. This is a bit of a backhanded approach, as the warning seems to be actually avoided by the function returning a void* rather than the assumed alignment, but this is very much self-documenting.
* solver3: Filter installed RecommendsJulian Andres Klode2025-06-101-0/+10
| | | | | | When inspecting Recommends of installed packages, filter them to the installed packages only, as we want to avoid switching between alternatives of recommended packages.
* solver3: Explicitly declare and define ~SolverJulian Andres Klode2025-06-102-0/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Ignore Architecture: all for obsoleted-byJulian Andres Klode2025-06-101-1/+3
| | | | | | | | | | | | 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.
* solver3: Only merge dependencies on the same packageJulian Andres Klode2025-05-281-6/+14
| | | | | Avoid or groups and dependencies on different (virtual) packages, to avoid some common pitfalls like the added xorg test case.
* solver3: Merge Depends into RecommendsJulian Andres Klode2025-05-271-7/+23
| | | | | | | | | | | | | | | | | | | | | | | 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.
* solver3: Merge intersecting dependenciesJulian Andres Klode2025-05-272-6/+49
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Assume manual packagesJulian Andres Klode2025-05-261-1/+16
| | | | | | | | | | | | | | | | | | | | 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
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-10-14 02:04:48 +0000