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

-- 
Best regards,
Michał Górny