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 E084B139694 for ; Tue, 13 Jun 2017 10:28:01 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id A3660E0C04; Tue, 13 Jun 2017 10:27:53 +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 444D3E0829 for ; Tue, 13 Jun 2017 10:27:53 +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 7AFB73418AF for ; Tue, 13 Jun 2017 10:27:51 +0000 (UTC) Date: Tue, 13 Jun 2017 12:27:45 +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: <20170613122745.455b39f7@gentoo.org> In-Reply-To: <1497295036.1575.10.camel@gentoo.org> References: <1496071993.31087.1.camel@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> <1497295036.1575.10.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: b64f7e34-ed0d-4df1-8dd8-5d9d14452f6d X-Archives-Hash: cb01121cc91db7f5d22699bebf331c72 On Mon, 12 Jun 2017 21:17:16 +0200 Micha=C5=82 G=C3=B3rny wrote: > 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 > >=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. =20 >=20 > Thanks for doing it. It's certainly an interesting case study. I've > merged it and pushed the result. >=20 > However, I personally think it's only going to work against your case. What do you mean here ? > 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. The code needs cleanup and probably some refactoring. I think it can be made much simpler. > 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: >=20 > 1. You do not have to define 'falsify' for anything other than pure > flags -- which makes it easy to inline it. >=20 > 2. ||, ??, ^^ groups are only flat lists of flags -- which makes > reordering and processing them trivial. >=20 > 3. The algorithm is recursive only on USE-conditional groups. This > makes it trivial to make it iterative. Optimizations become trivially > possible. While you're right in one sense, you're mixing two different things here. What you wrote *is* recursive. It does not recurse just because you're assuming a restricted syntax. You're only saving two things: you don't need to define how to enforce to false (that is 3 lines not 3 pages :=3D) ) and you're avoiding the nested use conditionals that are already ill defined per the current spec (foo? bar is equivalent to && ( foo bar ) when nested) which I believe is already another problem. Then, remember how I wanted to be much more drastic than you in the beginning by killing all ||,&&,^^ etc. and keep only use conditionals in REQUIRED_USE ? Well, that's where the complexity comes. The whole deal then is to define rewriting rules for the AST so that the algorithm you describe executes the exact same instructions but the new AST only has use conditionals. This is more like writing a compiler for the spec, so this does not belong to the spec and there is no issue here. [BTW: checking the rewrite rules behave properly is what I meant by rebasing solve() on top of it and being happy with it] > 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. >=20 > 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. If by that you also include code cleanup and writing tests then yes :) > [1]:https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse I really don't like the reordering thing. Even the restricted syntax does not fix the issue with '^^ ( a b ) b? ( a )' already mentioned here. It'd be much better and simpler for the spec just to assign a fixed value and use the solving rules with those. Alexis.