[gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 534 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Ulrich Mueller]

[-- Attachment #1: Type: text/plain, Size: 1078 bytes --]

>>>>> 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

[-- Attachment #2: Type: application/pgp-signature, Size: 490 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Alexis Ballier]

On Sat, 8 Jul 2017 12:26:59 +0200
Ulrich Mueller <ulm@gentoo.org> 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

[Ciaran McCreesh]

On Sat, 8 Jul 2017 13:49:56 +0200
Alexis Ballier <aballier@gentoo.org> wrote:
> On Sat, 8 Jul 2017 12:26:59 +0200
> Ulrich Mueller <ulm@gentoo.org> 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

[Alexis Ballier]

On Sat, 08 Jul 2017 11:43:39 +0200
Michał Górny <mgorny@gentoo.org> 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

[Alexis Ballier]

On Sat, 8 Jul 2017 13:01:39 +0100
Ciaran McCreesh <ciaran.mccreesh@googlemail.com> wrote:

> On Sat, 8 Jul 2017 13:49:56 +0200
> Alexis Ballier <aballier@gentoo.org> wrote:
> > On Sat, 8 Jul 2017 12:26:59 +0200
> > Ulrich Mueller <ulm@gentoo.org> 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

[Ciaran McCreesh]

On Sat, 8 Jul 2017 16:14:09 +0200
Alexis Ballier <aballier@gentoo.org> wrote:
> On Sat, 8 Jul 2017 13:01:39 +0100
> Ciaran McCreesh <ciaran.mccreesh@googlemail.com> wrote:
> > On Sat, 8 Jul 2017 13:49:56 +0200
> > Alexis Ballier <aballier@gentoo.org> wrote:  
> > > On Sat, 8 Jul 2017 12:26:59 +0200
> > > Ulrich Mueller <ulm@gentoo.org> 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

[Alexis Ballier]

On Sat, 8 Jul 2017 15:23:39 +0100
Ciaran McCreesh <ciaran.mccreesh@googlemail.com> wrote:

> On Sat, 8 Jul 2017 16:14:09 +0200
> Alexis Ballier <aballier@gentoo.org> wrote:
> > On Sat, 8 Jul 2017 13:01:39 +0100
> > Ciaran McCreesh <ciaran.mccreesh@googlemail.com> wrote:  
> > > On Sat, 8 Jul 2017 13:49:56 +0200
> > > Alexis Ballier <aballier@gentoo.org> wrote:    
> > > > On Sat, 8 Jul 2017 12:26:59 +0200
> > > > Ulrich Mueller <ulm@gentoo.org> 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

[Ciaran McCreesh]

On Sat, 8 Jul 2017 16:39:29 +0200
Alexis Ballier <aballier@gentoo.org> 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

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 981 bytes --]

On sob, 2017-07-08 at 18:58 +0100, Ciaran McCreesh wrote:
> On Sat, 8 Jul 2017 16:39:29 +0200
> Alexis Ballier <aballier@gentoo.org> 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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 1869 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 6458 bytes --]

On sob, 2017-07-08 at 16:12 +0200, Alexis Ballier wrote:
> On Sat, 08 Jul 2017 11:43:39 +0200
> Michał Górny <mgorny@gentoo.org> 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 everything for working without restriction.
> 	Plus, unlimited implication nesting has the same complexity.

No, I don't. I don't cover the meaning of nested groups and things just
explode when they come into game.

> -------
> 
> 
> 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.

I think I've mentioned that a few times in the GLEP. The validation
and verification bits were tested on all REQUIRED_USE cases from a few
days ago. For the former, all cases are listed in rationale. For
the latter, the reference implementation has test cases for every
construct that triggered an issue, including the false positives that
were fixed. I've only skipped a few that were completely redundant (e.g.
different versions of the same package that added 1-2 irrelevant items).

The solver was tested on all combinations of most of the corner cases. I
have only skipped those that would require humongous number of
combinations.

I haven't tested all combinations of masked/forced flags from
the profiles though. I plan to do this by implementing it in pkgcheck.
I will also have better performance reports based on optimized
algorithms and real use.

-- 
Best regards,
Michał Górny

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Ulrich Mueller]

