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 6B7BD139694 for ; Thu, 1 Jun 2017 21:31:40 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 76A5DE0BF4; Thu, 1 Jun 2017 21:31:31 +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 1BACFE0AC9 for ; Thu, 1 Jun 2017 21:31:31 +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 2C4FA33BF43; Thu, 1 Jun 2017 21:31:28 +0000 (UTC) Message-ID: <1496352685.30502.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: Thu, 01 Jun 2017 23:31:25 +0200 In-Reply-To: <20170601105523.08a9234e@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> Organization: Gentoo Content-Type: multipart/signed; micalg="pgp-sha512"; protocol="application/pgp-signature"; boundary="=-jofPiXEkgQcO2RIJPAql" 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: 368b957a-ee24-449c-95c2-a35bbf64c802 X-Archives-Hash: eabd617ec2fb115af7e1444ed94858bf --=-jofPiXEkgQcO2RIJPAql Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On czw, 2017-06-01 at 10:55 +0200, Alexis Ballier wrote: > On Wed, 31 May 2017 21:02:24 +0200 > Micha=C5=82 G=C3=B3rny wrote: >=20 > > On =C5=9Bro, 2017-05-31 at 19:39 +0200, Alexis Ballier wrote: > > > > > Again, you *need* to process the constraints in order. '!a? > > > > > ( b ) !b? ( a )' is not deterministic when none of a and b are > > > > > enabled otherwise. =20 > > > >=20 > > > > You can't rely on any particular order of constraints, especially > > > > when eclass stacking comes into play. You could try defining some > > > > constraint- sorting algorithm but it's going to be complex and > > > > it's usefulness will be limited anyway due to various kinds of > > > > grouping. =20 > > >=20 > > >=20 > > > Better have some order: If half of the above constraint comes from > > > ebuild and the other half comes from eclass, then PM might toggle > > > 'a' or 'b' depending on the phase of the moon which is specifically > > > what we're trying to avoid. =20 > >=20 > > No, it can't. That's the whole point. The algorithm must be defined so > > that it is always predictable independently of order (maybe except > > the ordering inside ^^, ||, ??) and independently of how it's nested > > (i.e. 'a? ( b? ( c ) )' must give the same result as 'b? ( a? ( c ) > > )'). >=20 > This is a lot of handwaving without real description of how it would > work. This starts to look a lot like confluence in rewriting systems > and you want developers to write only confluent rules and repoman to > decide that. Good luck with that. I'm sorry, what I said was quite stupid. I did some thinking and testing today, and the algorithm can be actually quite trivial. The real issue is getting a correct input, that is REQUIRED_USE constraints that have only one solution. That is the whole problem I was signaling, and which I seem to have lost sight of: solving is trivial, ensuring that the constraint can have only one solution isn't. Hopefully, most of the simple constraints in use will 'just work'. The biggest issue for me right now is to find a way to determine whether a particular REQUIRED_USE constraint can have only one solution, independently of the order of non-n-ary constraints. However, some of it can be easily eyeball-checked using a graph. > Let's look at real world examples: > gtk+: >=20 > REQUIRED_USE=3D" > || ( aqua wayland X ) > xinerama? ( X ) > " $ ./solve.py '|| ( aqua wayland X ) xinerama? ( X )' [!wayland? =3D> [!X? =3D> [aqua]], xinerama? =3D> [X]] =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0x=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0x =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0w i=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= w i =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0a n=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= a n =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0y e=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= y e =C2=A0=C2=A0=C2=A0a l r=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0a l r =C2=A0=C2=A0=C2=A0q a a=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0q a a =C2=A0=C2=A0=C2=A0u n m=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0u n m =C2=A0X a d a | X a d a =C2=A00 0 0 0 | 0 1 0 0 =C2=A00 0 0 1 | 1 1 0 1 =C2=A00 0 1 0 | 0 0 1 0 (=3D=3D) =C2=A00 0 1 1 | 1 0 1 1 =C2=A00 1 0 0 | 0 1 0 0 (=3D=3D) =C2=A00 1 0 1 | 1 1 0 1 =C2=A00 1 1 0 | 0 1 1 0 (=3D=3D) =C2=A00 1 1 1 | 1 1 1 1 =C2=A01 0 0 0 | 1 0 0 0 (=3D=3D) =C2=A01 0 0 1 | 1 0 0 1 (=3D=3D) =C2=A01 0 1 0 | 1 0 1 0 (=3D=3D) =C2=A01 0 1 1 | 1 0 1 1 (=3D=3D) =C2=A01 1 0 0 | 1 1 0 0 (=3D=3D) =C2=A01 1 0 1 | 1 1 0 1 (=3D=3D) =C2=A01 1 1 0 | 1 1 1 0 (=3D=3D) =C2=A01 1 1 1 | 1 1 1 1 (=3D=3D) >=20 > Let's assume aqua is masked, which reduces to: > REQUIRED_USE=3D" > || ( wayland X ) > xinerama? ( X ) > " $ ./solve.py '|| ( aqua wayland X ) xinerama? ( X )' '!aqua' [!X? =3D> [!aqua? =3D> [wayland]], xinerama? =3D> [X]] =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0x=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0x =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0w i=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= w i =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0a n=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= a n =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0y e=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= y e =C2=A0=C2=A0=C2=A0a l r=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0a l r =C2=A0=C2=A0=C2=A0q a a=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0q a a =C2=A0=C2=A0=C2=A0u n m=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0u n m =C2=A0X a d a | X a d a =C2=A00 0 0 0 | 0 0 1 0 =C2=A00 0 0 1 | 1 0 1 1 =C2=A00 0 1 0 | 0 0 1 0 (=3D=3D) =C2=A00 0 1 1 | 1 0 1 1 =C2=A01 0 0 0 | 1 0 0 0 (=3D=3D) =C2=A01 0 0 1 | 1 0 0 1 (=3D=3D) =C2=A01 0 1 0 | 1 0 1 0 (=3D=3D) =C2=A01 0 1 1 | 1 0 1 1 (=3D=3D) (to avoid having to explicitly play with empty clauses and such, it doesn't remove masked flags, just shifts them to the end) >=20 > With USE=3D'-* xinerama' this one is invalid: applying the first > constraint first enables wayland, then the 2nd enables X, giving a > result of USE=3D"xinerama wayland X". Applying the 2nd first enables X, > then the 1st does nothing, giving a result of USE=3D"xinerama X". Indeed. To regain order-indepedence, you could do: xinerama? ( X ) !xinerama? ( || ( aqua wayland X ) ) While it's non-obvious, it's the only reasonable way to ensure that things don't start falling apart randomly. > Now the funny one: > $ portageq metadata / ebuild dev-lang/php-7.0.18 REQUIRED_USE > cli? ( ^^ ( readline libedit ) ) truetype? ( gd ) webp? ( gd ) cjk? > ( gd ) exif? ( gd ) xpm? ( gd ) gd? ( zlib ) simplexml? ( xml ) soap? > ( xml ) wddx? ( xml ) xmlrpc? ( || ( xml iconv ) ) xmlreader? ( xml ) > xslt? ( xml ) ldap-sasl? ( ldap ) mhash? ( hash ) phar? ( hash ) qdbm? > ( !gdbm ) readline? ( !libedit ) recode? ( !imap !mysqli ) sharedmem? > ( !threads ) mysql? ( || ( mysqli pdo ) ) || ( cli cgi fpm apache2 > embed phpdbg ) It isn't as scary as it looks. If you graph it, then you can notice it's just got a few separate sub-graphs: 1. [!cgi, !fpm, !phpdbg, !apache2, !embed] -> cli -> (readline <=3D> !libed= it) (the last bit having duplicate 'readline? ( !libedit )' which is wrong) 2. [truetype, webp, cjk, exif, xpm] -> gd -> zlib 3. [simplexml, soap, wddx, xmlrpc, !iconv, xmlreader, xslt] -> xml 4. ldap-sasl -> ldap 5. [mhash, phar] -> hash 6. qdbm -> !gdbm 7. recode -> [!imap, !mysqli] [mysql, !pdo] -> mysqli (note that there are both implications for mysqli and !mysqli -- for 4 cases they cause convergence error) 8. sharedmem -> !threads All but 1 and 7 are trivial. > 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. You just take a second iteration, and things fall into place. That's not a problem. > > > 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 > 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. 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. > > > > The point would be: by definition, the solver should be able to > > > > touch *any* USE flag. If it can't, it mostly implies that you > > > > can't use the automatic solver, and so the case is irrelevant for > > > > checking. Attempting to go beyond that is going to give a lot of > > > > complexity and most likely kill the whole idea. > > > >=20 > > > > One thing we need to worry about are masks. We need to think about > > > > them. =20 > > >=20 > > > It makes zero difference for any solver if you replace variables > > > (useflags) by 'true' or 'false' constants (masked/forced/user-forced > > > useflags). It's even simpler actually. Whether the formula is not > > > constantly 'true' (ie REQUIRED_USE is useless) or constantly > > > 'false' (ie there's no way to solve it) is equivalent to solving > > > SAT. We likely don't want that for repoman running on php. > > > =20 > >=20 > > Well, probably yes. We just need to make sure to apply them correctly > > in different contexts, to avoid accidentally skipping some > > constraints. I think it would be reasonably to assume that: >=20 > [...] >=20 > Yes, you can eliminate constants. It is probably even confluent, i.e. > the order in which you eliminate them does not matter and it always > converges to the same result. >=20 As mentioned above, I've chosen an even simpler path -- I just push true parts up front, and false to back. This handles all the cases without extra checking logic -- if immutables satisfy the constraint, it's satisfied early; if they make it impossible to satisfy it, they just make it fail at trying to touch an immutable flag. $ ./solve.py "^^ ( c b a )" 'a b' [!a? =3D> [!c? =3D> [b]], b? =3D> [!a, !c], a? =3D> [!c]] =C2=A0a b c | a b c =C2=A01 1 0 | [unsolvable: immutable a mismatched] =C2=A01 1 1 | [unsolvable: immutable a mismatched] My current code is on github [1]. It's ugly, slow and incomplete. It's merely a proof-of-concept and testing toy but still could give some clues. [1]:https://github.com/mgorny/required-use --=20 Best regards, Micha=C5=82 G=C3=B3rny --=-jofPiXEkgQcO2RIJPAql 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+0Rk4FAlkwh61fFIAAAAAALgAo aXNzdWVyLWZwckBub3RhdGlvbnMub3BlbnBncC5maWZ0aGhvcnNlbWFuLm5ldDZE QkIwN0NDNEYwREFEMDZFQTBBRkU0MUIwN0ExQUVBRUZCNDQ2NEUSHG1nb3JueUBn ZW50b28ub3JnAAoJELB6GurvtEZOsDMQAIAQHpEIJg5q/w9ZITv1qZvRlRrYSQgc OPy6HbDApBzgq1YWldM4YiuGpCW57mmNrpJLeYtizZDmf7gRIVY/LWUgkoN7qhGU p91cLacHSzCsKnIWEtjhK5RXUuU1HQvh34MJHPt82K7ETlWhFEdqrqmSBDMVvXh8 OXcaoU+oS1i56Qq2ppwe+i7wRzeUTrCWrO3jRVUpk3TMw8o/JByNfWkSbM2vNaDL 9/4TuCs7vKw5+L+Dl64lme0mmM+dz6mRrGbL5JT881QCVVhNWbldQ1ZXA4SxvOwp RB5Pvgyamie9L6zSEjvd0FcOsurcM0mvw4uhxaK3vZtmAhIhkqfN/jW7ZNTRGbaK xnwhyWhQjIgcJg+ginnelofiiAhnfUaJvTiIyI716/2MYxEMJsBI3POaKy8x/kp1 XceIO2Pik1QCLwNFupx+ADiveiBqgEsZc1YyTmSMoRQl4d4K80gLnWY6846zvulS coQ9IGFrE5YxJtsmxbbYlxJUjEo+RkQ7z3NosJqIxI6Kk0dPasgCefAj4v/51m97 2Um5anGRZicgmBBPoJR1Si5jSgd7xremJzPD5oZeTPsCsNS7CCOH9l3mo2t08cQE +AigjR0sGEOmYBBoHHOi+NIvL7EndlKLxqoN/1926URESLv35MIFq3QZk6hjG8Hc Ry9uDc2UhNCT =R60i -----END PGP SIGNATURE----- --=-jofPiXEkgQcO2RIJPAql--