path: root/germinate/germinator.py

# -*- coding: utf-8 -*-
"""Expand seeds into dependency-closed lists of packages."""

# Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2011 Canonical Ltd.
#
# Germinate 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, or (at your option) any
# later version.
#
# Germinate 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.
#
# You should have received a copy of the GNU General Public License
# along with Germinate; see the file COPYING.  If not, write to the Free
# Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
# 02110-1301, USA.

from __future__ import print_function

from collections import defaultdict, MutableMapping
import fnmatch
import logging
import re
import sys

import apt_pkg

from germinate.archive import IndexType
from germinate.seeds import AtomicFile, SeedStructure, _ensure_unicode

# TODO: would be much more elegant to reduce our recursion depth!
sys.setrecursionlimit(3000)


__all__ = [
    'Germinator',
]

BUILD_DEPENDS = (
    "Build-Depends",
    "Build-Depends-Indep",
    "Build-Depends-Arch",
)

_logger = logging.getLogger(__name__)


try:
    apt_pkg.parse_src_depends("dummy:any", False)
    _apt_pkg_multiarch = True
except TypeError:
    _apt_pkg_multiarch = False


def _progress(msg, *args, **kwargs):
    _logger.info(msg, *args, extra={'progress': True}, **kwargs)


class SeedReason(object):
    def __init__(self, branch, name):
        self._branch = branch
        self._name = name

    def __str__(self):
        if self._branch is None:
            return '%s seed' % self._name.title()
        else:
            return '%s %s seed' % (self._branch.title(), self._name)


class BuildDependsReason(object):
    def __init__(self, src):
        self._src = src

    def __str__(self):
        return '%s (Build-Depend)' % self._src


class RecommendsReason(object):
    def __init__(self, pkg):
        self._pkg = pkg

    def __str__(self):
        return '%s (Recommends)' % self._pkg


class DependsReason(object):
    def __init__(self, pkg):
        self._pkg = pkg

    def __str__(self):
        return self._pkg


class ExtraReason(object):
    def __init__(self, src):
        self._src = src

    def __str__(self):
        return 'Generated by %s' % self._src


class RescueReason(object):
    def __init__(self, src):
        self._src = src

    def __str__(self):
        return 'Rescued from %s' % self._src


class SeedKernelVersions(object):
    """A virtual seed entry representing lexically scoped Kernel-Version."""

    def __init__(self, kernel_versions):
        self.kernel_versions = set(kernel_versions)


class GerminatedSeed(object):
    def __init__(self, germinator, name, structure, raw_seed):
        self._germinator = germinator
        self._name = name
        self._structure = structure
        self._raw_seed = raw_seed
        self._copy = None
        self._entries = []
        self._features = set()
        self._recommends_entries = []
        self._close_seeds = set()
        self._depends = set()
        self._build_depends = set()
        self._sourcepkgs = set()
        self._build_sourcepkgs = set()
        self._pkgprovides = defaultdict(set)
        self._build = set()
        self._not_build = set()
        self._build_srcs = set()
        self._not_build_srcs = set()
        self._reasons = {}
        self._blacklist = set()
        self._blacklist_seen = False
        # Note that this relates to the vestigial global blacklist file, not
        # to the per-seed blacklist entries in _blacklist.
        self._blacklisted = set()
        self._includes = defaultdict(list)
        self._excludes = defaultdict(list)
        self._seed_reason = SeedReason(structure.branch, name)
        self._grown = False
        self._cache_inner_seeds = None
        self._cache_strictly_outer_seeds = None
        self._cache_outer_seeds = None

    def copy_plant(self, structure):
        """Return a copy of this seed attached to a different structure.

        At this point, we only copy the parts of this seed that were filled
        in by planting; the copy may be aborted if it transpires that it
        needs to be grown independently after all.  The copy may be
        completed after all seeds have been planted by calling copy_grow."""
        new = GerminatedSeed(self._germinator, self._name, structure,
                             self._raw_seed)
        new._copy = self
        # We deliberately don't take copies of anything; deep copies would
        # take up substantial amounts of memory.
        new._entries = self._entries
        new._features = self._features
        new._recommends_entries = self._recommends_entries
        new._close_seeds = self._close_seeds
        new._blacklist = self._blacklist
        new._includes = self._includes
        new._excludes = self._excludes
        new._seed_reason = SeedReason(structure.branch, self._name)

        return new

    def copy_growth(self):
        """Complete copying of this seed."""
        if self._copy is None:
            return
        # Does this seed still look the same as the one it was copied from
        # after we've finished planting it?
        if self != self._copy:
            self._copy = None
            return
        copy = self._copy

        assert copy._grown

        # We deliberately don't take copies of anything; this seed has been
        # grown and thus should not be modified further, and deep copies
        # would take up substantial amounts of memory.
        self._entries = copy._entries
        self._recommends_entries = copy._recommends_entries
        self._depends = copy._depends
        self._build_depends = copy._build_depends
        self._sourcepkgs = copy._sourcepkgs
        self._build_sourcepkgs = copy._build_sourcepkgs
        self._build = copy._build
        self._not_build = copy._not_build
        self._build_srcs = copy._build_srcs
        self._not_build_srcs = copy._not_build_srcs
        self._reasons = copy._reasons
        self._blacklist_seen = False
        self._blacklisted = copy._blacklisted
        self._grown = True

    @property
    def name(self):
        return self._name

    @property
    def structure(self):
        return self._structure

    def __str__(self):
        return self._name

    @property
    def entries(self):
        return [
            e for e in self._entries
            if not isinstance(e, SeedKernelVersions)]

    @property
    def recommends_entries(self):
        return [
            e for e in self._recommends_entries
            if not isinstance(e, SeedKernelVersions)]

    @property
    def depends(self):
        return set(self._depends)

    @property
    def build_depends(self):
        return set(self._build_depends)

    def __eq__(self, other):
        def eq_blacklist_seen(left_name, right_name):
            # Ignore KeyError in the following; if seeds haven't been
            # planted yet, they can't have seen blacklist entries from outer
            # seeds.
            try:
                left_seed = self._germinator._seeds[left_name]
                if left_seed._blacklist_seen:
                    return False
            except KeyError:
                pass
            try:
                right_seed = other._germinator._seeds[right_name]
                if right_seed._blacklist_seen:
                    return False
            except KeyError:
                pass
            return True

        def eq_inheritance(left_name, right_name):
            if left_name == "extra":
                left_inherit = self.structure.names + ["extra"]
            else:
                left_inherit = self.structure.inner_seeds(left_name)
            if right_name == "extra":
                right_inherit = other.structure.names + ["extra"]
            else:
                right_inherit = other.structure.inner_seeds(right_name)
            if len(left_inherit) != len(right_inherit):
                return False
            left_branch = self.structure.branch
            right_branch = other.structure.branch
            for left, right in zip(left_inherit, right_inherit):
                if left != right:
                    return False
                left_seedname = self._germinator._make_seed_name(
                    left_branch, left)
                right_seedname = other._germinator._make_seed_name(
                    right_branch, right)
                if not eq_blacklist_seen(left_seedname, right_seedname):
                    return False
            return True

        if isinstance(other, GerminatedSeed):
            if self._raw_seed != other._raw_seed:
                return False

            if not eq_inheritance(self.name, other.name):
                return False

            try:
                left_lesser = self._germinator._strictly_outer_seeds(self)
                right_lesser = other._germinator._strictly_outer_seeds(other)
                left_close = [l for l in left_lesser
                                if self.name in l._close_seeds]
                right_close = [l for l in right_lesser
                                 if other.name in l._close_seeds]
                if left_close != right_close:
                    return False
                left_branch = self.structure.branch
                right_branch = other.structure.branch
                for close_seed in left_close:
                    left_seedname = self._germinator._make_seed_name(
                        left_branch, close_seed)
                    right_seedname = self._germinator._make_seed_name(
                        right_branch, close_seed)
                    if not eq_inheritance(left_seedname, right_seedname):
                        return False
            except KeyError:
                pass

            return True
        else:
            return NotImplemented

    def __ne__(self, other):
        return not self == other

    __hash__ = None


