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@g.o> 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.