path: root/lib/portage/dep/dep_check.py

# Copyright 2010-2024 Gentoo Authors
# Distributed under the terms of the GNU General Public License v2

__all__ = ["dep_check", "dep_eval", "dep_wordreduce", "dep_zapdeps"]

import collections
import itertools
import logging
import operator

import portage
from portage.dep import Atom, match_from_list, use_reduce
from portage.dep._dnf import (
    dnf_convert as _dnf_convert,
    contains_disjunction as _contains_disjunction,
)
from portage.exception import InvalidDependString, ParseError
from portage.localization import _
from portage.util import writemsg, writemsg_level
from portage.util.digraph import digraph
from portage.util.SlotObject import SlotObject
from portage.versions import vercmp


def _expand_new_virtuals(
    mysplit,
    edebug,
    mydbapi,
    mysettings,
    myroot="/",
    trees=None,
    use_mask=None,
    use_force=None,
    **kwargs,
):
    """
    In order to solve bug #141118, recursively expand new-style virtuals so
    as to collapse one or more levels of indirection, generating an expanded
    search space. In dep_zapdeps, new-style virtuals will be assigned
    zero cost regardless of whether or not they are currently installed. Virtual
    blockers are supported but only when the virtual expands to a single
    atom because it wouldn't necessarily make sense to block all the components
    of a compound virtual.  When more than one new-style virtual is matched,
    the matches are sorted from highest to lowest versions and the atom is
    expanded to || ( highest match ... lowest match ).

    The result is normalized in the same way as use_reduce, having a top-level
    conjunction, and no redundant nested lists.
    """
    newsplit = []
    mytrees = trees[myroot]
    portdb = mytrees["porttree"].dbapi
    pkg_use_enabled = mytrees.get("pkg_use_enabled")
    # Atoms are stored in the graph as (atom, id(atom)) tuples
    # since each atom is considered to be a unique entity. For
    # example, atoms that appear identical may behave differently
    # in USE matching, depending on their unevaluated form. Also,
    # specially generated virtual atoms may appear identical while
    # having different _orig_atom attributes.
    atom_graph = mytrees.get("atom_graph")
    parent = mytrees.get("parent")
    virt_parent = mytrees.get("virt_parent")
    graph_parent = None
    if parent is not None:
        if virt_parent is not None:
            graph_parent = virt_parent
            parent = virt_parent
        else:
            graph_parent = parent
    repoman = not mysettings.local_config
    if kwargs["use_binaries"]:
        portdb = trees[myroot]["bintree"].dbapi
    pprovideddict = mysettings.pprovideddict
    myuse = kwargs["myuse"]
    is_disjunction = mysplit and mysplit[0] == "||"
    for x in mysplit:
        if x == "||":
            newsplit.append(x)
            continue
        elif isinstance(x, list):
            assert x, f"Normalization error, empty conjunction found in {mysplit}"
            if is_disjunction:
                assert (
                    x[0] != "||"
                ), f"Normalization error, nested disjunction found in {mysplit}"
            else:
                assert (
                    x[0] == "||"
                ), f"Normalization error, nested conjunction found in {mysplit}"
            x_exp = _expand_new_virtuals(
                x,
                edebug,
                mydbapi,
                mysettings,
                myroot=myroot,
                trees=trees,
                use_mask=use_mask,
                use_force=use_force,
                **kwargs,
            )
            if is_disjunction:
                if len(x_exp) == 1:
                    x = x_exp[0]
                    if isinstance(x, list):
                        # Due to normalization, a conjunction must not be
                        # nested directly in another conjunction, so this
                        # must be a disjunction.
                        assert (
                            x and x[0] == "||"
                        ), f"Normalization error, nested conjunction found in {x_exp}"
                        newsplit.extend(x[1:])
                    else:
                        newsplit.append(x)
                else:
                    newsplit.append(x_exp)
            else:
                newsplit.extend(x_exp)
            continue

        if not isinstance(x, Atom):
            raise ParseError(_("invalid token: '%s'") % x)

        if repoman:
            x = x._eval_qa_conditionals(use_mask, use_force)

        mykey = x.cp
        if not mykey.startswith("virtual/"):
            newsplit.append(x)
            if atom_graph is not None:
                atom_graph.add((x, id(x)), graph_parent)
            continue

        if x.blocker:
            # Virtual blockers are no longer expanded here since
            # the un-expanded virtual atom is more useful for
            # maintaining a cache of blocker atoms.
            newsplit.append(x)
            if atom_graph is not None:
                atom_graph.add((x, id(x)), graph_parent)
            continue

        if repoman or not hasattr(portdb, "match_pkgs") or pkg_use_enabled is None:
            if portdb.cp_list(x.cp):
                newsplit.append(x)
            else:
                a = []
                myvartree = mytrees.get("vartree")
                if myvartree is not None:
                    mysettings._populate_treeVirtuals_if_needed(myvartree)
                mychoices = mysettings.getvirtuals().get(mykey, [])
                for y in mychoices:
                    a.append(Atom(x.replace(x.cp, y.cp, 1)))
                if not a:
                    newsplit.append(x)
                elif is_disjunction:
                    newsplit.extend(a)
                elif len(a) == 1:
                    newsplit.append(a[0])
                else:
                    newsplit.append(["||"] + a)
            continue

        pkgs = []
        # Ignore USE deps here, since otherwise we might not
        # get any matches. Choices with correct USE settings
        # will be preferred in dep_zapdeps().
        matches = portdb.match_pkgs(x.without_use)
        # Use descending order to prefer higher versions.
        matches.reverse()
        for pkg in matches:
            # only use new-style matches
            if pkg.cp.startswith("virtual/"):
                pkgs.append(pkg)

        mychoices = []
        if not pkgs and not portdb.cp_list(x.cp):
            myvartree = mytrees.get("vartree")
            if myvartree is not None:
                mysettings._populate_treeVirtuals_if_needed(myvartree)
            mychoices = mysettings.getvirtuals().get(mykey, [])

        if not (pkgs or mychoices):
            # This one couldn't be expanded as a new-style virtual.  Old-style
            # virtuals have already been expanded by dep_virtual, so this one
            # is unavailable and dep_zapdeps will identify it as such.  The
            # atom is not eliminated here since it may still represent a
            # dependency that needs to be satisfied.
            newsplit.append(x)
            if atom_graph is not None:
                atom_graph.add((x, id(x)), graph_parent)
            continue

        a = []
        for pkg in pkgs:
            virt_atom = "=" + pkg.cpv
            if x.unevaluated_atom.use:
                virt_atom += str(x.unevaluated_atom.use)
                virt_atom = Atom(virt_atom)
                if parent is None:
                    if myuse is None:
                        virt_atom = virt_atom.evaluate_conditionals(
                            mysettings.get("PORTAGE_USE", "").split()
                        )
                    else:
                        virt_atom = virt_atom.evaluate_conditionals(myuse)
                else:
                    virt_atom = virt_atom.evaluate_conditionals(pkg_use_enabled(parent))
            else:
                virt_atom = Atom(virt_atom)

            # Allow the depgraph to map this atom back to the
            # original, in order to avoid distortion in places
            # like display or conflict resolution code.
            virt_atom.__dict__["_orig_atom"] = x

            # According to GLEP 37, RDEPEND is the only dependency
            # type that is valid for new-style virtuals. Repoman
            # should enforce this.
            depstring = pkg._metadata["RDEPEND"]
            pkg_kwargs = kwargs.copy()
            pkg_kwargs["myuse"] = pkg_use_enabled(pkg)
            if edebug:
                writemsg_level(
                    _("Virtual Parent:      %s\n") % (pkg,),
                    noiselevel=-1,
                    level=logging.DEBUG,
                )
                writemsg_level(
                    _("Virtual Depstring:   %s\n") % (depstring,),
                    noiselevel=-1,
                    level=logging.DEBUG,
                )

            # Set EAPI used for validation in dep_check() recursion.
            mytrees["virt_parent"] = pkg

            try:
                mycheck = dep_check(
                    depstring,
                    mydbapi,
                    mysettings,
                    myroot=myroot,
                    trees=trees,
                    **pkg_kwargs,
                )
            finally:
                # Restore previous EAPI after recursion.
                if virt_parent is not None:
                    mytrees["virt_parent"] = virt_parent
                else:
                    del mytrees["virt_parent"]

            if not mycheck[0]:
                raise ParseError(f"{pkg}: {mycheck[1]} '{depstring}'")

            # Replace the original atom "x" with "virt_atom" which refers
            # to the specific version of the virtual whose deps we're
            # expanding. The virt_atom._orig_atom attribute is used
            # by depgraph to map virt_atom back to the original atom.
            # We specifically exclude the original atom "x" from the
            # the expanded output here, since otherwise it could trigger
            # incorrect dep_zapdeps behavior (see bug #597752).
            mycheck[1].append(virt_atom)
            a.append(mycheck[1])
            if atom_graph is not None:
                virt_atom_node = (virt_atom, id(virt_atom))
                atom_graph.add(virt_atom_node, graph_parent)
                atom_graph.add(pkg, virt_atom_node)
                atom_graph.add((x, id(x)), graph_parent)

        if not a and mychoices:
            # Check for a virtual package.provided match.
            for y in mychoices:
                new_atom = Atom(x.replace(x.cp, y.cp, 1))
                if match_from_list(new_atom, pprovideddict.get(new_atom.cp, [])):
                    a.append(new_atom)
                    if atom_graph is not None:
                        atom_graph.add((new_atom, id(new_atom)), graph_parent)

        if not a:
            newsplit.append(x)
            if atom_graph is not None:
                atom_graph.add((x, id(x)), graph_parent)
        elif is_disjunction:
            newsplit.extend(a)
        elif len(a) == 1:
            newsplit.extend(a[0])
        else:
            newsplit.append(["||"] + a)

    # For consistency with related functions like use_reduce, always
    # normalize the result to have a top-level conjunction.
    if is_disjunction:
        newsplit = [newsplit]

    return newsplit


