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

[Alexis Ballier <aballier@gentoo.org>]

On Wed, 31 May 2017 21:02:24 +0200
Michał Górny <mgorny@gentoo.org> wrote:

> On śro, 2017-05-31 at 19:39 +0200, Alexis Ballier wrote:
> > > >  Again, you *need* to process the constraints in order. '!a?
> > > > ( b ) !b? ( a )' is not deterministic when none of a and b are
> > > > enabled otherwise.    
> > > 
> > > You can't rely on any particular order of constraints, especially
> > > when eclass stacking comes into play. You could try defining some
> > > constraint- sorting algorithm but it's going to be complex and
> > > it's usefulness will be limited anyway due to various kinds of
> > > grouping.  
> > 
> > 
> > Better have some order: If half of the above constraint comes from
> > ebuild and the other half comes from eclass, then PM might toggle
> > 'a' or 'b' depending on the phase of the moon which is specifically
> > what we're trying to avoid.  
> 
> No, it can't. That's the whole point. The algorithm must be defined so
> that it is always predictable independently of order (maybe except
> the ordering inside ^^, ||, ??) and independently of how it's nested
> (i.e. 'a? ( b? ( c ) )' must give the same result as 'b? ( a? ( c )
> )').

This is a lot of handwaving without real description of how it would
work. This starts to look a lot like confluence in rewriting systems
and you want developers to write only confluent rules and repoman to
decide that. Good luck with that.

Let's look at real world examples:
gtk+:

REQUIRED_USE="
    || ( aqua wayland X )
    xinerama? ( X )
"

Let's assume aqua is masked, which reduces to:
REQUIRED_USE="
    || ( wayland X )
    xinerama? ( X )
"

With USE='-* xinerama' this one is invalid: applying the first
constraint first enables wayland, then the 2nd enables X, giving a
result of USE="xinerama wayland X". Applying the 2nd first enables X,
then the 1st does nothing, giving a result of USE="xinerama X".


Now the funny one:
$ portageq metadata / ebuild dev-lang/php-7.0.18 REQUIRED_USE
cli? ( ^^ ( readline libedit ) ) truetype? ( gd ) webp? ( gd ) cjk?
( gd ) exif? ( gd ) xpm? ( gd ) gd? ( zlib ) simplexml? ( xml ) soap?
( xml ) wddx? ( xml ) xmlrpc? ( || ( xml iconv ) ) xmlreader? ( xml )
xslt? ( xml ) ldap-sasl? ( ldap ) mhash? ( hash ) phar? ( hash ) qdbm?
( !gdbm ) readline? ( !libedit ) recode? ( !imap !mysqli ) sharedmem?
( !threads ) mysql? ( || ( mysqli pdo ) ) || ( cli cgi fpm apache2
embed phpdbg )



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.

> If you start relying on stuff like ordering, you're one step from
> making stuff suddenly fail or change meaning due to minor changes,
> like sorting stuff.

What we want to ensure is that for 2 identical inputs the results are
identical. If ordering is specified, then re-ordering REQUIRED_USE in
an ebuild is not minor anymore. That's a trade off.


> > eclass stacking is not a problem: specify if it's append or prepend
> > and be done.  
> 
> What about multiple inherits with guards? Next thing I know, we end up
> putting REQUIRED_USE outside guards (like we have to do with
> EXPORT_FUNCTIONS now) because you need a specific order, and guards
> make it unpredictable.

guards wont make much of a difference: They'll simply de-duplicate
constraints by keeping only the rightmost one in the prepend case and
the leftmost one in the append case I think.

> > Note that if you want to remove the need for an order, you'll need
> > to ensure that all orderings of the constraints give the same
> > result. It's not sufficient to "only" check all possible inputs.  
> 
> That's the matter of the algorithm.

For what I know, this algorithm does not even exist.

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


> > > The point would be: by definition, the solver should be able to
> > > touch *any* USE flag. If it can't, it mostly implies that you
> > > can't use the automatic solver, and so the case is irrelevant for
> > > checking. Attempting to go beyond that is going to give a lot of
> > > complexity and most likely kill the whole idea.
> > > 
> > > One thing we need to worry about are masks. We need to think about
> > > them.  
> > 
> > It makes zero difference for any solver if you replace variables
> > (useflags) by 'true' or 'false' constants (masked/forced/user-forced
> > useflags). It's even simpler actually. Whether the formula is not
> > constantly 'true' (ie REQUIRED_USE is useless) or constantly
> > 'false' (ie there's no way to solve it) is equivalent to solving
> > SAT. We likely don't want that for repoman running on php.
> >   
> 
> Well, probably yes. We just need to make sure to apply them correctly
> in different contexts, to avoid accidentally skipping some
> constraints. I think it would be reasonably to assume that:
[...]

Yes, you can eliminate constants. It is probably even confluent, i.e.
the order in which you eliminate them does not matter and it always
converges to the same result.

Alexis.