Bug#660409: Rewrite Britney's installability tester in python
tags 660409 + patch
thanks
On 2012-02-18 23:28, Niels Thykier wrote:
> Package: release.debian.org
> Severity: wishlist
> User: release.debian.org@packages.debian.org
> Usertags: britney
>
>
> Hi,
>
> I took a look at replacing Britney's installability tester[1]. In my
> follow up mail I will attach my patches[2]. Part of my focus has been
> to implement this as a(n almost) compatible replacement for the old
> module.
>
> [...]
>
> ~Niels
>
> [...]
>
>
See attached patches.
~Niels
>From 8078b5751696a7f51a1a9469a73642b3276a22ac Mon Sep 17 00:00:00 2001
From: Niels Thykier <niels@thykier.net>
Date: Tue, 13 Dec 2011 18:52:01 +0100
Subject: [PATCH 1/3] Move installability testing to a separate module
Signed-off-by: Niels Thykier <niels@thykier.net>
---
britney.py | 6 +++---
installability.py | 43 +++++++++++++++++++++++++++++++++++++++++++
2 files changed, 46 insertions(+), 3 deletions(-)
create mode 100644 installability.py
diff --git a/britney.py b/britney.py
index 604e7ab..76938b7 100755
--- a/britney.py
+++ b/britney.py
@@ -209,10 +209,10 @@ if __name__ == '__main__':
# it useless).
sys.path.insert(0, idir)
+from installability import InstallabilityTester
from excuse import Excuse
from migrationitem import MigrationItem, HintItem
from hints import HintCollection
-from britney import buildSystem
__author__ = 'Fabio Tranchitella and the Debian Release Team'
@@ -428,7 +428,7 @@ class Britney(object):
if packages[k][PROVIDES]:
packages[k][PROVIDES] = ", ".join(packages[k][PROVIDES])
else: packages[k][PROVIDES] = None
- self.systems[a] = buildSystem(a, packages)
+ self.systems[a] = InstallabilityTester(a, packages)
def read_sources(self, basedir):
"""Read the list of source packages from the specified directory
@@ -2253,7 +2253,7 @@ class Britney(object):
"""Undoes one or more changes to testing
* lundo is a list of (undo, item)-tuples
- * systems is the britney-py.c system
+ * systems is an InstallabilityTester
* sources is the table of all source packages for all suites
* binaries is the table of all binary packages for all suites
and architectures
diff --git a/installability.py b/installability.py
new file mode 100644
index 0000000..3e5f0e4
--- /dev/null
+++ b/installability.py
@@ -0,0 +1,43 @@
+# -*- coding: utf-8 -*-
+
+# Copyright (C) 2011 Niels Thykier <niels@thykier.net>
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+
+from britney import buildSystem
+
+class InstallabilityTester(object):
+
+ def __init__(self, arch, packages):
+ self._arch = arch
+ self._system = buildSystem(arch, packages)
+
+ @property
+ def arch(self):
+ """Returns the architecture for this package set
+ """
+ return self._arch
+
+ def add_binary(self, pkg_name, binary_data):
+ """Add a binary to the package set
+ """
+ return self._system.add_binary(pkg_name, binary_data)
+
+ def remove_binary(self, pkg_name):
+ """Remove a binary from the package set
+ """
+ return self._system.remove_binary(pkg_name)
+
+ def is_installable(self, pkg_name):
+ """Test if pkg_name is installable in this package set
+ """
+ return self._system.is_installable(pkg_name)
+
--
1.7.9
>From d9548bfe5bb725e7c5a29a53c7e3ac94a3472d63 Mon Sep 17 00:00:00 2001
From: Niels Thykier <niels@thykier.net>
Date: Sat, 18 Feb 2012 18:51:05 +0100
Subject: [PATCH 2/3] Defer building the nun-inst cache
This is needed for the next commit, where the "per-arch"
installability tester disappears.
Signed-off-by: Niels Thykier <niels@thykier.net>
---
britney.py | 46 +++++++++++++++++++++++-----------------------
1 files changed, 23 insertions(+), 23 deletions(-)
diff --git a/britney.py b/britney.py
index 76938b7..267a027 100755
--- a/britney.py
+++ b/britney.py
@@ -274,30 +274,12 @@ class Britney(object):
# if requested, build the non-installable status and save it
# if this or the population of self.binaries below takes a very
# long time, try increasing SIZEOFHASHMAP in lib/dpkg.c and rebuilding
- if not self.options.nuninst_cache:
- self.__log("Building the list of non-installable packages for the full archive", type="I")
- self.sources['testing'] = self.read_sources(self.options.testing)
- self.binaries['testing'] = {}
- nuninst = {}
- for arch in self.options.architectures:
- self.binaries['testing'][arch] = self.read_binaries(self.options.testing, "testing", arch)
- self.build_systems(arch)
- self.__log("> Checking for non-installable packages for architecture %s" % arch, type="I")
- result = self.get_nuninst(arch, build=True)
- nuninst.update(result)
- self.__log("> Found %d non-installable packages" % len(nuninst[arch]), type="I")
- if self.options.print_uninst:
- self.nuninst_arch_report(nuninst, arch)
- if not self.options.print_uninst:
- self.write_nuninst(nuninst)
- else:
+ if self.options.nuninst_cache:
self.__log("Not building the list of non-installable packages, as requested", type="I")
-
- # if running in --print-uninst mode, quit here
- if self.options.print_uninst:
- print '* summary'
- print '\n'.join(map(lambda x: '%4d %s' % (len(nuninst[x]), x), self.options.architectures))
- return
+ if self.options.print_uninst:
+ print '* summary'
+ print '\n'.join(map(lambda x: '%4d %s' % (len(nuninst[x]), x), self.options.architectures))
+ return
# read the source and binary packages for the involved distributions
# if this takes a very long time, try increasing SIZEOFHASHMAP in
@@ -328,6 +310,24 @@ class Britney(object):
# build the testing system
self.build_systems(arch)
+ if not self.options.nuninst_cache:
+ self.__log("Building the list of non-installable packages for the full archive", type="I")
+ nuninst = {}
+ for arch in self.options.architectures:
+ self.__log("> Checking for non-installable packages for architecture %s" % arch, type="I")
+ result = self.get_nuninst(arch, build=True)
+ nuninst.update(result)
+ self.__log("> Found %d non-installable packages" % len(nuninst[arch]), type="I")
+ if self.options.print_uninst:
+ self.nuninst_arch_report(nuninst, arch)
+
+ if self.options.print_uninst:
+ print '* summary'
+ print '\n'.join(map(lambda x: '%4d %s' % (len(nuninst[x]), x), self.options.architectures))
+ return
+ else:
+ self.write_nuninst(nuninst)
+
# read the release-critical bug summaries for testing and unstable
self.bugs = {'unstable': self.read_bugs(self.options.unstable),
'testing': self.read_bugs(self.options.testing),}
--
1.7.9
>From 2eac5fca43027c57d538df02824e376f56838676 Mon Sep 17 00:00:00 2001
From: Niels Thykier <niels@thykier.net>
Date: Sat, 18 Feb 2012 19:36:48 +0100
Subject: [PATCH 3/3] Rewrite installability tester
The new Installability Tester (IT) module replaces the remaining
C-parts. Unlike C-implementation, it does not give up and emit an
"AIEEE" half-way through.
In order to determine installability, it uses two sets "musts" and
"never". As the names suggest, the sets represents the packages that
must be (co-)installable with the package being tested and those that
can never be co-installable. For a package to be installable, "musts"
and "never" have remain disjoint.
These sets are also used to reduce the number of alternatives that are
available to satisfy a given dependency. When these sets are unable
to remove the choice completely, the new IT defers the choice to later.
This occasionally reduces backtracking as a later package may conflict
or unconditionally depend on one of the remaining alternatives.
Speed-wise, the implementation is comparable, but is slower on 2 out
of 3 live-data samples. A substansial part of the speed-regression
appears to disappear when using Python2.7.
Signed-off-by: Niels Thykier <niels@thykier.net>
---
britney.py | 203 ++++++++++++++++++++-------
installability.py | 404 ++++++++++++++++++++++++++++++++++++++++++++++++++---
2 files changed, 536 insertions(+), 71 deletions(-)
diff --git a/britney.py b/britney.py
index 267a027..8ee56c7 100755
--- a/britney.py
+++ b/britney.py
@@ -267,7 +267,6 @@ class Britney(object):
# initialize the apt_pkg back-end
apt_pkg.init()
- self.systems = {}
self.sources = {}
self.binaries = {}
@@ -298,7 +297,8 @@ class Britney(object):
self.binaries['testing'] = {}
self.binaries['unstable'] = {}
self.binaries['tpu'] = {}
- self.binaries['pu'] = {}
+ if hasattr(self.options, 'pu'):
+ self.binaries['pu'] = {}
for arch in self.options.architectures:
if arch not in self.binaries['testing']:
@@ -307,8 +307,25 @@ class Britney(object):
self.binaries['tpu'][arch] = self.read_binaries(self.options.tpu, "tpu", arch)
if hasattr(self.options, 'pu'):
self.binaries['pu'][arch] = self.read_binaries(self.options.pu, "pu", arch)
- # build the testing system
- self.build_systems(arch)
+ self._build_installability_tester(self.options.architectures)
+
+ if not self.options.nuninst_cache:
+ self.__log("Building the list of non-installable packages for the full archive", type="I")
+ nuninst = {}
+ for arch in self.options.architectures:
+ self.__log("> Checking for non-installable packages for architecture %s" % arch, type="I")
+ result = self.get_nuninst(arch, build=True)
+ nuninst.update(result)
+ self.__log("> Found %d non-installable packages" % len(nuninst[arch]), type="I")
+ if self.options.print_uninst:
+ self.nuninst_arch_report(nuninst, arch)
+
+ if self.options.print_uninst:
+ print '* summary'
+ print '\n'.join(map(lambda x: '%4d %s' % (len(nuninst[x]), x), self.options.architectures))
+ return
+ else:
+ self.write_nuninst(nuninst)
if not self.options.nuninst_cache:
self.__log("Building the list of non-installable packages for the full archive", type="I")
@@ -415,21 +432,90 @@ class Britney(object):
if self.options.verbose or type in ("E", "W"):
print "%s: [%s] - %s" % (type, time.asctime(), msg)
+ def _build_installability_tester(self, archs):
+ """Create the installability tester"""
+ # set of (name, version, arch) tuples
+ # - multiple versions allowed (smooth updates)
+ testing = set()
+ # map (name, version, arch) -> (set([deps]), set([conflicts]))
+ pkguniverse = {}
+ # map (name, version, arch) -> (set([rdeps]), set([rconflicts]))
+ pkgrevuniverse = {}
+ # set (name, version, arch) - packages that has
+ # unsatisfiable dependency clauses
+ broken = set()
+ solvers = self.get_dependency_solvers
+ binaries = self.binaries
+ for dist in binaries:
+ for arch in archs:
+ for pkgname in binaries[dist][arch][0]:
+ pkgdata = binaries[dist][arch][0][pkgname]
+ version = pkgdata[VERSION]
+ t = (pkgname, version, arch)
+ if t in pkguniverse:
+ # skip repeated packages - we assume them to
+ # be identical. This usually happens if
+ # testing and unstable have the same version.
+ continue
+ depends = []
+ conflicts = []
+ deptuples = set()
+ contuples = set()
+ # We do not differ between depends and pre-depends
+ if pkgdata[DEPENDS]:
+ depends.extend(apt_pkg.parse_depends(pkgdata[DEPENDS], False))
+ if pkgdata[PREDEPENDS]:
+ depends.extend(apt_pkg.parse_depends(pkgdata[PREDEPENDS], False))
+ if pkgdata[CONFLICTS]:
+ conflicts = apt_pkg.parse_depends(pkgdata[CONFLICTS], False)
+
+ for (al, tl, dep) in [(depends, deptuples, True), \
+ (conflicts, contuples, False)]:
+ for block in al:
+ sat = set()
+ for d in binaries:
+ if d not in binaries or arch not in binaries[d]:
+ continue
+ (_, pkgs) = solvers(block, arch, d)
+ for p in pkgs:
+ pdata = binaries[d][arch][0][p]
+ pt = (p, pdata[VERSION], arch)
+ if dep:
+ sat.add(pt)
+ else:
+ tl.add(pt)
+ if dep:
+ if not sat:
+ # No package across all suites satisfy the dep relation.
+ # This makes t broken
+ broken.add(t)
+ tl.add(frozenset(sat))
+
+ # if t satisfies its own conflicts relation, then it is using §7.6.2
+ # - so filter out self-conflicts
+ contuples.discard(t)
+ pkguniverse[t] = (frozenset(deptuples), frozenset(contuples))
+ if dist == 'testing':
+ testing.add(t)
+
+ for t in pkguniverse:
+ (deps, conflicts) = pkguniverse[t]
+ for dgroup in deps:
+ for dep in dgroup:
+ if dep not in pkgrevuniverse:
+ pkgrevuniverse[dep] = [set(), set()]
+ pkgrevuniverse[dep][0].add(t)
+ for con in conflicts:
+ if con not in pkgrevuniverse:
+ pkgrevuniverse[con] = [set(), set()]
+ pkgrevuniverse[con][1].add(t)
+
+ self._inst_tester = InstallabilityTester(pkguniverse, pkgrevuniverse, testing, broken)
+
+
# Data reading/writing methods
# ----------------------------
- def build_systems(self, arch=None):
- for a in self.options.architectures:
- if arch and a != arch: continue
- packages = {}
- binaries = self.binaries['testing'][arch][0].copy()
- for k in binaries:
- packages[k] = binaries[k][:]
- if packages[k][PROVIDES]:
- packages[k][PROVIDES] = ", ".join(packages[k][PROVIDES])
- else: packages[k][PROVIDES] = None
- self.systems[a] = InstallabilityTester(a, packages)
-
def read_sources(self, basedir):
"""Read the list of source packages from the specified directory
@@ -1706,7 +1792,7 @@ class Britney(object):
# local copies for better performance
binaries = self.binaries['testing']
- systems = self.systems
+ inst_tester = self._inst_tester
# for all the architectures
for arch in self.options.architectures:
@@ -1720,7 +1806,8 @@ class Britney(object):
# uninstallable package is found
nuninst[arch] = set()
for pkg_name in binaries[arch][0]:
- r = systems[arch].is_installable(pkg_name)
+ pkgdata = binaries[arch][0][pkg_name]
+ r = inst_tester.is_installable(pkg_name, pkgdata[VERSION], arch)
if not r:
nuninst[arch].add(pkg_name)
@@ -1874,8 +1961,9 @@ class Britney(object):
if len(binaries[parch][1][j]) == 0:
del binaries[parch][1][j]
# finally, remove the binary package
+ version = binaries[parch][0][binary][VERSION]
del binaries[parch][0][binary]
- self.systems[parch].remove_binary(binary)
+ self._inst_tester.remove_testing_binary(binary, version, parch)
# remove the source package
if item.architecture == 'source':
undo['sources'][item.package] = source
@@ -1890,8 +1978,10 @@ class Britney(object):
undo['binaries'][item.package + "/" + item.architecture] = binaries[item.architecture][0][item.package]
affected.update( [ (x, item.architecture) for x in \
self.get_reverse_tree(item.package, item.architecture, 'testing') ] )
+ version = binaries[item.architecture][0][item.package][VERSION]
del binaries[item.architecture][0][item.package]
- self.systems[item.architecture].remove_binary(item.package)
+ self._inst_tester.remove_testing_binary(item.package, version, item.architecture)
+
# add the new binary packages (if we are not removing)
if not item.is_removal:
@@ -1916,7 +2006,8 @@ class Britney(object):
for p in self.get_full_tree(j, parch, 'testing'):
key = (p, parch)
if key not in affected: affected.add(key)
- self.systems[parch].remove_binary(binary)
+ version = binaries[parch][0][binary][VERSION]
+ self._inst_tester.remove_testing_binary(binary, version, parch)
else:
# if the binary was previously built by a different
# source package in testing, all of the reverse
@@ -1934,8 +2025,8 @@ class Britney(object):
self.get_reverse_tree(rdep, parch, 'testing') ] )
# add/update the binary package
binaries[parch][0][binary] = self.binaries[item.suite][parch][0][binary]
- self.systems[parch].add_binary(binary, binaries[parch][0][binary][:PROVIDES] + \
- [", ".join(binaries[parch][0][binary][PROVIDES]) or None])
+ version = binaries[parch][0][binary][VERSION]
+ self._inst_tester.add_testing_binary(binary, version, parch)
# register new provided packages
for j in binaries[parch][0][binary][PROVIDES]:
key = j + "/" + parch
@@ -2021,7 +2112,6 @@ class Britney(object):
# local copies for better performance
binaries = self.binaries['testing']
sources = self.sources
- systems = self.systems
architectures = self.options.architectures
nobreakall_arches = self.options.nobreakall_arches.split()
new_arches = self.options.new_arches.split()
@@ -2090,10 +2180,13 @@ class Britney(object):
for p in [x[0] for x in affected if x[1] == arch]:
if p not in binaries[arch][0]:
continue
+ pkgdata = binaries[arch][0][p]
+ version = pkgdata[VERSION]
+ parch = pkgdata[ARCHITECTURE]
nuninst_arch = None
- if not (skip_archall and binaries[arch][0][p][ARCHITECTURE] == 'all'):
+ if not (skip_archall and parch == 'all'):
nuninst_arch = nuninst[arch]
- self._installability_test(systems[arch], p, broken, to_check, nuninst_arch)
+ self._installability_test(p, version, arch, broken, to_check, nuninst_arch)
# broken packages (second round, reverse dependencies of the first round)
while to_check:
@@ -2102,10 +2195,13 @@ class Britney(object):
for p in binaries[arch][0][j][RDEPENDS]:
if p in broken or p not in binaries[arch][0]:
continue
+ pkgdata = binaries[arch][0][p]
+ version = pkgdata[VERSION]
+ parch = pkgdata[ARCHITECTURE]
nuninst_arch = None
- if not (skip_archall and binaries[arch][0][p][ARCHITECTURE] == 'all'):
+ if not (skip_archall and arch == 'all'):
nuninst_arch = nuninst[arch]
- self._installability_test(systems[arch], p, broken, to_check, nuninst_arch)
+ self._installability_test(p, version, arch, broken, to_check, nuninst_arch)
# if we are processing hints, go ahead
if hint:
@@ -2148,7 +2244,7 @@ class Britney(object):
skipped.append(pkg)
single_undo = [(undo, item)]
# (local-scope) binaries is actually self.binaries["testing"] so we cannot use it here.
- self.undo_changes(single_undo, systems, sources, self.binaries)
+ self.undo_changes(single_undo, sources, self.binaries)
# if we are processing hints, return now
if hint:
@@ -2246,14 +2342,13 @@ class Britney(object):
self.output_write("FAILED\n")
if not undo: return
- self.undo_changes(lundo, self.systems, self.sources, self.binaries)
+ self.undo_changes(lundo, self.sources, self.binaries)
- def undo_changes(self, lundo, systems, sources, binaries):
+ def undo_changes(self, lundo, sources, binaries):
"""Undoes one or more changes to testing
* lundo is a list of (undo, item)-tuples
- * systems is an InstallabilityTester
* sources is the table of all source packages for all suites
* binaries is the table of all binary packages for all suites
and architectures
@@ -2266,7 +2361,7 @@ class Britney(object):
# see commit:ef71f0e33a7c3d8ef223ec9ad5e9843777e68133 and
# #624716 for the issues we had when we did not do this.
-
+ inst_tester = self._inst_tester
# STEP 1
# undo all the changes for sources
for (undo, item) in lundo:
@@ -2283,8 +2378,9 @@ class Britney(object):
for p in sources[item.suite][item.package][BINARIES]:
binary, arch = p.split("/")
if item.architecture in ['source', arch]:
+ version = binaries["testing"][arch][0][binary][VERSION]
del binaries["testing"][arch][0][binary]
- systems[arch].remove_binary(binary)
+ inst_tester.remove_testing_binary(binary, version, arch)
# STEP 3
@@ -2293,14 +2389,17 @@ class Britney(object):
for p in undo['binaries'].keys():
binary, arch = p.split("/")
if binary[0] == "-":
+ version = binaries["testing"][arch][0][binary][VERSION]
del binaries['testing'][arch][0][binary[1:]]
- systems[arch].remove_binary(binary[1:])
+ inst_tester.remove_testing_binary(binary, version, arch)
else:
binaries_t_a = binaries['testing'][arch][0]
- binaries_t_a[binary] = undo['binaries'][p]
- systems[arch].remove_binary(binary)
- systems[arch].add_binary(binary, binaries_t_a[binary][:PROVIDES] + \
- [", ".join(binaries_t_a[binary][PROVIDES]) or None])
+ if p in binaries_t_a:
+ rmpkgdata = binaries_t_a[p]
+ inst_tester.remove_testing_binary(binary, rmpkgdata[VERSION], arch)
+ pkgdata = undo['binaries'][p]
+ binaries_t_a[binary] = pkgdata
+ inst_tester.add_testing_binary(binary, pkgdata[VERSION], arch)
# STEP 4
# undo all changes to virtual packages
@@ -2721,10 +2820,10 @@ class Britney(object):
self.__output.close()
- def _installability_test(self, system, p, broken, to_check, nuninst_arch):
+ def _installability_test(self, pkg_name, pkg_version, pkg_arch, broken, to_check, nuninst_arch):
"""Test for installability of a package on an architecture
- p is the package to check and system does the actual check.
+ (pkg_name, pkg_version, pkg_arch) is the package to check.
broken is the set of broken packages. If p changes
installability (e.g. goes from uninstallable to installable),
@@ -2734,20 +2833,20 @@ class Britney(object):
If nuninst_arch is not None then it also updated in the same
way as broken is.
"""
- r = system.is_installable(p)
+ r = self._inst_tester.is_installable(pkg_name, pkg_version, pkg_arch)
if not r:
# not installable
- if p not in broken:
- broken.add(p)
- to_check.append(p)
- if nuninst_arch is not None and p not in nuninst_arch:
- nuninst_arch.add(p)
+ if pkg_name not in broken:
+ broken.add(pkg_name)
+ to_check.append(pkg_name)
+ if nuninst_arch is not None and pkg_name not in nuninst_arch:
+ nuninst_arch.add(pkg_name)
else:
- if p in broken:
- to_check.append(p)
- broken.remove(p)
- if nuninst_arch is not None and p in nuninst_arch:
- nuninst_arch.remove(p)
+ if pkg_name in broken:
+ to_check.append(pkg_name)
+ broken.remove(pkg_name)
+ if nuninst_arch is not None and pkg_name in nuninst_arch:
+ nuninst_arch.remove(pkg_name)
if __name__ == '__main__':
diff --git a/installability.py b/installability.py
index 3e5f0e4..ad3476d 100644
--- a/installability.py
+++ b/installability.py
@@ -1,6 +1,6 @@
# -*- coding: utf-8 -*-
-# Copyright (C) 2011 Niels Thykier <niels@thykier.net>
+# Copyright (C) 2012 Niels Thykier <niels@thykier.net>
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
@@ -12,32 +12,398 @@
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
-from britney import buildSystem
-
class InstallabilityTester(object):
- def __init__(self, arch, packages):
- self._arch = arch
- self._system = buildSystem(arch, packages)
+ def __init__(self, universe, revuniverse, testing, broken):
+ """Create a new installability tester
+
+ universe is a dict mapping package tuples to their
+ dependencies and conflicts.
+
+ revuniverse is a dict mapping package tuples to their reverse
+ dependencies and reverse conflicts.
+
+ testing is a (mutable) set of package tuples that determines
+ which of the packages in universe are currently in testing.
- @property
- def arch(self):
- """Returns the architecture for this package set
+ broken is a (mutable) set of package tuples that are known to
+ be uninstallable.
+
+ Package tuple: (pkg_name, pkg_version, pkg_arch)
+ - NB: arch:all packages are "re-mapped" to given architecture.
+ (simplifies caches and dependency checking)
"""
- return self._arch
- def add_binary(self, pkg_name, binary_data):
- """Add a binary to the package set
+ self._universe = universe
+ self._revuniverse = revuniverse
+ self._testing = testing
+ self._broken = broken
+ # the "safe set" is a set of packages that will not involve
+ # conflicts. It can occasionally be used to break a choice.
+ self._safe_set = set()
+ # Cache of packages known to be broken - we deliberately do not
+ # include "broken" in it. See _optimize for more info.
+ self._cache_broken = set()
+ # Cache of packages known to be installable
+ self._cache_inst = set()
+ self._optimize()
+
+ def add_testing_binary(self, pkg_name, pkg_version, pkg_arch):
+ """Add a binary package to "testing"
+
+ If the package is not known, this method will throw an
+ Keyrror.
"""
- return self._system.add_binary(pkg_name, binary_data)
- def remove_binary(self, pkg_name):
- """Remove a binary from the package set
+ t = (pkg_name, pkg_version, pkg_arch)
+
+ if t not in self._universe:
+ raise KeyError(str(t))
+
+ if t in self._broken:
+ self._testing.add(t)
+ elif t not in self._testing:
+ self._testing.add(t)
+ self._cache_inst = set()
+ self._cache_broken = set()
+
+ return True
+
+ def remove_testing_binary(self, pkg_name, pkg_version, pkg_arch):
+ """Remove a binary from "testing"
+
+ If the package is not known, this method will throw an
+ Keyrror.
"""
- return self._system.remove_binary(pkg_name)
- def is_installable(self, pkg_name):
- """Test if pkg_name is installable in this package set
+ t = (pkg_name, pkg_version, pkg_arch)
+
+ if t not in self._universe:
+ raise KeyError(str(t))
+
+ if t in self._testing:
+ self._testing.remove(t)
+ if t not in self._revuniverse:
+ # no reverse relations - safe
+ return True
+ if t not in self._broken and (t in self._cache_inst or t in self._cache_broken):
+ # It is in our cache (and not guaranteed to be broken) - throw out the cache
+ self._cache_inst = set()
+ self._cache_broken = set()
+
+ return True
+
+ def is_installable(self, pkg_name, pkg_version, pkg_arch, _m=frozenset(), _n=frozenset(), _c=frozenset()):
+ """Test if a package is installable in this package set
+
+ The package is assumed to be in "testing" and only packages in
+ "testing" can be used to satisfy relations.
+
+ Returns True iff the package is installable.
+ Returns False otherwise.
"""
- return self._system.is_installable(pkg_name)
+ # Note the _m, _n and _c arguments are for recursive calls. They
+ # are used to pass on the current state of "musts", "never" and
+ # "choices" (see below).
+
+ t = (pkg_name, pkg_version, pkg_arch)
+
+ if t in self._cache_inst and not _n:
+ # use the inst cache only if "never" is "clean" - our cache result
+ # might have been based on something that our pre-seeded "never"
+ # contains.
+ return True
+
+ if t in self._cache_broken or t in self._broken:
+ return False
+
+ if t not in self._universe:
+ raise KeyError(str(t))
+
+
+ universe = self._universe
+ revuniverse = self._revuniverse
+ testing = self._testing
+ cbroken = self._cache_broken
+ cache_inst = self._cache_inst
+ safe_set = self._safe_set
+
+
+ # Our installability verdict - start with "yes" and change if
+ # prove otherwise.
+ verdict = True
+
+ # set of packages that must be installed with this package
+ musts = set(_m)
+ musts.add(t)
+ # set of packages we can *never* choose (e.g. due to conflicts)
+ never = set(_n)
+ # set of relations were we have a choice, but where we have not
+ # committed ourselves yet. Hopefully some choices may be taken
+ # for us (if one of the alternatives appear in "musts")
+ choices = set(_c)
+
+ # The subset of musts we haven't checked yet.
+ check = set([t])
+
+
+ # Useful things to remember:
+ #
+ # * musts and never are disjointed at all times
+ # - if not, t cannot be installable. Either t, or one of
+ # its dependencies conflict with t or one of its (other)
+ # dependencies.
+ #
+ # * choices should generally be avoided as much as possible.
+ # - picking a bad choice requires backtracking
+ # - sometimes musts/never will eventually "solve" the choice.
+ #
+ # * check never includes choices (these are always in choices)
+ #
+ # * A package is installable if never and musts are disjoined
+ # and both check and choices are empty.
+ # - exception: _pick_choice may determine the installability
+ # of t via recursion (calls is_installable). In this case
+ # check and choices are not (always) empty.
+
+ def _check_loop():
+ """Finds all guaranteed dependencies via "check".
+
+ If it returns False, t is not installable. If it returns True
+ then "check" is exhausted. If "choices" are empty and this
+ returns True, then t is installable.
+ """
+ # While we have guaranteed dependencies (in check), examine all
+ # of them.
+ while check:
+ cur = check.pop()
+ check_never = False
+
+ if universe[cur][1]:
+ # We must install cur for the package to be installable,
+ # so "obviously" we can never choose any of its conflicts
+ never.update(universe[cur][1] & testing)
+ check_never = True
+
+ if cur in revuniverse and revuniverse[cur][1]:
+ # Flag reverse-conflicts as unacceptable as well
+ never.update(revuniverse[cur][1] & testing)
+ check_never = True
+
+ if check_never and cur in never:
+ # cur adds a (reverse) conflict, so check if cur
+ # is in never.
+ #
+ # - there is a window where two conflicting
+ # packages can be in check. Example "A" depends
+ # on "B" and "C". If "B" conflicts with "C",
+ # then both "B" and "C" could end in "check".
+ return False
+
+ for depgroup in universe[cur][0]:
+ if not depgroup.isdisjoint(musts):
+ # depgroup can be satisifed by picking something that is
+ # already in musts - lets pick that (again). :)
+ continue
+
+ # Of all the packages listed in the relation remove those that
+ # are either:
+ # - not in testing
+ # - known to be broken (by cache)
+ # - in never
+ candidates = frozenset((depgroup & testing) - cbroken - never)
+
+ if len(candidates) == 0:
+ # We got no candidates to satisfy it - this
+ # package cannot be installed with the current
+ # testing
+ if depgroup.isdisjoint(never):
+ # cur's dependency cannot be satisfied even if never was empty.
+ # This means that cur itself is broken (as well).
+ cbroken.add(cur)
+ return False
+ if len(candidates) == 1:
+ # only one possible solution to this choice and we
+ # haven't seen it before
+ check.update(candidates)
+ musts.update(candidates)
+ else:
+ # defer this choice till later
+ choices.add(candidates)
+ return True
+ # END _check_loop
+
+ def _pick_choice(rebuild):
+ """Picks a choice from choices and updates rebuild.
+
+ Prunes the choices and updates "rebuild" to reflect the
+ pruned choices.
+
+ Returns True if t is installable (determined via recursion).
+ Returns False if a choice was picked and added to check.
+ Returns None if t is uninstallable (no choice can be picked).
+
+ NB: If this returns False, choices should be replaced by
+ rebuild.
+ """
+
+ for choice in choices:
+ if not choice.isdisjoint(musts):
+ # We already satisfied/chosen at least one of the litterals
+ # in the choice, so the choice is gone
+ continue
+ remain = choice - never
+
+ if not remain:
+ # all alternatives would violate the conflicts => package is not installable
+ return None
+ if len(remain) == 1:
+ # the choice was reduced to one package we haven't checked - check that
+ check.update(remain)
+ continue
+ # The choice is still deferred
+ rebuild.add(frozenset(remain))
+
+ if check or not rebuild:
+ return False
+
+ for choice in rebuild:
+ for p in choice:
+ if p in safe_set and p in cache_inst:
+ check.add(p)
+ musts.add(p)
+ if not check:
+ for p in choice:
+ if self.is_installable(p[0], p[1], p[2], musts, never, choices):
+ return True
+ # If we get here, we failed to find something that would satisfy choice (without breaking
+ # the installability of t)
+ return None
+ return False
+ # END _pick_choice
+
+ while choices or check:
+ if not check:
+ rebuild = set()
+ # We have to "guess" now, which is always fun, but not cheap
+ r = _pick_choice(rebuild)
+ if r is None:
+ verdict = False
+ break
+ if r:
+ break
+ choices = rebuild
+
+ if not _check_loop():
+ verdict = False
+ break
+
+ if verdict:
+ # if t is installable, then so are all packages in musts
+ self._cache_inst.update(musts)
+ elif not _n and not _c:
+ # only add it to the broken cache if "never" and "choices" were "clean"
+ # - t may be uninstallable due to conflicts/choices inherited from
+ # reverse dependency.
+ self._cache_broken.add(t)
+
+ return verdict
+
+ def _safe_set_satisifes(self, t):
+ """Check if t's dependencies can be satisfied by the safe set"""
+ universe = self._universe
+ safe_set = self._safe_set
+ if not universe[t][0]:
+ # If it has no dependencies at all, then it is safe. :)
+ return True
+ for depgroup in universe[t][0]:
+ ok = False
+ for dep in depgroup:
+ if dep not in safe_set:
+ continue
+ ok = True
+ break
+ if not ok:
+ return False
+ return True
+
+ def _optimize(self):
+ """Optimize universe, broken and package relations"""
+
+ broken = self._broken
+ universe = self._universe
+ revuniverse = self._revuniverse
+ safe_set = self._safe_set
+ check = set(broken)
+
+ # First, check if we can expand broken.
+ while check:
+ t = check.pop()
+ if t not in broken:
+ # This package is not known to be broken... but it might be now
+ isb = False
+ for depgroup in universe[t][0]:
+ ok = False
+ for dep in depgroup:
+ if dep in universe and dep not in broken:
+ ok = True
+ break
+ if not ok:
+ # A single clause is unsatisfiable, the
+ # package can never be installed - add it to
+ # broken.
+ isb = True
+ break
+
+ if not isb:
+ continue
+
+ broken.add(t)
+
+ if t not in revuniverse:
+ continue
+ for rdep in revuniverse[t][0]:
+ check.add(rdep)
+
+ if len(broken) > 0:
+ # Since a broken package will never be installable, nothing that depends on it
+ # will ever be installable. Thus, there is no point in keeping relations on
+ # the broken package.
+ seen = set()
+ for b in (x for x in broken if x in revuniverse):
+ for rdep in (r for r in revuniverse[b][0] if r not in broken and r not in seen):
+ ndep = frozenset([(x - broken) for x in universe[rdep][0]])
+ universe[rdep] = (ndep, universe[rdep][1] - broken)
+ seen.add(rdep)
+
+ # Now find an initial safe set (if any)
+ check = set()
+ for pkg in universe:
+
+ if pkg in revuniverse and revuniverse[pkg][1]:
+ # Has reverse conflicts - not safe
+ continue
+ if universe[pkg][1]:
+ # has conflicts - not safe
+ continue
+ if not self._safe_set_satisifes(pkg):
+ continue
+ safe_set.add(pkg)
+ if pkg in revuniverse:
+ # add all rdeps (except those already in the safe_set)
+ check.update(revuniverse[pkg][0] - safe_set)
+ # Check if we can expand the initial safe set
+ while check:
+ pkg = check.pop()
+ if pkg in revuniverse and revuniverse[pkg][1]:
+ # Has reverse conflicts - not safe
+ continue
+ if universe[pkg][1]:
+ # has conflicts - not safe
+ continue
+ if self._safe_set_satisifes(pkg):
+ safe_set.add(pkg)
+ if pkg in revuniverse:
+ # add all rdeps (except those already in the safe_set)
+ check.update(revuniverse[pkg][0] - safe_set)
--
1.7.9
Reply to: