Sorting of choices by new_slot_count causes the order of choices specified in the ebuild to be discarded, and new_slot_count may have variance related to the order that packages are added to the graph. This variance can contribute to outcomes that appear to be random, like when catalyst stage1 builds sometimes pull in paludis to satisfy perl-cleaner dependencies.
Meanwhile, the order specified in the ebuild has no variance, and the preferences that it specifies can serve as a crucial sources of guidance. Therefore, take advantage of the order specified in the ebuild whenever possible, and use new_slot_count only when it is needed to select optimal choices from DNF (as in bug 632026). This fixes random outcomes in the unit test for bug 645002. Previously, the unit test pulled in paludis randomly unless portage-utils was added to the arguments. With this patch, the portage-utils argument is no longer needed for the unit test to succeed consistently. The perl-cleaner dependencies do not have any overlapping || deps, so the DNF conversion and new_slot_count sorting do not apply, and the first choice is preferred regardless of the number of slots that it pulls in: || ( ( sys-apps/portage app-portage/portage-utils ) sys-apps/pkgcore sys-apps/paludis ) The _overlap_dnf function now returns the argument object when there is no overlap, so OverlapDNFTestCase has to be adjusted to account for this. Bug: https://bugs.gentoo.org/645002 Fixes: 9fdaf9bdbdf5 ("dep_check: use DNF to optimize overlapping virtual || deps (bug 632026)") --- pym/portage/dep/dep_check.py | 49 ++++++++++++++++++---- pym/portage/tests/dep/test_overlap_dnf.py | 2 +- .../resolver/test_virtual_minimize_children.py | 12 +++--- 3 files changed, 47 insertions(+), 16 deletions(-) diff --git a/pym/portage/dep/dep_check.py b/pym/portage/dep/dep_check.py index 7e5a3186e..2896e2389 100644 --- a/pym/portage/dep/dep_check.py +++ b/pym/portage/dep/dep_check.py @@ -298,7 +298,8 @@ class _dep_choice(SlotObject): __slots__ = ('atoms', 'slot_map', 'cp_map', 'all_available', 'all_installed_slots', 'new_slot_count') -def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None): +def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None, + minimize_slots=False): """ Takes an unreduced and reduced deplist and removes satisfied dependencies. Returned deplist contains steps that must be taken to satisfy dependencies. @@ -314,7 +315,8 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None): for x, satisfied in zip(unreduced, reduced): if isinstance(x, list): unresolved += dep_zapdeps(x, satisfied, myroot, - use_binaries=use_binaries, trees=trees) + use_binaries=use_binaries, trees=trees, + minimize_slots=minimize_slots) elif not satisfied: unresolved.append(x) return unresolved @@ -386,7 +388,8 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None): for x, satisfied in zip(deps, satisfieds): if isinstance(x, list): atoms = dep_zapdeps(x, satisfied, myroot, - use_binaries=use_binaries, trees=trees) + use_binaries=use_binaries, trees=trees, + minimize_slots=minimize_slots) else: atoms = [x] if vardb is None: @@ -663,9 +666,28 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None): for choices in choice_bins: if len(choices) < 2: continue - # Prefer choices with all_installed_slots for bug #480736, and - # choices with a smaller number of new slots for bug #632026. - choices.sort(key=lambda x: (not x.all_installed_slots, x.new_slot_count)) + + sort_keys =  + # Prefer choices with all_installed_slots for bug #480736. + sort_keys.append(lambda x: not x.all_installed_slots) + + if minimize_slots: + # Prefer choices having fewer new slots. When used with DNF form, + # this can eliminate unecessary packages that depclean would + # ultimately eliminate (see bug 632026). Only use this behavior + # when deemed necessary by the caller, since this will discard the + # order specified in the ebuild, and the preferences specified + # there can serve as a crucial sources of guidance (see bug 645002). + + # NOTE: Under some conditions, new_slot_count value may have some + # variance from one calculation to the next because it depends on + # the order that packages are added to the graph. This variance can + # contribute to outcomes that appear to be random. Meanwhile, + # the order specified in the ebuild is without variance, so it + # does not have this problem. + sort_keys.append(lambda x: x.new_slot_count) + + choices.sort(key=lambda x: tuple(f(x) for f in sort_keys)) for choice_1 in choices[1:]: cps = set(choice_1.cp_map) for choice_2 in choices: @@ -792,8 +814,11 @@ def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None, except ParseError as e: return [0, "%s" % (e,)] + dnf = False if mysettings.local_config: # if not repoman + orig_split = mysplit mysplit = _overlap_dnf(mysplit) + dnf = mysplit is not orig_split mysplit2 = dep_wordreduce(mysplit, mysettings, mydbapi, mode, use_cache=use_cache) @@ -805,7 +830,7 @@ def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None, writemsg("mysplit2: %s\n" % (mysplit2), 1) selected_atoms = dep_zapdeps(mysplit, mysplit2, myroot, - use_binaries=use_binaries, trees=trees) + use_binaries=use_binaries, trees=trees, minimize_slots=dnf) return [1, selected_atoms] @@ -817,6 +842,12 @@ def _overlap_dnf(dep_struct): "|| ( foo bar ) || ( bar baz )" as in bug #632026. Non-overlapping groups are excluded from the conversion, since DNF leads to exponential explosion of the formula. + + When dep_struct does not contain any overlapping groups, no DNF + conversion will be performed, and dep_struct will be returned as-is. + Callers can detect this case by checking if the returned object has + the same identity as dep_struct. If the identity is different, then + DNF conversion was performed. """ if not _contains_disjunction(dep_struct): return dep_struct @@ -847,6 +878,7 @@ def _overlap_dnf(dep_struct): # group together disjunctions having atom.cp overlap traversed = set() + overlap = False for cp in overlap_graph: if cp in traversed: continue @@ -863,6 +895,7 @@ def _overlap_dnf(dep_struct): stack.append(other_cp) if len(disjunctions) > 1: + overlap = True # convert overlapping disjunctions to DNF result.extend(_dnf_convert( sorted(disjunctions.values(), key=order_key))) @@ -870,7 +903,7 @@ def _overlap_dnf(dep_struct): # pass through non-overlapping disjunctions result.append(disjunctions.popitem()) - return result + return result if overlap else dep_struct def _iter_flatten(dep_struct): diff --git a/pym/portage/tests/dep/test_overlap_dnf.py b/pym/portage/tests/dep/test_overlap_dnf.py index 79b3e8e46..ee48e5556 100644 --- a/pym/portage/tests/dep/test_overlap_dnf.py +++ b/pym/portage/tests/dep/test_overlap_dnf.py @@ -12,7 +12,7 @@ class OverlapDNFTestCase(TestCase): test_cases = ( ( '|| ( cat/A cat/B ) cat/E || ( cat/C cat/D )', - ['cat/E', ['||', 'cat/A', 'cat/B'], ['||', 'cat/C', 'cat/D']], + [['||', 'cat/A', 'cat/B'], 'cat/E', ['||', 'cat/C', 'cat/D']], ), ( '|| ( cat/A cat/B ) cat/D || ( cat/B cat/C )', diff --git a/pym/portage/tests/resolver/test_virtual_minimize_children.py b/pym/portage/tests/resolver/test_virtual_minimize_children.py index 287445e58..b566cb592 100644 --- a/pym/portage/tests/resolver/test_virtual_minimize_children.py +++ b/pym/portage/tests/resolver/test_virtual_minimize_children.py @@ -168,17 +168,15 @@ class VirtualMinimizeChildrenTestCase(TestCase): } test_cases = ( - # Test bug 645002, where we want to prefer choices - # based on the number of new slots rather than the total - # number of slots. This is necessary so that perl-cleaner's - # deps are satisfied by the ( portage portage-utils ) - # choice which has a larger total number of slots than the - # paludis choice. + # Test bug 645002, where paludis was selected to satisfy a + # perl-cleaner dependency because that choice contained fewer + # packages than the ( portage portage-utils ) choice which + # should have been preferred according to the order of + # choices specified in the ebuild. ResolverPlaygroundTestCase( [ 'app-admin/perl-cleaner', 'virtual/package-manager', - 'app-portage/portage-utils', ], all_permutations=True, success=True, -- 2.13.6