Gentoo Archives: gentoo-portage-dev

From: Zac Medico <zmedico@g.o>
To: gentoo-portage-dev@l.g.o
Cc: Zac Medico <zmedico@g.o>
Subject: [gentoo-portage-dev] [PATCH] depgraph._serialize_tasks: improve runtime cycle handling (bug 590514)
Date: Fri, 05 Aug 2016 04:34:47
Message-Id: 1470371639-8324-1-git-send-email-zmedico@gentoo.org
1 Previously, it was possible for _serialize_tasks to count some
2 dependencies of a runtime cycle as part of that cycle, leading to
3 sub-optimal merge order for these dependencies because they got
4 grouped together with the cycle in the overall merge order. Fix
5 it to separate these dependencies from the cycle, and merge them
6 earlier.
7
8 X-Gentoo-Bug: 590514
9 X-Gentoo-Bug-url: https://bugs.gentoo.org/show_bug.cgi?id=590514
10 ---
11 pym/_emerge/depgraph.py | 50 +++++++--------
12 .../resolver/test_runtime_cycle_merge_order.py | 72 ++++++++++++++++++++++
13 2 files changed, 98 insertions(+), 24 deletions(-)
14 create mode 100644 pym/portage/tests/resolver/test_runtime_cycle_merge_order.py
15
16 diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
17 index fc957f5..26037ad 100644
18 --- a/pym/_emerge/depgraph.py
19 +++ b/pym/_emerge/depgraph.py
20 @@ -7415,36 +7415,38 @@ class depgraph(object):
21 selected_nodes = set()
22 if gather_deps(ignore_priority,
23 mergeable_nodes, selected_nodes, node):
24 - # When selecting asap_nodes, we need to ensure
25 - # that we haven't selected a large runtime cycle
26 - # that is obviously sub-optimal. This will be
27 - # obvious if any of the non-asap selected_nodes
28 - # is a leaf node when medium_soft deps are
29 - # ignored.
30 - if prefer_asap and asap_nodes and \
31 - len(selected_nodes) > 1:
32 - for node in selected_nodes.difference(
33 - asap_nodes):
34 - if not mygraph.child_nodes(node,
35 - ignore_priority =
36 - DepPriorityNormalRange.ignore_medium_soft):
37 - selected_nodes = None
38 - break
39 - if selected_nodes:
40 - if smallest_cycle is None or \
41 - len(selected_nodes) < len(smallest_cycle):
42 - smallest_cycle = selected_nodes
43 + if smallest_cycle is None or \
44 + len(selected_nodes) < len(smallest_cycle):
45 + smallest_cycle = selected_nodes
46
47 selected_nodes = smallest_cycle
48
49 - if selected_nodes and debug:
50 - writemsg("\nruntime cycle digraph (%s nodes):\n\n" %
51 - (len(selected_nodes),), noiselevel=-1)
52 + if selected_nodes is not None:
53 cycle_digraph = mygraph.copy()
54 cycle_digraph.difference_update([x for x in
55 cycle_digraph if x not in selected_nodes])
56 - cycle_digraph.debug_print()
57 - writemsg("\n", noiselevel=-1)
58 +
59 + leaves = cycle_digraph.leaf_nodes()
60 + if leaves:
61 + # NOTE: This case should only be triggered when
62 + # prefer_asap is True, since otherwise these
63 + # leaves would have been selected to merge
64 + # before this point. Since these "leaves" may
65 + # actually have some low-priority dependencies
66 + # that we have intentionally ignored, select
67 + # only one node here, so that merge order
68 + # accounts for as many dependencies as possible.
69 + selected_nodes = [leaves[0]]
70 +
71 + if debug:
72 + writemsg("\nruntime cycle digraph (%s nodes):\n\n" %
73 + (len(selected_nodes),), noiselevel=-1)
74 + cycle_digraph.debug_print()
75 + writemsg("\n", noiselevel=-1)
76 +
77 + if leaves:
78 + writemsg("runtime cycle leaf: %s\n\n" %
79 + (selected_nodes[0],), noiselevel=-1)
80
81 if prefer_asap and asap_nodes and not selected_nodes:
82 # We failed to find any asap nodes to merge, so ignore
83 diff --git a/pym/portage/tests/resolver/test_runtime_cycle_merge_order.py b/pym/portage/tests/resolver/test_runtime_cycle_merge_order.py
84 new file mode 100644
85 index 0000000..438d9cb
86 --- /dev/null
87 +++ b/pym/portage/tests/resolver/test_runtime_cycle_merge_order.py
88 @@ -0,0 +1,72 @@
89 +# Copyright 2016 Gentoo Foundation
90 +# Distributed under the terms of the GNU General Public License v2
91 +
92 +from portage.tests import TestCase
93 +from portage.tests.resolver.ResolverPlayground import (ResolverPlayground,
94 + ResolverPlaygroundTestCase)
95 +
96 +
97 +class RuntimeCycleMergeOrderTestCase(TestCase):
98 +
99 + def testRuntimeCycleMergeOrder(self):
100 + ebuilds = {
101 + 'app-misc/plugins-consumer-1' : {
102 + 'EAPI': '6',
103 + 'DEPEND' : 'app-misc/plugin-b:=',
104 + 'RDEPEND' : 'app-misc/plugin-b:=',
105 + },
106 + 'app-misc/plugin-b-1' : {
107 + 'EAPI': '6',
108 + 'RDEPEND' : 'app-misc/runtime-cycle-b',
109 + 'PDEPEND': 'app-misc/plugins-consumer',
110 + },
111 + 'app-misc/runtime-cycle-b-1' : {
112 + 'RDEPEND' : 'app-misc/plugin-b app-misc/branch-b',
113 + },
114 + 'app-misc/branch-b-1' : {
115 + 'RDEPEND' : 'app-misc/leaf-b app-misc/branch-c',
116 + },
117 + 'app-misc/leaf-b-1' : {},
118 + 'app-misc/branch-c-1' : {
119 + 'RDEPEND' : 'app-misc/runtime-cycle-c app-misc/runtime-c',
120 + },
121 + 'app-misc/runtime-cycle-c-1' : {
122 + 'RDEPEND' : 'app-misc/branch-c',
123 + },
124 + 'app-misc/runtime-c-1' : {
125 + 'RDEPEND' : 'app-misc/branch-d',
126 + },
127 + 'app-misc/branch-d-1' : {
128 + 'RDEPEND' : 'app-misc/leaf-d app-misc/branch-e',
129 + },
130 + 'app-misc/branch-e-1' : {
131 + 'RDEPEND' : 'app-misc/leaf-e',
132 + },
133 + 'app-misc/leaf-d-1' : {},
134 + 'app-misc/leaf-e-1' : {},
135 + }
136 +
137 + test_cases = (
138 + ResolverPlaygroundTestCase(
139 + ['app-misc/plugin-b'],
140 + success = True,
141 + ambiguous_merge_order = True,
142 + mergelist = [
143 + ('app-misc/leaf-b-1', 'app-misc/leaf-d-1', 'app-misc/leaf-e-1'),
144 + ('app-misc/branch-d-1', 'app-misc/branch-e-1'),
145 + 'app-misc/runtime-c-1',
146 + ('app-misc/runtime-cycle-c-1', 'app-misc/branch-c-1'),
147 + 'app-misc/branch-b-1',
148 + ('app-misc/runtime-cycle-b-1', 'app-misc/plugin-b-1'),
149 + 'app-misc/plugins-consumer-1',
150 + ],
151 + ),
152 + )
153 +
154 + playground = ResolverPlayground(ebuilds=ebuilds)
155 + try:
156 + for test_case in test_cases:
157 + playground.run_TestCase(test_case)
158 + self.assertEqual(test_case.test_success, True, test_case.fail_msg)
159 + finally:
160 + playground.cleanup()
161 --
162 2.7.4

Replies