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.

Am Mon, Sep 01, 2025 at 07:47:46PM -0500, schrieb Aaron Rainbolt:
solver works. Over the years mostly me did some things to paper over
this for the easy cases, but "solving" it is a matter of rewriting the
solver ~ something Julian did with different trade offs.

We call the classic one greedy, as it goes from dependency to dependency
and decides to install it directly, no second chances (usually) and no
waiting.

So, apt simply sees your mate-polkit dependency too late. You can
literally solve this (to some extend) by ordering your dependencies
differently: The more specific ones first (or the ones that lead to more
specific ones first).


You can solve that to some extend in apt, and we tried for some cases,
but a "real" solution would be making all the unavoidable decisions
in the entire tree first and the ones including choices later. Rinse and
repeat until all choices are made.

In theory that is easy, in practice choices are everywhere: E.g. on
a multi-arch enabled system every M-A:foreign package is a choice even
if in all likelihood only the native one will be the chosen one.

You end up somewhere around aptitudes solver I guess if you go too deep
in this direction.


There is a reason most other package management ecosystems have no
concept of or-groups and many avoid provides as well. They make
everything complicated that looks like a simple SAT thing at first.


So, yeah, as said, reorder your dependencies and see if that helps.
Or reorder the way you install the metapackages (I hope you realized
now that 'apt install A B' and 'apt install B A' can produce different
results).


Best regards

David Kalnischkies

It would be interesting to see what --solver 3.0 does here as it is
_less_ greedy. Basically it goes:

1. Resolve all dependencies with one solution with solution
2. Pick some(*) dependency and the leftmost allowed choice
3. If conflicts, undo
4. Go back to 1


(*) This is _mostly_ in traversal order right now, but there's
some priorities: For example, dependencies involving an obsolete
packages are solved after dependencies not doing so, and dependencies
involving new packages are solved before other dependencies.

The eventual goal if you have say:

X depends policykit-1-gnome | polkit-1-auth-agent
Y depends mate-polkit       | policykit-1-gnome

Is to compare across rows for the active column:


1. We try policykit-1-gnome vs mate-polkit (leftmost choices):

    X depends policykit-1-gnome | polkit-1-auth-agent
                    |
                    vs
                    |
    Y depends mate-polkit       | policykit-1-gnome

   select say policykit-1-gnome

2. That failed, now we are left with

    X depends polkit-1-auth-agent
                |
                vs
                |
    Y depends mate-polkit       | policykit-1-gnome

    We need to pick mate-polkit because it's a stronger
    dependency (since the other is a virtual package).

Things are a bit tricky here since we don't yet keep track
of whether we are looking at a virtual package or not, so
if we did that right now we'd battle the strongest provider against
the explicit preference.

On Tue, 2 Sep 2025 12:37:52 +0200 Julian Andres Klode <jak@debian.org> wrote:

Aren't I already using the 3.0 solver? The issue is mostly in Trixie and
Sid which I *thought* used a different solver than Bookworm (especially
since it shows the less desirable behavior). I'll pass `--solver 3.0`
and see what happens. I'll also try David's suggestion of passing the
packages in a different order (both on the metapackage level and with
the order of installing metapackages), although I fear that getting the
order right may be impossible in some non-trivial situations.

On Tue, 2 Sep 2025 09:14:14 -0500 Aaron Rainbolt <arraybolt3@gmail.com> wrote:

*snip*

So, I did a test with `--solver 3.0`, and it *did* change things for
the better - now only mate-polkit is chosen, not ukui-polkit. A whole
lot of other things are also not installed, using `--solver 3.0` didn't
add any additional packages, it only removed packages (and it removed A
LOT of packages - the test shared in the original report resulted in
apt trying to install 315 packages, but when using `--solver 3.0` apt
only tries to install 178 packages).

The full results are more than a bit long, but here's some pastebins:

`apt -s install --no-install-recommends nm-connection-editor
mate-settings-daemon`: https://termbin.com/qzr9

`apt -s install --no-install-recommends --solver 3.0
nm-connection-editor mate-settings-daemon`: https://termbin.com/y6qc

Diff of the output from the above two commands with table-formatted data
removed and the remaining data sorted alphabetically:
https://termbin.com/ke2ud