Coverage for britney2/installability/tester.py: 98%
331 statements
« prev ^ index » next coverage.py v6.5.0, created at 2024-04-18 20:48 +0000
1# -*- coding: utf-8 -*-
3# Copyright (C) 2012 Niels Thykier <niels@thykier.net>
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.
15from collections import defaultdict
16from functools import partial
17import logging
18from itertools import chain, filterfalse
20from britney2.utils import iter_except, add_transitive_dependencies_flatten
23class InstallabilityTester(object):
25 def __init__(self, universe, suite_contents):
26 """Create a new installability tester
28 universe is a BinaryPackageUniverse
30 suite_contents is a (mutable) set of package ids that determines
31 which of the packages in universe are currently in the suite.
33 Package id: (pkg_name, pkg_version, pkg_arch)
34 - NB: arch:all packages are "re-mapped" to given architecture.
35 (simplifies caches and dependency checking)
36 """
38 self._universe = universe
39 # FIXME: Move this field to TargetSuite
40 self._suite_contents = suite_contents
41 self._stats = InstallabilityStats()
42 logger_name = ".".join((self.__class__.__module__, self.__class__.__name__))
43 self.logger = logging.getLogger(logger_name)
45 # Cache of packages known to be broken - we deliberately do not
46 # include "broken" in it. See _optimize for more info.
47 self._cache_broken = set()
48 # Cache of packages known to be installable
49 self._cache_inst = set()
50 # Per "arch" cache of the "minimal" (possibly incomplete)
51 # pseudo-essential set. This includes all the packages that
52 # are essential and packages that will always follow.
53 #
54 # It may not be a complete essential set, since alternatives
55 # are not always resolved. Noticeably cases like "awk" may be
56 # left out (since it could be either gawk, mawk or
57 # original-awk) unless something in this sets depends strictly
58 # on one of them
59 self._cache_ess = {}
61 essential_w_transitive_deps = set(universe.essential_packages)
62 add_transitive_dependencies_flatten(universe, essential_w_transitive_deps)
63 self._cache_essential_transitive_dependencies = essential_w_transitive_deps
65 def compute_installability(self):
66 """Computes the installability of all the packages in the suite
68 This method computes the installability of all packages in
69 the suite and caches the result. This has the advantage of
70 making "is_installable" queries very fast for all packages
71 in the suite.
72 """
74 universe = self._universe
75 check_inst = self._check_inst
76 cbroken = self._cache_broken
77 cache_inst = self._cache_inst
78 suite_contents = self._suite_contents
79 tcopy = [x for x in suite_contents]
80 for t in filterfalse(cache_inst.__contains__, tcopy):
81 if t in cbroken: 81 ↛ 82line 81 didn't jump to line 82, because the condition on line 81 was never true
82 continue
83 res = check_inst(t)
84 if t in universe.equivalent_packages:
85 eqv = (x for x in universe.packages_equivalent_to(t) if x in suite_contents)
86 if res:
87 cache_inst.update(eqv)
88 else:
89 eqv_set = frozenset(eqv)
90 suite_contents -= eqv_set
91 cbroken |= eqv_set
93 @property
94 def stats(self):
95 return self._stats
97 def any_of_these_are_in_the_suite(self, pkgs):
98 """Test if at least one package of a given set is in the suite
100 :param pkgs: A set of package ids (as defined in the constructor)
101 :return: True if any of the packages in pkgs are currently in the suite
102 """
103 return not self._suite_contents.isdisjoint(pkgs)
105 def is_pkg_in_the_suite(self, pkg_id):
106 """Test if the package of is in the suite
108 :param pkg_id: A package id (as defined in the constructor)
109 :return: True if the pkg is currently in the suite
110 """
111 return pkg_id in self._suite_contents
113 def which_of_these_are_in_the_suite(self, pkgs):
114 """Iterate over all packages that are in the suite
116 :param pkgs: An iterable of package ids
117 :return: An iterable of package ids that are in the suite
118 """
119 yield from (x for x in pkgs if x in self._suite_contents)
121 def add_binary(self, pkg_id):
122 """Add a binary package to the suite
124 If the package is not known, this method will throw an
125 KeyError.
127 :param pkg_id The id of the package
128 """
130 if pkg_id not in self._universe: # pragma: no cover
131 raise KeyError(str(pkg_id))
133 if pkg_id in self._universe.broken_packages:
134 self._suite_contents.add(pkg_id)
135 elif pkg_id not in self._suite_contents: 135 ↛ 149line 135 didn't jump to line 149, because the condition on line 135 was never false
136 self._suite_contents.add(pkg_id)
137 if self._cache_inst:
138 self._stats.cache_drops += 1
139 self._cache_inst = set()
140 if self._cache_broken:
141 # Re-add broken packages as some of them may now be installable
142 self._suite_contents |= self._cache_broken
143 self._cache_broken = set()
144 if pkg_id in self._cache_essential_transitive_dependencies and pkg_id.architecture in self._cache_ess:
145 # Adds new possibly pseudo-essential => "pseudo-essential" set needs to be
146 # recomputed
147 del self._cache_ess[pkg_id.architecture]
149 return True
151 def remove_binary(self, pkg_id):
152 """Remove a binary from the suite
154 :param pkg_id The id of the package
155 If the package is not known, this method will throw an
156 KeyError.
157 """
159 if pkg_id not in self._universe: # pragma: no cover
160 raise KeyError(str(pkg_id))
162 self._cache_broken.discard(pkg_id)
164 if pkg_id in self._suite_contents:
165 self._suite_contents.remove(pkg_id)
166 if pkg_id.architecture in self._cache_ess:
167 (start, ess_never, ess_choices) = self._cache_ess[pkg_id.architecture]
168 if pkg_id in start or any([pkg_id in choices for choices in ess_choices]):
169 # Removes a package from the "pseudo-essential set"
170 del self._cache_ess[pkg_id.architecture]
172 if not self._universe.reverse_dependencies_of(pkg_id):
173 # no reverse relations - safe
174 return True
175 if pkg_id not in self._universe.broken_packages and pkg_id in self._cache_inst:
176 # It is in our cache (and not guaranteed to be broken) - throw out the cache
177 self._cache_inst = set()
178 self._stats.cache_drops += 1
180 return True
182 def is_installable(self, pkg_id):
183 """Test if a package is installable in this package set
185 The package is assumed to be in the suite and only packages in
186 the suite can be used to satisfy relations.
188 :param pkg_id The id of the package
189 Returns True iff the package is installable.
190 Returns False otherwise.
191 """
193 self._stats.is_installable_calls += 1
195 if pkg_id not in self._universe: # pragma: no cover
196 raise KeyError(str(pkg_id))
198 if pkg_id not in self._suite_contents or pkg_id in self._universe.broken_packages:
199 self._stats.cache_hits += 1
200 return False
202 if pkg_id in self._cache_inst:
203 self._stats.cache_hits += 1
204 return True
206 self._stats.cache_misses += 1
207 return self._check_inst(pkg_id)
209 def _check_inst(self, t, musts=None, never=None, choices=None):
210 # See the explanation of musts, never and choices below.
211 stats = self._stats
212 universe = self._universe
213 suite_contents = self._suite_contents
214 cbroken = self._cache_broken
216 # Our installability verdict - start with "yes" and change if
217 # prove otherwise.
218 verdict = True
220 # set of packages that must be installed with this package
221 if musts is None:
222 musts = set()
223 musts.add(t)
224 # set of packages we can *never* choose (e.g. due to conflicts)
225 if never is None:
226 never = set()
227 # set of relations were we have a choice, but where we have not
228 # committed ourselves yet. Hopefully some choices may be taken
229 # for us (if one of the alternatives appear in "musts")
230 if choices is None:
231 choices = set()
233 # The subset of musts we haven't checked yet.
234 check = [t]
236 if len(musts) == 1:
237 # Include the essential packages in the suite as a starting point.
238 if t.architecture not in self._cache_ess:
239 # The minimal essential set cache is not present -
240 # compute it now.
241 (start, ess_never, ess_choices) = self._get_min_pseudo_ess_set(t.architecture)
242 else:
243 (start, ess_never, ess_choices) = self._cache_ess[t.architecture]
245 if t in ess_never:
246 # t conflicts with something in the essential set or the essential
247 # set conflicts with t - either way, t is f***ed
248 cbroken.add(t)
249 suite_contents.remove(t)
250 stats.conflicts_essential += 1
251 return False
252 musts.update(start)
253 never.update(ess_never)
254 choices.update(ess_choices)
256 # curry check_loop
257 check_loop = partial(self._check_loop, universe, suite_contents,
258 stats, musts, never, cbroken)
260 # Useful things to remember:
261 #
262 # * musts and never are disjointed at all times
263 # - if not, t cannot be installable. Either t, or one of
264 # its dependencies conflict with t or one of its (other)
265 # dependencies.
266 #
267 # * choices should generally be avoided as much as possible.
268 # - picking a bad choice requires backtracking
269 # - sometimes musts/never will eventually "solve" the choice.
270 #
271 # * check never includes choices (these are always in choices)
272 #
273 # * A package is installable if never and musts are disjointed
274 # and both check and choices are empty.
275 # - exception: resolve_choices may determine the installability
276 # of t via recursion (calls _check_inst). In this case
277 # check and choices are not (always) empty.
279 def _prune_choices(rebuild, len=len):
280 """Picks a choice from choices and updates rebuild.
282 Prunes the choices and updates "rebuild" to reflect the
283 pruned choices.
285 Returns True if t is installable (determined via recursion).
286 Returns False if a choice was picked and added to check.
287 Returns None if t is uninstallable (no choice can be picked).
289 NB: If this returns False, choices should be replaced by
290 rebuild.
291 """
293 # We already satisfied/chosen at least one of the literals
294 # in the choice, so the choice is gone
295 for choice in filter(musts.isdisjoint, choices):
296 # cbroken is needed here because (in theory) it could
297 # have changed since the choice was discovered and it
298 # is smaller than suite_contents (so presumably faster)
299 remain = choice - never - cbroken
301 if len(remain) == 1:
302 # the choice was reduced to one package we haven't checked - check that
303 check.extend(remain)
304 musts.update(remain)
305 stats.choice_presolved += 1
306 continue
308 if not remain:
309 # all alternatives would violate the conflicts or are uninstallable
310 # => package is not installable
311 stats.choice_presolved += 1
312 return False
314 # The choice is still deferred
315 rebuild.add(frozenset(remain))
317 return True
319 # END _prune_choices
321 while check:
322 if not check_loop(choices, check):
323 verdict = False
324 break
326 if choices:
327 rebuild = set()
329 if not _prune_choices(rebuild):
330 verdict = False
331 break
333 if not check and rebuild:
334 # We have to "guess" now, which is always fun, but not cheap. We
335 # stop guessing:
336 # - once we run out of choices to make (obviously), OR
337 # - if one of the choices exhaust all but one option
338 if self.resolve_choices(check, musts, never, rebuild):
339 # The recursive call have already updated the
340 # cache so there is not point in doing it again.
341 return True
342 choices = rebuild
344 if verdict:
345 # if t is installable, then so are all packages in musts
346 self._cache_inst.update(musts)
347 stats.solved_installable += 1
348 else:
349 stats.solved_uninstallable += 1
351 return verdict
353 def resolve_choices(self, check, musts, never, choices):
354 universe = self._universe
355 suite_contents = self._suite_contents
356 stats = self._stats
357 cbroken = self._cache_broken
359 while choices:
360 choice_options = choices.pop()
362 choice = iter(choice_options)
363 last = next(choice) # pick one to go last
364 solved = False
365 for p in choice:
366 musts_copy = musts.copy()
367 never_tmp = set()
368 choices_tmp = set()
369 check_tmp = [p]
370 # _check_loop assumes that "musts" is up to date
371 musts_copy.add(p)
372 if not self._check_loop(universe, suite_contents,
373 stats, musts_copy, never_tmp,
374 cbroken, choices_tmp,
375 check_tmp):
376 # p cannot be chosen/is broken (unlikely, but ...)
377 continue
379 # Test if we can pick p without any consequences.
380 # - when we can, we avoid a backtrack point.
381 if never_tmp <= never and choices_tmp <= choices:
382 # we can pick p without picking up new conflicts
383 # or unresolved choices. Therefore we commit to
384 # using p.
385 musts.update(musts_copy)
386 stats.choice_resolved_without_restore_point += 1
387 solved = True
388 break
390 if not musts.isdisjoint(never_tmp):
391 # If we pick p, we will definitely end up making
392 # t uninstallable, so p is a no-go.
393 continue
395 stats.backtrace_restore_point_created += 1
396 # We are not sure that p is safe, setup a backtrack
397 # point and recurse.
398 never_tmp |= never
399 choices_tmp |= choices
400 if self._check_inst(p, musts_copy, never_tmp,
401 choices_tmp):
402 # Success, p was a valid choice and made it all
403 # installable
404 return True
406 # If we get here, we failed to find something that
407 # would satisfy choice (without breaking the
408 # installability of t). This means p cannot be used
409 # to satisfy the dependencies, so pretend to conflict
410 # with it - hopefully it will reduce future choices.
411 never.add(p)
412 stats.backtrace_restore_point_used += 1
414 if not solved:
415 # Optimization for the last case; avoid the recursive call
416 # and just assume the last will lead to a solution. If it
417 # doesn't there is no solution and if it does, we don't
418 # have to back-track anyway.
419 check.append(last)
420 musts.add(last)
421 stats.backtrace_last_option += 1
422 return False
424 def _check_loop(self, universe, suite_contents, stats, musts, never,
425 cbroken, choices, check, len=len,
426 frozenset=frozenset):
427 """Finds all guaranteed dependencies via "check".
429 If it returns False, t is not installable. If it returns True
430 then "check" is exhausted. If "choices" are empty and this
431 returns True, then t is installable.
432 """
433 # Local variables for faster access...
434 not_satisfied = partial(filter, musts.isdisjoint)
436 # While we have guaranteed dependencies (in check), examine all
437 # of them.
438 for cur in iter_except(check.pop, IndexError):
439 relations = universe.relations_of(cur)
441 if relations.negative_dependencies:
442 # Conflicts?
443 if cur in never:
444 # cur adds a (reverse) conflict, so check if cur
445 # is in never.
446 #
447 # - there is a window where two conflicting
448 # packages can be in check. Example "A" depends
449 # on "B" and "C". If "B" conflicts with "C",
450 # then both "B" and "C" could end in "check".
451 return False
452 # We must install cur for the package to be installable,
453 # so "obviously" we can never choose any of its conflicts
454 never.update(relations.negative_dependencies & suite_contents)
456 # depgroup can be satisfied by picking something that is
457 # already in musts - lets pick that (again). :)
458 for depgroup in not_satisfied(relations.dependencies):
460 # Of all the packages listed in the relation remove those that
461 # are either:
462 # - not in the suite
463 # - known to be broken (by cache)
464 # - in never
465 candidates = (depgroup & suite_contents) - never
467 if not candidates:
468 # We got no candidates to satisfy it - this
469 # package cannot be installed with the current
470 # (version of the) suite
471 if cur not in cbroken and depgroup.isdisjoint(never):
472 # cur's dependency cannot be satisfied even if never was empty.
473 # This means that cur itself is broken (as well).
474 cbroken.add(cur)
475 suite_contents.remove(cur)
476 return False
477 if len(candidates) == 1:
478 # only one possible solution to this choice and we
479 # haven't seen it before
480 check.extend(candidates)
481 musts.update(candidates)
482 else:
483 possible_eqv = set(x for x in candidates if x in universe.equivalent_packages)
484 if len(possible_eqv) > 1:
485 # Exploit equivalency to reduce the number of
486 # candidates if possible. Basically, this
487 # code maps "similar" candidates into a single
488 # candidate that will give a identical result
489 # to any other candidate it eliminates.
490 #
491 # See InstallabilityTesterBuilder's
492 # _build_eqv_packages_table method for more
493 # information on how this works.
494 new_cand = set(x for x in candidates if x not in possible_eqv)
495 stats.eqv_table_times_used += 1
497 for chosen in iter_except(possible_eqv.pop, KeyError):
498 new_cand.add(chosen)
499 possible_eqv -= universe.packages_equivalent_to(chosen)
500 stats.eqv_table_total_number_of_alternatives_eliminated += len(candidates) - len(new_cand)
501 if len(new_cand) == 1:
502 check.extend(new_cand)
503 musts.update(new_cand)
504 stats.eqv_table_reduced_to_one += 1
505 continue
506 elif len(candidates) == len(new_cand):
507 stats.eqv_table_reduced_by_zero += 1
509 candidates = frozenset(new_cand)
510 else:
511 # Candidates have to be a frozenset to be added to choices
512 candidates = frozenset(candidates)
513 # defer this choice till later
514 choices.add(candidates)
515 return True
517 def _get_min_pseudo_ess_set(self, arch):
518 if arch not in self._cache_ess: 518 ↛ 558line 518 didn't jump to line 558, because the condition on line 518 was never false
519 # The minimal essential set cache is not present -
520 # compute it now.
521 suite_contents = self._suite_contents
522 cbroken = self._cache_broken
523 universe = self._universe
524 stats = self._stats
526 ess_base = [x for x in self._universe.essential_packages if x.architecture == arch and x in suite_contents]
527 start = set(ess_base)
528 ess_never = set()
529 ess_choices = set()
530 not_satisfied = partial(filter, start.isdisjoint)
532 while ess_base:
533 self._check_loop(universe, suite_contents, stats,
534 start, ess_never, cbroken,
535 ess_choices, ess_base)
536 if ess_choices:
537 # Try to break choices where possible
538 nchoice = set()
539 for choice in not_satisfied(ess_choices):
540 b = False
541 for c in choice:
542 relations = universe.relations_of(c)
543 if relations.negative_dependencies <= ess_never and \
544 not any(not_satisfied(relations.dependencies)):
545 ess_base.append(c)
546 b = True
547 break
548 if not b:
549 nchoice.add(choice)
550 ess_choices = nchoice
551 else:
552 break
554 for x in start:
555 ess_never.update(universe.negative_dependencies_of(x))
556 self._cache_ess[arch] = (frozenset(start), frozenset(ess_never), frozenset(ess_choices))
558 return self._cache_ess[arch]
560 def compute_stats(self):
561 universe = self._universe
562 graph_stats = defaultdict(ArchStats)
563 seen_eqv = defaultdict(set)
565 for pkg in universe:
566 (pkg_name, pkg_version, pkg_arch) = pkg
567 relations = universe.relations_of(pkg)
568 arch_stats = graph_stats[pkg_arch]
570 arch_stats.nodes += 1
572 if pkg in universe.equivalent_packages and pkg not in seen_eqv[pkg_arch]:
573 eqv = [e for e in universe.packages_equivalent_to(pkg) if e.architecture == pkg_arch]
574 arch_stats.eqv_nodes += len(eqv)
576 arch_stats.add_dep_edges(relations.dependencies)
577 arch_stats.add_con_edges(relations.negative_dependencies)
579 for stat in graph_stats.values():
580 stat.compute_all()
582 return graph_stats
585class InstallabilityStats(object):
587 def __init__(self):
588 self.cache_hits = 0
589 self.cache_misses = 0
590 self.cache_drops = 0
591 self.backtrace_restore_point_created = 0
592 self.backtrace_restore_point_used = 0
593 self.backtrace_last_option = 0
594 self.choice_presolved = 0
595 self.choice_resolved_without_restore_point = 0
596 self.is_installable_calls = 0
597 self.solved_installable = 0
598 self.solved_uninstallable = 0
599 self.conflicts_essential = 0
600 self.eqv_table_times_used = 0
601 self.eqv_table_reduced_to_one = 0
602 self.eqv_table_reduced_by_zero = 0
603 self.eqv_table_total_number_of_alternatives_eliminated = 0
605 def stats(self):
606 formats = [
607 "Requests - is_installable: {is_installable_calls}",
608 "Cache - hits: {cache_hits}, misses: {cache_misses}, drops: {cache_drops}",
609 "Choices - pre-solved: {choice_presolved}, No RP: {choice_resolved_without_restore_point}",
610 "Backtrace - RP created: {backtrace_restore_point_created}, RP used: {backtrace_restore_point_used}, reached last option: {backtrace_last_option}", # nopep8
611 "Solved - installable: {solved_installable}, uninstallable: {solved_uninstallable}, conflicts essential: {conflicts_essential}", # nopep8
612 "Eqv - times used: {eqv_table_times_used}, perfect reductions: {eqv_table_reduced_to_one}, failed reductions: {eqv_table_reduced_by_zero}, total no. of alternatives pruned: {eqv_table_total_number_of_alternatives_eliminated}", # nopep8
613 ]
614 return [x.format(**self.__dict__) for x in formats]
617class ArchStats(object):
619 def __init__(self):
620 self.nodes = 0
621 self.eqv_nodes = 0
622 self.dep_edges = []
623 self.con_edges = []
624 self.stats = defaultdict(lambda: defaultdict(int))
626 def stat(self, statname):
627 return self.stats[statname]
629 def stat_summary(self):
630 text = []
631 for statname in ['nodes', 'dependency-clauses', 'dependency-clause-alternatives', 'negative-dependency-clauses']:
632 stat = self.stats[statname]
633 if statname != 'nodes':
634 format_str = "%s, max: %d, min: %d, median: %d, average: %f (%d/%d)"
635 values = [statname, stat['max'], stat['min'], stat['median'], stat['average'], stat['sum'], stat['size']]
636 if 'average-per-node' in stat:
637 format_str += ", average-per-node: %f"
638 values.append(stat['average-per-node'])
639 else:
640 format_str = "nodes: %d, eqv-nodes: %d"
641 values = (self.nodes, self.eqv_nodes)
642 text.append(format_str % tuple(values))
643 return text
645 def add_dep_edges(self, edges):
646 self.dep_edges.append(edges)
648 def add_con_edges(self, edges):
649 self.con_edges.append(edges)
651 def _list_stats(self, stat_name, sorted_list, average_per_node=False):
652 if sorted_list:
653 stats = self.stats[stat_name]
654 stats['max'] = sorted_list[-1]
655 stats['min'] = sorted_list[0]
656 stats['sum'] = sum(sorted_list)
657 stats['size'] = len(sorted_list)
658 stats['average'] = float(stats['sum'])/len(sorted_list)
659 stats['median'] = sorted_list[len(sorted_list)//2]
660 if average_per_node:
661 stats['average-per-node'] = float(stats['sum'])/self.nodes
663 def compute_all(self):
664 dep_edges = self.dep_edges
665 con_edges = self.con_edges
666 sorted_no_dep_edges = sorted(len(x) for x in dep_edges)
667 sorted_size_dep_edges = sorted(len(x) for x in chain.from_iterable(dep_edges))
668 sorted_no_con_edges = sorted(len(x) for x in con_edges)
669 self._list_stats('dependency-clauses', sorted_no_dep_edges)
670 self._list_stats('dependency-clause-alternatives', sorted_size_dep_edges, average_per_node=True)
671 self._list_stats('negative-dependency-clauses', sorted_no_con_edges)