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