| # -*- coding: utf-8 -*- |
| # Copyright 2019 The Chromium OS Authors. All rights reserved. |
| # Use of this source code is governed by a BSD-style license that can be |
| # found in the LICENSE file. |
| |
| """Interface for calculating dependency graphs via Portage internals""" |
| |
| from __future__ import print_function |
| |
| import collections |
| import copy |
| import os |
| import sys |
| import time |
| from typing import List, Optional, Union |
| |
| from chromite.lib import constants |
| from chromite.lib import cros_logging as logging |
| from chromite.lib import cros_test_lib |
| from chromite.lib import dependency_graph |
| from chromite.lib import dependency_lib |
| from chromite.lib.parser import package_info |
| |
| assert sys.version_info >= (3, 6), 'This module requires Python 3.6+' |
| |
| pytestmark = [cros_test_lib.pytestmark_inside_only] |
| |
| try: |
| import pytest # pylint: disable=import-error |
| pytest.importorskip('_emerge') |
| except ImportError: |
| pass |
| |
| # These aren't available outside the SDK. |
| # pylint: disable=import-error,wrong-import-order,wrong-import-position |
| from _emerge.actions import adjust_configs |
| from _emerge.actions import load_emerge_config |
| from _emerge.create_depgraph_params import create_depgraph_params |
| from _emerge.depgraph import backtrack_depgraph |
| from _emerge.main import parse_opts |
| from _emerge.Package import Package |
| from _emerge.stdout_spinner import stdout_spinner |
| from portage._global_updates import _global_updates |
| import portage |
| # pylint: enable=import-error |
| |
| # pylint: disable=ungrouped-imports |
| from chromite.lib import cros_build_lib |
| from chromite.lib import cros_event |
| |
| # pylint: enable=wrong-import-order,wrong-import-position,ungrouped-imports |
| |
| |
| class DepGraphGenerator(object): |
| """Grab dependency information about packages from portage. |
| |
| Typical usage: |
| deps = DepGraphGenerator() |
| deps.Initialize(sys.argv[1:]) |
| deps_tree, deps_info, bdeps_tree = deps.GenDependencyTree() |
| deps_graph = deps.GenDependencyGraph(deps_tree, deps_info) |
| deps.PrintTree(deps_tree) |
| PrintDepsMap(deps_graph) |
| """ |
| |
| __slots__ = [ |
| 'board', |
| 'emerge', |
| 'package_db', |
| 'show_output', |
| 'sysroot', |
| 'unpack_only', |
| 'max_retries', |
| 'include_bdepend', |
| ] |
| |
| def __init__(self): |
| self.board = None |
| self.emerge = EmergeData() |
| self.package_db = {} |
| self.show_output = False |
| self.sysroot = None |
| self.unpack_only = False |
| self.max_retries = int(os.environ.get('PARALLEL_EMERGE_MAX_RETRIES', 1)) |
| # include_bdepend controls whether or not BDEPEND packages are returned as |
| # part of the dependency graph for the build target. This option only |
| # changes behavior when ROOT is not equal to "/", i.e. when the build |
| # target is a board and not the SDK itself. |
| self.include_bdepend = False |
| |
| def ParseParallelEmergeArgs(self, argv): |
| """Read the parallel emerge arguments from the command-line. |
| |
| We need to be compatible with emerge arg format. We scrape arguments that |
| are specific to parallel_emerge, and pass through the rest directly to |
| emerge. |
| |
| Args: |
| argv: arguments list |
| |
| Returns: |
| Arguments that don't belong to parallel_emerge |
| """ |
| emerge_args = [] |
| for arg in argv: |
| # Specifically match arguments that are specific to parallel_emerge, and |
| # pass through the rest. |
| if arg.startswith('--board='): |
| self.board = arg.replace('--board=', '') |
| elif arg.startswith('--sysroot='): |
| self.sysroot = arg.replace('--sysroot=', '') |
| elif arg.startswith('--workon='): |
| workon_str = arg.replace('--workon=', '') |
| emerge_args.append('--reinstall-atoms=%s' % workon_str) |
| emerge_args.append('--usepkg-exclude=%s' % workon_str) |
| elif arg.startswith('--force-remote-binary='): |
| force_remote_binary = arg.replace('--force-remote-binary=', '') |
| emerge_args.append('--useoldpkg-atoms=%s' % force_remote_binary) |
| elif arg.startswith('--retries='): |
| self.max_retries = int(arg.replace('--retries=', '')) |
| elif arg == '--show-output': |
| self.show_output = True |
| elif arg == '--rebuild': |
| emerge_args.append('--rebuild-if-unbuilt') |
| elif arg == '--unpackonly': |
| emerge_args.append('--fetchonly') |
| self.unpack_only = True |
| elif arg.startswith('--eventlogfile='): |
| log_file_name = arg.replace('--eventlogfile=', '') |
| event_logger = cros_event.getEventFileLogger(log_file_name) |
| event_logger.setKind('ParallelEmerge') |
| cros_event.setEventLogger(event_logger) |
| elif arg == '--include-bdepend': |
| self.include_bdepend = True |
| else: |
| # Not one of our options, so pass through to emerge. |
| emerge_args.append(arg) |
| |
| # These packages take a really long time to build, so, for expediency, we |
| # are blacklisting them from automatic rebuilds because one of their |
| # dependencies needs to be recompiled. |
| for pkg in ('chromeos-base/chromeos-chrome',): |
| emerge_args.append('--rebuild-exclude=%s' % pkg) |
| |
| return emerge_args |
| |
| def Initialize(self, args): |
| """Initializer. Parses arguments and sets up portage state.""" |
| |
| # Parse and strip out args that are just intended for parallel_emerge. |
| emerge_args = self.ParseParallelEmergeArgs(args) |
| |
| if self.sysroot and self.board: |
| cros_build_lib.Die('--sysroot and --board are incompatible.') |
| |
| # Setup various environment variables based on our current board. These |
| # variables are normally setup inside emerge-${BOARD}, but since we don't |
| # call that script, we have to set it up here. These variables serve to |
| # point our tools at /build/BOARD and to setup cross compiles to the |
| # appropriate board as configured in toolchain.conf. |
| if self.board: |
| self.sysroot = os.environ.get('SYSROOT', |
| cros_build_lib.GetSysroot(self.board)) |
| |
| if self.sysroot: |
| os.environ['PORTAGE_CONFIGROOT'] = self.sysroot |
| os.environ['SYSROOT'] = self.sysroot |
| |
| # Turn off interactive delays |
| os.environ['EBEEP_IGNORE'] = '1' |
| os.environ['EPAUSE_IGNORE'] = '1' |
| os.environ['CLEAN_DELAY'] = '0' |
| |
| # Parse the emerge options. |
| action, opts, cmdline_packages = parse_opts(emerge_args, silent=True) |
| |
| # Set environment variables based on options. Portage normally sets these |
| # environment variables in emerge_main, but we can't use that function, |
| # because it also does a bunch of other stuff that we don't want. |
| # TODO(davidjames): Patch portage to move this logic into a function we can |
| # reuse here. |
| if '--debug' in opts: |
| os.environ['PORTAGE_DEBUG'] = '1' |
| if '--config-root' in opts: |
| os.environ['PORTAGE_CONFIGROOT'] = opts['--config-root'] |
| if '--root' in opts: |
| os.environ['ROOT'] = opts['--root'] |
| elif self.board and 'ROOT' not in os.environ: |
| os.environ['ROOT'] = self.sysroot |
| if '--accept-properties' in opts: |
| os.environ['ACCEPT_PROPERTIES'] = opts['--accept-properties'] |
| |
| # If we're installing packages to the board, we can disable vardb locks. |
| # This is safe because we only run up to one instance of parallel_emerge in |
| # parallel. |
| # TODO(davidjames): Enable this for the host too. |
| if self.sysroot: |
| os.environ.setdefault('PORTAGE_LOCKS', 'false') |
| |
| # Now that we've setup the necessary environment variables, we can load the |
| # emerge config from disk. |
| # pylint: disable=unpacking-non-sequence |
| settings, trees, mtimedb = load_emerge_config() |
| |
| # Add in EMERGE_DEFAULT_OPTS, if specified. |
| tmpcmdline = [] |
| if '--ignore-default-opts' not in opts: |
| tmpcmdline.extend(settings['EMERGE_DEFAULT_OPTS'].split()) |
| tmpcmdline.extend(emerge_args) |
| action, opts, cmdline_packages = parse_opts(tmpcmdline) |
| |
| # If we're installing to the board, we want the --root-deps option so that |
| # portage will install the build dependencies to that location as well. |
| if self.sysroot: |
| opts.setdefault('--root-deps', True) |
| |
| # Check whether our portage tree is out of date. Typically, this happens |
| # when you're setting up a new portage tree, such as in setup_board and |
| # make_chroot. In that case, portage applies a bunch of global updates |
| # here. Once the updates are finished, we need to commit any changes |
| # that the global update made to our mtimedb, and reload the config. |
| # |
| # Portage normally handles this logic in emerge_main, but again, we can't |
| # use that function here. |
| if _global_updates(trees, mtimedb['updates']): |
| mtimedb.commit() |
| # pylint: disable=unpacking-non-sequence |
| settings, trees, mtimedb = load_emerge_config(trees=trees) |
| |
| # Setup implied options. Portage normally handles this logic in |
| # emerge_main. |
| if '--buildpkgonly' in opts or 'buildpkg' in settings.features: |
| opts.setdefault('--buildpkg', True) |
| if '--getbinpkgonly' in opts: |
| opts.setdefault('--usepkgonly', True) |
| opts.setdefault('--getbinpkg', True) |
| if 'getbinpkg' in settings.features: |
| # Per emerge_main, FEATURES=getbinpkg overrides --getbinpkg=n |
| opts['--getbinpkg'] = True |
| if '--getbinpkg' in opts or '--usepkgonly' in opts: |
| opts.setdefault('--usepkg', True) |
| if '--fetch-all-uri' in opts: |
| opts.setdefault('--fetchonly', True) |
| if '--skipfirst' in opts: |
| opts.setdefault('--resume', True) |
| if '--buildpkgonly' in opts: |
| # --buildpkgonly will not merge anything, so it overrides all binary |
| # package options. |
| for opt in ('--getbinpkg', '--getbinpkgonly', '--usepkg', '--usepkgonly'): |
| opts.pop(opt, None) |
| if (settings.get('PORTAGE_DEBUG', '') == '1' and |
| 'python-trace' in settings.features): |
| portage.debug.set_trace(True) |
| |
| # Complain about unsupported options |
| for opt in ('--ask', '--ask-enter-invalid', '--resume', '--skipfirst'): |
| if opt in opts: |
| print('%s is not supported by parallel_emerge' % opt) |
| sys.exit(1) |
| |
| # Make emerge specific adjustments to the config (e.g. colors!) |
| adjust_configs(opts, trees) |
| |
| # Save our configuration so far in the emerge object |
| emerge = self.emerge |
| emerge.action, emerge.opts = action, opts |
| emerge.settings, emerge.trees, emerge.mtimedb = settings, trees, mtimedb |
| emerge.cmdline_packages = cmdline_packages |
| root = settings['ROOT'] |
| emerge.root_config = trees[root]['root_config'] |
| |
| if '--usepkg' in opts: |
| emerge.trees[root]['bintree'].populate('--getbinpkg' in opts) |
| |
| def CreateDepgraph(self, emerge, packages): |
| """Create an emerge depgraph object.""" |
| # Setup emerge options. |
| emerge_opts = emerge.opts.copy() |
| |
| # Ask portage to build a dependency graph. with the options we specified |
| # above. |
| params = create_depgraph_params(emerge_opts, emerge.action) |
| success, depgraph, favorites = backtrack_depgraph( |
| emerge.settings, emerge.trees, emerge_opts, params, emerge.action, |
| packages, emerge.spinner) |
| emerge.depgraph = depgraph |
| |
| # Is it impossible to honor the user's request? Bail! |
| if not success: |
| depgraph.display_problems() |
| sys.exit(1) |
| |
| emerge.depgraph = depgraph |
| emerge.favorites = favorites |
| |
| # Prime and flush emerge caches. |
| root = emerge.settings['ROOT'] |
| vardb = emerge.trees[root]['vartree'].dbapi |
| if '--pretend' not in emerge.opts: |
| vardb.counter_tick() |
| vardb.flush_cache() |
| |
| def HasPrebuilt(self, pkg_cpf: str): |
| """Check if the given package cpf has a prebuilt. |
| |
| Args: |
| pkg_cpf: The fully qualified category/package-version-revision. |
| |
| Returns: |
| bool: True if there is a prebuilt available, False otherwise. |
| """ |
| if not self.package_db: |
| self.GenDependencyTree() |
| |
| package = self.package_db.get(pkg_cpf) |
| if package: |
| return package.type_name == 'binary' |
| |
| return False |
| |
| def GenDependencyTree(self): |
| """Get dependency tree info from emerge. |
| |
| Returns: |
| A 3-tuple of the dependency tree, the dependency tree info, and the |
| BDEPEND dependency tree. |
| The BDEPEND dependency tree, or "bdeps_tree", consists of the packages |
| that would be installed to the SDK BROOT (at "/") rather than the board |
| root at "/build/$BOARD". If the ROOT is already equal to "/" the contents |
| of deps_tree and bdeps_tree will be identical. |
| """ |
| start = time.time() |
| |
| emerge = self.emerge |
| |
| # Create a list of packages to merge |
| packages = set(emerge.cmdline_packages[:]) |
| |
| # Tell emerge to be quiet. We print plenty of info ourselves so we don't |
| # need any extra output from portage. |
| portage.util.noiselimit = -1 |
| |
| # My favorite feature: The silent spinner. It doesn't spin. Ever. |
| # I'd disable the colors by default too, but they look kind of cool. |
| emerge.spinner = stdout_spinner() |
| emerge.spinner.update = emerge.spinner.update_quiet |
| |
| if '--quiet' not in emerge.opts: |
| print('Calculating deps...') |
| |
| with cros_event.newEvent(task_name='GenerateDepTree'): |
| self.CreateDepgraph(emerge, packages) |
| depgraph = emerge.depgraph |
| |
| # Build our own tree from the emerge digraph. |
| deps_tree = {} |
| bdeps_tree = {} |
| # pylint: disable=protected-access |
| digraph = depgraph._dynamic_config.digraph |
| root = emerge.settings['ROOT'] |
| final_db = depgraph._dynamic_config._filtered_trees[root]['graph_db'] |
| for node, node_deps in digraph.nodes.items(): |
| # Calculate dependency packages that need to be installed first. Each |
| # child on the digraph is a dependency. The "operation" field specifies |
| # what we're doing (e.g. merge, uninstall, etc.). The "priorities" array |
| # contains the type of dependency (e.g. build, runtime, runtime_post, |
| # etc.) |
| # |
| # Portage refers to the identifiers for packages as a CPV. This acronym |
| # stands for Component/Path/Version. |
| # |
| # Here's an example CPV: chromeos-base/power_manager-0.0.1-r1 |
| # Split up, this CPV would be: |
| # C -- Component: chromeos-base |
| # P -- Path: power_manager |
| # V -- Version: 0.0.1-r1 |
| # |
| # We just refer to CPVs as packages here because it's easier. |
| |
| if not isinstance(node, Package): |
| # Some nodes may be the AtomArgs (usually the virtuals) or sets. |
| # We only want to deal with the packages themselves. |
| continue |
| |
| deps = {} |
| for child, priorities in node_deps[0].items(): |
| if not isinstance(child, Package): |
| continue |
| |
| if self.include_bdepend or child.root == node.root: |
| cpv = str(child.cpv) |
| action = str(child.operation) |
| |
| # If we're uninstalling a package, check whether Portage is |
| # installing a replacement. If so, just depend on the installation |
| # of the new package, because the old package will automatically |
| # be uninstalled at that time. |
| if action == 'uninstall': |
| for pkg in final_db.match_pkgs(child.slot_atom): |
| cpv = str(pkg.cpv) |
| action = 'merge' |
| break |
| |
| deps[cpv] = dict( |
| action=action, deptypes=[str(x) for x in priorities], deps={}, |
| root=child.root) |
| |
| # We've built our list of deps, so we can add our package to the tree. |
| |
| # If a package is destined for ROOT, then it is in DEPEND OR RDEPEND |
| # and we want to include it in the deps tree. If the package is not |
| # destined for ROOT, then (in the Chrome OS build) we must be building |
| # for a board and the package is a BDEPEND. We only want to add that |
| # package to the deps_tree if include_bdepend is set. |
| if node.root == root or self.include_bdepend: |
| deps_tree[str(node.cpv)] = dict(action=str(node.operation), deps=deps, |
| root=node.root) |
| |
| # The only packages that will have a distinct root (in the Chrome OS |
| # build) are BDEPEND packages for a board target. If we are building |
| # for the host (the SDK) then BDEPEND packages 1. Will have the same |
| # root as every other package and 2. Are functionally the same as |
| # DEPEND packages and belong in the deps_tree. |
| # |
| # If include_bdepend is passed and we are building for a board target, |
| # BDEPEND packages will intentionally show up in both deps_tree and |
| # bdeps_tree. |
| if node.root != root: |
| bdeps_tree[str(node.cpv)] = dict( |
| action=str(node.operation), deps=deps, root=node.root) |
| |
| # Ask portage for its install plan, so that we can only throw out |
| # dependencies that portage throws out. |
| deps_info = {} |
| for pkg in depgraph.altlist(): |
| if isinstance(pkg, Package): |
| # Save off info about the package |
| deps_info[str(pkg.cpv)] = {'idx': len(deps_info)} |
| self.package_db[pkg.cpv] = pkg |
| |
| seconds = time.time() - start |
| if '--quiet' not in emerge.opts: |
| print('Deps calculated in %dm%.1fs' % (seconds // 60, seconds % 60)) |
| |
| return deps_tree, deps_info, bdeps_tree |
| |
| def PrintTree(self, deps, depth=''): |
| """Print the deps we have seen in the emerge output. |
| |
| Args: |
| deps: Dependency tree structure. |
| depth: Allows printing the tree recursively, with indentation. |
| """ |
| for entry in sorted(deps): |
| action = deps[entry]['action'] |
| print('%s %s (%s)' % (depth, entry, action)) |
| self.PrintTree(deps[entry]['deps'], depth=depth + ' ') |
| |
| def GenDependencyGraph(self, deps_tree, deps_info): |
| """Generate a doubly linked dependency graph. |
| |
| Args: |
| deps_tree: Dependency tree structure. |
| deps_info: More details on the dependencies. |
| |
| Returns: |
| Deps graph in the form of a dict of packages, with each package |
| specifying a "needs" list and "provides" list. |
| """ |
| emerge = self.emerge |
| |
| # deps_map is the actual dependency graph. |
| # |
| # Each package specifies a "needs" list and a "provides" list. The "needs" |
| # list indicates which packages we depend on. The "provides" list |
| # indicates the reverse dependencies -- what packages need us. |
| # |
| # We also provide some other information in the dependency graph: |
| # - action: What we're planning on doing with this package. Generally, |
| # "merge", "nomerge", or "uninstall" |
| deps_map = {} |
| |
| def ReverseTree(packages): |
| """Convert tree to digraph. |
| |
| Take the tree of package -> requirements and reverse it to a digraph of |
| buildable packages -> packages they unblock. |
| |
| Args: |
| packages: Tree(s) of dependencies. |
| |
| Returns: |
| Unsanitized digraph. |
| """ |
| binpkg_phases = set(['setup', 'preinst', 'postinst']) |
| needed_dep_types = set([ |
| 'blocker', 'buildtime', 'buildtime_slot_op', 'runtime', |
| 'runtime_slot_op' |
| ]) |
| ignored_dep_types = set(['ignored', 'runtime_post', 'soft']) |
| |
| # There's a bug in the Portage library where it always returns 'optional' |
| # and never 'buildtime' for the digraph while --usepkg is enabled; even |
| # when the package is being rebuilt. To work around this, we treat |
| # 'optional' as needed when we are using --usepkg. See crbug.com/756240 . |
| if '--usepkg' in self.emerge.opts: |
| needed_dep_types.add('optional') |
| else: |
| ignored_dep_types.add('optional') |
| |
| all_dep_types = ignored_dep_types | needed_dep_types |
| for pkg in packages: |
| |
| # Create an entry for the package |
| action = packages[pkg]['action'] |
| default_pkg = { |
| 'needs': {}, |
| 'provides': set(), |
| 'action': action, |
| 'nodeps': False, |
| 'binary': False |
| } |
| this_pkg = deps_map.setdefault(pkg, default_pkg) |
| |
| if pkg in deps_info: |
| this_pkg['idx'] = deps_info[pkg]['idx'] |
| |
| # If a package doesn't have any defined phases that might use the |
| # dependent packages (i.e. pkg_setup, pkg_preinst, or pkg_postinst), |
| # we can install this package before its deps are ready. |
| emerge_pkg = self.package_db.get(pkg) |
| if emerge_pkg and emerge_pkg.type_name == 'binary': |
| this_pkg['binary'] = True |
| defined_phases = emerge_pkg.defined_phases |
| defined_binpkg_phases = binpkg_phases.intersection(defined_phases) |
| if not defined_binpkg_phases: |
| this_pkg['nodeps'] = True |
| |
| # Create entries for dependencies of this package first. |
| ReverseTree(packages[pkg]['deps']) |
| |
| # Add dependencies to this package. |
| for dep, dep_item in packages[pkg]['deps'].items(): |
| # We only need to enforce strict ordering of dependencies if the |
| # dependency is a blocker, or is a buildtime or runtime dependency. |
| # (I.e., ignored, optional, and runtime_post dependencies don't |
| # depend on ordering.) |
| dep_types = dep_item['deptypes'] |
| if needed_dep_types.intersection(dep_types): |
| deps_map[dep]['provides'].add(pkg) |
| this_pkg['needs'][dep] = '/'.join(dep_types) |
| |
| # Verify we processed all appropriate dependency types. |
| unknown_dep_types = set(dep_types) - all_dep_types |
| if unknown_dep_types: |
| print('Unknown dependency types found:') |
| print(' %s -> %s (%s)' % (pkg, dep, '/'.join(unknown_dep_types))) |
| sys.exit(1) |
| |
| # If there's a blocker, Portage may need to move files from one |
| # package to another, which requires editing the CONTENTS files of |
| # both packages. To avoid race conditions while editing this file, |
| # the two packages must not be installed in parallel, so we can't |
| # safely ignore dependencies. See https://crbug.com/202428. |
| if 'blocker' in dep_types: |
| this_pkg['nodeps'] = False |
| |
| def FindCycles(): |
| """Find cycles in the dependency tree. |
| |
| Returns: |
| A dict mapping cyclic packages to a dict of the deps that cause |
| cycles. For each dep that causes cycles, it returns an example |
| traversal of the graph that shows the cycle. |
| """ |
| |
| def FindCyclesAtNode(pkg, cycles, unresolved, resolved): |
| """Find cycles in cyclic dependencies starting at specified package. |
| |
| Args: |
| pkg: Package identifier. |
| cycles: A dict mapping cyclic packages to a dict of the deps that |
| cause cycles. For each dep that causes cycles, it returns an |
| example traversal of the graph that shows the cycle. |
| unresolved: Nodes that have been visited but are not fully processed. |
| resolved: Nodes that have been visited and are fully processed. |
| """ |
| pkg_cycles = cycles.get(pkg) |
| if pkg in resolved and not pkg_cycles: |
| # If we already looked at this package, and found no cyclic |
| # dependencies, we can stop now. |
| return |
| unresolved.append(pkg) |
| for dep in deps_map[pkg]['needs']: |
| if dep in unresolved: |
| idx = unresolved.index(dep) |
| mycycle = unresolved[idx:] + [dep] |
| for i in range(len(mycycle) - 1): |
| pkg1, pkg2 = mycycle[i], mycycle[i + 1] |
| cycles.setdefault(pkg1, {}).setdefault(pkg2, mycycle) |
| elif not pkg_cycles or dep not in pkg_cycles: |
| # Looks like we haven't seen this edge before. |
| FindCyclesAtNode(dep, cycles, unresolved, resolved) |
| unresolved.pop() |
| resolved.add(pkg) |
| |
| cycles, unresolved, resolved = {}, [], set() |
| for pkg in deps_map: |
| FindCyclesAtNode(pkg, cycles, unresolved, resolved) |
| return cycles |
| |
| def RemoveUnusedPackages(): |
| """Remove installed packages, propagating dependencies.""" |
| # Schedule packages that aren't on the install list for removal |
| rm_pkgs = set(deps_map.keys()) - set(deps_info.keys()) |
| |
| # Remove the packages we don't want, simplifying the graph and making |
| # it easier for us to crack cycles. |
| for pkg in sorted(rm_pkgs): |
| this_pkg = deps_map[pkg] |
| needs = this_pkg['needs'] |
| provides = this_pkg['provides'] |
| for dep in needs: |
| dep_provides = deps_map[dep]['provides'] |
| dep_provides.update(provides) |
| dep_provides.discard(pkg) |
| dep_provides.discard(dep) |
| for target in provides: |
| target_needs = deps_map[target]['needs'] |
| target_needs.update(needs) |
| target_needs.pop(pkg, None) |
| target_needs.pop(target, None) |
| del deps_map[pkg] |
| |
| def PrintCycleBreak(basedep, dep, mycycle): |
| """Print details about a cycle that we are planning on breaking. |
| |
| We are breaking a cycle where dep needs basedep. mycycle is an |
| example cycle which contains dep -> basedep. |
| """ |
| |
| needs = deps_map[dep]['needs'] |
| depinfo = needs.get(basedep, 'deleted') |
| |
| # It's OK to swap install order for blockers, as long as the two |
| # packages aren't installed in parallel. If there is a cycle, then |
| # we know the packages depend on each other already, so we can drop the |
| # blocker safely without printing a warning. |
| if depinfo == 'blocker': |
| return |
| |
| # Notify the user that we're breaking a cycle. |
| print('Breaking %s -> %s (%s)' % (dep, basedep, depinfo)) |
| |
| # Show cycle. |
| for i in range(len(mycycle) - 1): |
| pkg1, pkg2 = mycycle[i], mycycle[i + 1] |
| needs = deps_map[pkg1]['needs'] |
| depinfo = needs.get(pkg2, 'deleted') |
| if pkg1 == dep and pkg2 == basedep: |
| depinfo = depinfo + ', deleting' |
| print(' %s -> %s (%s)' % (pkg1, pkg2, depinfo)) |
| |
| def SanitizeTree(): |
| """Remove circular dependencies. |
| |
| We prune all dependencies involved in cycles that go against the emerge |
| ordering. This has a nice property: we're guaranteed to merge |
| dependencies in the same order that portage does. |
| |
| Because we don't treat any dependencies as "soft" unless they're killed |
| by a cycle, we pay attention to a larger number of dependencies when |
| merging. This hurts performance a bit, but helps reliability. |
| """ |
| start = time.time() |
| cycles = FindCycles() |
| while cycles: |
| for dep, mycycles in cycles.items(): |
| for basedep, mycycle in mycycles.items(): |
| if deps_info[basedep]['idx'] >= deps_info[dep]['idx']: |
| if '--quiet' not in emerge.opts: |
| PrintCycleBreak(basedep, dep, mycycle) |
| del deps_map[dep]['needs'][basedep] |
| deps_map[basedep]['provides'].remove(dep) |
| cycles = FindCycles() |
| seconds = time.time() - start |
| if '--quiet' not in emerge.opts and seconds >= 0.1: |
| print('Tree sanitized in %dm%.1fs' % (seconds // 60, seconds % 60)) |
| |
| def FindRecursiveProvides(pkg, seen): |
| """Find all nodes that require a particular package. |
| |
| Assumes that graph is acyclic. |
| |
| Args: |
| pkg: Package identifier. |
| seen: Nodes that have been visited so far. |
| """ |
| if pkg in seen: |
| return |
| seen.add(pkg) |
| info = deps_map[pkg] |
| info['tprovides'] = info['provides'].copy() |
| for dep in info['provides']: |
| FindRecursiveProvides(dep, seen) |
| info['tprovides'].update(deps_map[dep]['tprovides']) |
| |
| ReverseTree(deps_tree) |
| |
| # We need to remove unused packages so that we can use the dependency |
| # ordering of the install process to show us what cycles to crack. |
| RemoveUnusedPackages() |
| SanitizeTree() |
| seen = set() |
| for pkg in deps_map: |
| FindRecursiveProvides(pkg, seen) |
| return deps_map |
| |
| def PrintInstallPlan(self, deps_map): |
| """Print an emerge-style install plan. |
| |
| The install plan lists what packages we're installing, in order. |
| It's useful for understanding what parallel_emerge is doing. |
| |
| Args: |
| deps_map: The dependency graph. |
| """ |
| |
| def InstallPlanAtNode(target, deps_map): |
| nodes = [] |
| nodes.append(target) |
| for dep in deps_map[target]['provides']: |
| del deps_map[dep]['needs'][target] |
| if not deps_map[dep]['needs']: |
| nodes.extend(InstallPlanAtNode(dep, deps_map)) |
| return nodes |
| |
| deps_map = copy.deepcopy(deps_map) |
| install_plan = [] |
| plan = set() |
| for target, info in deps_map.items(): |
| if not info['needs'] and target not in plan: |
| for item in InstallPlanAtNode(target, deps_map): |
| plan.add(item) |
| install_plan.append(self.package_db[item]) |
| |
| for pkg in plan: |
| del deps_map[pkg] |
| |
| if deps_map: |
| print('Cyclic dependencies:', ' '.join(deps_map)) |
| PrintDepsMap(deps_map) |
| sys.exit(1) |
| |
| self.emerge.depgraph.display(install_plan) |
| |
| |
| class EmergeData(object): |
| """This simple struct holds various emerge variables. |
| |
| This struct helps us easily pass emerge variables around as a unit. |
| These variables are used for calculating dependencies and installing |
| packages. |
| """ |
| |
| __slots__ = [ |
| 'action', 'cmdline_packages', 'depgraph', 'favorites', 'mtimedb', 'opts', |
| 'root_config', 'scheduler_graph', 'settings', 'spinner', 'trees' |
| ] |
| |
| def __init__(self): |
| # The action the user requested. If the user is installing packages, this |
| # is None. If the user is doing anything other than installing packages, |
| # this will contain the action name, which will map exactly to the |
| # long-form name of the associated emerge option. |
| # |
| # Example: If you call parallel_emerge --unmerge package, the action name |
| # will be "unmerge" |
| self.action = None |
| |
| # The list of packages the user passed on the command-line. |
| self.cmdline_packages = None |
| |
| # The emerge dependency graph. It'll contain all the packages involved in |
| # this merge, along with their versions. |
| self.depgraph = None |
| |
| # The list of candidates to add to the world file. |
| self.favorites = None |
| |
| # A dict of the options passed to emerge. This dict has been cleaned up |
| # a bit by parse_opts, so that it's a bit easier for the emerge code to |
| # look at the options. |
| # |
| # Emerge takes a few shortcuts in its cleanup process to make parsing of |
| # the options dict easier. For example, if you pass in "--usepkg=n", the |
| # "--usepkg" flag is just left out of the dictionary altogether. Because |
| # --usepkg=n is the default, this makes parsing easier, because emerge |
| # can just assume that if "--usepkg" is in the dictionary, it's enabled. |
| # |
| # These cleanup processes aren't applied to all options. For example, the |
| # --with-bdeps flag is passed in as-is. For a full list of the cleanups |
| # applied by emerge, see the parse_opts function in the _emerge.main |
| # package. |
| self.opts = None |
| |
| # A dictionary used by portage to maintain global state. This state is |
| # loaded from disk when portage starts up, and saved to disk whenever we |
| # call mtimedb.commit(). |
| # |
| # This database contains information about global updates (i.e., what |
| # version of portage we have) and what we're currently doing. Portage |
| # saves what it is currently doing in this database so that it can be |
| # resumed when you call it with the --resume option. |
| # |
| # parallel_emerge does not save what it is currently doing in the mtimedb, |
| # so we do not support the --resume option. |
| self.mtimedb = None |
| |
| # The portage configuration for our current root. This contains the portage |
| # settings (see below) and the three portage trees for our current root. |
| # (The three portage trees are explained below, in the documentation for |
| # the "trees" member.) |
| self.root_config = None |
| |
| # The scheduler graph is used by emerge to calculate what packages to |
| # install. We don't actually install any deps, so this isn't really used, |
| # but we pass it in to the Scheduler object anyway. |
| self.scheduler_graph = None |
| |
| # Portage settings for our current session. Most of these settings are set |
| # in make.conf inside our current install root. |
| self.settings = None |
| |
| # The spinner, which spews stuff to stdout to indicate that portage is |
| # doing something. We maintain our own spinner, so we set the portage |
| # spinner to "silent" mode. |
| self.spinner = None |
| |
| # The portage trees. There are separate portage trees for each root. To get |
| # the portage tree for the current root, you can look in self.trees[root], |
| # where root = self.settings["ROOT"]. |
| # |
| # In each root, there are three trees: vartree, porttree, and bintree. |
| # - vartree: A database of the currently-installed packages. |
| # - porttree: A database of ebuilds, that can be used to build packages. |
| # - bintree: A database of binary packages. |
| self.trees = None |
| |
| |
| def PrintDepsMap(deps_map): |
| """Print dependency graph, for each package list it's prerequisites.""" |
| for i in sorted(deps_map): |
| print('%s: (%s) needs' % (i, deps_map[i]['action'])) |
| needs = deps_map[i]['needs'] |
| for j in sorted(needs): |
| print(' %s' % (j)) |
| if not needs: |
| print(' no dependencies') |
| |
| |
| # Depgraph results data container used by the raw depgraph functions. The |
| # deps attribute has the main depgraph info (DEPEND, RDEPEND, and optionally |
| # BDEPEND), while the bdeps attribute contains just the bdepends depgraph, |
| # i.e. the depgraph installed to the SDK. |
| DepgraphResult = collections.namedtuple('DepgraphResult', |
| ('deps', 'bdeps', 'packages')) |
| |
| |
| def _get_emerge_args(sysroot_path: str, |
| packages: Union[List[str], List[package_info.PackageInfo]], |
| include_bdeps: bool) -> List[str]: |
| """Get the default emerge arguments for building a depgraph.""" |
| # Pretend: Don't actually install anything. |
| # Emptytree: Act as though nothing is installed (even if some packages are). |
| # Sysroot: Which sysroot we're considering. |
| args = ['--quiet', '--pretend', '--emptytree', '--sysroot', sysroot_path] |
| # Also set the root for DepGraphGenerator specific semantics. This might not |
| # be necessary, pending more investigation. |
| # TODO: Document final reason or remove if unnecessary. |
| args.extend(['--root', sysroot_path]) |
| if include_bdeps: |
| args.append('--include-bdepend') |
| |
| try: |
| # Assume PackageInfo instance. |
| final_pkgs = [p.atom for p in packages] |
| except AttributeError: |
| # Also accept strings. |
| final_pkgs = [str(p) for p in packages] |
| args.extend(final_pkgs) |
| |
| logging.info('Generating depgraph for packages: %s', ', '.join(final_pkgs)) |
| |
| return args |
| |
| |
| def _get_sysroot_path( |
| sysroot: Union[str, 'sysroot_lib.Sysroot'], |
| build_target: Union[str, 'build_target_lib.BuildTarget']) -> str: |
| """Convenience function to support sysroot paths from a variety of sources. |
| |
| Get the sysroot path from a sysroot (the path, or a Sysroot instance), or |
| a build target (by name, or from the BuildTarget instance). |
| """ |
| if sysroot: |
| try: |
| return sysroot.path |
| except AttributeError: |
| return sysroot |
| else: |
| try: |
| return build_target.root |
| except AttributeError: |
| return cros_build_lib.GetSysroot(build_target) |
| |
| |
| def _get_raw_sdk_depgraph( |
| packages: Optional[Union[List[str], List[package_info.PackageInfo]]] = None |
| ) -> DepgraphResult: |
| """Get the depgraph for the SDK itself. |
| |
| The SDK deps will contain the packages installed to a fresh SDK. |
| The bdeps will always be empty since everything is installed to the SDK. |
| """ |
| sysroot_path = cros_build_lib.GetSysroot(board=None) |
| packages = packages or [constants.TARGET_SDK] |
| lib_argv = _get_emerge_args(sysroot_path, packages, include_bdeps=True) |
| deps = DepGraphGenerator() |
| deps.Initialize(lib_argv) |
| deps_tree, _deps_info, bdeps_tree = deps.GenDependencyTree() |
| |
| return DepgraphResult(deps=deps_tree, bdeps=bdeps_tree, packages=packages) |
| |
| |
| def _get_raw_sysroot_depgraph( |
| sysroot: Optional['sysroot_lib.Sysroot'] = None, |
| build_target: Optional['build_target_lib.BuildTarget'] = None, |
| packages: Optional[Union[List[str], List[package_info.PackageInfo]]] = None |
| ) -> DepgraphResult: |
| """Get the sysroot depgraph for a build target. |
| |
| The sysroot deps are the packages installed to a sysroot -- effectively |
| the packages installed on a device. The bdeps contains all the packages |
| installed to the SDK when the board is built. The two graphs are technically |
| disjoint, but packages can appear in both (with different roots). |
| """ |
| assert build_target or sysroot |
| packages = packages or constants.ALL_TARGET_PACKAGES |
| sysroot_path = _get_sysroot_path(sysroot, build_target) |
| lib_argv = _get_emerge_args(sysroot_path, packages, include_bdeps=False) |
| |
| deps = DepGraphGenerator() |
| deps.Initialize(lib_argv) |
| deps_tree, _deps_info, bdeps_tree = deps.GenDependencyTree() |
| |
| return DepgraphResult(deps=deps_tree, bdeps=bdeps_tree, packages=packages) |
| |
| |
| def _get_raw_build_target_depgraph( |
| sysroot: Optional['sysroot_lib.Sysroot'] = None, |
| build_target: Optional['build_target_lib.BuildTarget'] = None, |
| packages: Optional[Union[List[str], List[package_info.PackageInfo]]] = None |
| ) -> DepgraphResult: |
| """Get the full depgraph for a build target - its sysroot and bdepends. |
| |
| The build target deps contains the [r]depends packages installed |
| to the sysroot and bdepends packages installed to the SDK. |
| The bdeps contains only the bdepends packages installed to |
| the SDK. The bdeps graph is a subgraph of the deps graph. |
| """ |
| assert build_target or sysroot |
| packages = packages or constants.ALL_TARGET_PACKAGES |
| sysroot_path = _get_sysroot_path(sysroot, build_target) |
| lib_argv = _get_emerge_args(sysroot_path, packages, include_bdeps=True) |
| |
| deps = DepGraphGenerator() |
| deps.Initialize(lib_argv) |
| |
| deps_tree, _deps_info, bdeps_tree = deps.GenDependencyTree() |
| return DepgraphResult(deps=deps_tree, bdeps=bdeps_tree, packages=packages) |
| |
| |
| def get_sdk_dependency_graph( |
| pkgs: Optional[Union[List[str], List[package_info.PackageInfo]]] = None, |
| with_src_paths: bool = False |
| ) -> dependency_graph.DependencyGraph: |
| """Get the DependencyGraph for the SDK itself.""" |
| result = _get_raw_sdk_depgraph(packages=pkgs) |
| return _create_graph_from_deps(result.deps, |
| sysroot=cros_build_lib.GetSysroot(board=None), |
| packages=result.packages, |
| with_src_paths=with_src_paths) |
| |
| |
| def get_sysroot_dependency_graph( |
| sysroot: Union[str, 'sysroot_lib.Sysroot'], |
| packages: Optional[Union[List[str], List[package_info.PackageInfo]]] = None, |
| with_src_paths: bool = False |
| ) -> dependency_graph.DependencyGraph: |
| """Get the DependencyGraph for the sysroot only.""" |
| result = _get_raw_sysroot_depgraph(sysroot, packages=packages) |
| return _create_graph_from_deps(result.deps, sysroot, result.packages, |
| with_src_paths) |
| |
| |
| def get_build_target_dependency_graph( |
| sysroot: Union[str, 'sysroot_lib.Sysroot'], |
| packages: Optional[Union[List[str], List[package_info.PackageInfo]]] = None, |
| with_src_paths: bool = False |
| ) -> dependency_graph.DependencyGraph: |
| """Get the DependencyGraph for the sysroot and its bdeps.""" |
| result = _get_raw_build_target_depgraph(sysroot, packages=packages) |
| return _create_graph_from_deps(result.deps, sysroot, result.packages, |
| with_src_paths) |
| |
| |
| def _create_graph_from_deps( |
| deps: dict, sysroot: Union[str, 'sysroot_lib.Sysroot'], |
| packages: Union[List[str], List[package_info.PackageInfo]], |
| with_src_paths: bool |
| ) -> dependency_graph.DependencyGraph: |
| """Create DependencyGraph from the raw DepGraphGenerator deps. |
| |
| Translate the raw DepGraphGenerator deps into PackageNodes for a |
| DependencyGraph. This is extracted from the DependencyGraph class to make |
| testing the DependencyGraph class itself much easier. |
| """ |
| node_dict = collections.defaultdict(dict) |
| nodes = [] |
| src_paths = {} |
| if with_src_paths: |
| sysroot_path = getattr(sysroot, 'path', sysroot) |
| board = os.path.basename(sysroot_path) |
| src_paths = dependency_lib.get_source_path_mapping( |
| packages=deps.keys(), |
| sysroot_path=sysroot_path, |
| board=board) |
| |
| for pkg_cpv, pkg_data in deps.items(): |
| pkg_info = package_info.parse(pkg_cpv) |
| node = dependency_graph.PackageNode( |
| pkg_info, root=pkg_data['root'], src_paths=src_paths.get(pkg_info.cpvr)) |
| node_dict[pkg_info][pkg_data['root']] = node |
| nodes.append(node) |
| |
| for pkg_cpv, pkg_data in deps.items(): |
| pkg_info = package_info.parse(pkg_cpv) |
| pkg_node = node_dict[pkg_info][pkg_data['root']] |
| for dep_cpv, dep_data in pkg_data['deps'].items(): |
| dep_info = package_info.parse(dep_cpv) |
| dep_node = node_dict[dep_info][dep_data['root']] |
| pkg_node.add_dependency(dep_node) |
| |
| return dependency_graph.DependencyGraph( |
| nodes, sysroot=sysroot, root_packages=packages) |