From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by finch.gentoo.org (Postfix) with ESMTPS id 7C9C01382C5 for ; Tue, 13 Feb 2018 08:42:47 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id B5F7CE0C24; Tue, 13 Feb 2018 08:42:40 +0000 (UTC) Received: from smtp.gentoo.org (dev.gentoo.org [IPv6:2001:470:ea4a:1:5054:ff:fec7:86e4]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id 6B223E0BEE for ; Tue, 13 Feb 2018 08:42:40 +0000 (UTC) Received: from pomiot (d202-252.icpnet.pl [109.173.202.252]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) (Authenticated sender: mgorny) by smtp.gentoo.org (Postfix) with ESMTPSA id 38362335C38; Tue, 13 Feb 2018 08:42:38 +0000 (UTC) Message-ID: <1518511354.1385.1.camel@gentoo.org> Subject: Re: [gentoo-dev] Re: SAT-based dependency solver: request for test cases From: =?UTF-8?Q?Micha=C5=82_G=C3=B3rny?= To: gentoo-dev@lists.gentoo.org Date: Tue, 13 Feb 2018 09:42:34 +0100 In-Reply-To: References: <1518250836.1474.3.camel@gentoo.org> <7ff216a3-a389-aa07-c17f-28dfce3c7f81@laposte.net> Organization: Gentoo Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.24.6 Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-dev@lists.gentoo.org Reply-to: gentoo-dev@lists.gentoo.org Mime-Version: 1.0 Content-Transfer-Encoding: 8bit X-Archives-Salt: c0769635-14e0-4836-861d-0489f429c397 X-Archives-Hash: 6212fd34839b33e68c35048b4fd28568 W dniu wto, 13.02.2018 o godzinie 07∶49 +0000, 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