public inbox for gentoo-portage-dev@lists.gentoo.org
 help / color / mirror / Atom feed
* [gentoo-portage-dev] [PATCH] depgraph._serialize_tasks: improve runtime cycle handling (bug 590514)
@ 2016-08-05  4:33 Zac Medico
  2016-08-07 15:14 ` Brian Dolbec
  0 siblings, 1 reply; 3+ messages in thread
From: Zac Medico @ 2016-08-05  4:33 UTC (permalink / raw
  To: gentoo-portage-dev; +Cc: Zac Medico

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
---
 pym/_emerge/depgraph.py                            | 50 +++++++--------
 .../resolver/test_runtime_cycle_merge_order.py     | 72 ++++++++++++++++++++++
 2 files changed, 98 insertions(+), 24 deletions(-)
 create mode 100644 pym/portage/tests/resolver/test_runtime_cycle_merge_order.py

diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index fc957f5..26037ad 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 0000000..438d9cb
--- /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()
-- 
2.7.4



^ permalink raw reply related	[flat|nested] 3+ messages in thread
end of thread, other threads:[~2016-08-07 17:57 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2016-08-05  4:33 [gentoo-portage-dev] [PATCH] depgraph._serialize_tasks: improve runtime cycle handling (bug 590514) Zac Medico
2016-08-07 15:14 ` Brian Dolbec
2016-08-07 17:57   ` Zac Medico

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox