[gentoo-dev] Re: SAT-based dependency solver: request for test cases

[Martin Vaeth]

Michał Górny <mgorny@g.o> wrote:
>>
>> d. In || ( ... ) clauses the left-most packages should be preserved.

s/preserved/preferred/

> you've missed the most important point: we want to prefer
> the newest version, whenever possible
> ;-).

Yes, you are right: I had thought only about packages, not about versions.
Of course, a version upgrade within the same slot should have a
negative penalty. I am already not sure how upgrades with slot
changes should be treated. And then there are subslots...
The list is probably still not exhaustive and - as already mentioned -
the penalties are certainly a topic of discussion (and even more of
trial and error: which works best in practice).

Anyway, I think that it would be a huge improvement over the current
(portage's) solver if one could formulate such a list explicitly in
some specified format, and then one abstract algorithm takes care to
find the best solution according to the specified penalties:
If I understand it correctly, all these rules are currently hard-coded
into the algorithm by using various hacks in backtracking steps,
finding of a solution is convoluted with determining the order, etc.
One would obtain a solver which not only is "provably" correct,
but also much easier to maintain and to tweak (e.g. if one realizes
that certain penalties were not cleverly chosen).

This would also provide the possibility for much richer user configuration.
An example which immediately come to mind is "weak-masking" of packages
or versions ("use it or upgrade only if no alternative is available").
Theoretically, one could then even endow the entries of package.mask
with a penalty number.