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 2C279139694 for ; Mon, 12 Jun 2017 19:17:31 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id D20F1E0CB0; Mon, 12 Jun 2017 19:17: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 75B4BE0C31 for ; Mon, 12 Jun 2017 19:17:23 +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 B95E23417DD; Mon, 12 Jun 2017 19:17:21 +0000 (UTC) Message-ID: <1497295036.1575.10.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, 12 Jun 2017 21:17:16 +0200 In-Reply-To: <20170612110836.7b670c93@gentoo.org> References: <1496071993.31087.1.camel@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> <1496686212.1222.4.camel@gentoo.org> <20170606140803.051f8048@gentoo.org> <1496770744.1157.1.camel@gentoo.org> <20170607101759.7e21f0f6@gentoo.org> <1496827679.2129.3.camel@gentoo.org> <20170607115654.2a5da5e2@gentoo.org> <1496999960.29391.1.camel@gentoo.org> <20170609134110.418ae6ac@gentoo.org> <1497012847.25475.4.camel@gentoo.org> <20170609161619.1b72ad5b@gentoo.org> <1497025310.25475.7.camel@gentoo.org> <20170611180518.5e28ddfa@gentoo.org> <20170612110836.7b670c93@gentoo.org> Organization: Gentoo Content-Type: multipart/signed; micalg="pgp-sha512"; protocol="application/pgp-signature"; boundary="=-4XUVlo11bHpoOGsnMOs2" 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: bc012e14-67ce-49cb-ae11-f9fdaca9c1c7 X-Archives-Hash: cc8b2f81509c30a4e03ea05354d5873b --=-4XUVlo11bHpoOGsnMOs2 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On pon, 2017-06-12 at 11:08 +0200, Alexis Ballier wrote: > On Sun, 11 Jun 2017 18:05:18 +0200 > Alexis Ballier wrote: >=20 > > I think this handles all the cases. I'll try to update the repo with > > that algo. >=20 > I've updated my fork. It'd be good to merge it and rebase solve() on > top of the output of to_impl.convert_to_implications if you're happy > with it. >=20 > $ time python3 classify.py requsel=20 > Stats: > Parse error: 0 > Good: 8334 > Need topo sort: 152 > Cyclic: 43 >=20 > real 0m1.874s > user 0m1.869s > sys 0m0.005s >=20 >=20 >=20 > It works better, no more parse error, and only 43 problematic cases. Thanks for doing it. It's certainly an interesting case study. I've merged it and pushed the result. However, I personally think it's only going to work against your case. You can clearly see now how complex the code has become. Even in the pseudo-ocaml you presented it already is complex. Now imagine having to retype it in cleartext suitable for the PMS. I've actually started typing the initial specification yesterday [1]. As you can see, banning the extra constraints has made the algorithms much simpler. In particular: 1. You do not have to define 'falsify' for anything other than pure flags -- which makes it easy to inline it. 2. ||, ??, ^^ groups are only flat lists of flags -- which makes reordering and processing them trivial. 3. The algorithm is recursive only on USE-conditional groups. This makes it trivial to make it iterative. Optimizations become trivially possible. Nevertheless, feel free to play with the full implementation. If you're interested, you can play with the complex cases more. In particular, I'm wondering whether nsolve will actually consider most of them solvable. As for the results, I think it is the point where we start preparing pull requests with REQUIRED_USE changes to see whether the developers agree with such changes. [1]:https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse --=20 Best regards, Micha=C5=82 G=C3=B3rny --=-4XUVlo11bHpoOGsnMOs2 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+0Rk4FAlk+6L1fFIAAAAAALgAo aXNzdWVyLWZwckBub3RhdGlvbnMub3BlbnBncC5maWZ0aGhvcnNlbWFuLm5ldDZE QkIwN0NDNEYwREFEMDZFQTBBRkU0MUIwN0ExQUVBRUZCNDQ2NEUSHG1nb3JueUBn ZW50b28ub3JnAAoJELB6GurvtEZOjb8P/jqOAP9zVY8xoRJUQFMAn2LDgDfGcj1e bRxlrlHjoGaa2nZU8YIDSxrYODwNSb6tAan63O0lmfguLfHHfhBEdqh71euJisCf AunMPYLDZSe4+Z6nMr6bdHciMgNXEsV0+FV/qFOvtAjrvhzGltxH+R6EIloWCKF6 n6MvzNJbHDGWp+M7/fX5GhNsGvjvDtdd3yQvndJcEolW6/lT8w6yvtXzkZfK7dYr DHbxLG804ZnkLSemO2pnkRfEFg/ZwFkgHFwNmQT3p3/offfj4KMvuxNEKWDXb4J4 4c2ZSycBJo4XV5udrcf/h+I9APqxRDEm84Tu/jOUCdZkJ/ErI4xMzz61S9ncgmvF RMQlKezq40Izko6pbU+8I6D6HOhQXZ5eCeqcOQ+bPBPLXbo+yb76E+IBKo3BNmG1 4adm47EAlDqBumST9iUFVVd7ppt2EF9a1OfzDW7FYVF8FOoZ4vUU3NP64ucZYDlW osZmsR1FNTNWynsg8ChLS7Mtd4Q+6p8QtLjk9ugm1dUx3rLGCWSmx+4sb/yTOVk+ HGctetQ2hGW0U/8MrpyAixv45rQwMQoZCXgyABmBon+3aQypqHNJ3hr66o51QF62 k2RWCG79qmie/859FMmzq4++dBkeMYWqzcLl9SPMRai/54lJQfnZmIoUc1SvKUyj WAQVxGdT0gyw =fEdv -----END PGP SIGNATURE----- --=-4XUVlo11bHpoOGsnMOs2--