Coverage for britney2/installability/solver.py: 98%
209 statements
« prev ^ index » next coverage.py v7.6.0, created at 2026-08-18 12:43 +0000
1# Copyright (C) 2012 Niels Thykier <niels@thykier.net>
2# - Includes code by Paul Harrison
3# (http://www.logarithmic.net/pfh-files/blog/01208083168/sort.py)
5# This program is free software; you can redistribute it and/or modify
6# it under the terms of the GNU General Public License as published by
7# the Free Software Foundation; either version 2 of the License, or
8# (at your option) any later version.
10# This program is distributed in the hope that it will be useful,
11# but WITHOUT ANY WARRANTY; without even the implied warranty of
12# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13# GNU General Public License for more details.
15import logging
16from collections import deque
17from collections.abc import Iterable
18from dataclasses import dataclass, field
19from itertools import chain, tee
20from typing import TYPE_CHECKING
22from more_itertools import iter_except
24from britney2.utils import ifilter_only
26if TYPE_CHECKING: 26 ↛ 27line 26 didn't jump to line 27 because the condition on line 26 was never true
27 from .. import BinaryPackageId
28 from ..migrationitem import MigrationItem
29 from .tester import InstallabilityTester
30 from .universe import BinaryPackageUniverse
33@dataclass(slots=True)
34class OrderNode:
35 after: set[str] = field(default_factory=set)
36 before: set[str] = field(default_factory=set)
39def compute_scc(graph: dict[str, OrderNode]) -> list[tuple[str, ...]]:
40 """Iterative algorithm for strongly-connected components
42 Iterative variant of Tarjan's algorithm for finding strongly-connected
43 components.
45 :param graph: dict of all nodes along which their edges (in "before" and "after")
46 :return: List of components (each component is a list of items)
47 """
48 result: list[tuple[str, ...]] = []
49 low: dict[str, int] = {}
50 node_stack: list[str] = []
52 def _cannot_be_a_scc(graph_node: str) -> bool:
53 node = graph[graph_node]
54 if not node.before or not node.after:
55 # Short-cut obviously isolated component
56 result.append((graph_node,))
57 # Set the item number so high that no other item might
58 # mistakenly assume that they can form a component via
59 # this item.
60 # (Replaces the "is w on the stack check" for us from
61 # the original algorithm)
62 low[graph_node] = len(graph) + 1
63 return True
64 return False
66 def _handle_succ(
67 parent: str, parent_num: int, successors_remaining: list[str]
68 ) -> bool:
69 while successors_remaining:
70 succ = successors_remaining.pop()
71 succ_num = low.get(succ, None)
72 if succ_num is not None:
73 if succ_num < parent_num:
74 # These two nodes are part of the probably
75 # same SSC (or succ is isolated
76 low[parent] = parent_num = succ_num
77 continue
78 # It cannot be a part of a SCC if it does not have depends
79 # or reverse depends.
80 if _cannot_be_a_scc(succ):
81 continue
82 succ_num = len(low)
83 low[succ] = succ_num
84 work_stack.append((succ, len(node_stack), succ_num, graph[succ].before))
85 node_stack.append(succ)
86 # "Recurse" into the child node first
87 return True
88 return False
90 # graph is a dict, shouldn't need sorting
91 for n, n_data in graph.items():
92 if n in low:
93 continue
94 # It cannot be a part of a SCC if it does not have depends
95 # or reverse depends.
96 if _cannot_be_a_scc(n):
97 continue
99 root_num = len(low)
100 low[n] = root_num
101 # DFS work-stack needed to avoid call recursion. It (more or less)
102 # replaces the variables on the call stack in Tarjan's algorithm
103 work_stack = [(n, len(node_stack), root_num, n_data.before)]
104 node_stack.append(n)
105 while work_stack:
106 node, stack_idx, orig_node_num, successors = work_stack[-1]
107 if successors and _handle_succ(node, low[node], sorted(successors)):
108 # _handle_succ has pushed a new node on to work_stack
109 # and we need to "restart" the loop to handle that first
110 continue
112 # This node is done; remove it from the work stack
113 work_stack.pop()
115 # This node is out of successor. Push up the "low" value
116 # (Exception: root node has no parent)
117 node_num = low[node]
118 if work_stack:
119 parent = work_stack[-1][0]
120 parent_num = low[parent]
121 if node_num <= parent_num:
122 # This node is a part of a component with its parent.
123 # We update the parent's node number and push the
124 # responsibility of building the component unto the
125 # parent.
126 low[parent] = node_num
127 continue
128 if node_num != orig_node_num: 128 ↛ 130line 128 didn't jump to line 130 because the condition on line 128 was never true
129 # The node is a part of an SCC with a ancestor (and parent)
130 continue
131 # We got a component
132 component = tuple(node_stack[stack_idx:])
133 del node_stack[stack_idx:]
134 result.append(component)
135 # Re-number all items, so no other item might
136 # mistakenly assume that they can form a component via
137 # one of these items.
138 # (Replaces the "is w on the stack check" for us from
139 # the original algorithm)
140 new_num = len(graph) + 1
141 for item in component:
142 low[item] = new_num
144 assert not node_stack
146 return result
149def apply_order(
150 key: str,
151 other: str,
152 order: dict[str, OrderNode],
153 logger: logging.Logger,
154 order_cause: str,
155 invert: bool = False,
156 order_sub_cause: str = "",
157) -> None:
158 if other == key:
159 # "Self-relation" => ignore
160 return
161 order_key = order[key]
162 if invert:
163 order[other].after.add(key)
164 order_set = order_key.before
165 else:
166 order[other].before.add(key)
167 order_set = order_key.after
168 if (
169 logger.isEnabledFor(logging.DEBUG) and other not in order_set
170 ): # pragma: no cover
171 if order_sub_cause:
172 order_sub_cause = " (%s)" % order_sub_cause
173 logger.debug(
174 "%s induced order%s: %s before %s", order_cause, order_sub_cause, key, other
175 )
176 # Defer adding until the end to ensure we only log the first time a dependency order is introduced.
177 order_set.add(other)
180class InstallabilitySolver:
181 def __init__(
182 self, universe: "BinaryPackageUniverse", inst_tester: "InstallabilityTester"
183 ) -> None:
184 """Create a new installability solver"""
185 self._universe = universe
186 self._inst_tester = inst_tester
187 logger_name = ".".join((self.__class__.__module__, self.__class__.__name__))
188 self.logger = logging.getLogger(logger_name)
190 def _compute_group_order_rms(
191 self,
192 rms: Iterable["BinaryPackageId"],
193 order: dict[str, OrderNode],
194 key: str,
195 ptable: dict["BinaryPackageId", str],
196 going_out: set["BinaryPackageId"],
197 ) -> None:
198 sat_in_testing = self._inst_tester.any_of_these_are_in_the_suite
199 universe = self._universe
200 logger = self.logger
201 for rdep in chain.from_iterable(
202 universe.reverse_dependencies_of(r) for r in rms
203 ):
204 # The binaries have reverse dependencies in testing;
205 # check if we can/should migrate them first.
206 for depgroup in universe.dependencies_of(rdep):
207 rigid = depgroup - going_out
208 if sat_in_testing(rigid):
209 # (partly) satisfied by testing, assume it is okay
210 continue
211 if (v := ptable.get(rdep)) is not None:
212 apply_order(key, v, order, logger, "Removal")
214 def _compute_order_for_dependency(
215 self,
216 key: str,
217 depgroup: frozenset["BinaryPackageId"],
218 ptable: dict["BinaryPackageId", str],
219 order: dict[str, OrderNode],
220 going_in: set["BinaryPackageId"],
221 ) -> None:
222 # We got three cases:
223 # - "swap" (replace existing binary with a newer version)
224 # - "addition" (add new binary without removing any)
225 # - "removal" (remove binary without providing a new)
226 #
227 # The problem is that only the two latter requires
228 # an ordering. A "swap" (in itself) should not
229 # affect us.
230 other_adds = set()
231 other_rms = set()
232 logger = self.logger
233 for d in ifilter_only(ptable, depgroup):
234 other = ptable[d]
235 if d in going_in:
236 # "other" provides something "key" needs,
237 # schedule accordingly.
238 other_adds.add(other)
239 else:
240 # "other" removes something "key" needs,
241 # schedule accordingly.
242 other_rms.add(other)
244 for other in other_adds:
245 if other in other_rms:
246 continue
247 apply_order(key, other, order, logger, "Dependency", order_sub_cause="add")
248 for other in other_rms:
249 if other in other_adds:
250 continue
251 apply_order(
252 key,
253 other,
254 order,
255 logger,
256 "Dependency",
257 order_sub_cause="remove",
258 invert=True,
259 )
261 def _compute_group_order_adds(
262 self,
263 adds: Iterable["BinaryPackageId"],
264 order: dict[str, OrderNode],
265 key: str,
266 ptable: dict["BinaryPackageId", str],
267 going_out: set["BinaryPackageId"],
268 going_in: set["BinaryPackageId"],
269 ) -> None:
270 sat_in_testing = self._inst_tester.any_of_these_are_in_the_suite
271 universe = self._universe
272 for depgroup in chain.from_iterable(universe.dependencies_of(a) for a in adds):
273 # Check if this item should migrate before others
274 # (e.g. because they depend on a new [version of a]
275 # binary provided by this item).
276 rigid = depgroup - going_out
277 if sat_in_testing(rigid):
278 # (partly) satisfied by testing, assume it is okay
279 continue
280 self._compute_order_for_dependency(key, depgroup, ptable, order, going_in)
282 def _compute_group_order(
283 self,
284 groups: Iterable[
285 tuple[
286 "MigrationItem",
287 Iterable["BinaryPackageId"],
288 Iterable["BinaryPackageId"],
289 ]
290 ],
291 key2item: dict[str, "MigrationItem"],
292 ) -> dict[str, OrderNode]:
293 universe = self._universe
294 ptable = {}
295 order: dict[str, OrderNode] = {}
296 going_out: set["BinaryPackageId"] = set()
297 going_in: set["BinaryPackageId"] = set()
298 logger = self.logger
299 debug_solver = logger.isEnabledFor(logging.DEBUG)
301 first_it, debug_it, second_it = tee(groups, 3)
303 # Build the tables
304 for item, adds, rms in first_it:
305 key = str(item)
306 key2item[key] = item
307 order[key] = OrderNode()
308 going_in.update(adds)
309 going_out.update(rms)
310 for x in chain(adds, rms):
311 ptable[x] = key
313 if debug_solver: # pragma: no cover
314 self._dump_groups(debug_it)
316 # This large loop will add ordering constrains on each "item"
317 # that migrates based on various rules.
318 for item, adds, rms in second_it:
319 key = str(item)
320 oldcons = set(
321 chain.from_iterable(universe.negative_dependencies_of(r) for r in rms)
322 )
323 oldcons.difference_update(
324 chain.from_iterable(universe.negative_dependencies_of(a) for a in adds)
325 )
326 # Some of the old binaries have "conflicts" that will
327 # be removed.
328 for o in ifilter_only(ptable, oldcons):
329 # "key" removes a conflict with one of
330 # "other"'s binaries, so it is probably a good
331 # idea to migrate "key" before "other"
332 apply_order(key, ptable[o], order, logger, "Conflict", invert=True)
334 self._compute_group_order_rms(rms, order, key, ptable, going_out)
335 self._compute_group_order_adds(
336 adds, order, key, ptable, going_out, going_in
337 )
339 return order
341 def _merge_items_into_components(
342 self, comps: list[tuple[str, ...]], order: dict[str, OrderNode]
343 ) -> dict[str, tuple[str, ...]]:
344 merged = {}
345 scc: dict[str, tuple[str, ...]] = {}
346 debug_solver = self.logger.isEnabledFor(logging.DEBUG)
347 for com in comps:
348 scc_id = com[0]
349 scc[scc_id] = com
350 merged[scc_id] = scc_id
351 if len(com) < 2:
352 # Trivial case
353 continue
354 so_before = order[scc_id].before
355 so_after = order[scc_id].after
356 for n in com:
357 if n == scc_id:
358 continue
359 so_before.update(order[n].before)
360 so_after.update(order[n].after)
361 merged[n] = scc_id
362 del order[n]
363 if debug_solver: # pragma: no cover
364 self.logger.debug("SCC: %s -- %s", scc_id, sorted(com))
366 for com in comps:
367 node = com[0]
368 nbefore = {merged[b] for b in order[node].before}
369 nafter = {merged[b] for b in order[node].after}
371 # Drop self-relations (usually caused by the merging)
372 nbefore.discard(node)
373 nafter.discard(node)
374 order[node].before = nbefore
375 order[node].after = nafter
377 for com in comps:
378 scc_id = com[0]
380 for other_scc_id in order[scc_id].before:
381 order[other_scc_id].after.add(scc_id)
382 for other_scc_id in order[scc_id].after:
383 order[other_scc_id].before.add(scc_id)
385 return scc
387 def solve_groups(
388 self,
389 groups: Iterable[
390 tuple[
391 "MigrationItem",
392 Iterable["BinaryPackageId"],
393 Iterable["BinaryPackageId"],
394 ]
395 ],
396 ) -> list[list["MigrationItem"]]:
397 """
398 :param groups: iterable of tuples. The first element is a
399 MigrationItem, the second element is a collection of BinaryPackageId
400 reflecting requested updates and the third element is a collection of
401 BinaryPackageId reflecting requested removals.
402 """
403 result: list[list["MigrationItem"]] = []
404 emitted: set[str] = set()
405 queue: deque[str] = deque()
406 key2item: dict[str, "MigrationItem"] = {}
407 debug_solver = self.logger.isEnabledFor(logging.DEBUG)
409 order = self._compute_group_order(groups, key2item)
411 # === MILESTONE: Partial-order constrains computed ===
413 # At this point, we have computed all the partial-order
414 # constrains needed. Some of these may have created strongly
415 # connected components (SSC) [of size 2 or greater], which
416 # represents a group of items that (we believe) must migrate
417 # together.
418 #
419 # Each one of those components will become an "easy" hint.
421 comps = compute_scc(order)
422 # Now that we got the SSCs (in comps), we select on item from
423 # each SSC to represent the group and become an ID for that
424 # SSC.
425 # * scc_keys[ssc_id] => All the item-keys in that SSC
426 #
427 # We also "repair" the ordering, so we know in which order the
428 # hints should be emitted.
429 scc_keys = self._merge_items_into_components(comps, order)
431 if debug_solver: # pragma: no cover
432 self.logger.debug("-- PARTIAL ORDER --")
434 initial_round = []
435 for com in sorted(order):
436 if debug_solver and order[com].before: # pragma: no cover
437 self.logger.debug("N: %s <= %s", com, sorted(order[com].before))
438 if not order[com].after:
439 # This component can be scheduled immediately, add it
440 # to the queue
441 initial_round.append(com)
442 elif debug_solver: # pragma: no cover
443 self.logger.debug("N: %s >= %s", com, sorted(order[com].after))
445 queue.extend(sorted(initial_round, key=len))
446 del initial_round
448 if debug_solver: # pragma: no cover
449 self.logger.debug("-- END PARTIAL ORDER --")
450 self.logger.debug("-- LINEARIZED ORDER --")
452 for cur in iter_except(queue.popleft, IndexError):
453 if order[cur].after <= emitted and cur not in emitted:
454 # This item is ready to be emitted right now
455 if debug_solver: # pragma: no cover
456 self.logger.debug("%s -- %s", cur, sorted(scc_keys[cur]))
457 emitted.add(cur)
458 result.append([key2item[x] for x in scc_keys[cur]])
459 if order[cur].before:
460 # There are components that come after this one.
461 # Add it to queue:
462 # - if it is ready, it will be emitted.
463 # - else, it will be dropped and re-added later.
464 queue.extend(sorted(order[cur].before - emitted, key=len))
466 if debug_solver: # pragma: no cover
467 self.logger.debug("-- END LINEARIZED ORDER --")
469 return result
471 def _dump_groups(
472 self,
473 groups: Iterable[
474 tuple[
475 "MigrationItem",
476 Iterable["BinaryPackageId"],
477 Iterable["BinaryPackageId"],
478 ]
479 ],
480 ) -> None: # pragma: no cover
481 self.logger.debug("=== Groups ===")
482 for item, adds, rms in groups:
483 self.logger.debug("%s => A: %s, R: %s", item, adds, rms)
484 self.logger.debug("=== END Groups ===")