def dep_eval(deplist):
    if not deplist:
        return 1
    if deplist[0] == "||":
        # or list; we just need one "1"
        for x in deplist[1:]:
            if isinstance(x, list):
                if dep_eval(x) == 1:
                    return 1
            elif x == 1:
                return 1
        # XXX: unless there's no available atoms in the list
        # in which case we need to assume that everything is
        # okay as some ebuilds are relying on an old bug.
        if len(deplist) == 1:
            return 1
        return 0
    for x in deplist:
        if isinstance(x, list):
            if dep_eval(x) == 0:
                return 0
        elif x == 0 or x == 2:
            return 0
    return 1


class _dep_choice(SlotObject):
    __slots__ = (
        "atoms",
        "slot_map",
        "cp_map",
        "all_available",
        "all_installed_slots",
        "new_slot_count",
        "want_update",
        "all_in_graph",
    )


def dep_zapdeps(
    unreduced, reduced, myroot, use_binaries=0, trees=None, minimize_slots=False
):
    """
    Takes an unreduced and reduced deplist and removes satisfied dependencies.
    Returned deplist contains steps that must be taken to satisfy dependencies.
    """
    if trees is None:
        trees = portage.db
    writemsg(f"ZapDeps -- {use_binaries}\n", 2)
    if not reduced or unreduced == ["||"] or dep_eval(reduced):
        return []

    if unreduced[0] != "||":
        unresolved = []
        for x, satisfied in zip(unreduced, reduced):
            if isinstance(x, list):
                unresolved += dep_zapdeps(
                    x,
                    satisfied,
                    myroot,
                    use_binaries=use_binaries,
                    trees=trees,
                    minimize_slots=minimize_slots,
                )
            elif not satisfied:
                unresolved.append(x)
        return unresolved

    # We're at a ( || atom ... ) type level and need to make a choice
    deps = unreduced[1:]
    satisfieds = reduced[1:]

    # Our preference order is for an the first item that:
    # a) contains all unmasked packages with the same key as installed packages
    # b) contains all unmasked packages
    # c) contains masked installed packages
    # d) is the first item

    preferred_in_graph = []
    preferred_installed = preferred_in_graph
    preferred_any_slot = preferred_in_graph
    preferred_non_installed = []
    unsat_use_in_graph = []
    unsat_use_installed = []
    unsat_use_non_installed = []
    other_installed = []
    other_installed_some = []
    other_installed_any_slot = []
    other = []

    # unsat_use_* must come after preferred_non_installed
    # for correct ordering in cases like || ( foo[a] foo[b] ).
    choice_bins = (
        preferred_in_graph,
        preferred_non_installed,
        unsat_use_in_graph,
        unsat_use_installed,
        unsat_use_non_installed,
        other_installed,
        other_installed_some,
        other_installed_any_slot,
        other,
    )

    # Alias the trees we'll be checking availability against
    parent = trees[myroot].get("parent")
    virt_parent = trees[myroot].get("virt_parent")
    priority = trees[myroot].get("priority")
    graph_db = trees[myroot].get("graph_db")
    graph = trees[myroot].get("graph")
    pkg_use_enabled = trees[myroot].get("pkg_use_enabled")
    graph_interface = trees[myroot].get("graph_interface")
    downgrade_probe = trees[myroot].get("downgrade_probe")
    circular_dependency = trees[myroot].get("circular_dependency")
    vardb = None
    if "vartree" in trees[myroot]:
        vardb = trees[myroot]["vartree"].dbapi
    if use_binaries:
        mydbapi = trees[myroot]["bintree"].dbapi
    else:
        mydbapi = trees[myroot]["porttree"].dbapi

    try:
        mydbapi_match_pkgs = mydbapi.match_pkgs
    except AttributeError:

        def mydbapi_match_pkgs(atom):
            return [mydbapi._pkg_str(cpv, atom.repo) for cpv in mydbapi.match(atom)]

    # Sort the deps into installed, not installed but already
    # in the graph and other, not installed and not in the graph
    # and other, with values of [[required_atom], availability]
    for x, satisfied in zip(deps, satisfieds):
        if isinstance(x, list):
            atoms = dep_zapdeps(
                x,
                satisfied,
                myroot,
                use_binaries=use_binaries,
                trees=trees,
                minimize_slots=minimize_slots,
            )
        else:
            atoms = [x]
        if vardb is None:
            # When called by repoman, we can simply return the first choice
            # because dep_eval() handles preference selection.
            return atoms

        all_available = True
        all_use_satisfied = True
        all_use_unmasked = True
        conflict_downgrade = False
        installed_downgrade = False
        slot_atoms = collections.defaultdict(list)
        slot_map = {}
        cp_map = {}
        for atom in atoms:
            if atom.blocker:
                continue

            # It's not a downgrade if parent is replacing child.
            replacing = (
                parent
                and graph_interface
                and graph_interface.will_replace_child(parent, myroot, atom)
            )
            # Ignore USE dependencies here since we don't want USE
            # settings to adversely affect || preference evaluation.
            avail_pkg = mydbapi_match_pkgs(atom.without_use)
            if not avail_pkg and replacing:
                avail_pkg = [replacing]
            if avail_pkg:
                avail_pkg = avail_pkg[-1]  # highest (ascending order)
                avail_slot = Atom(f"{atom.cp}:{avail_pkg.slot}")
            if not avail_pkg:
                all_available = False
                all_use_satisfied = False
                break

            if not replacing and graph_db is not None and downgrade_probe is not None:
                slot_matches = graph_db.match_pkgs(avail_slot)
                if (
                    len(slot_matches) > 1
                    and avail_pkg < slot_matches[-1]
                    and not downgrade_probe(avail_pkg)
                ):
                    # If a downgrade is not desirable, then avoid a
                    # choice that pulls in a lower version involved
                    # in a slot conflict (bug #531656).
                    conflict_downgrade = True

            if atom.use:
                avail_pkg_use = mydbapi_match_pkgs(atom)
                if not avail_pkg_use:
                    all_use_satisfied = False

                    if pkg_use_enabled is not None:
                        # Check which USE flags cause the match to fail,
                        # so we can prioritize choices that do not
                        # require changes to use.mask or use.force
                        # (see bug #515584).
                        violated_atom = atom.violated_conditionals(
                            pkg_use_enabled(avail_pkg), avail_pkg.iuse.is_valid_flag
                        )

                        # Note that violated_atom.use can be None here,
                        # since evaluation can collapse conditional USE
                        # deps that cause the match to fail due to
                        # missing IUSE (match uses atom.unevaluated_atom
                        # to detect such missing IUSE).
                        if violated_atom.use is not None:
                            for flag in violated_atom.use.enabled:
                                if flag in avail_pkg.use.mask:
                                    all_use_unmasked = False
                                    break
                            else:
                                for flag in violated_atom.use.disabled:
                                    if (
                                        flag in avail_pkg.use.force
                                        and flag not in avail_pkg.use.mask
                                    ):
                                        all_use_unmasked = False
                                        break
                else:
                    # highest (ascending order)
                    avail_pkg_use = avail_pkg_use[-1]
                    if avail_pkg_use != avail_pkg:
                        avail_pkg = avail_pkg_use
                    avail_slot = Atom(f"{atom.cp}:{avail_pkg.slot}")

            if not replacing and downgrade_probe is not None and graph is not None:
                highest_in_slot = mydbapi_match_pkgs(avail_slot)
                highest_in_slot = highest_in_slot[-1] if highest_in_slot else None
                if (
                    avail_pkg
                    and highest_in_slot
                    and avail_pkg < highest_in_slot
                    and not downgrade_probe(avail_pkg)
                    and (highest_in_slot.installed or highest_in_slot in graph)
                ):
                    installed_downgrade = True

            slot_map[avail_slot] = avail_pkg
            slot_atoms[avail_slot].append(atom)
            highest_cpv = cp_map.get(avail_pkg.cp)
            all_match_current = None
            all_match_previous = None
            if highest_cpv is not None and highest_cpv.slot == avail_pkg.slot:
                # If possible, make the package selection internally
                # consistent by choosing a package that satisfies all
                # atoms which match a package in the same slot. Later on,
                # the package version chosen here is used in the
                # has_upgrade/has_downgrade logic to prefer choices with
                # upgrades, and a package choice that is not internally
                # consistent will lead the has_upgrade/has_downgrade logic
                # to produce invalid results (see bug 600346).
                all_match_current = all(
                    a.match(avail_pkg) for a in slot_atoms[avail_slot]
                )
                all_match_previous = all(
                    a.match(highest_cpv) for a in slot_atoms[avail_slot]
                )
                if all_match_previous and not all_match_current:
                    continue

            current_higher = (
                highest_cpv is None
                or vercmp(avail_pkg.version, highest_cpv.version) > 0
            )

            if current_higher or (all_match_current and not all_match_previous):
                cp_map[avail_pkg.cp] = avail_pkg

        want_update = False
        if graph_interface is None or graph_interface.removal_action:
            new_slot_count = len(slot_map)
        else:
            new_slot_count = 0
            for slot_atom, avail_pkg in slot_map.items():
                if parent is not None and graph_interface.want_update_pkg(
                    parent, avail_pkg
                ):
                    want_update = True
                if not slot_atom.cp.startswith("virtual/") and not graph_db.match_pkgs(
                    slot_atom
                ):
                    new_slot_count += 1

        this_choice = _dep_choice(
            atoms=atoms,
            slot_map=slot_map,
            cp_map=cp_map,
            all_available=all_available,
            all_installed_slots=False,
            new_slot_count=new_slot_count,
            all_in_graph=False,
            want_update=want_update,
        )
        if all_available:
            # The "all installed" criterion is not version or slot specific.
            # If any version of a package is already in the graph then we
            # assume that it is preferred over other possible packages choices.
            all_installed = True
            for atom in {Atom(atom.cp) for atom in atoms if not atom.blocker}:
                # New-style virtuals have zero cost to install.
                if not vardb.match(atom) and not atom.startswith("virtual/"):
                    all_installed = False
                    break
            all_installed_slots = False
            if all_installed:
                all_installed_slots = True
                for slot_atom in slot_map:
                    # New-style virtuals have zero cost to install.
                    if not vardb.match(slot_atom) and not slot_atom.startswith(
                        "virtual/"
                    ):
                        all_installed_slots = False
                        break
            this_choice.all_installed_slots = all_installed_slots
            if graph_db is None:
                if all_use_satisfied:
                    if all_installed:
                        if all_installed_slots:
                            preferred_installed.append(this_choice)
                        else:
                            preferred_any_slot.append(this_choice)
                    else:
                        preferred_non_installed.append(this_choice)
                else:
                    if not all_use_unmasked:
                        other.append(this_choice)
                    elif all_installed_slots:
                        unsat_use_installed.append(this_choice)
                    else:
                        unsat_use_non_installed.append(this_choice)
            elif conflict_downgrade or installed_downgrade:
                other.append(this_choice)
            else:
                all_in_graph = True
                for atom in atoms:
                    # New-style virtuals have zero cost to install.
                    if atom.blocker or atom.cp.startswith("virtual/"):
                        continue
                    # We check if the matched package has actually been
                    # added to the digraph, in order to distinguish between
                    # those packages and installed packages that may need
                    # to be uninstalled in order to resolve blockers.
                    if not any(pkg in graph for pkg in graph_db.match_pkgs(atom)):
                        all_in_graph = False
                        break
                this_choice.all_in_graph = all_in_graph

                circular_atom = None
                if parent and parent.onlydeps:
                    # Check if the atom would result in a direct circular
                    # dependency and avoid that for --onlydeps arguments
                    # since it can defeat the purpose of --onlydeps.
                    # This check should only be used for --onlydeps
                    # arguments, since it can interfere with circular
                    # dependency backtracking choices, causing the test
                    # case for bug 756961 to fail.
                    cpv_slot_list = [parent]
                    for atom in atoms:
                        if atom.blocker:
                            continue
                        if vardb.match(atom):
                            # If the atom is satisfied by an installed
                            # version then it's not a circular dep.
                            continue
                        if atom.cp != parent.cp:
                            continue
                        if match_from_list(atom, cpv_slot_list):
                            circular_atom = atom
                            break
                if circular_atom is None and circular_dependency is not None:
                    for circular_child in itertools.chain(
                        circular_dependency.get(parent, []),
                        circular_dependency.get(virt_parent, []),
                    ):
                        for atom in atoms:
                            if not atom.blocker and atom.match(circular_child):
                                circular_atom = atom
                                break
                        if circular_atom is not None:
                            break

                if circular_atom is not None:
                    other.append(this_choice)
                else:
                    if all_use_satisfied:
                        if all_in_graph:
                            preferred_in_graph.append(this_choice)
                        elif all_installed:
                            if all_installed_slots:
                                preferred_installed.append(this_choice)
                            else:
                                preferred_any_slot.append(this_choice)
                        else:
                            preferred_non_installed.append(this_choice)
                    else:
                        if not all_use_unmasked:
                            other.append(this_choice)
                        elif all_in_graph:
                            unsat_use_in_graph.append(this_choice)
                        elif all_installed_slots:
                            unsat_use_installed.append(this_choice)
                        else:
                            unsat_use_non_installed.append(this_choice)
        else:
            all_installed = True
            some_installed = False
            for atom in atoms:
                if not atom.blocker:
                    if vardb.match(atom):
                        some_installed = True
                    else:
                        all_installed = False

            if all_installed:
                this_choice.all_installed_slots = True
                other_installed.append(this_choice)
            elif some_installed:
                other_installed_some.append(this_choice)

            # Use Atom(atom.cp) for a somewhat "fuzzy" match, since
            # the whole atom may be too specific. For example, see
            # bug #522652, where using the whole atom leads to an
            # unsatisfiable choice.
            elif any(vardb.match(Atom(atom.cp)) for atom in atoms if not atom.blocker):
                other_installed_any_slot.append(this_choice)
            else:
                other.append(this_choice)

    # Prefer choices which contain upgrades to higher slots. This helps
    # for deps such as || ( foo:1 foo:2 ), where we want to prefer the
    # atom which matches the higher version rather than the atom furthest
    # to the left. Sorting is done separately for each of choice_bins, so
    # as not to interfere with the ordering of the bins. Because of the
    # bin separation, the main function of this code is to allow
    # --depclean to remove old slots (rather than to pull in new slots).
    for choices in choice_bins:
        if len(choices) < 2:
            continue

        if minimize_slots:
            # Prefer choices having fewer new slots. When used with DNF form,
            # this can eliminate unnecessary packages that depclean would
            # ultimately eliminate (see bug 632026). Only use this behavior
            # when deemed necessary by the caller, since this will discard the
            # order specified in the ebuild, and the preferences specified
            # there can serve as a crucial sources of guidance (see bug 645002).

            # NOTE: Under some conditions, new_slot_count value may have some
            # variance from one calculation to the next because it depends on
            # the order that packages are added to the graph. This variance can
            # contribute to outcomes that appear to be random. Meanwhile,
            # the order specified in the ebuild is without variance, so it
            # does not have this problem.
            choices.sort(key=operator.attrgetter("new_slot_count"))

        for choice_1 in choices[1:]:
            cps = set(choice_1.cp_map)
            for choice_2 in choices:
                if choice_1 is choice_2:
                    # choice_1 will not be promoted, so move on
                    break
                if (
                    choice_1.all_installed_slots
                    and not choice_2.all_installed_slots
                    and not choice_2.want_update
                ):
                    # promote choice_1 in front of choice_2
                    choices.remove(choice_1)
                    index_2 = choices.index(choice_2)
                    choices.insert(index_2, choice_1)
                    break

                intersecting_cps = cps.intersection(choice_2.cp_map)
                has_upgrade = False
                has_downgrade = False
                for cp in intersecting_cps:
                    version_1 = choice_1.cp_map[cp]
                    version_2 = choice_2.cp_map[cp]
                    difference = vercmp(version_1.version, version_2.version)
                    if difference != 0:
                        if difference > 0:
                            has_upgrade = True
                        else:
                            has_downgrade = True

                if (
                    # Prefer upgrades.
                    (has_upgrade and not has_downgrade)
                    # Prefer choices where all packages have been pulled into
                    # the graph, except for choices that eliminate upgrades.
                    or (
                        choice_1.all_in_graph
                        and not choice_2.all_in_graph
                        and not (has_downgrade and not has_upgrade)
                    )
                ):
                    # promote choice_1 in front of choice_2
                    choices.remove(choice_1)
                    index_2 = choices.index(choice_2)
                    choices.insert(index_2, choice_1)
                    break

    for allow_masked in (False, True):
        for choices in choice_bins:
            for choice in choices:
                if choice.all_available or allow_masked:
                    return choice.atoms

    assert False  # This point should not be reachable


