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

David Kalnischkies <[email protected]> Tue, 2 Sep 2025 11:12:06 +0200

Newsgroups	gmane.linux.debian.apt.devel
Message-ID	<gretw2a2m27bwqx5rmetwxr2jqspmbuhht6vjjmewuenonibfd__33480.7333465264$1756805008$gmane$org@ce3qfmkprqaw>

Am Mon, Sep 01, 2025 at 07:47:46PM -0500, schrieb Aaron Rainbolt:
> * 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.

This isn't new, its a problem somewhat inherent to the way the classic
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

signature.asc (application/pgp-signature, 833 B)