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