def dep_check(
    depstring,
    mydbapi,
    mysettings,
    use="yes",
    mode=None,
    myuse=None,
    use_cache=1,
    use_binaries=0,
    myroot=None,
    trees=None,
):
    """
    Takes a depend string, parses it, and selects atoms.
    The myroot parameter is unused (use mysettings['EROOT'] instead).
    """
    myroot = mysettings["EROOT"]
    edebug = mysettings.get("PORTAGE_DEBUG", None) == "1"
    # check_config_instance(mysettings)
    if trees is None:
        trees = globals()["db"]
    if use == "yes":
        if myuse is None:
            # default behavior
            myusesplit = mysettings["PORTAGE_USE"].split()
        else:
            myusesplit = myuse
            # We've been given useflags to use.
            # print "USE FLAGS PASSED IN."
            # print myuse
            # if "bindist" in myusesplit:
            # 	print "BINDIST is set!"
            # else:
            # 	print "BINDIST NOT set."
    else:
        # we are being run by autouse(), don't consult USE vars yet.
        # WE ALSO CANNOT USE SETTINGS
        myusesplit = []

    mymasks = set()
    useforce = set()
    if use == "all":
        # This is only for repoman, in order to constrain the use_reduce
        # matchall behavior to account for profile use.mask/force. The
        # ARCH/archlist code here may be redundant, since the profile
        # really should be handling ARCH masking/forcing itself.
        arch = mysettings.get("ARCH")
        mymasks.update(mysettings.usemask)
        mymasks.update(mysettings.archlist())
        if arch:
            mymasks.discard(arch)
            useforce.add(arch)
        useforce.update(mysettings.useforce)
        useforce.difference_update(mymasks)

    # eapi code borrowed from _expand_new_virtuals()
    mytrees = trees[myroot]
    parent = mytrees.get("parent")
    virt_parent = mytrees.get("virt_parent")
    current_parent = None
    eapi = None
    if parent is not None:
        if virt_parent is not None:
            current_parent = virt_parent
        else:
            current_parent = parent

    if current_parent is not None:
        # Don't pass the eapi argument to use_reduce() for installed packages
        # since previous validation will have already marked them as invalid
        # when necessary and now we're more interested in evaluating
        # dependencies so that things like --depclean work as well as possible
        # in spite of partial invalidity.
        if not current_parent.installed:
            eapi = current_parent.eapi

    if isinstance(depstring, list):
        mysplit = depstring
    else:
        try:
            mysplit = use_reduce(
                depstring,
                uselist=myusesplit,
                masklist=mymasks,
                matchall=(use == "all"),
                excludeall=useforce,
                opconvert=True,
                token_class=Atom,
                eapi=eapi,
            )
        except InvalidDependString as e:
            return [0, f"{e}"]

    if mysplit == []:
        # dependencies were reduced to nothing
        return [1, []]

    # Recursively expand new-style virtuals so as to
    # collapse one or more levels of indirection.
    try:
        mysplit = _expand_new_virtuals(
            mysplit,
            edebug,
            mydbapi,
            mysettings,
            use=use,
            mode=mode,
            myuse=myuse,
            use_force=useforce,
            use_mask=mymasks,
            use_cache=use_cache,
            use_binaries=use_binaries,
            myroot=myroot,
            trees=trees,
        )
    except ParseError as e:
        return [0, f"{e}"]

    dnf = False
    if mysettings.local_config:  # if not repoman
        orig_split = mysplit
        mysplit = _overlap_dnf(mysplit)
        dnf = mysplit is not orig_split

    mysplit2 = dep_wordreduce(mysplit, mysettings, mydbapi, mode, use_cache=use_cache)
    if mysplit2 is None:
        return [0, _("Invalid token")]

    writemsg("\n\n\n", 1)
    writemsg(f"mysplit:  {mysplit}\n", 1)
    writemsg(f"mysplit2: {mysplit2}\n", 1)

    selected_atoms = dep_zapdeps(
        mysplit,
        mysplit2,
        myroot,
        use_binaries=use_binaries,
        trees=trees,
        minimize_slots=dnf,
    )

    return [1, selected_atoms]


