Merge lp:~jtv/launchpad/bug-884649-branch-3 into lp:launchpad

[Jeroen T. Vermeulen]

Limit 2nd binary-domination pass to packages with arch-indep publications.

= Summary =

Domination is slow. A major reason is the two-pass domination algorithm needed for binary publications.

== Proposed fix ==

The first binary-domination pass touches only architecture-specific publications. This pass is relatively cheap, per package dominated.

The second pass touches only architecture-independent publications. This pass is expensive per package dominated. It probably dominates the same number of packages as the first pass, but for most, does nothing.

So: keep track during the first pass of which packages have architecture-independent publications, and limit the second pass to just those.

== Pre-implementation notes ==

This was Julian's idea.

== Implementation details ==

I made the second pass iterate over the intersection of “packages with multiple live publications” and “packages that were found during the first pass to have architecture-independent live publications.” This is because a package might conceivably have architecture-independent live publications in one architecture, but no live publications at all in another.

That's not really supposed to happen, which is to say it can be helpful to be prepared for the case but it's not worth optimizing for.

== Tests ==

All the high-level desired outcomes and integration are tested in scenario tests; those remain unchanged because this is a functionally neutral optimization.

I did add one helper function, which is short but easy to mess up and so it gets its own series of tests.

{{{
./bin/test -vvc lp.archivepublisher.tests.test_dominator
}}}

== Demo and Q/A ==

Run the dominator. It should be tons faster, but still dominate even architecture-independent binary publications.

= Launchpad lint =

Checking for conflicts and issues in changed files.

Linting changed files:
  lib/lp/archivepublisher/domination.py
  lib/lp/archivepublisher/tests/test_dominator.py

=== modified file 'lib/lp/archivepublisher/domination.py'
--- lib/lp/archivepublisher/domination.py	2011-11-02 12:58:31 +0000
+++ lib/lp/archivepublisher/domination.py	2011-11-03 11:52:37 +0000
@@ -52,8 +52,12 @@
 
 __all__ = ['Dominator']
 
+from collections import defaultdict
 from datetime import timedelta
-from operator import itemgetter
+from operator import (
+    attrgetter,
+    itemgetter,
+    )
 
 import apt_pkg
 from storm.expr import (
@@ -72,6 +76,7 @@
     DecoratedResultSet,
     )
 from canonical.launchpad.interfaces.lpstorm import IStore