[-- Attachment #1: Type: text/plain, Size: 929 bytes --]

>>>>> 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

[-- Attachment #2: Type: application/pgp-signature, Size: 490 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Ulrich Mueller]

[-- Attachment #1: Type: text/plain, Size: 832 bytes --]

>>>>> On Sat, 8 Jul 2017, Ciaran McCreesh wrote:

> On Sat, 8 Jul 2017 16:39:29 +0200
> Alexis Ballier <aballier@gentoo.org> 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

[-- Attachment #2: Type: application/pgp-signature, Size: 490 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Alexis Ballier]

On Sat, 8 Jul 2017 21:05:57 +0200
Ulrich Mueller <ulm@gentoo.org> wrote:

> >>>>> On Sat, 8 Jul 2017, Ciaran McCreesh wrote:  
> 
> > On Sat, 8 Jul 2017 16:39:29 +0200
> > Alexis Ballier <aballier@gentoo.org> 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

[Alexis Ballier]

On Sat, 08 Jul 2017 20:44:24 +0200
Michał Górny <mgorny@gentoo.org> 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 <mgorny@gentoo.org> 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 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 :)


> > -------
> > 
> > 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.


There is a huge gap between failing to solve a constraint voluntarily
because it has one too much nesting level and having a repoman warning
telling 'it is not recommended you write it that way'. The latter
ensures said developer is able to predict what is happening, the former
just adds annoyance onto users for no real reason.


> > - 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.

Isn't the goal of it to have it in a future EAPI ?


> > - keeping the specification and implementation relatively simple:
> > 	You already define everything for working without
> > restriction. Plus, unlimited implication nesting has the same
> > complexity.  
> 
> No, I don't. I don't cover the meaning of nested groups and things
> just explode when they come into game.


You mostly do with the rewriting part, you're only refusing to admit
it :)


> > -------
> > 
> > 
> > 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.  
> 
> I think I've mentioned that a few times in the GLEP. The validation
> and verification bits were tested on all REQUIRED_USE cases from a few
> days ago. For the former, all cases are listed in rationale. For
> the latter, the reference implementation has test cases for every
> construct that triggered an issue, including the false positives that
> were fixed. I've only skipped a few that were completely redundant
> (e.g. different versions of the same package that added 1-2
> irrelevant items).

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.


> The solver was tested on all combinations of most of the corner
> cases. I have only skipped those that would require humongous number
> of combinations.

That's great!

> I haven't tested all combinations of masked/forced flags from
> the profiles though. I plan to do this by implementing it in pkgcheck.
> I will also have better performance reports based on optimized
> algorithms and real use.

Makes sense.


Alexis.

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 2026 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Kristian Fiskerstrand]

[-- Attachment #1.1: Type: text/plain, Size: 781 bytes --]

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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 10660 bytes --]

On sob, 2017-07-08 at 22:34 +0200, Alexis Ballier wrote:
> On Sat, 08 Jul 2017 20:44:24 +0200
> Michał Górny <mgorny@gentoo.org> 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 <mgorny@gentoo.org> 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. 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.

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.

> > > 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.

> > > -------
> > > 
> > > 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.
> 
> 
> There is a huge gap between failing to solve a constraint voluntarily
> because it has one too much nesting level and having a repoman warning
> telling 'it is not recommended you write it that way'. The latter
> ensures said developer is able to predict what is happening, the former
> just adds annoyance onto users for no real reason.

Except it doesn't because it's extremely uncommon (and even unlikely)
and I am successfully exterminating the last occurrences. Implementing
support for something that will be never used is a waste of time.

> > > - 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.
> 
> Isn't the goal of it to have it in a future EAPI ?

I don't see how that's relevant. Nobody will be copying the whole GLEP
verbatim into the PMS.

> > > - keeping the specification and implementation relatively simple:
> > > 	You already define everything for working without
> > > restriction. Plus, unlimited implication nesting has the same
> > > complexity.  
> > 
> > No, I don't. I don't cover the meaning of nested groups and things
> > just explode when they come into game.
> 
> 
> You mostly do with the rewriting part, you're only refusing to admit
> it :)

You mean the transform? It doesn't cover the possibility of those groups
containing anything but plain flags. As we've already established,
the results become non-trivial when they do and those cases are
certainly not covered here.

> > > -------
> > > 
> > > 
> > > 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.  
> > 
> > I think I've mentioned that a few times in the GLEP. The validation
> > and verification bits were tested on all REQUIRED_USE cases from a few
> > days ago. For the former, all cases are listed in rationale. For
> > the latter, the reference implementation has test cases for every
> > construct that triggered an issue, including the false positives that
> > were fixed. I've only skipped a few that were completely redundant
> > (e.g. different versions of the same package that added 1-2
> > irrelevant items).
> 
> 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.

-- 
Best regards,
Michał Górny

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 1118 bytes --]

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:              16            0.2%        0.04%
Conflicting enforcements:    49            0.5%        0.13%
Requiring >1 pass:          153            1.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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Daniel Campbell]

[-- Attachment #1.1: Type: text/plain, Size: 1491 bytes --]

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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 1791 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Daniel Campbell]

