pym/portage/dep/dep_check.py

   1 # Copyright 2010-2011 Gentoo Foundation
   2 # Distributed under the terms of the GNU General Public License v2
   3
   4 __all__ = ['dep_check', 'dep_eval', 'dep_wordreduce', 'dep_zapdeps']
   5
   6 import logging
   7
   8 import portage
   9 from portage.dep import Atom, match_from_list, use_reduce
  10 from portage.exception import InvalidDependString, ParseError
  11 from portage.localization import _
  12 from portage.util import writemsg, writemsg_level
  13 from portage.versions import catpkgsplit, cpv_getkey, pkgcmp
  14
  15 def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
  16         trees=None, use_mask=None, use_force=None, **kwargs):
  17         """
  18         In order to solve bug #141118, recursively expand new-style virtuals so
  19         as to collapse one or more levels of indirection, generating an expanded
  20         search space. In dep_zapdeps, new-style virtuals will be assigned
  21         zero cost regardless of whether or not they are currently installed. Virtual
  22         blockers are supported but only when the virtual expands to a single
  23         atom because it wouldn't necessarily make sense to block all the components
  24         of a compound virtual.  When more than one new-style virtual is matched,
  25         the matches are sorted from highest to lowest versions and the atom is
  26         expanded to || ( highest match ... lowest match )."""
  27         newsplit = []
  28         mytrees = trees[myroot]
  29         portdb = mytrees["porttree"].dbapi
  30         pkg_use_enabled = mytrees.get("pkg_use_enabled")
  31         # Atoms are stored in the graph as (atom, id(atom)) tuples
  32         # since each atom is considered to be a unique entity. For
  33         # example, atoms that appear identical may behave differently
  34         # in USE matching, depending on their unevaluated form. Also,
  35         # specially generated virtual atoms may appear identical while
  36         # having different _orig_atom attributes.
  37         atom_graph = mytrees.get("atom_graph")
  38         parent = mytrees.get("parent")
  39         virt_parent = mytrees.get("virt_parent")
  40         graph_parent = None
  41         eapi = None
  42         if parent is not None:
  43                 if virt_parent is not None:
  44                         graph_parent = virt_parent
  45                         parent = virt_parent
  46                 else:
  47                         graph_parent = parent
  48                 eapi = parent.metadata["EAPI"]
  49         repoman = not mysettings.local_config
  50         if kwargs["use_binaries"]:
  51                 portdb = trees[myroot]["bintree"].dbapi
  52         myvirtuals = mysettings.getvirtuals()
  53         pprovideddict = mysettings.pprovideddict
  54         myuse = kwargs["myuse"]
  55         for x in mysplit:
  56                 if x == "||":
  57                         newsplit.append(x)
  58                         continue
  59                 elif isinstance(x, list):
  60                         newsplit.append(_expand_new_virtuals(x, edebug, mydbapi,
  61                                 mysettings, myroot=myroot, trees=trees, use_mask=use_mask,
  62                                 use_force=use_force, **kwargs))
  63                         continue
  64
  65                 if not isinstance(x, Atom):
  66                         raise ParseError(
  67                                 _("invalid token: '%s'") % x)
  68
  69                 if repoman:
  70                         x = x._eval_qa_conditionals(use_mask, use_force)
  71
  72                 mykey = x.cp
  73                 if not mykey.startswith("virtual/"):
  74                         newsplit.append(x)
  75                         if atom_graph is not None:
  76                                 atom_graph.add((x, id(x)), graph_parent)
  77                         continue
  78                 mychoices = myvirtuals.get(mykey, [])
  79                 if x.blocker:
  80                         # Virtual blockers are no longer expanded here since
  81                         # the un-expanded virtual atom is more useful for
  82                         # maintaining a cache of blocker atoms.
  83                         newsplit.append(x)
  84                         if atom_graph is not None:
  85                                 atom_graph.add((x, id(x)), graph_parent)
  86                         continue
  87
  88                 if repoman or not hasattr(portdb, 'match_pkgs') or \
  89                         pkg_use_enabled is None:
  90                         if portdb.cp_list(x.cp):
  91                                 newsplit.append(x)
  92                         else:
  93                                 # TODO: Add PROVIDE check for repoman.
  94                                 a = []
  95                                 for y in mychoices:
  96                                         a.append(Atom(x.replace(x.cp, y.cp, 1)))
  97                                 if not a:
  98                                         newsplit.append(x)
  99                                 elif len(a) == 1:
 100                                         newsplit.append(a[0])
 101                                 else:
 102                                         newsplit.append(['||'] + a)
 103                         continue
 104
 105                 pkgs = []
 106                 # Ignore USE deps here, since otherwise we might not
 107                 # get any matches. Choices with correct USE settings
 108                 # will be preferred in dep_zapdeps().
 109                 matches = portdb.match_pkgs(x.without_use)
 110                 # Use descending order to prefer higher versions.
 111                 matches.reverse()
 112                 for pkg in matches:
 113                         # only use new-style matches
 114                         if pkg.cp.startswith("virtual/"):
 115                                 pkgs.append(pkg)
 116                 if not (pkgs or mychoices):
 117                         # This one couldn't be expanded as a new-style virtual.  Old-style
 118                         # virtuals have already been expanded by dep_virtual, so this one
 119                         # is unavailable and dep_zapdeps will identify it as such.  The
 120                         # atom is not eliminated here since it may still represent a
 121                         # dependency that needs to be satisfied.
 122                         newsplit.append(x)
 123                         if atom_graph is not None:
 124                                 atom_graph.add((x, id(x)), graph_parent)
 125                         continue
 126
 127                 a = []
 128                 for pkg in pkgs:
 129                         virt_atom = '=' + pkg.cpv
 130                         if x.unevaluated_atom.use:
 131                                 virt_atom += str(x.unevaluated_atom.use)
 132                                 virt_atom = Atom(virt_atom)
 133                                 if parent is None:
 134                                         if myuse is None:
 135                                                 virt_atom = virt_atom.evaluate_conditionals(
 136                                                         mysettings.get("PORTAGE_USE", "").split())
 137                                         else:
 138                                                 virt_atom = virt_atom.evaluate_conditionals(myuse)
 139                                 else:
 140                                         virt_atom = virt_atom.evaluate_conditionals(
 141                                                 pkg_use_enabled(parent))
 142                         else:
 143                                 virt_atom = Atom(virt_atom)
 144
 145                         # Allow the depgraph to map this atom back to the
 146                         # original, in order to avoid distortion in places
 147                         # like display or conflict resolution code.
 148                         virt_atom.__dict__['_orig_atom'] = x
 149
 150                         # According to GLEP 37, RDEPEND is the only dependency
 151                         # type that is valid for new-style virtuals. Repoman
 152                         # should enforce this.
 153                         depstring = pkg.metadata['RDEPEND']
 154                         pkg_kwargs = kwargs.copy()
 155                         pkg_kwargs["myuse"] = pkg_use_enabled(pkg)
 156                         if edebug:
 157                                 writemsg_level(_("Virtual Parent:      %s\n") \
 158                                         % (pkg,), noiselevel=-1, level=logging.DEBUG)
 159                                 writemsg_level(_("Virtual Depstring:   %s\n") \
 160                                         % (depstring,), noiselevel=-1, level=logging.DEBUG)
 161
 162                         # Set EAPI used for validation in dep_check() recursion.
 163                         mytrees["virt_parent"] = pkg
 164
 165                         try:
 166                                 mycheck = dep_check(depstring, mydbapi, mysettings,
 167                                         myroot=myroot, trees=trees, **pkg_kwargs)
 168                         finally:
 169                                 # Restore previous EAPI after recursion.
 170                                 if virt_parent is not None:
 171                                         mytrees["virt_parent"] = virt_parent
 172                                 else:
 173                                         del mytrees["virt_parent"]
 174
 175                         if not mycheck[0]:
 176                                 raise ParseError(
 177                                         "%s: %s '%s'" % (pkg, mycheck[1], depstring))
 178
 179                         # pull in the new-style virtual
 180                         mycheck[1].append(virt_atom)
 181                         a.append(mycheck[1])
 182                         if atom_graph is not None:
 183                                 virt_atom_node = (virt_atom, id(virt_atom))
 184                                 atom_graph.add(virt_atom_node, graph_parent)
 185                                 atom_graph.add(pkg, virt_atom_node)
 186                 # Plain old-style virtuals.  New-style virtuals are preferred.
 187                 if not pkgs:
 188                                 for y in mychoices:
 189                                         new_atom = Atom(x.replace(x.cp, y.cp, 1))
 190                                         matches = portdb.match(new_atom)
 191                                         # portdb is an instance of depgraph._dep_check_composite_db, so
 192                                         # USE conditionals are already evaluated.
 193                                         if matches and mykey in \
 194                                                 portdb.aux_get(matches[-1], ['PROVIDE'])[0].split():
 195                                                 a.append(new_atom)
 196                                                 if atom_graph is not None:
 197                                                         atom_graph.add((new_atom, id(new_atom)),
 198                                                                 graph_parent)
 199
 200                 if not a and mychoices:
 201                         # Check for a virtual package.provided match.
 202                         for y in mychoices:
 203                                 new_atom = Atom(x.replace(x.cp, y.cp, 1))
 204                                 if match_from_list(new_atom,
 205                                         pprovideddict.get(new_atom.cp, [])):
 206                                         a.append(new_atom)
 207                                         if atom_graph is not None:
 208                                                 atom_graph.add((new_atom, id(new_atom)), graph_parent)
 209
 210                 if not a:
 211                         newsplit.append(x)
 212                         if atom_graph is not None:
 213                                 atom_graph.add((x, id(x)), graph_parent)
 214                 elif len(a) == 1:
 215                         newsplit.append(a[0])
 216                 else:
 217                         newsplit.append(['||'] + a)
 218
 219         return newsplit
 220
 221 def dep_eval(deplist):
 222         if not deplist:
 223                 return 1
 224         if deplist[0]=="||":
 225                 #or list; we just need one "1"
 226                 for x in deplist[1:]:
 227                         if isinstance(x, list):
 228                                 if dep_eval(x)==1:
 229                                         return 1
 230                         elif x==1:
 231                                         return 1
 232                 #XXX: unless there's no available atoms in the list
 233                 #in which case we need to assume that everything is
 234                 #okay as some ebuilds are relying on an old bug.
 235                 if len(deplist) == 1:
 236                         return 1
 237                 return 0
 238         else:
 239                 for x in deplist:
 240                         if isinstance(x, list):
 241                                 if dep_eval(x)==0:
 242                                         return 0
 243                         elif x==0 or x==2:
 244                                 return 0
 245                 return 1
 246
 247 def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):
 248         """
 249         Takes an unreduced and reduced deplist and removes satisfied dependencies.
 250         Returned deplist contains steps that must be taken to satisfy dependencies.
 251         """
 252         if trees is None:
 253                 trees = portage.db
 254         writemsg("ZapDeps -- %s\n" % (use_binaries), 2)
 255         if not reduced or unreduced == ["||"] or dep_eval(reduced):
 256                 return []
 257
 258         if unreduced[0] != "||":
 259                 unresolved = []
 260                 for x, satisfied in zip(unreduced, reduced):
 261                         if isinstance(x, list):
 262                                 unresolved += dep_zapdeps(x, satisfied, myroot,
 263                                         use_binaries=use_binaries, trees=trees)
 264                         elif not satisfied:
 265                                 unresolved.append(x)
 266                 return unresolved
 267
 268         # We're at a ( || atom ... ) type level and need to make a choice
 269         deps = unreduced[1:]
 270         satisfieds = reduced[1:]
 271
 272         # Our preference order is for an the first item that:
 273         # a) contains all unmasked packages with the same key as installed packages
 274         # b) contains all unmasked packages
 275         # c) contains masked installed packages
 276         # d) is the first item
 277
 278         preferred_installed = []
 279         preferred_in_graph = []
 280         preferred_any_slot = []
 281         preferred_non_installed = []
 282         unsat_use_in_graph = []
 283         unsat_use_installed = []
 284         unsat_use_non_installed = []
 285         other_installed = []
 286         other_installed_some = []
 287         other = []
 288
 289         # unsat_use_* must come after preferred_non_installed
 290         # for correct ordering in cases like || ( foo[a] foo[b] ).
 291         choice_bins = (
 292                 preferred_in_graph,
 293                 preferred_installed,
 294                 preferred_any_slot,
 295                 preferred_non_installed,
 296                 unsat_use_in_graph,
 297                 unsat_use_installed,
 298                 unsat_use_non_installed,
 299                 other_installed,
 300                 other_installed_some,
 301                 other,
 302         )
 303
 304         # Alias the trees we'll be checking availability against
 305         parent   = trees[myroot].get("parent")
 306         priority = trees[myroot].get("priority")
 307         graph_db = trees[myroot].get("graph_db")
 308         vardb = None
 309         if "vartree" in trees[myroot]:
 310                 vardb = trees[myroot]["vartree"].dbapi
 311         if use_binaries:
 312                 mydbapi = trees[myroot]["bintree"].dbapi
 313         else:
 314                 mydbapi = trees[myroot]["porttree"].dbapi
 315
 316         # Sort the deps into installed, not installed but already
 317         # in the graph and other, not installed and not in the graph
 318         # and other, with values of [[required_atom], availablility]
 319         for x, satisfied in zip(deps, satisfieds):
 320                 if isinstance(x, list):
 321                         atoms = dep_zapdeps(x, satisfied, myroot,
 322                                 use_binaries=use_binaries, trees=trees)
 323                 else:
 324                         atoms = [x]
 325                 if vardb is None:
 326                         # When called by repoman, we can simply return the first choice
 327                         # because dep_eval() handles preference selection.
 328                         return atoms
 329
 330                 all_available = True
 331                 all_use_satisfied = True
 332                 slot_map = {}
 333                 cp_map = {}
 334                 for atom in atoms:
 335                         if atom.blocker:
 336                                 continue
 337                         # Ignore USE dependencies here since we don't want USE
 338                         # settings to adversely affect || preference evaluation.
 339                         avail_pkg = mydbapi.match(atom.without_use)
 340                         if avail_pkg:
 341                                 avail_pkg = avail_pkg[-1] # highest (ascending order)
 342                                 avail_slot = Atom("%s:%s" % (atom.cp,
 343                                         mydbapi.aux_get(avail_pkg, ["SLOT"])[0]))
 344                         if not avail_pkg:
 345                                 all_available = False
 346                                 all_use_satisfied = False
 347                                 break
 348
 349                         if atom.use:
 350                                 avail_pkg_use = mydbapi.match(atom)
 351                                 if not avail_pkg_use:
 352                                         all_use_satisfied = False
 353                                 else:
 354                                         # highest (ascending order)
 355                                         avail_pkg_use = avail_pkg_use[-1]
 356                                         if avail_pkg_use != avail_pkg:
 357                                                 avail_pkg = avail_pkg_use
 358                                                 avail_slot = Atom("%s:%s" % (atom.cp,
 359                                                         mydbapi.aux_get(avail_pkg, ["SLOT"])[0]))
 360
 361                         slot_map[avail_slot] = avail_pkg
 362                         pkg_cp = cpv_getkey(avail_pkg)
 363                         highest_cpv = cp_map.get(pkg_cp)
 364                         if highest_cpv is None or \
 365                                 pkgcmp(catpkgsplit(avail_pkg)[1:],
 366                                 catpkgsplit(highest_cpv)[1:]) > 0:
 367                                 cp_map[pkg_cp] = avail_pkg
 368
 369                 this_choice = (atoms, slot_map, cp_map, all_available)
 370                 if all_available:
 371                         # The "all installed" criterion is not version or slot specific.
 372                         # If any version of a package is already in the graph then we
 373                         # assume that it is preferred over other possible packages choices.
 374                         all_installed = True
 375                         for atom in set(Atom(atom.cp) for atom in atoms \
 376                                 if not atom.blocker):
 377                                 # New-style virtuals have zero cost to install.
 378                                 if not vardb.match(atom) and not atom.startswith("virtual/"):
 379                                         all_installed = False
 380                                         break
 381                         all_installed_slots = False
 382                         if all_installed:
 383                                 all_installed_slots = True
 384                                 for slot_atom in slot_map:
 385                                         # New-style virtuals have zero cost to install.
 386                                         if not vardb.match(slot_atom) and \
 387                                                 not slot_atom.startswith("virtual/"):
 388                                                 all_installed_slots = False
 389                                                 break
 390                         if graph_db is None:
 391                                 if all_use_satisfied:
 392                                         if all_installed:
 393                                                 if all_installed_slots:
 394                                                         preferred_installed.append(this_choice)
 395                                                 else:
 396                                                         preferred_any_slot.append(this_choice)
 397                                         else:
 398                                                 preferred_non_installed.append(this_choice)
 399                                 else:
 400                                         if all_installed_slots:
 401                                                 unsat_use_installed.append(this_choice)
 402                                         else:
 403                                                 unsat_use_non_installed.append(this_choice)
 404                         else:
 405                                 all_in_graph = True
 406                                 for slot_atom in slot_map:
 407                                         # New-style virtuals have zero cost to install.
 408                                         if not graph_db.match(slot_atom) and \
 409                                                 not slot_atom.startswith("virtual/"):
 410                                                 all_in_graph = False
 411                                                 break
 412                                 circular_atom = None
 413                                 if all_in_graph:
 414                                         if parent is None or priority is None:
 415                                                 pass
 416                                         elif priority.buildtime and \
 417                                                 not (priority.satisfied or priority.optional):
 418                                                 # Check if the atom would result in a direct circular
 419                                                 # dependency and try to avoid that if it seems likely
 420                                                 # to be unresolvable. This is only relevant for
 421                                                 # buildtime deps that aren't already satisfied by an
 422                                                 # installed package.
 423                                                 cpv_slot_list = [parent]
 424                                                 for atom in atoms:
 425                                                         if atom.blocker:
 426                                                                 continue
 427                                                         if vardb.match(atom):
 428                                                                 # If the atom is satisfied by an installed
 429                                                                 # version then it's not a circular dep.
 430                                                                 continue
 431                                                         if atom.cp != parent.cp:
 432                                                                 continue
 433                                                         if match_from_list(atom, cpv_slot_list):
 434                                                                 circular_atom = atom
 435                                                                 break
 436                                 if circular_atom is not None:
 437                                         other.append(this_choice)
 438                                 else:
 439                                         if all_use_satisfied:
 440                                                 if all_in_graph:
 441                                                         preferred_in_graph.append(this_choice)
 442                                                 elif all_installed:
 443                                                         if all_installed_slots:
 444                                                                 preferred_installed.append(this_choice)
 445                                                         else:
 446                                                                 preferred_any_slot.append(this_choice)
 447                                                 else:
 448                                                         preferred_non_installed.append(this_choice)
 449                                         else:
 450                                                 if all_in_graph:
 451                                                         unsat_use_in_graph.append(this_choice)
 452                                                 elif all_installed_slots:
 453                                                         unsat_use_installed.append(this_choice)
 454                                                 else:
 455                                                         unsat_use_non_installed.append(this_choice)
 456                 else:
 457                         all_installed = True
 458                         some_installed = False
 459                         for atom in atoms:
 460                                 if not atom.blocker:
 461                                         if vardb.match(atom):
 462                                                 some_installed = True
 463                                         else:
 464                                                 all_installed = False
 465
 466                         if all_installed:
 467                                 other_installed.append(this_choice)
 468                         elif some_installed:
 469                                 other_installed_some.append(this_choice)
 470                         else:
 471                                 other.append(this_choice)
 472
 473         # Prefer choices which contain upgrades to higher slots. This helps
 474         # for deps such as || ( foo:1 foo:2 ), where we want to prefer the
 475         # atom which matches the higher version rather than the atom furthest
 476         # to the left. Sorting is done separately for each of choice_bins, so
 477         # as not to interfere with the ordering of the bins. Because of the
 478         # bin separation, the main function of this code is to allow
 479         # --depclean to remove old slots (rather than to pull in new slots).
 480         for choices in choice_bins:
 481                 if len(choices) < 2:
 482                         continue
 483                 for choice_1 in choices[1:]:
 484                         atoms_1, slot_map_1, cp_map_1, all_available_1 = choice_1
 485                         cps = set(cp_map_1)
 486                         for choice_2 in choices:
 487                                 if choice_1 is choice_2:
 488                                         # choice_1 will not be promoted, so move on
 489                                         break
 490                                 atoms_2, slot_map_2, cp_map_2, all_available_2 = choice_2
 491                                 intersecting_cps = cps.intersection(cp_map_2)
 492                                 if not intersecting_cps:
 493                                         continue
 494                                 has_upgrade = False
 495                                 has_downgrade = False
 496                                 for cp in intersecting_cps:
 497                                         version_1 = cp_map_1[cp]
 498                                         version_2 = cp_map_2[cp]
 499                                         difference = pkgcmp(catpkgsplit(version_1)[1:],
 500                                                 catpkgsplit(version_2)[1:])
 501                                         if difference != 0:
 502                                                 if difference > 0:
 503                                                         has_upgrade = True
 504                                                 else:
 505                                                         has_downgrade = True
 506                                                         break
 507                                 if has_upgrade and not has_downgrade:
 508                                         # promote choice_1 in front of choice_2
 509                                         choices.remove(choice_1)
 510                                         index_2 = choices.index(choice_2)
 511                                         choices.insert(index_2, choice_1)
 512                                         break
 513
 514         for allow_masked in (False, True):
 515                 for choices in choice_bins:
 516                         for atoms, slot_map, cp_map, all_available in choices:
 517                                 if all_available or allow_masked:
 518                                         return atoms
 519
 520         assert(False) # This point should not be reachable
 521
 522 def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,
 523         use_cache=1, use_binaries=0, myroot="/", trees=None):
 524         """Takes a depend string and parses the condition."""
 525         edebug = mysettings.get("PORTAGE_DEBUG", None) == "1"
 526         #check_config_instance(mysettings)
 527         if trees is None:
 528                 trees = globals()["db"]
 529         if use=="yes":
 530                 if myuse is None:
 531                         #default behavior
 532                         myusesplit = mysettings["PORTAGE_USE"].split()
 533                 else:
 534                         myusesplit = myuse
 535                         # We've been given useflags to use.
 536                         #print "USE FLAGS PASSED IN."
 537                         #print myuse
 538                         #if "bindist" in myusesplit:
 539                         #       print "BINDIST is set!"
 540                         #else:
 541                         #       print "BINDIST NOT set."
 542         else:
 543                 #we are being run by autouse(), don't consult USE vars yet.
 544                 # WE ALSO CANNOT USE SETTINGS
 545                 myusesplit=[]
 546
 547         mymasks = set()
 548         useforce = set()
 549         useforce.add(mysettings["ARCH"])
 550         if use == "all":
 551                 # This masking/forcing is only for repoman.  In other cases, relevant
 552                 # masking/forcing should have already been applied via
 553                 # config.regenerate().  Also, binary or installed packages may have
 554                 # been built with flags that are now masked, and it would be
 555                 # inconsistent to mask them now.  Additionally, myuse may consist of
 556                 # flags from a parent package that is being merged to a $ROOT that is
 557                 # different from the one that mysettings represents.
 558                 mymasks.update(mysettings.usemask)
 559                 mymasks.update(mysettings.archlist())
 560                 mymasks.discard(mysettings["ARCH"])
 561                 useforce.update(mysettings.useforce)
 562                 useforce.difference_update(mymasks)
 563
 564         # eapi code borrowed from _expand_new_virtuals()
 565         mytrees = trees[myroot]
 566         parent = mytrees.get("parent")
 567         virt_parent = mytrees.get("virt_parent")
 568         current_parent = None
 569         eapi = None
 570         if parent is not None:
 571                 if virt_parent is not None:
 572                         current_parent = virt_parent
 573                 else:
 574                         current_parent = parent
 575
 576         if current_parent is not None:
 577                 # Don't pass the eapi argument to use_reduce() for installed packages
 578                 # since previous validation will have already marked them as invalid
 579                 # when necessary and now we're more interested in evaluating
 580                 # dependencies so that things like --depclean work as well as possible
 581                 # in spite of partial invalidity.
 582                 if not current_parent.installed:
 583                         eapi = current_parent.metadata['EAPI']
 584
 585         try:
 586                 mysplit = use_reduce(depstring, uselist=myusesplit, masklist=mymasks, \
 587                         matchall=(use=="all"), excludeall=useforce, opconvert=True, \
 588                         token_class=Atom, eapi=eapi)
 589         except InvalidDependString as e:
 590                 return [0, str(e)]
 591
 592         if mysplit == []:
 593                 #dependencies were reduced to nothing
 594                 return [1,[]]
 595
 596         # Recursively expand new-style virtuals so as to
 597         # collapse one or more levels of indirection.
 598         try:
 599                 mysplit = _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings,
 600                         use=use, mode=mode, myuse=myuse,
 601                         use_force=useforce, use_mask=mymasks, use_cache=use_cache,
 602                         use_binaries=use_binaries, myroot=myroot, trees=trees)
 603         except ParseError as e:
 604                 return [0, str(e)]
 605
 606         mysplit2=mysplit[:]
 607         mysplit2=dep_wordreduce(mysplit2,mysettings,mydbapi,mode,use_cache=use_cache)
 608         if mysplit2 is None:
 609                 return [0, _("Invalid token")]
 610
 611         writemsg("\n\n\n", 1)
 612         writemsg("mysplit:  %s\n" % (mysplit), 1)
 613         writemsg("mysplit2: %s\n" % (mysplit2), 1)
 614
 615         selected_atoms = dep_zapdeps(mysplit, mysplit2, myroot,
 616                 use_binaries=use_binaries, trees=trees)
 617
 618         return [1, selected_atoms]
 619
 620 def dep_wordreduce(mydeplist,mysettings,mydbapi,mode,use_cache=1):
 621         "Reduces the deplist to ones and zeros"
 622         deplist=mydeplist[:]
 623         for mypos, token in enumerate(deplist):
 624                 if isinstance(deplist[mypos], list):
 625                         #recurse
 626                         deplist[mypos]=dep_wordreduce(deplist[mypos],mysettings,mydbapi,mode,use_cache=use_cache)
 627                 elif deplist[mypos]=="||":
 628                         pass
 629                 elif token[:1] == "!":
 630                         deplist[mypos] = False
 631                 else:
 632                         mykey = deplist[mypos].cp
 633                         if mysettings and mykey in mysettings.pprovideddict and \
 634                                 match_from_list(deplist[mypos], mysettings.pprovideddict[mykey]):
 635                                 deplist[mypos]=True
 636                         elif mydbapi is None:
 637                                 # Assume nothing is satisfied.  This forces dep_zapdeps to
 638                                 # return all of deps the deps that have been selected
 639                                 # (excluding those satisfied by package.provided).
 640                                 deplist[mypos] = False
 641                         else:
 642                                 if mode:
 643                                         x = mydbapi.xmatch(mode, deplist[mypos])
 644                                         if mode.startswith("minimum-"):
 645                                                 mydep = []
 646                                                 if x:
 647                                                         mydep.append(x)
 648                                         else:
 649                                                 mydep = x
 650                                 else:
 651                                         mydep=mydbapi.match(deplist[mypos],use_cache=use_cache)
 652                                 if mydep!=None:
 653                                         tmp=(len(mydep)>=1)
 654                                         if deplist[mypos][0]=="!":
 655                                                 tmp=False
 656                                         deplist[mypos]=tmp
 657                                 else:
 658                                         #encountered invalid string
 659                                         return None
 660         return deplist