From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <gentoo-portage-dev+bounces-5895-garchives=archives.gentoo.org@lists.gentoo.org>
Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80])
(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
(No client certificate requested)
by finch.gentoo.org (Postfix) with ESMTPS id 6783313832E
for <garchives@archives.gentoo.org>; Fri, 5 Aug 2016 04:34:47 +0000 (UTC)
Received: from pigeon.gentoo.org (localhost [127.0.0.1])
by pigeon.gentoo.org (Postfix) with SMTP id 4F7EEE0913;
Fri, 5 Aug 2016 04:34:44 +0000 (UTC)
Received: from smtp.gentoo.org (smtp.gentoo.org [140.211.166.183])
(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
(No client certificate requested)
by pigeon.gentoo.org (Postfix) with ESMTPS id 46129E090B
for <gentoo-portage-dev@lists.gentoo.org>; Fri, 5 Aug 2016 04:34:43 +0000 (UTC)
Received: from x51r2.ad.gaikai.biz (unknown [100.42.98.197])
(using TLSv1.2 with cipher ECDHE-RSA-AES128-SHA256 (128/128 bits))
(No client certificate requested)
(Authenticated sender: zmedico)
by smtp.gentoo.org (Postfix) with ESMTPSA id BA86A340B7A;
Fri, 5 Aug 2016 04:34:41 +0000 (UTC)
From: Zac Medico <zmedico@gentoo.org>
To: gentoo-portage-dev@lists.gentoo.org
Cc: Zac Medico <zmedico@gentoo.org>
Subject: [gentoo-portage-dev] [PATCH] depgraph._serialize_tasks: improve runtime cycle handling (bug 590514)
Date: Thu, 4 Aug 2016 21:33:59 -0700
Message-Id: <1470371639-8324-1-git-send-email-zmedico@gentoo.org>
X-Mailer: git-send-email 2.7.4
Precedence: bulk
List-Post: <mailto:gentoo-portage-dev@lists.gentoo.org>
List-Help: <mailto:gentoo-portage-dev+help@lists.gentoo.org>
List-Unsubscribe: <mailto:gentoo-portage-dev+unsubscribe@lists.gentoo.org>
List-Subscribe: <mailto:gentoo-portage-dev+subscribe@lists.gentoo.org>
List-Id: Gentoo Linux mail <gentoo-portage-dev.gentoo.org>
X-BeenThere: gentoo-portage-dev@lists.gentoo.org
Reply-to: gentoo-portage-dev@lists.gentoo.org
X-Archives-Salt: c7a116a1-6b34-4864-bd0c-392c6914a4b4
X-Archives-Hash: 23fb8cfa5e8c8ad207c5e42e65024742
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