[gentoo-portage-dev] [PATCH] _serialize_tasks: limit scope of dropped circular dependencies

[Zac Medico]

Ensure that all members of a buildtime dependency cycle are merged
as a group, such that packages which depend on one or more members
of the group will only be merged *after* the entire group has been
merged.

This extends runtime cycle handling to also handle buildtime cycles
in cases where the buildtime dependencies happen to be satisfied by
installed packages. In situations when this is necessary, it is
desirable to rely on the old installed instances of these packages
as little as possible, since they might have been broken by the
upgrade of a package that is a member of the dependency cycle.
Upgrading members of the cycle as a group effectively minimizes
reliance on the old installed package instances, avoiding some cases
of bug 199856. For example, it should avoid bug 703676, where
libspectre reportedly failed to build against an old installed
instance of ghostscript-gpl.

Bug: https://bugs.gentoo.org/199856
Bug: https://bugs.gentoo.org/690436
Bug: https://bugs.gentoo.org/703676
---
 lib/_emerge/depgraph.py                       | 91 +++++++++++--------
 .../tests/resolver/test_merge_order.py        | 25 ++++-
 2 files changed, 75 insertions(+), 41 deletions(-)

diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index ed7aeccad..58255681c 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -7636,21 +7636,6 @@ class depgraph(object):
 				break
 			removed_nodes.clear()
 		self._merge_order_bias(mygraph)
-		def cmp_circular_bias(n1, n2):
-			"""
-			RDEPEND is stronger than PDEPEND and this function
-			measures such a strength bias within a circular
-			dependency relationship.
-			"""
-			n1_n2_medium = n2 in mygraph.child_nodes(n1,
-				ignore_priority=priority_range.ignore_medium_soft)
-			n2_n1_medium = n1 in mygraph.child_nodes(n2,
-				ignore_priority=priority_range.ignore_medium_soft)
-			if n1_n2_medium == n2_n1_medium:
-				return 0
-			elif n1_n2_medium:
-				return 1
-			return -1
 		myblocker_uninstalls = self._dynamic_config._blocker_uninstalls.copy()
 		retlist=[]
 		# Contains uninstall tasks that have been scheduled to
@@ -7811,7 +7796,8 @@ class depgraph(object):
 			self._spinner_update()
 			selected_nodes = None
 			ignore_priority = None
-			if drop_satisfied or (prefer_asap and asap_nodes):
+			cycle_digraph = None
+			if prefer_asap and asap_nodes:
 				priority_range = DepPrioritySatisfiedRange
 			else:
 				priority_range = DepPriorityNormalRange
@@ -7893,11 +7879,12 @@ class depgraph(object):
 							break
 
 			if not selected_nodes:
-				nodes = get_nodes(ignore_priority=priority_range.ignore_medium)
-				if nodes:
-					mergeable_nodes = set(nodes)
+
+				def find_smallest_cycle(mergeable_nodes, priority_ranges):
 					if prefer_asap and asap_nodes:
 						nodes = asap_nodes
+					else:
+						nodes = mergeable_nodes
 					# When gathering the nodes belonging to a runtime cycle,
 					# we want to minimize the number of nodes gathered, since
 					# this tends to produce a more optimal merge order.
@@ -7908,21 +7895,44 @@ class depgraph(object):
 					# that depend on them. Therefore, we search for the
 					# smallest cycle in order to try and identify and prefer
 					# these smaller independent cycles.
-					ignore_priority = priority_range.ignore_medium_soft
 					smallest_cycle = None
+					ignore_priority = None
 					for node in nodes:
 						if not mygraph.parent_nodes(node):
 							continue
-						selected_nodes = set()
-						if gather_deps(ignore_priority,
-							mergeable_nodes, selected_nodes, node):
-							if smallest_cycle is None or \
-								len(selected_nodes) < len(smallest_cycle):
-								smallest_cycle = selected_nodes
+						for local_priority_range in priority_ranges:
+							selected_nodes = set()
+							if gather_deps(local_priority_range.ignore_medium_soft,
+								mergeable_nodes, selected_nodes, node):
+								if smallest_cycle is None or \
+									len(selected_nodes) < len(smallest_cycle):
+									smallest_cycle = selected_nodes
+									ignore_priority = local_priority_range.ignore_medium_soft
+								break
+
+					return smallest_cycle, ignore_priority
 
-					selected_nodes = smallest_cycle
+				priority_ranges = []
+				if priority_range is not DepPriorityNormalRange:
+					priority_ranges.append(DepPriorityNormalRange)
+				priority_ranges.append(priority_range)
+				if drop_satisfied and priority_range is not DepPrioritySatisfiedRange:
+					priority_ranges.append(DepPrioritySatisfiedRange)
 
-					if selected_nodes is not None:
+				for local_priority_range in priority_ranges:
+					mergeable_nodes = set(get_nodes(ignore_priority=local_priority_range.ignore_medium))
+					if mergeable_nodes:
+						selected_nodes, ignore_priority = find_smallest_cycle(mergeable_nodes, priority_ranges)
+						if selected_nodes:
+							break
+
+				if not selected_nodes:
+					if prefer_asap and asap_nodes:
+						# We failed to find any asap nodes to merge, so ignore
+						# them for the next iteration.
+						prefer_asap = False
+						continue
+				else:
 						cycle_digraph = mygraph.copy()
 						cycle_digraph.difference_update([x for x in
 							cycle_digraph if x not in selected_nodes])
