[gentoo-dev] [RFC] Restricting allowed nesting of REQUIRED_USE

[gentoo-dev] [RFC] Restricting allowed nesting of REQUIRED_USE

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 6702 bytes --]

Hi, everyone.

As you may or may not know, PMS says rather little about REQUIRED_USE
[1,2]. The largest past of the definition is shared with other
dependency-like specifications [3].

Similarly to regular dependency specifications, PMS is rather lax in
nesting things. While this isn't a major problem for dependencies where
the syntax is limited to any-of, all-of and USE-conditional groups
(though it already may cause some confusion there), it allows quite
a bit of a mayhem with the full set of REQUIRED_USE clauses.

We have five different kinds of clauses there: any-of, at-most-one-of,
exactly-one-of, all-of and USE-conditional. Furthermore, unlike
in dependency specifications, the last type is circular with flags
enforced by REQUIRED_USE constraints.

While nesting all of those clauses is technically valid (and can be
logically verified), it has no proven usability. As a result, it is
either not used at all or has a few use cases which suffer from poor
readability and can be easily replaced with *much simpler* constraints.
In fact, allowing them is not solving any issues but only introducing
more when developers fail at using them.

I would therefore like to discuss restricting nesting of REQUIRED_USE
clauses.


What's my take in this? As you have probably noticed (and stopped
reading) I am working with Alexis on solving REQUIRED_USE constraints
automatically. We're working towards a few goals: keeping things simple,
giving predictable solutions, and being able to automatically validate
whether the constraints are solvable.

While we're near solving almost everything, the complex clauses add
unnecessary complexity (both to the spec and to the code) which does not
really benefit anyone, and bring solutions that can not be predictable
because the clauses are ambiguous by design.

To avoid adding this complexity, it would be reasonable to ban at least
some of the non-useful combinations. This means either banning them
completely (in a future EAPI + possibly repoman) so that developers do
not even try to use them, or disabling autosolving when they are being
used).


Below I have listed the clauses I'd like to ban in a few logical groups,
along with explanations and examples.


1. Nested ||, ?? and ^^ groups
------------------------------

Technically, any level of ||, ?? and ^^ nesting is valid. Practically,
any nesting is hardly readable, and could be replaced by something
simpler. For a few examples:

  || ( a || ( b c ) )  <->  || ( a b c )

  || ( a ?? ( b c ) )  <->  b? ( c? ( a ) )

  ?? ( ?? ( a b ) c )  <->  !a? ( !c ) !b ( !c )

  ?? ( a || ( b c ) )  <->  a? ( !b !c )

The 'simpler versions' of those constraints may seem weird but that's
only because the constraints themselves are weird as hell and it's hard
to tell what the original intent might be. I've skipped ^^ as it is
equivalent to the conjunction of || and ??.

FWICS, we have only two cases of this kind of nesting in ::gentoo:

A. app-backup/bacula:

  || ( ^^ ( mysql postgres sqlite ) bacula-clientonly )

which could be written equivalently as:

  !bacula-clientonly? ( ^^ ( mysql postgres sqlite ) )

B. dev-games/ogre:

  ?? ( gl3plus ( || ( gles2 gles3 ) ) ) gles3? ( gles2 )

which is completely insane. Per the above examples, it could be replaced
e.g. by more predictable:

  gl3plus? ( !gles2 !gles3 ) gles3? ( gles2 )

To summarize, I don't think we really need or want this kind of nesting.
I would therefore want to disallow nesting any of ||, ??, ^^ inside any
other of ||, ??, ^^ (including as subexpressions).


2. All-of groups inside ??, ^^
------------------------------

This one is technically valid and not even hard to solve. However,
I haven't found any use case for it and it's impossible to solve it
in a completely predictable way.

Let's take a simple case here:

  ?? ( A ( B C ) )

The meaning is rather simple: you can't enable both A and (B and C).
If we put the preference on A, then this constraint can be solved
by either disabling B or C, or both. And there's no definitive answer
on what would be the preferred action here.

