When installing a package A, which depends on a virtual package V, apt
uses the first package, which provides "V".

Imagine that "V" gets provided by M and N, where M depends on M1 and N
on N1. N1 is already installed, but M1 isn't.

Now, installing A will also install M and M1, while it would be better
to install N only.

At least that was what I was expecting and this seems to be the reason
for a bug in Ubuntu, where installing virtualbox-ose on a system with
"generic" kernel pulls in the 386 kernel.
See https://launchpad.net/bugs/188579 for more details.

I've looked at the source and started hacking around (without much C++
knowledge at hand).

What I came up with, was the following:
In pkgDepCache::MarkInstall, instead of using the first candidate (in
case of provides), run MarkInstall on all of them (recursively) and use
the version where iInstCount changes the least.
The missing part in my patch is to really revert the pkgCache; I have no
idea how to do this properly and since this whole approach might be
wrong, I'd like to only propose this.

Please consider adding this feature/functionality/idea.


btw: do you have any suggestion about fixing the particular
virtualbox-ose issue mentioned above?
Apart from moving the modules into the general "kernel modules" package, I
only see the fallback of making the "Depends" and "Recommends" again.


I hope that the feature suggestion makes any sense and that you can help
me to work around/fix it for apt currents behavior.

Thank you.

Trying this with the python module for apt, using markDelete has not removed every package again.
Bug#473247: When trying to satisfy a dependency on a virtual package, prefer the providing package with the higher priority
(http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=473247)

and let apt handle kernel modules in a special way, i.e. installing the module for the current kernel.

Your way should also be added, but disabled by default and given an option like Apt::ResolutionStrategy 0 for the current behavior, 1 for my
suggestion (and set 1 as default) and 2 for your suggestion.

And if one uses 2, we should still compare first with my mode, than your mode, and then classical mode.

1. Install with higher priority
2. Install package with less dependencies (if priorities are equal)
3. Install first package (if number of dependencies is equal)

This should give use the fastest mode. and remember, the package with the higher priority is much more likely to pull in less dependencies than the
other package. My mode is also used in debimg's (http://wiki.debian.org/DebImg | http://jak-linux.org/projects/debimg/)  dependency resolver.

Has there been made any progress on this issue?

Looking at the code of version 0.8.16~exp5ubuntu6 it appears to be still
the same in pkgDepCache::MarkInstall.