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

[Alexis Ballier <aballier@gentoo.org>]

On Fri, 02 Jun 2017 15:55:17 +0200
Michał Górny <mgorny@gentoo.org> wrote:

> On pią, 2017-06-02 at 13:27 +0200, Alexis Ballier wrote:
> > On Thu, 01 Jun 2017 23:31:25 +0200
> > Michał Górny <mgorny@gentoo.org> wrote:
> > [...]  
> > > > There are probably dozens of ways to make that non
> > > > deterministic. Here's one: USE='-*'. Apply '|| ( cli cgi fpm
> > > > apache2 embed phpdbg )' last; this enables 'cli'. Since it's
> > > > the last one, REQUIRED_USE is not satisfied because of 'cli?
> > > > ( ^^ ( readline libedit ) )'. If you process it first, then you
> > > > enable cli and readline and are good.    
> > > 
> > > You just take a second iteration, and things fall into place.
> > > That's not a problem.
> > >   
> > > > > > Also, what happens if we applied all the constraints and
> > > > > > obtained some useflags setting that still fails REQUIRED_USE
> > > > > > check ?      
> > > > > 
> > > > > It can't happen. If you can apply all the constraints, then
> > > > > implicitly REQUIRED_USE is satisfied. If you can't apply all
> > > > > the constraints, then it just fails. Of course, we want to
> > > > > ultimately avoid that case.    
> > > > 
> > > > See the php example above. How do you ensure this does not
> > > > happen?
> > > > 
> > > > Note that your assertion 'If you can apply all the constraints,
> > > > then implicitly REQUIRED_USE is satisfied.' is false: You're
> > > > changing the values of useflags, thus might violate some
> > > > previously checked constraint.    
> > > 
> > > So you reiterate. Either you reach a solution (preferably there's
> > > only a single valid solution you can reach) or you hit a previous
> > > state which indicates a loop and you fail.  
> > 
> > 
> > So, PM, for every ebuild, will need to store the (at most) 2^n
> > states it has already seen while trying to solve REQUIRED_USE and
> > iterate until it cannot proceed anymore or falls into a previous
> > state (so that's 2^n time too). That way we go from a linear time &
> > linear space algorithm to one in exponential time & space. That's
> > probably not a good idea.  
> 
> I don't think that's actually going to happen. You'd have to try
> really hard to get over n-1 iterations. I mean, the only simple way I
> can think of is:
> 
>   b? ( a ) c? ( b ) d? ( c ) e? ( d ) ...
> 
> and this only means n-1 iterations. Can you think of a better way to
> force multiple iterations that can be written without making
> REQUIRED_USE completely unreadable? How likely is that going to happen
> accidentally?

I don't see any reason why it should terminate after n iterations; I
don't see any example of how to do more either. I can try to think more
about it, but maybe it is not even needed, see below.

> > I think it's better to limit the number of iterations to some
> > constant. I'd say 1, then fail if REQUIRED_USE is still not
> > satisfied. Maybe 2 or 3 can be useful but I think it'd be much
> > harder to provide automated checks for that and much harder for
> > ebuild writers to understand what will happen with the REQUIRED_USE
> > they're about to write. 
> 
> Well, I don't mind setting that. All my tests (that weren't
> deliberately abusing the algorithm) were able to finish in a single
> iteration. 2 or 3 should probably be safe for all the reasonable
> uses. However, if we're not going to verify all possible values on
> repoman side, I think it would be better to have a larger limit for
> users, to not have things explode on them unnecessarily.


Look, if we assume left to right solving, only one iteration possible
and all the constraints to be of the form 'p_1? p_2? ... p_n? ( q_1 ...
q_m )' where p_i and q_i are either 'useflag' or '!useflag', then we
only have to check when such a clause can change a previously satisfied
clause to unsatisfied.

