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 792EE139694 for ; Mon, 5 Jun 2017 18:10:27 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 9E8BF21C0B9; Mon, 5 Jun 2017 18:10:18 +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 414FE21C087 for ; Mon, 5 Jun 2017 18:10:18 +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 AF31D341673; Mon, 5 Jun 2017 18:10:16 +0000 (UTC) Message-ID: <1496686212.1222.4.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: Mon, 05 Jun 2017 20:10:12 +0200 In-Reply-To: <20170605192433.6238797b@gentoo.org> References: <1496071993.31087.1.camel@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> <1496411717.29233.5.camel@gentoo.org> <20170603130000.4f88fb14@gentoo.org> <1496503989.15351.1.camel@gentoo.org> <20170603185835.57741ff0@gentoo.org> <20170604105938.2b40157f@gentoo.org> <20170605095516.0b463432@gentoo.org> <1496671825.1230.3.camel@gentoo.org> <20170605192433.6238797b@gentoo.org> Organization: Gentoo Content-Type: multipart/signed; micalg="pgp-sha512"; protocol="application/pgp-signature"; boundary="=-/8X6GyCTz6tczZLUcPrn" 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: b5409a0b-a956-46a7-a02d-536dbc36688e X-Archives-Hash: 8f1e1e3f11a497485ad036bd61664e47 --=-/8X6GyCTz6tczZLUcPrn Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On pon, 2017-06-05 at 19:24 +0200, Alexis Ballier wrote: > On Mon, 05 Jun 2017 16:10:25 +0200 > Micha=C5=82 G=C3=B3rny wrote: >=20 > > On pon, 2017-06-05 at 09:55 +0200, Alexis Ballier wrote: > > > On Sun, 4 Jun 2017 10:59:38 +0200 > > > Alexis Ballier wrote: > > > =20 > > > > Here's a quick n dirty code to play with, based on yours:=20 > > > > https://github.com/aballier/required-use =20 > > >=20 > > > I've run that on the whole tree (considering all ebuilds with non > > > empty REQUIRED_USE), some stats: > > >=20 > > > $ time python3 classify.py requsel=20 > > > Stats: > > > Parse error: 16 =20 > >=20 > > Hmm, how did you get those numbers? I just tested parsing and found > > only 7 unique REQUIRED_USE entries that fail. However, my sample file > > is only around 1000 entries long, so either I failed to get all of > > them, or you didn't deduplicate your list ;-). More on it below. >=20 > I did not deduplicate anything. I took every single ebuild and > generated a list of req use out of it. Meaning if you had 10 ebuilds > for 1 package with the same req use that'd count as 10 above. >=20 > [...] > > > The cycle is mostly due to: > > > $ python3 nsolve.py 'llvm? ( gallium ) gallium? ( llvm )' > > > [...] > > > toposort.CircularDependencyError: Circular dependencies exist among > > > these items: {[gallium]? =3D> [llvm]:{[llvm]? =3D> [gallium]}, [llvm]= ? > > > =3D> [gallium]:{[gallium]? =3D> [llvm]}} > > >=20 > > >=20 > > > This is something I had overseen when replacing 'a q'_j is some p_i > > > and one of q_1 ... q_m might be false' by only 'a q'_j is some > > > p_i'; it can be replaced without changing anything in the way PM > > > would solve it by "a q'_j is some p_i and the set of {q_j} is not a > > > subset of q' union p'" (that is, {q_i} is not trivially true if the > > > 2nd clause is applied). Extending that, we get those stats: =20 > >=20 > > I'm not even trying to understand the things you say with indexes but > > I trust you know what you're doing. >=20 > With that kind of things it's good to have someone having a second > look. It's so easy to forget a case or to miss a simplification. I'm sure Ciaran will love to elaborate ;-). > > Well, I guess it's time to hit the next level. For a start, we have to > > handle all-of groups, i.e.: > >=20 > > ( a b c ) > >=20 > > Stand-alone makes little sense (and little trouble) but as you could > > have seen it's used nested in other thingies: > >=20 > > 1. || ( ( a b ) ( c d ) e ) > >=20 > > 2. ?? ( ( a b ) ( c d ) e ) > >=20 > > 3. ^^ ( ( a b ) ( c d ) e ) >=20 > Yeah that's the nesting problem causing a parse error. > Those should be expanded to implications. What I'm relying onto is all > clauses to be of the form '[list of conditions]? [list of constraints]' I've noticed that you turned the implications into multi-conditions, breaking all my scripts ;-). Is the [list of conditions] conjunctive or disjunctive? > > For verifying constraints, they are not bad. We just follow the > > generic rule that the branch evaluates to true if all subexpressions > > are true.=C2=A0 > >=20 > > For solving, it might be a little unclear on how to proceed with > > partially true branches but for the sake of simplicity I would just > > ignore them and behave as if they were false. That is, case (1) with > > USE=3D'c' would result in 'a b' being enabled. > >=20 > > The practical uses I've seen are: > >=20 > > a.=C2=A0|| ( deprecated ( gtk3 introspection ) ) > >=20 > > I guess this one would be equivalent to: > >=20 > > !gtk3? ( !introspection? ( deprecated ) ) >=20 > Unfortunately no. Favoring leftmost, you need to enable 'deprecated' > when either gtk3 or introspection is false. >=20 > That'd be: > !gtk3? ( deprecated ) > !introspection? ( deprecated ) Well, I meant 'by current rules', without considering preferences. > Fortunately we can distribute \/ and /\: > > > ( deprecated ( gtk3 introspection ) ) >=20 > is equivalent to: > > > ( deprecated gtk3 ) > > > ( deprecated introspection ) >=20 > giving the above implication translation. >=20 > This can be extended to=20 > > > ( ( a1 a2 a3 ... ) ( b1 b2 b3 ... ) ... ) to handle all cases. >=20 >=20 >=20 > > b. ^^ ( ( !32bit 64bit ) ( 32bit !64bit ) ( 32bit 64bit ) ) > >=20 > > This looks like a crazy way of saying: > >=20 > > || ( 32bit 64bit ) >=20 > Hmm yes >=20 >=20 > > c. ^^ ( ( !ruby !s7 ) ( ruby !s7 ) ( !ruby s7 ) ) > >=20 > > This looks like an insane version of: > >=20 > > ?? ( ruby s7 ) >=20 >=20 > yes too it seems >=20 >=20 >=20 > > except that per my solver it just disables both when both are set ;-). >=20 > That's kind of the point. And that's why it is important to have the > solving rules well defined. Depending on how REQUIRED_USE is written, > it will be solved differently even for equivalent logical formulas. >=20 >=20 > > Not sure if the extra complexity is worth for roughly one valid use > > case, and a lot of insanity. >=20 > I think this can be done without too much pain. As you noticed, replace > '^^ ( whatever )' by '|| ( whatever ) ?? ( whatever )' so we're left > with only || and ?? (and 'and' denoted by space and grouping in our > notation). >=20 > > > ( clause1 clause2 ... ) is replaced by >=20 > [!clause1 !clause2 ...]?[clause1] >=20 > ?? ( clause1 clause2 ... ) is replaced by: > [clause1]?[!clause2 !clause3 ...] > [!clause1]?[ ?? ( clause2 clause3 ... ) ] >=20 > ! (|| ( clause1 clause2 ... ) ) is '!clause1 !clause2 ...' (de morgan) > ! ( clause1 clause2 ... ) is '|| ( !clause1 !clause2 ... )' (de morgan > too) > ! (?? ( clause1 clause2 ... ) ) could be written as 'clause1? ( || > ( clause2 ... ) ) !clause1? ( ! ?? ( clause2 ... ) )' >=20 > and I think that's it to allow expanding everything to implications. >=20 >=20 > [ begin || ( clause1 clause2 ... ) end ]?[constraint] >=20 > is: > [ begin clause1 end]?[constraint] > [ begin clause2 end]?[constraint] > etc. >=20 >=20 > [ begin ([icond]?[iconstraint]) end]?[constraint] > is: > [ begin icond]?[iconstraint] > [ begin end]?[constraint] >=20 > I think >=20 > and >=20 > [ begin ( clause1 clause2 ... ) end]?[constraint] > is > [ begin clause1 clause2 ... end]?[constraint] >=20 >=20 > [...] > > Of course past that there's a deeper insanity: all those constructs > > can be nested without limits. Verification is possible, solving maybe > > -- but I'm not sure if we even want to try to think what the correct > > solution would be. >=20 > We're good as long as they're rewritten as implications internally. >=20 >=20 > > There's only one use of this: > >=20 > > ?? ( gl3plus ( || ( gles2 gles3 ) ) ) >=20 > That'd be: > gl3plus? ( ! || ( gles2 gles3 ) ) >=20 > per the above reduced to: > gl3plus? ( !gles2 !gles3 ) >=20 > >=20 > > FWICS, it probably works like this; > >=20 > > =C2=A0g=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0g=C2=A0=C2=A0=C2=A0=C2= =A0 > > =C2=A0l=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0l=C2=A0=C2=A0=C2=A0=C2= =A0 > > =C2=A03 g g=C2=A0=C2=A0=C2=A03 g g > > =C2=A0p l l=C2=A0=C2=A0=C2=A0p l l > > =C2=A0l e e=C2=A0=C2=A0=C2=A0l e e > > =C2=A0u s s=C2=A0=C2=A0=C2=A0u s s > > =C2=A0s 2 3 | s 2 3 > > =C2=A00 0 0 | 0 0 0 (=3D=3D) > > =C2=A00 0 1 | 0 0 1 (=3D=3D) > > =C2=A00 1 0 | 0 1 0 (=3D=3D) > > =C2=A00 1 1 | 0 1 1 (=3D=3D) > > =C2=A01 0 0 | 1 0 0 (=3D=3D) > > =C2=A01 0 1 | 1 0 1 [unsolvable due to loop] > > =C2=A01 1 0 | 1 1 0 [unsolvable due to loop] > > =C2=A01 1 1 | 1 1 1 [unsolvable due to loop] > >=20 > > i.e. it would be equivalent to: > >=20 > > gl3plus? ( !gles2 !gles3 ) > >=20 > > unless the author meant something else and failed. >=20 >=20 > Exactly. I don't know why you see a loop. My solver doesn't really support nested || ^^, so it failed to apply any reasonable change ;-). > > The question is whether we want to: > >=20 > > a. actually try to solve this nesting insanity, > >=20 > > b. declare it unsupported and throw REQUIRED_USE mismatch on user, > >=20 > > c. ban it altogether. >=20 >=20 > I don't think it is *that* insane to support nesting :) >=20 || ( ^^ ( ?? ( a b ) c ( d e ) ) f ) ? ;-) --=20 Best regards, Micha=C5=82 G=C3=B3rny --=-/8X6GyCTz6tczZLUcPrn 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+0Rk4FAlk1noRfFIAAAAAALgAo aXNzdWVyLWZwckBub3RhdGlvbnMub3BlbnBncC5maWZ0aGhvcnNlbWFuLm5ldDZE QkIwN0NDNEYwREFEMDZFQTBBRkU0MUIwN0ExQUVBRUZCNDQ2NEUSHG1nb3JueUBn ZW50b28ub3JnAAoJELB6GurvtEZOc/YP/1hQPHDoS2+vF1OTT7jCsRmS9OGFHGp5 W/NTJCRL/NJ0R7MadXmKoLzafJxkVCsAzjncy1EFgncEF3d3RQP3cMrOmlJbGDyj oTCJIYJ0NNU2L5yAwkil4mOxt1GO6qucKYS2rvdrTKsniPDh0Vh1g+GNFYNSXWKW oUhSv6rK2XzbHW2Rn54/ZuXgvZTKuF/BVy3QOk0tjZBW1OQEl0Xnfo636pP095Sz 0ydelj0ddjZ9roWBVpQEfNOik/k7X/V0hWfZ48sh0OxCbC/mHz6z8vpVX1eGwro1 7ug9YjN7pOOngVSqrmOibhUJMtlo+bK7Y2E02DOv617PHxseJO8LtOJ6UEk4H6f8 LETOF4bQv3vMqcXusvQWibXOtYEEm0PR5HttE7x/brsbW5zabsRK5C37P0cLZ1Z8 L6fxFj4QuIht3cBXsRxfojFSRZOWJ/ZclAupmhccxI5zfZeDHYc3uHm/HXBpeD0M +mwMmoBBvR4G0KwuEbOp97hpyrewhxoQNkTELMJZJv13HXn1iKZXpquppXt7YAlW jU+5vWT38sTrWpSv9vJr05yCR3dO/8TNQ7Jzz6Eg72MB3NGFEHkw3LjGmi+GiUse U9TY8oK75jWUj5PXKKzMACf5QCFdPPaqF64Q33rbyUWkWuWDrXBEWVnoSft6lc6l A7v4J0JllMbE =rIm8 -----END PGP SIGNATURE----- --=-/8X6GyCTz6tczZLUcPrn--