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

[Michał Górny]

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