Bug#1113744: Solver is making weird decisions when picking one of multiple supported dependencies

Aaron Rainbolt <[email protected]> Mon, 1 Sep 2025 19:47:46 -0500
Newsgroups	gmane.linux.debian.apt.devel
Message-ID	<20250901194746.37a4f0c7__26940.5037908413$1756774169$gmane$org@kf-m2g5>
Package: apt
Version: 3.0.3
Severity: important
X-Debbugs-Cc: [email protected]

I'm not sure if I have the bug severity right, this seems to have been a
problem in at least Bookworm and has gotten worse in Trixie and later,
but for what it's worth:

When presented with a multiple-choice dependency, such as
'policykit-1-gnome | polkit-1-auth-agent', I'd expect apt to pick the
first listed dependency *if* it can be installed without breaking
anything else and *if* no other package that fulfills the
multiple-choice dependency is installed or going to be installed. What
oftentimes happens instead though is that apt will pick one of the other
dependencies (or some package that provides one of the other
dependencies), disregarding other things that are being simultaneously
installed.

Real world instances of this being a problem:

* In a particular virtual machine I'm building with some
  out-of-Debian metapackages, I have a dependency on
  'network-manager-gnome'. In another metapackage, I have a dependency
  on 'mate-polkit'. Both of these metapackages and all their
  dependencies (but none of their recommends or suggests) are installed
  at the same time. 'network-manager-gnome' depends on
  'nm-connection-editor' which depends on 'policykit-1-gnome |
  polkit-1-auth-agent'. What I *expect* to have happen is that apt
  should notice I have a hard depends on 'mate-polkit' in one of the
  metas, which satisfies that dependency, and therefore should not
  install any other polkit agent. What happens instead is apt decides to
  install 'ukui-polkit' to satisfy the dependency. There aren't any UKUI
  components being intentionally installed on this machine.

* Another situation I've noticed this happen in is another Trixie-based
  VM, which is supposed to contain no desktop environment and is almost
  purely CLI-based (which I know apt has no way of knowing, but it's
  semi-relevant in a bit). I'm installing 'gpg-agent' in this VM.
  'gpg-agent' has a dependency on 'pinentry-curses | pinentry'. No other
  'pinentry' provider is intentionally being installed, so I'd expect
  'pinentry-curses' to be chosen. As it turns out, 'pinentry-curses'
  does get installed... and so does 'pinentry-gnome3'. `aptitude why`
  has no idea why 'pinentry-gnome3' is there (the best it can tell me is
  that gpg-agent suggests it, which should mean nothing since I'm not
  installing suggested packages), the best I can figure is something
  else had this same or similar dependency and apt picked
  'pinentry-gnome3' one time and 'pinentry-curses' another time.

* The last situation is during a build of a Lubuntu 25.10 ISO. The ISO
  build installs a package that depends on 'qterminal', and 'xorg', at
  (I believe) the same time. 'xorg' has a dependency on 'xterm |
  x-terminal-emulator'. What should happen is apt should see that
  'qterminal' provides 'x-terminal-emulator' and thus only install
  qterminal. What actually happens is apt satisfies xorg's dependency
  with 'alacritty' (which is especially weird since it seems like even
  if it was going to install another terminal, which it shouldn't, that
  other terminal would most logically be 'xterm'). Thus the ISO ends up
  with both 'qterminal' and 'alacritty' installed. (I realize this is
  talking about Ubuntu's apt, but I'm guessing the same root cause is at
  play here.)

How to reproduce:

* On a Debian Trixie host, create a minimal Trixie chroot:
  `sudo mmdebstrap trixie testtrixie`
  * I assume any host will work here since I'm reproducing the issue in
    a chroot, but wanted to not leave details out.
* Chroot into it: `sudo chroot testtrixie`
* Update the apt database: `apt update`
* Simulate the installation of 'nm-connection-editor' and
  'mate-settings-daemon' at the same time without recommended packages,
  and pipe the output to a pager for inspection: `apt -s install
  --no-install-recommends nm-connection-editor mate-settings-daemon |
  less`
  * The reason for using this combination is because
    'nm-connection-editor' depends on 'policykit-1-gnome |
    polkit-1-auth-agent', while 'mate-settings-daemon' depends on
    'mate-polkit' specifically.
 * Search the output for `polkit`. Both `mate-polkit` and `ukui-polkit`
   will be in the list of dependencies that are about to be installed.

These reproduction steps work on Sid as well, only there you will see
'mate-polkit' and 'xfce-polkit' being installed at the same time.

This does *kind of* happen on bookworm, but not as bad. In bookworm,
'network-manager-gnome' depends on 'policykit-1-gnome |
polkit-1-auth-agent' and there is no 'nm-connection-editor', so I'll
replace 'nm-connection-editor' with it. If you try to install
'network-manager-gnome' and 'mate-settings-daemon' at the same time, apt
will only install 'mate-polkit' and won't additional install another
'polkit-1-auth-agent' provider. Thus it seems to handle one level of
indirection correctly. However, two levels of indirection throws it off
- if I install 'openbox-lxde-session' and 'mate-settings-daemon' at the
same time, both 'lxpolkit' and 'mate-polkit' will be installed,
presumably because 'openbox-lxde-session' depends on 'lxsession' which
depends on 'lxpolkit | polkit-1-auth-agent'. The package that depends on
'[whatever] | polkit-1-auth-agent' isn't being directly installed, but
is a dependency of another package being directly installed, which is
what I mean by "two layers of indirection".

I'm not sure this is enough of a report to diagnose the issue, but I'm
hoping this at least will help with finding what info is needed to
diagnose things. Unless this is expected behavior, please tell me what
debugging info I can provide.

I've set the priority to 'important' since this issue is making it very
hard to build Debian Trixie VMs tailored to a specific purpose without
seemingly-arbitrary junk getting integrated into the image. I'm not sure
if this is warranted or not though, since the issue isn't entirely a
regression from Bookworm even though the undesirable behavior seems to
be exacerbated in Trixie and higher.
signature.asc (application/pgp-signature, 833 B)