+from canonical.launchpad.utilities.orderingcheck import OrderingCheck
 from lp.registry.model.sourcepackagename import SourcePackageName
 from lp.services.database.bulk import load_related
 from lp.soyuz.enums import (
@@ -192,6 +197,109 @@
         else:
             return version_comparison
 
+    def sortPublications(self, publications):
+        """Sort publications from most to least current versions."""
+        # Listify; we want to iterate this twice, which won't do for a
+        # non-persistent sequence.
+        sorted_publications = list(publications)
+        # Batch-load associated package releases; we'll be needing them
+        # to compare versions.
+        self.load_releases(sorted_publications)
+        # Now sort.  This is that second iteration.  An in-place sort
+        # won't hurt the original, because we're working on a copy of
+        # the original iterable.
+        sorted_publications.sort(cmp=self.compare, reverse=True)
+        return sorted_publications
+
+
+def find_live_source_versions(publications):
+    """Find versions out of Published `publications` that should stay live.
+
+    This particular notion of liveness applies to source domination: the
+    latest version stays live, and that's it.
+
+    :param publications: An iterable of `SourcePackagePublishingHistory`
+        sorted by descending package version.
+    :return: A list of live versions.
+    """
+    # Given the required sort order, the latest version is at the head
+    # of the list.
+    return [publications[0].sourcepackagerelease.version]
+
+
+def get_binary_versions(binary_publications):
+    """List versions for sequence of `BinaryPackagePublishingHistory`."""
+    return [pub.binarypackagerelease.version for pub in binary_publications]
+
+
+def find_live_binary_versions_pass_1(publications):
+    """Find versions out of Published `publications` that should stay live.
+
+    This particular notion of liveness applies to first-pass binary
+    domination: the latest version stays live, and so do publications of
+    binary packages for the "all" architecture.
+
+    :param publications: An iterable of `BinaryPackagePublishingHistory`,
+        sorted by descending package version.
+    :return: A list of live versions.
+    """
+    publications = list(publications)
+    latest = publications.pop(0)
+    return get_binary_versions(
+        [latest] + [
+            pub for pub in publications if not pub.architecture_specific])
+
+
+def find_live_binary_versions_pass_2(publications):
+    """Find versions out of Published `publications` that should stay live.
+
+    This particular notion of liveness applies to second-pass binary
+    domination: the latest version stays live, and architecture-specific
+    publications stay live (i.e, ones that are not for the "all"
+    architecture).
+
+    More importantly, any publication for binary packages of the "all"
+    architecture stay live if any of the non-"all" binary packages from
+    the same source package release are still active -- even if they are
+    for other architectures.
+
+    This is the raison d'etre for the two-pass binary domination algorithm:
+    to let us see which architecture-independent binary publications can be
+    superseded without rendering any architecture-specific binaries from the
+    same source package release uninstallable.
+
+    (Note that here, "active" includes Published publications but also
+    Pending ones.  This is standard nomenclature in Soyuz.  Some of the
+    domination code confuses matters by using the term "active" to mean only
+    Published publications).
+
+    :param publications: An iterable of `BinaryPackagePublishingHistory`,
+        sorted by descending package version.
+    :return: A list of live versions.
+    """
+    publications = list(publications)
+    latest = publications.pop(0)
+    is_arch_specific = attrgetter('architecture_specific')
+    arch_specific_pubs = filter(is_arch_specific, publications)
+    arch_indep_pubs = filter(
+        lambda pub: not is_arch_specific(pub),
+        publications)
+
+    # XXX JeroenVermeulen 2011-11-01 bug=884649: This is likely to be
+    # costly, and the result could be reused for all builds of the same
+    # source package release to all architectures.
+    reprieved_pubs = [
+        pub
+        for pub in arch_indep_pubs
+            if pub.getOtherPublicationsForSameSource().any()]
+
+    return get_binary_versions([latest] + arch_specific_pubs + reprieved_pubs)
+
+
+def contains_arch_indep(bpphs):
+    """Are any of the publications among `bpphs` architecture-independent?"""
+    return any(not bpph.architecture_specific for bpph in bpphs)
+
 
 class Dominator:
     """Manage the process of marking packages as superseded.
@@ -209,27 +317,6 @@
         self.logger = logger
         self.archive = archive
 
-    def _checkArchIndep(self, publication):
-        """Return True if the binary publication can be superseded.
-
-        If the publication is an arch-indep binary, we can only supersede
-        it if all the binaries from the same source are also superseded,
-        else those binaries may become uninstallable.
-        See bug 34086.
-        """
-        binary = publication.binarypackagerelease
-        if not binary.architecturespecific:
-            # getOtherPublicationsForSameSource returns PENDING in
-            # addition to PUBLISHED binaries, and we rely on this since
-            # they must also block domination.
-            others = publication.getOtherPublicationsForSameSource()
-            if others.any():
-                # Don't dominate this arch:all binary as there are
-                # other arch-specific binaries from the same build
-                # that are still active.
-                return False
-        return True
-
     def dominatePackage(self, publications, live_versions, generalization):
         """Dominate publications for a single package.
 
@@ -247,34 +334,33 @@
 
         :param publications: Iterable of publications for the same package,
             in the same archive, series, and pocket, all with status
-            `PackagePublishingStatus.PUBLISHED`.
-        :param live_versions: Iterable of version strings that are still
-            considered live for this package.  The given publications will
-            remain active insofar as they represent any of these versions;
-            older publications will be marked as superseded and newer ones
-            as deleted.
+            `PackagePublishingStatus.PUBLISHED`.  They must be sorted from
+            most current to least current, as would be the result of
+            `generalization.sortPublications`.
+        :param live_versions: Iterable of versions that are still considered
+            "live" for this package.  For any of these, the latest publication
+            among `publications` will remain Published.  Publications for
+            older releases, as well as older publications of live versions,
+            will be marked as Superseded.  Publications of newer versions than
+            are listed in `live_versions` are marked as Deleted.
         :param generalization: A `GeneralizedPublication` helper representing
-            the kind of publications these are--source or binary.
+            the kind of publications these are: source or binary.
         """
-        publications = list(publications)
-        generalization.load_releases(publications)
-
-        # Go through publications from latest version to oldest.  This
-        # makes it easy to figure out which release superseded which:
-        # the dominant is always the oldest live release that is newer
-        # than the one being superseded.  In this loop, that means the
-        # dominant is always the last live publication we saw.
-        publications = sorted(
-            publications, cmp=generalization.compare, reverse=True)
+        live_versions = frozenset(live_versions)
 
         self.logger.debug(
             "Package has %d live publication(s).  Live versions: %s",
             len(publications), live_versions)
 
+        # Verify that the publications are really sorted properly.
+        check_order = OrderingCheck(cmp=generalization.compare, reverse=True)
+
         current_dominant = None
         dominant_version = None
 
         for pub in publications:
+            check_order.check(pub)
+
             version = generalization.getPackageVersion(pub)
             # There should never be two published releases with the same
             # version.  So it doesn't matter whether this comparison is
@@ -295,11 +381,6 @@
                 current_dominant = pub
                 dominant_version = version
                 self.logger.debug2("Keeping version %s.", version)
-            elif not (generalization.is_source or self._checkArchIndep(pub)):
-                # As a special case, we keep this version live as well.
-                current_dominant = pub
-                dominant_version = version
-                self.logger.debug2("Keeping version %s.", version)
             elif current_dominant is None:
                 # This publication is no longer live, but there is no
                 # newer version to supersede it either.  Therefore it
@@ -312,50 +393,32 @@
                 pub.supersede(current_dominant, logger=self.logger)
                 self.logger.debug2("Superseding version %s.", version)
 
-    def _dominatePublications(self, pubs, generalization):
-        """Perform dominations for the given publications.
-
-        Keep the latest published version for each package active,
-        superseding older versions.
-
-        :param pubs: A dict mapping names to a list of publications. Every
-            publication must be PUBLISHED or PENDING, and the first in each
-            list will be treated as dominant (so should be the latest).
-        :param generalization: A `GeneralizedPublication` helper representing
-            the kind of publications these are--source or binary.
-        """
-        self.logger.debug("Dominating packages...")
-        for name, publications in pubs.iteritems():
-            assert publications, "Empty list of publications for %s." % name
-            # Since this always picks the latest version as the live
-            # one, this dominatePackage call will never result in a
-            # deletion.
-            latest_version = generalization.getPackageVersion(publications[0])
-            self.logger.debug2("Dominating %s" % name)
-            self.dominatePackage(
-                publications, [latest_version], generalization)
-
-    def _sortPackages(self, pkglist, generalization):
-        """Map out packages by name, and sort by descending version.
-
-        :param pkglist: An iterable of `SourcePackagePublishingHistory` or
-            `BinaryPackagePublishingHistory`.
-        :param generalization: A `GeneralizedPublication` helper representing
-            the kind of publications these are--source or binary.
-        :return: A dict mapping each package name to a list of publications
-            from `pkglist`, newest first.
-        """
-        self.logger.debug("Sorting packages...")
-
-        outpkgs = {}
-        for inpkg in pkglist:
-            key = generalization.getPackageName(inpkg)
-            outpkgs.setdefault(key, []).append(inpkg)
-
-        for package_pubs in outpkgs.itervalues():
-            package_pubs.sort(cmp=generalization.compare, reverse=True)
-
-        return outpkgs
+    def _sortPackages(self, publications, generalization):
+        """Partition publications by package name, and sort them.
+
+        The publications are sorted from most current to least current,
+        as required by `dominatePackage` etc.
+
+        :param publications: An iterable of `SourcePackagePublishingHistory`
+            or of `BinaryPackagePublishingHistory`.
+        :param generalization: A `GeneralizedPublication` helper representing
+            the kind of publications these are: source or binary.
+        :return: A dict mapping each package name to a sorted list of
+            publications from `publications`.
+        """
+        pubs_by_package = defaultdict(list)
+        for pub in publications:
+            pubs_by_package[generalization.getPackageName(pub)].append(pub)
+
+        # Sort the publication lists.  This is not an in-place sort, so
+        # it involves altering the dict while we iterate it.  Listify
+        # the keys so that we can be sure that we're not altering the
+        # iteration order while iteration is underway.
+        for package in list(pubs_by_package.keys()):
+            pubs_by_package[package] = generalization.sortPublications(
+                pubs_by_package[package])
+
+        return pubs_by_package
 
     def _setScheduledDeletionDate(self, pub_record):
         """Set the scheduleddeletiondate on a publishing record.
@@ -510,6 +573,18 @@
         """
         generalization = GeneralizedPublication(is_source=False)
 
+        # Domination happens in two passes.  The first tries to
+        # supersede architecture-dependent publications; the second
+        # tries to supersede architecture-independent ones.  An
+        # architecture-independent pub is kept alive as long as any
+        # architecture-dependent pubs from the same source package build
+        # are still live for any architecture, because they may depend
+        # on the architecture-independent package.
+        # Thus we limit the second pass to those packages that have
+        # published, architecture-independent publications; anything
+        # else will have completed domination in the first pass.
+        packages_w_arch_indep = set()
+
         for distroarchseries in distroseries.architectures:
             self.logger.info(
                 "Performing domination across %s/%s (%s)",
@@ -520,21 +595,34 @@
             bins = self.findBinariesForDomination(distroarchseries, pocket)
             sorted_packages = self._sortPackages(bins, generalization)
             self.logger.info("Dominating binaries...")
-            self._dominatePublications(sorted_packages, generalization)
-
-        # We need to make a second pass to cover the cases where:
-        #  * arch-specific binaries were not all dominated before arch-all
-        #    ones that depend on them
-        #  * An arch-all turned into an arch-specific, or vice-versa
-        #  * A package is completely schizophrenic and changes all of
-        #    its binaries between arch-all and arch-any (apparently
-        #    occurs sometimes!)
+            for name, pubs in sorted_packages.iteritems():
+                self.logger.debug("Dominating %s" % name)
+                assert len(pubs) > 0, "Dominating zero binaries!"
+                live_versions = find_live_binary_versions_pass_1(pubs)
+                self.dominatePackage(pubs, live_versions, generalization)
+                if contains_arch_indep(pubs):
+                    packages_w_arch_indep.add(name)
+
+        packages_w_arch_indep = frozenset(packages_w_arch_indep)
+
+        # The second pass attempts to supersede arch-all publications of
+        # older versions, from source package releases that no longer
+        # have any active arch-specific publications that might depend
+        # on the arch-indep ones.
+        # (In maintaining this code, bear in mind that some or all of a
+        # source package's binary packages may switch between
+        # arch-specific and arch-indep between releases.)
         for distroarchseries in distroseries.architectures:
             self.logger.info("Finding binaries...(2nd pass)")
             bins = self.findBinariesForDomination(distroarchseries, pocket)
             sorted_packages = self._sortPackages(bins, generalization)
             self.logger.info("Dominating binaries...(2nd pass)")
-            self._dominatePublications(sorted_packages, generalization)
+            for name in packages_w_arch_indep.intersection(sorted_packages):
+                pubs = sorted_packages[name]
+                self.logger.debug("Dominating %s" % name)
+                assert len(pubs) > 0, "Dominating zero binaries in 2nd pass!"
+                live_versions = find_live_binary_versions_pass_2(pubs)
+                self.dominatePackage(pubs, live_versions, generalization)
 
     def _composeActiveSourcePubsCondition(self, distroseries, pocket):
         """Compose ORM condition for restricting relevant source pubs."""
@@ -550,7 +638,12 @@
             )
 
     def findSourcesForDomination(self, distroseries, pocket):
-        """Find binary publications that need dominating."""
+        """Find binary publications that need dominating.
+
+        This is only for traditional domination, where the latest published
+        publication is always kept published.  It will ignore publications
+        that have no other publications competing for the same binary package.
+        """
         # Avoid circular imports.
         from lp.soyuz.model.publishing import SourcePackagePublishingHistory
 
@@ -589,11 +682,18 @@
             distroseries.name, pocket.title)
 
         generalization = GeneralizedPublication(is_source=True)
+
+        self.logger.debug("Finding sources...")
         sources = self.findSourcesForDomination(distroseries, pocket)
+        sorted_packages = self._sortPackages(sources, generalization)
 
         self.logger.debug("Dominating sources...")
-        self._dominatePublications(
-            self._sortPackages(sources, generalization), generalization)
+        for name, pubs in sorted_packages.iteritems():
+            self.logger.debug("Dominating %s" % name)
+            assert len(pubs) > 0, "Dominating zero binaries!"
+            live_versions = find_live_source_versions(pubs)
+            self.dominatePackage(pubs, live_versions, generalization)
+
         flush_database_updates()
 
     def findPublishedSourcePackageNames(self, distroseries, pocket):
@@ -653,6 +753,7 @@
         """
         generalization = GeneralizedPublication(is_source=True)
         pubs = self.findPublishedSPPHs(distroseries, pocket, package_name)
+        pubs = generalization.sortPublications(pubs)
         self.dominatePackage(pubs, live_versions, generalization)
 
     def judge(self, distroseries, pocket):

=== modified file 'lib/lp/archivepublisher/tests/test_dominator.py'
--- lib/lp/archivepublisher/tests/test_dominator.py	2011-11-02 10:28:31 +0000
+++ lib/lp/archivepublisher/tests/test_dominator.py	2011-11-03 11:52:37 +0000
@@ -15,7 +15,11 @@
 from canonical.database.sqlbase import flush_database_updates
 from canonical.testing.layers import ZopelessDatabaseLayer
 from lp.archivepublisher.domination import (
+    contains_arch_indep,
     Dominator,
+    find_live_binary_versions_pass_1,
+    find_live_binary_versions_pass_2,
+    find_live_source_versions,
     GeneralizedPublication,
     STAY_OF_EXECUTION,
     )
@@ -30,6 +34,7 @@
     StormStatementRecorder,
     TestCaseWithFactory,
     )
+from lp.testing.fakemethod import FakeMethod
 from lp.testing.matchers import HasQueryCount
 
 
@@ -72,13 +77,9 @@
             is_source=ISourcePackagePublishingHistory.providedBy(dominant))
         dominator = Dominator(self.logger, self.ubuntutest.main_archive)
 
-        # The _dominate* test methods require a dictionary where the
-        # package name is the key. The key's value is a list of
-        # source or binary packages representing dominant, the first element
-        # and dominated, the subsequents.
-        pubs = {'foo': [dominant, dominated]}
-
-        dominator._dominatePublications(pubs, generalization)
+        pubs = [dominant, dominated]
+        live_versions = [generalization.getPackageVersion(dominant)]
+        dominator.dominatePackage(pubs, live_versions, generalization)
         flush_database_updates()
 
         # The dominant version remains correctly published.
@@ -158,16 +159,30 @@
             [foo_10_source] + foo_10_binaries,
             PackagePublishingStatus.SUPERSEDED)
 
-    def testEmptyDomination(self):
-        """Domination asserts for not empty input list."""
-        dominator = Dominator(self.logger, self.ubuntutest.main_archive)
-        pubs = {'foo': []}
-        # This isn't a really good exception. It should probably be
-        # something more indicative of bad input.
-        self.assertRaises(
-            AssertionError,
-            dominator._dominatePublications,
-            pubs, GeneralizedPublication(True))
+    def test_dominateBinaries_rejects_empty_publication_list(self):
+        """Domination asserts for non-empty input list."""
+        package = self.factory.makeBinaryPackageName()
+        dominator = Dominator(self.logger, self.ubuntutest.main_archive)
+        dominator._sortPackages = FakeMethod({package.name: []})
+        # This isn't a really good exception. It should probably be
+        # something more indicative of bad input.
+        self.assertRaises(
+            AssertionError,
+            dominator.dominateBinaries,
+            self.factory.makeDistroArchSeries().distroseries,
+            self.factory.getAnyPocket())
+
+    def test_dominateSources_rejects_empty_publication_list(self):
+        """Domination asserts for non-empty input list."""
+        package = self.factory.makeSourcePackageName()
+        dominator = Dominator(self.logger, self.ubuntutest.main_archive)
+        dominator._sortPackages = FakeMethod({package.name: []})
+        # This isn't a really good exception. It should probably be
+        # something more indicative of bad input.
+        self.assertRaises(
+            AssertionError,
+            dominator.dominateSources,
+            self.factory.makeDistroSeries(), self.factory.getAnyPocket())
 
     def test_archall_domination(self):
         # Arch-all binaries should not be dominated when a new source
