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