Debians commandline package manager https://git.kalnischkies.de/apt/atom?h=2.9.8 2024-08-12T14:05:54Z 2024-08-12T14:05:54Z Julian Andres Klode julian.klode@canonical.com 2024-08-12T13:27:31Z urn:sha1:5d2c0e600656db690aaeb0768f3df8e71127808a 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. 2024-07-16T11:55:07Z Julian Andres Klode julian.klode@canonical.com 2024-07-16T11:54:11Z urn:sha1:62573e3ca6b45b0d12b9be8b02da116ce0d91b75 More code but nicer to read 2024-07-02T18:08:38Z Julian Andres Klode julian.klode@canonical.com 2024-07-02T16:51:11Z urn:sha1:8c13d9cb1c38ebb52cf6e1c8c7561c5c5d87c970 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. 2024-06-13T13:10:06Z Julian Andres Klode julian.klode@canonical.com 2024-06-06T09:19:04Z urn:sha1:6708203296911800caf94bb94ce204d3a39af0bd 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. 2024-06-13T13:10:06Z Julian Andres Klode julian.klode@canonical.com 2024-05-25T07:45:39Z urn:sha1:102017ecaa01a733a0860a62edae60cb0ab0220e 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. 2024-05-14T09:56:18Z Julian Andres Klode julian.klode@canonical.com 2024-05-06T13:34:33Z urn:sha1:89dcc342e17dd2439d97a5d27200cf5c26ba35bc This is a simple backtracking brute-force solver with heurisitcs, this initial version has the following known gaps: - Errors are not kept from branches, the error reporting after backtracking isn't particularly useful. - We cannot show automatically removed packages - We cannot replace packages with others - We do not have conflict-driven clause learning yet Untested: - Multi-arch This solver is fundamentally different in key aspects: - It solves smaller dependency groups before larger ones, leading us to avoid installing A in A|B if B is installed more often and more consistently. - It only keeps the automatic packages reachable via the strongest path. Currently it only implements autoremoval, but not display of autoremoval as we simply enqueue all automatically installed packages at the end when not doing automatic removal. This will need some translation where we Solve() first, and then Solve() again with the automatically installed packages added such that we can mark them as Garbage for display purposes. - It does not remove manually installed packages. Hook the solver in via the EDSP framework, this allows us to achieve easy initial integration without lots of issues. A lot of this work was planned and executed in my free time and then some leaked into work time I suppose. Implementation notes: - Restore the full backlog of items The annoying thing is that we record only when an item was enqueued and not the level at which it was installed, so when going back a decision level we might have to reinstall packages that were queued at an earlier decision level because they were only installed at a later decision level. - When picking one version, reject the others - Propagate conflicts up to reverse dependencies This will recursively mark every reverse dependency that can no longer be satisfied as MUSTNOT. Also make sure to recursively call Reject(Ver) from Reject(Pkg) to make sure we trigger the Rejections there. This means we now end up having Recursion in the algorithm. An alternative approach would be to push *reject* items to the heap and then do them, but this is not entirely straight forward and it may simply not be necessary. - Sort upgrades before other optional installs containing subsets If I want to upgrade a package A, I schedule A3|A2|A1; if another thing depends specifically on A1; we'd not be installed. Hence we need to sort upgrades first. This only is needed for optional packages; manual packages will figure this out naturally. - Rescoring is lazily implemented. Instead of calling make_heap() after rescoring items, we just mark the items as dirty and reinsert them. We also only rescore from the main solve loop, Reject() marks the heap as needing a rescore due to a Conflict (as some versions will no longer be installable), and RescoreWorkIfNeeded() then will do the rescoring. - Recursive unit propagation: Install() and Reject() recursively call each other to promote decisions across single-version dependencies (or across not-anymore satisfiable reverse-depends). - Make Reason constructors explicit, this enhances readability This makes calls like the one in here be Reject(object, Reason(otherObject)) Ensuring that it's clear that the 2nd argument is a reason at the caller side. - Split Decision into Decision and Hint vs. first draft When branching/deciding, we do not want to override SHOULD and MAY. We do not actually use them yet, and we do actually clean them when backtracking, but let's at least keep the data structure correct. Convert the enum to a 16-bit integer so we can still fit in the same space as before.