@@ -358,6 +373,16 @@
             SeriesStatus.OBSOLETE)
 
 
+def remove_security_proxies(proxied_objects):
+    """Return list of `proxied_objects`, without their proxies.
+
+    The dominator runs only in scripts, where security proxies don't get
+    in the way.  To test realistically for this environment, strip the
+    proxies wherever necessary and do as you will.
+    """
+    return [removeSecurityProxy(obj) for obj in proxied_objects]
+
+
 def make_spphs_for_versions(factory, versions):
     """Create publication records for each of `versions`.
 
@@ -400,14 +425,15 @@
     archive = das.distroseries.main_archive
     pocket = factory.getAnyPocket()
     bprs = [
-        factory.makeBinaryPackageRelease(binarypackagename=bpn)
+        factory.makeBinaryPackageRelease(
+            binarypackagename=bpn, version=version)
         for version in versions]
-    return [
+    return remove_security_proxies([
         factory.makeBinaryPackagePublishingHistory(
             binarypackagerelease=bpr, binarypackagename=bpn,
             distroarchseries=das, pocket=pocket, archive=archive,
             sourcepackagename=spn, status=PackagePublishingStatus.PUBLISHED)
-        for bpr in bprs]
+        for bpr in bprs])
 
 
 def list_source_versions(spphs):
@@ -591,9 +617,10 @@
     def test_dominatePackage_supersedes_older_pub_with_newer_live_pub(self):
         # When marking a package as superseded, dominatePackage
         # designates a newer live version as the superseding version.
+        generalization = GeneralizedPublication(True)
         pubs = make_spphs_for_versions(self.factory, ['1.0', '1.1'])
         self.makeDominator(pubs).dominatePackage(
-            pubs, ['1.1'], GeneralizedPublication(True))
+            generalization.sortPublications(pubs), ['1.1'], generalization)
         self.assertEqual(PackagePublishingStatus.SUPERSEDED, pubs[0].status)
         self.assertEqual(pubs[1].sourcepackagerelease, pubs[0].supersededby)
         self.assertEqual(PackagePublishingStatus.PUBLISHED, pubs[1].status)
@@ -601,10 +628,11 @@
     def test_dominatePackage_only_supersedes_with_live_pub(self):
         # When marking a package as superseded, dominatePackage will
         # only pick a live version as the superseding one.
+        generalization = GeneralizedPublication(True)
         pubs = make_spphs_for_versions(
             self.factory, ['1.0', '2.0', '3.0', '4.0'])
         self.makeDominator(pubs).dominatePackage(
-            pubs, ['3.0'], GeneralizedPublication(True))
+            generalization.sortPublications(pubs), ['3.0'], generalization)
         self.assertEqual([
                 pubs[2].sourcepackagerelease,
                 pubs[2].sourcepackagerelease,
@@ -616,23 +644,27 @@
     def test_dominatePackage_supersedes_with_oldest_newer_live_pub(self):
         # When marking a package as superseded, dominatePackage picks
         # the oldest of the newer, live versions as the superseding one.
+        generalization = GeneralizedPublication(True)
         pubs = make_spphs_for_versions(self.factory, ['2.7', '2.8', '2.9'])
         self.makeDominator(pubs).dominatePackage(
-            pubs, ['2.8', '2.9'], GeneralizedPublication(True))
+            generalization.sortPublications(pubs), ['2.8', '2.9'],
+            generalization)
         self.assertEqual(pubs[1].sourcepackagerelease, pubs[0].supersededby)
 
     def test_dominatePackage_only_supersedes_with_newer_live_pub(self):
         # When marking a package as superseded, dominatePackage only
         # considers a newer version as the superseding one.
+        generalization = GeneralizedPublication(True)
         pubs = make_spphs_for_versions(self.factory, ['0.1', '0.2'])
         self.makeDominator(pubs).dominatePackage(
-            pubs, ['0.1'], GeneralizedPublication(True))
+            generalization.sortPublications(pubs), ['0.1'], generalization)
         self.assertEqual(None, pubs[1].supersededby)
         self.assertEqual(PackagePublishingStatus.DELETED, pubs[1].status)
 
     def test_dominatePackage_supersedes_replaced_pub_for_live_version(self):
         # Even if a publication record is for a live version, a newer
         # one for the same version supersedes it.
+        generalization = GeneralizedPublication(True)
         spr = self.factory.makeSourcePackageRelease()
         series = self.factory.makeDistroSeries()
         pocket = PackagePublishingPocket.RELEASE
@@ -649,7 +681,8 @@
             ])
 
         self.makeDominator(pubs).dominatePackage(
-            pubs, [spr.version], GeneralizedPublication(True))
+            generalization.sortPublications(pubs), [spr.version],
+            generalization)
         self.assertEqual([
             PackagePublishingStatus.SUPERSEDED,
             PackagePublishingStatus.SUPERSEDED,
@@ -661,12 +694,13 @@
 
     def test_dominatePackage_is_efficient(self):
         # dominatePackage avoids issuing too many queries.
+        generalization = GeneralizedPublication(True)
         versions = ["1.%s" % revision for revision in xrange(5)]
         pubs = make_spphs_for_versions(self.factory, versions)
         with StormStatementRecorder() as recorder:
             self.makeDominator(pubs).dominatePackage(
-                pubs, versions[2:-1],
-                GeneralizedPublication(True))
+                generalization.sortPublications(pubs), versions[2:-1],
+                generalization)
         self.assertThat(recorder, HasQueryCount(LessThan(5)))
 
     def test_dominatePackage_advanced_scenario(self):
@@ -677,6 +711,7 @@
         # don't just patch up the code or this test.  Create unit tests
         # that specifically cover the difference, then change the code
         # and/or adapt this test to return to harmony.
+        generalization = GeneralizedPublication(True)
         series = self.factory.makeDistroSeries()
         package = self.factory.makeSourcePackageName()
         pocket = PackagePublishingPocket.RELEASE
@@ -723,7 +758,8 @@
 
         all_pubs = sum(pubs_by_version.itervalues(), [])
         Dominator(DevNullLogger(), series.main_archive).dominatePackage(
-            all_pubs, live_versions, GeneralizedPublication(True))
+            generalization.sortPublications(all_pubs), live_versions,
+            generalization)
 
         for version in reversed(versions):
             pubs = pubs_by_version[version]
@@ -1089,3 +1125,94 @@
             published_spphs,
             dominator.findSourcesForDomination(
                 spphs[0].distroseries, spphs[0].pocket))
+
+
+def make_publications_arch_specific(pubs, arch_specific=True):
+    """Set the `architecturespecific` attribute for given SPPHs.
+
+    :param pubs: An iterable of `BinaryPackagePublishingHistory`.
+    :param arch_specific: Whether the binary package releases published
+        by `pubs` are to be architecture-specific.  If not, they will be
+        treated as being for the "all" architecture.
+    """
+    for pub in pubs:
+        bpr = removeSecurityProxy(pub).binarypackagerelease
+        bpr.architecturespecific = arch_specific
+
+
+class TestLivenessFunctions(TestCaseWithFactory):
+    """Tests for the functions that say which versions are live."""
+
+    layer = ZopelessDatabaseLayer
+
+    def test_find_live_source_versions_blesses_latest(self):
+        spphs = make_spphs_for_versions(self.factory, ['1.2', '1.1', '1.0'])
+        self.assertEqual(['1.2'], find_live_source_versions(spphs))
+
+    def test_find_live_binary_versions_pass_1_blesses_latest(self):
+        bpphs = make_bpphs_for_versions(self.factory, ['1.2', '1.1', '1.0'])
+        make_publications_arch_specific(bpphs)
+        self.assertEqual(['1.2'], find_live_binary_versions_pass_1(bpphs))
+
+    def test_find_live_binary_versions_pass_1_blesses_arch_all(self):
+        versions = list(reversed(['1.%d' % version for version in range(3)]))
+        bpphs = make_bpphs_for_versions(self.factory, versions)
+
+        # All of these publications are architecture-specific, except
+        # the last one.  This would happen if the binary package had
+        # just changed from being architecture-specific to being
+        # architecture-independent.
+        make_publications_arch_specific(bpphs, True)
+        make_publications_arch_specific(bpphs[-1:], False)
+        self.assertEqual(
+            versions[:1] + versions[-1:],
+            find_live_binary_versions_pass_1(bpphs))
+
+    def test_find_live_binary_versions_pass_2_blesses_latest(self):
+        bpphs = make_bpphs_for_versions(self.factory, ['1.2', '1.1', '1.0'])
+        make_publications_arch_specific(bpphs, False)
+        self.assertEqual(['1.2'], find_live_binary_versions_pass_2(bpphs))
+
+    def test_find_live_binary_versions_pass_2_blesses_arch_specific(self):
+        versions = list(reversed(['1.%d' % version for version in range(3)]))
+        bpphs = make_bpphs_for_versions(self.factory, versions)
+        make_publications_arch_specific(bpphs)
+        self.assertEqual(versions, find_live_binary_versions_pass_2(bpphs))
+
+    def test_find_live_binary_versions_pass_2_reprieves_arch_all(self):
+        # An arch-all BPPH for a BPR built by an SPR that also still has
+        # active arch-dependent BPPHs gets a reprieve: it can't be
+        # superseded until those arch-dependent BPPHs have been
+        # superseded.
+        bpphs = make_bpphs_for_versions(self.factory, ['1.2', '1.1', '1.0'])
+        make_publications_arch_specific(bpphs, False)
+        dependent = self.factory.makeBinaryPackagePublishingHistory(
+            binarypackagerelease=bpphs[1].binarypackagerelease)
+        make_publications_arch_specific([dependent], True)
+        self.assertEqual(
+            ['1.2', '1.1'], find_live_binary_versions_pass_2(bpphs))
+
+
+class TestDominationHelpers(TestCaseWithFactory):
+    """Test lightweight helpers for the `Dominator`."""
+
+    layer = ZopelessDatabaseLayer
+
+    def test_contains_arch_indep_says_True_for_arch_indep(self):
+        bpphs = [self.factory.makeBinaryPackagePublishingHistory()]
+        make_publications_arch_specific(bpphs, False)
+        self.assertTrue(contains_arch_indep(bpphs))
+
+    def test_contains_arch_indep_says_False_for_arch_specific(self):
+        bpphs = [self.factory.makeBinaryPackagePublishingHistory()]
+        make_publications_arch_specific(bpphs, True)
+        self.assertFalse(contains_arch_indep(bpphs))
+
+    def test_contains_arch_indep_says_True_for_combination(self):
+        bpphs = make_bpphs_for_versions(self.factory, ['1.1', '1.0'])
+        make_publications_arch_specific(bpphs[:1], True)
+        make_publications_arch_specific(bpphs[1:], False)
+        self.assertTrue(contains_arch_indep(bpphs))
+
+    def test_contains_arch_indep_says_False_for_empty_list(self):
+        self.assertFalse(contains_arch_indep([]))