1 |
commit: 9fdaf9bdbdf500b7120aa95cb2ca421b931e6cea |
2 |
Author: Zac Medico <zmedico <AT> gentoo <DOT> org> |
3 |
AuthorDate: Sun Nov 5 22:21:43 2017 +0000 |
4 |
Commit: Zac Medico <zmedico <AT> gentoo <DOT> org> |
5 |
CommitDate: Tue Nov 14 03:35:19 2017 +0000 |
6 |
URL: https://gitweb.gentoo.org/proj/portage.git/commit/?id=9fdaf9bd |
7 |
|
8 |
dep_check: use DNF to optimize overlapping virtual || deps (bug 632026) |
9 |
|
10 |
Deps like these: |
11 |
|
12 |
|| ( foo bar ) || ( bar baz ) |
13 |
|
14 |
Translate to disjunctive normal form (DNF): |
15 |
|
16 |
|| ( ( foo bar ) ( foo baz ) ( bar bar ) ( bar baz ) ) |
17 |
|
18 |
Using DNF, if none of the packages are currently installed, |
19 |
then the ( bar bar ) choice will be automatically preferred |
20 |
since it is satisfied by the fewest number of packages. |
21 |
If the ( foo baz ) choice is already satisfied, then that |
22 |
choice will be preferred instead. |
23 |
|
24 |
Since DNF results in exponential explosion of the formula, |
25 |
only use DNF for the parts of the dependencies that have |
26 |
overlapping atoms. |
27 |
|
28 |
In order to simplify the implementation of the dnf_convert |
29 |
function, this patch also fixes _expand_new_virtuals to |
30 |
normalize results in the same way as use_reduce (with no |
31 |
redundant nested lists). |
32 |
|
33 |
Bug: https://bugs.gentoo.org/632026 |
34 |
Reviewed-by: Manuel RĂ¼ger <mrueg <AT> gentoo.org> |
35 |
Reviewed-by: Alec Warner <antarus <AT> gentoo.org> |
36 |
|
37 |
pym/portage/dep/_dnf.py | 90 +++++++++++++ |
38 |
pym/portage/dep/dep_check.py | 136 ++++++++++++++++++- |
39 |
pym/portage/tests/dep/test_dnf_convert.py | 48 +++++++ |
40 |
pym/portage/tests/dep/test_overlap_dnf.py | 28 ++++ |
41 |
.../resolver/test_virtual_minimize_children.py | 145 +++++++++++++++++++++ |
42 |
5 files changed, 440 insertions(+), 7 deletions(-) |
43 |
|
44 |
diff --git a/pym/portage/dep/_dnf.py b/pym/portage/dep/_dnf.py |
45 |
new file mode 100644 |
46 |
index 000000000..59657fd6a |
47 |
--- /dev/null |
48 |
+++ b/pym/portage/dep/_dnf.py |
49 |
@@ -0,0 +1,90 @@ |
50 |
+# Copyright 2017 Gentoo Foundation |
51 |
+# Distributed under the terms of the GNU General Public License v2 |
52 |
+ |
53 |
+from __future__ import unicode_literals |
54 |
+ |
55 |
+import itertools |
56 |
+ |
57 |
+ |
58 |
+def dnf_convert(dep_struct): |
59 |
+ """ |
60 |
+ Convert dep_struct to disjunctive normal form (DNF), where dep_struct |
61 |
+ is either a conjunction or disjunction of the form produced by |
62 |
+ use_reduce(opconvert=True). |
63 |
+ """ |
64 |
+ # Normalize input to have a top-level conjunction. |
65 |
+ if isinstance(dep_struct, list): |
66 |
+ if dep_struct and dep_struct[0] == '||': |
67 |
+ dep_struct = [dep_struct] |
68 |
+ else: |
69 |
+ dep_struct = [dep_struct] |
70 |
+ |
71 |
+ conjunction = [] |
72 |
+ disjunctions = [] |
73 |
+ |
74 |
+ for x in dep_struct: |
75 |
+ if isinstance (x, list): |
76 |
+ assert x and x[0] == '||', \ |
77 |
+ 'Normalization error, nested conjunction found in %s' % (dep_struct,) |
78 |
+ if any(isinstance(element, list) for element in x): |
79 |
+ x_dnf = ['||'] |
80 |
+ for element in x[1:]: |
81 |
+ if isinstance(element, list): |
82 |
+ # Due to normalization, a disjunction must not be |
83 |
+ # nested directly in another disjunction, so this |
84 |
+ # must be a conjunction. |
85 |
+ assert element, 'Normalization error, empty conjunction found in %s' % (x,) |
86 |
+ assert element[0] != '||', \ |
87 |
+ 'Normalization error, nested disjunction found in %s' % (x,) |
88 |
+ element = dnf_convert(element) |
89 |
+ if contains_disjunction(element): |
90 |
+ assert (len(element) == 1 and |
91 |
+ element[0] and element[0][0] == '||'), \ |
92 |
+ 'Normalization error, expected single disjunction in %s' % (element,) |
93 |
+ x_dnf.extend(element[0][1:]) |
94 |
+ else: |
95 |
+ x_dnf.append(element) |
96 |
+ else: |
97 |
+ x_dnf.append(element) |
98 |
+ x = x_dnf |
99 |
+ disjunctions.append(x) |
100 |
+ else: |
101 |
+ conjunction.append(x) |
102 |
+ |
103 |
+ if disjunctions and (conjunction or len(disjunctions) > 1): |
104 |
+ dnf_form = ['||'] |
105 |
+ for x in itertools.product(*[x[1:] for x in disjunctions]): |
106 |
+ normalized = conjunction[:] |
107 |
+ for element in x: |
108 |
+ if isinstance(element, list): |
109 |
+ normalized.extend(element) |
110 |
+ else: |
111 |
+ normalized.append(element) |
112 |
+ dnf_form.append(normalized) |
113 |
+ result = [dnf_form] |
114 |
+ else: |
115 |
+ result = conjunction + disjunctions |
116 |
+ |
117 |
+ return result |
118 |
+ |
119 |
+ |
120 |
+def contains_disjunction(dep_struct): |
121 |
+ """ |
122 |
+ Search for a disjunction contained in dep_struct, where dep_struct |
123 |
+ is either a conjunction or disjunction of the form produced by |
124 |
+ use_reduce(opconvert=True). If dep_struct is a disjunction, then |
125 |
+ this only returns True if there is a nested disjunction. Due to |
126 |
+ normalization, recursion is only needed when dep_struct is a |
127 |
+ disjunction containing a conjunction. If dep_struct is a conjunction, |
128 |
+ then it is assumed that normalization has elevated any nested |
129 |
+ disjunctions to the top-level. |
130 |
+ """ |
131 |
+ is_disjunction = dep_struct and dep_struct[0] == '||' |
132 |
+ for x in dep_struct: |
133 |
+ if isinstance(x, list): |
134 |
+ assert x, 'Normalization error, empty conjunction found in %s' % (dep_struct,) |
135 |
+ if x[0] == '||': |
136 |
+ return True |
137 |
+ elif is_disjunction and contains_disjunction(x): |
138 |
+ return True |
139 |
+ return False |
140 |
|
141 |
diff --git a/pym/portage/dep/dep_check.py b/pym/portage/dep/dep_check.py |
142 |
index b33f7e5db..2bb9dc339 100644 |
143 |
--- a/pym/portage/dep/dep_check.py |
144 |
+++ b/pym/portage/dep/dep_check.py |
145 |
@@ -6,14 +6,20 @@ from __future__ import unicode_literals |
146 |
__all__ = ['dep_check', 'dep_eval', 'dep_wordreduce', 'dep_zapdeps'] |
147 |
|
148 |
import collections |
149 |
+import itertools |
150 |
import logging |
151 |
import operator |
152 |
|
153 |
import portage |
154 |
from portage.dep import Atom, match_from_list, use_reduce |
155 |
+from portage.dep._dnf import ( |
156 |
+ dnf_convert as _dnf_convert, |
157 |
+ contains_disjunction as _contains_disjunction, |
158 |
+) |
159 |
from portage.exception import InvalidDependString, ParseError |
160 |
from portage.localization import _ |
161 |
from portage.util import writemsg, writemsg_level |
162 |
+from portage.util.digraph import digraph |
163 |
from portage.util.SlotObject import SlotObject |
164 |
from portage.versions import vercmp, _pkg_str |
165 |
|
166 |
@@ -28,7 +34,11 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/", |
167 |
atom because it wouldn't necessarily make sense to block all the components |
168 |
of a compound virtual. When more than one new-style virtual is matched, |
169 |
the matches are sorted from highest to lowest versions and the atom is |
170 |
- expanded to || ( highest match ... lowest match ).""" |
171 |
+ expanded to || ( highest match ... lowest match ). |
172 |
+ |
173 |
+ The result is normalized in the same way as use_reduce, having a top-level |
174 |
+ conjuction, and no redundant nested lists. |
175 |
+ """ |
176 |
newsplit = [] |
177 |
mytrees = trees[myroot] |
178 |
portdb = mytrees["porttree"].dbapi |
179 |
@@ -54,14 +64,38 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/", |
180 |
portdb = trees[myroot]["bintree"].dbapi |
181 |
pprovideddict = mysettings.pprovideddict |
182 |
myuse = kwargs["myuse"] |
183 |
+ is_disjunction = mysplit and mysplit[0] == '||' |
184 |
for x in mysplit: |
185 |
if x == "||": |
186 |
newsplit.append(x) |
187 |
continue |
188 |
elif isinstance(x, list): |
189 |
- newsplit.append(_expand_new_virtuals(x, edebug, mydbapi, |
190 |
+ assert x, 'Normalization error, empty conjunction found in %s' % (mysplit,) |
191 |
+ if is_disjunction: |
192 |
+ assert x[0] != '||', \ |
193 |
+ 'Normalization error, nested disjunction found in %s' % (mysplit,) |
194 |
+ else: |
195 |
+ assert x[0] == '||', \ |
196 |
+ 'Normalization error, nested conjunction found in %s' % (mysplit,) |
197 |
+ x_exp = _expand_new_virtuals(x, edebug, mydbapi, |
198 |
mysettings, myroot=myroot, trees=trees, use_mask=use_mask, |
199 |
- use_force=use_force, **kwargs)) |
200 |
+ use_force=use_force, **kwargs) |
201 |
+ if is_disjunction: |
202 |
+ if len(x_exp) == 1: |
203 |
+ x = x_exp[0] |
204 |
+ if isinstance(x, list): |
205 |
+ # Due to normalization, a conjunction must not be |
206 |
+ # nested directly in another conjunction, so this |
207 |
+ # must be a disjunction. |
208 |
+ assert x and x[0] == '||', \ |
209 |
+ 'Normalization error, nested conjunction found in %s' % (x_exp,) |
210 |
+ newsplit.extend(x[1:]) |
211 |
+ else: |
212 |
+ newsplit.append(x) |
213 |
+ else: |
214 |
+ newsplit.append(x_exp) |
215 |
+ else: |
216 |
+ newsplit.extend(x_exp) |
217 |
continue |
218 |
|
219 |
if not isinstance(x, Atom): |
220 |
@@ -101,6 +135,8 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/", |
221 |
a.append(Atom(x.replace(x.cp, y.cp, 1))) |
222 |
if not a: |
223 |
newsplit.append(x) |
224 |
+ elif is_disjunction: |
225 |
+ newsplit.extend(a) |
226 |
elif len(a) == 1: |
227 |
newsplit.append(a[0]) |
228 |
else: |
229 |
@@ -218,11 +254,18 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/", |
230 |
newsplit.append(x) |
231 |
if atom_graph is not None: |
232 |
atom_graph.add((x, id(x)), graph_parent) |
233 |
+ elif is_disjunction: |
234 |
+ newsplit.extend(a) |
235 |
elif len(a) == 1: |
236 |
- newsplit.append(a[0]) |
237 |
+ newsplit.extend(a[0]) |
238 |
else: |
239 |
newsplit.append(['||'] + a) |
240 |
|
241 |
+ # For consistency with related functions like use_reduce, always |
242 |
+ # normalize the result to have a top-level conjunction. |
243 |
+ if is_disjunction: |
244 |
+ newsplit = [newsplit] |
245 |
+ |
246 |
return newsplit |
247 |
|
248 |
def dep_eval(deplist): |
249 |
@@ -612,9 +655,9 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None): |
250 |
for choices in choice_bins: |
251 |
if len(choices) < 2: |
252 |
continue |
253 |
- # Prefer choices with all_installed_slots for bug #480736. |
254 |
- choices.sort(key=operator.attrgetter('all_installed_slots'), |
255 |
- reverse=True) |
256 |
+ # Prefer choices with all_installed_slots for bug #480736, and |
257 |
+ # choices with a smaller number of packages for bug #632026. |
258 |
+ choices.sort(key=lambda x: (not x.all_installed_slots, len(x.slot_map))) |
259 |
for choice_1 in choices[1:]: |
260 |
cps = set(choice_1.cp_map) |
261 |
for choice_2 in choices: |
262 |
@@ -741,6 +784,9 @@ def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None, |
263 |
except ParseError as e: |
264 |
return [0, "%s" % (e,)] |
265 |
|
266 |
+ if mysettings.local_config: # if not repoman |
267 |
+ mysplit = _overlap_dnf(mysplit) |
268 |
+ |
269 |
mysplit2 = dep_wordreduce(mysplit, |
270 |
mysettings, mydbapi, mode, use_cache=use_cache) |
271 |
if mysplit2 is None: |
272 |
@@ -755,6 +801,82 @@ def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None, |
273 |
|
274 |
return [1, selected_atoms] |
275 |
|
276 |
+ |
277 |
+def _overlap_dnf(dep_struct): |
278 |
+ """ |
279 |
+ Combine overlapping || groups using disjunctive normal form (DNF), in |
280 |
+ order to minimize the number of packages chosen to satisfy cases like |
281 |
+ "|| ( foo bar ) || ( bar baz )" as in bug #632026. Non-overlapping |
282 |
+ groups are excluded from the conversion, since DNF leads to exponential |
283 |
+ explosion of the formula. |
284 |
+ """ |
285 |
+ if not _contains_disjunction(dep_struct): |
286 |
+ return dep_struct |
287 |
+ |
288 |
+ # map atom.cp to disjunctions |
289 |
+ cp_map = collections.defaultdict(list) |
290 |
+ # graph atom.cp, with edges connecting atoms in the same disjunction |
291 |
+ overlap_graph = digraph() |
292 |
+ # map id(disjunction) to index in dep_struct, for deterministic output |
293 |
+ order_map = {} |
294 |
+ order_key = lambda x: order_map[id(x)] |
295 |
+ result = [] |
296 |
+ for i, x in enumerate(dep_struct): |
297 |
+ if isinstance(x, list): |
298 |
+ assert x and x[0] == '||', \ |
299 |
+ 'Normalization error, nested conjunction found in %s' % (dep_struct,) |
300 |
+ order_map[id(x)] = i |
301 |
+ prev_cp = None |
302 |
+ for atom in _iter_flatten(x): |
303 |
+ if isinstance(atom, Atom) and not atom.blocker: |
304 |
+ cp_map[atom.cp].append(x) |
305 |
+ overlap_graph.add(atom.cp, parent=prev_cp) |
306 |
+ prev_cp = atom.cp |
307 |
+ if prev_cp is None: # only contains blockers |
308 |
+ result.append(x) |
309 |
+ else: |
310 |
+ result.append(x) |
311 |
+ |
312 |
+ # group together disjunctions having atom.cp overlap |
313 |
+ traversed = set() |
314 |
+ for cp in overlap_graph: |
315 |
+ if cp in traversed: |
316 |
+ continue |
317 |
+ disjunctions = {} |
318 |
+ stack = [cp] |
319 |
+ while stack: |
320 |
+ cp = stack.pop() |
321 |
+ traversed.add(cp) |
322 |
+ for x in cp_map[cp]: |
323 |
+ disjunctions[id(x)] = x |
324 |
+ for other_cp in itertools.chain(overlap_graph.child_nodes(cp), |
325 |
+ overlap_graph.parent_nodes(cp)): |
326 |
+ if other_cp not in traversed: |
327 |
+ stack.append(other_cp) |
328 |
+ |
329 |
+ if len(disjunctions) > 1: |
330 |
+ # convert overlapping disjunctions to DNF |
331 |
+ result.extend(_dnf_convert( |
332 |
+ sorted(disjunctions.values(), key=order_key))) |
333 |
+ else: |
334 |
+ # pass through non-overlapping disjunctions |
335 |
+ result.append(disjunctions.popitem()[1]) |
336 |
+ |
337 |
+ return result |
338 |
+ |
339 |
+ |
340 |
+def _iter_flatten(dep_struct): |
341 |
+ """ |
342 |
+ Yield nested elements of dep_struct. |
343 |
+ """ |
344 |
+ for x in dep_struct: |
345 |
+ if isinstance(x, list): |
346 |
+ for x in _iter_flatten(x): |
347 |
+ yield x |
348 |
+ else: |
349 |
+ yield x |
350 |
+ |
351 |
+ |
352 |
def dep_wordreduce(mydeplist,mysettings,mydbapi,mode,use_cache=1): |
353 |
"Reduces the deplist to ones and zeros" |
354 |
deplist=mydeplist[:] |
355 |
|
356 |
diff --git a/pym/portage/tests/dep/test_dnf_convert.py b/pym/portage/tests/dep/test_dnf_convert.py |
357 |
new file mode 100644 |
358 |
index 000000000..b92778d4a |
359 |
--- /dev/null |
360 |
+++ b/pym/portage/tests/dep/test_dnf_convert.py |
361 |
@@ -0,0 +1,48 @@ |
362 |
+# Copyright 2017 Gentoo Foundation |
363 |
+# Distributed under the terms of the GNU General Public License v2 |
364 |
+ |
365 |
+from portage.tests import TestCase |
366 |
+from portage.dep import use_reduce |
367 |
+from portage.dep._dnf import dnf_convert |
368 |
+ |
369 |
+class DNFConvertTestCase(TestCase): |
370 |
+ |
371 |
+ def testDNFConvert(self): |
372 |
+ |
373 |
+ test_cases = ( |
374 |
+ ( |
375 |
+ '|| ( A B ) || ( C D )', |
376 |
+ [['||', ['A', 'C'], ['A', 'D'], ['B', 'C'], ['B', 'D']]], |
377 |
+ ), |
378 |
+ ( |
379 |
+ '|| ( A B ) || ( B C )', |
380 |
+ [['||', ['A', 'B'], ['A', 'C'], ['B', 'B'], ['B', 'C']]], |
381 |
+ ), |
382 |
+ ( |
383 |
+ '|| ( A ( B C D ) )', |
384 |
+ [['||', 'A', ['B', 'C', 'D']]], |
385 |
+ ), |
386 |
+ ( |
387 |
+ '|| ( A ( B C D ) ) E', |
388 |
+ [['||', ['E', 'A'], ['E', 'B', 'C', 'D']]], |
389 |
+ ), |
390 |
+ ( |
391 |
+ '|| ( A ( B C ) ) || ( D E ) F', |
392 |
+ [['||', ['F', 'A', 'D'], ['F', 'A', 'E'], ['F', 'B', 'C', 'D'], ['F', 'B', 'C', 'E']]], |
393 |
+ ), |
394 |
+ ( |
395 |
+ '|| ( A ( B C || ( D E ) ) ( F G ) H )', |
396 |
+ [['||', 'A', ['B', 'C', 'D'], ['B', 'C', 'E'], ['F', 'G'], 'H']], |
397 |
+ ), |
398 |
+ ( |
399 |
+ '|| ( A ( B C || ( D E ) ) F )', |
400 |
+ [['||', 'A', ['B', 'C', 'D'], ['B', 'C', 'E'], 'F']], |
401 |
+ ), |
402 |
+ ( |
403 |
+ '|| ( A ( C || ( D E ) || ( F G ) ) H )', |
404 |
+ [['||', 'A', ['C', 'D', 'F'], ['C', 'D', 'G'], ['C', 'E', 'F'], ['C', 'E', 'G'], 'H']], |
405 |
+ ), |
406 |
+ ) |
407 |
+ |
408 |
+ for dep_str, result in test_cases: |
409 |
+ self.assertEqual(dnf_convert(use_reduce(dep_str, opconvert=True)), result) |
410 |
|
411 |
diff --git a/pym/portage/tests/dep/test_overlap_dnf.py b/pym/portage/tests/dep/test_overlap_dnf.py |
412 |
new file mode 100644 |
413 |
index 000000000..79b3e8e46 |
414 |
--- /dev/null |
415 |
+++ b/pym/portage/tests/dep/test_overlap_dnf.py |
416 |
@@ -0,0 +1,28 @@ |
417 |
+# Copyright 2017 Gentoo Foundation |
418 |
+# Distributed under the terms of the GNU General Public License v2 |
419 |
+ |
420 |
+from portage.tests import TestCase |
421 |
+from portage.dep import Atom, use_reduce |
422 |
+from portage.dep.dep_check import _overlap_dnf |
423 |
+ |
424 |
+class OverlapDNFTestCase(TestCase): |
425 |
+ |
426 |
+ def testOverlapDNF(self): |
427 |
+ |
428 |
+ test_cases = ( |
429 |
+ ( |
430 |
+ '|| ( cat/A cat/B ) cat/E || ( cat/C cat/D )', |
431 |
+ ['cat/E', ['||', 'cat/A', 'cat/B'], ['||', 'cat/C', 'cat/D']], |
432 |
+ ), |
433 |
+ ( |
434 |
+ '|| ( cat/A cat/B ) cat/D || ( cat/B cat/C )', |
435 |
+ ['cat/D', ['||', ['cat/A', 'cat/B'], ['cat/A', 'cat/C'], ['cat/B', 'cat/B'], ['cat/B', 'cat/C']]], |
436 |
+ ), |
437 |
+ ( |
438 |
+ '|| ( cat/A cat/B ) || ( cat/C cat/D ) || ( ( cat/B cat/E ) cat/F )', |
439 |
+ [['||', ['cat/A', 'cat/B', 'cat/E'], ['cat/A', 'cat/F'], ['cat/B', 'cat/B', 'cat/E'], ['cat/B', 'cat/F']], ['||', 'cat/C', 'cat/D']], |
440 |
+ ), |
441 |
+ ) |
442 |
+ |
443 |
+ for dep_str, result in test_cases: |
444 |
+ self.assertEqual(_overlap_dnf(use_reduce(dep_str, token_class=Atom, opconvert=True)), result) |
445 |
|
446 |
diff --git a/pym/portage/tests/resolver/test_virtual_minimize_children.py b/pym/portage/tests/resolver/test_virtual_minimize_children.py |
447 |
new file mode 100644 |
448 |
index 000000000..83ae34e77 |
449 |
--- /dev/null |
450 |
+++ b/pym/portage/tests/resolver/test_virtual_minimize_children.py |
451 |
@@ -0,0 +1,145 @@ |
452 |
+# Copyright 2017 Gentoo Foundation |
453 |
+# Distributed under the terms of the GNU General Public License v2 |
454 |
+ |
455 |
+from portage.tests import TestCase |
456 |
+from portage.tests.resolver.ResolverPlayground import ( |
457 |
+ ResolverPlayground, |
458 |
+ ResolverPlaygroundTestCase, |
459 |
+) |
460 |
+ |
461 |
+class VirtualMinimizeChildrenTestCase(TestCase): |
462 |
+ |
463 |
+ def testVirtualMinimizeChildren(self): |
464 |
+ ebuilds = { |
465 |
+ 'app-misc/bar-1': { |
466 |
+ 'EAPI': '6', |
467 |
+ 'RDEPEND': 'virtual/foo' |
468 |
+ }, |
469 |
+ 'virtual/foo-1': { |
470 |
+ 'EAPI': '6', |
471 |
+ 'RDEPEND': '|| ( app-misc/A app-misc/B ) || ( app-misc/B app-misc/C )' |
472 |
+ }, |
473 |
+ 'app-misc/A-1': { |
474 |
+ 'EAPI': '6', |
475 |
+ }, |
476 |
+ 'app-misc/B-1': { |
477 |
+ 'EAPI': '6', |
478 |
+ }, |
479 |
+ 'app-misc/C-1': { |
480 |
+ 'EAPI': '6', |
481 |
+ }, |
482 |
+ } |
483 |
+ |
484 |
+ test_cases = ( |
485 |
+ # Test bug 632026, where we want to minimize the number of |
486 |
+ # packages chosen to satisfy overlapping || deps like |
487 |
+ # "|| ( foo bar ) || ( bar baz )". |
488 |
+ ResolverPlaygroundTestCase( |
489 |
+ ['app-misc/bar'], |
490 |
+ success=True, |
491 |
+ mergelist=[ |
492 |
+ 'app-misc/B-1', |
493 |
+ 'virtual/foo-1', |
494 |
+ 'app-misc/bar-1', |
495 |
+ ], |
496 |
+ ), |
497 |
+ ) |
498 |
+ |
499 |
+ playground = ResolverPlayground(debug=False, |
500 |
+ ebuilds=ebuilds) |
501 |
+ |
502 |
+ try: |
503 |
+ for test_case in test_cases: |
504 |
+ playground.run_TestCase(test_case) |
505 |
+ self.assertEqual(test_case.test_success, True, |
506 |
+ test_case.fail_msg) |
507 |
+ finally: |
508 |
+ playground.debug = False |
509 |
+ playground.cleanup() |
510 |
+ |
511 |
+ # If app-misc/A and app-misc/C are installed then |
512 |
+ # that choice should be preferred over app-misc/B. |
513 |
+ installed = { |
514 |
+ 'app-misc/A-1': { |
515 |
+ 'EAPI': '6', |
516 |
+ }, |
517 |
+ 'app-misc/C-1': { |
518 |
+ 'EAPI': '6', |
519 |
+ }, |
520 |
+ } |
521 |
+ |
522 |
+ test_cases = ( |
523 |
+ ResolverPlaygroundTestCase( |
524 |
+ ['app-misc/bar'], |
525 |
+ success=True, |
526 |
+ mergelist=[ |
527 |
+ 'virtual/foo-1', |
528 |
+ 'app-misc/bar-1', |
529 |
+ ], |
530 |
+ ), |
531 |
+ ) |
532 |
+ |
533 |
+ playground = ResolverPlayground(debug=False, |
534 |
+ ebuilds=ebuilds, installed=installed) |
535 |
+ |
536 |
+ try: |
537 |
+ for test_case in test_cases: |
538 |
+ playground.run_TestCase(test_case) |
539 |
+ self.assertEqual(test_case.test_success, True, |
540 |
+ test_case.fail_msg) |
541 |
+ finally: |
542 |
+ playground.debug = False |
543 |
+ playground.cleanup() |
544 |
+ |
545 |
+ def testOverlapSlotConflict(self): |
546 |
+ ebuilds = { |
547 |
+ 'app-misc/bar-1': { |
548 |
+ 'EAPI': '6', |
549 |
+ 'RDEPEND': 'virtual/foo' |
550 |
+ }, |
551 |
+ 'virtual/foo-1': { |
552 |
+ 'EAPI': '6', |
553 |
+ 'RDEPEND': '|| ( app-misc/A >=app-misc/B-2 ) || ( <app-misc/B-2 app-misc/C )' |
554 |
+ }, |
555 |
+ 'app-misc/A-1': { |
556 |
+ 'EAPI': '6', |
557 |
+ }, |
558 |
+ 'app-misc/B-2': { |
559 |
+ 'EAPI': '6', |
560 |
+ }, |
561 |
+ 'app-misc/B-1': { |
562 |
+ 'EAPI': '6', |
563 |
+ }, |
564 |
+ 'app-misc/C-1': { |
565 |
+ 'EAPI': '6', |
566 |
+ }, |
567 |
+ } |
568 |
+ |
569 |
+ test_cases = ( |
570 |
+ # Here the ( >=app-misc/B-2 <app-misc/B-2 ) choice is not satisfiable. |
571 |
+ ResolverPlaygroundTestCase( |
572 |
+ ['app-misc/bar'], |
573 |
+ success=True, |
574 |
+ ambiguous_merge_order=True, |
575 |
+ mergelist=[ |
576 |
+ ( |
577 |
+ 'app-misc/C-1', |
578 |
+ 'app-misc/A-1', |
579 |
+ ), |
580 |
+ 'virtual/foo-1', |
581 |
+ 'app-misc/bar-1', |
582 |
+ ] |
583 |
+ ), |
584 |
+ ) |
585 |
+ |
586 |
+ playground = ResolverPlayground(debug=False, |
587 |
+ ebuilds=ebuilds) |
588 |
+ |
589 |
+ try: |
590 |
+ for test_case in test_cases: |
591 |
+ playground.run_TestCase(test_case) |
592 |
+ self.assertEqual(test_case.test_success, True, |
593 |
+ test_case.fail_msg) |
594 |
+ finally: |
595 |
+ playground.debug = False |
596 |
+ playground.cleanup() |