Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On Sun, 09 Jul 2017 13:36:16 +0200 Michał Górny wrote: > On nie, 2017-07-09 at 11:29 +0200, Alexis Ballier wrote: > > You don't seem to get how normalizing and constant > > propagation/elimination works. > > > > Basically, reordering would be: > > And(list) -> And( forced(list) + free(list) + masked(list) ) > > Or(list) -> Or( ... . ) > > etc. > > > > While normalizing is: > > And(list) -> False if False appears in a normalize(x) for x in list, > > True if normalize(x) for x in list is empty or all > > True, And(normalize(x) for x in list if != True and != False) > > etc. > > > > That's described in one point: Apply boolean algebra rules. > > Last I checked, implementing a full-fledged boolean algebra processor > with reductions and other magic is a non-goal here. That is not a goal for auto solving required use, but catching uninstallable packages is probably more important than that... > > What I don't like about reordering is that it is too tightly > > coupled to the following solving algorithm and the restricted > > syntax, while really, having REQUIRED_USE constraints asking you to > > enable a masked flag is something we ought to kill even without > > solving as they hide broken deps and make all our QA checks less > > useful. > > It's irrelevant since we kill the unsupported syntax anyway. Your logic is flawed. You kill unsupported syntax because you fail to get it right with all the complexity you're carrying, not the other way around. > > Finally, reordering, being essentially a local thing, does not have > > the proper behavior in a general AST: > > '|| ( ( a b ) c )' with 'a' and 'b' masked will be left invariant by > > reordering and the resulting expanded form will be rejected while > > constant propagation/elimination will reduce that to 'c' and be > > good. > > Handling a rejected syntax is irrelevant. Rejected by PMS ? > > Hence, the reordering check cannot be used as a good input for > > checking for broken REQUIRED_USE: I really think things like > > 'vulkan? ( || ( video_cards_i965 video_cards_radeonsi ) )' should > > be a repoman error on stable profiles where both those video cards > > are masked and vulkan is not. For that, we need to support the > > whole PMS-defined syntax, not a reduced one. > > No, we don't. It works just fine. The only difference is that it stops > on the first erroneous constraint. Don't you think it's a bit of an understatement saying that an optional auto solver might need to enable masked useflag when in fact there is a useflag that can never be enabled, auto solver or not ? This also makes CI/repoman dep checks fail to catch broken cases: As of today, nothing will catch a game depending on mesa[vulkan] and being ~arm. Good luck installing such a game on arm though. > > > No, it is not. You do not have the values of all the items inside > > > the group, just some of them. Depending on how many of them do you > > > have and what are them, you need to transform the group > > > appropriately, e.g. by removing items, replacing the group or > > > failing entirely. > > > > Yes, that's boolean algebra rules. You propagate constants from > > leaves to root in the AST and if some 'False' appears in your AST > > when you've reached the root you fail. I agree one needs some > > practice on recursive structures to understand that quickly and > > easily though. > > Except that we're dealing with structures which don't strictly follow > boolean algebra rules, as you've already noticed. Hmmm. No ? > > > > > > One big advantage of working on ASTs is that it becomes > > > > > > trivial to suggest a proper reordering. > > > > > > > > > > Reordering is never a trivial problem. Unless I'm missing > > > > > something, it is technically possible that a 'reordering' will > > > > > actually require a sub- item being moved out of the containing > > > > > group. > > > > > > > > Not if done at the AST level. > > > > > > > > > And to be honest, I find the output of the verification > > > > > script in this regard quite useful. That is, it saying 'X > > > > > affects Y, so it needs to go before it' is quite clear to me. > > > > > I don't think most developers would actually need to script > > > > > to pinpoint a specific location for every single > > > > > constraint. > > > > > > > > In most cases this is sufficient. > > > > Think of a more complex case: > > > > A -> B > > > > B -> C > > > > A -> D > > > > D -> C > > > > > > > >|-> B -| > > > > A -| |->C > > > >|-> D -| > > > > > > > > It's starting to be a more complex mental exercise to get the > > > > proper ordering when given the 1st form only. > > > > > > > > > > > > Actually, considering people rant against git merges because > > > > they want linear history in the graph log but fail to > > > > understand 'git log' is precisely about displaying such a > > > > linear ordering, I'm ready to bet someone will rant :) > > > > > > We can discuss
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On nie, 2017-07-09 at 11:29 +0200, Alexis Ballier wrote: > You don't seem to get how normalizing and constant > propagation/elimination works. > > Basically, reordering would be: > And(list) -> And( forced(list) + free(list) + masked(list) ) > Or(list) -> Or( ... . ) > etc. > > While normalizing is: > And(list) -> False if False appears in a normalize(x) for x in list, >True if normalize(x) for x in list is empty or all True, >And(normalize(x) for x in list if != True and != False) > etc. > > That's described in one point: Apply boolean algebra rules. Last I checked, implementing a full-fledged boolean algebra processor with reductions and other magic is a non-goal here. > What I don't like about reordering is that it is too tightly coupled to > the following solving algorithm and the restricted syntax, while really, > having REQUIRED_USE constraints asking you to enable a masked flag is > something we ought to kill even without solving as they hide broken > deps and make all our QA checks less useful. It's irrelevant since we kill the unsupported syntax anyway. > Finally, reordering, being essentially a local thing, does not have the > proper behavior in a general AST: > '|| ( ( a b ) c )' with 'a' and 'b' masked will be left invariant by > reordering and the resulting expanded form will be rejected while > constant propagation/elimination will reduce that to 'c' and be good. Handling a rejected syntax is irrelevant. > Hence, the reordering check cannot be used as a good input for checking > for broken REQUIRED_USE: I really think things like 'vulkan? ( || > ( video_cards_i965 video_cards_radeonsi ) )' should be a repoman error > on stable profiles where both those video cards are masked and vulkan is > not. For that, we need to support the whole PMS-defined syntax, not a > reduced one. No, we don't. It works just fine. The only difference is that it stops on the first erroneous constraint. > > No, it is not. You do not have the values of all the items inside > > the group, just some of them. Depending on how many of them do you > > have and what are them, you need to transform the group > > appropriately, e.g. by removing items, replacing the group or failing > > entirely. > > Yes, that's boolean algebra rules. You propagate constants from leaves > to root in the AST and if some 'False' appears in your AST when you've > reached the root you fail. I agree one needs some practice on recursive > structures to understand that quickly and easily though. Except that we're dealing with structures which don't strictly follow boolean algebra rules, as you've already noticed. > > > > > One big advantage of working on ASTs is that it becomes trivial > > > > > to suggest a proper reordering. > > > > > > > > Reordering is never a trivial problem. Unless I'm missing > > > > something, it is technically possible that a 'reordering' will > > > > actually require a sub- item being moved out of the containing > > > > group. > > > > > > Not if done at the AST level. > > > > > > > And to be honest, I find the output of the verification script in > > > > this regard quite useful. That is, it saying 'X affects Y, so it > > > > needs to go before it' is quite clear to me. I don't think most > > > > developers would actually need to script to pinpoint a specific > > > > location for every single constraint. > > > > > > In most cases this is sufficient. > > > Think of a more complex case: > > > A -> B > > > B -> C > > > A -> D > > > D -> C > > > > > >|-> B -| > > > A -| |->C > > >|-> D -| > > > > > > It's starting to be a more complex mental exercise to get the proper > > > ordering when given the 1st form only. > > > > > > > > > Actually, considering people rant against git merges because they > > > want linear history in the graph log but fail to understand 'git > > > log' is precisely about displaying such a linear ordering, I'm > > > ready to bet someone will rant :) > > > > We can discuss this when you have a working algorithm. Right now, it's > > a purely theoretical exercise unless someone can come up with > > a reasonable way of implementing it. > > Hmmm. lol ? > May I suggest you spend 30 minutes on wikipedia about what topological > sorting is, what it does and what purpose it serves? I was referring to doing all the work on AST level, especially detecting problems. > It's a bit annoying to see you completely lost every time it comes up. I find almost every your mail annoying because of your inability to focus outside one thing you've convinced yourself is the only solution to every problem that ever comes, and to accept that there could be alternative solutions that would work as well. But that's completely irrelevant to the topic at hand and I don't see how pointing out how every one of us is irritating is going to help solve anything. > > Except it doesn't because it's extremely uncommon (and even unlikely) > > and I am successfully ext
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On Sat, 08 Jul 2017 23:56:07 +0200 Michał Górny wrote: > On sob, 2017-07-08 at 22:34 +0200, Alexis Ballier wrote: > > On Sat, 08 Jul 2017 20:44:24 +0200 > > Michał Górny wrote: > > > > > On sob, 2017-07-08 at 16:12 +0200, Alexis Ballier wrote: > > > > On Sat, 08 Jul 2017 11:43:39 +0200 > > > > Michał Górny wrote: > > > > > > > > > Hi, everyone. > > > > > > > > > > I think the affairs have settled enough and I've finished > > > > > filling in the pre-GLEP for REQUIRED_USE auto-enforcing. It's > > > > > got all the algorithms, rationale and separated reference > > > > > implementation. > > > > > > > > > > If there are no major concerns raised, I will soon start > > > > > working on writing an optimized implementation for > > > > > pkgcore/pkgcheck and integrating the verification algos with > > > > > the CI. > > > > > > > > > > The pre-GLEP for review is here: > > > > > > > > > > https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse > > > > > > > > > > > > Constraint group reordering algorithm > > > > > > > > I really think we should only consider REQUIRED_USE with > > > > forced/masked useflags instantiated there. And ban (in repoman) > > > > REQUIRED_USE that contain some "False": "a? ( b )" with 'a' free > > > > and 'b' masked is perfectly ok now but it hides a serious > > > > problem in the package/profile. Instantiating this would give: > > > > "a? ( False )" and be an error just like we have depend.bad & > > > > co. This is independent of auto solving or not, it's already > > > > wrong. > > > > > > As I've already explained you multiple times, this obtains > > > *exactly the same* effect. However, it's much simpler when it's > > > done like this because it makes it possible to reuse the already > > > defined algorithms instead of having to precisely define how to > > > preprocess REQUIRED_USE for this and cover all the corner cases. > > > > Simpler??? I don't think so. What I wrote clearly pinpoints that: > > When you'll write the algorithm for "Verifying that the constraints > > do not alter immutable flags" you'll notice this is exactly that > > and can be put as a preprocessing step and then you can drop all > > the corner cases considerations for immutable flags. I never > > understood why you're insisting that much on immutables: they're > > really not natural, not simple, not standard, and carrying them all > > over seems to be a burden to me. > > I wrote the algorithms, and they're simple. This specific check is > the combination of three simple steps: > > a. reordering the groups based on immutables, > > b. transforming the AST into flat form, > > c. verifying each flat constraint. > > The first step is trivial -- it's basically 'move true to front, false > to back'. The second step is more complex but it's needed anyway, > and quite well-defined, especially with the assumption that all > the groups always have at least one flag inside. The third step is > trivial again because it's just checking the conditions and > constraints against a list. > > The alternative to reordering is altering the groups. Altering means > we need to have separate logic for every type of group while sorting > works the same in all of them. Altering means we need to explicitly > special case forcing 1 and >1 items, and masking all items, for each > group. Again, sorting does not need to be concerned about that because > the check following it (also trivial) will catch it anyway. You don't seem to get how normalizing and constant propagation/elimination works. Basically, reordering would be: And(list) -> And( forced(list) + free(list) + masked(list) ) Or(list) -> Or( ... . ) etc. While normalizing is: And(list) -> False if False appears in a normalize(x) for x in list, True if normalize(x) for x in list is empty or all True, And(normalize(x) for x in list if != True and != False) etc. That's described in one point: Apply boolean algebra rules. What I don't like about reordering is that it is too tightly coupled to the following solving algorithm and the restricted syntax, while really, having REQUIRED_USE constraints asking you to enable a masked flag is something we ought to kill even without solving as they hide broken deps and make all our QA checks less useful. Finally, reordering, being essentially a local thing, does not have the proper behavior in a general AST: '|| ( ( a b ) c )' with 'a' and 'b' masked will be left invariant by reordering and the resulting expanded form will be rejected while constant propagation/elimination will reduce that to 'c' and be good. Hence, the reordering check cannot be used as a good input for checking for broken REQUIRED_USE: I really think things like 'vulkan? ( || ( video_cards_i965 video_cards_radeonsi ) )' should be a repoman error on stable profiles where both those video cards are masked and vulkan is not. For that, we need to support the whole PMS-defined syntax, not a reduced one. Basically, this d
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On nie, 2017-07-09 at 10:29 +0200, Ulrich Mueller wrote: > > > > > > On Sun, 09 Jul 2017, Michał Górny wrote: > > On nie, 2017-07-09 at 09:22 +0200, Ulrich Mueller wrote: > > > Second, and more important, introduction of an automatic solver > > > would inevitably lead to proliferation of REQUIRED_USE in the tree. > > > However, nothing would guarantee that the package manager on the > > > user's side is capable of solving the constraints automatically. > > > The result would be more emerge failures and asking for more > > > micro-management of flags by users. > > Think of dynamic deps. We were able to eventually contain them, and > > teach developers not to account for them even though they are still > > enabled by default, I think. > > I don't see why optional autosolving of REQUIRED_USE could not be > > contained by a policy as well. > > Then can you please confirm that the policy outlined in > https://devmanual.gentoo.org/general-concepts/use-flags/index.html#conflicting-use-flags > can stay in place indefinitely, and that your GLEP doesn't intend to > change it? The GLEP does not mention that policy at all, so it's not affected. If we decide to change it, it will be done independently of the GLEP. > > Of course, there will be some people who will violate it but it's > > not something that doesn't happen anyway right now. > > A policy that isn't enforced is useless. Say that to the people who invented USE=gtk2,gtk3 instead of USE=gtk. Oh wait... > > Are you suggesting that we introduce half-tested feature in EAPI 7, > > then spend a few years figuring out that it doesn't work as > > expected? > > No, I am suggesting that we introduce a new package manager feature in > a well defined way, so that ebuild authors can rely on it. We have a > mechanism for that, and I don't see a good reason not to follow it. > > > Because I don't see how we get it tested properly without having > > users actually test it and report the results. > > It shouldn't be necessary for the spec to specify all details of the > algorithm. It should catch the basics though in the next EAPI, like > leftmost preferred, banning empty groups, and banning USE conditionals > inside groups. > Works for me. However, the problem is whether i'll live to see the day when I can realistically use it. python-single-r1 needs this urgently. Today. Not 15 years from now when we can drop support for EAPI <=6. Presuming Gentoo will be anything but a huge pile of defunct policies and bureaucracy 15 years from now. -- Best regards, Michał Górny signature.asc Description: This is a digitally signed message part
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
> On Sun, 09 Jul 2017, Michał Górny wrote: > On nie, 2017-07-09 at 09:22 +0200, Ulrich Mueller wrote: >> Second, and more important, introduction of an automatic solver >> would inevitably lead to proliferation of REQUIRED_USE in the tree. >> However, nothing would guarantee that the package manager on the >> user's side is capable of solving the constraints automatically. >> The result would be more emerge failures and asking for more >> micro-management of flags by users. > Think of dynamic deps. We were able to eventually contain them, and > teach developers not to account for them even though they are still > enabled by default, I think. > I don't see why optional autosolving of REQUIRED_USE could not be > contained by a policy as well. Then can you please confirm that the policy outlined in https://devmanual.gentoo.org/general-concepts/use-flags/index.html#conflicting-use-flags can stay in place indefinitely, and that your GLEP doesn't intend to change it? > Of course, there will be some people who will violate it but it's > not something that doesn't happen anyway right now. A policy that isn't enforced is useless. > Are you suggesting that we introduce half-tested feature in EAPI 7, > then spend a few years figuring out that it doesn't work as > expected? No, I am suggesting that we introduce a new package manager feature in a well defined way, so that ebuild authors can rely on it. We have a mechanism for that, and I don't see a good reason not to follow it. > Because I don't see how we get it tested properly without having > users actually test it and report the results. It shouldn't be necessary for the spec to specify all details of the algorithm. It should catch the basics though in the next EAPI, like leftmost preferred, banning empty groups, and banning USE conditionals inside groups. Ulrich pgpd3g7YRU5Zz.pgp Description: PGP signature
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On sob, 2017-07-08 at 15:47 -0700, Daniel Campbell wrote:
> On 07/08/2017 03:29 PM, Michał Górny wrote:
> > On sob, 2017-07-08 at 15:21 -0700, Daniel Campbell wrote:
> > > On 07/08/2017 02:43 AM, Michał Górny wrote:
> > > > Hi, everyone.
> > > >
> > > > I think the affairs have settled enough and I've finished filling
> > > > in the pre-GLEP for REQUIRED_USE auto-enforcing. It's got all
> > > > the algorithms, rationale and separated reference implementation.
> > > >
> > > > If there are no major concerns raised, I will soon start working
> > > > on writing an optimized implementation for pkgcore/pkgcheck
> > > > and integrating the verification algos with the CI.
> > > >
> > > > The pre-GLEP for review is here:
> > > >
> > > > https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse
> > > >
> > > > TIA.
> > > >
> > >
> > > This has grown quite a bit since first recommended! Great job so far.
> > > Forgive me if I missed something, but wouldn't it be helpful to the user
> > > to let them know when automatically choosing for them? A single line in
> > > a logfile, einfo output, whatever, would be useful for people wondering
> > > how certain packages got pulled in. Users will continue to get errors if
> > > the constraints aren't met (or are wrong), but where will information go
> > > that indicates the automatic solver's choice? You and I can read an
> > > ebuild and guess from the dep spec, but what will a user look at?
> > >
> > > I searched the GLEP page for "log", "einfo", and "output" with no
> > > results. If I've missed something please let me know.
> > >
> > > Thanks for the work that's been put into this so far.
> > >
> >
> > Indeed I have entirely skipped the user output problem, and left it
> > purely for package manager's design choice. Do you really feel like we
> > need to explicitly specify it? I think it's best if package manager
> > authors decide how to best fit it into whatever output the PMs already
> > have.
> >
> >
>
> I just considered it helpful, that's all. I hadn't considered the PMS
> vs. PM devs perspective. Do we plan to support some way for users to get
> such output from Portage?
>
The original proposal suggested marking the flags with some symbol
indicating that their values were changed, and possibly even grouping
them by inferences (like 'foo => {bar}'). But I don't know if Portage
will eventually get more than the first one.
--
Best regards,
Michał Górny
signature.asc
Description: This is a digitally signed message part
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On nie, 2017-07-09 at 09:22 +0200, Ulrich Mueller wrote: > > > > > > On Sat, 08 Jul 2017, Michał Górny wrote: > > Nobody said anything about the next EAPI. The GLEP doesn't say a > > word about introducing it in a future EAPI. > > We're adding this as an optional (default off) FEATURE into Portage > > and we'll see how it works. As far as I'm concerned, we can enable > > it for all EAPIs without touching PMS at all. > > Not sure if this is a good idea. First, there is the issue that we > would have different syntax for REQUIRED_USE, a looser one defined by > PMS and a stricter one defined by your GLEP, which can cause > confusion. > > Second, and more important, introduction of an automatic solver would > inevitably lead to proliferation of REQUIRED_USE in the tree. However, > nothing would guarantee that the package manager on the user's side is > capable of solving the constraints automatically. The result would be > more emerge failures and asking for more micro-management of flags by > users. Think of dynamic deps. We were able to eventually contain them, and teach developers not to account for them even though they are still enabled by default, I think. I don't see why optional autosolving of REQUIRED_USE could not be contained by a policy as well. Of course, there will be some people who will violate it but it's not something that doesn't happen anyway right now. In fact, consider that people hit REQUIRED_USE conflicts today and have no help against them, adding the autosolver will certainly reduce the overall 'conflict hit rate' of our users, even if more conflicts are introduced by the developers not following the policy. See all the RequiredUseDefaults reports in [1]. And that's purely for the profile-set defaults, i.e. packages that fail to emerge out-of-the- box. > > In fact, the GLEP points out that the PMS does not specifically > > define how PMs are supposed to deal with ensuring that REQUIRED_USE > > is satisfied. Failing with poor error messages is just established > > historical Portage behavior. But if we get good test results and > > majority agreement, I see no reason why we couldn't start enabling > > it by default and eventually relying on it. > > After all, it wouldn't be the first non-PMS extension that we accept > > for user convenience yet do not require strictly. > > See above. I fear it would cause pain for users whose PM doesn't > implement the feature. So do broken executables for PMs that do not preserve-libs. This is not something we can cover 100%. We can aim to make it work automatically for the most, and be solvable for the rest. > > Of course, if you think it should be made obligatory or at least > > accounted for in a future EAPI, I have no problem with that. Ciaran > > might, however. > > That is exactly what EAPI was invented for. Ebuild authors can only > rely on package manager support on users' side if the feature is > introduced with a new EAPI. Leaving the policy specified in [1] in > place forever is no good alternative, because then the full potential > of the automatic solver could not be exploited in ebuilds. (Also, how > would we enforce the devmanual policy?) Are you suggesting that we introduce half-tested feature in EAPI 7, then spend a few years figuring out that it doesn't work as expected? Because I don't see how we get it tested properly without having users actually test it and report the results. Or are you suggesting that we go through those 1 ebuilds and test every flag combination by hand? And then, we figure out that with the new feature the developers start writing different REQUIRED_USE constraints and find bugs. [1]:https://qa-reports.gentoo.org/output/gentoo-ci/output.html -- Best regards, Michał Górny signature.asc Description: This is a digitally signed message part
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
> On Sat, 08 Jul 2017, Michał Górny wrote: > Nobody said anything about the next EAPI. The GLEP doesn't say a > word about introducing it in a future EAPI. > We're adding this as an optional (default off) FEATURE into Portage > and we'll see how it works. As far as I'm concerned, we can enable > it for all EAPIs without touching PMS at all. Not sure if this is a good idea. First, there is the issue that we would have different syntax for REQUIRED_USE, a looser one defined by PMS and a stricter one defined by your GLEP, which can cause confusion. Second, and more important, introduction of an automatic solver would inevitably lead to proliferation of REQUIRED_USE in the tree. However, nothing would guarantee that the package manager on the user's side is capable of solving the constraints automatically. The result would be more emerge failures and asking for more micro-management of flags by users. Also, I believe that with an automatic solver, we would want to change the policy defined in the devmanual which says that REQUIRED_USE should be used sparingly [1]? When would we do this, if the feature isn't connected to an EAPI? After a long enough waiting period? Welcome back to pre-EAPI-0 times. > In fact, the GLEP points out that the PMS does not specifically > define how PMs are supposed to deal with ensuring that REQUIRED_USE > is satisfied. Failing with poor error messages is just established > historical Portage behavior. But if we get good test results and > majority agreement, I see no reason why we couldn't start enabling > it by default and eventually relying on it. > After all, it wouldn't be the first non-PMS extension that we accept > for user convenience yet do not require strictly. See above. I fear it would cause pain for users whose PM doesn't implement the feature. > Of course, if you think it should be made obligatory or at least > accounted for in a future EAPI, I have no problem with that. Ciaran > might, however. That is exactly what EAPI was invented for. Ebuild authors can only rely on package manager support on users' side if the feature is introduced with a new EAPI. Leaving the policy specified in [1] in place forever is no good alternative, because then the full potential of the automatic solver could not be exploited in ebuilds. (Also, how would we enforce the devmanual policy?) Ulrich [1] https://devmanual.gentoo.org/general-concepts/use-flags/index.html#conflicting-use-flags pgpAaknfTFtPd.pgp Description: PGP signature
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On 07/08/2017 03:29 PM, Michał Górny wrote: > On sob, 2017-07-08 at 15:21 -0700, Daniel Campbell wrote: >> On 07/08/2017 02:43 AM, Michał Górny wrote: >>> Hi, everyone. >>> >>> I think the affairs have settled enough and I've finished filling >>> in the pre-GLEP for REQUIRED_USE auto-enforcing. It's got all >>> the algorithms, rationale and separated reference implementation. >>> >>> If there are no major concerns raised, I will soon start working >>> on writing an optimized implementation for pkgcore/pkgcheck >>> and integrating the verification algos with the CI. >>> >>> The pre-GLEP for review is here: >>> >>> https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse >>> >>> TIA. >>> >> >> This has grown quite a bit since first recommended! Great job so far. >> Forgive me if I missed something, but wouldn't it be helpful to the user >> to let them know when automatically choosing for them? A single line in >> a logfile, einfo output, whatever, would be useful for people wondering >> how certain packages got pulled in. Users will continue to get errors if >> the constraints aren't met (or are wrong), but where will information go >> that indicates the automatic solver's choice? You and I can read an >> ebuild and guess from the dep spec, but what will a user look at? >> >> I searched the GLEP page for "log", "einfo", and "output" with no >> results. If I've missed something please let me know. >> >> Thanks for the work that's been put into this so far. >> > > Indeed I have entirely skipped the user output problem, and left it > purely for package manager's design choice. Do you really feel like we > need to explicitly specify it? I think it's best if package manager > authors decide how to best fit it into whatever output the PMs already > have. > > I just considered it helpful, that's all. I hadn't considered the PMS vs. PM devs perspective. Do we plan to support some way for users to get such output from Portage? Thanks for clarifying. It does make more sense to leave it to PM devs. -- Daniel Campbell - Gentoo Developer OpenPGP Key: 0x1EA055D6 @ hkp://keys.gnupg.net fpr: AE03 9064 AE00 053C 270C 1DE4 6F7A 9091 1EA0 55D6 signature.asc Description: OpenPGP digital signature
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On sob, 2017-07-08 at 15:21 -0700, Daniel Campbell wrote: > On 07/08/2017 02:43 AM, Michał Górny wrote: > > Hi, everyone. > > > > I think the affairs have settled enough and I've finished filling > > in the pre-GLEP for REQUIRED_USE auto-enforcing. It's got all > > the algorithms, rationale and separated reference implementation. > > > > If there are no major concerns raised, I will soon start working > > on writing an optimized implementation for pkgcore/pkgcheck > > and integrating the verification algos with the CI. > > > > The pre-GLEP for review is here: > > > > https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse > > > > TIA. > > > > This has grown quite a bit since first recommended! Great job so far. > Forgive me if I missed something, but wouldn't it be helpful to the user > to let them know when automatically choosing for them? A single line in > a logfile, einfo output, whatever, would be useful for people wondering > how certain packages got pulled in. Users will continue to get errors if > the constraints aren't met (or are wrong), but where will information go > that indicates the automatic solver's choice? You and I can read an > ebuild and guess from the dep spec, but what will a user look at? > > I searched the GLEP page for "log", "einfo", and "output" with no > results. If I've missed something please let me know. > > Thanks for the work that's been put into this so far. > Indeed I have entirely skipped the user output problem, and left it purely for package manager's design choice. Do you really feel like we need to explicitly specify it? I think it's best if package manager authors decide how to best fit it into whatever output the PMs already have. -- Best regards, Michał Górny signature.asc Description: This is a digitally signed message part
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On 07/08/2017 02:43 AM, Michał Górny wrote: > Hi, everyone. > > I think the affairs have settled enough and I've finished filling > in the pre-GLEP for REQUIRED_USE auto-enforcing. It's got all > the algorithms, rationale and separated reference implementation. > > If there are no major concerns raised, I will soon start working > on writing an optimized implementation for pkgcore/pkgcheck > and integrating the verification algos with the CI. > > The pre-GLEP for review is here: > > https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse > > TIA. > This has grown quite a bit since first recommended! Great job so far. Forgive me if I missed something, but wouldn't it be helpful to the user to let them know when automatically choosing for them? A single line in a logfile, einfo output, whatever, would be useful for people wondering how certain packages got pulled in. Users will continue to get errors if the constraints aren't met (or are wrong), but where will information go that indicates the automatic solver's choice? You and I can read an ebuild and guess from the dep spec, but what will a user look at? I searched the GLEP page for "log", "einfo", and "output" with no results. If I've missed something please let me know. Thanks for the work that's been put into this so far. ~zlg -- Daniel Campbell - Gentoo Developer OpenPGP Key: 0x1EA055D6 @ hkp://keys.gnupg.net fpr: AE03 9064 AE00 053C 270C 1DE4 6F7A 9091 1EA0 55D6 signature.asc Description: OpenPGP digital signature
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On sob, 2017-07-08 at 23:56 +0200, Michał Górny wrote: > On sob, 2017-07-08 at 22:34 +0200, Alexis Ballier wrote: > > Unless I'm missing something, rationale seems more about cases rejected > > by the restricted syntax. Numbers I'm talking about is the # of rejected > > constraints vs accepted (and assumed solvable) ones. > > I'll crunch some fresh numbers based on today's repository. Ebuild counts follow. count % of requse % of total Total ebuilds:38344 --- -- Ebuilds w/ REQUIRED_USE: 9945 --- -- Good REQUIRED_USE: 9727 97.8% 25.37% Invalid syntax: 160.2%0.04% Conflicting enforcements:490.5%0.13% Requiring >1 pass: 1531.5%0.40% So realstically saying, right now we're talking about 'rejecting' 0.04% of ebuilds, conditionally failing for 0.13% of them (i.e. with bad flag combinations) and conditionally requiring >1 iteration for 0.4% of them. -- Best regards, Michał Górny signature.asc Description: This is a digitally signed message part
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On 07/08/2017 11:31 PM, Michał Górny wrote: > Nobody said anything about the next EAPI. The GLEP doesn't say a word > about introducing it in a future EAPI. > > We're adding this as an optional (default off) FEATURE into Portage > and we'll see how it works. As far as I'm concerned, we can enable it > for all EAPIs without touching PMS at all. With that in mind, does it really need a GLEP? Isn't this something that can be done within the package manager as a feature anyways without mandating changes? If anything it seems like it'd be an informational GLEP and not a standards track if going down that route. -- Kristian Fiskerstrand OpenPGP keyblock reachable at hkp://pool.sks-keyservers.net fpr:94CB AFDD 3034 5109 5618 35AA 0B7F 8B60 E3ED FAE3 signature.asc Description: OpenPGP digital signature
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On sob, 2017-07-08 at 22:34 +0200, Alexis Ballier wrote: > On Sat, 08 Jul 2017 20:44:24 +0200 > Michał Górny wrote: > > > On sob, 2017-07-08 at 16:12 +0200, Alexis Ballier wrote: > > > On Sat, 08 Jul 2017 11:43:39 +0200 > > > Michał Górny wrote: > > > > > > > Hi, everyone. > > > > > > > > I think the affairs have settled enough and I've finished filling > > > > in the pre-GLEP for REQUIRED_USE auto-enforcing. It's got all > > > > the algorithms, rationale and separated reference implementation. > > > > > > > > If there are no major concerns raised, I will soon start working > > > > on writing an optimized implementation for pkgcore/pkgcheck > > > > and integrating the verification algos with the CI. > > > > > > > > The pre-GLEP for review is here: > > > > > > > > https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse > > > > > > > > > Constraint group reordering algorithm > > > > > > I really think we should only consider REQUIRED_USE with > > > forced/masked useflags instantiated there. And ban (in repoman) > > > REQUIRED_USE that contain some "False": "a? ( b )" with 'a' free > > > and 'b' masked is perfectly ok now but it hides a serious problem > > > in the package/profile. Instantiating this would give: "a? ( False > > > )" and be an error just like we have depend.bad & co. This is > > > independent of auto solving or not, it's already wrong. > > > > As I've already explained you multiple times, this obtains *exactly > > the same* effect. However, it's much simpler when it's done like this > > because it makes it possible to reuse the already defined algorithms > > instead of having to precisely define how to preprocess REQUIRED_USE > > for this and cover all the corner cases. > > Simpler??? I don't think so. What I wrote clearly pinpoints that: > When you'll write the algorithm for "Verifying that the constraints do > not alter immutable flags" you'll notice this is exactly that and can > be put as a preprocessing step and then you can drop all the corner > cases considerations for immutable flags. I never understood why you're > insisting that much on immutables: they're really not natural, not > simple, not standard, and carrying them all over seems to be a burden > to me. I wrote the algorithms, and they're simple. This specific check is the combination of three simple steps: a. reordering the groups based on immutables, b. transforming the AST into flat form, c. verifying each flat constraint. The first step is trivial -- it's basically 'move true to front, false to back'. The second step is more complex but it's needed anyway, and quite well-defined, especially with the assumption that all the groups always have at least one flag inside. The third step is trivial again because it's just checking the conditions and constraints against a list. The alternative to reordering is altering the groups. Altering means we need to have separate logic for every type of group while sorting works the same in all of them. Altering means we need to explicitly special case forcing 1 and >1 items, and masking all items, for each group. Again, sorting does not need to be concerned about that because the check following it (also trivial) will catch it anyway. Of course, you could say that you will get a little better error message, like 'all flags inside || are masked' instead of '!b -> a' will alter immutable flag. But that's purely an implementation detail. It's not worth making the reference algorithms longer. > > > Reordering is a dangerous path as we've already seen since it can > > > create unexpected loops for the solver. > > > > Freeform reordering is dangerous, and I've removed that already. > > Reordering restricted to immutables can not cause any issues that any > > other solution wouldn't cause. > > You're very likely right there. Any proof? Esp. any proof that the > checker still guarantees the existence of a solution in all cases? > I'm not asking for a formal proof, but simply a bit more details than > just an assertion saying it's fine. The case for checker is just the same as with any other kind of immutability processing. We need to run the reordering, transform and verification separately for every possible combination of immutable flags. The reordering explicitly alters the results of the transform, and with the trivial implication form of the flattened constraints the verification stage checks will find any problems that may arise from it, just like they would find any problem from doing a similar thing verbatim. > > > > Working on instantiated REQUIRED_USE constraints would probably > > > simplify quite a bit your GLEP too: you already have the "Verifying > > > that the constraints do not alter immutable flags" part that roughly > > > does the same thing as instantiating, except if you assume it's > > > already true you can skip the reordering. > > > > Except that the reordering can be described in 2 points, and so can be > > the immutability verification. P
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On sob, 2017-07-08 at 20:58 +0200, Ulrich Mueller wrote: > > > > > > On Sat, 08 Jul 2017, Michał Górny wrote: > > On sob, 2017-07-08 at 12:26 +0200, Ulrich Mueller wrote: > > > Section "Processing algorithm": > > > > > > > 2. Check whether the REQUIRED_USE constraint matches restrictions > > > > set in #Restrictions on REQUIRED_USE format. If it does not, report > > > > a REQUIRED_USE mismatch and abort. > > > > > > Why is this needed? This case should never occur if the REQUIRED_USE > > > syntax doesn't allow it. > > The syntax is restricted from the one allowed by the PMS. The > > algorithm doesn't cover the weird deep nesting cases. Unless we want > > to retroactively change PMS to disallow them as well, the spec needs > > to clearly establish the acceptable input for the algorithm > > presented. > > Sorry, but that makes no sense. Why would we introduce automatic > solving with the next EAPI, but at the same time not restrict > REQUIRED_USE syntax to the one the solver can handle? > Nobody said anything about the next EAPI. The GLEP doesn't say a word about introducing it in a future EAPI. We're adding this as an optional (default off) FEATURE into Portage and we'll see how it works. As far as I'm concerned, we can enable it for all EAPIs without touching PMS at all. In fact, the GLEP points out that the PMS does not specifically define how PMs are supposed to deal with ensuring that REQUIRED_USE is satisfied. Failing with poor error messages is just established historical Portage behavior. But if we get good test results and majority agreement, I see no reason why we couldn't start enabling it by default and eventually relying on it. After all, it wouldn't be the first non-PMS extension that we accept for user convenience yet do not require strictly. Of course, if you think it should be made obligatory or at least accounted for in a future EAPI, I have no problem with that. Ciaran might, however. -- Best regards, Michał Górny signature.asc Description: This is a digitally signed message part
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On Sat, 08 Jul 2017 20:44:24 +0200 Michał Górny wrote: > On sob, 2017-07-08 at 16:12 +0200, Alexis Ballier wrote: > > On Sat, 08 Jul 2017 11:43:39 +0200 > > Michał Górny wrote: > > > > > Hi, everyone. > > > > > > I think the affairs have settled enough and I've finished filling > > > in the pre-GLEP for REQUIRED_USE auto-enforcing. It's got all > > > the algorithms, rationale and separated reference implementation. > > > > > > If there are no major concerns raised, I will soon start working > > > on writing an optimized implementation for pkgcore/pkgcheck > > > and integrating the verification algos with the CI. > > > > > > The pre-GLEP for review is here: > > > > > > https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse > > > > > > Constraint group reordering algorithm > > > > I really think we should only consider REQUIRED_USE with > > forced/masked useflags instantiated there. And ban (in repoman) > > REQUIRED_USE that contain some "False": "a? ( b )" with 'a' free > > and 'b' masked is perfectly ok now but it hides a serious problem > > in the package/profile. Instantiating this would give: "a? ( False > > )" and be an error just like we have depend.bad & co. This is > > independent of auto solving or not, it's already wrong. > > As I've already explained you multiple times, this obtains *exactly > the same* effect. However, it's much simpler when it's done like this > because it makes it possible to reuse the already defined algorithms > instead of having to precisely define how to preprocess REQUIRED_USE > for this and cover all the corner cases. Simpler??? I don't think so. What I wrote clearly pinpoints that: When you'll write the algorithm for "Verifying that the constraints do not alter immutable flags" you'll notice this is exactly that and can be put as a preprocessing step and then you can drop all the corner cases considerations for immutable flags. I never understood why you're insisting that much on immutables: they're really not natural, not simple, not standard, and carrying them all over seems to be a burden to me. > > Reordering is a dangerous path as we've already seen since it can > > create unexpected loops for the solver. > > Freeform reordering is dangerous, and I've removed that already. > Reordering restricted to immutables can not cause any issues that any > other solution wouldn't cause. You're very likely right there. Any proof? Esp. any proof that the checker still guarantees the existence of a solution in all cases? I'm not asking for a formal proof, but simply a bit more details than just an assertion saying it's fine. > > Working on instantiated REQUIRED_USE constraints would probably > > simplify quite a bit your GLEP too: you already have the "Verifying > > that the constraints do not alter immutable flags" part that roughly > > does the same thing as instantiating, except if you assume it's > > already true you can skip the reordering. > > Except that the reordering can be described in 2 points, and so can be > the immutability verification. Please prove that you can provide > a simpler explanation that doesn't fail in any of the corner cases. Except reordering is an invention and immutable checking is simply applying boolean logic rules to your implication and check that no "False" can appear. You can simply start by applying boolean logic and forget about reordering. > > Concept for transforming REQUIRED_USE into implications > > > > Ok, now I probably understand better the concept of common prefix. > > I'm definitely biased here, but I would feel better with a more > > recursive presentation of it. Assume we have 'validate(list of > > clauses)'; basically, the common prefix idea is that for an > > implication 'foo? ( consequences = list of clauses )' you first > > validate the consequences as if it were a REQUIRED_USE (so that the > > subtree rooted at foo is not self-conflicting) and then consider > > the whole thing as a clause. The idea would then be to have similar > > checks as to what you've written but working on trees (ASTs) > > instead of flattened clauses. This would avoid having to deal with > > unique identities (these would come for free) and IMHO would be > > easier to understand. I'm not sure how to do this though, I'll ping > > you when I have some idea. > > Well, the problem of common prefix is quite complex, and I'm not even > sure if it's really worth more consideration. After all, we're > prettych much talking about doing: > > a? ( !a ... ) > > which has extremely low usability and even lower likeness of > occurring. Hmm. I think you came up with more valid cases. Can't remember a precise one though. > > One big advantage of working on ASTs is that it becomes trivial to > > suggest a proper reordering. > > Reordering is never a trivial problem. Unless I'm missing something, > it is technically possible that a 'reordering' will actually require > a sub- item being moved out of the containing group. Not
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On Sat, 8 Jul 2017 21:05:57 +0200 Ulrich Mueller wrote: > > On Sat, 8 Jul 2017, Ciaran McCreesh wrote: > > > On Sat, 8 Jul 2017 16:39:29 +0200 > > Alexis Ballier wrote: > >> Indeed, makes sense. Would it also make sense to have some more > >> logical meaning in a future EAPI ? I mean, in every context I've > >> ever seen, applying a rule to the empty set is the neutral of that > >> rule, so that it preserves associativity. > >> That'd mean: || ( ) is false, && ( ) is true, ^^ ( ) is false, > > I have no strong opinion about this. Is it worth the effort of > changing the spec? > > >> ?? ( ) is false. > > I think ?? ( ) aka at-most-one-of should be true if empty. Maybe; this one is annoying I think since it is not associative per definition: ?? ( true ?? ( false false ) ) -> ?? ( true true ) -> false ?? ( ?? ( true false ) false ) -> ?? ( true false) -> true > > The sensible thing to do is ban it, and additionally ban use? ( ) > > inside || and ^^ (if we've not done that already...). > > Right. We have to check if this will break any eclass generated > dependencies, though. That's probably the best course of action indeed. Alexis.
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
> On Sat, 8 Jul 2017, Ciaran McCreesh wrote: > On Sat, 8 Jul 2017 16:39:29 +0200 > Alexis Ballier wrote: >> Indeed, makes sense. Would it also make sense to have some more >> logical meaning in a future EAPI ? I mean, in every context I've ever >> seen, applying a rule to the empty set is the neutral of that rule, >> so that it preserves associativity. >> That'd mean: || ( ) is false, && ( ) is true, ^^ ( ) is false, I have no strong opinion about this. Is it worth the effort of changing the spec? >> ?? ( ) is false. I think ?? ( ) aka at-most-one-of should be true if empty. > The sensible thing to do is ban it, and additionally ban use? ( ) > inside || and ^^ (if we've not done that already...). Right. We have to check if this will break any eclass generated dependencies, though. Ulrich pgp1k8IEIi3sC.pgp Description: PGP signature
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
> On Sat, 08 Jul 2017, Michał Górny wrote: > On sob, 2017-07-08 at 12:26 +0200, Ulrich Mueller wrote: >> Section "Processing algorithm": >> >> > 2. Check whether the REQUIRED_USE constraint matches restrictions >> > set in #Restrictions on REQUIRED_USE format. If it does not, report >> > a REQUIRED_USE mismatch and abort. >> >> Why is this needed? This case should never occur if the REQUIRED_USE >> syntax doesn't allow it. > The syntax is restricted from the one allowed by the PMS. The > algorithm doesn't cover the weird deep nesting cases. Unless we want > to retroactively change PMS to disallow them as well, the spec needs > to clearly establish the acceptable input for the algorithm > presented. Sorry, but that makes no sense. Why would we introduce automatic solving with the next EAPI, but at the same time not restrict REQUIRED_USE syntax to the one the solver can handle? Ulrich pgp7n76dDaKcN.pgp Description: PGP signature
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On sob, 2017-07-08 at 16:12 +0200, Alexis Ballier wrote: > On Sat, 08 Jul 2017 11:43:39 +0200 > Michał Górny wrote: > > > Hi, everyone. > > > > I think the affairs have settled enough and I've finished filling > > in the pre-GLEP for REQUIRED_USE auto-enforcing. It's got all > > the algorithms, rationale and separated reference implementation. > > > > If there are no major concerns raised, I will soon start working > > on writing an optimized implementation for pkgcore/pkgcheck > > and integrating the verification algos with the CI. > > > > The pre-GLEP for review is here: > > > > https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse > > > Constraint group reordering algorithm > > I really think we should only consider REQUIRED_USE with forced/masked > useflags instantiated there. And ban (in repoman) REQUIRED_USE that > contain some "False": "a? ( b )" with 'a' free and 'b' masked is > perfectly ok now but it hides a serious problem in the package/profile. > Instantiating this would give: "a? ( False )" and be an error > just like we have depend.bad & co. This is independent of auto > solving or not, it's already wrong. As I've already explained you multiple times, this obtains *exactly the same* effect. However, it's much simpler when it's done like this because it makes it possible to reuse the already defined algorithms instead of having to precisely define how to preprocess REQUIRED_USE for this and cover all the corner cases. > Reordering is a dangerous path as we've already seen since it can > create unexpected loops for the solver. Freeform reordering is dangerous, and I've removed that already. Reordering restricted to immutables can not cause any issues that any other solution wouldn't cause. > Working on instantiated REQUIRED_USE constraints would probably > simplify quite a bit your GLEP too: you already have the "Verifying > that the constraints do not alter immutable flags" part that roughly > does the same thing as instantiating, except if you assume it's already > true you can skip the reordering. Except that the reordering can be described in 2 points, and so can be the immutability verification. Please prove that you can provide a simpler explanation that doesn't fail in any of the corner cases. > Concept for transforming REQUIRED_USE into implications > > Ok, now I probably understand better the concept of common prefix. I'm > definitely biased here, but I would feel better with a more recursive > presentation of it. Assume we have 'validate(list of clauses)'; > basically, the common prefix idea is that for an implication 'foo? > ( consequences = list of clauses )' you first validate the consequences > as if it were a REQUIRED_USE (so that the subtree rooted at foo is > not self-conflicting) and then consider the whole thing as a clause. > The idea would then be to have similar checks as to what you've written > but working on trees (ASTs) instead of flattened clauses. This would > avoid having to deal with unique identities (these would come for free) > and IMHO would be easier to understand. > I'm not sure how to do this though, I'll ping you when I have some idea. Well, the problem of common prefix is quite complex, and I'm not even sure if it's really worth more consideration. After all, we're prettych much talking about doing: a? ( !a ... ) which has extremely low usability and even lower likeness of occurring. > One big advantage of working on ASTs is that it becomes trivial to > suggest a proper reordering. Reordering is never a trivial problem. Unless I'm missing something, it is technically possible that a 'reordering' will actually require a sub- item being moved out of the containing group. And to be honest, I find the output of the verification script in this regard quite useful. That is, it saying 'X affects Y, so it needs to go before it' is quite clear to me. I don't think most developers would actually need to script to pinpoint a specific location for every single constraint. > --- > > Restrictions on REQUIRED_USE format > > I still fail to see the point here. One can simply apply the rewriting > you suggest below and be done with it. Rationale is not very convincing > to me: > > - avoiding unpredictable results of automatic flag adjustments: > A deterministic algorithm is, by definition, predictable. s/unpredictable/surprising/? The goal is for it do something that the developer *not reading the spec* could reasonably predict happening. > - improving readability of REQUIRED_USE constraints: > No need for a restriction for that. If people want to shoot > themselves in the foot, it is not a PMS problem. I see that > like proposing death penalty for those who commit suicide :) This is not PMS. This is a GLEP which serves both the purpose of a technical specification with extended rationale and a policy document. > - keeping the specification and implementation relatively simple: > You already define everythi
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On sob, 2017-07-08 at 12:26 +0200, Ulrich Mueller wrote: > > > > > > On Sat, 08 Jul 2017, Michał Górny wrote: > > The pre-GLEP for review is here: > > https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse > > On first glance: > > Section "Processing algorithm": > > > 2. Check whether the REQUIRED_USE constraint matches restrictions > > set in #Restrictions on REQUIRED_USE format. If it does not, report > > a REQUIRED_USE mismatch and abort. > > Why is this needed? This case should never occur if the REQUIRED_USE > syntax doesn't allow it. The syntax is restricted from the one allowed by the PMS. The algorithm doesn't cover the weird deep nesting cases. Unless we want to retroactively change PMS to disallow them as well, the spec needs to clearly establish the acceptable input for the algorithm presented. Of course, you are free to omit this step if you implement algorithm that covers all the PMS-defined cases. However, this goes beyond the basic scope which this GLEP is concerned about. > Section "REQUIRED_USE verification algorithm": > > > * An any-of group (||) evaluates to true if at least one of the > > items in it evaluates to true. > > * An exactly-one-of group (^^) evaluates to true if exactly one of > > the items in it evaluates to true, and all the remaining items > > evaluate to false. > > * An at-most-one-of group (??) evaluates to true if at most one of > > the items in it evaluates to true. > > It should be added that any empty group (|| or ^^ or ??) evalutates to > true, because that's what PMS specifies: > https://projects.gentoo.org/pms/6/pms.html#x1-780008.2 > Indeed you are correct. However, considering what Ciaran wrote it might be a reasonable alternative to ban them as well. I'm going to wait a while and see what others say. -- Best regards, Michał Górny signature.asc Description: This is a digitally signed message part
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On sob, 2017-07-08 at 18:58 +0100, Ciaran McCreesh wrote: > On Sat, 8 Jul 2017 16:39:29 +0200 > Alexis Ballier wrote: > > > As much as I hate the weird || ( use ? ( ) ) and empty block rules, > > > it would be worse to have them apply in some situations but not > > > others. > > > > Indeed, makes sense. Would it also make sense to have some more > > logical meaning in a future EAPI ? I mean, in every context I've ever > > seen, applying a rule to the empty set is the neutral of that rule, > > so that it preserves associativity. > > That'd mean: || ( ) is false, && ( ) is true, ^^ ( ) is false, ?? ( ) > > is false. > > The sensible thing to do is ban it, and additionally ban use? ( ) > inside || and ^^ (if we've not done that already...). > My GLEP bans the latter. As someone already pointed out, it didn't concern the case of empty groups, so I can either ban them or describe them. -- Best regards, Michał Górny signature.asc Description: This is a digitally signed message part
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On Sat, 8 Jul 2017 16:39:29 +0200 Alexis Ballier wrote: > > As much as I hate the weird || ( use ? ( ) ) and empty block rules, > > it would be worse to have them apply in some situations but not > > others. > > Indeed, makes sense. Would it also make sense to have some more > logical meaning in a future EAPI ? I mean, in every context I've ever > seen, applying a rule to the empty set is the neutral of that rule, > so that it preserves associativity. > That'd mean: || ( ) is false, && ( ) is true, ^^ ( ) is false, ?? ( ) > is false. The sensible thing to do is ban it, and additionally ban use? ( ) inside || and ^^ (if we've not done that already...). -- Ciaran McCreesh
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On Sat, 8 Jul 2017 15:23:39 +0100 Ciaran McCreesh wrote: > On Sat, 8 Jul 2017 16:14:09 +0200 > Alexis Ballier wrote: > > On Sat, 8 Jul 2017 13:01:39 +0100 > > Ciaran McCreesh wrote: > > > On Sat, 8 Jul 2017 13:49:56 +0200 > > > Alexis Ballier wrote: > > > > On Sat, 8 Jul 2017 12:26:59 +0200 > > > > Ulrich Mueller wrote: > > > > > | * An any-of group (||) evaluates to true if at least one of > > > > > the | items in it evaluates to true. > > > > > | * An exactly-one-of group (^^) evaluates to true if exactly > > > > > one of | the items in it evaluates to true, and all the > > > > > remaining items | evaluate to false. > > > > > | * An at-most-one-of group (??) evaluates to true if at most > > > > > one of | the items in it evaluates to true. > > > > > > > > > > It should be added that any empty group (|| or ^^ or ??) > > > > > evalutates to true, because that's what PMS specifies: > > > > > https://projects.gentoo.org/pms/6/pms.html#x1-780008.2 > > > > > > > > A bit OT, but that is *definitely* counter intuitive. What's the > > > > rationale and usecase behind this ? > > > > > > Annoying special cases like || ( foo? ( ... ) bar? ( ... ) ) . The > > > original reason was that old versions of Portage would simply > > > remove unmet "flag? ( )" blocks internally. It was kept in EAPI 0 > > > because stuff in the tree used it back then. > > > > Wasn't REQUIRED_USE something completely new with no prior usage in > > EAPI 3 ? > > Yes, but the spec defines dependency-like structures and their > meanings once and consistently, rather than all over the place and > inconsistently. > > As much as I hate the weird || ( use ? ( ) ) and empty block rules, it > would be worse to have them apply in some situations but not others. Indeed, makes sense. Would it also make sense to have some more logical meaning in a future EAPI ? I mean, in every context I've ever seen, applying a rule to the empty set is the neutral of that rule, so that it preserves associativity. That'd mean: || ( ) is false, && ( ) is true, ^^ ( ) is false, ?? ( ) is false. Alexis.
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On Sat, 8 Jul 2017 16:14:09 +0200 Alexis Ballier wrote: > On Sat, 8 Jul 2017 13:01:39 +0100 > Ciaran McCreesh wrote: > > On Sat, 8 Jul 2017 13:49:56 +0200 > > Alexis Ballier wrote: > > > On Sat, 8 Jul 2017 12:26:59 +0200 > > > Ulrich Mueller wrote: > > > > | * An any-of group (||) evaluates to true if at least one of > > > > the | items in it evaluates to true. > > > > | * An exactly-one-of group (^^) evaluates to true if exactly > > > > one of | the items in it evaluates to true, and all the > > > > remaining items | evaluate to false. > > > > | * An at-most-one-of group (??) evaluates to true if at most > > > > one of | the items in it evaluates to true. > > > > > > > > It should be added that any empty group (|| or ^^ or ??) > > > > evalutates to true, because that's what PMS specifies: > > > > https://projects.gentoo.org/pms/6/pms.html#x1-780008.2 > > > > > > A bit OT, but that is *definitely* counter intuitive. What's the > > > rationale and usecase behind this ? > > > > Annoying special cases like || ( foo? ( ... ) bar? ( ... ) ) . The > > original reason was that old versions of Portage would simply remove > > unmet "flag? ( )" blocks internally. It was kept in EAPI 0 because > > stuff in the tree used it back then. > > Wasn't REQUIRED_USE something completely new with no prior usage in > EAPI 3 ? Yes, but the spec defines dependency-like structures and their meanings once and consistently, rather than all over the place and inconsistently. As much as I hate the weird || ( use ? ( ) ) and empty block rules, it would be worse to have them apply in some situations but not others. -- Ciaran McCreesh
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On Sat, 8 Jul 2017 13:01:39 +0100 Ciaran McCreesh wrote: > On Sat, 8 Jul 2017 13:49:56 +0200 > Alexis Ballier wrote: > > On Sat, 8 Jul 2017 12:26:59 +0200 > > Ulrich Mueller wrote: > > > | * An any-of group (||) evaluates to true if at least one of the > > > | items in it evaluates to true. > > > | * An exactly-one-of group (^^) evaluates to true if exactly one > > > of | the items in it evaluates to true, and all the remaining > > > items | evaluate to false. > > > | * An at-most-one-of group (??) evaluates to true if at most one > > > of | the items in it evaluates to true. > > > > > > It should be added that any empty group (|| or ^^ or ??) > > > evalutates to true, because that's what PMS specifies: > > > https://projects.gentoo.org/pms/6/pms.html#x1-780008.2 > > > > A bit OT, but that is *definitely* counter intuitive. What's the > > rationale and usecase behind this ? > > Annoying special cases like || ( foo? ( ... ) bar? ( ... ) ) . The > original reason was that old versions of Portage would simply remove > unmet "flag? ( )" blocks internally. It was kept in EAPI 0 because > stuff in the tree used it back then. > Wasn't REQUIRED_USE something completely new with no prior usage in EAPI 3 ?
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On Sat, 08 Jul 2017 11:43:39 +0200 Michał Górny wrote: > Hi, everyone. > > I think the affairs have settled enough and I've finished filling > in the pre-GLEP for REQUIRED_USE auto-enforcing. It's got all > the algorithms, rationale and separated reference implementation. > > If there are no major concerns raised, I will soon start working > on writing an optimized implementation for pkgcore/pkgcheck > and integrating the verification algos with the CI. > > The pre-GLEP for review is here: > > https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse Constraint group reordering algorithm I really think we should only consider REQUIRED_USE with forced/masked useflags instantiated there. And ban (in repoman) REQUIRED_USE that contain some "False": "a? ( b )" with 'a' free and 'b' masked is perfectly ok now but it hides a serious problem in the package/profile. Instantiating this would give: "a? ( False )" and be an error just like we have depend.bad & co. This is independent of auto solving or not, it's already wrong. Reordering is a dangerous path as we've already seen since it can create unexpected loops for the solver. Working on instantiated REQUIRED_USE constraints would probably simplify quite a bit your GLEP too: you already have the "Verifying that the constraints do not alter immutable flags" part that roughly does the same thing as instantiating, except if you assume it's already true you can skip the reordering. Concept for transforming REQUIRED_USE into implications Ok, now I probably understand better the concept of common prefix. I'm definitely biased here, but I would feel better with a more recursive presentation of it. Assume we have 'validate(list of clauses)'; basically, the common prefix idea is that for an implication 'foo? ( consequences = list of clauses )' you first validate the consequences as if it were a REQUIRED_USE (so that the subtree rooted at foo is not self-conflicting) and then consider the whole thing as a clause. The idea would then be to have similar checks as to what you've written but working on trees (ASTs) instead of flattened clauses. This would avoid having to deal with unique identities (these would come for free) and IMHO would be easier to understand. I'm not sure how to do this though, I'll ping you when I have some idea. One big advantage of working on ASTs is that it becomes trivial to suggest a proper reordering. --- Restrictions on REQUIRED_USE format I still fail to see the point here. One can simply apply the rewriting you suggest below and be done with it. Rationale is not very convincing to me: - avoiding unpredictable results of automatic flag adjustments: A deterministic algorithm is, by definition, predictable. - improving readability of REQUIRED_USE constraints: No need for a restriction for that. If people want to shoot themselves in the foot, it is not a PMS problem. I see that like proposing death penalty for those who commit suicide :) - keeping the specification and implementation relatively simple: You already define everything for working without restriction. Plus, unlimited implication nesting has the same complexity. --- Do you have numbers on the checker run on all inputs from gentoo-x86 ? Since we're dealing with heuristics those are particularly important to validate we're not rejecting too many constructs. Alexis.
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On Sat, 8 Jul 2017 13:49:56 +0200 Alexis Ballier wrote: > On Sat, 8 Jul 2017 12:26:59 +0200 > Ulrich Mueller wrote: > > | * An any-of group (||) evaluates to true if at least one of the > > | items in it evaluates to true. > > | * An exactly-one-of group (^^) evaluates to true if exactly one of > > | the items in it evaluates to true, and all the remaining items > > | evaluate to false. > > | * An at-most-one-of group (??) evaluates to true if at most one of > > | the items in it evaluates to true. > > > > It should be added that any empty group (|| or ^^ or ??) evalutates > > to true, because that's what PMS specifies: > > https://projects.gentoo.org/pms/6/pms.html#x1-780008.2 > > A bit OT, but that is *definitely* counter intuitive. What's the > rationale and usecase behind this ? Annoying special cases like || ( foo? ( ... ) bar? ( ... ) ) . The original reason was that old versions of Portage would simply remove unmet "flag? ( )" blocks internally. It was kept in EAPI 0 because stuff in the tree used it back then. -- Ciaran McCreesh
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
On Sat, 8 Jul 2017 12:26:59 +0200 Ulrich Mueller wrote: > | * An any-of group (||) evaluates to true if at least one of the > | items in it evaluates to true. > | * An exactly-one-of group (^^) evaluates to true if exactly one of > | the items in it evaluates to true, and all the remaining items > | evaluate to false. > | * An at-most-one-of group (??) evaluates to true if at most one of > | the items in it evaluates to true. > > It should be added that any empty group (|| or ^^ or ??) evalutates to > true, because that's what PMS specifies: > https://projects.gentoo.org/pms/6/pms.html#x1-780008.2 A bit OT, but that is *definitely* counter intuitive. What's the rationale and usecase behind this ?
Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
> On Sat, 08 Jul 2017, Michał Górny wrote: > The pre-GLEP for review is here: > https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse On first glance: Section "Processing algorithm": | 2. Check whether the REQUIRED_USE constraint matches restrictions | set in #Restrictions on REQUIRED_USE format. If it does not, report | a REQUIRED_USE mismatch and abort. Why is this needed? This case should never occur if the REQUIRED_USE syntax doesn't allow it. Section "REQUIRED_USE verification algorithm": | * An any-of group (||) evaluates to true if at least one of the | items in it evaluates to true. | * An exactly-one-of group (^^) evaluates to true if exactly one of | the items in it evaluates to true, and all the remaining items | evaluate to false. | * An at-most-one-of group (??) evaluates to true if at most one of | the items in it evaluates to true. It should be added that any empty group (|| or ^^ or ??) evalutates to true, because that's what PMS specifies: https://projects.gentoo.org/pms/6/pms.html#x1-780008.2 Ulrich pgpuHyyNDQclx.pgp Description: PGP signature
[gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints
Hi, everyone. I think the affairs have settled enough and I've finished filling in the pre-GLEP for REQUIRED_USE auto-enforcing. It's got all the algorithms, rationale and separated reference implementation. If there are no major concerns raised, I will soon start working on writing an optimized implementation for pkgcore/pkgcheck and integrating the verification algos with the CI. The pre-GLEP for review is here: https://wiki.gentoo.org/wiki/User:MGorny/GLEP:ReqUse TIA. -- Best regards, Michał Górny signature.asc Description: This is a digitally signed message part
