Re: [gentoo-dev] [RFC] Forced/automatic USE flag constraints (codename: ENFORCED_USE)

[Alexis Ballier]

On Mon, 05 Jun 2017 16:10:25 +0200
Michał Górny <mgorny@g.o> wrote:

> On pon, 2017-06-05 at 09:55 +0200, Alexis Ballier wrote:
> > On Sun, 4 Jun 2017 10:59:38 +0200
> > Alexis Ballier <aballier@g.o> wrote:
> >
> > > Here's a quick n dirty code to play with, based on yours:
> > > https://github.com/aballier/required-use
> >
> > I've run that on the whole tree (considering all ebuilds with non
> > empty REQUIRED_USE), some stats:
> >
> > $ time python3 classify.py requsel
> > Stats:
> > 	Parse error: 16
>
> Hmm, how did you get those numbers? I just tested parsing and found
> only 7 unique REQUIRED_USE entries that fail. However, my sample file
> is only around 1000 entries long, so either I failed to get all of
> them, or you didn't deduplicate your list ;-). More on it below.

I did not deduplicate anything. I took every single ebuild and
generated a list of req use out of it. Meaning if you had 10 ebuilds
for 1 package with the same req use that'd count as 10 above.

[...]
> > The cycle is mostly due to:
> > $ python3 nsolve.py 'llvm? ( gallium ) gallium? ( llvm )'
> > [...]
> > toposort.CircularDependencyError: Circular dependencies exist among
> > these items: {[gallium]? => [llvm]:{[llvm]? => [gallium]}, [llvm]?
> > => [gallium]:{[gallium]? => [llvm]}}
> >
> >
> > This is something I had overseen when replacing 'a q'_j is some p_i
> > and one of q_1 ... q_m might be false' by only 'a q'_j is some
> > p_i'; it can be replaced without changing anything in the way PM
> > would solve it by "a q'_j is some p_i and the set of {q_j} is not a
> > subset of q' union p'" (that is, {q_i} is not trivially true if the
> > 2nd clause is applied). Extending that, we get those stats:
>
> I'm not even trying to understand the things you say with indexes but
> I trust you know what you're doing.

With that kind of things it's good to have someone having a second
look. It's so easy to forget a case or to miss a simplification.

> For completeness, we need to
> consider three cross-dependent states:
>
> a. a? ( b ) b? ( a )


that's exactly the above :p

{q_j} is {b}, {q'} is {a}, {p'} is {b}; {b} is a subset of {a} union
{b}


[...]
> b. !a? ( !b ) !b? ( !a )

that's also the above with s/!b/b/ s/!a/a/ :=)

> c. a? ( b ) !a? ( !b )

that's already handled.

[...]
> > I'll let you play with it, but for me it seems this would work quite
> > nicely.
> >
>
> Well, I guess it's time to hit the next level. For a start, we have to
> handle all-of groups, i.e.:
>
>   ( a b c )
>
> Stand-alone makes little sense (and little trouble) but as you could
> have seen it's used nested in other thingies:
>
> 1. || ( ( a b ) ( c d ) e )
>
> 2. ?? ( ( a b ) ( c d ) e )
>
> 3. ^^ ( ( a b ) ( c d ) e )

Yeah that's the nesting problem causing a parse error.
Those should be expanded to implications. What I'm relying onto is all
clauses to be of the form '[list of conditions]? [list of constraints]'


> For verifying constraints, they are not bad. We just follow the
> generic rule that the branch evaluates to true if all subexpressions
> are true. 
>
> For solving, it might be a little unclear on how to proceed with
> partially true branches but for the sake of simplicity I would just
> ignore them and behave as if they were false. That is, case (1) with
> USE='c' would result in 'a b' being enabled.
>
> The practical uses I've seen are:
>
> a. || ( deprecated ( gtk3 introspection ) )
>
> I guess this one would be equivalent to:
>
>   !gtk3? ( !introspection? ( deprecated ) )

Unfortunately no. Favoring leftmost, you need to enable 'deprecated'
when either gtk3 or introspection is false.

That'd be:
!gtk3? ( deprecated )
!introspection? ( deprecated )


