1 |
On wto, 2017-05-30 at 20:46 +0200, Alexis Ballier wrote: |
2 |
> On Tue, 30 May 2017 20:11:38 +0200 |
3 |
> Michał Górny <mgorny@g.o> wrote: |
4 |
> [...] |
5 |
> > > > Of course, we could just validate all the possible cases via |
6 |
> > > > repoman, and reject the ebuild if there's at least one conflict |
7 |
> > > > between them. Not sure how to express that properly in the spec |
8 |
> > > > though. Not sure how it would work practically. |
9 |
> > > |
10 |
> > > Adding a 2^n check to repoman isn't gonna work well. |
11 |
> > > |
12 |
> > |
13 |
> > I'm not saying it's the most optimal algorithm of verifying |
14 |
> > the correctness of the constraints. It's just the one that's quite |
15 |
> > obvious -- relatively simple and reliable. If someone can come up with |
16 |
> > something better that covers at least the most common cases, I'm all |
17 |
> > for it. |
18 |
> > |
19 |
> > That said, this wouldn't be that much of a problem if we can keep the |
20 |
> > n low. For a start, we can rule out all flags that don't appear |
21 |
> > in REQUIRED_USE at all. Furthermore, I think we could also ignore |
22 |
> > the constraints for flags that don't appear there at least 'twice', |
23 |
> > and so on. |
24 |
> |
25 |
> :) |
26 |
> |
27 |
> You're applying classical techniques to lower the size of a SAT |
28 |
> instance so that your exponential algorithm does not explode, but it's |
29 |
> still hard. |
30 |
> |
31 |
> I'm not sure what you want: If you want to detect that there is an |
32 |
> impossible constraint, well, ebuild writer will notice soon enough when |
33 |
> testing it. If you want to detect that there is a way to have a |
34 |
> conflict between useflags, then there will be valid cases where this |
35 |
> will happen. |
36 |
> |
37 |
> That said, assuming we have REQUIRED_USE in CNF form, its negation is |
38 |
> in DNF form. Solving SAT on DNF formulas is easy (linear I think), and |
39 |
> this would give you an assignment of useflags triggering an impossible |
40 |
> constraint. e.g. 'foo? ( bar )' with USE='foo -bar' in make.conf. |
41 |
> This could be used to trigger a repoman warning but basically every |
42 |
> single ebuild would trigger those. |
43 |
|
44 |
Not sure if we understand each other. |
45 |
|
46 |
I'd like the constraints to be plain straightforward, to the point of |
47 |
having only one acceptable solution. No special Portage-style algorithms |
48 |
that attempt to provide a reasonable solution to unreasonable input, |
49 |
resulting in horrible solutions that need 20 more hacks every few |
50 |
months. |
51 |
|
52 |
For example: |
53 |
|
54 |
foo? ( bar ) |
55 |
|
56 |
would mean 'if you have USE=foo, then USE=bar is enabled as well'. Not |
57 |
'find some random solution which satisfies this'. In other words, here |
58 |
changing USE=foo into USE=-foo is not an acceptable solution. |
59 |
|
60 |
Now, this also means that every constraint that can't be solved in this |
61 |
easy fashion is invalid. We want to detect that, and warn the developer. |
62 |
Some of those could be tricky. Simple example: |
63 |
|
64 |
foo? ( baz ) bar? ( !baz ) |
65 |
|
66 |
This one is invalid because USE='foo bar' requires both 'baz' and '!baz' |
67 |
as a solution. Remember that we don't want to do any changes besides |
68 |
what's explicitly written there, no guessing. However, the following |
69 |
should be valid: |
70 |
|
71 |
foo? ( baz ) bar? ( !foo !baz ) |
72 |
|
73 |
Because now we clearly indicate that USE=bar disables USE=foo, |
74 |
and therefore makes the first constraint inapplicable. It clearly |
75 |
indicates course of action for all combinations: |
76 |
|
77 |
foo bar baz -> foo bar baz |
78 |
F F F -> [valid] |
79 |
F F T -> [valid] |
80 |
F T F -> [valid] |
81 |
F T T -> F T F |
82 |
T F F -> T F T |
83 |
T F T -> [valid] |
84 |
T T F -> F T F |
85 |
T T T -> F T F |
86 |
|
87 |
-- |
88 |
Best regards, |
89 |
Michał Górny |