depgraph._serialize_tasks: improve runtime cycle handling (bug 590514)

Previously, it was possible for _serialize_tasks to count some
dependencies of a runtime cycle as part of that cycle, leading to
sub-optimal merge order for these dependencies because they got
grouped together with the cycle in the overall merge order. Fix
it to separate these dependencies from the cycle, and merge them
earlier.

X-Gentoo-Bug: 590514
X-Gentoo-Bug-url: https://bugs.gentoo.org/show_bug.cgi?id=590514
Acked-by: Brian Dolbec <dolsen@gentoo.org>

2 files changed, 98 insertions, 24 deletions

diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index fc957f59d..26037adbe 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -7415,36 +7415,38 @@ class depgraph(object):
 						selected_nodes = set()
 						if gather_deps(ignore_priority,
 							mergeable_nodes, selected_nodes, node):
-							# When selecting asap_nodes, we need to ensure
-							# that we haven't selected a large runtime cycle
-							# that is obviously sub-optimal. This will be
-							# obvious if any of the non-asap selected_nodes
-							# is a leaf node when medium_soft deps are
-							# ignored.
-							if prefer_asap and asap_nodes and \
-								len(selected_nodes) > 1:
-								for node in selected_nodes.difference(
-									asap_nodes):
-									if not mygraph.child_nodes(node,
-										ignore_priority =
-										DepPriorityNormalRange.ignore_medium_soft):
-										selected_nodes = None
-										break
-							if selected_nodes:
-								if smallest_cycle is None or \
-									len(selected_nodes) < len(smallest_cycle):
-									smallest_cycle = selected_nodes
+							if smallest_cycle is None or \
+								len(selected_nodes) < len(smallest_cycle):
+								smallest_cycle = selected_nodes
 
 					selected_nodes = smallest_cycle
 
-					if selected_nodes and debug:
-						writemsg("\nruntime cycle digraph (%s nodes):\n\n" %
-							(len(selected_nodes),), noiselevel=-1)
+					if selected_nodes is not None:
 						cycle_digraph = mygraph.copy()
 						cycle_digraph.difference_update([x for x in
 							cycle_digraph if x not in selected_nodes])
-						cycle_digraph.debug_print()
-						writemsg("\n", noiselevel=-1)
+
+						leaves = cycle_digraph.leaf_nodes()
+						if leaves:
+							# NOTE: This case should only be triggered when
+							# prefer_asap is True, since otherwise these
+							# leaves would have been selected to merge
+							# before this point. Since these "leaves" may
+							# actually have some low-priority dependencies
+							# that we have intentionally ignored, select
+							# only one node here, so that merge order
+							# accounts for as many dependencies as possible.
+							selected_nodes = [leaves[0]]
+
+						if debug:
+							writemsg("\nruntime cycle digraph (%s nodes):\n\n" %
+								(len(selected_nodes),), noiselevel=-1)
+							cycle_digraph.debug_print()
+							writemsg("\n", noiselevel=-1)
+
+							if leaves:
+								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
diff --git a/pym/portage/tests/resolver/test_runtime_cycle_merge_order.py b/pym/portage/tests/resolver/test_runtime_cycle_merge_order.py
new file mode 100644
index 000000000..438d9cbfc
--- /dev/null
+++ b/pym/portage/tests/resolver/test_runtime_cycle_merge_order.py
@@ -0,0 +1,72 @@
+# Copyright 2016 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import (ResolverPlayground,
+	ResolverPlaygroundTestCase)
+
+
+class RuntimeCycleMergeOrderTestCase(TestCase):
+
+	def testRuntimeCycleMergeOrder(self):
+		ebuilds = {
+			'app-misc/plugins-consumer-1' : {
+				'EAPI': '6',
+				'DEPEND' : 'app-misc/plugin-b:=',
+				'RDEPEND' : 'app-misc/plugin-b:=',
+			},
+			'app-misc/plugin-b-1' : {
+				'EAPI': '6',
+				'RDEPEND' : 'app-misc/runtime-cycle-b',
+				'PDEPEND': 'app-misc/plugins-consumer',
+			},
+			'app-misc/runtime-cycle-b-1' : {
+				'RDEPEND' : 'app-misc/plugin-b app-misc/branch-b',
+			},
+			'app-misc/branch-b-1' : {
+				'RDEPEND' : 'app-misc/leaf-b app-misc/branch-c',
+			},
+			'app-misc/leaf-b-1' : {},
+			'app-misc/branch-c-1' : {
+				'RDEPEND' : 'app-misc/runtime-cycle-c app-misc/runtime-c',
+			},
+			'app-misc/runtime-cycle-c-1' : {
+				'RDEPEND' : 'app-misc/branch-c',
+			},
+			'app-misc/runtime-c-1' : {
+				'RDEPEND' : 'app-misc/branch-d',
+			},
+			'app-misc/branch-d-1' : {
+				'RDEPEND' : 'app-misc/leaf-d app-misc/branch-e',
+			},
+			'app-misc/branch-e-1' : {
+				'RDEPEND' : 'app-misc/leaf-e',
+			},
+			'app-misc/leaf-d-1' : {},
+			'app-misc/leaf-e-1' : {},
+		}
+
+		test_cases = (
+			ResolverPlaygroundTestCase(
+				['app-misc/plugin-b'],
+				success = True,
+				ambiguous_merge_order = True,
+				mergelist = [
+					('app-misc/leaf-b-1', 'app-misc/leaf-d-1', 'app-misc/leaf-e-1'),
+					('app-misc/branch-d-1', 'app-misc/branch-e-1'),
+					'app-misc/runtime-c-1',
+					('app-misc/runtime-cycle-c-1', 'app-misc/branch-c-1'),
+					'app-misc/branch-b-1',
+					('app-misc/runtime-cycle-b-1', 'app-misc/plugin-b-1'),
+					'app-misc/plugins-consumer-1',
+				],
+			),
+		)
+
+		playground = ResolverPlayground(ebuilds=ebuilds)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True, test_case.fail_msg)
+		finally:
+			playground.cleanup()