Gentoo Archives: gentoo-dev

From: Michael Lienhardt <michael.lienhardt@×××××××.net>
To: gentoo-dev@l.g.o
Subject: Re: [gentoo-dev] Re: SAT-based dependency solver: request for test cases
Date: Tue, 13 Feb 2018 11:53:32
Message-Id: 5ae09299-b20d-f40e-842e-7bc13f85e39c@laposte.net
In Reply to: Re: [gentoo-dev] Re: SAT-based dependency solver: request for test cases by "Michał Górny"
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

Replies

Subject Author
[gentoo-dev] Re: SAT-based dependency solver: request for test cases Martin Vaeth <martin@×××××.de>