[-- Attachment #1.1: Type: text/plain, Size: 2222 bytes --]

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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Ulrich Mueller]

[-- Attachment #1: Type: text/plain, Size: 2516 bytes --]

>>>>> 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

[-- Attachment #2: Type: application/pgp-signature, Size: 490 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 3840 bytes --]

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 10000 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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 2509 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Ulrich Mueller]

[-- Attachment #1: Type: text/plain, Size: 1896 bytes --]

>>>>> 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

[-- Attachment #2: Type: application/pgp-signature, Size: 490 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 2618 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Alexis Ballier]

On Sat, 08 Jul 2017 23:56:07 +0200
Michał Górny <mgorny@gentoo.org> 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 <mgorny@gentoo.org> 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 <mgorny@gentoo.org> 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 duplicates the code and work on that side and makes you
having to carry the reordering burden all along your GLEP :)


> 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.

Well, as noted above, I don't think this is related to any solver.

> > > > 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.

Ok that works. I don't see much difference between
'check(reorder(formula,immutables))' and
'check(reduce(formula,immutables))'... except the latter does not
have to deal with any immutable anymore.

> >   
> > > > 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.  
> 
> 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.


> > > > 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?
It's a bit annoying to see you completely lost every time it comes up.

In a few words, from a list of 'X affects Y' it gives you a compatible
linear ordering. While it can be done by hand on the easy cases, that's
something computers are much better at doing on the more complex cases.


> > > > -------
> > > > 
> > > > 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.  
> > 
> > 
> > There is a huge gap between failing to solve a constraint
> > voluntarily because it has one too much nesting level and having a
> > repoman warning telling 'it is not recommended you write it that
> > way'. The latter ensures said developer is able to predict what is
> > happening, the former just adds annoyance onto users for no real
> > reason.  
> 
> Except it doesn't because it's extremely uncommon (and even unlikely)
> and I am successfully exterminating the last occurrences. Implementing
> support for something that will be never used is a waste of time.

Except you're already wasting your time exterminating some cases for
which support is already written. You still don't know whether your
restricted syntax will be accepted in PMS (which mostly depends if
people feel comfortable with its expressivity), so you don't know if
you won't have to plug support for it later. May I remind you the
numbers I ran? Among all the rejected "too complex" usages of requse,
only *1* could have led to an invalid solution by the solver.

Feel free to do so, I mean, it cannot hurt to simplify requse in the
tree, but keep in mind that maybe support for more syntaxes will still
be needed. Esp. since I learnt recently that PMS factors the definition
of ||, &&, ^^ and co with all the other usages of it (DEPEND, etc.).

Anyway, I'm thinking it's more important to move on with this, and
iterate later, than getting everything perfect beforehand.


> > > > - 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.  
> > 
> > Isn't the goal of it to have it in a future EAPI ?  
> 
> I don't see how that's relevant. Nobody will be copying the whole GLEP
> verbatim into the PMS.

Unless you're writing a throwaway GLEP, the syntax restrictions are
supposed to go to PMS since that's what defines it...


> > > > - keeping the specification and implementation relatively
> > > > simple: You already define everything for working without
> > > > restriction. Plus, unlimited implication nesting has the same
> > > > complexity.    
> > > 
> > > No, I don't. I don't cover the meaning of nested groups and things
> > > just explode when they come into game.  
> > 
> > 
> > You mostly do with the rewriting part, you're only refusing to admit
> > it :)  
> 
> You mean the transform? It doesn't cover the possibility of those
> groups containing anything but plain flags. As we've already
> established, the results become non-trivial when they do and those
> cases are certainly not covered here.

That's why I said mostly. The missing parts are really small, trust me.


[...]

Alexis.

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 7484 bytes --]

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 exterminating the last occurrences. Implementing
> > support for something that will be never used is a waste of time.
> 
> Except you're already wasting your time exterminating some cases for
> which support is already written. You still don't know whether your
> restricted syntax will be accepted in PMS (which mostly depends if
> people feel comfortable with its expressivity), so you don't know if
> you won't have to plug support for it later. May I remind you the
> numbers I ran? Among all the rejected "too complex" usages of requse,
> only *1* could have led to an invalid solution by the solver.

May I remind you the numbers that are in the GLEP? Every single case
could have been expressed in a more readable way using a much simpler
syntax. The developers approached about that agreed with it.

I really don't like the idea of arguing on the basis of 'someone may
figure out some really complex case to prove you wrong one day'. People
weren't able to come up with a good use case for 6.5yr. What makes you
believe they will suddenly need it now?

