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

Julian Andres Klode <[email protected]> Tue, 2 Sep 2025 12:37:52 +0200
Newsgroups	gmane.linux.debian.apt.devel
Message-ID	<20250902122352.GA164503__46941.3164815464$1756809565$gmane$org@debian.org>
On Tue, Sep 02, 2025 at 11:12:06AM +0200, David Kalnischkies wrote:
> 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.

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.


-- 
debian developer - deb.li/jak | jak-linux.org - free software dev
ubuntu core developer                              i speak de, en
signature.asc (application/pgp-signature, 833 B)