@@ -7949,12 +7959,6 @@ class depgraph(object):
 								writemsg("runtime cycle leaf: %s\n\n" %
 									(selected_nodes[0],), noiselevel=-1)
 
-					if prefer_asap and asap_nodes and not selected_nodes:
-						# We failed to find any asap nodes to merge, so ignore
-						# them for the next iteration.
-						prefer_asap = False
-						continue
-
 			if selected_nodes and ignore_priority is not None:
 				# Try to merge ignored medium_soft deps as soon as possible
 				# if they're not satisfied by installed packages.
@@ -7976,10 +7980,21 @@ class depgraph(object):
 						# Merge PDEPEND asap for bug #180045.
 						asap_nodes.append(child)
 
-			if selected_nodes and len(selected_nodes) > 1:
-				if not isinstance(selected_nodes, list):
-					selected_nodes = list(selected_nodes)
-				selected_nodes.sort(key=cmp_sort_key(cmp_circular_bias))
+			if selected_nodes and len(selected_nodes) > 1 and cycle_digraph is not None:
+				# Sort nodes to account for direct circular relationships. Relevant
+				# priorities here are: runtime < buildtime < buildtime slot operator
+				ignore_priorities = [lambda priority: not priority.buildtime, lambda priority: not priority.buildtime_slot_op]
+				selected_nodes = []
+				while cycle_digraph:
+					for ignore_priority in ignore_priorities:
+						leaves = cycle_digraph.leaf_nodes(ignore_priority=ignore_priority)
+						if leaves:
+							cycle_digraph.difference_update(leaves)
+							selected_nodes.extend(leaves)
+							break
+					else:
+						selected_nodes.extend(cycle_digraph)
+						break
 
 			if not selected_nodes and myblocker_uninstalls:
 				# An Uninstall task needs to be executed in order to
diff --git a/lib/portage/tests/resolver/test_merge_order.py b/lib/portage/tests/resolver/test_merge_order.py
index 74e826661..11752d71e 100644
--- a/lib/portage/tests/resolver/test_merge_order.py
+++ b/lib/portage/tests/resolver/test_merge_order.py
@@ -81,6 +81,13 @@ class MergeOrderTestCase(TestCase):
 				"DEPEND": "app-misc/circ-satisfied-a",
 				"RDEPEND": "app-misc/circ-satisfied-a",
 			},
+			"app-misc/circ-direct-a-1": {
+				"RDEPEND": "app-misc/circ-direct-b",
+			},
+			"app-misc/circ-direct-b-1": {
+				"RDEPEND": "app-misc/circ-direct-a",
+				"DEPEND": "app-misc/circ-direct-a",
+			},
 			"app-misc/circ-smallest-a-1": {
 				"RDEPEND": "app-misc/circ-smallest-b",
 			},
@@ -220,6 +227,13 @@ class MergeOrderTestCase(TestCase):
 		}
 
 		installed = {
+			"app-misc/circ-direct-a-1": {
+				"RDEPEND": "app-misc/circ-direct-b",
+			},
+			"app-misc/circ-direct-b-1": {
+				"RDEPEND": "app-misc/circ-direct-a",
+				"DEPEND": "app-misc/circ-direct-a",
+			},
 			"app-misc/circ-buildtime-a-0": {},
 			"app-misc/circ-satisfied-a-0": {
 				"RDEPEND": "app-misc/circ-satisfied-b",
@@ -295,6 +309,12 @@ class MergeOrderTestCase(TestCase):
 		}
 
 		test_cases = (
+			ResolverPlaygroundTestCase(
+				["app-misc/circ-direct-a", "app-misc/circ-direct-b"],
+				success = True,
+				all_permutations = True,
+				mergelist = ["app-misc/circ-direct-a-1", "app-misc/circ-direct-b-1"],
+			),
 			ResolverPlaygroundTestCase(
 				["app-misc/some-app-a"],
 				success = True,
@@ -321,9 +341,8 @@ class MergeOrderTestCase(TestCase):
 				ambiguous_merge_order = True,
 				# The following merge order assertion reflects optimal order for
 				# a circular relationship which is DEPEND in one direction and
-				# RDEPEND in the other. The assertion currently fails, and the
-				# patch for bug 690436 will fix it.
-				#merge_order_assertions = (("app-misc/circ-buildtime-a-1", "app-misc/circ-buildtime-c-1"),),
+				# RDEPEND in the other.
+				merge_order_assertions = (("app-misc/circ-buildtime-a-1", "app-misc/circ-buildtime-c-1"),),
 				mergelist = [("app-misc/circ-buildtime-b-1", "app-misc/circ-buildtime-c-1", "app-misc/circ-buildtime-a-1"), "app-misc/some-app-c-1"]),
 			# Test optimal merge order for a circular dep that is
 			# RDEPEND in one direction and PDEPEND in the other.
-- 
2.21.0