def _overlap_dnf(dep_struct):
    """
    Combine overlapping || groups using disjunctive normal form (DNF), in
    order to minimize the number of packages chosen to satisfy cases like
    "|| ( foo bar ) || ( bar baz )" as in bug #632026. Non-overlapping
    groups are excluded from the conversion, since DNF leads to exponential
    explosion of the formula. Duplicate || groups are eliminated since
    DNF expansion of duplicates is nonsensical (bug #891137).

    When dep_struct does not contain any overlapping groups, no DNF
    conversion will be performed, and dep_struct will be returned as-is.
    Callers can detect this case by checking if the returned object has
    the same identity as dep_struct. If the identity is different, then
    DNF conversion was performed.
    """
    if not _contains_disjunction(dep_struct):
        return dep_struct

    # map atom.cp to disjunctions
    cp_map = collections.defaultdict(list)
    # graph atom.cp, with edges connecting atoms in the same disjunction
    overlap_graph = digraph()
    # map id(disjunction) to index in dep_struct, for deterministic output
    order_map = {}
    order_key = lambda x: order_map[id(x)]
    result = []
    for i, x in enumerate(dep_struct):
        if isinstance(x, list):
            assert (
                x and x[0] == "||"
            ), f"Normalization error, nested conjunction found in {dep_struct}"
            order_map[id(x)] = i
            prev_cp = None
            for atom in _iter_flatten(x):
                if isinstance(atom, Atom) and not atom.blocker:
                    cp_map[atom.cp].append(x)
                    overlap_graph.add(atom.cp, parent=prev_cp)
                    prev_cp = atom.cp
            if prev_cp is None:  # only contains blockers
                result.append(x)
        else:
            result.append(x)

    # group together disjunctions having atom.cp overlap
    traversed = set()
    overlap = False
    for cp in overlap_graph:
        if cp in traversed:
            continue
        disjunctions = {}
        stack = [cp]
        while stack:
            cp = stack.pop()
            traversed.add(cp)
            for x in cp_map[cp]:
                disjunctions[id(x)] = x
            for other_cp in itertools.chain(
                overlap_graph.child_nodes(cp), overlap_graph.parent_nodes(cp)
            ):
                if other_cp not in traversed:
                    stack.append(other_cp)

        if len(disjunctions) > 1:
            overlap = True
            # convert overlapping disjunctions to DNF
            dedup_set = set()
            unique_disjunctions = []
            for x in sorted(disjunctions.values(), key=order_key):
                dep_repr = portage.dep.paren_enclose(x, opconvert=True)
                if dep_repr not in dedup_set:
                    dedup_set.add(dep_repr)
                    unique_disjunctions.append(x)
            if len(unique_disjunctions) > 1:
                result.extend(_dnf_convert(unique_disjunctions))
            else:
                result.extend(unique_disjunctions)
        else:
            # pass through non-overlapping disjunctions
            result.append(disjunctions.popitem()[1])

    return result if overlap else dep_struct