class GerminatedSeedStructure(object):
    def __init__(self, structure):
        self._structure = structure

        # TODO: move to collections.OrderedDict with 2.7
        self._seednames = []

        self._all = set()
        self._all_srcs = set()
        self._all_reasons = {}

        self._blacklist = {}

        self._rdepends_cache_entries = None


class GerminatorOutput(MutableMapping, object):
    def __init__(self):
        self._dict = {}

    def __iter__(self):
        return iter(self._dict)

    def __len__(self):
        return len(self._dict)

    def __getitem__(self, key):
        if isinstance(key, SeedStructure):
            return self._dict[key.branch]
        else:
            return self._dict[key]

    def __setitem__(self, key, value):
        if isinstance(key, SeedStructure):
            self._dict[key.branch] = value
        else:
            self._dict[key] = value

    def __delitem__(self, key):
        if isinstance(key, SeedStructure):
            del self._dict[key.branch]
        else:
            del self._dict[key]


class Germinator(object):
    """A dependency expander."""

    # Initialisation.
    # ---------------

    def __init__(self, arch):
        """Create a dependency expander.

        Each instance of this class can only process a single architecture,
        but can process multiple seed structures against it.

        """
        self._arch = arch
        apt_pkg.config.set("APT::Architecture", self._arch)

        # Global hints file.
        self._hints = {}

        # Parsed representation of the archive.
        self._packages = {}
        self._packagetype = {}
        self._provides = {}
        self._sources = {}

        # All the seeds we know about, regardless of seed structure.
        self._seeds = {}

        # The current Kernel-Version value for the seed currently being
        # processed.  This just saves us passing a lot of extra method
        # arguments around.
        self._di_kernel_versions = None

        # Results of germination for each seed structure.
        self._output = GerminatorOutput()

        self._always_follow_build_depends = False

    # Parsing.
    # --------

    def parse_hints(self, f):
        """Parse a hints file."""
        for line in f:
            if line.startswith("#") or not len(line.rstrip()):
                continue

            words = line.rstrip().split(None)
            if len(words) != 2:
                continue

            self._hints[words[1]] = words[0]
        f.close()

    def _parse_depends(self, value):
        """Parse Depends from value, without stripping qualifiers."""
        try:
            if _apt_pkg_multiarch:
                return apt_pkg.parse_depends(value, False)
            else:
                return apt_pkg.parse_depends(value)
        except ValueError as e:
            raise ValueError("%s (%s)" % (e, value))

    def _parse_package(self, section, pkgtype):
        """Parse a section from a Packages file."""
        pkg = section["Package"]
        ver = section["Version"]

        # If we have already seen an equal or newer version of this package,
        # then skip this section.
        if pkg in self._packages:
            last_ver = self._packages[pkg]["Version"]
            if apt_pkg.version_compare(last_ver, ver) >= 0:
                return

        self._packages[pkg] = {}
        self._packagetype[pkg] = pkgtype

        self._packages[pkg]["Section"] = \
            section.get("Section", "").split('/')[-1]

        self._packages[pkg]["Version"] = ver

        self._packages[pkg]["Maintainer"] = \
            _ensure_unicode(section.get("Maintainer", ""))

        self._packages[pkg]["Essential"] = section.get("Essential", "")

        for field in "Pre-Depends", "Depends", "Recommends", "Built-Using":
            value = section.get(field, "")
            try:
                self._packages[pkg][field] = self._parse_depends(value)
            except ValueError:
                if field == "Built-Using":
                    _logger.error(
                        "Package %s has invalid Built-Using: %s", pkg, value)
                else:
                    raise

        for field in "Size", "Installed-Size":
            value = section.get(field, "0")
            self._packages[pkg][field] = int(value)

        src = section.get("Source", pkg)
        idx = src.find("(")
        if idx != -1:
            src = src[:idx].strip()
        self._packages[pkg]["Source"] = src

        self._packages[pkg]["Provides"] = apt_pkg.parse_depends(
            section.get("Provides", ""))

        if pkg in self._provides:
            self._provides[pkg].append(pkg)

        self._packages[pkg]["Multi-Arch"] = section.get("Multi-Arch", "none")

        self._packages[pkg]["Kernel-Version"] = section.get(
            "Kernel-Version", "")

    def _strip_restrictions(self, value):
        # Work around lack of https://wiki.debian.org/BuildProfileSpec
        # support in some older series (Ubuntu precise/trusty).  This can be
        # removed once the necessary apt/python-apt changes have been
        # backported everywhere.
        # The manual parsing here is based closely on Dpkg::Deps:
        # Copyright (c) 2007-2009 Raphaël Hertzog <hertzog@debian.org>
        # Copyright (c) 2008-2009,2012-2014 Guillem Jover <guillem@debian.org>
        dep_list = []
        for dep_and in re.split(r"\s*,\s*", value):
            or_list = []
            for dep_or in re.split(r"\s\|\s*", dep_and):
                match = re.match(r"""
                    (
                     \s*                            # skip leading whitespace
                     [a-zA-Z0-9][a-zA-Z0-9+.-]*     # package name
                     (?:
                       :                            # colon for architecture
                       [a-zA-Z0-9][a-zA-Z0-9-]*     # architecture name
                     )?
                     (?:
                       \s* \(                       # start of version part
                       \s* (?:<<|<=|=|>=|>>|[<>])   # relation part
                       \s* .*?                      # don't parse version
                       \s* \)                       # end of version part
                     )?
                     (?:
                       \s* \[                       # start of architectures
                       \s* .*?                      # don't parse architectures
                       \s* \]                       # end of architectures
                     )?
                    )
                    (?:
                      \s* <                         # start of restrictions
                      \s* (.*)                      # don't parse restrictions
                      \s* >                         # end of restrictions
                    )?
                    \s*$                            # skip trailing whitespace
                    """, dep_or, re.X)
                if match is None:
                    raise ValueError("can't parse '%s'" % dep_or)
                restrictions = match.group(2)
                if restrictions is not None:
                    restrictions = [
                        term.split()
                        for term in re.split(r">\s+<", restrictions)]
                    # Since we only care about the case where no build
                    # profiles are enabled, a restriction formula is only
                    # true if it contains at least one AND-list consisting
                    # of only negated terms.
                    # Restriction formulas are in disjunctive normal form:
                    # (foo AND bar) OR (blub AND bla)
                    enabled = False
                    for restrlist in restrictions:
                        if all(r.startswith("!") for r in restrlist):
                            enabled = True
                            break
                    if not enabled:
                        continue
                or_list.append(match.group(1))
            if or_list:
                dep_list.append(" | ".join(or_list))
        return ", ".join(dep_list)

    def _parse_src_depends(self, value):
        """Parse Build-Depends from value, without stripping qualifiers."""
        try:
            if _apt_pkg_multiarch:
                return apt_pkg.parse_src_depends(value, False)
            else:
                return apt_pkg.parse_src_depends(value)
        except ValueError:
            value = self._strip_restrictions(value)
            try:
                if _apt_pkg_multiarch:
                    return apt_pkg.parse_src_depends(value, False)
                else:
                    return apt_pkg.parse_src_depends(value)
            except ValueError as e:
                raise ValueError("%s (%s)" % (e, value))

    def _parse_source(self, section):
        """Parse a section from a Sources file."""
        src = section["Package"]
        ver = section["Version"]

        # If we have already seen an equal or newer version of this source,
        # then skip this section.
        if src in self._sources:
            last_ver = self._sources[src]["Version"]
            if apt_pkg.version_compare(last_ver, ver) >= 0:
                return

        self._sources[src] = {}

        self._sources[src]["Maintainer"] = \
            _ensure_unicode(section.get("Maintainer", ""))
        self._sources[src]["Version"] = ver

        for field in BUILD_DEPENDS:
            value = section.get(field, "")
            self._sources[src][field] = self._parse_src_depends(value)

        binaries = apt_pkg.parse_depends(section.get("Binary", src))
        self._sources[src]["Binaries"] = [b[0][0] for b in binaries]

    def parse_archive(self, archive):
        """Parse an archive.

        This must be called before planting any seeds.

        """
        for indextype, section in archive.sections():
            if indextype == IndexType.PACKAGES:
                self._parse_package(section, "deb")
            elif indextype == IndexType.SOURCES:
                self._parse_source(section)
            elif indextype == IndexType.INSTALLER_PACKAGES:
                self._parse_package(section, "udeb")
            else:
                raise ValueError("Unknown index type %d" % indextype)

        # Construct a more convenient representation of Provides fields.
        for pkg in sorted(self._packages):
            for prov in self._packages[pkg]["Provides"]:
                if prov[0][0] not in self._provides:
                    self._provides[prov[0][0]] = []
                    if prov[0][0] in self._packages:
                        self._provides[prov[0][0]].append(prov[0][0])
                self._provides[prov[0][0]].append(pkg)

    def parse_blacklist(self, structure, f):
        """Parse a blacklist file, used to indicate unwanted packages."""
        output = self._output[structure]
        name = ''

        for line in f:
            line = line.strip()
            if line.startswith('# blacklist: '):
                name = line[13:]
            elif not line or line.startswith('#'):
                continue
            else:
                output._blacklist[line] = name
        f.close()

    # Seed structure handling.  We need to wrap a few methods.
    # --------------------------------------------------------

    def _inner_seeds(self, seed):
        if seed._cache_inner_seeds is None:
            branch = seed.structure.branch
            if seed.name == "extra":
                seed._cache_inner_seeds = [
                    self._seeds[self._make_seed_name(branch, seedname)]
                    for seedname in seed.structure.names + ["extra"]]
            else:
                seed._cache_inner_seeds = [
                    self._seeds[self._make_seed_name(branch, seedname)]
                    for seedname in seed.structure.inner_seeds(seed.name)]
        return seed._cache_inner_seeds

    def _strictly_outer_seeds(self, seed):
        if seed._cache_strictly_outer_seeds is None:
            branch = seed.structure.branch
            ret = []
            for seedname in seed.structure.strictly_outer_seeds(seed.name):
                ret.append(self._seeds[self._make_seed_name(branch, seedname)])
            try:
                ret.append(self._seeds[self._make_seed_name(branch, "extra")])
            except KeyError:
                pass
            seed._cache_strictly_outer_seeds = ret
        return seed._cache_strictly_outer_seeds

    def _outer_seeds(self, seed):
        if seed._cache_outer_seeds is None:
            branch = seed.structure.branch
            ret = []
            for seedname in seed.structure.outer_seeds(seed.name):
                ret.append(self._seeds[self._make_seed_name(branch, seedname)])
            try:
                ret.append(self._seeds[self._make_seed_name(branch, "extra")])
            except KeyError:
                pass
            seed._cache_outer_seeds = ret
        return seed._cache_outer_seeds

    def _supported(self, seed):
        try:
            return self._get_seed(seed.structure, seed.structure.supported)
        except KeyError:
            return None

    # The main germination algorithm.
    # -------------------------------

    def _filter_packages(self, packages, pattern):
        """Filter a list of packages, returning those that match the given
        pattern. The pattern may either be a shell-style glob, or (if
        surrounded by slashes) an extended regular expression."""

        if pattern.startswith('/') and pattern.endswith('/'):
            patternre = re.compile(pattern[1:-1])
            filtered = [p for p in packages if patternre.search(p) is not None]
        elif '*' in pattern or '?' in pattern or '[' in pattern:
            filtered = fnmatch.filter(packages, pattern)
        else:
            # optimisation for common case
            if pattern in packages:
                return [pattern]
            else:
                return []
        return sorted(filtered)

    def _substitute_seed_vars(self, substvars, pkg):
        """Process substitution variables. These look like ${name} (e.g.
        "kernel-image-${Kernel-Version}"). The name is case-insensitive.
        Substitution variables are set with a line that looks like
        " * name: value [value ...]", values being whitespace-separated.

        A package containing substitution variables will be expanded into
        one package for each possible combination of values of those
        variables."""

        pieces = re.split(r'(\${.*?})', pkg)
        substituted = [[]]

        for piece in pieces:
            if piece.startswith("${") and piece.endswith("}"):
                name = piece[2:-1].lower()
                if name in substvars:
                    # Duplicate substituted once for each available substvar
                    # expansion.
                    newsubst = []
                    for value in substvars[name]:
                        for substpieces in substituted:
                            newsubstpieces = list(substpieces)
                            newsubstpieces.append(value)
                            newsubst.append(newsubstpieces)
                    substituted = newsubst
                else:
                    _logger.error("Undefined seed substvar: %s", name)
            else:
                for substpieces in substituted:
                    substpieces.append(piece)

        substpkgs = []
        for substpieces in substituted:
            substpkgs.append("".join(substpieces))
        return substpkgs

    def _already_seeded(self, seed, pkg):
        """Has pkg already been seeded in this seed or in one from
        which we inherit?"""

        for innerseed in self._inner_seeds(seed):
            if (pkg in innerseed._entries or
                pkg in innerseed._recommends_entries):
                return True

        return False

    def _make_seed_name(self, branch, seedname):
        return '%s/%s' % (branch, seedname)

    def _plant_seed(self, structure, seedname, raw_seed):
        """Add a seed."""
        seed = GerminatedSeed(self, seedname, structure, structure[seedname])
        full_seedname = self._make_seed_name(structure.branch, seedname)
        for existing in self._seeds.values():
            if seed == existing:
                _logger.info("Already planted seed %s" % seed)
                self._seeds[full_seedname] = existing.copy_plant(structure)
                self._output[structure]._seednames.append(seedname)
                return
        self._seeds[full_seedname] = seed
        self._output[structure]._seednames.append(seedname)

        seedpkgs = []
        seedrecommends = []
        substvars = {}

        for line in raw_seed:
            if line.lower().startswith('task-seeds:'):
                seed._close_seeds.update(line[11:].strip().split())
                seed._close_seeds.discard(seedname)
                continue

            if not line.startswith(" * "):
                continue

            pkg = line[3:].strip()
            if pkg.find("#") != -1:
                pkg = pkg[:pkg.find("#")]

            colon = pkg.find(":")
            if colon != -1:
                # Special header
                name = pkg[:colon]
                name = name.lower()
                value = pkg[colon + 1:]
                values = value.strip().split()
                if name == "kernel-version":
                    # Allows us to pick the right modules later
                    _logger.warning("Allowing d-i kernel versions: %s", values)
                    # Remember the point in the seed at which we saw this,
                    # so that we can handle it correctly while expanding
                    # dependencies.
                    seedpkgs.append(SeedKernelVersions(values))
                elif name == "feature":
                    _logger.warning("Setting features {%s} for seed %s",
                                    ', '.join(values), seed)
                    seed._features.update(values)
                elif name.endswith("-include"):
                    included_seed = name[:-8]
                    if (included_seed not in structure.names and
                        included_seed != "extra"):
                        _logger.error("Cannot include packages from unknown "
                                      "seed: %s", included_seed)
                    else:
                        _logger.warning("Including packages from %s: %s",
                                        included_seed, values)
                        seed._includes[included_seed].extend(values)
                elif name.endswith("-exclude"):
                    excluded_seed = name[:-8]
                    if (excluded_seed not in structure.names and
                        excluded_seed != "extra"):
                        _logger.error("Cannot exclude packages from unknown "
                                      "seed: %s", excluded_seed)
                    else:
                        _logger.warning("Excluding packages from %s: %s",
                                        excluded_seed, values)
                        seed._excludes[excluded_seed].extend(values)
                substvars[name] = values
                continue

            pkg = pkg.strip()
            if pkg.endswith("]"):
                archspec = []
                startarchspec = pkg.rfind("[")
                if startarchspec != -1:
                    archspec = pkg[startarchspec + 1:-1].split()
                    pkg = pkg[:startarchspec - 1]
                    posarch = [x for x in archspec if not x.startswith('!')]
                    negarch = [x[1:] for x in archspec if x.startswith('!')]
                    if self._arch in negarch:
                        continue
                    if posarch and self._arch not in posarch:
                        continue

            pkg = pkg.split()[0]

            # a leading ! indicates a per-seed blacklist; never include this
            # package in the given seed or any of its inner seeds, no matter
            # what
            if pkg.startswith('!'):
                pkg = pkg[1:]
                is_blacklist = True
            else:
                is_blacklist = False

            # a (pkgname) indicates that this is a recommend
            # and not a depends
            if pkg.startswith('(') and pkg.endswith(')'):
                pkg = pkg[1:-1]
                pkgs = self._filter_packages(self._packages, pkg)
                if not pkgs:
                    pkgs = [pkg]  # virtual or expanded; check again later
                for pkg in pkgs:
                    seedrecommends.extend(self._substitute_seed_vars(
                        substvars, pkg))

            if pkg.startswith('%'):
                pkg = pkg[1:]
                if pkg in self._sources:
                    pkgs = [p for p in self._sources[pkg]["Binaries"]
                              if p in self._packages]
                else:
                    _logger.warning("Unknown source package: %s", pkg)
                    pkgs = []
            else:
                pkgs = self._filter_packages(self._packages, pkg)
                if not pkgs:
                    pkgs = [pkg]  # virtual or expanded; check again later

            if is_blacklist:
                for pkg in pkgs:
                    _logger.info("Blacklisting %s from %s", pkg, seed)
                    seed._blacklist.update(self._substitute_seed_vars(
                        substvars, pkg))
            else:
                for pkg in pkgs:
                    seedpkgs.extend(self._substitute_seed_vars(substvars, pkg))

        di_kernel_versions = None

        for pkg in seedpkgs:
            if isinstance(pkg, SeedKernelVersions):
                di_kernel_versions = pkg
                continue

            if pkg in self._hints and self._hints[pkg] != seed.name:
                _logger.warning("Taking the hint: %s", pkg)
                continue

            if pkg in self._packages:
                # Ordinary package
                if self._already_seeded(seed, pkg):
                    _logger.warning("Duplicated seed: %s", pkg)
                elif self._is_pruned(di_kernel_versions, pkg):
                    _logger.warning("Pruned %s from %s", pkg, seed)
                else:
                    if pkg in seedrecommends:
                        seed._recommends_entries.append(pkg)
                    else:
                        seed._entries.append(pkg)
            elif pkg in self._provides:
                # Virtual package, include everything
                msg = "Virtual %s package: %s" % (seed, pkg)
                for vpkg in self._provides[pkg]:
                    if self._already_seeded(seed, vpkg):
                        pass
                    elif self._is_pruned(di_kernel_versions, vpkg):
                        pass
                    else:
                        msg += "\n  - %s" % vpkg
                        if pkg in seedrecommends:
                            seed._recommends_entries.append(vpkg)
                        else:
                            seed._entries.append(vpkg)
                _logger.info("%s", msg)

            else:
                # No idea
                _logger.error("Unknown %s package: %s", seed, pkg)

        for pkg in self._hints:
            if (self._hints[pkg] == seed.name and
                not self._already_seeded(seed, pkg)):
                if pkg in self._packages:
                    if pkg in seedrecommends:
                        seed._recommends_entries.append(pkg)
                    else:
                        seed._entries.append(pkg)
                else:
                    _logger.error("Unknown hinted package: %s", pkg)

    def plant_seeds(self, structure, seeds=None):
        """Add all seeds found in a seed structure."""
        if structure not in self._output:
            self._output[structure] = GerminatedSeedStructure(structure)

        if seeds is not None:
            structure.limit(seeds)

        for name in structure.names:
            with structure[name] as seed:
                self._plant_seed(structure, name, seed)

    def _is_pruned(self, di_kernel_versions, pkg):
        """Test whether pkg is for a forbidden d-i kernel version."""
        if not di_kernel_versions or not di_kernel_versions.kernel_versions:
            return False
        kernvers = di_kernel_versions.kernel_versions
        kernver = self._packages[pkg]["Kernel-Version"]
        return kernver != "" and kernver not in kernvers

    def _weed_blacklist(self, pkgs, seed, build_tree, why):
        """Weed out blacklisted seed entries from a list."""
        white = []
        if build_tree:
            outerseeds = [self._supported(seed)]
        else:
            outerseeds = self._outer_seeds(seed)
        for pkg in pkgs:
            for outerseed in outerseeds:
                if outerseed is not None and pkg in outerseed._blacklist:
                    _logger.error("Package %s blacklisted in %s but seeded in "
                                  "%s (%s)", pkg, outerseed, seed, why)
                    seed._blacklist_seen = True
                    break
            else:
                white.append(pkg)
        return white

    def grow(self, structure):
        """Grow the seeds."""
        output = self._output[structure]

        for seedname in output._seednames:
            self._di_kernel_versions = None

            seed = self._get_seed(structure, seedname)
            if seed._copy:
                seed.copy_growth()

            if seed._grown:
                _logger.info("Already grown seed %s" % seed)

                # We still need to update a few structure-wide outputs.
                output._all.update(seed._build)
                output._all_srcs.update(seed._build_srcs)
                for pkg, (why, build_tree,
                          recommends) in seed._reasons.items():
                    if isinstance(why, SeedReason):
                        # Adjust this reason to refer to the correct branch.
                        why = seed._seed_reason
                        seed._reasons[pkg] = (why, build_tree, recommends)
                    self._remember_why(output._all_reasons, pkg, why,
                                       build_tree, recommends)

                continue

            _progress("Resolving %s dependencies ...", seed)

            # Check for blacklisted seed entries.
            seed._entries = self._weed_blacklist(
                seed._entries, seed, False, seed._seed_reason)
            seed._recommends_entries = self._weed_blacklist(
                seed._recommends_entries, seed, False, seed._seed_reason)

            # Note that seedrecommends are not processed with
            # recommends=True; that is reserved for Recommends of packages,
            # not packages recommended by the seed. Changing this results in
            # less helpful output when a package is recommended by an inner
            # seed and required by an outer seed.
            # We go through _get_seed_entries/_get_seed_recommends_entries
            # here so that promoted dependencies are filtered out.
            for pkg in self._get_seed_entries(structure, seedname):
                if isinstance(pkg, SeedKernelVersions):
                    self._di_kernel_versions = pkg
                else:
                    self._add_package(seed, pkg, seed._seed_reason)
            for pkg in self._get_seed_recommends_entries(structure, seedname):
                if isinstance(pkg, SeedKernelVersions):
                    self._di_kernel_versions = pkg
                else:
                    self._add_package(seed, pkg, seed._seed_reason)

            self._di_kernel_versions = None

            for rescue_seedname in output._seednames:
                self._rescue_includes(structure, seed.name, rescue_seedname,
                                      build_tree=False)
                if rescue_seedname == seed.name:
                    # only rescue from seeds up to and including the current
                    # seed; later ones have not been grown
                    break
            self._rescue_includes(structure, seed.name, "extra",
                                  build_tree=False)

            seed._grown = True

        try:
            supported = self._get_seed(structure, structure.supported)
        except KeyError:
            supported = None
        if supported is not None:
            self._rescue_includes(structure, supported.name, "extra",
                                  build_tree=True)

    def add_extras(self, structure):
        """Add packages generated by the sources but not in any seed."""
        output = self._output[structure]

        seed = GerminatedSeed(self, "extra", structure, None)
        self._seeds[self._make_seed_name(structure.branch, "extra")] = seed
        output._seednames.append("extra")

        self._di_kernel_versions = None

        _progress("Identifying extras ...")
        found = True
        while found:
            found = False
            sorted_srcs = sorted(output._all_srcs)
            for srcname in sorted_srcs:
                for pkg in self._sources[srcname]["Binaries"]:
                    if pkg not in self._packages:
                        continue
                    if self._packages[pkg]["Source"] != srcname:
                        continue
                    if pkg in output._all:
                        continue

                    if pkg in self._hints and self._hints[pkg] != "extra":
                        _logger.warning("Taking the hint: %s", pkg)
                        continue

                    seed._entries.append(pkg)
                    self._add_package(seed, pkg, ExtraReason(srcname),
                                      second_class=True)
                    found = True

    def _allowed_dependency(self, pkg, depend, seed, build_depend):
        """Test whether a dependency arc is allowed.

        Return True if pkg is allowed to satisfy a (build-)dependency using
        depend within seed.  Note that depend must be a real package.

        If seed is None, check whether the (build-)dependency is allowed
        within any seed.

        """
        if ":" in depend:
            depname, depqual = depend.split(":", 1)
        else:
            depname = depend
            depqual = None
        if depname not in self._packages:
            _logger.warning("_allowed_dependency called with virtual package "
                            "%s", depend)
            return False
        if (seed is not None and
            self._is_pruned(self._di_kernel_versions, depname)):
            return False
        depmultiarch = self._packages[depname]["Multi-Arch"]
        if depqual == "any" and depmultiarch != "allowed":
            return False
        if build_depend:
            if depqual not in (None, "any", "native"):
                return False
            if (depqual == "native" and
                depmultiarch not in ("none", "same", "allowed")):
                return False
            return self._packagetype[depname] == "deb"
        else:
            if depqual not in (None, "any"):
                return False
            if self._packagetype[pkg] == self._packagetype[depname]:
                # If both packages have a Kernel-Version field, they must
                # match.
                pkgkernver = self._packages[pkg]["Kernel-Version"]
                depkernver = self._packages[depname]["Kernel-Version"]
                if (pkgkernver != "" and depkernver != "" and
                    pkgkernver != depkernver):
                    return False
                return True
            else:
                return False

    def _allowed_virtual_dependency(self, pkg, deptype):
        """Test whether a virtual dependency type is allowed.

        Return True if pkg's dependency relationship type deptype may be
        satisfied by a virtual package.  (Versioned dependencies may not be
        satisfied by virtual packages, unless pkg is a udeb.)

        """
        if pkg in self._packagetype and self._packagetype[pkg] == "udeb":
            return True
        else:
            return deptype == ""

    def _check_versioned_dependency(self, depname, depver, deptype):
        """Test whether a versioned dependency can be satisfied."""
        depname = depname.split(":", 1)[0]
        if depname not in self._packages:
            return False
        if deptype == "":
            return True

        ver = self._packages[depname]["Version"]
        compare = apt_pkg.version_compare(ver, depver)
        if deptype == "<=":
            return compare <= 0
        elif deptype == ">=":
            return compare >= 0
        elif deptype == "<":
            return compare < 0
        elif deptype == ">":
            return compare > 0
        elif deptype == "=":
            return compare == 0
        elif deptype == "!=":
            return compare != 0
        else:
            _logger.error("Unknown dependency comparator: %s" % deptype)
            return False

    def _unparse_dependency(self, depname, depver, deptype):
        """Return a string representation of a dependency."""
        if deptype == "":
            return depname
        else:
            return "%s (%s %s)" % (depname, deptype, depver)

    def _follow_recommends(self, structure, seed=None):
        """Test whether we should follow Recommends for this seed."""
        if seed is not None:
            if "follow-recommends" in seed._features:
                return True
            if "no-follow-recommends" in seed._features:
                return False
        return "follow-recommends" in structure.features

    def _follow_build_depends(self, structure, seed=None):
        """
        Test whether we should follow Build-Depends for this seed.
        Defaults to True if not explicitly specified.
        """
        if self._always_follow_build_depends:
            return True
        if seed is not None:
            if "follow-build-depends" in seed._features:
                return True
            if "no-follow-build-depends" in seed._features:
                return False
        return "no-follow-build-depends" not in structure.features

    def _add_reverse(self, pkg, field, rdep):
        """Add a reverse dependency entry."""
        if "Reverse-Depends" not in self._packages[pkg]:
            self._packages[pkg]["Reverse-Depends"] = defaultdict(list)
        self._packages[pkg]["Reverse-Depends"][field].append(rdep)

    def reverse_depends(self, structure):
        """Calculate the reverse dependency relationships."""
        output = self._output[structure]

        for pkg in output._all:
            fields = ["Pre-Depends", "Depends"]
            if (self._follow_recommends(structure) or
                self._packages[pkg]["Section"] == "metapackages"):
                fields.append("Recommends")
            for field in fields:
                for deplist in self._packages[pkg][field]:
                    for dep in deplist:
                        depname = dep[0].split(":", 1)[0]
                        if depname in output._all and \
                           self._allowed_dependency(pkg, dep[0], None, False):
                            self._add_reverse(depname, field, pkg)

        for src in output._all_srcs:
            fields = ()
            if self._follow_build_depends(structure):
                fields = BUILD_DEPENDS
            for field in fields:
                for deplist in self._sources[src][field]:
                    for dep in deplist:
                        depname = dep[0].split(":", 1)[0]
                        if depname in output._all and \
                           self._allowed_dependency(src, dep[0], None, True):
                            self._add_reverse(depname, field, src)

        for pkg in output._all:
            if "Reverse-Depends" not in self._packages[pkg]:
                continue

            fields = ["Pre-Depends", "Depends"]
            if (self._follow_recommends(structure) or
                self._packages[pkg]["Section"] == "metapackages"):
                fields.append("Recommends")
            fields.extend(BUILD_DEPENDS)
            for field in fields:
                if field not in self._packages[pkg]["Reverse-Depends"]:
                    continue

                self._packages[pkg]["Reverse-Depends"][field].sort()

    def _already_satisfied(self, seed, pkg, depend, build_depend=False,
                           with_build=False):
        """Test whether a dependency has already been satisfied."""
        (depname, depver, deptype) = depend
        if (self._allowed_virtual_dependency(pkg, deptype) and
            depname in self._provides):
            trylist = [d for d in self._provides[depname]
                       if d in self._packages and
                          self._allowed_dependency(pkg, d, seed, build_depend)]
        elif (self._check_versioned_dependency(depname, depver, deptype) and
              self._allowed_dependency(pkg, depname, seed, build_depend)):
            trylist = [depname.split(":", 1)[0]]
        else:
            return False

        for trydep in trylist:
            if with_build:
                for innerseed in self._inner_seeds(seed):
                    if trydep in innerseed._build:
                        return True
            else:
                for innerseed in self._inner_seeds(seed):
                    if trydep in innerseed._not_build:
                        return True
            if (trydep in seed._entries or
                trydep in seed._recommends_entries):
                return True
        else:
            return False

    def _add_dependency(self, seed, pkg, dependlist, build_depend,
                        second_class, build_tree, recommends):
        """Add a single dependency.

        Return True if a dependency was added, otherwise False.

        """
        if build_tree and build_depend:
            why = BuildDependsReason(self._packages[pkg]["Source"])
        elif recommends:
            why = RecommendsReason(pkg)
        else:
            why = DependsReason(pkg)

        dependlist = self._weed_blacklist(dependlist, seed, build_tree, why)
        if not dependlist:
            return False

        if build_tree:
            for dep in dependlist:
                seed._build_depends.add(dep)
        else:
            for dep in dependlist:
                seed._depends.add(dep)

        for dep in dependlist:
            self._add_package(seed, dep, why,
                              build_tree, second_class, recommends)

        return True

    def _promote_dependency(self, seed, pkg, depend, close, build_depend,
                            second_class, build_tree, recommends):
        """Try to satisfy a dependency by promoting from a lesser seed.

        If close is True, only "close-by" seeds (ones that generate the same
        task, as defined by Task-Seeds headers) are considered.  Return True
        if a dependency was added, otherwise False.

        """
        (depname, depver, deptype) = depend
        if (self._check_versioned_dependency(depname, depver, deptype) and
            self._allowed_dependency(pkg, depname, seed, build_depend)):
            trylist = [depname.split(":", 1)[0]]
        elif (self._allowed_virtual_dependency(pkg, deptype) and
              depname in self._provides):
            trylist = [d for d in self._provides[depname]
                       if d in self._packages and
                          self._allowed_dependency(pkg, d, seed, build_depend)]
        else:
            return False

        lesserseeds = self._strictly_outer_seeds(seed)
        if close:
            lesserseeds = [l for l in lesserseeds
                             if seed.name in l._close_seeds]
        for trydep in trylist:
            for lesserseed in lesserseeds:
                if (trydep in lesserseed._entries or
                    trydep in lesserseed._recommends_entries):
                    # Has it already been promoted from this seed?
                    already_promoted = False
                    for innerseed in self._inner_seeds(lesserseed):
                        if innerseed.name == lesserseed.name:
                            continue
                        if trydep in innerseed._depends:
                            already_promoted = True
                            break
                    if already_promoted:
                        continue

                    if second_class:
                        # "I'll get you next time, Gadget!"
                        # When processing the build tree, we don't promote
                        # packages from lesser seeds, since we still want to
                        # consider them (e.g.) part of ship even if they're
                        # build-dependencies of desktop. However, we do need
                        # to process them now anyway, since otherwise we
                        # might end up selecting the wrong alternative from
                        # an or-ed build-dependency.
                        pass
                    else:
                        # We want to remove trydep from lesserseed._entries
                        # and lesserseed._recommends_entries, but we can't
                        # because those might need to be copied for another
                        # seed structure; the removal is handled on output
                        # instead.  Even so, it's still useful to log it
                        # here.
                        _logger.warning("Promoted %s from %s to %s to satisfy "
                                        "%s", trydep, lesserseed, seed, pkg)

                    return self._add_dependency(seed, pkg, [trydep],
                                                build_depend, second_class,
                                                build_tree, recommends)

        return False

    def _new_dependency(self, seed, pkg, depend, build_depend,
                        second_class, build_tree, recommends):
        """Try to satisfy a dependency by adding a new package.

        Return True if a dependency was added, otherwise False.

        """
        (depname, depver, deptype) = depend
        if (self._check_versioned_dependency(depname, depver, deptype) and
            self._allowed_dependency(pkg, depname, seed, build_depend)):
            virtual = None
        elif (self._allowed_virtual_dependency(pkg, deptype) and
              depname in self._provides):
            virtual = depname
        else:
            if build_depend:
                desc = "build-dependency"
            elif recommends:
                desc = "recommendation"
            else:
                desc = "dependency"
            _logger.error("Unknown %s %s by %s", desc,
                          self._unparse_dependency(depname, depver, deptype),
                          pkg)
            return False

        dependlist = [depname.split(":", 1)[0]]
        if virtual is not None:
            reallist = [d for d in self._provides[virtual]
                        if d in self._packages and
                           self._allowed_dependency(
                               pkg, d, seed, build_depend)]
            if len(reallist):
                depname = reallist[0]
                # If the depending package isn't a d-i kernel module but the
                # dependency is, then pick all the modules for other allowed
                # kernel versions too.
                if (self._packages[pkg]["Kernel-Version"] == "" and
                    self._packages[depname]["Kernel-Version"] != ""):
                    dependlist = [d for d in reallist
                                  if not self._di_kernel_versions or
                                     (self._packages[d]["Kernel-Version"] in
                                      self._di_kernel_versions)]
                else:
                    dependlist = [depname]
                _logger.info("Chose %s out of %s to satisfy %s",
                             ", ".join(dependlist), virtual, pkg)
            else:
                _logger.error("Nothing to choose out of %s to satisfy %s",
                              virtual, pkg)
                return False

        return self._add_dependency(seed, pkg, dependlist, build_depend,
                                    second_class, build_tree, recommends)

    def _add_dependency_tree(self, seed, pkg, depends,
                             build_depend=False,
                             second_class=False,
                             build_tree=False,
                             recommends=False):
        """Add a package's dependency tree."""
        if build_depend:
            build_tree = True
        if build_tree:
            second_class = True
        for deplist in depends:
            for dep in deplist:
                # TODO cjwatson 2008-07-02: At the moment this check will
                # catch an existing Recommends and we'll never get as far as
                # calling _remember_why with a dependency, so seed._reasons
                # will be a bit inaccurate. We may need another pass for
                # Recommends to fix this.
                if self._already_satisfied(
                    seed, pkg, dep, build_depend, second_class):
                    break
            else:
                firstdep = True
                for dep in deplist:
                    if firstdep:
                        # For the first (preferred) alternative, we may
                        # consider promoting it from any lesser seed.
                        close = False
                        firstdep = False
                    else:
                        # Other alternatives are less favoured, and will
                        # only be promoted from closely-allied seeds.
                        close = True
                    if self._promote_dependency(seed, pkg, dep, close,
                                                build_depend, second_class,
                                                build_tree, recommends):
                        if len(deplist) > 1:
                            _logger.info("Chose %s to satisfy %s", dep[0], pkg)
                        break
                else:
                    for dep in deplist:
                        if self._new_dependency(seed, pkg, dep,
                                                build_depend,
                                                second_class, build_tree,
                                                recommends):
                            if len(deplist) > 1:
                                _logger.info("Chose %s to satisfy %s", dep[0],
                                             pkg)
                            break
                    else:
                        if len(deplist) > 1:
                            _logger.error("Nothing to choose to satisfy %s",
                                          pkg)

    def _remember_why(self, reasons, pkg, why, build_tree=False,
                      recommends=False):
        """Remember why this package was added to the output for this seed."""
        if pkg in reasons:
            old_why, old_build_tree, old_recommends = reasons[pkg]
            # Reasons from the dependency tree beat reasons from the
            # build-dependency tree; but pick the first of either type that
            # we see. Within either tree, dependencies beat recommendations.
            if not old_build_tree and build_tree:
                return
            if old_build_tree == build_tree:
                if not old_recommends or recommends:
                    return

        reasons[pkg] = (why, build_tree, recommends)

    def _add_package(self, seed, pkg, why,
                     second_class=False,
                     build_tree=False,
                     recommends=False):
        """Add a package and its dependency trees."""
        if self._is_pruned(self._di_kernel_versions, pkg):
            _logger.warning("Pruned %s from %s", pkg, seed)
            return
        if build_tree:
            outerseeds = [self._supported(seed)]
        else:
            outerseeds = self._outer_seeds(seed)
        for outerseed in outerseeds:
            if outerseed is not None and pkg in outerseed._blacklist:
                _logger.error("Package %s blacklisted in %s but seeded in %s "
                              "(%s)", pkg, outerseed, seed, why)
                seed._blacklist_seen = True
                return
        if build_tree:
            second_class = True

        output = self._output[seed.structure]

        if pkg not in output._all:
            output._all.add(pkg)

        for innerseed in self._inner_seeds(seed):
            if pkg in innerseed._build:
                break
        else:
            seed._build.add(pkg)

        if not build_tree:
            for innerseed in self._inner_seeds(seed):
                if pkg in innerseed._not_build:
                    break
            else:
                seed._not_build.add(pkg)

        # Remember why the package was added to the output for this seed.
        # Also remember a reason for "all" too, so that an aggregated list
        # of all selected packages can be constructed easily.
        self._remember_why(seed._reasons, pkg, why, build_tree, recommends)
        self._remember_why(output._all_reasons, pkg, why, build_tree,
                           recommends)

        for prov in self._packages[pkg]["Provides"]:
            seed._pkgprovides[prov[0][0]].add(pkg)

        self._add_dependency_tree(seed, pkg,
                                  self._packages[pkg]["Pre-Depends"],
                                  second_class=second_class,
                                  build_tree=build_tree)

        self._add_dependency_tree(seed, pkg,
                                  self._packages[pkg]["Depends"],
                                  second_class=second_class,
                                  build_tree=build_tree)

        if (self._follow_recommends(seed.structure, seed) or
            self._packages[pkg]["Section"] == "metapackages"):
            self._add_dependency_tree(seed, pkg,
                                      self._packages[pkg]["Recommends"],
                                      second_class=second_class,
                                      build_tree=build_tree,
                                      recommends=True)

        src = self._packages[pkg]["Source"]

        # Built-Using field is in a form of apt_pkg.parse_depends For
        # common-case "pkg (= 1)" it returns
        #     [[('pkg', '1', '=')]]
        # We thus unpack the first listed alternative pkg-name, for
        # each built-using source.
        built_using = [i[0][0] for i in self._packages[pkg]["Built-Using"]]
        pkg_srcs = []

        if second_class:
            excluded_srcs = "_build_srcs"
        else:
            excluded_srcs = "_not_build_srcs"

        # Create set of all sources needed for pkg: Source + Built-Using
        for pkg_src in built_using + [src]:
            if pkg_src in self._sources and pkg_src not in pkg_srcs:
                # Consider this source unless it is already part of an inner
                # seed
                for innerseed in self._inner_seeds(seed):
                    if pkg_src in getattr(innerseed, excluded_srcs):
                        break
                else:
                    pkg_srcs.append(pkg_src)
            else:
                _logger.error("Missing source package: %s (for %s)", pkg_src, pkg)

        # Use build_tree flag for src
        # Treat all Built-Using as if it's part of build_tree
        for pkg_src in pkg_srcs:
            if build_tree or pkg_src in built_using:
                seed._build_sourcepkgs.add(pkg_src)
                if pkg_src in output._blacklist:
                    seed._blacklisted.add(pkg_src)
            else:
                seed._not_build_srcs.add(pkg_src)
                seed._sourcepkgs.add(pkg_src)

            output._all_srcs.add(pkg_src)
            seed._build_srcs.add(pkg_src)

            if self._follow_build_depends(seed.structure, seed):
                for build_depends in BUILD_DEPENDS:
                    self._add_dependency_tree(seed, pkg,
                                              self._sources[pkg_src][build_depends],
                                              build_depend=True)


    def _rescue_includes(self, structure, seedname, rescue_seedname,
                         build_tree):
        """Rescue packages matching certain patterns from other seeds."""
        output = self._output[structure]

        try:
            seed = self._get_seed(structure, seedname)
        except KeyError:
            return

        if (rescue_seedname not in structure.names and
            rescue_seedname != "extra"):
            return

        # Find all the source packages.
        rescue_srcs = set()
        if rescue_seedname == "extra":
            rescue_seeds = self._inner_seeds(seed)
        else:
            rescue_seeds = [self._get_seed(structure, rescue_seedname)]
        for one_rescue_seed in rescue_seeds:
            if build_tree:
                rescue_srcs |= one_rescue_seed._build_srcs
            else:
                rescue_srcs |= one_rescue_seed._not_build_srcs

        # For each source, add any binaries that match the include/exclude
        # patterns.
        for src in rescue_srcs:
            rescue = [p for p in self._sources[src]["Binaries"]
                        if p in self._packages]
            included = set()
            if rescue_seedname in seed._includes:
                for include in seed._includes[rescue_seedname]:
                    included |= set(self._filter_packages(rescue, include))
            if rescue_seedname in seed._excludes:
                for exclude in seed._excludes[rescue_seedname]:
                    included -= set(self._filter_packages(rescue, exclude))
            for pkg in included:
                if pkg in output._all:
                    continue
                for lesserseed in self._strictly_outer_seeds(seed):
                    if pkg in lesserseed._entries:
                        seed._entries.remove(pkg)
                        _logger.warning("Promoted %s from %s to %s due to "
                                        "%s-Includes",
                                        pkg, lesserseed, seed,
                                        rescue_seedname.title())
                        break
                _logger.debug("Rescued %s from %s to %s", pkg,
                              rescue_seedname, seed)
                if build_tree:
                    seed._build_depends.add(pkg)
                else:
                    seed._depends.add(pkg)
                self._add_package(seed, pkg, RescueReason(src),
                                  build_tree=build_tree)

    # Accessors.
    # ----------

    def get_source(self, pkg):
        """Return the name of the source package that builds pkg."""
        return self._packages[pkg]["Source"]

    def is_essential(self, pkg):
        """Test whether pkg is Essential."""
        return self._packages[pkg].get("Essential", "no") == "yes"

    def _get_seed(self, structure, seedname):
        """Return the GerminatedSeed for this structure and seed name."""
        full_seedname = self._make_seed_name(structure.branch, seedname)
        return self._seeds[full_seedname]

    def _get_seed_entries(self, structure, seedname):
        """Return the explicitly seeded entries for this seed.

        This includes virtual SeedKernelVersions entries.

        """
        seed = self._get_seed(structure, seedname)
        output = set(seed._entries)
        for innerseed in self._inner_seeds(seed):
            if innerseed.name == seed.name:
                continue
            output -= innerseed._depends
        # Take care to preserve the original ordering.
        # Use a temporary variable to work around a pychecker bug.
        ret = [e for e in seed._entries if e in output]
        return ret

    def get_seed_entries(self, structure, seedname):
        """Return the explicitly seeded entries for this seed."""
        # Use a temporary variable to work around a pychecker bug.
        ret = [
            e for e in self._get_seed_entries(structure, seedname)
            if not isinstance(e, SeedKernelVersions)]
        return ret

    def _get_seed_recommends_entries(self, structure, seedname):
        """Return the explicitly seeded Recommends entries for this seed.

        This includes virtual SeedKernelVersions entries.

        """
        seed = self._get_seed(structure, seedname)
        output = set(seed._recommends_entries)
        for innerseed in self._inner_seeds(seed):
            if innerseed.name == seed.name:
                continue
            output -= innerseed._depends
        # Take care to preserve the original ordering.
        # Use a temporary variable to work around a pychecker bug.
        ret = [e for e in seed._recommends_entries if e in output]
        return ret

    def get_seed_recommends_entries(self, structure, seedname):
        """Return the explicitly seeded Recommends entries for this seed."""
        # Use a temporary variable to work around a pychecker bug.
        ret = [
            e for e in self._get_seed_recommends_entries(structure, seedname)
            if not isinstance(e, SeedKernelVersions)]
        return ret

    def get_depends(self, structure, seedname):
        """Return the dependencies of this seed."""
        return self._get_seed(structure, seedname).depends

    def get_full(self, structure, seedname):
        """Return the full (run-time) dependency expansion of this seed."""
        seed = self._get_seed(structure, seedname)
        return (set(self.get_seed_entries(structure, seedname)) |
                set(self.get_seed_recommends_entries(structure, seedname)) |
                seed._depends)

    def get_build_depends(self, structure, seedname):
        """Return the build-dependencies of this seed."""
        output = set(self._get_seed(structure, seedname)._build_depends)
        for outerseedname in structure.outer_seeds(seedname):
            output -= self.get_full(structure, outerseedname)
        return output

    def get_all(self, structure):
        """Return all the packages in this structure."""
        return list(self._output[structure]._all)

    # Methods for writing output to files.
    # ------------------------------------

    def _write_list(self, reasons, filename, pkgset):
        pkglist = sorted(pkgset)

        pkg_len = len("Package")
        src_len = len("Source")
        why_len = len("Why")
        mnt_len = len("Maintainer")

        for pkg in pkglist:
            _pkg_len = len(pkg)
            if _pkg_len > pkg_len:
                pkg_len = _pkg_len

            _src_len = len(self._packages[pkg]["Source"])
            if _src_len > src_len:
                src_len = _src_len

            why = reasons[pkg][0] if pkg in reasons else ""
            _why_len = len(str(why))
            if _why_len > why_len:
                why_len = _why_len

            _mnt_len = len(self._packages[pkg]["Maintainer"])
            if _mnt_len > mnt_len:
                mnt_len = _mnt_len

        size = 0
        installed_size = 0

        with AtomicFile(filename) as f:
            print("%-*s | %-*s | %-*s | %-*s | %-15s | %-15s" %
                  (pkg_len, "Package",
                   src_len, "Source",
                   why_len, "Why",
                   mnt_len, "Maintainer",
                   "Deb Size (B)",
                   "Inst Size (KB)"), file=f)
            print(("-" * pkg_len) + "-+-" + ("-" * src_len) + "-+-"
                  + ("-" * why_len) + "-+-" + ("-" * mnt_len) + "-+-"
                  + ("-" * 15) + "-+-" + ("-" * 15) + "-", file=f)
            for pkg in pkglist:
                why = reasons[pkg][0] if pkg in reasons else ""
                size += self._packages[pkg]["Size"]
                installed_size += self._packages[pkg]["Installed-Size"]
                print("%-*s | %-*s | %-*s | %-*s | %15d | %15d" %
                      (pkg_len, pkg,
                       src_len, self._packages[pkg]["Source"],
                       why_len, why,
                       mnt_len, self._packages[pkg]["Maintainer"],
                       self._packages[pkg]["Size"],
                       self._packages[pkg]["Installed-Size"]), file=f)
            print(("-" * (pkg_len + src_len + why_len + mnt_len + 9))
                  + "-+-" + ("-" * 15) + "-+-" + ("-" * 15) + "-", file=f)
            print("%*s | %15d | %15d" %
                  ((pkg_len + src_len + why_len + mnt_len + 9), "",
                   size, installed_size), file=f)

    def _write_source_list(self, filename, srcset):
        srclist = sorted(srcset)

        src_len = len("Source")
        mnt_len = len("Maintainer")

        for src in srclist:
            _src_len = len(src)
            if _src_len > src_len:
                src_len = _src_len

            _mnt_len = len(self._sources[src]["Maintainer"])
            if _mnt_len > mnt_len:
                mnt_len = _mnt_len

        with AtomicFile(filename) as f:
            fmt = "%-*s | %-*s"

            print(fmt % (src_len, "Source", mnt_len, "Maintainer"), file=f)
            print(("-" * src_len) + "-+-" + ("-" * mnt_len) + "-", file=f)
            for src in srclist:
                print(fmt % (src_len, src, mnt_len,
                             self._sources[src]["Maintainer"]), file=f)

    def write_full_list(self, structure, filename, seedname):
        """Write the full (run-time) dependency expansion of this seed."""
        seed = self._get_seed(structure, seedname)
        self._write_list(seed._reasons, filename,
                         self.get_full(structure, seedname))

    def write_seed_list(self, structure, filename, seedname):
        """Write the explicitly seeded entries for this seed."""
        seed = self._get_seed(structure, seedname)
        self._write_list(seed._reasons, filename,
                         self.get_seed_entries(structure, seedname))

    def write_seed_recommends_list(self, structure, filename, seedname):
        """Write the explicitly seeded Recommends entries for this seed."""
        seed = self._get_seed(structure, seedname)
        self._write_list(seed._reasons, filename,
                         self.get_seed_recommends_entries(structure, seedname))

    def write_depends_list(self, structure, filename, seedname):
        """Write the dependencies of this seed."""
        seed = self._get_seed(structure, seedname)
        self._write_list(seed._reasons, filename, seed._depends)

    def write_build_depends_list(self, structure, filename, seedname):
        """Write the build-dependencies of this seed."""
        seed = self._get_seed(structure, seedname)
        self._write_list(seed._reasons, filename,
                         self.get_build_depends(structure, seedname))

    def write_sources_list(self, structure, filename, seedname):
        """Write the source packages for this seed and its dependencies."""
        seed = self._get_seed(structure, seedname)
        self._write_source_list(filename, seed._sourcepkgs)

    def write_build_sources_list(self, structure, filename, seedname):
        """Write the source packages for this seed's build-dependencies."""
        seed = self._get_seed(structure, seedname)
        build_sourcepkgs = seed._build_sourcepkgs
        for buildseedname in structure.names:
            buildseed = self._get_seed(structure, buildseedname)
            build_sourcepkgs -= buildseed._sourcepkgs
        self._write_source_list(filename, build_sourcepkgs)

    def write_all_list(self, structure, filename):
        """Write all the packages in this structure."""
        all_bins = set()

        for seedname in structure.names:
            all_bins |= self.get_full(structure, seedname)
            all_bins |= self.get_build_depends(structure, seedname)

        self._write_list(self._output[structure]._all_reasons, filename,
                         all_bins)

    def write_all_source_list(self, structure, filename):
        """Write all the source packages for this structure."""
        all_srcs = set()

        for seedname in structure.names:
            seed = self._get_seed(structure, seedname)

            all_srcs |= seed._sourcepkgs
            all_srcs |= seed._build_sourcepkgs

        self._write_source_list(filename, all_srcs)

    def write_supported_list(self, structure, filename):
        """Write the "supported+build-depends" list."""
        sup_bins = set()

        for seedname in structure.names:
            if seedname == structure.supported:
                sup_bins |= self.get_full(structure, seedname)

            # Only include those build-dependencies that aren't already in
            # the dependency outputs for inner seeds of supported. This
            # allows supported+build-depends to be usable as an "everything
            # else" output.
            build_depends = set(self.get_build_depends(structure, seedname))
            for innerseedname in structure.inner_seeds(structure.supported):
                build_depends -= self.get_full(structure, innerseedname)
            sup_bins |= build_depends

        self._write_list(self._output[structure]._all_reasons, filename,
                         sup_bins)

    def write_supported_source_list(self, structure, filename):
        """Write the "supported+build-depends" sources list."""
        sup_srcs = set()

        for seedname in structure.names:
            seed = self._get_seed(structure, seedname)

            if seedname == structure.supported:
                sup_srcs |= seed._sourcepkgs

            # Only include those build-dependencies that aren't already in
            # the dependency outputs for inner seeds of supported. This
            # allows supported+build-depends to be usable as an "everything
            # else" output.
            build_sourcepkgs = set(seed._build_sourcepkgs)
            for innerseed in self._inner_seeds(self._supported(seed)):
                build_sourcepkgs -= innerseed._sourcepkgs
            sup_srcs |= build_sourcepkgs

        self._write_source_list(filename, sup_srcs)

    def write_all_extra_list(self, structure, filename):
        """Write the "all+extra" list."""
        output = self._output[structure]
        self._write_list(output._all_reasons, filename, output._all)

    def write_all_extra_source_list(self, structure, filename):
        """Write the "all+extra" sources list."""
        output = self._output[structure]
        self._write_source_list(filename, output._all_srcs)

    def write_rdepend_list(self, structure, filename, pkg):
        """Write a detailed analysis of reverse-dependencies."""
        # First, build a cache of entries for each seed.
        output = self._output[structure]
        if output._rdepends_cache_entries is None:
            cache_entries = {}
            for seedname in output._seednames:
                cache_entries[seedname] = self.get_seed_entries(
                    structure, seedname)
            output._rdepends_cache_entries = cache_entries

        # Then write out the list itself.
        with AtomicFile(filename) as f:
            print(pkg, file=f)
            self._write_rdepend_list(structure, f, pkg, "", done=set())

    def _write_rdepend_list(self, structure, f, pkg, prefix, stack=None,
                            done=None):
        if stack is None:
            stack = []
        else:
            stack = list(stack)
            if pkg in stack:
                print(prefix + "! loop", file=f)
                return
        stack.append(pkg)

        if done is None:
            done = set()
        elif pkg in done:
            print(prefix + "! skipped", file=f)
            return
        done.add(pkg)

        output = self._output[structure]
        cache_entries = output._rdepends_cache_entries
        for seedname in output._seednames:
            if pkg in cache_entries[seedname]:
                print(prefix + "*", seedname.title(), "seed", file=f)

        if "Reverse-Depends" not in self._packages[pkg]:
            return

        for field in ("Pre-Depends", "Depends", "Recommends") + BUILD_DEPENDS:
            if field not in self._packages[pkg]["Reverse-Depends"]:
                continue

            i = 0
            print(prefix + "*", "Reverse", field + ":", file=f)
            for dep in self._packages[pkg]["Reverse-Depends"][field]:
                i += 1
                print(prefix + " +- " + dep, file=f)
                if field.startswith("Build-"):
                    continue

                if i == len(self._packages[pkg]["Reverse-Depends"][field]):
                    extra = "    "
                else:
                    extra = " |  "
                self._write_rdepend_list(structure, f, dep, prefix + extra,
                                         stack, done)

    def write_provides_list(self, structure, filename):
        """Write a summary of which packages satisfied Provides."""
        output = self._output[structure]

        with AtomicFile(filename) as f:
            all_pkgprovides = defaultdict(set)
            for seedname in output._seednames:
                seed = self._get_seed(structure, seedname)
                for prov, provset in seed._pkgprovides.items():
                    all_pkgprovides[prov].update(provset)

            for prov in sorted(all_pkgprovides):
                print(prov, file=f)
                for pkg in sorted(all_pkgprovides[prov]):
                    print("\t%s" % (pkg,), file=f)
                print(file=f)

    def write_blacklisted(self, structure, filename):
        """Write the list of blacklisted packages we encountered."""
        output = self._output[structure]

        with AtomicFile(filename) as fh:
            all_blacklisted = set()
            for seedname in output._seednames:
                seed = self._get_seed(structure, seedname)
                all_blacklisted.update(seed._blacklisted)

            for pkg in sorted(all_blacklisted):
                blacklist = output._blacklist[pkg]
                fh.write('%s\t%s\n' % (pkg, blacklist))