source: germinate/trunk/fuentes/.pc/ignore_gpg_check/germinate/germinator.py @ 1926

Last change on this file since 1926 was 1926, checked in by kbut, 5 years ago

add ignore gpg

File size: 79.3 KB
Line 
1# -*- coding: utf-8 -*-
2"""Expand seeds into dependency-closed lists of packages."""
3
4# Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2011 Canonical Ltd.
5#
6# Germinate is free software; you can redistribute it and/or modify it
7# under the terms of the GNU General Public License as published by the
8# Free Software Foundation; either version 2, or (at your option) any
9# later version.
10#
11# Germinate is distributed in the hope that it will be useful, but
12# WITHOUT ANY WARRANTY; without even the implied warranty of
13# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14# General Public License for more details.
15#
16# You should have received a copy of the GNU General Public License
17# along with Germinate; see the file COPYING.  If not, write to the Free
18# Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
19# 02110-1301, USA.
20
21from __future__ import print_function
22
23from collections import defaultdict, MutableMapping
24import fnmatch
25import logging
26import re
27import sys
28
29import apt_pkg
30
31from germinate.archive import IndexType
32from germinate.seeds import AtomicFile, SeedStructure, _ensure_unicode
33
34# TODO: would be much more elegant to reduce our recursion depth!
35sys.setrecursionlimit(3000)
36
37
38__all__ = [
39    'Germinator',
40]
41
42BUILD_DEPENDS = (
43    "Build-Depends",
44    "Build-Depends-Indep",
45    "Build-Depends-Arch",
46)
47
48_logger = logging.getLogger(__name__)
49
50
51try:
52    apt_pkg.parse_src_depends("dummy:any", False)
53    _apt_pkg_multiarch = True
54except TypeError:
55    _apt_pkg_multiarch = False
56
57
58def _progress(msg, *args, **kwargs):
59    _logger.info(msg, *args, extra={'progress': True}, **kwargs)
60
61
62class SeedReason(object):
63    def __init__(self, branch, name):
64        self._branch = branch
65        self._name = name
66
67    def __str__(self):
68        if self._branch is None:
69            return '%s seed' % self._name.title()
70        else:
71            return '%s %s seed' % (self._branch.title(), self._name)
72
73
74class BuildDependsReason(object):
75    def __init__(self, src):
76        self._src = src
77
78    def __str__(self):
79        return '%s (Build-Depend)' % self._src
80
81
82class RecommendsReason(object):
83    def __init__(self, pkg):
84        self._pkg = pkg
85
86    def __str__(self):
87        return '%s (Recommends)' % self._pkg
88
89
90class DependsReason(object):
91    def __init__(self, pkg):
92        self._pkg = pkg
93
94    def __str__(self):
95        return self._pkg
96
97
98class ExtraReason(object):
99    def __init__(self, src):
100        self._src = src
101
102    def __str__(self):
103        return 'Generated by %s' % self._src
104
105
106class RescueReason(object):
107    def __init__(self, src):
108        self._src = src
109
110    def __str__(self):
111        return 'Rescued from %s' % self._src
112
113
114class SeedKernelVersions(object):
115    """A virtual seed entry representing lexically scoped Kernel-Version."""
116
117    def __init__(self, kernel_versions):
118        self.kernel_versions = set(kernel_versions)
119
120
121class GerminatedSeed(object):
122    def __init__(self, germinator, name, structure, raw_seed):
123        self._germinator = germinator
124        self._name = name
125        self._structure = structure
126        self._raw_seed = raw_seed
127        self._copy = None
128        self._entries = []
129        self._features = set()
130        self._recommends_entries = []
131        self._close_seeds = set()
132        self._depends = set()
133        self._build_depends = set()
134        self._sourcepkgs = set()
135        self._build_sourcepkgs = set()
136        self._pkgprovides = defaultdict(set)
137        self._build = set()
138        self._not_build = set()
139        self._build_srcs = set()
140        self._not_build_srcs = set()
141        self._reasons = {}
142        self._blacklist = set()
143        self._blacklist_seen = False
144        # Note that this relates to the vestigial global blacklist file, not
145        # to the per-seed blacklist entries in _blacklist.
146        self._blacklisted = set()
147        self._includes = defaultdict(list)
148        self._excludes = defaultdict(list)
149        self._seed_reason = SeedReason(structure.branch, name)
150        self._grown = False
151        self._cache_inner_seeds = None
152        self._cache_strictly_outer_seeds = None
153        self._cache_outer_seeds = None
154
155    def copy_plant(self, structure):
156        """Return a copy of this seed attached to a different structure.
157
158        At this point, we only copy the parts of this seed that were filled
159        in by planting; the copy may be aborted if it transpires that it
160        needs to be grown independently after all.  The copy may be
161        completed after all seeds have been planted by calling copy_grow."""
162        new = GerminatedSeed(self._germinator, self._name, structure,
163                             self._raw_seed)
164        new._copy = self
165        # We deliberately don't take copies of anything; deep copies would
166        # take up substantial amounts of memory.
167        new._entries = self._entries
168        new._features = self._features
169        new._recommends_entries = self._recommends_entries
170        new._close_seeds = self._close_seeds
171        new._blacklist = self._blacklist
172        new._includes = self._includes
173        new._excludes = self._excludes
174        new._seed_reason = SeedReason(structure.branch, self._name)
175
176        return new
177
178    def copy_growth(self):
179        """Complete copying of this seed."""
180        if self._copy is None:
181            return
182        # Does this seed still look the same as the one it was copied from
183        # after we've finished planting it?
184        if self != self._copy:
185            self._copy = None
186            return
187        copy = self._copy
188
189        assert copy._grown
190
191        # We deliberately don't take copies of anything; this seed has been
192        # grown and thus should not be modified further, and deep copies
193        # would take up substantial amounts of memory.
194        self._entries = copy._entries
195        self._recommends_entries = copy._recommends_entries
196        self._depends = copy._depends
197        self._build_depends = copy._build_depends
198        self._sourcepkgs = copy._sourcepkgs
199        self._build_sourcepkgs = copy._build_sourcepkgs
200        self._build = copy._build
201        self._not_build = copy._not_build
202        self._build_srcs = copy._build_srcs
203        self._not_build_srcs = copy._not_build_srcs
204        self._reasons = copy._reasons
205        self._blacklist_seen = False
206        self._blacklisted = copy._blacklisted
207        self._grown = True
208
209    @property
210    def name(self):
211        return self._name
212
213    @property
214    def structure(self):
215        return self._structure
216
217    def __str__(self):
218        return self._name
219
220    @property
221    def entries(self):
222        return [
223            e for e in self._entries
224            if not isinstance(e, SeedKernelVersions)]
225
226    @property
227    def recommends_entries(self):
228        return [
229            e for e in self._recommends_entries
230            if not isinstance(e, SeedKernelVersions)]
231
232    @property
233    def depends(self):
234        return set(self._depends)
235
236    @property
237    def build_depends(self):
238        return set(self._build_depends)
239
240    def __eq__(self, other):
241        def eq_blacklist_seen(left_name, right_name):
242            # Ignore KeyError in the following; if seeds haven't been
243            # planted yet, they can't have seen blacklist entries from outer
244            # seeds.
245            try:
246                left_seed = self._germinator._seeds[left_name]
247                if left_seed._blacklist_seen:
248                    return False
249            except KeyError:
250                pass
251            try:
252                right_seed = other._germinator._seeds[right_name]
253                if right_seed._blacklist_seen:
254                    return False
255            except KeyError:
256                pass
257            return True
258
259        def eq_inheritance(left_name, right_name):
260            if left_name == "extra":
261                left_inherit = self.structure.names + ["extra"]
262            else:
263                left_inherit = self.structure.inner_seeds(left_name)
264            if right_name == "extra":
265                right_inherit = other.structure.names + ["extra"]
266            else:
267                right_inherit = other.structure.inner_seeds(right_name)
268            if len(left_inherit) != len(right_inherit):
269                return False
270            left_branch = self.structure.branch
271            right_branch = other.structure.branch
272            for left, right in zip(left_inherit, right_inherit):
273                if left != right:
274                    return False
275                left_seedname = self._germinator._make_seed_name(
276                    left_branch, left)
277                right_seedname = other._germinator._make_seed_name(
278                    right_branch, right)
279                if not eq_blacklist_seen(left_seedname, right_seedname):
280                    return False
281            return True
282
283        if isinstance(other, GerminatedSeed):
284            if self._raw_seed != other._raw_seed:
285                return False
286
287            if not eq_inheritance(self.name, other.name):
288                return False
289
290            try:
291                left_lesser = self._germinator._strictly_outer_seeds(self)
292                right_lesser = other._germinator._strictly_outer_seeds(other)
293                left_close = [l for l in left_lesser
294                                if self.name in l._close_seeds]
295                right_close = [l for l in right_lesser
296                                 if other.name in l._close_seeds]
297                if left_close != right_close:
298                    return False
299                left_branch = self.structure.branch
300                right_branch = other.structure.branch
301                for close_seed in left_close:
302                    left_seedname = self._germinator._make_seed_name(
303                        left_branch, close_seed)
304                    right_seedname = self._germinator._make_seed_name(
305                        right_branch, close_seed)
306                    if not eq_inheritance(left_seedname, right_seedname):
307                        return False
308            except KeyError:
309                pass
310
311            return True
312        else:
313            return NotImplemented
314
315    def __ne__(self, other):
316        return not self == other
317
318    __hash__ = None
319
320
321class GerminatedSeedStructure(object):
322    def __init__(self, structure):
323        self._structure = structure
324
325        # TODO: move to collections.OrderedDict with 2.7
326        self._seednames = []
327
328        self._all = set()
329        self._all_srcs = set()
330        self._all_reasons = {}
331
332        self._blacklist = {}
333
334        self._rdepends_cache_entries = None
335
336
337class GerminatorOutput(MutableMapping, object):
338    def __init__(self):
339        self._dict = {}
340
341    def __iter__(self):
342        return iter(self._dict)
343
344    def __len__(self):
345        return len(self._dict)
346
347    def __getitem__(self, key):
348        if isinstance(key, SeedStructure):
349            return self._dict[key.branch]
350        else:
351            return self._dict[key]
352
353    def __setitem__(self, key, value):
354        if isinstance(key, SeedStructure):
355            self._dict[key.branch] = value
356        else:
357            self._dict[key] = value
358
359    def __delitem__(self, key):
360        if isinstance(key, SeedStructure):
361            del self._dict[key.branch]
362        else:
363            del self._dict[key]
364
365
366class Germinator(object):
367    """A dependency expander."""
368
369    # Initialisation.
370    # ---------------
371
372    def __init__(self, arch):
373        """Create a dependency expander.
374
375        Each instance of this class can only process a single architecture,
376        but can process multiple seed structures against it.
377
378        """
379        self._arch = arch
380        apt_pkg.config.set("APT::Architecture", self._arch)
381
382        # Global hints file.
383        self._hints = {}
384
385        # Parsed representation of the archive.
386        self._packages = {}
387        self._packagetype = {}
388        self._provides = {}
389        self._sources = {}
390
391        # All the seeds we know about, regardless of seed structure.
392        self._seeds = {}
393
394        # The current Kernel-Version value for the seed currently being
395        # processed.  This just saves us passing a lot of extra method
396        # arguments around.
397        self._di_kernel_versions = None
398
399        # Results of germination for each seed structure.
400        self._output = GerminatorOutput()
401
402    # Parsing.
403    # --------
404
405    def parse_hints(self, f):
406        """Parse a hints file."""
407        for line in f:
408            if line.startswith("#") or not len(line.rstrip()):
409                continue
410
411            words = line.rstrip().split(None)
412            if len(words) != 2:
413                continue
414
415            self._hints[words[1]] = words[0]
416        f.close()
417
418    def _parse_depends(self, value):
419        """Parse Depends from value, without stripping qualifiers."""
420        try:
421            if _apt_pkg_multiarch:
422                return apt_pkg.parse_depends(value, False)
423            else:
424                return apt_pkg.parse_depends(value)
425        except ValueError as e:
426            raise ValueError("%s (%s)" % (e, value))
427
428    def _parse_package(self, section, pkgtype):
429        """Parse a section from a Packages file."""
430        pkg = section["Package"]
431        ver = section["Version"]
432
433        # If we have already seen an equal or newer version of this package,
434        # then skip this section.
435        if pkg in self._packages:
436            last_ver = self._packages[pkg]["Version"]
437            if apt_pkg.version_compare(last_ver, ver) >= 0:
438                return
439
440        self._packages[pkg] = {}
441        self._packagetype[pkg] = pkgtype
442
443        self._packages[pkg]["Section"] = \
444            section.get("Section", "").split('/')[-1]
445
446        self._packages[pkg]["Version"] = ver
447
448        self._packages[pkg]["Maintainer"] = \
449            _ensure_unicode(section.get("Maintainer", ""))
450
451        self._packages[pkg]["Essential"] = section.get("Essential", "")
452
453        for field in "Pre-Depends", "Depends", "Recommends", "Built-Using":
454            value = section.get(field, "")
455            try:
456                self._packages[pkg][field] = self._parse_depends(value)
457            except ValueError:
458                if field == "Built-Using":
459                    _logger.error(
460                        "Package %s has invalid Built-Using: %s", pkg, value)
461                else:
462                    raise
463
464        for field in "Size", "Installed-Size":
465            value = section.get(field, "0")
466            self._packages[pkg][field] = int(value)
467
468        src = section.get("Source", pkg)
469        idx = src.find("(")
470        if idx != -1:
471            src = src[:idx].strip()
472        self._packages[pkg]["Source"] = src
473
474        self._packages[pkg]["Provides"] = apt_pkg.parse_depends(
475            section.get("Provides", ""))
476
477        if pkg in self._provides:
478            self._provides[pkg].append(pkg)
479
480        self._packages[pkg]["Multi-Arch"] = section.get("Multi-Arch", "none")
481
482        self._packages[pkg]["Kernel-Version"] = section.get(
483            "Kernel-Version", "")
484
485    def _strip_restrictions(self, value):
486        # Work around lack of https://wiki.debian.org/BuildProfileSpec
487        # support in some older series (Ubuntu precise/trusty).  This can be
488        # removed once the necessary apt/python-apt changes have been
489        # backported everywhere.
490        # The manual parsing here is based closely on Dpkg::Deps:
491        # Copyright (c) 2007-2009 Raphaël Hertzog <hertzog@debian.org>
492        # Copyright (c) 2008-2009,2012-2014 Guillem Jover <guillem@debian.org>
493        dep_list = []
494        for dep_and in re.split(r"\s*,\s*", value):
495            or_list = []
496            for dep_or in re.split(r"\s\|\s*", dep_and):
497                match = re.match(r"""
498                    (
499                     \s*                            # skip leading whitespace
500                     [a-zA-Z0-9][a-zA-Z0-9+.-]*     # package name
501                     (?:
502                       :                            # colon for architecture
503                       [a-zA-Z0-9][a-zA-Z0-9-]*     # architecture name
504                     )?
505                     (?:
506                       \s* \(                       # start of version part
507                       \s* (?:<<|<=|=|>=|>>|[<>])   # relation part
508                       \s* .*?                      # don't parse version
509                       \s* \)                       # end of version part
510                     )?
511                     (?:
512                       \s* \[                       # start of architectures
513                       \s* .*?                      # don't parse architectures
514                       \s* \]                       # end of architectures
515                     )?
516                    )
517                    (?:
518                      \s* <                         # start of restrictions
519                      \s* (.*)                      # don't parse restrictions
520                      \s* >                         # end of restrictions
521                    )?
522                    \s*$                            # skip trailing whitespace
523                    """, dep_or, re.X)
524                if match is None:
525                    raise ValueError("can't parse '%s'" % dep_or)
526                restrictions = match.group(2)
527                if restrictions is not None:
528                    restrictions = [
529                        term.split()
530                        for term in re.split(r">\s+<", restrictions)]
531                    # Since we only care about the case where no build
532                    # profiles are enabled, a restriction formula is only
533                    # true if it contains at least one AND-list consisting
534                    # of only negated terms.
535                    # Restriction formulas are in disjunctive normal form:
536                    # (foo AND bar) OR (blub AND bla)
537                    enabled = False
538                    for restrlist in restrictions:
539                        if all(r.startswith("!") for r in restrlist):
540                            enabled = True
541                            break
542                    if not enabled:
543                        continue
544                or_list.append(match.group(1))
545            if or_list:
546                dep_list.append(" | ".join(or_list))
547        return ", ".join(dep_list)
548
549    def _parse_src_depends(self, value):
550        """Parse Build-Depends from value, without stripping qualifiers."""
551        try:
552            if _apt_pkg_multiarch:
553                return apt_pkg.parse_src_depends(value, False)
554            else:
555                return apt_pkg.parse_src_depends(value)
556        except ValueError:
557            value = self._strip_restrictions(value)
558            try:
559                if _apt_pkg_multiarch:
560                    return apt_pkg.parse_src_depends(value, False)
561                else:
562                    return apt_pkg.parse_src_depends(value)
563            except ValueError as e:
564                raise ValueError("%s (%s)" % (e, value))
565
566    def _parse_source(self, section):
567        """Parse a section from a Sources file."""
568        src = section["Package"]
569        ver = section["Version"]
570
571        # If we have already seen an equal or newer version of this source,
572        # then skip this section.
573        if src in self._sources:
574            last_ver = self._sources[src]["Version"]
575            if apt_pkg.version_compare(last_ver, ver) >= 0:
576                return
577
578        self._sources[src] = {}
579
580        self._sources[src]["Maintainer"] = \
581            _ensure_unicode(section.get("Maintainer", ""))
582        self._sources[src]["Version"] = ver
583
584        for field in BUILD_DEPENDS:
585            value = section.get(field, "")
586            self._sources[src][field] = self._parse_src_depends(value)
587
588        binaries = apt_pkg.parse_depends(section.get("Binary", src))
589        self._sources[src]["Binaries"] = [b[0][0] for b in binaries]
590
591    def parse_archive(self, archive):
592        """Parse an archive.
593
594        This must be called before planting any seeds.
595
596        """
597        for indextype, section in archive.sections():
598            if indextype == IndexType.PACKAGES:
599                self._parse_package(section, "deb")
600            elif indextype == IndexType.SOURCES:
601                self._parse_source(section)
602            elif indextype == IndexType.INSTALLER_PACKAGES:
603                self._parse_package(section, "udeb")
604            else:
605                raise ValueError("Unknown index type %d" % indextype)
606
607        # Construct a more convenient representation of Provides fields.
608        for pkg in sorted(self._packages):
609            for prov in self._packages[pkg]["Provides"]:
610                if prov[0][0] not in self._provides:
611                    self._provides[prov[0][0]] = []
612                    if prov[0][0] in self._packages:
613                        self._provides[prov[0][0]].append(prov[0][0])
614                self._provides[prov[0][0]].append(pkg)
615
616    def parse_blacklist(self, structure, f):
617        """Parse a blacklist file, used to indicate unwanted packages."""
618        output = self._output[structure]
619        name = ''
620
621        for line in f:
622            line = line.strip()
623            if line.startswith('# blacklist: '):
624                name = line[13:]
625            elif not line or line.startswith('#'):
626                continue
627            else:
628                output._blacklist[line] = name
629        f.close()
630
631    # Seed structure handling.  We need to wrap a few methods.
632    # --------------------------------------------------------
633
634    def _inner_seeds(self, seed):
635        if seed._cache_inner_seeds is None:
636            branch = seed.structure.branch
637            if seed.name == "extra":
638                seed._cache_inner_seeds = [
639                    self._seeds[self._make_seed_name(branch, seedname)]
640                    for seedname in seed.structure.names + ["extra"]]
641            else:
642                seed._cache_inner_seeds = [
643                    self._seeds[self._make_seed_name(branch, seedname)]
644                    for seedname in seed.structure.inner_seeds(seed.name)]
645        return seed._cache_inner_seeds
646
647    def _strictly_outer_seeds(self, seed):
648        if seed._cache_strictly_outer_seeds is None:
649            branch = seed.structure.branch
650            ret = []
651            for seedname in seed.structure.strictly_outer_seeds(seed.name):
652                ret.append(self._seeds[self._make_seed_name(branch, seedname)])
653            try:
654                ret.append(self._seeds[self._make_seed_name(branch, "extra")])
655            except KeyError:
656                pass
657            seed._cache_strictly_outer_seeds = ret
658        return seed._cache_strictly_outer_seeds
659
660    def _outer_seeds(self, seed):
661        if seed._cache_outer_seeds is None:
662            branch = seed.structure.branch
663            ret = []
664            for seedname in seed.structure.outer_seeds(seed.name):
665                ret.append(self._seeds[self._make_seed_name(branch, seedname)])
666            try:
667                ret.append(self._seeds[self._make_seed_name(branch, "extra")])
668            except KeyError:
669                pass
670            seed._cache_outer_seeds = ret
671        return seed._cache_outer_seeds
672
673    def _supported(self, seed):
674        try:
675            return self._get_seed(seed.structure, seed.structure.supported)
676        except KeyError:
677            return None
678
679    # The main germination algorithm.
680    # -------------------------------
681
682    def _filter_packages(self, packages, pattern):
683        """Filter a list of packages, returning those that match the given
684        pattern. The pattern may either be a shell-style glob, or (if
685        surrounded by slashes) an extended regular expression."""
686
687        if pattern.startswith('/') and pattern.endswith('/'):
688            patternre = re.compile(pattern[1:-1])
689            filtered = [p for p in packages if patternre.search(p) is not None]
690        elif '*' in pattern or '?' in pattern or '[' in pattern:
691            filtered = fnmatch.filter(packages, pattern)
692        else:
693            # optimisation for common case
694            if pattern in packages:
695                return [pattern]
696            else:
697                return []
698        return sorted(filtered)
699
700    def _substitute_seed_vars(self, substvars, pkg):
701        """Process substitution variables. These look like ${name} (e.g.
702        "kernel-image-${Kernel-Version}"). The name is case-insensitive.
703        Substitution variables are set with a line that looks like
704        " * name: value [value ...]", values being whitespace-separated.
705
706        A package containing substitution variables will be expanded into
707        one package for each possible combination of values of those
708        variables."""
709
710        pieces = re.split(r'(\${.*?})', pkg)
711        substituted = [[]]
712
713        for piece in pieces:
714            if piece.startswith("${") and piece.endswith("}"):
715                name = piece[2:-1].lower()
716                if name in substvars:
717                    # Duplicate substituted once for each available substvar
718                    # expansion.
719                    newsubst = []
720                    for value in substvars[name]:
721                        for substpieces in substituted:
722                            newsubstpieces = list(substpieces)
723                            newsubstpieces.append(value)
724                            newsubst.append(newsubstpieces)
725                    substituted = newsubst
726                else:
727                    _logger.error("Undefined seed substvar: %s", name)
728            else:
729                for substpieces in substituted:
730                    substpieces.append(piece)
731
732        substpkgs = []
733        for substpieces in substituted:
734            substpkgs.append("".join(substpieces))
735        return substpkgs
736
737    def _already_seeded(self, seed, pkg):
738        """Has pkg already been seeded in this seed or in one from
739        which we inherit?"""
740
741        for innerseed in self._inner_seeds(seed):
742            if (pkg in innerseed._entries or
743                pkg in innerseed._recommends_entries):
744                return True
745
746        return False
747
748    def _make_seed_name(self, branch, seedname):
749        return '%s/%s' % (branch, seedname)
750
751    def _plant_seed(self, structure, seedname, raw_seed):
752        """Add a seed."""
753        seed = GerminatedSeed(self, seedname, structure, structure[seedname])
754        full_seedname = self._make_seed_name(structure.branch, seedname)
755        for existing in self._seeds.values():
756            if seed == existing:
757                _logger.info("Already planted seed %s" % seed)
758                self._seeds[full_seedname] = existing.copy_plant(structure)
759                self._output[structure]._seednames.append(seedname)
760                return
761        self._seeds[full_seedname] = seed
762        self._output[structure]._seednames.append(seedname)
763
764        seedpkgs = []
765        seedrecommends = []
766        substvars = {}
767
768        for line in raw_seed:
769            if line.lower().startswith('task-seeds:'):
770                seed._close_seeds.update(line[11:].strip().split())
771                seed._close_seeds.discard(seedname)
772                continue
773
774            if not line.startswith(" * "):
775                continue
776
777            pkg = line[3:].strip()
778            if pkg.find("#") != -1:
779                pkg = pkg[:pkg.find("#")]
780
781            colon = pkg.find(":")
782            if colon != -1:
783                # Special header
784                name = pkg[:colon]
785                name = name.lower()
786                value = pkg[colon + 1:]
787                values = value.strip().split()
788                if name == "kernel-version":
789                    # Allows us to pick the right modules later
790                    _logger.warning("Allowing d-i kernel versions: %s", values)
791                    # Remember the point in the seed at which we saw this,
792                    # so that we can handle it correctly while expanding
793                    # dependencies.
794                    seedpkgs.append(SeedKernelVersions(values))
795                elif name == "feature":
796                    _logger.warning("Setting features {%s} for seed %s",
797                                    ', '.join(values), seed)
798                    seed._features.update(values)
799                elif name.endswith("-include"):
800                    included_seed = name[:-8]
801                    if (included_seed not in structure.names and
802                        included_seed != "extra"):
803                        _logger.error("Cannot include packages from unknown "
804                                      "seed: %s", included_seed)
805                    else:
806                        _logger.warning("Including packages from %s: %s",
807                                        included_seed, values)
808                        seed._includes[included_seed].extend(values)
809                elif name.endswith("-exclude"):
810                    excluded_seed = name[:-8]
811                    if (excluded_seed not in structure.names and
812                        excluded_seed != "extra"):
813                        _logger.error("Cannot exclude packages from unknown "
814                                      "seed: %s", excluded_seed)
815                    else:
816                        _logger.warning("Excluding packages from %s: %s",
817                                        excluded_seed, values)
818                        seed._excludes[excluded_seed].extend(values)
819                substvars[name] = values
820                continue
821
822            pkg = pkg.strip()
823            if pkg.endswith("]"):
824                archspec = []
825                startarchspec = pkg.rfind("[")
826                if startarchspec != -1:
827                    archspec = pkg[startarchspec + 1:-1].split()
828                    pkg = pkg[:startarchspec - 1]
829                    posarch = [x for x in archspec if not x.startswith('!')]
830                    negarch = [x[1:] for x in archspec if x.startswith('!')]
831                    if self._arch in negarch:
832                        continue
833                    if posarch and self._arch not in posarch:
834                        continue
835
836            pkg = pkg.split()[0]
837
838            # a leading ! indicates a per-seed blacklist; never include this
839            # package in the given seed or any of its inner seeds, no matter
840            # what
841            if pkg.startswith('!'):
842                pkg = pkg[1:]
843                is_blacklist = True
844            else:
845                is_blacklist = False
846
847            # a (pkgname) indicates that this is a recommend
848            # and not a depends
849            if pkg.startswith('(') and pkg.endswith(')'):
850                pkg = pkg[1:-1]
851                pkgs = self._filter_packages(self._packages, pkg)
852                if not pkgs:
853                    pkgs = [pkg]  # virtual or expanded; check again later
854                for pkg in pkgs:
855                    seedrecommends.extend(self._substitute_seed_vars(
856                        substvars, pkg))
857
858            if pkg.startswith('%'):
859                pkg = pkg[1:]
860                if pkg in self._sources:
861                    pkgs = [p for p in self._sources[pkg]["Binaries"]
862                              if p in self._packages]
863                else:
864                    _logger.warning("Unknown source package: %s", pkg)
865                    pkgs = []
866            else:
867                pkgs = self._filter_packages(self._packages, pkg)
868                if not pkgs:
869                    pkgs = [pkg]  # virtual or expanded; check again later
870
871            if is_blacklist:
872                for pkg in pkgs:
873                    _logger.info("Blacklisting %s from %s", pkg, seed)
874                    seed._blacklist.update(self._substitute_seed_vars(
875                        substvars, pkg))
876            else:
877                for pkg in pkgs:
878                    seedpkgs.extend(self._substitute_seed_vars(substvars, pkg))
879
880        di_kernel_versions = None
881
882        for pkg in seedpkgs:
883            if isinstance(pkg, SeedKernelVersions):
884                di_kernel_versions = pkg
885                continue
886
887            if pkg in self._hints and self._hints[pkg] != seed.name:
888                _logger.warning("Taking the hint: %s", pkg)
889                continue
890
891            if pkg in self._packages:
892                # Ordinary package
893                if self._already_seeded(seed, pkg):
894                    _logger.warning("Duplicated seed: %s", pkg)
895                elif self._is_pruned(di_kernel_versions, pkg):
896                    _logger.warning("Pruned %s from %s", pkg, seed)
897                else:
898                    if pkg in seedrecommends:
899                        seed._recommends_entries.append(pkg)
900                    else:
901                        seed._entries.append(pkg)
902            elif pkg in self._provides:
903                # Virtual package, include everything
904                msg = "Virtual %s package: %s" % (seed, pkg)
905                for vpkg in self._provides[pkg]:
906                    if self._already_seeded(seed, vpkg):
907                        pass
908                    elif self._is_pruned(di_kernel_versions, vpkg):
909                        pass
910                    else:
911                        msg += "\n  - %s" % vpkg
912                        if pkg in seedrecommends:
913                            seed._recommends_entries.append(vpkg)
914                        else:
915                            seed._entries.append(vpkg)
916                _logger.info("%s", msg)
917
918            else:
919                # No idea
920                _logger.error("Unknown %s package: %s", seed, pkg)
921
922        for pkg in self._hints:
923            if (self._hints[pkg] == seed.name and
924                not self._already_seeded(seed, pkg)):
925                if pkg in self._packages:
926                    if pkg in seedrecommends:
927                        seed._recommends_entries.append(pkg)
928                    else:
929                        seed._entries.append(pkg)
930                else:
931                    _logger.error("Unknown hinted package: %s", pkg)
932
933    def plant_seeds(self, structure, seeds=None):
934        """Add all seeds found in a seed structure."""
935        if structure not in self._output:
936            self._output[structure] = GerminatedSeedStructure(structure)
937
938        if seeds is not None:
939            structure.limit(seeds)
940
941        for name in structure.names:
942            with structure[name] as seed:
943                self._plant_seed(structure, name, seed)
944
945    def _is_pruned(self, di_kernel_versions, pkg):
946        """Test whether pkg is for a forbidden d-i kernel version."""
947        if not di_kernel_versions or not di_kernel_versions.kernel_versions:
948            return False
949        kernvers = di_kernel_versions.kernel_versions
950        kernver = self._packages[pkg]["Kernel-Version"]
951        return kernver != "" and kernver not in kernvers
952
953    def _weed_blacklist(self, pkgs, seed, build_tree, why):
954        """Weed out blacklisted seed entries from a list."""
955        white = []
956        if build_tree:
957            outerseeds = [self._supported(seed)]
958        else:
959            outerseeds = self._outer_seeds(seed)
960        for pkg in pkgs:
961            for outerseed in outerseeds:
962                if outerseed is not None and pkg in outerseed._blacklist:
963                    _logger.error("Package %s blacklisted in %s but seeded in "
964                                  "%s (%s)", pkg, outerseed, seed, why)
965                    seed._blacklist_seen = True
966                    break
967            else:
968                white.append(pkg)
969        return white
970
971    def grow(self, structure):
972        """Grow the seeds."""
973        output = self._output[structure]
974
975        for seedname in output._seednames:
976            self._di_kernel_versions = None
977
978            seed = self._get_seed(structure, seedname)
979            if seed._copy:
980                seed.copy_growth()
981
982            if seed._grown:
983                _logger.info("Already grown seed %s" % seed)
984
985                # We still need to update a few structure-wide outputs.
986                output._all.update(seed._build)
987                output._all_srcs.update(seed._build_srcs)
988                for pkg, (why, build_tree,
989                          recommends) in seed._reasons.items():
990                    if isinstance(why, SeedReason):
991                        # Adjust this reason to refer to the correct branch.
992                        why = seed._seed_reason
993                        seed._reasons[pkg] = (why, build_tree, recommends)
994                    self._remember_why(output._all_reasons, pkg, why,
995                                       build_tree, recommends)
996
997                continue
998
999            _progress("Resolving %s dependencies ...", seed)
1000
1001            # Check for blacklisted seed entries.
1002            seed._entries = self._weed_blacklist(
1003                seed._entries, seed, False, seed._seed_reason)
1004            seed._recommends_entries = self._weed_blacklist(
1005                seed._recommends_entries, seed, False, seed._seed_reason)
1006
1007            # Note that seedrecommends are not processed with
1008            # recommends=True; that is reserved for Recommends of packages,
1009            # not packages recommended by the seed. Changing this results in
1010            # less helpful output when a package is recommended by an inner
1011            # seed and required by an outer seed.
1012            # We go through _get_seed_entries/_get_seed_recommends_entries
1013            # here so that promoted dependencies are filtered out.
1014            for pkg in self._get_seed_entries(structure, seedname):
1015                if isinstance(pkg, SeedKernelVersions):
1016                    self._di_kernel_versions = pkg
1017                else:
1018                    self._add_package(seed, pkg, seed._seed_reason)
1019            for pkg in self._get_seed_recommends_entries(structure, seedname):
1020                if isinstance(pkg, SeedKernelVersions):
1021                    self._di_kernel_versions = pkg
1022                else:
1023                    self._add_package(seed, pkg, seed._seed_reason)
1024
1025            self._di_kernel_versions = None
1026
1027            for rescue_seedname in output._seednames:
1028                self._rescue_includes(structure, seed.name, rescue_seedname,
1029                                      build_tree=False)
1030                if rescue_seedname == seed.name:
1031                    # only rescue from seeds up to and including the current
1032                    # seed; later ones have not been grown
1033                    break
1034            self._rescue_includes(structure, seed.name, "extra",
1035                                  build_tree=False)
1036
1037            seed._grown = True
1038
1039        try:
1040            supported = self._get_seed(structure, structure.supported)
1041        except KeyError:
1042            supported = None
1043        if supported is not None:
1044            self._rescue_includes(structure, supported.name, "extra",
1045                                  build_tree=True)
1046
1047    def add_extras(self, structure):
1048        """Add packages generated by the sources but not in any seed."""
1049        output = self._output[structure]
1050
1051        seed = GerminatedSeed(self, "extra", structure, None)
1052        self._seeds[self._make_seed_name(structure.branch, "extra")] = seed
1053        output._seednames.append("extra")
1054
1055        self._di_kernel_versions = None
1056
1057        _progress("Identifying extras ...")
1058        found = True
1059        while found:
1060            found = False
1061            sorted_srcs = sorted(output._all_srcs)
1062            for srcname in sorted_srcs:
1063                for pkg in self._sources[srcname]["Binaries"]:
1064                    if pkg not in self._packages:
1065                        continue
1066                    if self._packages[pkg]["Source"] != srcname:
1067                        continue
1068                    if pkg in output._all:
1069                        continue
1070
1071                    if pkg in self._hints and self._hints[pkg] != "extra":
1072                        _logger.warning("Taking the hint: %s", pkg)
1073                        continue
1074
1075                    seed._entries.append(pkg)
1076                    self._add_package(seed, pkg, ExtraReason(srcname),
1077                                      second_class=True)
1078                    found = True
1079
1080    def _allowed_dependency(self, pkg, depend, seed, build_depend):
1081        """Test whether a dependency arc is allowed.
1082
1083        Return True if pkg is allowed to satisfy a (build-)dependency using
1084        depend within seed.  Note that depend must be a real package.
1085
1086        If seed is None, check whether the (build-)dependency is allowed
1087        within any seed.
1088
1089        """
1090        if ":" in depend:
1091            depname, depqual = depend.split(":", 1)
1092        else:
1093            depname = depend
1094            depqual = None
1095        if depname not in self._packages:
1096            _logger.warning("_allowed_dependency called with virtual package "
1097                            "%s", depend)
1098            return False
1099        if (seed is not None and
1100            self._is_pruned(self._di_kernel_versions, depname)):
1101            return False
1102        depmultiarch = self._packages[depname]["Multi-Arch"]
1103        if depqual == "any" and depmultiarch != "allowed":
1104            return False
1105        if build_depend:
1106            if depqual not in (None, "any", "native"):
1107                return False
1108            if (depqual == "native" and
1109                depmultiarch not in ("none", "same", "allowed")):
1110                return False
1111            return self._packagetype[depname] == "deb"
1112        else:
1113            if depqual not in (None, "any"):
1114                return False
1115            if self._packagetype[pkg] == self._packagetype[depname]:
1116                # If both packages have a Kernel-Version field, they must
1117                # match.
1118                pkgkernver = self._packages[pkg]["Kernel-Version"]
1119                depkernver = self._packages[depname]["Kernel-Version"]
1120                if (pkgkernver != "" and depkernver != "" and
1121                    pkgkernver != depkernver):
1122                    return False
1123                return True
1124            else:
1125                return False
1126
1127    def _allowed_virtual_dependency(self, pkg, deptype):
1128        """Test whether a virtual dependency type is allowed.
1129
1130        Return True if pkg's dependency relationship type deptype may be
1131        satisfied by a virtual package.  (Versioned dependencies may not be
1132        satisfied by virtual packages, unless pkg is a udeb.)
1133
1134        """
1135        if pkg in self._packagetype and self._packagetype[pkg] == "udeb":
1136            return True
1137        else:
1138            return deptype == ""
1139
1140    def _check_versioned_dependency(self, depname, depver, deptype):
1141        """Test whether a versioned dependency can be satisfied."""
1142        depname = depname.split(":", 1)[0]
1143        if depname not in self._packages:
1144            return False
1145        if deptype == "":
1146            return True
1147
1148        ver = self._packages[depname]["Version"]
1149        compare = apt_pkg.version_compare(ver, depver)
1150        if deptype == "<=":
1151            return compare <= 0
1152        elif deptype == ">=":
1153            return compare >= 0
1154        elif deptype == "<":
1155            return compare < 0
1156        elif deptype == ">":
1157            return compare > 0
1158        elif deptype == "=":
1159            return compare == 0
1160        elif deptype == "!=":
1161            return compare != 0
1162        else:
1163            _logger.error("Unknown dependency comparator: %s" % deptype)
1164            return False
1165
1166    def _unparse_dependency(self, depname, depver, deptype):
1167        """Return a string representation of a dependency."""
1168        if deptype == "":
1169            return depname
1170        else:
1171            return "%s (%s %s)" % (depname, deptype, depver)
1172
1173    def _follow_recommends(self, structure, seed=None):
1174        """Test whether we should follow Recommends for this seed."""
1175        if seed is not None:
1176            if "follow-recommends" in seed._features:
1177                return True
1178            if "no-follow-recommends" in seed._features:
1179                return False
1180        return "follow-recommends" in structure.features
1181
1182    def _follow_build_depends(self, structure, seed=None):
1183        """
1184        Test whether we should follow Build-Depends for this seed.
1185        Defaults to True, if not explicitly specified.
1186        """
1187        if seed is not None:
1188            if "follow-build-depends" in seed._features:
1189                return True
1190            if "no-follow-build-depends" in seed._features:
1191                return False
1192        return "no-follow-build-depends" not in structure.features
1193
1194    def _add_reverse(self, pkg, field, rdep):
1195        """Add a reverse dependency entry."""
1196        if "Reverse-Depends" not in self._packages[pkg]:
1197            self._packages[pkg]["Reverse-Depends"] = defaultdict(list)
1198        self._packages[pkg]["Reverse-Depends"][field].append(rdep)
1199
1200    def reverse_depends(self, structure):
1201        """Calculate the reverse dependency relationships."""
1202        output = self._output[structure]
1203
1204        for pkg in output._all:
1205            fields = ["Pre-Depends", "Depends"]
1206            if (self._follow_recommends(structure) or
1207                self._packages[pkg]["Section"] == "metapackages"):
1208                fields.append("Recommends")
1209            for field in fields:
1210                for deplist in self._packages[pkg][field]:
1211                    for dep in deplist:
1212                        depname = dep[0].split(":", 1)[0]
1213                        if depname in output._all and \
1214                           self._allowed_dependency(pkg, dep[0], None, False):
1215                            self._add_reverse(depname, field, pkg)
1216
1217        for src in output._all_srcs:
1218            fields = ()
1219            if self._follow_build_depends(structure):
1220                fields = BUILD_DEPENDS
1221            for field in fields:
1222                for deplist in self._sources[src][field]:
1223                    for dep in deplist:
1224                        depname = dep[0].split(":", 1)[0]
1225                        if depname in output._all and \
1226                           self._allowed_dependency(src, dep[0], None, True):
1227                            self._add_reverse(depname, field, src)
1228
1229        for pkg in output._all:
1230            if "Reverse-Depends" not in self._packages[pkg]:
1231                continue
1232
1233            fields = ["Pre-Depends", "Depends"]
1234            if (self._follow_recommends(structure) or
1235                self._packages[pkg]["Section"] == "metapackages"):
1236                fields.append("Recommends")
1237            fields.extend(BUILD_DEPENDS)
1238            for field in fields:
1239                if field not in self._packages[pkg]["Reverse-Depends"]:
1240                    continue
1241
1242                self._packages[pkg]["Reverse-Depends"][field].sort()
1243
1244    def _already_satisfied(self, seed, pkg, depend, build_depend=False,
1245                           with_build=False):
1246        """Test whether a dependency has already been satisfied."""
1247        (depname, depver, deptype) = depend
1248        if (self._allowed_virtual_dependency(pkg, deptype) and
1249            depname in self._provides):
1250            trylist = [d for d in self._provides[depname]
1251                       if d in self._packages and
1252                          self._allowed_dependency(pkg, d, seed, build_depend)]
1253        elif (self._check_versioned_dependency(depname, depver, deptype) and
1254              self._allowed_dependency(pkg, depname, seed, build_depend)):
1255            trylist = [depname.split(":", 1)[0]]
1256        else:
1257            return False
1258
1259        for trydep in trylist:
1260            if with_build:
1261                for innerseed in self._inner_seeds(seed):
1262                    if trydep in innerseed._build:
1263                        return True
1264            else:
1265                for innerseed in self._inner_seeds(seed):
1266                    if trydep in innerseed._not_build:
1267                        return True
1268            if (trydep in seed._entries or
1269                trydep in seed._recommends_entries):
1270                return True
1271        else:
1272            return False
1273
1274    def _add_dependency(self, seed, pkg, dependlist, build_depend,
1275                        second_class, build_tree, recommends):
1276        """Add a single dependency.
1277
1278        Return True if a dependency was added, otherwise False.
1279
1280        """
1281        if build_tree and build_depend:
1282            why = BuildDependsReason(self._packages[pkg]["Source"])
1283        elif recommends:
1284            why = RecommendsReason(pkg)
1285        else:
1286            why = DependsReason(pkg)
1287
1288        dependlist = self._weed_blacklist(dependlist, seed, build_tree, why)
1289        if not dependlist:
1290            return False
1291
1292        if build_tree:
1293            for dep in dependlist:
1294                seed._build_depends.add(dep)
1295        else:
1296            for dep in dependlist:
1297                seed._depends.add(dep)
1298
1299        for dep in dependlist:
1300            self._add_package(seed, dep, why,
1301                              build_tree, second_class, recommends)
1302
1303        return True
1304
1305    def _promote_dependency(self, seed, pkg, depend, close, build_depend,
1306                            second_class, build_tree, recommends):
1307        """Try to satisfy a dependency by promoting from a lesser seed.
1308
1309        If close is True, only "close-by" seeds (ones that generate the same
1310        task, as defined by Task-Seeds headers) are considered.  Return True
1311        if a dependency was added, otherwise False.
1312
1313        """
1314        (depname, depver, deptype) = depend
1315        if (self._check_versioned_dependency(depname, depver, deptype) and
1316            self._allowed_dependency(pkg, depname, seed, build_depend)):
1317            trylist = [depname.split(":", 1)[0]]
1318        elif (self._allowed_virtual_dependency(pkg, deptype) and
1319              depname in self._provides):
1320            trylist = [d for d in self._provides[depname]
1321                       if d in self._packages and
1322                          self._allowed_dependency(pkg, d, seed, build_depend)]
1323        else:
1324            return False
1325
1326        lesserseeds = self._strictly_outer_seeds(seed)
1327        if close:
1328            lesserseeds = [l for l in lesserseeds
1329                             if seed.name in l._close_seeds]
1330        for trydep in trylist:
1331            for lesserseed in lesserseeds:
1332                if (trydep in lesserseed._entries or
1333                    trydep in lesserseed._recommends_entries):
1334                    # Has it already been promoted from this seed?
1335                    already_promoted = False
1336                    for innerseed in self._inner_seeds(lesserseed):
1337                        if innerseed.name == lesserseed.name:
1338                            continue
1339                        if trydep in innerseed._depends:
1340                            already_promoted = True
1341                            break
1342                    if already_promoted:
1343                        continue
1344
1345                    if second_class:
1346                        # "I'll get you next time, Gadget!"
1347                        # When processing the build tree, we don't promote
1348                        # packages from lesser seeds, since we still want to
1349                        # consider them (e.g.) part of ship even if they're
1350                        # build-dependencies of desktop. However, we do need
1351                        # to process them now anyway, since otherwise we
1352                        # might end up selecting the wrong alternative from
1353                        # an or-ed build-dependency.
1354                        pass
1355                    else:
1356                        # We want to remove trydep from lesserseed._entries
1357                        # and lesserseed._recommends_entries, but we can't
1358                        # because those might need to be copied for another
1359                        # seed structure; the removal is handled on output
1360                        # instead.  Even so, it's still useful to log it
1361                        # here.
1362                        _logger.warning("Promoted %s from %s to %s to satisfy "
1363                                        "%s", trydep, lesserseed, seed, pkg)
1364
1365                    return self._add_dependency(seed, pkg, [trydep],
1366                                                build_depend, second_class,
1367                                                build_tree, recommends)
1368
1369        return False
1370
1371    def _new_dependency(self, seed, pkg, depend, build_depend,
1372                        second_class, build_tree, recommends):
1373        """Try to satisfy a dependency by adding a new package.
1374
1375        Return True if a dependency was added, otherwise False.
1376
1377        """
1378        (depname, depver, deptype) = depend
1379        if (self._check_versioned_dependency(depname, depver, deptype) and
1380            self._allowed_dependency(pkg, depname, seed, build_depend)):
1381            virtual = None
1382        elif (self._allowed_virtual_dependency(pkg, deptype) and
1383              depname in self._provides):
1384            virtual = depname
1385        else:
1386            if build_depend:
1387                desc = "build-dependency"
1388            elif recommends:
1389                desc = "recommendation"
1390            else:
1391                desc = "dependency"
1392            _logger.error("Unknown %s %s by %s", desc,
1393                          self._unparse_dependency(depname, depver, deptype),
1394                          pkg)
1395            return False
1396
1397        dependlist = [depname.split(":", 1)[0]]
1398        if virtual is not None:
1399            reallist = [d for d in self._provides[virtual]
1400                        if d in self._packages and
1401                           self._allowed_dependency(
1402                               pkg, d, seed, build_depend)]
1403            if len(reallist):
1404                depname = reallist[0]
1405                # If the depending package isn't a d-i kernel module but the
1406                # dependency is, then pick all the modules for other allowed
1407                # kernel versions too.
1408                if (self._packages[pkg]["Kernel-Version"] == "" and
1409                    self._packages[depname]["Kernel-Version"] != ""):
1410                    dependlist = [d for d in reallist
1411                                  if not self._di_kernel_versions or
1412                                     (self._packages[d]["Kernel-Version"] in
1413                                      self._di_kernel_versions)]
1414                else:
1415                    dependlist = [depname]
1416                _logger.info("Chose %s out of %s to satisfy %s",
1417                             ", ".join(dependlist), virtual, pkg)
1418            else:
1419                _logger.error("Nothing to choose out of %s to satisfy %s",
1420                              virtual, pkg)
1421                return False
1422
1423        return self._add_dependency(seed, pkg, dependlist, build_depend,
1424                                    second_class, build_tree, recommends)
1425
1426    def _add_dependency_tree(self, seed, pkg, depends,
1427                             build_depend=False,
1428                             second_class=False,
1429                             build_tree=False,
1430                             recommends=False):
1431        """Add a package's dependency tree."""
1432        if build_depend:
1433            build_tree = True
1434        if build_tree:
1435            second_class = True
1436        for deplist in depends:
1437            for dep in deplist:
1438                # TODO cjwatson 2008-07-02: At the moment this check will
1439                # catch an existing Recommends and we'll never get as far as
1440                # calling _remember_why with a dependency, so seed._reasons
1441                # will be a bit inaccurate. We may need another pass for
1442                # Recommends to fix this.
1443                if self._already_satisfied(
1444                    seed, pkg, dep, build_depend, second_class):
1445                    break
1446            else:
1447                firstdep = True
1448                for dep in deplist:
1449                    if firstdep:
1450                        # For the first (preferred) alternative, we may
1451                        # consider promoting it from any lesser seed.
1452                        close = False
1453                        firstdep = False
1454                    else:
1455                        # Other alternatives are less favoured, and will
1456                        # only be promoted from closely-allied seeds.
1457                        close = True
1458                    if self._promote_dependency(seed, pkg, dep, close,
1459                                                build_depend, second_class,
1460                                                build_tree, recommends):
1461                        if len(deplist) > 1:
1462                            _logger.info("Chose %s to satisfy %s", dep[0], pkg)
1463                        break
1464                else:
1465                    for dep in deplist:
1466                        if self._new_dependency(seed, pkg, dep,
1467                                                build_depend,
1468                                                second_class, build_tree,
1469                                                recommends):
1470                            if len(deplist) > 1:
1471                                _logger.info("Chose %s to satisfy %s", dep[0],
1472                                             pkg)
1473                            break
1474                    else:
1475                        if len(deplist) > 1:
1476                            _logger.error("Nothing to choose to satisfy %s",
1477                                          pkg)
1478
1479    def _remember_why(self, reasons, pkg, why, build_tree=False,
1480                      recommends=False):
1481        """Remember why this package was added to the output for this seed."""
1482        if pkg in reasons:
1483            old_why, old_build_tree, old_recommends = reasons[pkg]
1484            # Reasons from the dependency tree beat reasons from the
1485            # build-dependency tree; but pick the first of either type that
1486            # we see. Within either tree, dependencies beat recommendations.
1487            if not old_build_tree and build_tree:
1488                return
1489            if old_build_tree == build_tree:
1490                if not old_recommends or recommends:
1491                    return
1492
1493        reasons[pkg] = (why, build_tree, recommends)
1494
1495    def _add_package(self, seed, pkg, why,
1496                     second_class=False,
1497                     build_tree=False,
1498                     recommends=False):
1499        """Add a package and its dependency trees."""
1500        if self._is_pruned(self._di_kernel_versions, pkg):
1501            _logger.warning("Pruned %s from %s", pkg, seed)
1502            return
1503        if build_tree:
1504            outerseeds = [self._supported(seed)]
1505        else:
1506            outerseeds = self._outer_seeds(seed)
1507        for outerseed in outerseeds:
1508            if outerseed is not None and pkg in outerseed._blacklist:
1509                _logger.error("Package %s blacklisted in %s but seeded in %s "
1510                              "(%s)", pkg, outerseed, seed, why)
1511                seed._blacklist_seen = True
1512                return
1513        if build_tree:
1514            second_class = True
1515
1516        output = self._output[seed.structure]
1517
1518        if pkg not in output._all:
1519            output._all.add(pkg)
1520
1521        for innerseed in self._inner_seeds(seed):
1522            if pkg in innerseed._build:
1523                break
1524        else:
1525            seed._build.add(pkg)
1526
1527        if not build_tree:
1528            for innerseed in self._inner_seeds(seed):
1529                if pkg in innerseed._not_build:
1530                    break
1531            else:
1532                seed._not_build.add(pkg)
1533
1534        # Remember why the package was added to the output for this seed.
1535        # Also remember a reason for "all" too, so that an aggregated list
1536        # of all selected packages can be constructed easily.
1537        self._remember_why(seed._reasons, pkg, why, build_tree, recommends)
1538        self._remember_why(output._all_reasons, pkg, why, build_tree,
1539                           recommends)
1540
1541        for prov in self._packages[pkg]["Provides"]:
1542            seed._pkgprovides[prov[0][0]].add(pkg)
1543
1544        self._add_dependency_tree(seed, pkg,
1545                                  self._packages[pkg]["Pre-Depends"],
1546                                  second_class=second_class,
1547                                  build_tree=build_tree)
1548
1549        self._add_dependency_tree(seed, pkg,
1550                                  self._packages[pkg]["Depends"],
1551                                  second_class=second_class,
1552                                  build_tree=build_tree)
1553
1554        if (self._follow_recommends(seed.structure, seed) or
1555            self._packages[pkg]["Section"] == "metapackages"):
1556            self._add_dependency_tree(seed, pkg,
1557                                      self._packages[pkg]["Recommends"],
1558                                      second_class=second_class,
1559                                      build_tree=build_tree,
1560                                      recommends=True)
1561
1562        src = self._packages[pkg]["Source"]
1563
1564        # Built-Using field is in a form of apt_pkg.parse_depends For
1565        # common-case "pkg (= 1)" it returns
1566        #     [[('pkg', '1', '=')]]
1567        # We thus unpack the first listed alternative pkg-name, for
1568        # each built-using source.
1569        built_using = [i[0][0] for i in self._packages[pkg]["Built-Using"]]
1570        pkg_srcs = []
1571
1572        if second_class:
1573            excluded_srcs = "_build_srcs"
1574        else:
1575            excluded_srcs = "_not_build_srcs"
1576
1577        # Create set of all sources needed for pkg: Source + Built-Using
1578        for pkg_src in built_using + [src]:
1579            if pkg_src in self._sources and pkg_src not in pkg_srcs:
1580                # Consider this source unless it is already part of an inner
1581                # seed
1582                for innerseed in self._inner_seeds(seed):
1583                    if pkg_src in getattr(innerseed, excluded_srcs):
1584                        break
1585                else:
1586                    pkg_srcs.append(pkg_src)
1587            else:
1588                _logger.error("Missing source package: %s (for %s)", pkg_src, pkg)
1589
1590        # Use build_tree flag for src
1591        # Treat all Built-Using as if it's part of build_tree
1592        for pkg_src in pkg_srcs:
1593            if build_tree or pkg_src in built_using:
1594                seed._build_sourcepkgs.add(pkg_src)
1595                if pkg_src in output._blacklist:
1596                    seed._blacklisted.add(pkg_src)
1597            else:
1598                seed._not_build_srcs.add(pkg_src)
1599                seed._sourcepkgs.add(pkg_src)
1600
1601            output._all_srcs.add(pkg_src)
1602            seed._build_srcs.add(pkg_src)
1603
1604            if self._follow_build_depends(seed.structure, seed):
1605                for build_depends in BUILD_DEPENDS:
1606                    self._add_dependency_tree(seed, pkg,
1607                                              self._sources[pkg_src][build_depends],
1608                                              build_depend=True)
1609
1610
1611    def _rescue_includes(self, structure, seedname, rescue_seedname,
1612                         build_tree):
1613        """Rescue packages matching certain patterns from other seeds."""
1614        output = self._output[structure]
1615
1616        try:
1617            seed = self._get_seed(structure, seedname)
1618        except KeyError:
1619            return
1620
1621        if (rescue_seedname not in structure.names and
1622            rescue_seedname != "extra"):
1623            return
1624
1625        # Find all the source packages.
1626        rescue_srcs = set()
1627        if rescue_seedname == "extra":
1628            rescue_seeds = self._inner_seeds(seed)
1629        else:
1630            rescue_seeds = [self._get_seed(structure, rescue_seedname)]
1631        for one_rescue_seed in rescue_seeds:
1632            if build_tree:
1633                rescue_srcs |= one_rescue_seed._build_srcs
1634            else:
1635                rescue_srcs |= one_rescue_seed._not_build_srcs
1636
1637        # For each source, add any binaries that match the include/exclude
1638        # patterns.
1639        for src in rescue_srcs:
1640            rescue = [p for p in self._sources[src]["Binaries"]
1641                        if p in self._packages]
1642            included = set()
1643            if rescue_seedname in seed._includes:
1644                for include in seed._includes[rescue_seedname]:
1645                    included |= set(self._filter_packages(rescue, include))
1646            if rescue_seedname in seed._excludes:
1647                for exclude in seed._excludes[rescue_seedname]:
1648                    included -= set(self._filter_packages(rescue, exclude))
1649            for pkg in included:
1650                if pkg in output._all:
1651                    continue
1652                for lesserseed in self._strictly_outer_seeds(seed):
1653                    if pkg in lesserseed._entries:
1654                        seed._entries.remove(pkg)
1655                        _logger.warning("Promoted %s from %s to %s due to "
1656                                        "%s-Includes",
1657                                        pkg, lesserseed, seed,
1658                                        rescue_seedname.title())
1659                        break
1660                _logger.debug("Rescued %s from %s to %s", pkg,
1661                              rescue_seedname, seed)
1662                if build_tree:
1663                    seed._build_depends.add(pkg)
1664                else:
1665                    seed._depends.add(pkg)
1666                self._add_package(seed, pkg, RescueReason(src),
1667                                  build_tree=build_tree)
1668
1669    # Accessors.
1670    # ----------
1671
1672    def get_source(self, pkg):
1673        """Return the name of the source package that builds pkg."""
1674        return self._packages[pkg]["Source"]
1675
1676    def is_essential(self, pkg):
1677        """Test whether pkg is Essential."""
1678        return self._packages[pkg].get("Essential", "no") == "yes"
1679
1680    def _get_seed(self, structure, seedname):
1681        """Return the GerminatedSeed for this structure and seed name."""
1682        full_seedname = self._make_seed_name(structure.branch, seedname)
1683        return self._seeds[full_seedname]
1684
1685    def _get_seed_entries(self, structure, seedname):
1686        """Return the explicitly seeded entries for this seed.
1687
1688        This includes virtual SeedKernelVersions entries.
1689
1690        """
1691        seed = self._get_seed(structure, seedname)
1692        output = set(seed._entries)
1693        for innerseed in self._inner_seeds(seed):
1694            if innerseed.name == seed.name:
1695                continue
1696            output -= innerseed._depends
1697        # Take care to preserve the original ordering.
1698        # Use a temporary variable to work around a pychecker bug.
1699        ret = [e for e in seed._entries if e in output]
1700        return ret
1701
1702    def get_seed_entries(self, structure, seedname):
1703        """Return the explicitly seeded entries for this seed."""
1704        # Use a temporary variable to work around a pychecker bug.
1705        ret = [
1706            e for e in self._get_seed_entries(structure, seedname)
1707            if not isinstance(e, SeedKernelVersions)]
1708        return ret
1709
1710    def _get_seed_recommends_entries(self, structure, seedname):
1711        """Return the explicitly seeded Recommends entries for this seed.
1712
1713        This includes virtual SeedKernelVersions entries.
1714
1715        """
1716        seed = self._get_seed(structure, seedname)
1717        output = set(seed._recommends_entries)
1718        for innerseed in self._inner_seeds(seed):
1719            if innerseed.name == seed.name:
1720                continue
1721            output -= innerseed._depends
1722        # Take care to preserve the original ordering.
1723        # Use a temporary variable to work around a pychecker bug.
1724        ret = [e for e in seed._recommends_entries if e in output]
1725        return ret
1726
1727    def get_seed_recommends_entries(self, structure, seedname):
1728        """Return the explicitly seeded Recommends entries for this seed."""
1729        # Use a temporary variable to work around a pychecker bug.
1730        ret = [
1731            e for e in self._get_seed_recommends_entries(structure, seedname)
1732            if not isinstance(e, SeedKernelVersions)]
1733        return ret
1734
1735    def get_depends(self, structure, seedname):
1736        """Return the dependencies of this seed."""
1737        return self._get_seed(structure, seedname).depends
1738
1739    def get_full(self, structure, seedname):
1740        """Return the full (run-time) dependency expansion of this seed."""
1741        seed = self._get_seed(structure, seedname)
1742        return (set(self.get_seed_entries(structure, seedname)) |
1743                set(self.get_seed_recommends_entries(structure, seedname)) |
1744                seed._depends)
1745
1746    def get_build_depends(self, structure, seedname):
1747        """Return the build-dependencies of this seed."""
1748        output = set(self._get_seed(structure, seedname)._build_depends)
1749        for outerseedname in structure.outer_seeds(seedname):
1750            output -= self.get_full(structure, outerseedname)
1751        return output
1752
1753    def get_all(self, structure):
1754        """Return all the packages in this structure."""
1755        return list(self._output[structure]._all)
1756
1757    # Methods for writing output to files.
1758    # ------------------------------------
1759
1760    def _write_list(self, reasons, filename, pkgset):
1761        pkglist = sorted(pkgset)
1762
1763        pkg_len = len("Package")
1764        src_len = len("Source")
1765        why_len = len("Why")
1766        mnt_len = len("Maintainer")
1767
1768        for pkg in pkglist:
1769            _pkg_len = len(pkg)
1770            if _pkg_len > pkg_len:
1771                pkg_len = _pkg_len
1772
1773            _src_len = len(self._packages[pkg]["Source"])
1774            if _src_len > src_len:
1775                src_len = _src_len
1776
1777            why = reasons[pkg][0] if pkg in reasons else ""
1778            _why_len = len(str(why))
1779            if _why_len > why_len:
1780                why_len = _why_len
1781
1782            _mnt_len = len(self._packages[pkg]["Maintainer"])
1783            if _mnt_len > mnt_len:
1784                mnt_len = _mnt_len
1785
1786        size = 0
1787        installed_size = 0
1788
1789        with AtomicFile(filename) as f:
1790            print("%-*s | %-*s | %-*s | %-*s | %-15s | %-15s" %
1791                  (pkg_len, "Package",
1792                   src_len, "Source",
1793                   why_len, "Why",
1794                   mnt_len, "Maintainer",
1795                   "Deb Size (B)",
1796                   "Inst Size (KB)"), file=f)
1797            print(("-" * pkg_len) + "-+-" + ("-" * src_len) + "-+-"
1798                  + ("-" * why_len) + "-+-" + ("-" * mnt_len) + "-+-"
1799                  + ("-" * 15) + "-+-" + ("-" * 15) + "-", file=f)
1800            for pkg in pkglist:
1801                why = reasons[pkg][0] if pkg in reasons else ""
1802                size += self._packages[pkg]["Size"]
1803                installed_size += self._packages[pkg]["Installed-Size"]
1804                print("%-*s | %-*s | %-*s | %-*s | %15d | %15d" %
1805                      (pkg_len, pkg,
1806                       src_len, self._packages[pkg]["Source"],
1807                       why_len, why,
1808                       mnt_len, self._packages[pkg]["Maintainer"],
1809                       self._packages[pkg]["Size"],
1810                       self._packages[pkg]["Installed-Size"]), file=f)
1811            print(("-" * (pkg_len + src_len + why_len + mnt_len + 9))
1812                  + "-+-" + ("-" * 15) + "-+-" + ("-" * 15) + "-", file=f)
1813            print("%*s | %15d | %15d" %
1814                  ((pkg_len + src_len + why_len + mnt_len + 9), "",
1815                   size, installed_size), file=f)
1816
1817    def _write_source_list(self, filename, srcset):
1818        srclist = sorted(srcset)
1819
1820        src_len = len("Source")
1821        mnt_len = len("Maintainer")
1822
1823        for src in srclist:
1824            _src_len = len(src)
1825            if _src_len > src_len:
1826                src_len = _src_len
1827
1828            _mnt_len = len(self._sources[src]["Maintainer"])
1829            if _mnt_len > mnt_len:
1830                mnt_len = _mnt_len
1831
1832        with AtomicFile(filename) as f:
1833            fmt = "%-*s | %-*s"
1834
1835            print(fmt % (src_len, "Source", mnt_len, "Maintainer"), file=f)
1836            print(("-" * src_len) + "-+-" + ("-" * mnt_len) + "-", file=f)
1837            for src in srclist:
1838                print(fmt % (src_len, src, mnt_len,
1839                             self._sources[src]["Maintainer"]), file=f)
1840
1841    def write_full_list(self, structure, filename, seedname):
1842        """Write the full (run-time) dependency expansion of this seed."""
1843        seed = self._get_seed(structure, seedname)
1844        self._write_list(seed._reasons, filename,
1845                         self.get_full(structure, seedname))
1846
1847    def write_seed_list(self, structure, filename, seedname):
1848        """Write the explicitly seeded entries for this seed."""
1849        seed = self._get_seed(structure, seedname)
1850        self._write_list(seed._reasons, filename,
1851                         self.get_seed_entries(structure, seedname))
1852
1853    def write_seed_recommends_list(self, structure, filename, seedname):
1854        """Write the explicitly seeded Recommends entries for this seed."""
1855        seed = self._get_seed(structure, seedname)
1856        self._write_list(seed._reasons, filename,
1857                         self.get_seed_recommends_entries(structure, seedname))
1858
1859    def write_depends_list(self, structure, filename, seedname):
1860        """Write the dependencies of this seed."""
1861        seed = self._get_seed(structure, seedname)
1862        self._write_list(seed._reasons, filename, seed._depends)
1863
1864    def write_build_depends_list(self, structure, filename, seedname):
1865        """Write the build-dependencies of this seed."""
1866        seed = self._get_seed(structure, seedname)
1867        self._write_list(seed._reasons, filename,
1868                         self.get_build_depends(structure, seedname))
1869
1870    def write_sources_list(self, structure, filename, seedname):
1871        """Write the source packages for this seed and its dependencies."""
1872        seed = self._get_seed(structure, seedname)
1873        self._write_source_list(filename, seed._sourcepkgs)
1874
1875    def write_build_sources_list(self, structure, filename, seedname):
1876        """Write the source packages for this seed's build-dependencies."""
1877        seed = self._get_seed(structure, seedname)
1878        build_sourcepkgs = seed._build_sourcepkgs
1879        for buildseedname in structure.names:
1880            buildseed = self._get_seed(structure, buildseedname)
1881            build_sourcepkgs -= buildseed._sourcepkgs
1882        self._write_source_list(filename, build_sourcepkgs)
1883
1884    def write_all_list(self, structure, filename):
1885        """Write all the packages in this structure."""
1886        all_bins = set()
1887
1888        for seedname in structure.names:
1889            all_bins |= self.get_full(structure, seedname)
1890            all_bins |= self.get_build_depends(structure, seedname)
1891
1892        self._write_list(self._output[structure]._all_reasons, filename,
1893                         all_bins)
1894
1895    def write_all_source_list(self, structure, filename):
1896        """Write all the source packages for this structure."""
1897        all_srcs = set()
1898
1899        for seedname in structure.names:
1900            seed = self._get_seed(structure, seedname)
1901
1902            all_srcs |= seed._sourcepkgs
1903            all_srcs |= seed._build_sourcepkgs
1904
1905        self._write_source_list(filename, all_srcs)
1906
1907    def write_supported_list(self, structure, filename):
1908        """Write the "supported+build-depends" list."""
1909        sup_bins = set()
1910
1911        for seedname in structure.names:
1912            if seedname == structure.supported:
1913                sup_bins |= self.get_full(structure, seedname)
1914
1915            # Only include those build-dependencies that aren't already in
1916            # the dependency outputs for inner seeds of supported. This
1917            # allows supported+build-depends to be usable as an "everything
1918            # else" output.
1919            build_depends = set(self.get_build_depends(structure, seedname))
1920            for innerseedname in structure.inner_seeds(structure.supported):
1921                build_depends -= self.get_full(structure, innerseedname)
1922            sup_bins |= build_depends
1923
1924        self._write_list(self._output[structure]._all_reasons, filename,
1925                         sup_bins)
1926
1927    def write_supported_source_list(self, structure, filename):
1928        """Write the "supported+build-depends" sources list."""
1929        sup_srcs = set()
1930
1931        for seedname in structure.names:
1932            seed = self._get_seed(structure, seedname)
1933
1934            if seedname == structure.supported:
1935                sup_srcs |= seed._sourcepkgs
1936
1937            # Only include those build-dependencies that aren't already in
1938            # the dependency outputs for inner seeds of supported. This
1939            # allows supported+build-depends to be usable as an "everything
1940            # else" output.
1941            build_sourcepkgs = set(seed._build_sourcepkgs)
1942            for innerseed in self._inner_seeds(self._supported(seed)):
1943                build_sourcepkgs -= innerseed._sourcepkgs
1944            sup_srcs |= build_sourcepkgs
1945
1946        self._write_source_list(filename, sup_srcs)
1947
1948    def write_all_extra_list(self, structure, filename):
1949        """Write the "all+extra" list."""
1950        output = self._output[structure]
1951        self._write_list(output._all_reasons, filename, output._all)
1952
1953    def write_all_extra_source_list(self, structure, filename):
1954        """Write the "all+extra" sources list."""
1955        output = self._output[structure]
1956        self._write_source_list(filename, output._all_srcs)
1957
1958    def write_rdepend_list(self, structure, filename, pkg):
1959        """Write a detailed analysis of reverse-dependencies."""
1960        # First, build a cache of entries for each seed.
1961        output = self._output[structure]
1962        if output._rdepends_cache_entries is None:
1963            cache_entries = {}
1964            for seedname in output._seednames:
1965                cache_entries[seedname] = self.get_seed_entries(
1966                    structure, seedname)
1967            output._rdepends_cache_entries = cache_entries
1968
1969        # Then write out the list itself.
1970        with AtomicFile(filename) as f:
1971            print(pkg, file=f)
1972            self._write_rdepend_list(structure, f, pkg, "", done=set())
1973
1974    def _write_rdepend_list(self, structure, f, pkg, prefix, stack=None,
1975                            done=None):
1976        if stack is None:
1977            stack = []
1978        else:
1979            stack = list(stack)
1980            if pkg in stack:
1981                print(prefix + "! loop", file=f)
1982                return
1983        stack.append(pkg)
1984
1985        if done is None:
1986            done = set()
1987        elif pkg in done:
1988            print(prefix + "! skipped", file=f)
1989            return
1990        done.add(pkg)
1991
1992        output = self._output[structure]
1993        cache_entries = output._rdepends_cache_entries
1994        for seedname in output._seednames:
1995            if pkg in cache_entries[seedname]:
1996                print(prefix + "*", seedname.title(), "seed", file=f)
1997
1998        if "Reverse-Depends" not in self._packages[pkg]:
1999            return
2000
2001        for field in ("Pre-Depends", "Depends", "Recommends") + BUILD_DEPENDS:
2002            if field not in self._packages[pkg]["Reverse-Depends"]:
2003                continue
2004
2005            i = 0
2006            print(prefix + "*", "Reverse", field + ":", file=f)
2007            for dep in self._packages[pkg]["Reverse-Depends"][field]:
2008                i += 1
2009                print(prefix + " +- " + dep, file=f)
2010                if field.startswith("Build-"):
2011                    continue
2012
2013                if i == len(self._packages[pkg]["Reverse-Depends"][field]):
2014                    extra = "    "
2015                else:
2016                    extra = " |  "
2017                self._write_rdepend_list(structure, f, dep, prefix + extra,
2018                                         stack, done)
2019
2020    def write_provides_list(self, structure, filename):
2021        """Write a summary of which packages satisfied Provides."""
2022        output = self._output[structure]
2023
2024        with AtomicFile(filename) as f:
2025            all_pkgprovides = defaultdict(set)
2026            for seedname in output._seednames:
2027                seed = self._get_seed(structure, seedname)
2028                for prov, provset in seed._pkgprovides.items():
2029                    all_pkgprovides[prov].update(provset)
2030
2031            for prov in sorted(all_pkgprovides):
2032                print(prov, file=f)
2033                for pkg in sorted(all_pkgprovides[prov]):
2034                    print("\t%s" % (pkg,), file=f)
2035                print(file=f)
2036
2037    def write_blacklisted(self, structure, filename):
2038        """Write the list of blacklisted packages we encountered."""
2039        output = self._output[structure]
2040
2041        with AtomicFile(filename) as fh:
2042            all_blacklisted = set()
2043            for seedname in output._seednames:
2044                seed = self._get_seed(structure, seedname)
2045                all_blacklisted.update(seed._blacklisted)
2046
2047            for pkg in sorted(all_blacklisted):
2048                blacklist = output._blacklist[pkg]
2049                fh.write('%s\t%s\n' % (pkg, blacklist))
Note: See TracBrowser for help on using the repository browser.