From 1fbb857b6b2cbddcea9e8b03aa0c766c72e91f34 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 29 Dec 2025 18:47:15 +0100 Subject: solver3: Use classical watchers for propagation 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 --- ...test-ubuntu-bug-2111792-intersecting-dependencies | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-) (limited to 'test/integration/test-ubuntu-bug-2111792-intersecting-dependencies') diff --git a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies index 7e770a30d..3f100cb1f 100755 --- a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies +++ b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies @@ -97,15 +97,21 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: git-ng : Depends: git (> 1:2.26.2) E: Unable to satisfy dependencies. Reached two conflicting assignments: - 1. git-ng:amd64=1:2.26.2-1 is selected for install - 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) + 1. git:i386=1:2.26.2-1 is selected for install because: + 1. git-ng:amd64=1:2.26.2-1 is selected for install + 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) + [selected git-ng:amd64] + For context, additional choices that could not be installed: + * In git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.): + - git:amd64=1:2.26.2-1 is not selected for install because: + 1. git:amd64=1:2.25.1-1 is selected for install + 2. git:amd64=1:2.26.2-1 conflicts with other versions of itself + 2. git:i386=1:2.26.2-1 -> | git:i386 but none of the choices are installable: - - git:amd64=1:2.26.2-1 is not selected for install because: - 1. git:amd64=1:2.25.1-1 is selected for install - 2. git:amd64=1:2.25.1-1 conflicts with other versions of itself - - git:i386=1:2.26.2-1 is not selected for install because: + - git:i386 is not selected for install because: 1. git:amd64=1:2.25.1-1 is selected for install as above - 2. git:amd64 Conflicts git:i386' apt install git-ng -s + 2. git:i386 Conflicts git + [selected git:amd64=1:2.25.1-1]' apt install git-ng -s msgmsg 'Now mix it up by' 'holding git-cvs' -- cgit v1.2.3-70-g09d2