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 A74FB139694 for ; Wed, 31 May 2017 06:55:32 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id DEC3321C072; Wed, 31 May 2017 06: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 7EA51E0CCD for ; Wed, 31 May 2017 06:55: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 D1372341692; Wed, 31 May 2017 06:55:21 +0000 (UTC) Message-ID: <1496213717.1164.1.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: Wed, 31 May 2017 08:55:17 +0200 In-Reply-To: <20170530204614.61e8e42c@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> Organization: Gentoo Content-Type: multipart/signed; micalg="pgp-sha512"; protocol="application/pgp-signature"; boundary="=-tBFB+PCnqx0GdvJMk6g/" 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: ddfbeb62-6a83-4ae7-bd69-c500177289f3 X-Archives-Hash: 2033cb21da9660e2fabfaa330e08c35e --=-tBFB+PCnqx0GdvJMk6g/ Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On wto, 2017-05-30 at 20:46 +0200, Alexis Ballier wrote: > On Tue, 30 May 2017 20:11:38 +0200 > Micha=C5=82 G=C3=B3rny wrote: > [...] > > > > Of course, we could just validate all the possible cases via > > > > repoman, and reject the ebuild if there's at least one conflict > > > > between them. Not sure how to express that properly in the spec > > > > though. Not sure how it would work practically. =20 > > >=20 > > > Adding a 2^n check to repoman isn't gonna work well. > > > =20 > >=20 > > I'm not saying it's the most optimal algorithm of verifying > > the correctness of the constraints. It's just the one that's quite > > obvious -- relatively simple and reliable. If someone can come up with > > something better that covers at least the most common cases, I'm all > > for it. > >=20 > > That said, this wouldn't be that much of a problem if we can keep the > > n low. For a start, we can rule out all flags that don't appear > > in REQUIRED_USE at all. Furthermore, I think we could also ignore > > the constraints for flags that don't appear there at least 'twice', > > and so on. >=20 > :) >=20 > You're applying classical techniques to lower the size of a SAT > instance so that your exponential algorithm does not explode, but it's > still hard. >=20 > I'm not sure what you want: If you want to detect that there is an > impossible constraint, well, ebuild writer will notice soon enough when > testing it. If you want to detect that there is a way to have a > conflict between useflags, then there will be valid cases where this > will happen. >=20 > That said, assuming we have REQUIRED_USE in CNF form, its negation is > in DNF form. Solving SAT on DNF formulas is easy (linear I think), and > this would give you an assignment of useflags triggering an impossible > constraint. e.g. 'foo? ( bar )' with USE=3D'foo -bar' in make.conf. > This could be used to trigger a repoman warning but basically every > single ebuild would trigger those. Not sure if we understand each other. I'd like the constraints to be plain straightforward, to the point of having only one acceptable solution. No special Portage-style algorithms that attempt to provide a reasonable solution to unreasonable input, resulting in horrible solutions that need 20 more hacks every few months. For example: foo? ( bar ) would mean 'if you have USE=3Dfoo, then USE=3Dbar is enabled as well'. Not 'find some random solution which satisfies this'. In other words, here changing USE=3Dfoo into USE=3D-foo is not an acceptable solution. Now, this also means that every constraint that can't be solved in this easy fashion is invalid. We want to detect that, and warn the developer. Some of those could be tricky. Simple example: foo? ( baz ) bar? ( !baz ) This one is invalid because USE=3D'foo bar' requires both 'baz' and '!baz' as a solution. Remember that we don't want to do any changes besides what's explicitly written there, no guessing. However, the following should be valid: foo? ( baz ) bar? ( !foo !baz ) Because now we clearly indicate that USE=3Dbar disables USE=3Dfoo, and therefore makes the first constraint inapplicable. It clearly indicates course of action for all combinations: foo bar baz -> foo bar baz F F F -> [valid] F F T -> [valid] F T F -> [valid] F T T -> F T F T F F -> T F T T F T -> [valid] T T F -> F T F T T T -> F T F --=20 Best regards, Micha=C5=82 G=C3=B3rny --=-tBFB+PCnqx0GdvJMk6g/ 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+0Rk4FAlkuaNVfFIAAAAAALgAo aXNzdWVyLWZwckBub3RhdGlvbnMub3BlbnBncC5maWZ0aGhvcnNlbWFuLm5ldDZE QkIwN0NDNEYwREFEMDZFQTBBRkU0MUIwN0ExQUVBRUZCNDQ2NEUSHG1nb3JueUBn ZW50b28ub3JnAAoJELB6GurvtEZOjyUQAN2i71jvveVOvh1JTtRcAYLPJ0/ZKssf W0J/bk2LGDGOM4/OXBvblnIi/2VOBHaHAe+6CTQN7ejpEhJz4neMTKZ3TZUGy2YA ocQFk6/SJ6mn1V4Ekl2y0XE00dToBqXZuJLXVbvKhiQPBaVTjLxoJXhDw6swiEzv j8SnujbCzyyRYiEBabtGZD5R8e/nRO4DwWfSmM4ZvWdgGAqTFDqt/hVeJBZ+0RYi dqKaE7h/dLO31ufnnWeRBCwv21eqje+a2ftLLu09fG8PNPGQDADv4YZ+8+SQSKmh WJmUrTG56TnJpuTl1qsRJxK0e3ez/PNO9peihRVBeakxzshknVpE1vxEkP7H5WE7 OSlUpZyLbUvcIZblPjQTrA2E7DxZMK9LYRNmCp4qEymdP1BYDLAu9kay+4Xzypkn YOiU7cS/R84Wl3TIsPxApwkPjOr4cVv5scpvYoh3YlU7Fzkrn10qmwXv2cB8FUyL aXwAymwXAiN2ct9fK604BcmbO4AJ/Mwz/BTgf7AdEvbsI3vQI8JhpYg+03CNDIPL KbW5GHhEGDvFD+pWh0JHbvvbu+CXq/GF4IzGgNNhE56/zGTw03fcw0Oe0RPHaSaS vnYZSGBLrwaOn1EDLnTfpQgDeBdUvWT13LHQMvd9WeEErEnthZUIDyJM5xzDVN3/ 6Y70o7nQf8oQ =JMyy -----END PGP SIGNATURE----- --=-tBFB+PCnqx0GdvJMk6g/--