> > > > > - keeping the specification and implementation relatively
> > > > > simple: You already define everything for working without
> > > > > restriction. Plus, unlimited implication nesting has the same
> > > > > complexity.    
> > > > 
> > > > No, I don't. I don't cover the meaning of nested groups and things
> > > > just explode when they come into game.  
> > > 
> > > 
> > > You mostly do with the rewriting part, you're only refusing to admit
> > > it :)  
> > 
> > You mean the transform? It doesn't cover the possibility of those
> > groups containing anything but plain flags. As we've already
> > established, the results become non-trivial when they do and those
> > cases are certainly not covered here.
> 
> That's why I said mostly. The missing parts are really small, trust me.
> 

It's funny how you insist on claiming your ideas to be 'small'. Yet my
implementation takes a single 23-line function and yours takes around 10
times that much, not counting all the out-of-place alterations you have
done which I don't really consider even worth counting.

Oh, and my code is more readable and easier to comprehend.

If you really want to true, then please argue with real arguments
and not run-around theory.

-- 
Best regards,
Michał Górny

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] Pre-GLEP RFC: Automated enforcing of REQUIRED_USE constraints

[Alexis Ballier]

On Sun, 09 Jul 2017 13:36:16 +0200
Michał Górny <mgorny@gentoo.org> 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 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.

The common prefix trick is similar to working on AST, except it
gives less readable output. The ordering step is identical.

For less readable output, I mean: 'foo1? ( bar )' must come before
'foo1? ( baz )' when your input in 'foo? ( baz bar )'. Working on AST
it'd be straightforward to say 'bar must come before baz in 'foo? ( baz
bar )', with common prefix either the merge-back step is left to the
reader or there needs to be a post processing step.

> > 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.

Considering you're completely skipping the step and leaving an ordering
to be manually inferred, I'm not sure what you mean by "there could be
alternative solutions that would work as well". Please explain if I've
missed something.


> > > Except it doesn't because it's extremely uncommon (and even
> > > unlikely) and I am successfully exterminating the last
> > > occurrences. Implementing support for something that will be
> > > never used is a waste of time.  
> > 
> > Except you're already wasting your time exterminating some cases for
> > which support is already written. You still don't know whether your
> > restricted syntax will be accepted in PMS (which mostly depends if
> > people feel comfortable with its expressivity), so you don't know if
> > you won't have to plug support for it later. May I remind you the
> > numbers I ran? Among all the rejected "too complex" usages of
> > requse, only *1* could have led to an invalid solution by the
> > solver.  
> 
> May I remind you the numbers that are in the GLEP? Every single case
> could have been expressed in a more readable way using a much simpler
> syntax. The developers approached about that agreed with it.

Everybody agrees the restricted syntax is more readable I think, at
least I do and have always said so. An algorithm or a spec does not care
if it's readable or not.

> I really don't like the idea of arguing on the basis of 'someone may
> figure out some really complex case to prove you wrong one day'.
> People weren't able to come up with a good use case for 6.5yr. What
> makes you believe they will suddenly need it now?

The fact that no-one has felt the need to restrict it in PMS and
clean-up crappy corner cases left for historical reasons.

It's a bit of a chicken and egg problem since now the corner cases are
more clear but I think it's almost mandatory to get the restrictions
approved and put in PMS.

> > > > > > - keeping the specification and implementation relatively
> > > > > > simple: You already define everything for working without
> > > > > > restriction. Plus, unlimited implication nesting has the
> > > > > > same complexity.      
> > > > > 
> > > > > No, I don't. I don't cover the meaning of nested groups and
> > > > > things just explode when they come into game.    
> > > > 
> > > > 
> > > > You mostly do with the rewriting part, you're only refusing to
> > > > admit it :)    
> > > 
> > > You mean the transform? It doesn't cover the possibility of those
> > > groups containing anything but plain flags. As we've already
> > > established, the results become non-trivial when they do and those
> > > cases are certainly not covered here.  
> > 
> > That's why I said mostly. The missing parts are really small, trust
> > me. 
> 
> It's funny how you insist on claiming your ideas to be 'small'. Yet my
> implementation takes a single 23-line function and yours takes around
> 10 times that much, not counting all the out-of-place alterations you
> have done which I don't really consider even worth counting.
> 
> Oh, and my code is more readable and easier to comprehend.
> 
> If you really want to true, then please argue with real arguments
> and not run-around theory.
> 

So, you're comparing quick n dirty POC to get some numbers and
investigate if an idea is worth it and something you've worked on
cleaning up ? Also, considering your usual rejection of anything
that you've not invented, I don't feel the need to waste my time
on getting something clean.

Alexis.