For two clauses: 
"p_1? p_2? ... p_n? ( q_1 ... q_m )" and "p'_1? p'_2? ... p'_{n'}?
( q'_1 ... q'_{m'} )", assuming the first is satisfied, when can solving
the 2nd break the 1st?

It must be that:
1.The conditions are compatible: No p_i is the negation of a p'_j.
2.Solving the 1st does not make the 2nd trivially true: No q_i is
  the negation of a p'_j.
3.Solving the 2nd does not make the 1st trivially true afterwards: No
  p_i is the negation of a q'_j.
4.Solving the 2nd does break the 1st assumption: (A q_i is
  the negation of a q_'j) or (a q'_j is some p_i and one of q_1 ... q_m
  might be false).

The only a priori non polynomial part here is "one of q_1 ... q_m
might be false". If we do not check that (only check that some q'_j is
some p_i), we are still guaranteed that the 2nd clause cannot break the
1st but we might end up rejecting otherwise valid constructs.

Doing that, we have a check guaranteeing that the above algorithm will
always provide a valid answer for 'clause_1 clause_2' in
O(|clause_1|*|clause_2|) time.
For a complete REQUIRED_USE='clause_1 ... clause_k', it is sufficient
to check that, for any i>j, clause_i cannot break clause_j in the above
sense. This gives a polynomial algorithm for being certain that a
REQUIRED_USE constraint guarantees the existence of a valid solution
after one pass.


We can do even better: Consider a graph where the nodes are the clauses
and there is an edge 'a -> b' if 'a' can break 'b' in the above sense.
This means 'a' must come left of 'b' in REQUIRED_USE. Hence, repoman
can do a topological sort of that graph and suggest a proper reordering
of the clauses or, when not possible, exhibit a cycle causing a problem
asking the developer to fix it.



Let's run a few examples to see if dropping the condition in point 4.
is not too much to ask:
"
   || ( aqua wayland X )
   xinerama? ( X )
"
Becomes:
"
  !X? ( !wayland? ( aqua ) )
  xinerama? ( X )
"
Points 1. and 2. above hold, point 3 fails with p_i = !X, q'_j = X. So
they're good and the constraint is valid in the above sense.


Another example, simplified form from php:
"
  cli? ( ^^ ( readline libedit ) ) 
  || ( cli cgi )
"
Becomes:
"
(a)   cli? ( !libedit? ( readline ) )
(b)   cli? ( libedit? ( !readline ) )
(c)   !cgi? ( cli )
"

Let's build the graph: No edge between (a) and (b) because they fail
point 1. No edge (a) -> (c) nor (b) -> (c): They fail point 4 since
"readline" does not appear in (c). There are edges (c) -> (a) and (c) ->
(b): Point 1 to 3 hold, point 4 holds because of 'a q'_j is some p_i'
with q'_j = p_i = "cli". The ordering is thus invalid because (a) and
(b) come before (c) and there are edges going from (c) to both of them.
A topological sort will give you something like "(c) (a) (b)" and
repoman can suggest you to rewrite that as:
"
(c)   !cgi? ( cli )
(a)   cli? ( !libedit? ( readline ) )
(b)   cli? ( libedit? ( !readline ) )
"
In addition, if we can ensure the topological sort is somewhat stable
(*), then it is possible to infer back that (a) (b) come from "cli? ( ^^
( readline libedit ) )" and (c) comes from "|| ( cli cgi )" so the
repoman warning/error could look like:
Hey, your REQUIRED_USE does not allow easy solving in one pass, would
you mind using "|| ( cli cgi ) cli? ( ^^ ( readline libedit ) )"
instead ?

(*) Ensuring clauses expanded from the same construct in REQUIRED_USE
stay together and thus can be grouped back to their original form. This
might not be possible or easy though.


A last example: The mysql/mysqli from php you mentioned in an earlier
email here.
"
(a)   recode? ( !imap !mysqli )
(b)   mysql? !pdo? ( mysqli )
"
There are edges (a) -> (b) and (b) -> (a): Points 1 to 3 hold; Point 4
holds because 'A q_i is the negation of a q_'j' with mysqli/!mysqli.
The topological sort will fail since there is a cycle and will exhibit
this cycle. repoman warning/error could look like:
Hey, your constraint does not allow automatic solving, there is a cycle
'recode? ( !imap !mysqli )' -> 'mysql? !pdo? ( mysqli )' -> 'recode?
( !imap !mysqli )'.





This whole thing definitely needs more thought and feedback but for now
those extra restrictions seem quite natural to me, allow easy solving
on the PM side and allow to have useful feedback from repoman.

Alexis.