Fortunately we can distribute \/ and /\:
|| ( deprecated ( gtk3 introspection ) )
is equivalent to:
|| ( deprecated gtk3 )
|| ( deprecated introspection )

giving the above implication translation.

This can be extended to 
|| ( ( a1 a2 a3 ... ) ( b1 b2 b3 ... ) ... ) to handle all cases.



> b. ^^ ( ( !32bit 64bit ) ( 32bit !64bit ) ( 32bit 64bit ) )
>
> This looks like a crazy way of saying:
>
>   || ( 32bit 64bit )

Hmm yes


> c. ^^ ( ( !ruby !s7 ) ( ruby !s7 ) ( !ruby s7 ) )
>
> This looks like an insane version of:
>
>   ?? ( ruby s7 )


yes too it seems



> except that per my solver it just disables both when both are set ;-).

That's kind of the point. And that's why it is important to have the
solving rules well defined. Depending on how REQUIRED_USE is written,
it will be solved differently even for equivalent logical formulas.


> Not sure if the extra complexity is worth for roughly one valid use
> case, and a lot of insanity.

I think this can be done without too much pain. As you noticed, replace
'^^ ( whatever )' by '|| ( whatever ) ?? ( whatever )' so we're left
with only || and ?? (and 'and' denoted by space and grouping in our
notation).

|| ( clause1 clause2 ... ) is replaced by
[!clause1 !clause2 ...]?[clause1]

?? ( clause1 clause2 ... ) is replaced by:
[clause1]?[!clause2 !clause3 ...]
[!clause1]?[ ?? ( clause2 clause3 ... ) ]

! (|| ( clause1 clause2 ... ) ) is '!clause1 !clause2 ...' (de morgan)
! ( clause1 clause2 ... ) is '|| ( !clause1 !clause2 ... )' (de morgan
too)
! (?? ( clause1 clause2 ... ) ) could be written as 'clause1? ( ||
( clause2 ... ) ) !clause1? ( ! ?? ( clause2 ... ) )'

and I think that's it to allow expanding everything to implications.


[ begin || ( clause1 clause2 ... ) end ]?[constraint]

is:
[ begin clause1 end]?[constraint]
[ begin clause2 end]?[constraint]
etc.


[ begin ([icond]?[iconstraint]) end]?[constraint]
is:
[ begin icond]?[iconstraint]
[ begin end]?[constraint]

I think

and

[ begin ( clause1 clause2 ... ) end]?[constraint]
is
[ begin clause1 clause2 ... end]?[constraint]


[...]
> Of course past that there's a deeper insanity: all those constructs
> can be nested without limits. Verification is possible, solving maybe
> -- but I'm not sure if we even want to try to think what the correct
> solution would be.

We're good as long as they're rewritten as implications internally.


> There's only one use of this:
>
>   ?? ( gl3plus ( || ( gles2 gles3 ) ) )

That'd be:
gl3plus? ( ! || ( gles2 gles3 ) )

per the above reduced to:
gl3plus? ( !gles2 !gles3 )

>
> FWICS, it probably works like this;
>
>  g       g    
>  l       l    
>  3 g g   3 g g
>  p l l   p l l
>  l e e   l e e
>  u s s   u s s
>  s 2 3 | s 2 3
>  0 0 0 | 0 0 0 (==)
>  0 0 1 | 0 0 1 (==)
>  0 1 0 | 0 1 0 (==)
>  0 1 1 | 0 1 1 (==)
>  1 0 0 | 1 0 0 (==)
>  1 0 1 | 1 0 1 [unsolvable due to loop]
>  1 1 0 | 1 1 0 [unsolvable due to loop]
>  1 1 1 | 1 1 1 [unsolvable due to loop]
>
> i.e. it would be equivalent to:
>
>   gl3plus? ( !gles2 !gles3 )
>
> unless the author meant something else and failed.


Exactly. I don't know why you see a loop.


> The question is whether we want to:
>
> a. actually try to solve this nesting insanity,
>
> b. declare it unsupported and throw REQUIRED_USE mismatch on user,
>
> c. ban it altogether.


I don't think it is *that* insane to support nesting :)


Alexis.