1 |
On pią, 2017-06-02 at 13:27 +0200, Alexis Ballier wrote: |
2 |
> On Thu, 01 Jun 2017 23:31:25 +0200 |
3 |
> Michał Górny <mgorny@g.o> wrote: |
4 |
> [...] |
5 |
> > > There are probably dozens of ways to make that non deterministic. |
6 |
> > > Here's one: USE='-*'. Apply '|| ( cli cgi fpm apache2 embed phpdbg |
7 |
> > > )' last; this enables 'cli'. Since it's the last one, REQUIRED_USE |
8 |
> > > is not satisfied because of 'cli? ( ^^ ( readline libedit ) )'. |
9 |
> > > If you process it first, then you enable cli and readline and are |
10 |
> > > good. |
11 |
> > |
12 |
> > You just take a second iteration, and things fall into place. That's |
13 |
> > not a problem. |
14 |
> > |
15 |
> > > > > Also, what happens if we applied all the constraints and |
16 |
> > > > > obtained some useflags setting that still fails REQUIRED_USE |
17 |
> > > > > check ? |
18 |
> > > > |
19 |
> > > > It can't happen. If you can apply all the constraints, then |
20 |
> > > > implicitly REQUIRED_USE is satisfied. If you can't apply all the |
21 |
> > > > constraints, then it just fails. Of course, we want to ultimately |
22 |
> > > > avoid that case. |
23 |
> > > |
24 |
> > > See the php example above. How do you ensure this does not happen? |
25 |
> > > |
26 |
> > > Note that your assertion 'If you can apply all the constraints, then |
27 |
> > > implicitly REQUIRED_USE is satisfied.' is false: You're changing the |
28 |
> > > values of useflags, thus might violate some previously checked |
29 |
> > > constraint. |
30 |
> > |
31 |
> > So you reiterate. Either you reach a solution (preferably there's only |
32 |
> > a single valid solution you can reach) or you hit a previous state |
33 |
> > which indicates a loop and you fail. |
34 |
> |
35 |
> |
36 |
> So, PM, for every ebuild, will need to store the (at most) 2^n states it |
37 |
> has already seen while trying to solve REQUIRED_USE and iterate until |
38 |
> it cannot proceed anymore or falls into a previous state (so that's 2^n |
39 |
> time too). That way we go from a linear time & linear space algorithm |
40 |
> to one in exponential time & space. That's probably not a good idea. |
41 |
|
42 |
I don't think that's actually going to happen. You'd have to try really |
43 |
hard to get over n-1 iterations. I mean, the only simple way I can think |
44 |
of is: |
45 |
|
46 |
b? ( a ) c? ( b ) d? ( c ) e? ( d ) ... |
47 |
|
48 |
and this only means n-1 iterations. Can you think of a better way to |
49 |
force multiple iterations that can be written without making |
50 |
REQUIRED_USE completely unreadable? How likely is that going to happen |
51 |
accidentally? |
52 |
|
53 |
> I think it's better to limit the number of iterations to some constant. |
54 |
> I'd say 1, then fail if REQUIRED_USE is still not satisfied. Maybe 2 or |
55 |
> 3 can be useful but I think it'd be much harder to provide automated |
56 |
> checks for that and much harder for ebuild writers to understand what |
57 |
> will happen with the REQUIRED_USE they're about to write. |
58 |
> |
59 |
|
60 |
Well, I don't mind setting that. All my tests (that weren't deliberately |
61 |
abusing the algorithm) were able to finish in a single iteration. 2 or 3 |
62 |
should probably be safe for all the reasonable uses. However, if we're |
63 |
not going to verify all possible values on repoman side, I think it |
64 |
would be better to have a larger limit for users, to not have things |
65 |
explode on them unnecessarily. |
66 |
|
67 |
-- |
68 |
Best regards, |
69 |
Michał Górny |