# 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