1 |
Enhance the find_smallest_cycle function to prioritize its |
2 |
search so that it will minimize the use of installed packages |
3 |
to break cycles. When installed packages must be used to |
4 |
break cycles, it will now prefer to do this for runtime |
5 |
dependencies over buildtime dependencies, since it's |
6 |
preferable to build against latest versions of buildtime |
7 |
dependencies whenever possible. This should solve some cases |
8 |
of bug 199856 which have been triggered by unsafe reliance |
9 |
on installed packages to break cycles. |
10 |
|
11 |
The included unit test case demonstrates correct merge order |
12 |
for a dependency calculation involving 6 independent cycles. |
13 |
This test case fails with the master branch, due to a buildtime |
14 |
dependency cycle of 3 packages being merged earlier than cycles |
15 |
of 2 packages. We can generalize this to say that the master |
16 |
branch may use an installed package to break an arbitrarily |
17 |
sized cycle in a somewhat random location, even though that |
18 |
cycle may be composed of smaller independent cycles which |
19 |
would be safer to break individually. |
20 |
|
21 |
Bug: https://bugs.gentoo.org/754903 |
22 |
Signed-off-by: Zac Medico <zmedico@g.o> |
23 |
--- |
24 |
[PATCH v2] |
25 |
* Add a unit test case which demonstrates a significant flaw |
26 |
in the master branch. |
27 |
* Sort nodes in find_smallest_cycle, for deterministic results. |
28 |
|
29 |
lib/_emerge/DepPriorityNormalRange.py | 2 + |
30 |
lib/_emerge/DepPrioritySatisfiedRange.py | 52 ++++++++++--------- |
31 |
lib/_emerge/depgraph.py | 43 +++++++++------ |
32 |
.../tests/resolver/test_merge_order.py | 10 ++++ |
33 |
4 files changed, 66 insertions(+), 41 deletions(-) |
34 |
|
35 |
diff --git a/lib/_emerge/DepPriorityNormalRange.py b/lib/_emerge/DepPriorityNormalRange.py |
36 |
index 5f3f3da70..10f205a3b 100644 |
37 |
--- a/lib/_emerge/DepPriorityNormalRange.py |
38 |
+++ b/lib/_emerge/DepPriorityNormalRange.py |
39 |
@@ -14,6 +14,7 @@ class DepPriorityNormalRange: |
40 |
""" |
41 |
MEDIUM = 3 |
42 |
MEDIUM_SOFT = 2 |
43 |
+ MEDIUM_POST = 2 |
44 |
SOFT = 1 |
45 |
NONE = 0 |
46 |
|
47 |
@@ -37,6 +38,7 @@ class DepPriorityNormalRange: |
48 |
|
49 |
ignore_medium = _ignore_runtime |
50 |
ignore_medium_soft = _ignore_runtime_post |
51 |
+ ignore_medium_post = _ignore_runtime_post |
52 |
ignore_soft = _ignore_optional |
53 |
|
54 |
DepPriorityNormalRange.ignore_priority = ( |
55 |
diff --git a/lib/_emerge/DepPrioritySatisfiedRange.py b/lib/_emerge/DepPrioritySatisfiedRange.py |
56 |
index e056e676f..df2439f1f 100644 |
57 |
--- a/lib/_emerge/DepPrioritySatisfiedRange.py |
58 |
+++ b/lib/_emerge/DepPrioritySatisfiedRange.py |
59 |
@@ -8,17 +8,18 @@ class DepPrioritySatisfiedRange: |
60 |
|
61 |
not satisfied and buildtime HARD |
62 |
not satisfied and runtime 7 MEDIUM |
63 |
- not satisfied and runtime_post 6 MEDIUM_SOFT |
64 |
- satisfied and buildtime_slot_op 5 SOFT |
65 |
- satisfied and buildtime 4 SOFT |
66 |
- satisfied and runtime 3 SOFT |
67 |
- satisfied and runtime_post 2 SOFT |
68 |
+ satisfied and buildtime_slot_op 6 MEDIUM_SOFT |
69 |
+ satisfied and buildtime 5 MEDIUM_SOFT |
70 |
+ satisfied and runtime 4 MEDIUM_SOFT |
71 |
+ runtime_post 3 MEDIUM_POST |
72 |
+ satisfied and runtime_post 2 MEDIUM_POST |
73 |
optional 1 SOFT |
74 |
(none of the above) 0 NONE |
75 |
""" |
76 |
MEDIUM = 7 |
77 |
MEDIUM_SOFT = 6 |
78 |
- SOFT = 5 |
79 |
+ MEDIUM_POST = 3 |
80 |
+ SOFT = 1 |
81 |
NONE = 0 |
82 |
|
83 |
@classmethod |
84 |
@@ -37,15 +38,23 @@ class DepPrioritySatisfiedRange: |
85 |
return False |
86 |
return bool(priority.runtime_post) |
87 |
|
88 |
+ @classmethod |
89 |
+ def _ignore_runtime_post(cls, priority): |
90 |
+ if priority.__class__ is not DepPriority: |
91 |
+ return False |
92 |
+ return bool(priority.optional or priority.runtime_post) |
93 |
+ |
94 |
@classmethod |
95 |
def _ignore_satisfied_runtime(cls, priority): |
96 |
if priority.__class__ is not DepPriority: |
97 |
return False |
98 |
if priority.optional: |
99 |
return True |
100 |
- if not priority.satisfied: |
101 |
+ if priority.buildtime: |
102 |
return False |
103 |
- return not priority.buildtime |
104 |
+ if not priority.runtime: |
105 |
+ return True |
106 |
+ return bool(priority.satisfied) |
107 |
|
108 |
@classmethod |
109 |
def _ignore_satisfied_buildtime(cls, priority): |
110 |
@@ -61,37 +70,32 @@ class DepPrioritySatisfiedRange: |
111 |
def _ignore_satisfied_buildtime_slot_op(cls, priority): |
112 |
if priority.__class__ is not DepPriority: |
113 |
return False |
114 |
- return bool(priority.optional or \ |
115 |
- priority.satisfied) |
116 |
- |
117 |
- @classmethod |
118 |
- def _ignore_runtime_post(cls, priority): |
119 |
- if priority.__class__ is not DepPriority: |
120 |
- return False |
121 |
- return bool(priority.optional or \ |
122 |
- priority.satisfied or \ |
123 |
- priority.runtime_post) |
124 |
+ if priority.optional: |
125 |
+ return True |
126 |
+ if priority.satisfied: |
127 |
+ return True |
128 |
+ return not priority.buildtime and not priority.runtime |
129 |
|
130 |
@classmethod |
131 |
def _ignore_runtime(cls, priority): |
132 |
if priority.__class__ is not DepPriority: |
133 |
return False |
134 |
- return bool(priority.satisfied or \ |
135 |
- priority.optional or \ |
136 |
- not priority.buildtime) |
137 |
+ return bool(priority.optional or |
138 |
+ priority.satisfied or priority.runtime) |
139 |
|
140 |
ignore_medium = _ignore_runtime |
141 |
- ignore_medium_soft = _ignore_runtime_post |
142 |
- ignore_soft = _ignore_satisfied_buildtime |
143 |
+ ignore_medium_soft = _ignore_satisfied_buildtime_slot_op |
144 |
+ ignore_medium_post = _ignore_runtime_post |
145 |
+ ignore_soft = _ignore_optional |
146 |
|
147 |
|
148 |
DepPrioritySatisfiedRange.ignore_priority = ( |
149 |
None, |
150 |
DepPrioritySatisfiedRange._ignore_optional, |
151 |
DepPrioritySatisfiedRange._ignore_satisfied_runtime_post, |
152 |
+ DepPrioritySatisfiedRange._ignore_runtime_post, |
153 |
DepPrioritySatisfiedRange._ignore_satisfied_runtime, |
154 |
DepPrioritySatisfiedRange._ignore_satisfied_buildtime, |
155 |
DepPrioritySatisfiedRange._ignore_satisfied_buildtime_slot_op, |
156 |
- DepPrioritySatisfiedRange._ignore_runtime_post, |
157 |
DepPrioritySatisfiedRange._ignore_runtime |
158 |
) |
159 |
diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py |
160 |
index 6aaacfe44..af26ecd93 100644 |
161 |
--- a/lib/_emerge/depgraph.py |
162 |
+++ b/lib/_emerge/depgraph.py |
163 |
@@ -7905,7 +7905,7 @@ class depgraph: |
164 |
if check_asap_parent: |
165 |
for node in nodes: |
166 |
parents = mygraph.parent_nodes(node, |
167 |
- ignore_priority=DepPrioritySatisfiedRange.ignore_soft) |
168 |
+ ignore_priority=DepPrioritySatisfiedRange.ignore_medium_soft) |
169 |
if any(x in asap_nodes for x in parents): |
170 |
selected_nodes = [node] |
171 |
break |
172 |
@@ -7921,7 +7921,7 @@ class depgraph: |
173 |
|
174 |
if not selected_nodes: |
175 |
|
176 |
- def find_smallest_cycle(mergeable_nodes, priority_ranges): |
177 |
+ def find_smallest_cycle(mergeable_nodes, local_priority_range): |
178 |
if prefer_asap and asap_nodes: |
179 |
nodes = asap_nodes |
180 |
else: |
181 |
@@ -7938,18 +7938,27 @@ class depgraph: |
182 |
# these smaller independent cycles. |
183 |
smallest_cycle = None |
184 |
ignore_priority = None |
185 |
- for node in nodes: |
186 |
- if not mygraph.parent_nodes(node): |
187 |
- continue |
188 |
- for local_priority_range in priority_ranges: |
189 |
+ |
190 |
+ # Sort nodes for deterministic results. |
191 |
+ nodes = sorted(nodes) |
192 |
+ for priority in (local_priority_range.ignore_priority[i] for i in range( |
193 |
+ local_priority_range.MEDIUM_POST, |
194 |
+ local_priority_range.MEDIUM_SOFT + 1)): |
195 |
+ for node in nodes: |
196 |
+ if not mygraph.parent_nodes(node): |
197 |
+ continue |
198 |
selected_nodes = set() |
199 |
- if gather_deps(local_priority_range.ignore_medium_soft, |
200 |
+ if gather_deps(priority, |
201 |
mergeable_nodes, selected_nodes, node): |
202 |
if smallest_cycle is None or \ |
203 |
len(selected_nodes) < len(smallest_cycle): |
204 |
smallest_cycle = selected_nodes |
205 |
- ignore_priority = local_priority_range.ignore_medium_soft |
206 |
- break |
207 |
+ ignore_priority = priority |
208 |
+ |
209 |
+ # Exit this loop with the lowest possible priority, which |
210 |
+ # minimizes the use of installed packages to break cycles. |
211 |
+ if smallest_cycle is not None: |
212 |
+ break |
213 |
|
214 |
return smallest_cycle, ignore_priority |
215 |
|
216 |
@@ -7963,7 +7972,7 @@ class depgraph: |
217 |
for local_priority_range in priority_ranges: |
218 |
mergeable_nodes = set(get_nodes(ignore_priority=local_priority_range.ignore_medium)) |
219 |
if mergeable_nodes: |
220 |
- selected_nodes, ignore_priority = find_smallest_cycle(mergeable_nodes, priority_ranges) |
221 |
+ selected_nodes, ignore_priority = find_smallest_cycle(mergeable_nodes, local_priority_range) |
222 |
if selected_nodes: |
223 |
break |
224 |
|
225 |
@@ -8001,19 +8010,19 @@ class depgraph: |
226 |
(selected_nodes[0],), noiselevel=-1) |
227 |
|
228 |
if selected_nodes and ignore_priority is not None: |
229 |
- # Try to merge ignored medium_soft deps as soon as possible |
230 |
+ # Try to merge ignored medium_post deps as soon as possible |
231 |
# if they're not satisfied by installed packages. |
232 |
for node in selected_nodes: |
233 |
children = set(mygraph.child_nodes(node)) |
234 |
soft = children.difference( |
235 |
- mygraph.child_nodes(node, |
236 |
- ignore_priority=DepPrioritySatisfiedRange.ignore_soft)) |
237 |
- medium_soft = children.difference( |
238 |
mygraph.child_nodes(node, |
239 |
ignore_priority = \ |
240 |
- DepPrioritySatisfiedRange.ignore_medium_soft)) |
241 |
- medium_soft -= soft |
242 |
- for child in medium_soft: |
243 |
+ DepPrioritySatisfiedRange.ignore_soft)) |
244 |
+ medium_post = children.difference( |
245 |
+ mygraph.child_nodes(node, |
246 |
+ ignore_priority=DepPrioritySatisfiedRange.ignore_medium_post)) |
247 |
+ medium_post -= soft |
248 |
+ for child in medium_post: |
249 |
if child in selected_nodes: |
250 |
continue |
251 |
if child in asap_nodes: |
252 |
diff --git a/lib/portage/tests/resolver/test_merge_order.py b/lib/portage/tests/resolver/test_merge_order.py |
253 |
index 0003cd7d8..f81fd2f6f 100644 |
254 |
--- a/lib/portage/tests/resolver/test_merge_order.py |
255 |
+++ b/lib/portage/tests/resolver/test_merge_order.py |
256 |
@@ -490,6 +490,16 @@ class MergeOrderTestCase(TestCase): |
257 |
success=True, |
258 |
all_permutations = True, |
259 |
mergelist = ['x11-base/xorg-server-1.14.1', 'media-libs/mesa-9.1.3']), |
260 |
+ # Test prioritization of the find_smallest_cycle function, which should |
261 |
+ # minimize the use of installed packages to break cycles. If installed |
262 |
+ # packages must be used to break cycles, then it should prefer to do this |
263 |
+ # for runtime dependencies over buildtime dependencies. If a package needs |
264 |
+ # to be uninstalled in order to solve a blocker, then it should prefer to |
265 |
+ # do this before it uses an installed package to break a cycle. |
266 |
+ ResolverPlaygroundTestCase( |
267 |
+ ["app-misc/some-app-a", "app-misc/some-app-b", "app-misc/some-app-c", "app-misc/circ-buildtime-a", "app-misc/blocker-buildtime-unbuilt-a", "media-libs/mesa", "x11-base/xorg-server", "app-misc/circ-direct-a", "app-misc/circ-direct-b", "app-misc/circ-satisfied-a", "app-misc/circ-satisfied-b", "app-misc/circ-satisfied-c"], |
268 |
+ success = True, |
269 |
+ mergelist = ['app-misc/circ-post-runtime-a-1', 'app-misc/circ-post-runtime-c-1', 'app-misc/circ-post-runtime-b-1', 'app-misc/some-app-b-1', 'app-misc/circ-runtime-a-1', 'app-misc/circ-runtime-b-1', 'app-misc/circ-runtime-c-1', 'app-misc/some-app-a-1', 'app-misc/blocker-buildtime-unbuilt-a-1', '[uninstall]app-misc/installed-blocker-a-1', '!app-misc/installed-blocker-a', 'app-misc/circ-direct-a-1', 'app-misc/circ-direct-b-1', 'x11-base/xorg-server-1.14.1', 'media-libs/mesa-9.1.3', 'app-misc/circ-buildtime-a-1', 'app-misc/circ-buildtime-b-1', 'app-misc/circ-buildtime-c-1', 'app-misc/some-app-c-1', 'app-misc/circ-satisfied-a-1', 'app-misc/circ-satisfied-b-1', 'app-misc/circ-satisfied-c-1']), |
270 |
) |
271 |
|
272 |
playground = ResolverPlayground(ebuilds=ebuilds, installed=installed) |
273 |
-- |
274 |
2.26.2 |