So it'd really be better to be clearer on the desired result, e.g.:

  A? ( !B !C )
  A? ( !B )

etc. I'm aware that it would become more complex with more clauses;
however, nobody has been able to come up with even one so far.

The only use cases of all-of groups inside ??/^^ in ::gentoo are:

A. sci-chemistry/icm:

  ^^ ( ( !32bit 64bit ) ( 32bit !64bit ) ( 32bit 64bit ) )

which is much more readable as:

  || ( 64bit 32bit )

B. media-sound/snd:

  ^^ ( ( !ruby !s7 ) ( ruby !s7 ) ( !ruby s7 ) )

which, once again, is much less confusing as:

  ?? ( ruby s7 )

All that considered, I think this has no real use case and only
encourages people to do stupid things. Since it's ambiguous
and unreadable, I would like to ban it.



3. USE-conditionals inside ||, ??, ^^ groups
--------------------------------------------

This one is not as horrible as the others mentioned but it seems to have
barely any use, unnecessarily complexifies the AST and damages
readability. I'm talking about cases like:

  || ( a foo? ( b ) c )

which is roughly equivalent to:

  foo? ( || ( a b c ) )
  !foo? ( || ( a c ) )

The only use I've seen is media-video/mpv:

  || ( cli libmpv ) [...]
  opengl? ( || ( aqua egl X raspberry-pi !cli? ( libmpv ) ) )

which is probably completely meaningless since you have to either enable
cli or libmpv in the first place.

I don't have *that* very strong opinion on this but I'd rather ban it
and expect people to use more straightforward (= readable
and predictable expressions).


Resulting AST
=============

If all three classes I've mentioned were banned, the AST would look
like:

REQUIRED_USE := [<top-expr>...]

top-expr := <flag> | <use-cond> | <any-of> | <most-one-of> | <exactly-one-of>

flag := ['!']<flag-name>

use-cond := ['!']<flag-name>'? (' <top-expr>... ')'

any-of := '|| (' <any-of-expr>... ')'

any-of-expr := <flag> | <all-of>

most-one-of := '??' ( <flag>... )

exactly-one-of := '^^' ( <flag>... )

all-of := '(' <flag>... ')'


Note that only USE conditionals are deeply nested now. Of all other
groups, || can contain pure flags and/or all-of blocks (which contain
only pure flags), and ?? and ^^ contain pure flags only.

Your thoughts?


[1]:https://projects.gentoo.org/pms/6/pms.html#x1-690007.3
[2]:https://projects.gentoo.org/pms/6/pms.html#x1-910008.2.7
[3]:https://projects.gentoo.org/pms/6/pms.html#x1-780008.2

-- 
Best regards,
Michał Górny

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] [RFC] Restricting allowed nesting of REQUIRED_USE

[Alexis Ballier]

On Sat, 10 Jun 2017 00:30:07 +0200
Michał Górny <mgorny@gentoo.org> wrote:

> Hi, everyone.
> 
> As you may or may not know, PMS says rather little about REQUIRED_USE
> [1,2]. The largest past of the definition is shared with other
> dependency-like specifications [3].
> 
> Similarly to regular dependency specifications, PMS is rather lax in
> nesting things. While this isn't a major problem for dependencies
> where the syntax is limited to any-of, all-of and USE-conditional
> groups (though it already may cause some confusion there), it allows
> quite a bit of a mayhem with the full set of REQUIRED_USE clauses.
> 
> We have five different kinds of clauses there: any-of, at-most-one-of,
> exactly-one-of, all-of and USE-conditional. Furthermore, unlike
> in dependency specifications, the last type is circular with flags
> enforced by REQUIRED_USE constraints.
> 
> While nesting all of those clauses is technically valid (and can be
> logically verified), it has no proven usability. As a result, it is
> either not used at all or has a few use cases which suffer from poor
> readability and can be easily replaced with *much simpler*
> constraints. In fact, allowing them is not solving any issues but
> only introducing more when developers fail at using them.
> 
> I would therefore like to discuss restricting nesting of REQUIRED_USE
> clauses.
> 
> 
> What's my take in this? As you have probably noticed (and stopped
> reading) I am working with Alexis on solving REQUIRED_USE constraints
> automatically. We're working towards a few goals: keeping things
> simple, giving predictable solutions, and being able to automatically
> validate whether the constraints are solvable.
> 
> While we're near solving almost everything, the complex clauses add
> unnecessary complexity (both to the spec and to the code) which does
> not really benefit anyone, and bring solutions that can not be
> predictable because the clauses are ambiguous by design.
> 
> To avoid adding this complexity, it would be reasonable to ban at
> least some of the non-useful combinations. This means either banning
> them completely (in a future EAPI + possibly repoman) so that
> developers do not even try to use them, or disabling autosolving when
> they are being used).

