# Copyright 2019 The ChromiumOS Authors
# 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"""

import collections
import copy
import logging
import os
import sys
import time
from typing import Collection, List, Optional, TYPE_CHECKING, Union

from chromite.lib import build_target_lib
from chromite.lib import constants
from chromite.lib import cros_build_lib
from chromite.lib import dependency_graph
from chromite.lib import dependency_lib
from chromite.lib.parser import package_info


try:
    # These aren't available outside the SDK.
    # pylint: disable=import-error
    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
    import portage
    from portage._global_updates import _global_updates
except ImportError:
    if cros_build_lib.IsInsideChroot():
        raise
# pylint: enable=import-error

if TYPE_CHECKING:
    from chromite.lib import sysroot_lib

PackageCollection = Union[Collection[str], Collection[package_info.PackageInfo]]


class DepGraphGenerator:
    """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) -> None:
        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 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="):
                pass
            elif arg == "--include-bdepend":
                self.include_bdepend = True
            else:
                # Not one of our options, so pass through to emerge.
                emerge_args.append(arg)

        return emerge_args

    def Initialize(self, args) -> None:
        """Initializer. Parses arguments and sets up portage state."""
        # We never want to see color output as it confuses parsing.
        emerge_args = ["--color=n"]

        # 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", build_target_lib.get_default_sysroot_path(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.
        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) -> None:
        """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.
        logging.debug(
            "Creating depgraph for %s with emerge options %s",
            packages,
            emerge_opts,
        )
        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)
        logging.debug("Checking if %s can use a prebuilt: %s", pkg_cpf, package)
        if package:
            logging.debug(
                "Checking whether the following package is a binpkg: %s",
                repr(package),
            )
            # pylint: disable=protected-access
            logging.debug("Package IUSE: %s", (package._metadata["IUSE"],))
            logging.debug("Package USE: %s", (package._metadata["USE"],))
            return package.type_name == "binary"

        return False

    def GenDependencyTree(self, with_roots: bool = False):
        """Get dependency tree info from emerge.

        Args:
            with_roots: When True, changes the output to have a list of packages
                for each cpv, and for the deps of each package. This allows more
                accurately reporting dependencies with the corresponding root
                information. This format is NOT compatible with other functions
                in this class, e.g. GenDependencyGraph.

        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...")

        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"]
        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)

                    dep = {
                        "action": action,
                        "deptypes": [str(x) for x in priorities],
                        "deps": {},
                        "root": child.root,
                    }
                    if with_roots:
                        deps.setdefault(cpv, []).append(dep)
                    else:
                        deps[cpv] = dep

            # We've built our list of deps, so we can add our package to the
            # tree.

            cpv = str(node.cpv)
            pkg_data = {
                "action": str(node.operation),
                "deps": deps,
                "root": node.root,
            }
            # 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:
                if with_roots:
                    deps_tree.setdefault(cpv, []).append(pkg_data)
                else:
                    deps_tree[cpv] = pkg_data

            # 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:
                if with_roots:
                    bdeps_tree.setdefault(cpv, []).append(pkg_data)
                else:
                    bdeps_tree[cpv] = pkg_data

        # 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="") -> None:
        """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) -> None:
            """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 = {"setup", "preinst", "postinst"}
            needed_dep_types = {
                "blocker",
                "buildtime",
                "buildtime_slot_op",
                "runtime",
                "runtime_slot_op",
            }
            ignored_dep_types = {"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) -> None:
                """Find cycles in cyclic dependencies starting at |pkg|.

                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() -> None:
            """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) -> None:
            """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() -> None:
            """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) -> None:
            """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) -> None:
        """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:
    """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) -> None:
        # 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) -> None:
    """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: PackageCollection, 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 needs to be set this way so parallel emerge parses it
        # correctly.
        f"--sysroot={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 build_target_lib.get_default_sysroot_path(build_target)


def _get_raw_sdk_depgraph(
    packages: Optional[PackageCollection] = 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 = build_target_lib.get_sdk_sysroot_path()
    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(with_roots=True)

    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[PackageCollection] = 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(with_roots=True)

    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[PackageCollection] = 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(with_roots=True)

    return DepgraphResult(deps=deps_tree, bdeps=bdeps_tree, packages=packages)


def get_sdk_dependency_graph(
    pkgs: Optional[PackageCollection] = 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,
        build_target_lib.get_sdk_sysroot_path(),
        result.packages,
        with_src_paths,
    )


def get_sysroot_dependency_graph(
    sysroot: Union[str, "sysroot_lib.Sysroot"],
    packages: Optional[PackageCollection] = 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[PackageCollection] = 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: PackageCollection,
    with_src_paths: bool,
) -> dependency_graph.DependencyGraph:
    """Create DependencyGraph from the raw DepGraphGenerator deps.

    Translate the raw DepGraphGenerator deps into PackageNodes for a
    DependencyGraph. DepGraphGenerator must be run with with_roots=True.
    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=list(deps.keys()), sysroot_path=sysroot_path, board=board
        )

    for pkg_cpv, pkg_instances in deps.items():
        pkg_info = package_info.parse(pkg_cpv)
        for pkg_data in pkg_instances:
            if pkg_data["action"] == "uninstall":
                # Skip uninstalls. Necessary for portage, but not for our
                # depgraph analysis right now.
                logging.debug("Skipping uninstall of %s", pkg_info)
                continue
            elif pkg_data["root"] in node_dict[pkg_info]:
                # In some cases packages get listed twice. "uninstall" should
                # be the only case, but log it for debugging just in case.
                logging.debug("Two instances of a package for the same root:")
                logging.debug(pkg_instances)

            node = dependency_graph.PackageNode(
                pkg_info, pkg_data["root"], src_paths.get(pkg_info.cpvr)
            )
            node_dict[pkg_info][pkg_data["root"]] = node
            nodes.append(node)

    for pkg_cpv, pkg_instances in deps.items():
        pkg_info = package_info.parse(pkg_cpv)
        for pkg_data in pkg_instances:
            if pkg_data["action"] == "uninstall":
                # Skip uninstalls.
                continue
            pkg_node = node_dict[pkg_info][pkg_data["root"]]
            for dep_cpv, pkg_deps in pkg_data["deps"].items():
                dep_info = package_info.parse(dep_cpv)
                for dep_data in pkg_deps:
                    if dep_data["action"] == "uninstall":
                        # Skip uninstalls.
                        continue
                    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
    )