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

[Michał Górny]

On pon, 2017-06-05 at 19:24 +0200, Alexis Ballier wrote:
> 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.

I'm sure Ciaran will love to elaborate ;-).

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

I've noticed that you turned the implications into multi-conditions,
breaking all my scripts ;-). Is the [list of conditions] conjunctive or
disjunctive?

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

Well, I meant 'by current rules', without considering preferences.

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

My solver doesn't really support nested || ^^, so it failed to apply any
reasonable change ;-).

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

|| ( ^^ ( ?? ( a b ) c ( d e ) ) f )

? ;-)


-- 
Best regards,
Michał Górny