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

[Michał Górny]

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