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