Coverage for britney2/installability/builder.py: 93%
171 statements
« prev ^ index » next coverage.py v6.5.0, created at 2024-04-18 20:48 +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.
15import apt_pkg
16from collections import defaultdict
17from itertools import product
19from britney2.utils import ifilter_except, iter_except, get_dependency_solvers
20from britney2.installability.tester import InstallabilityTester
21from britney2.installability.universe import BinaryPackageRelation, BinaryPackageUniverse
24def build_installability_tester(suite_info, archs) -> tuple[BinaryPackageUniverse, InstallabilityTester]:
25 """Create the installability tester"""
27 builder = InstallabilityTesterBuilder()
29 for (suite, arch) in product(suite_info, archs):
30 _build_inst_tester_on_suite_arch(builder, suite_info, suite, arch)
32 return builder.build()
35def _build_inst_tester_on_suite_arch(builder, suite_info, suite, arch):
36 packages_s_a = suite.binaries[arch]
37 is_target = suite.suite_class.is_target
38 bin_prov = [(s.binaries[arch], s.provides_table[arch]) for s in suite_info]
39 solvers = get_dependency_solvers
40 for pkgdata in packages_s_a.values():
41 pkg_id = pkgdata.pkg_id
42 if not builder.add_binary(pkg_id,
43 essential=pkgdata.is_essential,
44 in_testing=is_target):
45 continue
47 if pkgdata.conflicts:
48 conflicts = []
49 conflicts_parsed = apt_pkg.parse_depends(pkgdata.conflicts, False)
50 # Breaks/Conflicts are so simple that we do not need to keep align the relation
51 # with the suite. This enables us to do a few optimizations.
52 for dep_binaries_s_a, dep_provides_s_a in bin_prov:
53 for block in (relation for relation in conflicts_parsed):
54 # if a package satisfies its own conflicts relation, then it is using §7.6.2
55 conflicts.extend(s.pkg_id for s in solvers(block, dep_binaries_s_a, dep_provides_s_a)
56 if s.pkg_id != pkg_id)
57 else:
58 conflicts = None
60 if pkgdata.depends:
61 depends = _compute_depends(pkgdata, bin_prov, solvers)
62 else:
63 depends = None
65 builder.set_relations(pkg_id, depends, conflicts)
68def _compute_depends(pkgdata, bin_prov, solvers):
69 depends = []
70 possible_dep_ranges = {}
71 for block in apt_pkg.parse_depends(pkgdata.depends, False):
72 sat = {s.pkg_id for binaries_s_a, provides_s_a in bin_prov
73 for s in solvers(block, binaries_s_a, provides_s_a)}
75 if len(block) != 1:
76 depends.append(sat)
77 else:
78 # This dependency might be a part
79 # of a version-range a la:
80 #
81 # Depends: pkg-a (>= 1),
82 # pkg-a (<< 2~)
83 #
84 # In such a case we want to reduce
85 # that to a single clause for
86 # efficiency.
87 #
88 # In theory, it could also happen
89 # with "non-minimal" dependencies
90 # a la:
91 #
92 # Depends: pkg-a, pkg-a (>= 1)
93 #
94 # But dpkg is known to fix that up
95 # at build time, so we will
96 # probably only see "ranges" here.
97 key = block[0][0]
98 if key in possible_dep_ranges:
99 possible_dep_ranges[key] &= sat
100 else:
101 possible_dep_ranges[key] = sat
103 if possible_dep_ranges:
104 depends.extend(possible_dep_ranges.values())
106 return depends
109class InstallabilityTesterBuilder(object):
110 """Builder to create instances of InstallabilityTester"""
112 def __init__(self):
113 self._package_table = {}
114 self._reverse_package_table = {}
115 self._essentials = set()
116 self._testing = set()
117 self._internmap = {}
118 self._broken = set()
119 self._empty_set = self._intern_set(frozenset())
121 def add_binary(self, binary, essential=False, in_testing=False,
122 frozenset=frozenset):
123 """Add a new binary package
125 Adds a new binary package. The binary must be given as a
126 (name, version, architecture)-tuple. Returns True if this
127 binary is new (i.e. has never been added before) or False
128 otherwise.
130 Keyword arguments:
131 * essential - Whether this package is "Essential: yes".
132 * in_testing - Whether this package is in testing.
134 The frozenset argument is a private optimisation.
136 Cave-at: arch:all packages should be "re-mapped" to given
137 architecture. That is, (pkg, version, "all") should be
138 added as:
140 for arch in architectures:
141 binary = (pkg, version, arch)
142 it.add_binary(binary)
144 The resulting InstallabilityTester relies on this for
145 correctness!
146 """
147 # Note, even with a dup, we need to do these
148 if in_testing:
149 self._testing.add(binary)
150 if essential:
151 self._essentials.add(binary)
153 if binary not in self._package_table:
154 # Allow binaries to be added multiple times (happens
155 # when sid and testing have the same version)
156 self._package_table[binary] = (frozenset(), frozenset())
157 return True
158 return False
160 def set_relations(self, pkg_id, dependency_clauses, breaks):
161 """The dependency and breaks relations for a given package
163 :param pkg_id: BinaryPackageID determining which package will have its relations set
164 :param dependency_clauses: A list/set of OR clauses (i.e. CNF with each element in
165 dependency_clauses being a disjunction). Each OR cause (disjunction) should be a
166 set/list of BinaryPackageIDs that satisfy that relation.
167 :param breaks: An list/set of BinaryPackageIDs that has a Breaks/Conflicts relation
168 on the current package. Can be None
169 :return: No return value
170 """
171 if dependency_clauses is not None:
172 interned_or_clauses = self._intern_set(self._intern_set(c) for c in dependency_clauses)
173 satisfiable = True
174 for or_clause in interned_or_clauses:
175 if not or_clause:
176 satisfiable = False
177 for dep_tuple in or_clause:
178 rdeps, _, rdep_relations = self._reverse_relations(dep_tuple)
179 rdeps.add(pkg_id)
180 rdep_relations.add(or_clause)
182 if not satisfiable:
183 self._broken.add(pkg_id)
184 else:
185 interned_or_clauses = self._empty_set
187 if breaks is not None:
188 # Breaks
189 breaks_relations = self._intern_set(breaks)
190 for broken_binary in breaks_relations:
191 reverse_relations = self._reverse_relations(broken_binary)
192 reverse_relations[1].add(pkg_id)
193 else:
194 breaks_relations = self._empty_set
196 self._package_table[pkg_id] = (interned_or_clauses, breaks_relations)
198 def _intern_set(self, s, frozenset=frozenset):
199 """Freeze and intern a given sequence (set variant of intern())
201 Given a sequence, create a frozenset copy (if it is not
202 already a frozenset) and intern that frozen set. Returns the
203 interned set.
205 At first glance, interning sets may seem absurd. However,
206 it does enable memory savings of up to 600MB when applied
207 to the "inner" sets of the dependency clauses and all the
208 conflicts relations as well.
209 """
210 if type(s) is frozenset:
211 fset = s
212 else:
213 fset = frozenset(s)
214 if fset in self._internmap:
215 return self._internmap[fset]
216 self._internmap[fset] = fset
217 return fset
219 def _reverse_relations(self, binary, set=set):
220 """Return the reverse relations for a binary
222 Fetch the reverse relations for a given binary, which are
223 created lazily.
224 """
226 if binary in self._reverse_package_table:
227 return self._reverse_package_table[binary]
228 rel = [set(), set(), set()]
229 self._reverse_package_table[binary] = rel
230 return rel
232 def build(self) -> tuple[BinaryPackageUniverse, InstallabilityTester]:
233 """Compile the installability tester
235 This method will compile an installability tester from the
236 information given and (where possible) try to optimise a
237 few things.
238 """
239 package_table = self._package_table
240 reverse_package_table = self._reverse_package_table
241 intern_set = self._intern_set
242 broken = self._broken
243 not_broken = ifilter_except(broken)
244 check = set(broken)
246 # Merge reverse conflicts with conflicts - this saves some
247 # operations in _check_loop since we only have to check one
248 # set (instead of two) and we remove a few duplicates here
249 # and there.
250 #
251 # At the same time, intern the rdep sets
252 for pkg in reverse_package_table:
253 if pkg not in package_table: # pragma: no cover
254 raise AssertionError("%s referenced but not added!" % str(pkg))
255 deps, con = package_table[pkg]
256 rdeps, rcon, rdep_relations = reverse_package_table[pkg]
257 if rcon:
258 if not con:
259 con = intern_set(rcon)
260 else:
261 con = intern_set(con | rcon)
262 package_table[pkg] = (deps, con)
263 reverse_package_table[pkg] = (intern_set(rdeps), con,
264 intern_set(rdep_relations))
266 # Check if we can expand broken.
267 for t in not_broken(iter_except(check.pop, KeyError)): 267 ↛ 269line 267 didn't jump to line 269, because the loop on line 267 never started
268 # This package is not known to be broken... but it might be now
269 isb = False
270 for depgroup in package_table[t][0]:
271 if not any(not_broken(depgroup)):
272 # A single clause is unsatisfiable, the
273 # package can never be installed - add it to
274 # broken.
275 isb = True
276 break
278 if not isb:
279 continue
281 broken.add(t)
283 if t not in reverse_package_table:
284 continue
285 check.update(reverse_package_table[t][0] - broken)
287 if broken:
288 # Since a broken package will never be installable, nothing that depends on it
289 # will ever be installable. Thus, there is no point in keeping relations on
290 # the broken package.
291 seen = set()
292 empty_set = frozenset()
293 null_data = (frozenset([empty_set]), empty_set)
294 for b in (x for x in broken if x in reverse_package_table):
295 for rdep in (r for r in not_broken(reverse_package_table[b][0])
296 if r not in seen):
297 ndep = intern_set((x - broken) for x in package_table[rdep][0])
298 package_table[rdep] = (ndep, package_table[rdep][1] - broken)
299 seen.add(rdep)
301 # Since they won't affect the installability of any other package, we might as
302 # as well null their data. This memory for these packages, but likely there
303 # will only be a handful of these "at best" (fsvo of "best")
304 for b in broken:
305 package_table[b] = null_data
306 if b in reverse_package_table:
307 del reverse_package_table[b]
309 relations, eqv_set = self._build_relations_and_eqv_packages_set(package_table, reverse_package_table)
311 universe = BinaryPackageUniverse(relations,
312 intern_set(self._essentials),
313 intern_set(broken),
314 intern_set(eqv_set))
316 solver = InstallabilityTester(universe, self._testing)
318 return universe, solver
320 def _build_relations_and_eqv_packages_set(self,
321 package_table,
322 reverse_package_table,
323 frozenset=frozenset):
324 """Attempt to build a table of equivalent packages
326 This method attempts to create a table of packages that are
327 equivalent (in terms of installability). If two packages (A
328 and B) are equivalent then testing the installability of A is
329 the same as testing the installability of B. This equivalency
330 also applies to co-installability.
332 The example cases:
333 * aspell-*
334 * ispell-*
336 Cases that do *not* apply:
337 * MTA's
339 The theory:
341 The packages A and B are equivalent iff:
343 reverse_depends(A) == reverse_depends(B) AND
344 conflicts(A) == conflicts(B) AND
345 depends(A) == depends(B)
347 Where "reverse_depends(X)" is the set of reverse dependencies
348 of X, "conflicts(X)" is the set of negative dependencies of X
349 (Breaks and Conflicts plus the reverse ones of those combined)
350 and "depends(X)" is the set of strong dependencies of X
351 (Depends and Pre-Depends combined).
353 To be honest, we are actually equally interested another
354 property as well, namely substitutability. The package A can
355 always used instead of B, iff:
357 reverse_depends(A) >= reverse_depends(B) AND
358 conflicts(A) <= conflicts(B) AND
359 depends(A) == depends(B)
361 (With the same definitions as above). Note that equivalency
362 is just a special-case of substitutability, where A and B can
363 substitute each other (i.e. a two-way substitution).
365 Finally, note that the "depends(A) == depends(B)" for
366 substitutability is actually not a strict requirement. There
367 are cases where those sets are different without affecting the
368 property.
369 """
370 # Despite talking about substitutability, the method currently
371 # only finds the equivalence cases. Lets leave
372 # substitutability for a future version.
374 find_eqv_set = defaultdict(list)
375 eqv_set = set()
376 relations = {}
377 emptyset = frozenset()
378 intern_set = self._intern_set
380 for pkg in reverse_package_table:
381 rdeps = reverse_package_table[pkg][2]
382 if not rdeps:
383 # we don't care for things without rdeps (because
384 # it is not worth it)
385 continue
386 deps, con = package_table[pkg]
387 ekey = (deps, con, rdeps)
388 find_eqv_set[ekey].append(pkg)
390 for pkg_relations, pkg_list in find_eqv_set.items():
391 rdeps = reverse_package_table[pkg_list[0]][0]
392 rel = BinaryPackageRelation(intern_set(pkg_list), pkg_relations[0], pkg_relations[1], rdeps)
393 if len(pkg_list) < 2:
394 relations[pkg_list[0]] = rel
395 continue
397 eqv_set.update(pkg_list)
398 for pkg in pkg_list:
399 relations[pkg] = rel
401 for pkg, forward_relations in package_table.items():
402 if pkg in relations:
403 continue
404 rel = BinaryPackageRelation(intern_set((pkg,)), forward_relations[0], forward_relations[1], emptyset)
405 relations[pkg] = rel
407 return relations, eqv_set