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

[Michael Lienhardt]

Dear Michał,

I understand your concerns, and for some time I shared them too.
Portage is a very complex piece of software that evolved for almost 20 years to perform a very difficult task quite quickly with good results, so it is bound to contain many ad-hoc fixes and tweaks that can hardly be encoded into SAT constraints.
However, I think there are two arguments strongly in favor of my approach.
1. it seems to me that there is a real effort from the gentoo community and management to have a precise description of how Portage should behave, with the PMS and all the documentation on the wiki and devmanual. My work is based on this documentation and goes in the same direction by giving a simple and unambiguous description (i.e., a formal semantics) of Portage's dependencies as described in 
Section 8.2 of the PMS.
2. My work currently *only* focuses on the package dependencies. I don't deal with eclasses (I use egencache files), I don't deal with installation order (I just compute which packages must be installed in the end: in doing so, I avoid the circular dependency problem you were talking about), I don't deal with actual package compilation, installation, etc. I focus on a very precise part of Portage, 
dependency solving, subject on which I have some expertise.

So I agree with you that it is unlikely that my prototype's outputs will correspond one to one to emerge's.
However, I think it can be positive for Portage.
As my prototype uses an off-the-shelf solver as backend, in principle it just consists of a translation of Section 8.2 of the PMS into SAT constraints: consequently, it is a rather small piece of code compared to Portage, and once I finish reading the PMS and clean up my implementation, it would likely be a correct implementation of the PMS, or at least simple enough to be easily checked and 
corrected.
Then, testing my prototype to check for bugs is also a good opportunity to check for bugs into Portage itself, by taking the PMS as reference. And if you are right and my prototype --a direct translation of the PMS-- ends up worse than Portage, then maybe this means that the PMS should be revised.
Also, in the long run, having an alternative implementation of one of Portage's functionality instead of a complete alternative to Portage like paludis or pkgcore, could help in the discussion about a modular implementation of Portage (I've heard some people talking about it), or about a next version of the PMS.

I'll finish my prototype as soon as possible and see what the tests will tell.

Best regards,
Michael Lienhardt


Il 10/02/2018 09:20, Michał Górny ha scritto:
> W dniu wto, 06.02.2018 o godzinie 11∶52 +0100, użytkownik Michael
> Lienhardt napisał:
>> Dear all,
>>
>> With the help of some friends and colleagues, I am working on an SAT-based dependency solver for portage.
>> We need your help to test it and possibly improve in the long run the already great portage toolset.
>>
>> To help, you can send us the tar generated by this bash script: https://raw.githubusercontent.com/HyVar/gentoo_to_mspl/master/benchmarks/get_installation.sh
>> This bash script extracts your world file, the USE flags and keywords configuration of your system and the list of installed packages you have (it should not take more than few seconds).
>> With this, we will see if our solver is able to recreate your system and how much time it takes.
>>
>
> To be honest, I don't think this is the right approach to the problem.
> Truth is, dependencies in Gentoo are seriously broken, and most of
> the developers aren't even aware of that because of layers upon layers
> of hacks in Portage that make emerge somewhat go on.
>
> If you are really able to build something on top of the input you
> receive, it's probably going to be even worse than what's already
> in Portage.
>
> Example: many packages have impossible circular dependencies. However,
> Portage conditionally pretends they don't exist, preferring some random
> install-time breakage over fixing the packages in question.
>