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 2DA6A139694 for ; Tue, 30 May 2017 18:46:30 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 2C01D21C07B; Tue, 30 May 2017 18:46:22 +0000 (UTC) Received: from smtp.gentoo.org (smtp.gentoo.org [140.211.166.183]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id D9A7821C03C for ; Tue, 30 May 2017 18:46:21 +0000 (UTC) Received: from localhost (unknown [IPv6:2a01:e34:eeaa:6bd0:4ecc:6aff:fe03:1cfc]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) (Authenticated sender: aballier) by smtp.gentoo.org (Postfix) with ESMTPSA id 0EEEA34170E for ; Tue, 30 May 2017 18:46:19 +0000 (UTC) Date: Tue, 30 May 2017 20:46:14 +0200 From: Alexis Ballier To: gentoo-dev@lists.gentoo.org Subject: Re: [gentoo-dev] [RFC] Forced/automatic USE flag constraints (codename: ENFORCED_USE) Message-ID: <20170530204614.61e8e42c@gentoo.org> In-Reply-To: <1496167898.1335.1.camel@gentoo.org> References: <1496071993.31087.1.camel@gentoo.org> <20170529200037.2559f80a@gentoo.org> <1496093035.12795.3.camel@gentoo.org> <20170530094245.40e1cf64@gentoo.org> <20170530092245.681d4aeb@snowblower> <20170530104654.31b89e10@gentoo.org> <20170530095607.1adbc0b8@snowblower> <20170530112518.65b4f9e9@gentoo.org> <22829.24276.295.969060@a1i15.kph.uni-mainz.de> <1496154812.1238.5.camel@gentoo.org> <20170530173340.0b575526@gentoo.org> <1496167898.1335.1.camel@gentoo.org> Organization: Gentoo X-Mailer: Claws Mail 3.15.0-dirty (GTK+ 2.24.31; x86_64-pc-linux-gnu) 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-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Archives-Salt: 1c4fada3-c857-4fc4-9be3-ced9776926de X-Archives-Hash: 515285c16213e6cc88ca0056ca3a0df2 On Tue, 30 May 2017 20:11:38 +0200 Micha=C5=82 G=C3=B3rny wrote: [...] > > > Of course, we could just validate all the possible cases via > > > repoman, and reject the ebuild if there's at least one conflict > > > between them. Not sure how to express that properly in the spec > > > though. Not sure how it would work practically. =20 > >=20 > > Adding a 2^n check to repoman isn't gonna work well. > > =20 >=20 > I'm not saying it's the most optimal algorithm of verifying > the correctness of the constraints. It's just the one that's quite > obvious -- relatively simple and reliable. If someone can come up with > something better that covers at least the most common cases, I'm all > for it. >=20 > That said, this wouldn't be that much of a problem if we can keep the > n low. For a start, we can rule out all flags that don't appear > in REQUIRED_USE at all. Furthermore, I think we could also ignore > the constraints for flags that don't appear there at least 'twice', > and so on. :) You're applying classical techniques to lower the size of a SAT instance so that your exponential algorithm does not explode, but it's still hard. I'm not sure what you want: If you want to detect that there is an impossible constraint, well, ebuild writer will notice soon enough when testing it. If you want to detect that there is a way to have a conflict between useflags, then there will be valid cases where this will happen. That said, assuming we have REQUIRED_USE in CNF form, its negation is in DNF form. Solving SAT on DNF formulas is easy (linear I think), and this would give you an assignment of useflags triggering an impossible constraint. e.g. 'foo? ( bar )' with USE=3D'foo -bar' in make.conf. This could be used to trigger a repoman warning but basically every single ebuild would trigger those.