I'm not sure it is worth restricting too much in the spec, at least now.
It certainly has benefits, but the extra complexity they add forces to
thoroughly think about how to design the proper solver, which I don't
see as a bad thing.

The main problem is that the solver, in those complex cases, will
provide results that, at least to me, do not seem natural.

It'd probably be a very good thing to restrict the allowed nesting
since they add (runtime) complexity to the solver & checker, like a
repoman warning and/or error, depending on some threshold.

On the other hand, the syntax you propose seems way much saner. I like
it and consider it is a good way to guide developers into writing
easily predictable constraints. However, I would not disable auto
solving when this does not match, I would have a generic algorithm, and
wait for field testing before deciding if people are happy with the
results or if they prefer to rewrite their constraints in a saner way
to have a straightforward interpretation of the solver results.

Bests,

Alexis.

Re: [gentoo-dev] [RFC] Restricting allowed nesting of REQUIRED_USE

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 2195 bytes --]

On sob, 2017-06-10 at 00:30 +0200, Michał Górny wrote:
> Below I have listed the clauses I'd like to ban in a few logical groups,
> along with explanations and examples.
> 
> [...]

Actually, after some thinking, here's one more:

4. All-of operator inside ||
----------------------------

While this is not as bad as the others, it probably makes sense to ban
it to preserve symmetry between operators. It has very little real use,
killing it simplifies all algorithms even more. Since it was the last
valid use of all-of operator, this means we can ban it altogether
in REQUIRED_USE.

The only real use in ::gentoo right now is:

  || ( deprecated ( gtk3 introspection ) ) )

which is equivalent to:

  !gtk3? ( deprecated ) !introspection? ( deprecated )

While the former is a little shorter and might be considered somewhat
readable, I don't think it's worth to keep the extra complexity for
a single package. Especially considering that the package is not even
using it correctly since -- judging by the code -- it should actually
have:

  python? ( gtk3? ( introspection ) )

which would render the above clause irrelevant.

The two remaining uses of all-of in ::gentoo are obvious mistakes --
accidental extra parentheses.

> Resulting AST
> =============
> 
> If all three classes I've mentioned were banned, the AST would look
> like:
> 
> REQUIRED_USE := [<top-expr>...]
> 
> top-expr := <flag> | <use-cond> | <any-of> | <most-one-of> | <exactly-one-of>
> 
> flag := ['!']<flag-name>
> 
> use-cond := ['!']<flag-name>'? (' <top-expr>... ')'
> 
> any-of := '|| (' <any-of-expr>... ')'

Now:

any-of := '|| (' <flag>... ')'

> any-of-expr := <flag> | <all-of>

Scratch that.

> most-one-of := '??' ( <flag>... )
> 
> exactly-one-of := '^^' ( <flag>... )
> 
> all-of := '(' <flag>... ')'
> 
> 
> Note that only USE conditionals are deeply nested now. Of all other
> groups, || can contain pure flags and/or all-of blocks (which contain
> only pure flags), and ?? and ^^ contain pure flags only.
> 

