[gentoo-portage-dev] [PATCH] dep_zapdeps: sort by new_slot_count for DNF only (bug 645002)

[Zac Medico]

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()[1])
 
-	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