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

Aaron Rainbolt <[email protected]> Tue, 2 Sep 2025 09:14:14 -0500
Newsgroups	gmane.linux.debian.apt.devel
Message-ID	<20250902091414.3b8a3c78__15087.6219895267$1756822525$gmane$org@kf-m2g5>
On Tue, 2 Sep 2025 12:37:52 +0200
Julian Andres Klode <[email protected]> wrote:

> 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:

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.

> 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.
signature.asc (application/pgp-signature, 833 B)