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 809CE139694 for ; Fri, 2 Jun 2017 13:55:31 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 1C00D21C087; Fri, 2 Jun 2017 13:55:23 +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 B3F5021C06C for ; Fri, 2 Jun 2017 13:55:22 +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 15680341745; Fri, 2 Jun 2017 13:55:20 +0000 (UTC) Message-ID: <1496411717.29233.5.camel@gentoo.org> Subject: Re: [gentoo-dev] [RFC] Forced/automatic USE flag constraints (codename: ENFORCED_USE) From: =?UTF-8?Q?Micha=C5=82_G=C3=B3rny?= To: gentoo-dev@lists.gentoo.org Date: Fri, 02 Jun 2017 15:55:17 +0200 In-Reply-To: <20170602132758.50a5f734@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> <20170530204614.61e8e42c@gentoo.org> <1496213717.1164.1.camel@gentoo.org> <20170531093257.23b66f88@gentoo.org> <1496217792.1164.5.camel@gentoo.org> <20170531103819.417c2420@gentoo.org> <1496235892.25038.1.camel@gentoo.org> <20170531193922.477245bb@gentoo.org> <1496257344.25758.1.camel@gentoo.org> <20170601105523.08a9234e@gentoo.org> <1496352685.30502.4.camel@gentoo.org> <20170602132758.50a5f734@gentoo.org> Organization: Gentoo Content-Type: multipart/signed; micalg="pgp-sha512"; protocol="application/pgp-signature"; boundary="=-SJCX4EZj/aNjT6Jev9Z3" X-Mailer: Evolution 3.22.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 X-Archives-Salt: f4f5f493-0bf7-4413-867b-c3717d788f1e X-Archives-Hash: fc0dbfbb83ccb941095de641cb1496b1 --=-SJCX4EZj/aNjT6Jev9Z3 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On pi=C4=85, 2017-06-02 at 13:27 +0200, Alexis Ballier wrote: > On Thu, 01 Jun 2017 23:31:25 +0200 > Micha=C5=82 G=C3=B3rny wrote: > [...] > > > There are probably dozens of ways to make that non deterministic. > > > Here's one: USE=3D'-*'. Apply '|| ( cli cgi fpm apache2 embed phpdbg > > > )' last; this enables 'cli'. Since it's the last one, REQUIRED_USE > > > is not satisfied because of 'cli? ( ^^ ( readline libedit ) )'. > > > If you process it first, then you enable cli and readline and are > > > good. =20 > >=20 > > You just take a second iteration, and things fall into place. That's > > not a problem. > >=20 > > > > > Also, what happens if we applied all the constraints and > > > > > obtained some useflags setting that still fails REQUIRED_USE > > > > > check ? =20 > > > >=20 > > > > It can't happen. If you can apply all the constraints, then > > > > implicitly REQUIRED_USE is satisfied. If you can't apply all the > > > > constraints, then it just fails. Of course, we want to ultimately > > > > avoid that case. =20 > > >=20 > > > See the php example above. How do you ensure this does not happen? > > >=20 > > > Note that your assertion 'If you can apply all the constraints, then > > > implicitly REQUIRED_USE is satisfied.' is false: You're changing the > > > values of useflags, thus might violate some previously checked > > > constraint. =20 > >=20 > > So you reiterate. Either you reach a solution (preferably there's only > > a single valid solution you can reach) or you hit a previous state > > which indicates a loop and you fail. >=20 >=20 > So, PM, for every ebuild, will need to store the (at most) 2^n states it > has already seen while trying to solve REQUIRED_USE and iterate until > it cannot proceed anymore or falls into a previous state (so that's 2^n > time too). That way we go from a linear time & linear space algorithm > to one in exponential time & space. That's probably not a good idea. I don't think that's actually going to happen. You'd have to try really hard to get over n-1 iterations. I mean, the only simple way I can think of is: b? ( a ) c? ( b ) d? ( c ) e? ( d ) ... and this only means n-1 iterations. Can you think of a better way to force multiple iterations that can be written without making REQUIRED_USE completely unreadable? How likely is that going to happen accidentally? > I think it's better to limit the number of iterations to some constant. > I'd say 1, then fail if REQUIRED_USE is still not satisfied. Maybe 2 or > 3 can be useful but I think it'd be much harder to provide automated > checks for that and much harder for ebuild writers to understand what > will happen with the REQUIRED_USE they're about to write. >=20 Well, I don't mind setting that. All my tests (that weren't deliberately abusing the algorithm) were able to finish in a single iteration. 2 or 3 should probably be safe for all the reasonable uses. However, if we're not going to verify all possible values on repoman side, I think it would be better to have a larger limit for users, to not have things explode on them unnecessarily. --=20 Best regards, Micha=C5=82 G=C3=B3rny --=-SJCX4EZj/aNjT6Jev9Z3 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNATURE----- iQKmBAABCgCQFiEEbbsHzE8NrQbqCv5BsHoa6u+0Rk4FAlkxbkVfFIAAAAAALgAo aXNzdWVyLWZwckBub3RhdGlvbnMub3BlbnBncC5maWZ0aGhvcnNlbWFuLm5ldDZE QkIwN0NDNEYwREFEMDZFQTBBRkU0MUIwN0ExQUVBRUZCNDQ2NEUSHG1nb3JueUBn ZW50b28ub3JnAAoJELB6GurvtEZOAIUP/R8prhbS3AH+Fdn8zePdsP2H+bGRA7bN eCImGCxd2gYlGJNIxFaHzttQot+3JWSq35pxvBpL77h5wrFfkjjWWmoYT+lg0Uhw XJedjs5MxSf7Y/Jk8wWtx8Gs2bAOwd3LzYjYwsQH4RcW1163BNRmgmMhcJC1IY9e 7tEY9l9tmKZH+IngcCiJ7oSt153eLyQrGtWpnGhlVxFI/nNgpSPUnvUc3tX3dHki OAVUp24SkUDeBadHSaAVEeTK2o9gwJrIe/ptawGNPmAQQqzG7Q/KpTbppwQAXlnR Ff47K0YZNoAwurXz6HGfnzuvT34evUySUhGI9jdlwqXrnRovyVvuhTxNCtHJokUK EB01EF0kQCYJCpbJv/SaTaWaLwtyQeZRPKkHCKq0Gt4amtTW9eJakR3k5gzQdPr9 4oezlC+CMymoGYQVhmyhDcC4sZ/51PX/lQ7wF+CJYUFB3dzj9RsDyBONLLNJfceh egsnvT4X+12mRaxq7H0mYXjitjfC0eOvXCM1h/A/tpX1f1+acAxIHCWdya1ll4WQ 6ZoFZ1IXOIQ/UfQ1sC+A6hGiKbR3VTHTAK2H2YylWCATVyuMZczO9o4/FhCR8vI1 hwy0OeYZ28UjiO0rntNAYEwTx98W4R1zOwQMRIx1Oy7c36QdfsfXqZAAh3S1yVsf CE8ctt4USgKL =ORR4 -----END PGP SIGNATURE----- --=-SJCX4EZj/aNjT6Jev9Z3--