1 |
commit: 680276cc4d4faa653203366cbe3c896ac3883cf2 |
2 |
Author: Zac Medico <zmedico <AT> gentoo <DOT> org> |
3 |
AuthorDate: Wed Dec 25 08:37:18 2019 +0000 |
4 |
Commit: Zac Medico <zmedico <AT> gentoo <DOT> org> |
5 |
CommitDate: Thu Dec 26 22:56:39 2019 +0000 |
6 |
URL: https://gitweb.gentoo.org/proj/portage.git/commit/?id=680276cc |
7 |
|
8 |
_serialize_tasks: limit scope of dropped circular dependencies |
9 |
|
10 |
Ensure that all members of a buildtime dependency cycle are merged |
11 |
as a group, such that packages which depend on one or more members |
12 |
of the group will only be merged *after* the entire group has been |
13 |
merged. |
14 |
|
15 |
This extends runtime cycle handling to also handle buildtime cycles |
16 |
in cases where the buildtime dependencies happen to be satisfied by |
17 |
installed packages. In situations when this is necessary, it is |
18 |
desirable to rely on the old installed instances of these packages |
19 |
as little as possible, since they might have been broken by the |
20 |
upgrade of a package that is a member of the dependency cycle. |
21 |
Upgrading members of the cycle as a group effectively minimizes |
22 |
reliance on the old installed package instances, avoiding some cases |
23 |
of bug 199856. For example, it should avoid bug 703676, where |
24 |
libspectre reportedly failed to build against an old installed |
25 |
instance of ghostscript-gpl. |
26 |
|
27 |
Bug: https://bugs.gentoo.org/199856 |
28 |
Bug: https://bugs.gentoo.org/689644 |
29 |
Bug: https://bugs.gentoo.org/690436 |
30 |
Bug: https://bugs.gentoo.org/703676 |
31 |
Signed-off-by: Zac Medico <zmedico <AT> gentoo.org> |
32 |
|
33 |
lib/_emerge/depgraph.py | 94 +++++++++++++++----------- |
34 |
lib/portage/tests/resolver/test_merge_order.py | 25 ++++++- |
35 |
2 files changed, 78 insertions(+), 41 deletions(-) |
36 |
|
37 |
diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py |
38 |
index 0ee50d5de..bf8882774 100644 |
39 |
--- a/lib/_emerge/depgraph.py |
40 |
+++ b/lib/_emerge/depgraph.py |
41 |
@@ -7640,21 +7640,6 @@ class depgraph(object): |
42 |
break |
43 |
removed_nodes.clear() |
44 |
self._merge_order_bias(mygraph) |
45 |
- def cmp_circular_bias(n1, n2): |
46 |
- """ |
47 |
- RDEPEND is stronger than PDEPEND and this function |
48 |
- measures such a strength bias within a circular |
49 |
- dependency relationship. |
50 |
- """ |
51 |
- n1_n2_medium = n2 in mygraph.child_nodes(n1, |
52 |
- ignore_priority=priority_range.ignore_medium_soft) |
53 |
- n2_n1_medium = n1 in mygraph.child_nodes(n2, |
54 |
- ignore_priority=priority_range.ignore_medium_soft) |
55 |
- if n1_n2_medium == n2_n1_medium: |
56 |
- return 0 |
57 |
- elif n1_n2_medium: |
58 |
- return 1 |
59 |
- return -1 |
60 |
myblocker_uninstalls = self._dynamic_config._blocker_uninstalls.copy() |
61 |
retlist=[] |
62 |
# Contains uninstall tasks that have been scheduled to |
63 |
@@ -7815,7 +7800,8 @@ class depgraph(object): |
64 |
self._spinner_update() |
65 |
selected_nodes = None |
66 |
ignore_priority = None |
67 |
- if drop_satisfied or (prefer_asap and asap_nodes): |
68 |
+ cycle_digraph = None |
69 |
+ if prefer_asap and asap_nodes: |
70 |
priority_range = DepPrioritySatisfiedRange |
71 |
else: |
72 |
priority_range = DepPriorityNormalRange |
73 |
@@ -7897,11 +7883,12 @@ class depgraph(object): |
74 |
break |
75 |
|
76 |
if not selected_nodes: |
77 |
- nodes = get_nodes(ignore_priority=priority_range.ignore_medium) |
78 |
- if nodes: |
79 |
- mergeable_nodes = set(nodes) |
80 |
+ |
81 |
+ def find_smallest_cycle(mergeable_nodes, priority_ranges): |
82 |
if prefer_asap and asap_nodes: |
83 |
nodes = asap_nodes |
84 |
+ else: |
85 |
+ nodes = mergeable_nodes |
86 |
# When gathering the nodes belonging to a runtime cycle, |
87 |
# we want to minimize the number of nodes gathered, since |
88 |
# this tends to produce a more optimal merge order. |
89 |
@@ -7912,21 +7899,44 @@ class depgraph(object): |
90 |
# that depend on them. Therefore, we search for the |
91 |
# smallest cycle in order to try and identify and prefer |
92 |
# these smaller independent cycles. |
93 |
- ignore_priority = priority_range.ignore_medium_soft |
94 |
smallest_cycle = None |
95 |
+ ignore_priority = None |
96 |
for node in nodes: |
97 |
if not mygraph.parent_nodes(node): |
98 |
continue |
99 |
- selected_nodes = set() |
100 |
- if gather_deps(ignore_priority, |
101 |
- mergeable_nodes, selected_nodes, node): |
102 |
- if smallest_cycle is None or \ |
103 |
- len(selected_nodes) < len(smallest_cycle): |
104 |
- smallest_cycle = selected_nodes |
105 |
+ for local_priority_range in priority_ranges: |
106 |
+ selected_nodes = set() |
107 |
+ if gather_deps(local_priority_range.ignore_medium_soft, |
108 |
+ mergeable_nodes, selected_nodes, node): |
109 |
+ if smallest_cycle is None or \ |
110 |
+ len(selected_nodes) < len(smallest_cycle): |
111 |
+ smallest_cycle = selected_nodes |
112 |
+ ignore_priority = local_priority_range.ignore_medium_soft |
113 |
+ break |
114 |
+ |
115 |
+ return smallest_cycle, ignore_priority |
116 |
|
117 |
- selected_nodes = smallest_cycle |
118 |
+ priority_ranges = [] |
119 |
+ if priority_range is not DepPriorityNormalRange: |
120 |
+ priority_ranges.append(DepPriorityNormalRange) |
121 |
+ priority_ranges.append(priority_range) |
122 |
+ if drop_satisfied and priority_range is not DepPrioritySatisfiedRange: |
123 |
+ priority_ranges.append(DepPrioritySatisfiedRange) |
124 |
|
125 |
- if selected_nodes is not None: |
126 |
+ for local_priority_range in priority_ranges: |
127 |
+ mergeable_nodes = set(get_nodes(ignore_priority=local_priority_range.ignore_medium)) |
128 |
+ if mergeable_nodes: |
129 |
+ selected_nodes, ignore_priority = find_smallest_cycle(mergeable_nodes, priority_ranges) |
130 |
+ if selected_nodes: |
131 |
+ break |
132 |
+ |
133 |
+ if not selected_nodes: |
134 |
+ if prefer_asap and asap_nodes: |
135 |
+ # We failed to find any asap nodes to merge, so ignore |
136 |
+ # them for the next iteration. |
137 |
+ prefer_asap = False |
138 |
+ continue |
139 |
+ else: |
140 |
cycle_digraph = mygraph.copy() |
141 |
cycle_digraph.difference_update([x for x in |
142 |
cycle_digraph if x not in selected_nodes]) |
143 |
@@ -7953,12 +7963,6 @@ class depgraph(object): |
144 |
writemsg("runtime cycle leaf: %s\n\n" % |
145 |
(selected_nodes[0],), noiselevel=-1) |
146 |
|
147 |
- if prefer_asap and asap_nodes and not selected_nodes: |
148 |
- # We failed to find any asap nodes to merge, so ignore |
149 |
- # them for the next iteration. |
150 |
- prefer_asap = False |
151 |
- continue |
152 |
- |
153 |
if selected_nodes and ignore_priority is not None: |
154 |
# Try to merge ignored medium_soft deps as soon as possible |
155 |
# if they're not satisfied by installed packages. |
156 |
@@ -7980,10 +7984,24 @@ class depgraph(object): |
157 |
# Merge PDEPEND asap for bug #180045. |
158 |
asap_nodes.append(child) |
159 |
|
160 |
- if selected_nodes and len(selected_nodes) > 1: |
161 |
- if not isinstance(selected_nodes, list): |
162 |
- selected_nodes = list(selected_nodes) |
163 |
- selected_nodes.sort(key=cmp_sort_key(cmp_circular_bias)) |
164 |
+ if selected_nodes and len(selected_nodes) > 1 and cycle_digraph is not None: |
165 |
+ # Sort nodes to account for direct circular relationships. Relevant |
166 |
+ # priorities here are: runtime < buildtime < buildtime slot operator |
167 |
+ ignore_priorities = list(filter(None, chain( |
168 |
+ DepPriorityNormalRange.ignore_priority, |
169 |
+ DepPrioritySatisfiedRange.ignore_priority, |
170 |
+ ))) |
171 |
+ selected_nodes = [] |
172 |
+ while cycle_digraph: |
173 |
+ for ignore_priority in ignore_priorities: |
174 |
+ leaves = cycle_digraph.leaf_nodes(ignore_priority=ignore_priority) |
175 |
+ if leaves: |
176 |
+ cycle_digraph.difference_update(leaves) |
177 |
+ selected_nodes.extend(leaves) |
178 |
+ break |
179 |
+ else: |
180 |
+ selected_nodes.extend(cycle_digraph) |
181 |
+ break |
182 |
|
183 |
if not selected_nodes and myblocker_uninstalls: |
184 |
# An Uninstall task needs to be executed in order to |
185 |
|
186 |
diff --git a/lib/portage/tests/resolver/test_merge_order.py b/lib/portage/tests/resolver/test_merge_order.py |
187 |
index 74e826661..11752d71e 100644 |
188 |
--- a/lib/portage/tests/resolver/test_merge_order.py |
189 |
+++ b/lib/portage/tests/resolver/test_merge_order.py |
190 |
@@ -81,6 +81,13 @@ class MergeOrderTestCase(TestCase): |
191 |
"DEPEND": "app-misc/circ-satisfied-a", |
192 |
"RDEPEND": "app-misc/circ-satisfied-a", |
193 |
}, |
194 |
+ "app-misc/circ-direct-a-1": { |
195 |
+ "RDEPEND": "app-misc/circ-direct-b", |
196 |
+ }, |
197 |
+ "app-misc/circ-direct-b-1": { |
198 |
+ "RDEPEND": "app-misc/circ-direct-a", |
199 |
+ "DEPEND": "app-misc/circ-direct-a", |
200 |
+ }, |
201 |
"app-misc/circ-smallest-a-1": { |
202 |
"RDEPEND": "app-misc/circ-smallest-b", |
203 |
}, |
204 |
@@ -220,6 +227,13 @@ class MergeOrderTestCase(TestCase): |
205 |
} |
206 |
|
207 |
installed = { |
208 |
+ "app-misc/circ-direct-a-1": { |
209 |
+ "RDEPEND": "app-misc/circ-direct-b", |
210 |
+ }, |
211 |
+ "app-misc/circ-direct-b-1": { |
212 |
+ "RDEPEND": "app-misc/circ-direct-a", |
213 |
+ "DEPEND": "app-misc/circ-direct-a", |
214 |
+ }, |
215 |
"app-misc/circ-buildtime-a-0": {}, |
216 |
"app-misc/circ-satisfied-a-0": { |
217 |
"RDEPEND": "app-misc/circ-satisfied-b", |
218 |
@@ -295,6 +309,12 @@ class MergeOrderTestCase(TestCase): |
219 |
} |
220 |
|
221 |
test_cases = ( |
222 |
+ ResolverPlaygroundTestCase( |
223 |
+ ["app-misc/circ-direct-a", "app-misc/circ-direct-b"], |
224 |
+ success = True, |
225 |
+ all_permutations = True, |
226 |
+ mergelist = ["app-misc/circ-direct-a-1", "app-misc/circ-direct-b-1"], |
227 |
+ ), |
228 |
ResolverPlaygroundTestCase( |
229 |
["app-misc/some-app-a"], |
230 |
success = True, |
231 |
@@ -321,9 +341,8 @@ class MergeOrderTestCase(TestCase): |
232 |
ambiguous_merge_order = True, |
233 |
# The following merge order assertion reflects optimal order for |
234 |
# a circular relationship which is DEPEND in one direction and |
235 |
- # RDEPEND in the other. The assertion currently fails, and the |
236 |
- # patch for bug 690436 will fix it. |
237 |
- #merge_order_assertions = (("app-misc/circ-buildtime-a-1", "app-misc/circ-buildtime-c-1"),), |
238 |
+ # RDEPEND in the other. |
239 |
+ merge_order_assertions = (("app-misc/circ-buildtime-a-1", "app-misc/circ-buildtime-c-1"),), |
240 |
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"]), |
241 |
# Test optimal merge order for a circular dep that is |
242 |
# RDEPEND in one direction and PDEPEND in the other. |