summaryrefslogtreecommitdiff
path: root/apt-pkg/solver3.cc
Commit message (Collapse)AuthorAgeFilesLines
* solver3: Avoid std::vector for statically sized arraysJulian Andres Klode2025-02-071-11/+11
| | | | | | | | | | 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.
* solver3: Add const where helpfulJulian Andres Klode2025-02-071-4/+4
| | | | | operator[] is a bit annoying here, but oh well, what can we do?
* solver3: Point to stored clauses, do not copy themJulian Andres Klode2025-02-071-36/+39
| | | | | | 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.
* solver3: Use a package clause for optional rootsJulian Andres Klode2025-02-071-4/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* solver3: Refactor Dump() to toString()Julian Andres Klode2025-02-071-50/+25
| | | | | This vastly simplifies the code at the expense of performance, lol.
* solver3: Support comparing packages and versionsJulian Andres Klode2025-02-071-8/+15
| | | | | | | | | | | When comparing packages, we compare the best version for the package. To determine the best version, the rules for comparisons are applied normally. This allows us to mix packages and versions in a clause as the solutions for a dependency, which means we'll be able to defer the selection of a particular version of a package to a later time.
* solver3: Replace PropagateInstall() with Discover()Julian Andres Klode2025-02-071-75/+65
| | | | | | | | | | | | | | | Just propagate the stored clauses after we have discovered them; this is quite straightforward. We now more reliably discover common dependencies at the package level, adjust the test case accordingly. The next step is to make discovery recursive, or iterative, to build an entire recursive tree from all roots, and then we can reject reverse dependencies based on it. A bunch of refactorings are needed in the process. We remove the useless Hint enumeration and insert a flags struct into the State, such that we can record whether a package/version has been discovered, to avoid spending double time on discovery.
* solver3: Extract TranslateOrGroup() out of EnqueueOrGroup()Julian Andres Klode2025-02-071-39/+36
| | | | | | | This is not *purely* a refactoring, we accidentally used the version of the dependency when enqueuing conflicts rather than the reason, so the conflict string in the test case is different; the logging had the same issue.
* solver3: Extract Clause out of WorkJulian Andres Klode2025-02-071-54/+57
| | | | | Extract clause into a separate struct and embed a copy of it in our Work class.
* solver3: Simplify WhyStr()Julian Andres Klode2025-02-071-16/+5
| | | | Reuse the generic variable rendering
* solver3: Cache all configuration callsJulian Andres Klode2025-02-071-9/+4
|
* solver3: Cache calls to policyJulian Andres Klode2025-02-071-6/+8
| | | | It's a bit silly otherwise.
* solver3: Propagate single choice clauses as factsJulian Andres Klode2025-02-071-9/+11
| | | | | | | | | | | | This removes a bunch of complexity, and generalizes the propagation behavior, such that we don't need to do if (w.solutions.size() == 1 && not w.optional) Enqueue() else AddWork(w); in our callers.
* solver3: Early exit when propagating satisfied clausesJulian Andres Klode2025-02-071-4/+5
|
* solver3: Partially generalize work items from Version to VarJulian Andres Klode2025-02-071-29/+33
| | | | | | | | Store all possible solutions and choices as Var. Currently any Var in here must be a Version because CompareProviders3 cannot compare versions against packages yet, but in the future (TM), this will allow storing packages directly in clauses, which allows defering version selection to a later point.
* solver3: Simplify work orderingJulian Andres Klode2025-02-071-14/+4
| | | | | | | | | | Moving the optional != b.optional comparison ahead of the group one allows us to get a better behavior; and now we avoid the nested if. Also remove the special cases that ordered based on the reason of the work item, these have been superseded by groups a while ago.
* solver3: Drop unused upgrade flagJulian Andres Klode2025-02-071-2/+2
| | | | This was leftover from before the groups were added.
* solver3: Credit MiniSATJulian Andres Klode2025-01-301-0/+11
| | | | Gbp-Dch: ignore
* solver3: Use a propagation queueJulian Andres Klode2025-01-301-8/+24
| | | | | | | | | | | | | | | | | | | Instead of directly propagating in a recursive fashion, queue propagations in a queue and work on them in a loop per the miniSAT paper. We call Propagate() only at the end of the FromDepCache() function and then in the Solve loop. Delaying the initial propagation means that we get a stronger reasoning: Assume you have x->a->b->c, y->c and you install x,y: - Previously we traversed: x, y, x->a, a->b, b->c, (y->c) - but now we traverse: x, y, x->a, y->c, a->b, (b->c) Notably c now has the implication y->c instead of x->a->b->c. Inside the solver we need to call Propagate in a loop: Propagating facts can fail and we then backtrack. If backtracking is succesful, we have gained a new fact to propagate.
* solver3: Replace Install() with Enqueue(), and PropagateInstall()Julian Andres Klode2025-01-301-41/+33
| | | | | | Do not enqueue common dependencies if a version is selected already, this avoids test suites changing now in behavior as the ordering is different.
* solver3: Remove NewUnsatRecommends groupJulian Andres Klode2025-01-301-2/+0
| | | | | | This is more or less unused; but it particularly has the bad problem of forcing new unsat recommends to be solved *before* dependencies. Which is awkward.
* solver3: Soft unit propagation for optional itemsJulian Andres Klode2025-01-301-2/+7
| | | | | If both items are optional, unit items should be processed first.
* Drop usage of macro APT_OVERRIDE for simple overrideDavid Kalnischkies2025-01-051-2/+2
| | | | | | | | | We were rather inconsistent in using it and as our public headers contain deduction guides (a c++17 feature) it seems silly to try to hide a c++11 feature in a macro, so lets stop this charade and drop the macro and while we are changing all these lines lets apply [[nodiscard]] (another c++17 feature) and other suggestions from clang-tidy and formatting for a little more consistency.
* solver3: Reject all non-candidates outright for strict pinningJulian Andres Klode2024-12-031-25/+18
| | | | | | | | Reimplement strict pinning by rejecting the non-candidates when translating the problem from the depcache to the solver. This is substantially better than restricting the list of alternatives for an or group to only include allowed ones for debugging purposes, albeit a bit slower.
* solver3: Add a missing debug level checkJulian Andres Klode2024-12-031-1/+2
|
* solver3: Fix intransitivity of version comparison on upgradeJulian Andres Klode2024-12-021-11/+17
| | | | | | | | | | | | | | | | | | | | | | | | | We only compared candidate to installed version, but candidate should dominate all versions, otherwise we end up in the fancy problem of elpa-notmuch in upgrade-noble-t64-remove-desktop-2024-03-29.edsp Where we had three versions: not-installable 0.38.3-1ubuntu1 candidate 0.38.2-1.1ubuntu2 installed 0.38.2-1ubuntu2 And received an ordering: installed > non-installable > candidate despite candidate > installed This is only visible with no-strict-pinning right now, as we are otherwise filtering out invalid choices (and hence we only have candidate and installed otherwise).
* solver3: Refactor Install(Ver) to PropagateInstall(Ver)Julian Andres Klode2024-11-021-30/+34
| | | | | | | | | | This is the first part of changing from Install() to Enqueue() for installs, affecting only the versions. For packages, we still have to resolve the group changing: When propagating cleanly, we don't have the information as to which group the package was part of, hence we are no longer able to queue the version selection of upgrades before obsolete packages, for example, which needs solving.
* solver3: Check whether installable versions are allowedJulian Andres Klode2024-11-021-7/+10
| | | | | | | We only checked if they were still installable, but not if they were allowed. We should removed the allowed version handling altogether presumably - we should just mark non-allowed versions as rejected early on.
* solver3: A version selected for install already is allowed.Julian Andres Klode2024-11-021-1/+1
|
* Add a FIXME around the heap compactionJulian Andres Klode2024-11-021-0/+2
| | | | | | | | | | | | | | Our work heap is currently cleaned from deeper levels by removing the entries from the heap and then remaking the heap which is very inefficient. We should mark the items as erased instead, and only do the remove & make_heap dance if we have a lot of erased entries in there. Possibly we maybe should use a structure that actually allows removing entries, that is, an std::set, but that warrants more investigation on performance aspects.
* solver3: Rename the 'dirty' bit to 'erased'Julian Andres Klode2024-11-021-6/+6
| | | | This captures the meaning better
* solver3: Remove the Reject() function, propagate in Enqueue() insteadJulian Andres Klode2024-11-021-52/+37
| | | | | Long term we should have a propagate queue, this is the minimal change to keep the behavior identical, a first step on the road.
* solver3: Move needsRescore from Reject to Enqueue()Julian Andres Klode2024-11-021-4/+3
|
* solver3: Remove obsolete checksJulian Andres Klode2024-11-021-44/+5
| | | | | These checks are no longer needed since Enqueue() ensures the correctness for us.
* solver3: Introduce new Assume() and Enqueue() helpers and use themJulian Andres Klode2024-11-021-23/+41
| | | | | | | | | | | | | These are taken roughly from the MiniSAT paper. We still have a bit to go in actually encoding all clauses so the reasons are still variables, and Assume() isn't fully working yet. Adjust the existing Install()/Reject() code to use these functions, we already see additional lines in the log that we failed to log before, and this ensures more consistency. This is sort of still the wrong direction: Install()/Reject() do the propagation too; but that is tbd.
* solver3: Rename Reason to VarJulian Andres Klode2024-11-021-38/+38
|
* solver3: Track all assignments and undo them individuallyJulian Andres Klode2024-11-021-56/+71
| | | | | | | Adopt MiniSAT's strategy for dealing with assignments and choices, having a single step undoOne() function to undo one and record them all on the queue; this should likely speed up backtracking since we no longer need to rescan everything.
* Fix obsoleted-by handling for experimentalJulian Andres Klode2024-08-121-11/+37
| | | | | | | | | | Basically this boils down to checking that the priority of the source candidate candidate is higher or equal than the priority of the package's candidate that is being under consideration. It stands to reason if we maybe we should actually calculate a source candidate version; this will look similar but may perhaps perform slightly different.
* solver3: Refactor Reason.Pkg()/Reason.Ver() use with iteratorJulian Andres Klode2024-07-161-6/+6
| | | | More code but nicer to read
* solver3: Formatting cleanupJulian Andres Klode2024-07-021-8/+8
| | | | Run clang-format
* solver3: Only demote obsolete packages in choices for upgradesJulian Andres Klode2024-07-021-2/+3
| | | | | If we are not upgraded, we should continue to keep the installed package installed if possible.
* solver3: Consider packages as obsolete and not versionsJulian Andres Klode2024-07-021-11/+24
| | | | | | | | | | | | | This makes more sense, as all package versions are obsolete that are not the candidate, usually. Pay special attention to no-strict-pinning: If we don't have strict pinning, a package without a candidate version may still be non-obsolete if the latest version is not obsolete. Likewise, in no-strict-pinning any later source version that exists will cause the package to be considered obsolete, rather than just candidates.
* solver3: Refactor (rewrite) FromDepCache()Julian Andres Klode2024-07-011-36/+23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Refactor the various Install requests into a single one and move some stuff around, this should be a bit easier to maintain and we don't repeat ourselves all the time. This accidentally uncovered some bugs in the code, that get fixed by this: - The UpgradeManual and InstallManual groups did not work correctly, Essential packages were Install and others were Upgrade. - Automatically installed packages falsely got promoted to the manual groups as they got promoted into the manual code path, whenever we ran without allowing their removal. - The combination of --mark-auto --auto-remove now works correctly We previously skipped the installation of automatically installed packages when we did autoremoval, but we did not consider if the action was protected, that is specified on the command-line. Now we do not autoremove protected actions, and have added a test case for it. - The AllowRemoveManual option no longer is applied if removals are generally denied. Closes: #1071519
* solver3: Unmark packages before setting any in ToDepCacheJulian Andres Klode2024-07-011-0/+2
| | | | | | We should set the Mark/Garbage flags for all packages so we don't end up in an inconsistent state, so reset the flags for each package before evaluating further.
* solver3: Do not accidentally promote Replaces and Enhances to dependenciesJulian Andres Klode2024-07-011-1/+3
| | | | | | | | | | As part of the refactoring, we allowed the code to work on unimportant dependencies as we needed to promote Suggests to Depends if they are currently satisfied. However, Replaces and Enhances were not considered properly and both are not negative dependencies so they were accidentally promoted to Depends too if they were currently satisfied.
* solver3: Order obsolete choices lastJulian Andres Klode2024-06-131-8/+41
| | | | | | | | | | | | | | | | | | | | | | This has two aspects: 1. For a dependency A | B | C we order the obsolete packages last, that is, if A is obsolete, this gets reordered to B | C | A, such that we try to pick non-obsolete packages first to ease upgrade calculation. 2. When comparing two dependencies, we order dependencies into three groups: First we satisfy dependencies mentioning only non-installed (NEW) packages, then we satisfy "normal" dependencies, and finally we satisfy any dependencies mentioning obsolete packages. This means for example if you have obsolete libfoo1 and a new libfoo1t64, that we will see Depends: libfoo1t64 before any Depends: libfoo1 (which may expand to libfoo1 | libfoo1t64), so we effectively will have selected "replacement" packages this way already before getting to older packages where we would have to choose between the obsolete package and its replacement.
* solver3: Remove no longer necessary comparisonsJulian Andres Klode2024-06-131-22/+0
| | | | | | | | | | | | Comparing the size of work items is not strictly needed; we check if items have a single or no solution and propagate them early on, but it doesn't matter much if we solve A|B or C|D|E first. This will allow us to get rid of all the resizing business later on, and switch to using literal watching where we only watch one of the literals on the right hand side. Likewise, the upgrade case mattered initially in testing, but seems to have resolved itself.
* solver3: Group work itemsJulian Andres Klode2024-06-131-21/+33
| | | | | | | | | | | | | | | | | | | | | Our backtracking is chronological, so we will first try alternative choices or skip optional items in later groups. So installing manually installed packages before automatically installed ones allows manually installed packages to remove automatically installed packages easily. If we did automatic packages first, we'd keep back upgrades for manual packages or change choices for their dependencies, or would have to backtrack harder to get back to the right decision level. That's silly. Ordering automatically installed packages last also allows us to calculate autoremovable packages. Since we will have installed all dependencies from manually installed packages by the point where we get to automatically installed packages, everything that will be installed in those Auto groups is inherently garbage.
* solver3: Do not dump sizes that are clearly pointersJulian Andres Klode2024-06-131-1/+1
| | | | | | | | | We use a union here, but we don't know if we last stored a pointer, so let's just reject clearly non-sizes. Generally this will work fine -- you will not have enough choices in a dependency that you can construct a valid pointer to a Version*, especially given that any Version * > sizeof(pkgCache::Header) already, given it is in the cache.
* solver3: Fix translations of removals for marked installJulian Andres Klode2024-05-241-1/+1
| | | | | | | | | We also need to issue a MarkDelete() if the package is marked for installation currently but should not be, not only if it did not have a previous version. This fixes the final test in test-multiarch-barbarian, the others only needed adjustments to mark all packages as automatic.
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-07-20 03:11:33 +0000