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

[Michael Lienhardt]

Thanks a lot for this list!

You are totally right, simply translating the dependencies into SAT constraints 
and feeding them to a solver returns in most cases a very bad, totally useless 
solution.
However, nowadays many solvers support solution optimization, i.e., you can 
specify an ordered list of criteria you want to maximize/minimize, exactly like 
you did.
I already implemented the minimal status difference and the minimal 
installation size criteria, and the solutions I get are already acceptable/good.

I wasn't aware of the criteria list you gave (maybe it's in the PMS), so thank 
you very much, this is a big help :)
I have few questions about these criteria:
 - in criteria a., there could be an ambiguity between what I call a package 
(e.g., 'app-editors/nano-2.9.3') and a package group (e.g., 
'app-editors/nano'): is the criteria about package group (i.e., are version 
changes allowed)?
 - similarly in criteria b.: is this criteria valid across versions (i.e., when 
changing version, the USE-flag change should be minimal), across slots (i.e., 
two installed versions of the same package group should have a minimal USE flag 
difference)?
   If yes, what if package.use specifies very different USE flags for two 
versions of the same package group?
 - does the "prefer new version" criteria go between a. and b.?


b. Similarly, the number of USE-flag changes necessary to achieve this
aim should be minimized.
(You didn't tell whether your solver already supports such changes,
but when it is finished, it definitely should.)


Yes, my solver supports USE-flag, keyword and mask changes (it is currently 
oblivious of licenses, but supporting them should just be a technical/time 
consuming effort).
Due to keywords and mask changes, the "prefer new version" criteria needs to be after 
criteria "less keyword and mask change".
 - just to be sure, the "less keyword and mask change" criteria is at the top 
of the list?

Best regards,
Michael Lienhardt

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

[Michał Górny]

W dniu wto, 13.02.2018 o godzinie 07∶49 +, użytkownik Martin Vaeth
napisał:
> Michael Lienhardt  wrote:
> > 
> > ad-hoc fixes and tweaks that can hardly be encoded into SAT constraints.
> 
> The main difficulty which I see is that one does not want only _some_
> solution, but among all solutions one which optimizes certain quantities.
> So it seems to me that a discrete optimization under constraints
> is required instead of a pure SAT solver (although formally, of course,
> such an optimization problem can be reduced to SAT, I do not know whether
> you went the road):
> 
> a. The number of packages which change their status (from installed to
> uninstalled or vice versa) should be minimal.
> 
> b. Similarly, the number of USE-flag changes necessary to achieve this
> aim should be minimized.
> (You didn't tell whether your solver already supports such changes,
> but when it is finished, it definitely should.)
> 
> Hopefully in near future, there will be a second class of USE-flags
> whose change is "cheap" which should be excluded from this minimization
> restriction:
> https://bugs.gentoo.org/show_bug.cgi?id=424283
> I think the main reason why nobody dared to implement them yet
> (although almost everybody wants them) are exactly these implications
> on the current solver in portage which nobody dares to change anymore
> seriously.
> 
> c. A solution with dependency loops should be avoided if possible
> (which is why currently the PDEPEND hacks do exist: To tell the solver
> which loops are not a problem.)
> 
> d. In || ( ... ) clauses the left-most packages should be preserved.
> There are similar (and more difficult) rules for REQUIRED_USE.
> 
> e. Last but not least: The preferences are ordered a > b > c > d
> (A dependency loop of uninstalled packages should probably have even
> higher priority than a).
> Additionally the change installed -> uninstalled should be less
> "expensive" than the change uninstalled -> installed.
> The correct weighting of the quantities should probably be a matter
> of discussion (or preferrably even user-customizable), and preferrably
> should not depend only on the number of packages but also on other
> customizable quantities (e.g. the package size).
> 

Thank you for listing this. However, I think you've missed the most
important point: we want to prefer the newest version, whenever possible
;-).

-- 
Best regards,
Michał Górny

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

[Michael Lienhardt]

Il 07/02/2018 05:11, Duncan ha scritto:

AFAIK, (plain) etc-portage semantics are the same for both files -- that
is, /etc/portage/package.keywords and the newer package.accept_keywords
are identical.

The reason for the new name and deprecation of the old one was that
package.keywords also exists in the /profile/, where the semantics are
different, which created confusion for devs and others attempting to edit
the profile version as well as the more commonly user-edited (plain)
/etc/portage version.

(I add the parenthesized "(plain)" because there's also the deeper
/etc/portage/profile path, which takes profile changes and therefore the
profile format.  Actually, I suspect it was someone editing that using
the wrong format and then filing a bug when things didn't work as
expected that likely prompted the new name and deprecation of the old
one.)


Ok, thank you for the information, it's very interesting.
I may need to update my solver then :) (I thought that *.keywords always 
manipulated the KEYWORDS variable, while *.accept_keywords manipulated the 
ACCEPT_KEYWORDS).


I've a rather unusual portage config here:

* /etc/portage/profile/packages contains a -* entry, negating the entire
normal @system set.  Many normally @system packages I really need are
dependencies of something or other I already have in @world anyway, and
I've added @world entries where necessary to keep the few exceptions
installed.

* My USE starts with a -* entry as well, negating profile and package USE
defaults so I have direct control of all USE flag settings and don't have
to worry about USE flag changes on profile updates or tracking down why a
flag is changing when I didn't change anything, both previous problems I
had to deal with until I set that initial -*, so the only flags set are
the ones I deliberately chose, myself.


Does the -* also remove profile USE defaults for USE flags in 
PROFILE_ONLY_VARIABLES?
My understanding is that only files in a profile (either 
/etc/portage/make.profile or /etc/portage/profile) can configure these USE 
flags.


* My world file (/var/lib/portage/world) is empty.  I've categorized
everything into individual sets found in /etc/portage/sets, with those in
turn listed in the world_sets file (/var/lib/portage/world_sets).


Interesting, I didn't know about the /var/lib/portage/world_sets file (it 
escaped me somehow).
I currently include in all the packages listed in the /etc/portage/sets/* files.
It can be fixed easily.


* Overlays... (Less unusual, but still not mainline...) I run nearly all
the kde I have installed (frameworks/plasma/apps), as well as a few other
packages, from the live-git *- packages found in the gentoo/kde
overlay (and others).  Package keywording/masking is adjusted
accordingly.  (Everything else is mainline ~amd64.)

I expect  one or more of these you won't have anticipated so they'll
present a challenge for your current script, but because it /is/ a rather
unusual setup, I'm not sure it's worth your trouble to bother with.


Out of all your points, only the overlays are not managed by our solver.
As your setup is unusual, apar from the overlay, it could be a good test case 
for our tool to check the configuration loading.
Right now in my tests, I deal with overlay by adding manually all the installed 
packages that is missing from the base portage tree...
If there is not too much packages to add (I guess 50 is still ok, 100 is a bit 
too much).


OTOH, if you want unusual corner-cases to test...


I'm from formal methods, focused on correction and completeness...
So yes, corner cases are important and interesting, and are useful to detect 
early bug or design errors.


So bother sending the results in (you're ready for it already), or you
want them, but wait until you've adjusted the script to deal with it, or
don't bother, you're not going to try supporting anything that unusual
anyway?


Send it in :).
If I have problems with it, I may not fix the bugs right away, but at least I 
would know about it.

Thanks,
Michael Lienhardt