def _iter_flatten(dep_struct):
    """
    Yield nested elements of dep_struct.
    """
    for x in dep_struct:
        if isinstance(x, list):
            for x in _iter_flatten(x):
                yield x
        else:
            yield x


def dep_wordreduce(mydeplist, mysettings, mydbapi, mode, use_cache=1):
    "Reduces the deplist to ones and zeros"
    deplist = mydeplist[:]
    for mypos, token in enumerate(deplist):
        if isinstance(deplist[mypos], list):
            # recurse
            deplist[mypos] = dep_wordreduce(
                deplist[mypos], mysettings, mydbapi, mode, use_cache=use_cache
            )
        elif deplist[mypos] == "||":
            pass
        elif token[:1] == "!":
            deplist[mypos] = False
        else:
            mykey = deplist[mypos].cp
            if (
                mysettings
                and mykey in mysettings.pprovideddict
                and match_from_list(deplist[mypos], mysettings.pprovideddict[mykey])
            ):
                deplist[mypos] = True
            elif mydbapi is None:
                # Assume nothing is satisfied.  This forces dep_zapdeps to
                # return all of deps the deps that have been selected
                # (excluding those satisfied by package.provided).
                deplist[mypos] = False
            else:
                if mode:
                    x = mydbapi.xmatch(mode, deplist[mypos])
                    if mode.startswith("minimum-"):
                        mydep = []
                        if x:
                            mydep.append(x)
                    else:
                        mydep = x
                else:
                    mydep = mydbapi.match(deplist[mypos], use_cache=use_cache)
                if mydep is not None:
                    tmp = len(mydep) >= 1
                    if deplist[mypos][0] == "!":
                        tmp = False
                    deplist[mypos] = tmp
                else:
                    # encountered invalid string
                    return None
    return deplist