On Thu, 01 Jun 2017 23:31:25 +0200 Michał Górny <mgo...@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 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. [...] Alexis.