Now even better. ||, ?? and ^^ all are pure, flat groups of USE flags.


-- 
Best regards,
Michał Górny

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]

Re: [gentoo-dev] [RFC] Restricting allowed nesting of REQUIRED_USE

[Michał Górny]

[-- Attachment #1: Type: text/plain, Size: 4093 bytes --]

On nie, 2017-06-11 at 18:18 +0200, Alexis Ballier wrote:
> On Sat, 10 Jun 2017 00:30:07 +0200
> Michał Górny <mgorny@gentoo.org> wrote:
> 
> > Hi, everyone.
> > 
> > As you may or may not know, PMS says rather little about REQUIRED_USE
> > [1,2]. The largest past of the definition is shared with other
> > dependency-like specifications [3].
> > 
> > Similarly to regular dependency specifications, PMS is rather lax in
> > nesting things. While this isn't a major problem for dependencies
> > where the syntax is limited to any-of, all-of and USE-conditional
> > groups (though it already may cause some confusion there), it allows
> > quite a bit of a mayhem with the full set of REQUIRED_USE clauses.
> > 
> > We have five different kinds of clauses there: any-of, at-most-one-of,
> > exactly-one-of, all-of and USE-conditional. Furthermore, unlike
> > in dependency specifications, the last type is circular with flags
> > enforced by REQUIRED_USE constraints.
> > 
> > While nesting all of those clauses is technically valid (and can be
> > logically verified), it has no proven usability. As a result, it is
> > either not used at all or has a few use cases which suffer from poor
> > readability and can be easily replaced with *much simpler*
> > constraints. In fact, allowing them is not solving any issues but
> > only introducing more when developers fail at using them.
> > 
> > I would therefore like to discuss restricting nesting of REQUIRED_USE
> > clauses.
> > 
> > 
> > What's my take in this? As you have probably noticed (and stopped
> > reading) I am working with Alexis on solving REQUIRED_USE constraints
> > automatically. We're working towards a few goals: keeping things
> > simple, giving predictable solutions, and being able to automatically
> > validate whether the constraints are solvable.
> > 
> > While we're near solving almost everything, the complex clauses add
> > unnecessary complexity (both to the spec and to the code) which does
> > not really benefit anyone, and bring solutions that can not be
> > predictable because the clauses are ambiguous by design.
> > 
> > To avoid adding this complexity, it would be reasonable to ban at
> > least some of the non-useful combinations. This means either banning
> > them completely (in a future EAPI + possibly repoman) so that
> > developers do not even try to use them, or disabling autosolving when
> > they are being used).
> 
> I'm not sure it is worth restricting too much in the spec, at least now.
> It certainly has benefits, but the extra complexity they add forces to
> thoroughly think about how to design the proper solver, which I don't
> see as a bad thing.
> 
> The main problem is that the solver, in those complex cases, will
> provide results that, at least to me, do not seem natural.
> 
> It'd probably be a very good thing to restrict the allowed nesting
> since they add (runtime) complexity to the solver & checker, like a
> repoman warning and/or error, depending on some threshold.
> 
> On the other hand, the syntax you propose seems way much saner. I like
> it and consider it is a good way to guide developers into writing
> easily predictable constraints. However, I would not disable auto
> solving when this does not match, I would have a generic algorithm, and
> wait for field testing before deciding if people are happy with the
> results or if they prefer to rewrite their constraints in a saner way
> to have a straightforward interpretation of the solver results.
> 

I get your points. However, I don't think 'field testing' is really
going to change much here. With no restrictions imposed since EAPI 4,
there were no more than 10 cases for those 'complex' constraints. Sadly,
most of them were either simply invalid or could be replaced by
something simpler and shorter.

Sure, I don't mind you trying to implement a full parser and play with
it all. However, I don't think it's worth to make the spec a few pages
longer just for the sake of it.

-- 
Best regards,
Michał Górny

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 988 bytes --]