Coverage for britney2/installability/builder.py: 99%
185 statements
« prev ^ index » next coverage.py v7.6.0, created at 2026-01-29 17:21 +0000
1# Copyright (C) 2012 Niels Thykier <niels@thykier.net>
3# This program is free software; you can redistribute it and/or modify
4# it under the terms of the GNU General Public License as published by
5# the Free Software Foundation; either version 2 of the License, or
6# (at your option) any later version.
8# This program is distributed in the hope that it will be useful,
9# but WITHOUT ANY WARRANTY; without even the implied warranty of
10# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11# GNU General Public License for more details.
13from builtins import frozenset as _frozenset
14from collections import defaultdict
15from collections.abc import Callable, Iterable, MutableSet
16from functools import partial
17from itertools import filterfalse, product
18from typing import (
19 TYPE_CHECKING,
20 Any,
21 TypeVar,
22 cast,
23)
25import apt_pkg
27from britney2.installability.tester import InstallabilityTester
28from britney2.installability.universe import (
29 BinaryPackageRelation,
30 BinaryPackageUniverse,
31)
32from britney2.utils import get_dependency_solvers, ifilter_except, iter_except
34if TYPE_CHECKING: 34 ↛ 35line 34 didn't jump to line 35 because the condition on line 34 was never true
35 from .. import BinaryPackage, BinaryPackageId, PackageId, Suite, Suites
38def build_installability_tester(
39 suite_info: "Suites", archs: list[str]
40) -> tuple[BinaryPackageUniverse, InstallabilityTester]:
41 """Create the installability tester"""
43 builder = InstallabilityTesterBuilder()
45 for suite, arch in product(suite_info, archs):
46 _build_inst_tester_on_suite_arch(builder, suite_info, suite, arch)
48 return builder.build()
51def _build_inst_tester_on_suite_arch(
52 builder: "InstallabilityTesterBuilder",
53 suite_info: "Suites",
54 suite: "Suite",
55 arch: str,
56) -> None:
57 packages_s_a: dict[str, "BinaryPackage"] = suite.binaries[arch]
58 is_target: bool = suite.suite_class.is_target
59 bin_prov: list[
60 tuple[dict[str, "BinaryPackage"], dict[str, set[tuple[str, str]]]]
61 ] = [(s.binaries[arch], s.provides_table[arch]) for s in suite_info]
62 solvers = get_dependency_solvers
63 for pkgdata in packages_s_a.values():
64 pkg_id: "BinaryPackageId" = pkgdata.pkg_id
65 if not builder.add_binary(
66 pkg_id, essential=pkgdata.is_essential, in_testing=is_target
67 ):
68 continue
70 conflicts: list["BinaryPackageId"] | None = None
71 if pkgdata.conflicts:
72 conflicts = []
73 conflicts_parsed = apt_pkg.parse_depends(pkgdata.conflicts, False)
74 # Breaks/Conflicts are so simple that we do not need to keep align the relation
75 # with the suite. This enables us to do a few optimizations.
76 for dep_binaries_s_a, dep_provides_s_a in bin_prov:
77 for block in (relation for relation in conflicts_parsed):
78 # if a package satisfies its own conflicts relation, then it is using §7.6.2
79 conflicts.extend(
80 s.pkg_id
81 for s in solvers(block, dep_binaries_s_a, dep_provides_s_a)
82 if s.pkg_id != pkg_id
83 )
85 if pkgdata.depends:
86 depends = _compute_depends(pkgdata, bin_prov, solvers)
87 else:
88 depends = None
90 builder.set_relations(pkg_id, depends, conflicts)
93def _compute_depends(
94 pkgdata: "BinaryPackage",
95 bin_prov: list[tuple[dict[str, "BinaryPackage"], dict[str, set[tuple[str, str]]]]],
96 solvers: Callable[
97 [
98 list[tuple[str, str, str]],
99 dict[str, "BinaryPackage"],
100 dict[str, set[tuple[str, str]]],
101 ],
102 list["BinaryPackage"],
103 ],
104) -> list[frozenset["BinaryPackageId"]]:
105 depends: list[frozenset["BinaryPackageId"]] = []
106 possible_dep_ranges: dict[str, frozenset["BinaryPackageId"]] = {}
107 assert pkgdata.depends is not None
108 for block in apt_pkg.parse_depends(pkgdata.depends, False):
109 sat = frozenset(
110 s.pkg_id
111 for binaries_s_a, provides_s_a in bin_prov
112 for s in solvers(block, binaries_s_a, provides_s_a)
113 )
115 if len(block) != 1:
116 depends.append(sat)
117 else:
118 # This dependency might be a part
119 # of a version-range a la:
120 #
121 # Depends: pkg-a (>= 1),
122 # pkg-a (<< 2~)
123 #
124 # In such a case we want to reduce
125 # that to a single clause for
126 # efficiency.
127 #
128 # In theory, it could also happen
129 # with "non-minimal" dependencies
130 # a la:
131 #
132 # Depends: pkg-a, pkg-a (>= 1)
133 #
134 # But dpkg is known to fix that up
135 # at build time, so we will
136 # probably only see "ranges" here.
137 key = block[0][0]
138 if key in possible_dep_ranges:
139 possible_dep_ranges[key] &= sat
140 else:
141 possible_dep_ranges[key] = sat
143 if possible_dep_ranges:
144 depends.extend(possible_dep_ranges.values())
146 return depends
149_T = TypeVar("_T")
152class InstallabilityTesterBuilder:
153 """Builder to create instances of InstallabilityTester"""
155 def __init__(self) -> None:
156 self._package_table: dict[
157 "BinaryPackageId",
158 tuple[
159 frozenset[frozenset["BinaryPackageId"]], frozenset["BinaryPackageId"]
160 ],
161 ] = {}
162 self._reverse_package_table: dict[
163 "BinaryPackageId",
164 tuple[
165 set["BinaryPackageId"],
166 set["BinaryPackageId"],
167 set[frozenset["PackageId"]],
168 ],
169 ] = {}
170 self._essentials: set["BinaryPackageId"] = set()
171 self._testing: set["BinaryPackageId"] = set()
172 self._internmap: dict[Any, frozenset[Any]] = {}
173 self._broken: MutableSet["BinaryPackageId"] = set()
174 self._empty_set: frozenset[Any] = self._intern_set(frozenset())
176 def add_binary(
177 self,
178 binary: "BinaryPackageId",
179 essential: bool = False,
180 in_testing: bool = False,
181 frozenset: Callable[..., Any] = frozenset,
182 ) -> bool:
183 """Add a new binary package
185 Adds a new binary package. The binary must be given as a
186 (name, version, architecture)-tuple. Returns True if this
187 binary is new (i.e. has never been added before) or False
188 otherwise.
190 Keyword arguments:
191 * essential - Whether this package is "Essential: yes".
192 * in_testing - Whether this package is in testing.
194 The frozenset argument is a private optimisation.
196 Cave-at: arch:all packages should be "re-mapped" to given
197 architecture. That is, (pkg, version, "all") should be
198 added as:
200 for arch in architectures:
201 binary = (pkg, version, arch)
202 it.add_binary(binary)
204 The resulting InstallabilityTester relies on this for
205 correctness!
206 """
207 # Note, even with a dup, we need to do these
208 if in_testing:
209 self._testing.add(binary)
210 if essential:
211 self._essentials.add(binary)
213 if binary not in self._package_table:
214 # Allow binaries to be added multiple times (happens
215 # when sid and testing have the same version)
216 self._package_table[binary] = (frozenset(), frozenset())
217 return True
218 return False
220 def set_relations(
221 self,
222 pkg_id: "BinaryPackageId",
223 dependency_clauses: Iterable[frozenset["BinaryPackageId"]] | None,
224 breaks: Iterable["BinaryPackageId"] | None,
225 ) -> None:
226 """The dependency and breaks relations for a given package
228 :param pkg_id: determines which package will have its relations set
229 :param dependency_clauses: A list/set of OR clauses (i.e. CNF with each element in
230 dependency_clauses being a disjunction). Each OR cause (disjunction) should be a
231 set/list of BinaryPackageIDs that satisfy that relation.
232 :param breaks: An list/set of BinaryPackageIDs that has a Breaks/Conflicts relation
233 on the current package. Can be None
234 """
235 if dependency_clauses is not None:
236 interned_or_clauses: frozenset[frozenset["BinaryPackageId"]] = (
237 self._intern_set(self._intern_set(c) for c in dependency_clauses)
238 )
239 satisfiable = True
240 for or_clause in interned_or_clauses:
241 if not or_clause:
242 satisfiable = False
243 for dep_tuple in or_clause:
244 rdeps, _, rdep_relations = self._reverse_relations(dep_tuple)
245 rdeps.add(pkg_id)
246 rdep_relations.add(or_clause)
248 if not satisfiable:
249 self._broken.add(pkg_id)
250 else:
251 interned_or_clauses = self._empty_set
253 if breaks is not None:
254 # Breaks
255 breaks_relations = self._intern_set(breaks)
256 for broken_binary in breaks_relations:
257 reverse_relations = self._reverse_relations(broken_binary)
258 reverse_relations[1].add(pkg_id)
259 else:
260 breaks_relations = self._empty_set
262 self._package_table[pkg_id] = (interned_or_clauses, breaks_relations)
264 def _intern_set(
265 self, s: Iterable[_T], frozenset: Callable[..., Any] = frozenset
266 ) -> frozenset[_T]:
267 """Freeze and intern a given sequence (set variant of intern())
269 Given a sequence, create a frozenset copy (if it is not
270 already a frozenset) and intern that frozen set. Returns the
271 interned set.
273 At first glance, interning sets may seem absurd. However,
274 it does enable memory savings of up to 600MB when applied
275 to the "inner" sets of the dependency clauses and all the
276 conflicts relations as well.
277 """
278 if type(s) is frozenset:
279 fset = s
280 else:
281 fset = frozenset(s)
282 fset = cast(_frozenset[_T], fset)
283 if fset in self._internmap:
284 return self._internmap[fset]
285 self._internmap[fset] = fset
286 return fset
288 def _reverse_relations(
289 self, binary: "BinaryPackageId", set: Callable[..., Any] = set
290 ) -> tuple[
291 set["BinaryPackageId"],
292 set["BinaryPackageId"],
293 set[frozenset["PackageId"]],
294 ]:
295 """Return the reverse relations for a binary
297 Fetch the reverse relations for a given binary, which are
298 created lazily.
299 """
301 if binary in self._reverse_package_table:
302 return self._reverse_package_table[binary]
303 rel = (set(), set(), set())
304 self._reverse_package_table[binary] = rel
305 return rel
307 def build(self) -> tuple[BinaryPackageUniverse, InstallabilityTester]:
308 """Compile the installability tester
310 This method will compile an installability tester from the
311 information given and (where possible) try to optimise a
312 few things.
313 """
314 package_table = self._package_table
315 reverse_package_table = self._reverse_package_table
316 intern_set = self._intern_set
317 broken = self._broken
318 not_broken: partial[filterfalse["BinaryPackageId"]] = ifilter_except(broken)
320 # Merge reverse conflicts with conflicts - this saves some
321 # operations in _check_loop since we only have to check one
322 # set (instead of two) and we remove a few duplicates here
323 # and there.
324 #
325 # At the same time, intern the rdep sets
326 for pkg in reverse_package_table:
327 assert pkg in package_table, f"{str(pkg)} referenced but not added!"
329 deps, con = package_table[pkg]
330 rdeps, rcon, rdep_relations = reverse_package_table[pkg]
331 if rcon:
332 if not con:
333 con = intern_set(rcon)
334 else:
335 con = intern_set(con | rcon)
336 package_table[pkg] = (deps, con)
337 reverse_package_table[pkg] = (
338 intern_set(rdeps),
339 con, # type: ignore[assignment]
340 intern_set(rdep_relations),
341 )
342 # this is not great, sometimes self._reverse_package_table returns
343 # frozensets, sometimes it does not
345 # Check if we can expand broken.
346 check = set()
347 for b in broken:
348 if b not in reverse_package_table:
349 continue
350 check.update(reverse_package_table[b][0] - broken)
351 for t in not_broken(iter_except(check.pop, KeyError)):
352 # This package is not known to be broken... but it might be now
353 isb = False
354 for depgroup in package_table[t][0]:
355 if not any(not_broken(depgroup)):
356 # A single clause is unsatisfiable, the
357 # package can never be installed - add it to
358 # broken.
359 isb = True
360 break
362 if not isb:
363 continue
365 broken.add(t)
367 if t not in reverse_package_table: 367 ↛ 369line 367 didn't jump to line 369 because the condition on line 367 was always true
368 continue
369 check.update(reverse_package_table[t][0] - broken)
371 if broken:
372 # Since a broken package will never be installable, nothing that depends on it
373 # will ever be installable. Thus, there is no point in keeping relations on
374 # the broken package.
375 seen = set()
376 empty_set: frozenset[Any] = frozenset()
377 null_data = (frozenset([empty_set]), empty_set)
378 for b in (x for x in broken if x in reverse_package_table):
379 for rdep in (
380 r for r in not_broken(reverse_package_table[b][0]) if r not in seen
381 ):
382 ndep = intern_set((x - broken) for x in package_table[rdep][0])
383 package_table[rdep] = (ndep, package_table[rdep][1] - broken)
384 seen.add(rdep)
386 # Since they won't affect the installability of any other package, we might as
387 # as well null their data. This memory for these packages, but likely there
388 # will only be a handful of these "at best" (fsvo of "best")
389 for b in broken:
390 package_table[b] = null_data
391 if b in reverse_package_table:
392 del reverse_package_table[b]
394 relations, eqv_set = self._build_relations_and_eqv_packages_set(
395 package_table, reverse_package_table
396 )
398 universe = BinaryPackageUniverse(
399 relations,
400 intern_set(self._essentials),
401 intern_set(broken),
402 intern_set(eqv_set),
403 )
405 solver = InstallabilityTester(universe, self._testing)
407 return universe, solver
409 def _build_relations_and_eqv_packages_set(
410 self,
411 package_table: dict[
412 "BinaryPackageId",
413 tuple[
414 frozenset[frozenset["BinaryPackageId"]], frozenset["BinaryPackageId"]
415 ],
416 ],
417 reverse_package_table: dict[
418 "BinaryPackageId",
419 tuple[
420 set["BinaryPackageId"],
421 set["BinaryPackageId"],
422 set[frozenset["PackageId"]],
423 ],
424 ],
425 frozenset: Callable[..., Any] = frozenset,
426 ) -> tuple[
427 dict["BinaryPackageId", "BinaryPackageRelation"], set["BinaryPackageId"]
428 ]:
429 """Attempt to build a table of equivalent packages
431 This method attempts to create a table of packages that are
432 equivalent (in terms of installability). If two packages (A
433 and B) are equivalent then testing the installability of A is
434 the same as testing the installability of B. This equivalency
435 also applies to co-installability.
437 The example cases:
438 * aspell-*
439 * ispell-*
441 Cases that do *not* apply:
442 * MTA's
444 The theory:
446 The packages A and B are equivalent iff:
448 reverse_depends(A) == reverse_depends(B) AND
449 conflicts(A) == conflicts(B) AND
450 depends(A) == depends(B)
452 Where "reverse_depends(X)" is the set of reverse dependencies
453 of X, "conflicts(X)" is the set of negative dependencies of X
454 (Breaks and Conflicts plus the reverse ones of those combined)
455 and "depends(X)" is the set of strong dependencies of X
456 (Depends and Pre-Depends combined).
458 To be honest, we are actually equally interested another
459 property as well, namely substitutability. The package A can
460 always used instead of B, iff:
462 reverse_depends(A) >= reverse_depends(B) AND
463 conflicts(A) <= conflicts(B) AND
464 depends(A) == depends(B)
466 (With the same definitions as above). Note that equivalency
467 is just a special-case of substitutability, where A and B can
468 substitute each other (i.e. a two-way substitution).
470 Finally, note that the "depends(A) == depends(B)" for
471 substitutability is actually not a strict requirement. There
472 are cases where those sets are different without affecting the
473 property.
474 """
475 # Despite talking about substitutability, the method currently
476 # only finds the equivalence cases. Lets leave
477 # substitutability for a future version.
479 find_eqv_set: dict[
480 tuple[
481 _frozenset[_frozenset["BinaryPackageId"]],
482 _frozenset["BinaryPackageId"],
483 set[_frozenset["PackageId"]],
484 ],
485 list["BinaryPackageId"],
486 ] = defaultdict(list)
487 eqv_set = set()
488 relations = {}
489 emptyset = frozenset()
490 intern_set = self._intern_set
492 for pkg_r in reverse_package_table:
493 rdeps_r = reverse_package_table[pkg_r][2]
494 if not rdeps_r:
495 # we don't care for things without rdeps (because
496 # it is not worth it)
497 continue
498 deps, con = package_table[pkg_r]
499 ekey = (deps, con, rdeps_r)
500 find_eqv_set[ekey].append(pkg_r)
502 for pkg_relations, pkg_list in find_eqv_set.items():
503 rdeps_e = reverse_package_table[pkg_list[0]][0]
504 rel = BinaryPackageRelation(
505 intern_set(pkg_list), pkg_relations[0], pkg_relations[1], rdeps_e
506 )
507 if len(pkg_list) < 2:
508 relations[pkg_list[0]] = rel
509 continue
511 eqv_set.update(pkg_list)
512 for pkg_e in pkg_list:
513 relations[pkg_e] = rel
515 for pkg_f, forward_relations in package_table.items():
516 if pkg_f in relations:
517 continue
518 rel = BinaryPackageRelation(
519 intern_set((pkg_f,)),
520 forward_relations[0],
521 forward_relations[1],
522 emptyset,
523 )
524 relations[pkg_f] = rel
526 return relations, eqv_set