pym/portage/dep/__init__.py

   1 # deps.py -- Portage dependency resolution functions
   2 # Copyright 2003-2012 Gentoo Foundation
   3 # Distributed under the terms of the GNU General Public License v2
   4
   5 __all__ = [
   6         'Atom', 'best_match_to_list', 'cpvequal',
   7         'dep_getcpv', 'dep_getkey', 'dep_getslot',
   8         'dep_getusedeps', 'dep_opconvert', 'flatten',
   9         'get_operator', 'isjustname', 'isspecific',
  10         'isvalidatom', 'match_from_list', 'match_to_list',
  11         'paren_enclose', 'paren_normalize', 'paren_reduce',
  12         'remove_slot', 'strip_empty', 'use_reduce',
  13         '_repo_separator', '_slot_separator',
  14 ]
  15
  16 # DEPEND SYNTAX:
  17 #
  18 # 'use?' only affects the immediately following word!
  19 # Nesting is the only legal way to form multiple '[!]use?' requirements.
  20 #
  21 # Where: 'a' and 'b' are use flags, and 'z' is a depend atom.
  22 #
  23 # "a? z"           -- If 'a' in [use], then b is valid.
  24 # "a? ( z )"       -- Syntax with parenthesis.
  25 # "a? b? z"        -- Deprecated.
  26 # "a? ( b? z )"    -- Valid
  27 # "a? ( b? ( z ) ) -- Valid
  28 #
  29
  30 import re, sys
  31 import warnings
  32 from itertools import chain
  33
  34 import portage
  35 portage.proxy.lazyimport.lazyimport(globals(),
  36         'portage.util:cmp_sort_key,writemsg',
  37 )
  38
  39 from portage import _unicode_decode
  40 from portage.eapi import _get_eapi_attrs
  41 from portage.exception import InvalidAtom, InvalidData, InvalidDependString
  42 from portage.localization import _
  43 from portage.versions import catpkgsplit, catsplit, \
  44         vercmp, ververify, _cp, _cpv, _pkg_str, _unknown_repo
  45 import portage.cache.mappings
  46
  47 if sys.hexversion >= 0x3000000:
  48         basestring = str
  49
  50 # Api consumers included in portage should set this to True.
  51 # Once the relevant api changes are in a portage release with
  52 # stable keywords, make these warnings unconditional.
  53 _internal_warnings = False
  54
  55 # \w is [a-zA-Z0-9_]
  56
  57 # PMS 3.1.3: A slot name may contain any of the characters [A-Za-z0-9+_.-].
  58 # It must not begin with a hyphen or a dot.
  59 _slot_separator = ":"
  60 _slot = r'([\w+][\w+.-]*)'
  61 _slot_re = re.compile('^' + _slot + '$', re.VERBOSE)
  62
  63 _use = r'\[.*\]'
  64 _op = r'([=~]|[><]=?)'
  65
  66 _repo_separator = "::"
  67 _repo_name = r'[\w][\w-]*'
  68 _repo = r'(?:' + _repo_separator + '(' + _repo_name + ')' + ')?'
  69
  70 _extended_cat = r'[\w+*][\w+.*-]*'
  71
  72 _atom_re_cache = {}
  73
  74 def _get_atom_re(eapi_attrs):
  75         cache_key = eapi_attrs.dots_in_PN
  76         atom_re = _atom_re_cache.get(cache_key)
  77         if atom_re is not None:
  78                 return atom_re
  79
  80         if eapi_attrs.dots_in_PN:
  81                 cp_re =  _cp['dots_allowed_in_PN']
  82                 cpv_re = _cpv['dots_allowed_in_PN']
  83         else:
  84                 cp_re =  _cp['dots_disallowed_in_PN']
  85                 cpv_re = _cpv['dots_disallowed_in_PN']
  86
  87         atom_re = re.compile('^(?P<without_use>(?:' +
  88                 '(?P<op>' + _op + cpv_re + ')|' +
  89                 '(?P<star>=' + cpv_re + r'\*)|' +
  90                 '(?P<simple>' + cp_re + '))' +
  91                 '(' + _slot_separator + _slot + ')?' +
  92                 _repo + ')(' + _use + ')?$', re.VERBOSE)
  93
  94         _atom_re_cache[cache_key] = atom_re
  95         return atom_re
  96
  97 _atom_wildcard_re_cache = {}
  98
  99 def _get_atom_wildcard_re(eapi_attrs):
 100         cache_key = eapi_attrs.dots_in_PN
 101         atom_re = _atom_wildcard_re_cache.get(cache_key)
 102         if atom_re is not None:
 103                 return atom_re
 104
 105         if eapi_attrs.dots_in_PN:
 106                 pkg_re = r'[\w+*][\w+.*-]*?'
 107         else:
 108                 pkg_re = r'[\w+*][\w+*-]*?'
 109
 110         atom_re = re.compile(r'(?P<simple>(' +
 111                 _extended_cat + r')/(' + pkg_re +
 112                 r'))(:(?P<slot>' + _slot + r'))?(' +
 113                 _repo_separator + r'(?P<repo>' + _repo_name + r'))?$')
 114
 115         _atom_wildcard_re_cache[cache_key] = atom_re
 116         return atom_re
 117
 118 _usedep_re_cache = {}
 119
 120 def _get_usedep_re(eapi_attrs):
 121         """
 122         @param eapi_attrs: The EAPI attributes from _get_eapi_attrs
 123         @type eapi_attrs: _eapi_attrs
 124         @rtype: regular expression object
 125         @return: A regular expression object that matches valid USE deps for the
 126                 given eapi.
 127         """
 128         cache_key = eapi_attrs.dots_in_use_flags
 129         usedep_re = _usedep_re_cache.get(cache_key)
 130         if usedep_re is not None:
 131                 return usedep_re
 132
 133         if eapi_attrs.dots_in_use_flags:
 134                 _flag_re = r'[A-Za-z0-9][A-Za-z0-9+_@.-]*'
 135         else:
 136                 _flag_re = r'[A-Za-z0-9][A-Za-z0-9+_@-]*'
 137
 138         usedep_re = re.compile(r'^(?P<prefix>[!-]?)(?P<flag>' +
 139                 _flag_re + r')(?P<default>(\(\+\)|\(\-\))?)(?P<suffix>[?=]?)$')
 140
 141         _usedep_re_cache[cache_key] = usedep_re
 142         return usedep_re
 143
 144 _useflag_re_cache = {}
 145
 146 def _get_useflag_re(eapi):
 147         """
 148         When eapi is None then validation is not as strict, since we want the
 149         same to work for multiple EAPIs that may have slightly different rules.
 150         @param eapi: The EAPI
 151         @type eapi: String or None
 152         @rtype: regular expression object
 153         @return: A regular expression object that matches valid USE flags for the
 154                 given eapi.
 155         """
 156         eapi_attrs = _get_eapi_attrs(eapi)
 157         cache_key = eapi_attrs.dots_in_use_flags
 158         useflag_re = _useflag_re_cache.get(cache_key)
 159         if useflag_re is not None:
 160                 return useflag_re
 161
 162         if eapi_attrs.dots_in_use_flags:
 163                 flag_re = r'[A-Za-z0-9][A-Za-z0-9+_@.-]*'
 164         else:
 165                 flag_re = r'[A-Za-z0-9][A-Za-z0-9+_@-]*'
 166
 167         useflag_re = re.compile(r'^' + flag_re + r'$')
 168
 169         _useflag_re_cache[cache_key] = useflag_re
 170         return useflag_re
 171
 172 def cpvequal(cpv1, cpv2):
 173         """
 174
 175         @param cpv1: CategoryPackageVersion (no operators) Example: "sys-apps/portage-2.1"
 176         @type cpv1: String
 177         @param cpv2: CategoryPackageVersion (no operators) Example: "sys-apps/portage-2.1"
 178         @type cpv2: String
 179         @rtype: Boolean
 180         @return:
 181         1.  True if cpv1 = cpv2
 182         2.  False Otherwise
 183         3.  Throws PortageException if cpv1 or cpv2 is not a CPV
 184
 185         Example Usage:
 186         >>> from portage.dep import cpvequal
 187         >>> cpvequal("sys-apps/portage-2.1","sys-apps/portage-2.1")
 188         >>> True
 189
 190         """
 191
 192         try:
 193                 try:
 194                         split1 = cpv1.cpv_split
 195                 except AttributeError:
 196                         cpv1 = _pkg_str(cpv1)
 197                         split1 = cpv1.cpv_split
 198
 199                 try:
 200                         split2 = cpv2.cpv_split
 201                 except AttributeError:
 202                         cpv2 = _pkg_str(cpv2)
 203                         split2 = cpv2.cpv_split
 204
 205         except InvalidData:
 206                 raise portage.exception.PortageException(_("Invalid data '%s, %s', parameter was not a CPV") % (cpv1, cpv2))
 207
 208         if split1[0] != split2[0] or \
 209                 split1[1] != split2[1]:
 210                 return False
 211
 212         return vercmp(cpv1.version, cpv2.version) == 0
 213
 214 def strip_empty(myarr):
 215         """
 216         Strip all empty elements from an array
 217
 218         @param myarr: The list of elements
 219         @type myarr: List
 220         @rtype: Array
 221         @return: The array with empty elements removed
 222         """
 223         warnings.warn(_("%s is deprecated and will be removed without replacement.") % \
 224                 ('portage.dep.strip_empty',), DeprecationWarning, stacklevel=2)
 225         return [x for x in myarr if x]
 226
 227 def paren_reduce(mystr):
 228         """
 229         Take a string and convert all paren enclosed entities into sublists and
 230         split the list elements by spaces. All redundant brackets are removed.
 231
 232         Example usage:
 233                 >>> paren_reduce('foobar foo? ( bar baz )')
 234                 ['foobar', 'foo?', ['bar', 'baz']]
 235
 236         @param mystr: The string to reduce
 237         @type mystr: String
 238         @rtype: Array
 239         @return: The reduced string in an array
 240         """
 241         if _internal_warnings:
 242                 warnings.warn(_("%s is deprecated and will be removed without replacement.") % \
 243                         ('portage.dep.paren_reduce',), DeprecationWarning, stacklevel=2)
 244         mysplit = mystr.split()
 245         level = 0
 246         stack = [[]]
 247         need_bracket = False
 248
 249         for token in mysplit:
 250                 if token == "(":
 251                         need_bracket = False
 252                         stack.append([])
 253                         level += 1
 254                 elif token == ")":
 255                         if need_bracket:
 256                                 raise InvalidDependString(
 257                                         _("malformed syntax: '%s'") % mystr)
 258                         if level > 0:
 259                                 level -= 1
 260                                 l = stack.pop()
 261                                 is_single = (len(l) == 1 or (len(l)==2 and (l[0] == "||" or l[0][-1] == "?")))
 262
 263                                 def ends_in_any_of_dep(k):
 264                                         return k>=0 and stack[k] and stack[k][-1] == "||"
 265
 266                                 def ends_in_operator(k):
 267                                         return k>=0 and stack[k] and (stack[k][-1] == "||" or stack[k][-1][-1] == "?")
 268
 269                                 def special_append():
 270                                         """
 271                                         Use extend instead of append if possible. This kills all redundant brackets.
 272                                         """
 273                                         if is_single and (not stack[level] or not stack[level][-1][-1] == "?"):
 274                                                 if len(l) == 1 and isinstance(l[0], list):
 275                                                         # l = [[...]]
 276                                                         stack[level].extend(l[0])
 277                                                 else:
 278                                                         stack[level].extend(l)
 279                                         else:
 280                                                 stack[level].append(l)
 281
 282                                 if l:
 283                                         if not ends_in_any_of_dep(level-1) and not ends_in_operator(level):
 284                                                 #Optimize: ( ( ... ) ) -> ( ... ). Make sure there is no '||' hanging around.
 285                                                 stack[level].extend(l)
 286                                         elif not stack[level]:
 287                                                 #An '||' in the level above forces us to keep to brackets.
 288                                                 special_append()
 289                                         elif len(l) == 1 and ends_in_any_of_dep(level):
 290                                                 #Optimize: || ( A ) -> A
 291                                                 stack[level].pop()
 292                                                 special_append()
 293                                         elif len(l) == 2 and (l[0] == "||" or l[0][-1] == "?") and stack[level][-1] in (l[0], "||"):
 294                                                 #Optimize:      || ( || ( ... ) ) -> || ( ... )
 295                                                 #                       foo? ( foo? ( ... ) ) -> foo? ( ... )
 296                                                 #                       || ( foo? ( ... ) ) -> foo? ( ... )
 297                                                 stack[level].pop()
 298                                                 special_append()
 299                                         else:
 300                                                 special_append()
 301                                 else:
 302                                         if stack[level] and (stack[level][-1] == "||" or stack[level][-1][-1] == "?"):
 303                                                 stack[level].pop()
 304                         else:
 305                                 raise InvalidDependString(
 306                                         _("malformed syntax: '%s'") % mystr)
 307                 elif token == "||":
 308                         if need_bracket:
 309                                 raise InvalidDependString(
 310                                         _("malformed syntax: '%s'") % mystr)
 311                         need_bracket = True
 312                         stack[level].append(token)
 313                 else:
 314                         if need_bracket:
 315                                 raise InvalidDependString(
 316                                         _("malformed syntax: '%s'") % mystr)
 317
 318                         if token[-1] == "?":
 319                                 need_bracket = True
 320
 321                         stack[level].append(token)
 322
 323         if level != 0 or need_bracket:
 324                 raise InvalidDependString(
 325                         _("malformed syntax: '%s'") % mystr)
 326
 327         return stack[0]
 328
 329 class paren_normalize(list):
 330         """Take a dependency structure as returned by paren_reduce or use_reduce
 331         and generate an equivalent structure that has no redundant lists."""
 332         def __init__(self, src):
 333                 if _internal_warnings:
 334                         warnings.warn(_("%s is deprecated and will be removed without replacement.") % \
 335                                 ('portage.dep.paren_normalize',), DeprecationWarning, stacklevel=2)
 336                 list.__init__(self)
 337                 self._zap_parens(src, self)
 338
 339         def _zap_parens(self, src, dest, disjunction=False):
 340                 if not src:
 341                         return dest
 342                 i = iter(src)
 343                 for x in i:
 344                         if isinstance(x, basestring):
 345                                 if x in ('||', '^^'):
 346                                         y = self._zap_parens(next(i), [], disjunction=True)
 347                                         if len(y) == 1:
 348                                                 dest.append(y[0])
 349                                         else:
 350                                                 dest.append(x)
 351                                                 dest.append(y)
 352                                 elif x.endswith("?"):
 353                                         dest.append(x)
 354                                         dest.append(self._zap_parens(next(i), []))
 355                                 else:
 356                                         dest.append(x)
 357                         else:
 358                                 if disjunction:
 359                                         x = self._zap_parens(x, [])
 360                                         if len(x) == 1:
 361                                                 dest.append(x[0])
 362                                         else:
 363                                                 dest.append(x)
 364                                 else:
 365                                         self._zap_parens(x, dest)
 366                 return dest
 367
 368 def paren_enclose(mylist, unevaluated_atom=False, opconvert=False):
 369         """
 370         Convert a list to a string with sublists enclosed with parens.
 371
 372         Example usage:
 373                 >>> test = ['foobar','foo',['bar','baz']]
 374                 >>> paren_enclose(test)
 375                 'foobar foo ( bar baz )'
 376
 377         @param mylist: The list
 378         @type mylist: List
 379         @rtype: String
 380         @return: The paren enclosed string
 381         """
 382         mystrparts = []
 383         for x in mylist:
 384                 if isinstance(x, list):
 385                         if opconvert and x and x[0] == "||":
 386                                 mystrparts.append("%s ( %s )" % (x[0], paren_enclose(x[1:])))
 387                         else:
 388                                 mystrparts.append("( %s )" % paren_enclose(x))
 389                 else:
 390                         if unevaluated_atom:
 391                                 x = getattr(x, 'unevaluated_atom', x)
 392                         mystrparts.append(x)
 393         return " ".join(mystrparts)
 394
 395 def use_reduce(depstr, uselist=[], masklist=[], matchall=False, excludeall=[], is_src_uri=False, \
 396         eapi=None, opconvert=False, flat=False, is_valid_flag=None, token_class=None, matchnone=False):
 397         """
 398         Takes a dep string and reduces the use? conditionals out, leaving an array
 399         with subarrays. All redundant brackets are removed.
 400
 401         @param deparray: depstring
 402         @type deparray: String
 403         @param uselist: List of use enabled flags
 404         @type uselist: List
 405         @param masklist: List of masked flags (always treated as disabled)
 406         @type masklist: List
 407         @param matchall: Treat all conditionals as active. Used by repoman.
 408         @type matchall: Bool
 409         @param excludeall: List of flags for which negated conditionals are always treated as inactive.
 410         @type excludeall: List
 411         @param is_src_uri: Indicates if depstr represents a SRC_URI
 412         @type is_src_uri: Bool
 413         @param eapi: Indicates the EAPI the dep string has to comply to
 414         @type eapi: String
 415         @param opconvert: Put every operator as first element into it's argument list
 416         @type opconvert: Bool
 417         @param flat: Create a flat list of all tokens
 418         @type flat: Bool
 419         @param is_valid_flag: Function that decides if a given use flag might be used in use conditionals
 420         @type is_valid_flag: Function
 421         @param token_class: Convert all non operator tokens into this class
 422         @type token_class: Class
 423         @param matchnone: Treat all conditionals as inactive. Used by digestgen().
 424         @type matchnone: Bool
 425         @rtype: List
 426         @return: The use reduced depend array
 427         """
 428         if isinstance(depstr, list):
 429                 if _internal_warnings:
 430                         warnings.warn(_("Passing paren_reduced dep arrays to %s is deprecated. " + \
 431                                 "Pass the original dep string instead.") % \
 432                                 ('portage.dep.use_reduce',), DeprecationWarning, stacklevel=2)
 433                 depstr = paren_enclose(depstr)
 434
 435         if opconvert and flat:
 436                 raise ValueError("portage.dep.use_reduce: 'opconvert' and 'flat' are mutually exclusive")
 437
 438         if matchall and matchnone:
 439                 raise ValueError("portage.dep.use_reduce: 'matchall' and 'matchnone' are mutually exclusive")
 440
 441         eapi_attrs = _get_eapi_attrs(eapi)
 442         useflag_re = _get_useflag_re(eapi)
 443
 444         def is_active(conditional):
 445                 """
 446                 Decides if a given use conditional is active.
 447                 """
 448                 if conditional.startswith("!"):
 449                         flag = conditional[1:-1]
 450                         is_negated = True
 451                 else:
 452                         flag = conditional[:-1]
 453                         is_negated = False
 454
 455                 if is_valid_flag:
 456                         if not is_valid_flag(flag):
 457                                 msg = _("USE flag '%s' referenced in " + \
 458                                         "conditional '%s' is not in IUSE") \
 459                                         % (flag, conditional)
 460                                 e = InvalidData(msg, category='IUSE.missing')
 461                                 raise InvalidDependString(msg, errors=(e,))
 462                 else:
 463                         if useflag_re.match(flag) is None:
 464                                 raise InvalidDependString(
 465                                         _("invalid use flag '%s' in conditional '%s'") % (flag, conditional))
 466
 467                 if is_negated and flag in excludeall:
 468                         return False
 469
 470                 if flag in masklist:
 471                         return is_negated
 472
 473                 if matchall:
 474                         return True
 475
 476                 if matchnone:
 477                         return False
 478
 479                 return (flag in uselist and not is_negated) or \
 480                         (flag not in uselist and is_negated)
 481
 482         def missing_white_space_check(token, pos):
 483                 """
 484                 Used to generate good error messages for invalid tokens.
 485                 """
 486                 for x in (")", "(", "||"):
 487                         if token.startswith(x) or token.endswith(x):
 488                                 raise InvalidDependString(
 489                                         _("missing whitespace around '%s' at '%s', token %s") % (x, token, pos+1))
 490
 491         mysplit = depstr.split()
 492         #Count the bracket level.
 493         level = 0
 494         #We parse into a stack. Every time we hit a '(', a new empty list is appended to the stack.
 495         #When we hit a ')', the last list in the stack is merged with list one level up.
 496         stack = [[]]
 497         #Set need_bracket to True after use conditionals or ||. Other tokens need to ensure
 498         #that need_bracket is not True.
 499         need_bracket = False
 500         #Set need_simple_token to True after a SRC_URI arrow. Other tokens need to ensure
 501         #that need_simple_token is not True.
 502         need_simple_token = False
 503
 504         for pos, token in enumerate(mysplit):
 505                 if token == "(":
 506                         if need_simple_token:
 507                                 raise InvalidDependString(
 508                                         _("expected: file name, got: '%s', token %s") % (token, pos+1))
 509                         if len(mysplit) >= pos+2 and mysplit[pos+1] == ")":
 510                                 raise InvalidDependString(
 511                                         _("expected: dependency string, got: ')', token %s") % (pos+1,))
 512                         need_bracket = False
 513                         stack.append([])
 514                         level += 1
 515                 elif token == ")":
 516                         if need_bracket:
 517                                 raise InvalidDependString(
 518                                         _("expected: '(', got: '%s', token %s") % (token, pos+1))
 519                         if need_simple_token:
 520                                 raise InvalidDependString(
 521                                         _("expected: file name, got: '%s', token %s") % (token, pos+1))
 522                         if level > 0:
 523                                 level -= 1
 524                                 l = stack.pop()
 525
 526                                 is_single = len(l) == 1 or \
 527                                         (opconvert and l and l[0] == "||") or \
 528                                         (not opconvert and len(l)==2 and l[0] == "||")
 529                                 ignore = False
 530
 531                                 if flat:
 532                                         #In 'flat' mode, we simply merge all lists into a single large one.
 533                                         if stack[level] and stack[level][-1][-1] == "?":
 534                                                 #The last token before the '(' that matches the current ')'
 535                                                 #was a use conditional. The conditional is removed in any case.
 536                                                 #Merge the current list if needed.
 537                                                 if is_active(stack[level][-1]):
 538                                                         stack[level].pop()
 539                                                         stack[level].extend(l)
 540                                                 else:
 541                                                         stack[level].pop()
 542                                         else:
 543                                                 stack[level].extend(l)
 544                                         continue
 545
 546                                 if stack[level]:
 547                                         if stack[level][-1] == "||" and not l:
 548                                                 #Optimize: || ( ) -> .
 549                                                 stack[level].pop()
 550                                         elif stack[level][-1][-1] == "?":
 551                                                 #The last token before the '(' that matches the current ')'
 552                                                 #was a use conditional, remove it and decide if we
 553                                                 #have to keep the current list.
 554                                                 if not is_active(stack[level][-1]):
 555                                                         ignore = True
 556                                                 stack[level].pop()
 557
 558                                 def ends_in_any_of_dep(k):
 559                                         return k>=0 and stack[k] and stack[k][-1] == "||"
 560
 561                                 def starts_with_any_of_dep(k):
 562                                         #'ends_in_any_of_dep' for opconvert
 563                                         return k>=0 and stack[k] and stack[k][0] == "||"
 564
 565                                 def last_any_of_operator_level(k):
 566                                         #Returns the level of the last || operator if it is in effect for
 567                                         #the current level. It is not in effect, if there is a level, that
 568                                         #ends in a non-operator. This is almost equivalent to stack[level][-1]=="||",
 569                                         #expect that it skips empty levels.
 570                                         while k>=0:
 571                                                 if stack[k]:
 572                                                         if stack[k][-1] == "||":
 573                                                                 return k
 574                                                         elif stack[k][-1][-1] != "?":
 575                                                                 return -1
 576                                                 k -= 1
 577                                         return -1
 578
 579                                 def special_append():
 580                                         """
 581                                         Use extend instead of append if possible. This kills all redundant brackets.
 582                                         """
 583                                         if is_single:
 584                                                 #Either [A], [[...]] or [|| [...]]
 585                                                 if l[0] == "||" and ends_in_any_of_dep(level-1):
 586                                                         if opconvert:
 587                                                                 stack[level].extend(l[1:])
 588                                                         else:
 589                                                                 stack[level].extend(l[1])
 590                                                 elif len(l) == 1 and isinstance(l[0], list):
 591                                                         # l = [[...]]
 592                                                         last = last_any_of_operator_level(level-1)
 593                                                         if last == -1:
 594                                                                 if opconvert and isinstance(l[0], list) \
 595                                                                         and l[0] and l[0][0] == '||':
 596                                                                         stack[level].append(l[0])
 597                                                                 else:
 598                                                                         stack[level].extend(l[0])
 599                                                         else:
 600                                                                 if opconvert and l[0] and l[0][0] == "||":
 601                                                                         stack[level].extend(l[0][1:])
 602                                                                 else:
 603                                                                         stack[level].append(l[0])
 604                                                 else:
 605                                                         stack[level].extend(l)
 606                                         else:
 607                                                 if opconvert and stack[level] and stack[level][-1] == '||':
 608                                                         stack[level][-1] = ['||'] + l
 609                                                 else:
 610                                                         stack[level].append(l)
 611
 612                                 if l and not ignore:
 613                                         #The current list is not empty and we don't want to ignore it because
 614                                         #of an inactive use conditional.
 615                                         if not ends_in_any_of_dep(level-1) and not ends_in_any_of_dep(level):
 616                                                 #Optimize: ( ( ... ) ) -> ( ... ). Make sure there is no '||' hanging around.
 617                                                 stack[level].extend(l)
 618                                         elif not stack[level]:
 619                                                 #An '||' in the level above forces us to keep to brackets.
 620                                                 special_append()
 621                                         elif is_single and ends_in_any_of_dep(level):
 622                                                 #Optimize: || ( A ) -> A,  || ( || ( ... ) ) -> || ( ... )
 623                                                 stack[level].pop()
 624                                                 special_append()
 625                                         elif ends_in_any_of_dep(level) and ends_in_any_of_dep(level-1):
 626                                                 #Optimize: || ( A || ( B C ) ) -> || ( A B C )
 627                                                 stack[level].pop()
 628                                                 stack[level].extend(l)
 629                                         else:
 630                                                 if opconvert and ends_in_any_of_dep(level):
 631                                                         #In opconvert mode, we have to move the operator from the level
 632                                                         #above into the current list.
 633                                                         stack[level].pop()
 634                                                         stack[level].append(["||"] + l)
 635                                                 else:
 636                                                         special_append()
 637
 638                         else:
 639                                 raise InvalidDependString(
 640                                         _("no matching '%s' for '%s', token %s") % ("(", ")", pos+1))
 641                 elif token == "||":
 642                         if is_src_uri:
 643                                 raise InvalidDependString(
 644                                         _("any-of dependencies are not allowed in SRC_URI: token %s") % (pos+1,))
 645                         if need_bracket:
 646                                 raise InvalidDependString(
 647                                         _("expected: '(', got: '%s', token %s") % (token, pos+1))
 648                         need_bracket = True
 649                         stack[level].append(token)
 650                 elif token == "->":
 651                         if need_simple_token:
 652                                 raise InvalidDependString(
 653                                         _("expected: file name, got: '%s', token %s") % (token, pos+1))
 654                         if not is_src_uri:
 655                                 raise InvalidDependString(
 656                                         _("SRC_URI arrow are only allowed in SRC_URI: token %s") % (pos+1,))
 657                         if not eapi_attrs.src_uri_arrows:
 658                                 raise InvalidDependString(
 659                                         _("SRC_URI arrow not allowed in EAPI %s: token %s") % (eapi, pos+1))
 660                         need_simple_token = True
 661                         stack[level].append(token)
 662                 else:
 663                         missing_white_space_check(token, pos)
 664
 665                         if need_bracket:
 666                                 raise InvalidDependString(
 667                                         _("expected: '(', got: '%s', token %s") % (token, pos+1))
 668
 669                         if need_simple_token and "/" in token:
 670                                 #The last token was a SRC_URI arrow, make sure we have a simple file name.
 671                                 raise InvalidDependString(
 672                                         _("expected: file name, got: '%s', token %s") % (token, pos+1))
 673
 674                         if token[-1] == "?":
 675                                 need_bracket = True
 676                         else:
 677                                 need_simple_token = False
 678                                 if token_class and not is_src_uri:
 679                                         #Add a hack for SRC_URI here, to avoid conditional code at the consumer level
 680                                         try:
 681                                                 token = token_class(token, eapi=eapi,
 682                                                         is_valid_flag=is_valid_flag)
 683                                         except InvalidAtom as e:
 684                                                 raise InvalidDependString(
 685                                                         _("Invalid atom (%s), token %s") \
 686                                                         % (e, pos+1), errors=(e,))
 687                                         except SystemExit:
 688                                                 raise
 689                                         except Exception as e:
 690                                                 raise InvalidDependString(
 691                                                         _("Invalid token '%s', token %s") % (token, pos+1))
 692
 693                                         if not matchall and \
 694                                                 hasattr(token, 'evaluate_conditionals'):
 695                                                 token = token.evaluate_conditionals(uselist)
 696
 697                         stack[level].append(token)
 698
 699         if level != 0:
 700                 raise InvalidDependString(
 701                         _("Missing '%s' at end of string") % (")",))
 702
 703         if need_bracket:
 704                 raise InvalidDependString(
 705                         _("Missing '%s' at end of string") % ("(",))
 706
 707         if need_simple_token:
 708                 raise InvalidDependString(
 709                         _("Missing file name at end of string"))
 710
 711         return stack[0]
 712
 713 def dep_opconvert(deplist):
 714         """
 715         Iterate recursively through a list of deps, if the
 716         dep is a '||' or '&&' operator, combine it with the
 717         list of deps that follows..
 718
 719         Example usage:
 720                 >>> test = ["blah", "||", ["foo", "bar", "baz"]]
 721                 >>> dep_opconvert(test)
 722                 ['blah', ['||', 'foo', 'bar', 'baz']]
 723
 724         @param deplist: A list of deps to format
 725         @type mydep: List
 726         @rtype: List
 727         @return:
 728                 The new list with the new ordering
 729         """
 730         if _internal_warnings:
 731                 warnings.warn(_("%s is deprecated. Use %s with the opconvert parameter set to True instead.") % \
 732                         ('portage.dep.dep_opconvert', 'portage.dep.use_reduce'), DeprecationWarning, stacklevel=2)
 733
 734         retlist = []
 735         x = 0
 736         while x != len(deplist):
 737                 if isinstance(deplist[x], list):
 738                         retlist.append(dep_opconvert(deplist[x]))
 739                 elif deplist[x] == "||":
 740                         retlist.append([deplist[x]] + dep_opconvert(deplist[x+1]))
 741                         x += 1
 742                 else:
 743                         retlist.append(deplist[x])
 744                 x += 1
 745         return retlist
 746
 747 def flatten(mylist):
 748         """
 749         Recursively traverse nested lists and return a single list containing
 750         all non-list elements that are found.
 751
 752         Example usage:
 753                 >>> flatten([1, [2, 3, [4]]])
 754                 [1, 2, 3, 4]
 755
 756         @param mylist: A list containing nested lists and non-list elements.
 757         @type mylist: List
 758         @rtype: List
 759         @return: A single list containing only non-list elements.
 760         """
 761         if _internal_warnings:
 762                 warnings.warn(_("%s is deprecated and will be removed without replacement.") % \
 763                         ('portage.dep.flatten',), DeprecationWarning, stacklevel=2)
 764
 765         newlist = []
 766         for x in mylist:
 767                 if isinstance(x, list):
 768                         newlist.extend(flatten(x))
 769                 else:
 770                         newlist.append(x)
 771         return newlist
 772
 773 class _use_dep(object):
 774
 775         __slots__ = ("_eapi_attrs", "conditional", "missing_enabled", "missing_disabled",
 776                 "disabled", "enabled", "tokens", "required")
 777
 778         class _conditionals_class(object):
 779                 __slots__ = ("enabled", "disabled", "equal", "not_equal")
 780
 781                 def items(self):
 782                         for k in self.__slots__:
 783                                 v = getattr(self, k, None)
 784                                 if v:
 785                                         yield (k, v)
 786
 787                 def values(self):
 788                         for k in self.__slots__:
 789                                 v = getattr(self, k, None)
 790                                 if v:
 791                                         yield v
 792
 793         # used in InvalidAtom messages
 794         _conditional_strings = {
 795                 'enabled' :     '%s?',
 796                 'disabled':    '!%s?',
 797                 'equal':        '%s=',
 798                 'not_equal':   '!%s=',
 799         }
 800
 801         def __init__(self, use, eapi_attrs, enabled_flags=None, disabled_flags=None, missing_enabled=None,
 802                 missing_disabled=None, conditional=None, required=None):
 803
 804                 self._eapi_attrs = eapi_attrs
 805
 806                 if enabled_flags is not None:
 807                         #A shortcut for the classe's own methods.
 808                         self.tokens = use
 809                         if not isinstance(self.tokens, tuple):
 810                                 self.tokens = tuple(self.tokens)
 811
 812                         self.required = frozenset(required)
 813                         self.enabled = frozenset(enabled_flags)
 814                         self.disabled = frozenset(disabled_flags)
 815                         self.missing_enabled = frozenset(missing_enabled)
 816                         self.missing_disabled = frozenset(missing_disabled)
 817                         self.conditional = None
 818
 819                         if conditional:
 820                                 self.conditional = self._conditionals_class()
 821                                 for k in "enabled", "disabled", "equal", "not_equal":
 822                                         setattr(self.conditional, k, frozenset(conditional.get(k, [])))
 823
 824                         return
 825
 826                 enabled_flags = set()
 827                 disabled_flags = set()
 828                 missing_enabled = set()
 829                 missing_disabled = set()
 830                 no_default = set()
 831
 832                 conditional = {}
 833                 usedep_re = _get_usedep_re(self._eapi_attrs)
 834
 835                 for x in use:
 836                         m = usedep_re.match(x)
 837                         if m is None:
 838                                 raise InvalidAtom(_("Invalid use dep: '%s'") % (x,))
 839
 840                         operator = m.group("prefix") + m.group("suffix")
 841                         flag = m.group("flag")
 842                         default = m.group("default")
 843
 844                         if not operator:
 845                                 enabled_flags.add(flag)
 846                         elif operator == "-":
 847                                 disabled_flags.add(flag)
 848                         elif operator == "?":
 849                                 conditional.setdefault("enabled", set()).add(flag)
 850                         elif operator == "=":
 851                                 conditional.setdefault("equal", set()).add(flag)
 852                         elif operator == "!=":
 853                                 conditional.setdefault("not_equal", set()).add(flag)
 854                         elif operator == "!?":
 855                                 conditional.setdefault("disabled", set()).add(flag)
 856                         else:
 857                                 raise InvalidAtom(_("Invalid use dep: '%s'") % (x,))
 858
 859                         if default:
 860                                 if default == "(+)":
 861                                         if flag in missing_disabled or flag in no_default:
 862                                                 raise InvalidAtom(_("Invalid use dep: '%s'") % (x,))
 863                                         missing_enabled.add(flag)
 864                                 else:
 865                                         if flag in missing_enabled or flag in no_default:
 866                                                 raise InvalidAtom(_("Invalid use dep: '%s'") % (x,))
 867                                         missing_disabled.add(flag)
 868                         else:
 869                                 if flag in missing_enabled or flag in missing_disabled:
 870                                         raise InvalidAtom(_("Invalid use dep: '%s'") % (x,))
 871                                 no_default.add(flag)
 872
 873                 self.tokens = use
 874                 if not isinstance(self.tokens, tuple):
 875                         self.tokens = tuple(self.tokens)
 876
 877                 self.required = frozenset(no_default)
 878
 879                 self.enabled = frozenset(enabled_flags)
 880                 self.disabled = frozenset(disabled_flags)
 881                 self.missing_enabled = frozenset(missing_enabled)
 882                 self.missing_disabled = frozenset(missing_disabled)
 883                 self.conditional = None
 884
 885                 if conditional:
 886                         self.conditional = self._conditionals_class()
 887                         for k in "enabled", "disabled", "equal", "not_equal":
 888                                 setattr(self.conditional, k, frozenset(conditional.get(k, [])))
 889
 890         def __bool__(self):
 891                 return bool(self.tokens)
 892
 893         if sys.hexversion < 0x3000000:
 894                 __nonzero__ = __bool__
 895
 896         def __str__(self):
 897                 if not self.tokens:
 898                         return ""
 899                 return "[%s]" % (",".join(self.tokens),)
 900
 901         def __repr__(self):
 902                 return "portage.dep._use_dep(%s)" % repr(self.tokens)
 903
 904         def evaluate_conditionals(self, use):
 905                 """
 906                 Create a new instance with conditionals evaluated.
 907
 908                 Conditional evaluation behavior:
 909
 910                         parent state   conditional   result
 911
 912                          x              x?            x
 913                         -x              x?
 914                          x             !x?
 915                         -x             !x?           -x
 916
 917                          x              x=            x
 918                         -x              x=           -x
 919                          x             !x=           -x
 920                         -x             !x=            x
 921
 922                 Conditional syntax examples:
 923
 924                         Compact Form        Equivalent Expanded Form
 925
 926                         foo[bar?]           bar? ( foo[bar]  ) !bar? ( foo       )
 927                         foo[!bar?]          bar? ( foo       ) !bar? ( foo[-bar] )
 928                         foo[bar=]           bar? ( foo[bar]  ) !bar? ( foo[-bar] )
 929                         foo[!bar=]          bar? ( foo[-bar] ) !bar? ( foo[bar]  )
 930
 931                 """
 932                 enabled_flags = set(self.enabled)
 933                 disabled_flags = set(self.disabled)
 934
 935                 tokens = []
 936                 usedep_re = _get_usedep_re(self._eapi_attrs)
 937
 938                 for x in self.tokens:
 939                         m = usedep_re.match(x)
 940
 941                         operator = m.group("prefix") + m.group("suffix")
 942                         flag = m.group("flag")
 943                         default = m.group("default")
 944                         if default is None:
 945                                 default = ""
 946
 947                         if operator == "?":
 948                                 if flag in use:
 949                                         enabled_flags.add(flag)
 950                                         tokens.append(flag+default)
 951                         elif operator == "=":
 952                                 if flag in use:
 953                                         enabled_flags.add(flag)
 954                                         tokens.append(flag+default)
 955                                 else:
 956                                         disabled_flags.add(flag)
 957                                         tokens.append("-"+flag+default)
 958                         elif operator == "!=":
 959                                 if flag in use:
 960                                         disabled_flags.add(flag)
 961                                         tokens.append("-"+flag+default)
 962                                 else:
 963                                         enabled_flags.add(flag)
 964                                         tokens.append(flag+default)
 965                         elif operator == "!?":
 966                                 if flag not in use:
 967                                         disabled_flags.add(flag)
 968                                         tokens.append("-"+flag+default)
 969                         else:
 970                                 tokens.append(x)
 971
 972                 return _use_dep(tokens, self._eapi_attrs, enabled_flags=enabled_flags, disabled_flags=disabled_flags,
 973                         missing_enabled=self.missing_enabled, missing_disabled=self.missing_disabled, required=self.required)
 974
 975         def violated_conditionals(self, other_use, is_valid_flag, parent_use=None):
 976                 """
 977                 Create a new instance with satisfied use deps removed.
 978                 """
 979                 if parent_use is None and self.conditional:
 980                         raise InvalidAtom("violated_conditionals needs 'parent_use'" + \
 981                                 " parameter for conditional flags.")
 982
 983                 enabled_flags = set()
 984                 disabled_flags = set()
 985
 986                 conditional = {}
 987                 tokens = []
 988
 989                 all_defaults = frozenset(chain(self.missing_enabled, self.missing_disabled))
 990
 991                 def validate_flag(flag):
 992                         return is_valid_flag(flag) or flag in all_defaults
 993
 994                 usedep_re = _get_usedep_re(self._eapi_attrs)
 995
 996                 for x in self.tokens:
 997                         m = usedep_re.match(x)
 998
 999                         operator = m.group("prefix") + m.group("suffix")
1000                         flag = m.group("flag")
1001
1002                         if not validate_flag(flag):
1003                                 tokens.append(x)
1004                                 if not operator:
1005                                         enabled_flags.add(flag)
1006                                 elif operator == "-":
1007                                         disabled_flags.add(flag)
1008                                 elif operator == "?":
1009                                         conditional.setdefault("enabled", set()).add(flag)
1010                                 elif operator == "=":
1011                                         conditional.setdefault("equal", set()).add(flag)
1012                                 elif operator == "!=":
1013                                         conditional.setdefault("not_equal", set()).add(flag)
1014                                 elif operator == "!?":
1015                                         conditional.setdefault("disabled", set()).add(flag)
1016
1017                                 continue
1018
1019                         if not operator:
1020                                 if flag not in other_use:
1021                                         if is_valid_flag(flag) or flag in self.missing_disabled:
1022                                                 tokens.append(x)
1023                                                 enabled_flags.add(flag)
1024                         elif operator == "-":
1025                                 if flag not in other_use:
1026                                         if not is_valid_flag(flag):
1027                                                 if flag in self.missing_enabled:
1028                                                         tokens.append(x)
1029                                                         disabled_flags.add(flag)
1030                                 else:
1031                                         tokens.append(x)
1032                                         disabled_flags.add(flag)
1033                         elif operator == "?":
1034                                 if flag not in parent_use or flag in other_use:
1035                                         continue
1036
1037                                 if is_valid_flag(flag) or flag in self.missing_disabled:
1038                                         tokens.append(x)
1039                                         conditional.setdefault("enabled", set()).add(flag)
1040                         elif operator == "=":
1041                                 if flag in parent_use and flag not in other_use:
1042                                         if is_valid_flag(flag):
1043                                                 tokens.append(x)
1044                                                 conditional.setdefault("equal", set()).add(flag)
1045                                         else:
1046                                                 if flag in self.missing_disabled:
1047                                                         tokens.append(x)
1048                                                         conditional.setdefault("equal", set()).add(flag)
1049                                 elif flag not in parent_use:
1050                                         if flag not in other_use:
1051                                                 if not is_valid_flag(flag):
1052                                                         if flag in self.missing_enabled:
1053                                                                 tokens.append(x)
1054                                                                 conditional.setdefault("equal", set()).add(flag)
1055                                         else:
1056                                                 tokens.append(x)
1057                                                 conditional.setdefault("equal", set()).add(flag)
1058                         elif operator == "!=":
1059                                 if flag not in parent_use and flag not in other_use:
1060                                         if is_valid_flag(flag):
1061                                                 tokens.append(x)
1062                                                 conditional.setdefault("not_equal", set()).add(flag)
1063                                         else:
1064                                                 if flag in self.missing_disabled:
1065                                                         tokens.append(x)
1066                                                         conditional.setdefault("not_equal", set()).add(flag)
1067                                 elif flag in parent_use:
1068                                         if flag not in other_use:
1069                                                 if not is_valid_flag(flag):
1070                                                         if flag in self.missing_enabled:
1071                                                                 tokens.append(x)
1072                                                                 conditional.setdefault("not_equal", set()).add(flag)
1073                                         else:
1074                                                 tokens.append(x)
1075                                                 conditional.setdefault("not_equal", set()).add(flag)
1076                         elif operator == "!?":
1077                                 if flag not in parent_use:
1078                                         if flag not in other_use:
1079                                                 if not is_valid_flag(flag) and flag in self.missing_enabled:
1080                                                         tokens.append(x)
1081                                                         conditional.setdefault("disabled", set()).add(flag)
1082                                         else:
1083                                                 tokens.append(x)
1084                                                 conditional.setdefault("disabled", set()).add(flag)
1085
1086                 return _use_dep(tokens, self._eapi_attrs, enabled_flags=enabled_flags, disabled_flags=disabled_flags,
1087                         missing_enabled=self.missing_enabled, missing_disabled=self.missing_disabled, \
1088                         conditional=conditional, required=self.required)
1089
1090         def _eval_qa_conditionals(self, use_mask, use_force):
1091                 """
1092                 For repoman, evaluate all possible combinations within the constraints
1093                 of the given use.force and use.mask settings. The result may seem
1094                 ambiguous in the sense that the same flag can be in both the enabled
1095                 and disabled sets, but this is useful within the context of how its
1096                 intended to be used by repoman. It is assumed that the caller has
1097                 already ensured that there is no intersection between the given
1098                 use_mask and use_force sets when necessary.
1099                 """
1100                 enabled_flags = set(self.enabled)
1101                 disabled_flags = set(self.disabled)
1102                 missing_enabled = self.missing_enabled
1103                 missing_disabled = self.missing_disabled
1104
1105                 tokens = []
1106                 usedep_re = _get_usedep_re(self._eapi_attrs)
1107
1108                 for x in self.tokens:
1109                         m = usedep_re.match(x)
1110
1111                         operator = m.group("prefix") + m.group("suffix")
1112                         flag = m.group("flag")
1113                         default = m.group("default")
1114                         if default is None:
1115                                 default = ""
1116
1117                         if operator == "?":
1118                                 if flag not in use_mask:
1119                                         enabled_flags.add(flag)
1120                                         tokens.append(flag+default)
1121                         elif operator == "=":
1122                                 if flag not in use_mask:
1123                                         enabled_flags.add(flag)
1124                                         tokens.append(flag+default)
1125                                 if flag not in use_force:
1126                                         disabled_flags.add(flag)
1127                                         tokens.append("-"+flag+default)
1128                         elif operator == "!=":
1129                                 if flag not in use_force:
1130                                         enabled_flags.add(flag)
1131                                         tokens.append(flag+default)
1132                                 if flag not in use_mask:
1133                                         disabled_flags.add(flag)
1134                                         tokens.append("-"+flag+default)
1135                         elif operator == "!?":
1136                                 if flag not in use_force:
1137                                         disabled_flags.add(flag)
1138                                         tokens.append("-"+flag+default)
1139                         else:
1140                                 tokens.append(x)
1141
1142                 return _use_dep(tokens, self._eapi_attrs, enabled_flags=enabled_flags, disabled_flags=disabled_flags,
1143                         missing_enabled=missing_enabled, missing_disabled=missing_disabled, required=self.required)
1144
1145 if sys.hexversion < 0x3000000:
1146         _atom_base = unicode
1147 else:
1148         _atom_base = str
1149
1150 class Atom(_atom_base):
1151
1152         """
1153         For compatibility with existing atom string manipulation code, this
1154         class emulates most of the str methods that are useful with atoms.
1155         """
1156
1157         class _blocker(object):
1158                 __slots__ = ("overlap",)
1159
1160                 class _overlap(object):
1161                         __slots__ = ("forbid",)
1162
1163                         def __init__(self, forbid=False):
1164                                 self.forbid = forbid
1165
1166                 def __init__(self, forbid_overlap=False):
1167                         self.overlap = self._overlap(forbid=forbid_overlap)
1168
1169         def __new__(cls, s, unevaluated_atom=None, allow_wildcard=False, allow_repo=None,
1170                 _use=None, eapi=None, is_valid_flag=None):
1171                 return _atom_base.__new__(cls, s)
1172
1173         def __init__(self, s, unevaluated_atom=None, allow_wildcard=False, allow_repo=None,
1174                 _use=None, eapi=None, is_valid_flag=None):
1175                 if isinstance(s, Atom):
1176                         # This is an efficiency assertion, to ensure that the Atom
1177                         # constructor is not called redundantly.
1178                         raise TypeError(_("Expected %s, got %s") % \
1179                                 (_atom_base, type(s)))
1180
1181                 if not isinstance(s, _atom_base):
1182                         # Avoid TypeError from _atom_base.__init__ with PyPy.
1183                         s = _unicode_decode(s)
1184
1185                 _atom_base.__init__(s)
1186
1187                 eapi_attrs = _get_eapi_attrs(eapi)
1188                 atom_re = _get_atom_re(eapi_attrs)
1189
1190                 if eapi is not None:
1191                         # Ignore allow_repo when eapi is specified.
1192                         allow_repo = eapi_attrs.repo_deps
1193                 else:
1194                         if allow_repo is None:
1195                                 allow_repo = True
1196
1197                 if "!" == s[:1]:
1198                         blocker = self._blocker(forbid_overlap=("!" == s[1:2]))
1199                         if blocker.overlap.forbid:
1200                                 s = s[2:]
1201                         else:
1202                                 s = s[1:]
1203                 else:
1204                         blocker = False
1205                 self.__dict__['blocker'] = blocker
1206                 m = atom_re.match(s)
1207                 extended_syntax = False
1208                 if m is None:
1209                         if allow_wildcard:
1210                                 m = _get_atom_wildcard_re(eapi_attrs).match(s)
1211                                 if m is None:
1212                                         raise InvalidAtom(self)
1213                                 op = None
1214                                 gdict = m.groupdict()
1215                                 cpv = cp = gdict['simple']
1216                                 if cpv.find("**") != -1:
1217                                         raise InvalidAtom(self)
1218                                 slot = gdict['slot']
1219                                 repo = gdict['repo']
1220                                 use_str = None
1221                                 extended_syntax = True
1222                         else:
1223                                 raise InvalidAtom(self)
1224                 elif m.group('op') is not None:
1225                         base = atom_re.groupindex['op']
1226                         op = m.group(base + 1)
1227                         cpv = m.group(base + 2)
1228                         cp = m.group(base + 3)
1229                         slot = m.group(atom_re.groups - 2)
1230                         repo = m.group(atom_re.groups - 1)
1231                         use_str = m.group(atom_re.groups)
1232                         if m.group(base + 4) is not None:
1233                                 raise InvalidAtom(self)
1234                 elif m.group('star') is not None:
1235                         base = atom_re.groupindex['star']
1236                         op = '=*'
1237                         cpv = m.group(base + 1)
1238                         cp = m.group(base + 2)
1239                         slot = m.group(atom_re.groups - 2)
1240                         repo = m.group(atom_re.groups - 1)
1241                         use_str = m.group(atom_re.groups)
1242                         if m.group(base + 3) is not None:
1243                                 raise InvalidAtom(self)
1244                 elif m.group('simple') is not None:
1245                         op = None
1246                         cpv = cp = m.group(atom_re.groupindex['simple'] + 1)
1247                         slot = m.group(atom_re.groups - 2)
1248                         repo = m.group(atom_re.groups - 1)
1249                         use_str = m.group(atom_re.groups)
1250                         if m.group(atom_re.groupindex['simple'] + 2) is not None:
1251                                 raise InvalidAtom(self)
1252
1253                 else:
1254                         raise AssertionError(_("required group not found in atom: '%s'") % self)
1255                 self.__dict__['cp'] = cp
1256                 try:
1257                         self.__dict__['cpv'] = _pkg_str(cpv)
1258                         self.__dict__['version'] = self.cpv.version
1259                 except InvalidData:
1260                         # plain cp, wildcard, or something
1261                         self.__dict__['cpv'] = cpv
1262                         self.__dict__['version'] = None
1263                 self.__dict__['repo'] = repo
1264                 self.__dict__['slot'] = slot
1265                 self.__dict__['operator'] = op
1266                 self.__dict__['extended_syntax'] = extended_syntax
1267
1268                 if not (repo is None or allow_repo):
1269                         raise InvalidAtom(self)
1270
1271                 if use_str is not None:
1272                         if _use is not None:
1273                                 use = _use
1274                         else:
1275                                 use = _use_dep(use_str[1:-1].split(","), eapi_attrs)
1276                         without_use = Atom(m.group('without_use'), allow_repo=allow_repo)
1277                 else:
1278                         use = None
1279                         if unevaluated_atom is not None and \
1280                                 unevaluated_atom.use is not None:
1281                                 # unevaluated_atom.use is used for IUSE checks when matching
1282                                 # packages, so it must not propagate to without_use
1283                                 without_use = Atom(s, allow_wildcard=allow_wildcard,
1284                                         allow_repo=allow_repo)
1285                         else:
1286                                 without_use = self
1287
1288                 self.__dict__['use'] = use
1289                 self.__dict__['without_use'] = without_use
1290
1291                 if unevaluated_atom:
1292                         self.__dict__['unevaluated_atom'] = unevaluated_atom
1293                 else:
1294                         self.__dict__['unevaluated_atom'] = self
1295
1296                 if eapi is not None:
1297                         if not isinstance(eapi, basestring):
1298                                 raise TypeError('expected eapi argument of ' + \
1299                                         '%s, got %s: %s' % (basestring, type(eapi), eapi,))
1300                         if self.slot and not eapi_attrs.slot_deps:
1301                                 raise InvalidAtom(
1302                                         _("Slot deps are not allowed in EAPI %s: '%s'") \
1303                                         % (eapi, self), category='EAPI.incompatible')
1304                         if self.use:
1305                                 if not eapi_attrs.use_deps:
1306                                         raise InvalidAtom(
1307                                                 _("Use deps are not allowed in EAPI %s: '%s'") \
1308                                                 % (eapi, self), category='EAPI.incompatible')
1309                                 elif not eapi_attrs.use_dep_defaults and \
1310                                         (self.use.missing_enabled or self.use.missing_disabled):
1311                                         raise InvalidAtom(
1312                                                 _("Use dep defaults are not allowed in EAPI %s: '%s'") \
1313                                                 % (eapi, self), category='EAPI.incompatible')
1314                                 if is_valid_flag is not None and self.use.conditional:
1315                                         invalid_flag = None
1316                                         try:
1317                                                 for conditional_type, flags in \
1318                                                         self.use.conditional.items():
1319                                                         for flag in flags:
1320                                                                 if not is_valid_flag(flag):
1321                                                                         invalid_flag = (conditional_type, flag)
1322                                                                         raise StopIteration()
1323                                         except StopIteration:
1324                                                 pass
1325                                         if invalid_flag is not None:
1326                                                 conditional_type, flag = invalid_flag
1327                                                 conditional_str = _use_dep._conditional_strings[conditional_type]
1328                                                 msg = _("USE flag '%s' referenced in " + \
1329                                                         "conditional '%s' in atom '%s' is not in IUSE") \
1330                                                         % (flag, conditional_str % flag, self)
1331                                                 raise InvalidAtom(msg, category='IUSE.missing')
1332                         if self.blocker and self.blocker.overlap.forbid and not eapi_attrs.strong_blocks:
1333                                 raise InvalidAtom(
1334                                         _("Strong blocks are not allowed in EAPI %s: '%s'") \
1335                                                 % (eapi, self), category='EAPI.incompatible')
1336
1337         @property
1338         def without_repo(self):
1339                 if self.repo is None:
1340                         return self
1341                 return Atom(self.replace(_repo_separator + self.repo, '', 1),
1342                         allow_wildcard=True)
1343
1344         @property
1345         def without_slot(self):
1346                 if self.slot is None:
1347                         return self
1348                 return Atom(self.replace(_slot_separator + self.slot, '', 1),
1349                         allow_repo=True, allow_wildcard=True)
1350
1351         def with_repo(self, repo):
1352                 atom = remove_slot(self)
1353                 if self.slot is not None:
1354                         atom += _slot_separator + self.slot
1355                 atom += _repo_separator + repo
1356                 if self.use is not None:
1357                         atom += str(self.use)
1358                 return Atom(atom, allow_repo=True, allow_wildcard=True)
1359
1360         def with_slot(self, slot):
1361                 atom = remove_slot(self) + _slot_separator + slot
1362                 if self.repo is not None:
1363                         atom += _repo_separator + self.repo
1364                 if self.use is not None:
1365                         atom += str(self.use)
1366                 return Atom(atom, allow_repo=True, allow_wildcard=True)
1367
1368         def __setattr__(self, name, value):
1369                 raise AttributeError("Atom instances are immutable",
1370                         self.__class__, name, value)
1371
1372         def intersects(self, other):
1373                 """
1374                 Atoms with different cpv, operator or use attributes cause this method
1375                 to return False even though there may actually be some intersection.
1376                 TODO: Detect more forms of intersection.
1377                 @param other: The package atom to match
1378                 @type other: Atom
1379                 @rtype: Boolean
1380                 @return: True if this atom and the other atom intersect,
1381                         False otherwise.
1382                 """
1383                 if not isinstance(other, Atom):
1384                         raise TypeError("expected %s, got %s" % \
1385                                 (Atom, type(other)))
1386
1387                 if self == other:
1388                         return True
1389
1390                 if self.cp != other.cp or \
1391                         self.use != other.use or \
1392                         self.operator != other.operator or \
1393                         self.cpv != other.cpv:
1394                         return False
1395
1396                 if self.slot is None or \
1397                         other.slot is None or \
1398                         self.slot == other.slot:
1399                         return True
1400
1401                 return False
1402
1403         def evaluate_conditionals(self, use):
1404                 """
1405                 Create an atom instance with any USE conditionals evaluated.
1406                 @param use: The set of enabled USE flags
1407                 @type use: set
1408                 @rtype: Atom
1409                 @return: an atom instance with any USE conditionals evaluated
1410                 """
1411                 if not (self.use and self.use.conditional):
1412                         return self
1413                 atom = remove_slot(self)
1414                 if self.slot:
1415                         atom += ":%s" % self.slot
1416                 use_dep = self.use.evaluate_conditionals(use)
1417                 atom += str(use_dep)
1418                 return Atom(atom, unevaluated_atom=self, allow_repo=(self.repo is not None), _use=use_dep)
1419
1420         def violated_conditionals(self, other_use, is_valid_flag, parent_use=None):
1421                 """
1422                 Create an atom instance with any USE conditional removed, that is
1423                 satisfied by other_use.
1424                 @param other_use: The set of enabled USE flags
1425                 @type other_use: set
1426                 @param is_valid_flag: Function that decides if a use flag is referenceable in use deps
1427                 @type is_valid_flag: function
1428                 @param parent_use: Set of enabled use flags of the package requiring this atom
1429                 @type parent_use: set
1430                 @rtype: Atom
1431                 @return: an atom instance with any satisfied USE conditionals removed
1432                 """
1433                 if not self.use:
1434                         return self
1435                 atom = remove_slot(self)
1436                 if self.slot:
1437                         atom += ":%s" % self.slot
1438                 use_dep = self.use.violated_conditionals(other_use, is_valid_flag, parent_use)
1439                 atom += str(use_dep)
1440                 return Atom(atom, unevaluated_atom=self, allow_repo=(self.repo is not None), _use=use_dep)
1441
1442         def _eval_qa_conditionals(self, use_mask, use_force):
1443                 if not (self.use and self.use.conditional):
1444                         return self
1445                 atom = remove_slot(self)
1446                 if self.slot:
1447                         atom += ":%s" % self.slot
1448                 use_dep = self.use._eval_qa_conditionals(use_mask, use_force)
1449                 atom += str(use_dep)
1450                 return Atom(atom, unevaluated_atom=self, allow_repo=(self.repo is not None), _use=use_dep)
1451
1452         def __copy__(self):
1453                 """Immutable, so returns self."""
1454                 return self
1455
1456         def __deepcopy__(self, memo=None):
1457                 """Immutable, so returns self."""
1458                 memo[id(self)] = self
1459                 return self
1460
1461 _extended_cp_re_cache = {}
1462
1463 def extended_cp_match(extended_cp, other_cp):
1464         """
1465         Checks if an extended syntax cp matches a non extended cp
1466         """
1467         # Escape special '+' and '.' characters which are allowed in atoms,
1468         # and convert '*' to regex equivalent.
1469         global _extended_cp_re_cache
1470         extended_cp_re = _extended_cp_re_cache.get(extended_cp)
1471         if extended_cp_re is None:
1472                 extended_cp_re = re.compile("^" + re.escape(extended_cp).replace(
1473                         r'\*', '[^/]*') + "$")
1474                 _extended_cp_re_cache[extended_cp] = extended_cp_re
1475         return extended_cp_re.match(other_cp) is not None
1476
1477 class ExtendedAtomDict(portage.cache.mappings.MutableMapping):
1478         """
1479         dict() wrapper that supports extended atoms as keys and allows lookup
1480         of a normal cp against other normal cp and extended cp.
1481         The value type has to be given to __init__ and is assumed to be the same
1482         for all values.
1483         """
1484
1485         __slots__ = ('_extended', '_normal', '_value_class')
1486
1487         def __init__(self, value_class):
1488                 self._extended = {}
1489                 self._normal = {}
1490                 self._value_class = value_class
1491
1492         def copy(self):
1493                 result = self.__class__(self._value_class)
1494                 result._extended.update(self._extended)
1495                 result._normal.update(self._normal)
1496                 return result
1497
1498         def __iter__(self):
1499                 for k in self._normal:
1500                         yield k
1501                 for k in self._extended:
1502                         yield k
1503
1504         def iteritems(self):
1505                 try:
1506                         for item in self._normal.items():
1507                                 yield item
1508                         for item in self._extended.items():
1509                                 yield item
1510                 except AttributeError:
1511                         pass # FEATURES=python-trace
1512
1513         def __delitem__(self, cp):
1514                 if "*" in cp:
1515                         return self._extended.__delitem__(cp)
1516                 else:
1517                         return self._normal.__delitem__(cp)
1518
1519         if sys.hexversion >= 0x3000000:
1520                 keys = __iter__
1521                 items = iteritems
1522
1523         def __len__(self):
1524                 return len(self._normal) + len(self._extended)
1525
1526         def setdefault(self, cp, default=None):
1527                 if "*" in cp:
1528                         return self._extended.setdefault(cp, default)
1529                 else:
1530                         return self._normal.setdefault(cp, default)
1531
1532         def __getitem__(self, cp):
1533
1534                 if not isinstance(cp, basestring):
1535                         raise KeyError(cp)
1536
1537                 if '*' in cp:
1538                         return self._extended[cp]
1539
1540                 ret = self._value_class()
1541                 normal_match = self._normal.get(cp)
1542                 match = False
1543
1544                 if normal_match is not None:
1545                         match = True
1546                         if hasattr(ret, "update"):
1547                                 ret.update(normal_match)
1548                         elif hasattr(ret, "extend"):
1549                                 ret.extend(normal_match)
1550                         else:
1551                                 raise NotImplementedError()
1552
1553                 for extended_cp in self._extended:
1554                         if extended_cp_match(extended_cp, cp):
1555                                 match = True
1556                                 if hasattr(ret, "update"):
1557                                         ret.update(self._extended[extended_cp])
1558                                 elif hasattr(ret, "extend"):
1559                                         ret.extend(self._extended[extended_cp])
1560                                 else:
1561                                         raise NotImplementedError()
1562
1563                 if not match:
1564                         raise KeyError(cp)
1565
1566                 return ret
1567
1568         def __setitem__(self, cp, val):
1569                 if "*" in cp:
1570                         self._extended[cp] = val
1571                 else:
1572                         self._normal[cp] = val
1573
1574         def __eq__(self, other):
1575                 return self._value_class == other._value_class and \
1576                         self._extended == other._extended and \
1577                         self._normal == other._normal
1578
1579         def clear(self):
1580                 self._extended.clear()
1581                 self._normal.clear()
1582
1583
1584 def get_operator(mydep):
1585         """
1586         Return the operator used in a depstring.
1587
1588         Example usage:
1589                 >>> from portage.dep import *
1590                 >>> get_operator(">=test-1.0")
1591                 '>='
1592
1593         @param mydep: The dep string to check
1594         @type mydep: String
1595         @rtype: String
1596         @return: The operator. One of:
1597                 '~', '=', '>', '<', '=*', '>=', or '<='
1598         """
1599         if not isinstance(mydep, Atom):
1600                 mydep = Atom(mydep)
1601
1602         return mydep.operator
1603
1604 def dep_getcpv(mydep):
1605         """
1606         Return the category-package-version with any operators/slot specifications stripped off
1607
1608         Example usage:
1609                 >>> dep_getcpv('>=media-libs/test-3.0')
1610                 'media-libs/test-3.0'
1611
1612         @param mydep: The depstring
1613         @type mydep: String
1614         @rtype: String
1615         @return: The depstring with the operator removed
1616         """
1617         if not isinstance(mydep, Atom):
1618                 mydep = Atom(mydep)
1619
1620         return mydep.cpv
1621
1622 def dep_getslot(mydep):
1623         """
1624         Retrieve the slot on a depend.
1625
1626         Example usage:
1627                 >>> dep_getslot('app-misc/test:3')
1628                 '3'
1629
1630         @param mydep: The depstring to retrieve the slot of
1631         @type mydep: String
1632         @rtype: String
1633         @return: The slot
1634         """
1635         slot = getattr(mydep, "slot", False)
1636         if slot is not False:
1637                 return slot
1638
1639         #remove repo_name if present
1640         mydep = mydep.split(_repo_separator)[0]
1641
1642         colon = mydep.find(_slot_separator)
1643         if colon != -1:
1644                 bracket = mydep.find("[", colon)
1645                 if bracket == -1:
1646                         return mydep[colon+1:]
1647                 else:
1648                         return mydep[colon+1:bracket]
1649         return None
1650
1651 def dep_getrepo(mydep):
1652         """
1653         Retrieve the repo on a depend.
1654
1655         Example usage:
1656                 >>> dep_getrepo('app-misc/test::repository')
1657                 'repository'
1658
1659         @param mydep: The depstring to retrieve the repository of
1660         @type mydep: String
1661         @rtype: String
1662         @return: The repository name
1663         """
1664         repo = getattr(mydep, "repo", False)
1665         if repo is not False:
1666                 return repo
1667
1668         metadata = getattr(mydep, "metadata", False)
1669         if metadata:
1670                 repo = metadata.get('repository', False)
1671                 if repo is not False:
1672                         return repo
1673
1674         colon = mydep.find(_repo_separator)
1675         if colon != -1:
1676                 bracket = mydep.find("[", colon)
1677                 if bracket == -1:
1678                         return mydep[colon+2:]
1679                 else:
1680                         return mydep[colon+2:bracket]
1681         return None
1682 def remove_slot(mydep):
1683         """
1684         Removes dep components from the right side of an atom:
1685                 * slot
1686                 * use
1687                 * repo
1688         And repo_name from the left side.
1689         """
1690         colon = mydep.find(_slot_separator)
1691         if colon != -1:
1692                 mydep = mydep[:colon]
1693         else:
1694                 bracket = mydep.find("[")
1695                 if bracket != -1:
1696                         mydep = mydep[:bracket]
1697         return mydep
1698
1699 def dep_getusedeps( depend ):
1700         """
1701         Pull a listing of USE Dependencies out of a dep atom.
1702
1703         Example usage:
1704                 >>> dep_getusedeps('app-misc/test:3[foo,-bar]')
1705                 ('foo', '-bar')
1706
1707         @param depend: The depstring to process
1708         @type depend: String
1709         @rtype: List
1710         @return: List of use flags ( or [] if no flags exist )
1711         """
1712         use_list = []
1713         open_bracket = depend.find('[')
1714         # -1 = failure (think c++ string::npos)
1715         comma_separated = False
1716         bracket_count = 0
1717         while( open_bracket != -1 ):
1718                 bracket_count += 1
1719                 if bracket_count > 1:
1720                         raise InvalidAtom(_("USE Dependency with more "
1721                                 "than one set of brackets: %s") % (depend,))
1722                 close_bracket = depend.find(']', open_bracket )
1723                 if close_bracket == -1:
1724                         raise InvalidAtom(_("USE Dependency with no closing bracket: %s") % depend )
1725                 use = depend[open_bracket + 1: close_bracket]
1726                 # foo[1:1] may return '' instead of None, we don't want '' in the result
1727                 if not use:
1728                         raise InvalidAtom(_("USE Dependency with "
1729                                 "no use flag ([]): %s") % depend )
1730                 if not comma_separated:
1731                         comma_separated = "," in use
1732
1733                 if comma_separated and bracket_count > 1:
1734                         raise InvalidAtom(_("USE Dependency contains a mixture of "
1735                                 "comma and bracket separators: %s") % depend )
1736
1737                 if comma_separated:
1738                         for x in use.split(","):
1739                                 if x:
1740                                         use_list.append(x)
1741                                 else:
1742                                         raise InvalidAtom(_("USE Dependency with no use "
1743                                                 "flag next to comma: %s") % depend )
1744                 else:
1745                         use_list.append(use)
1746
1747                 # Find next use flag
1748                 open_bracket = depend.find( '[', open_bracket+1 )
1749         return tuple(use_list)
1750
1751 def isvalidatom(atom, allow_blockers=False, allow_wildcard=False, allow_repo=False):
1752         """
1753         Check to see if a depend atom is valid
1754
1755         Example usage:
1756                 >>> isvalidatom('media-libs/test-3.0')
1757                 False
1758                 >>> isvalidatom('>=media-libs/test-3.0')
1759                 True
1760
1761         @param atom: The depend atom to check against
1762         @type atom: String or Atom
1763         @rtype: Boolean
1764         @return: One of the following:
1765                 1) False if the atom is invalid
1766                 2) True if the atom is valid
1767         """
1768         try:
1769                 if not isinstance(atom, Atom):
1770                         atom = Atom(atom, allow_wildcard=allow_wildcard, allow_repo=allow_repo)
1771                 if not allow_blockers and atom.blocker:
1772                         return False
1773                 return True
1774         except InvalidAtom:
1775                 return False
1776
1777 def isjustname(mypkg):
1778         """
1779         Checks to see if the atom is only the package name (no version parts).
1780
1781         Example usage:
1782                 >>> isjustname('=media-libs/test-3.0')
1783                 False
1784                 >>> isjustname('media-libs/test')
1785                 True
1786
1787         @param mypkg: The package atom to check
1788         @param mypkg: String or Atom
1789         @rtype: Integer
1790         @return: One of the following:
1791                 1) False if the package string is not just the package name
1792                 2) True if it is
1793         """
1794         try:
1795                 if not isinstance(mypkg, Atom):
1796                         mypkg = Atom(mypkg)
1797                 return mypkg == mypkg.cp
1798         except InvalidAtom:
1799                 pass
1800
1801         for x in mypkg.split('-')[-2:]:
1802                 if ververify(x):
1803                         return False
1804         return True
1805
1806 def isspecific(mypkg):
1807         """
1808         Checks to see if a package is in =category/package-version or
1809         package-version format.
1810
1811         Example usage:
1812                 >>> isspecific('media-libs/test')
1813                 False
1814                 >>> isspecific('=media-libs/test-3.0')
1815                 True
1816
1817         @param mypkg: The package depstring to check against
1818         @type mypkg: String
1819         @rtype: Boolean
1820         @return: One of the following:
1821                 1) False if the package string is not specific
1822                 2) True if it is
1823         """
1824         try:
1825                 if not isinstance(mypkg, Atom):
1826                         mypkg = Atom(mypkg)
1827                 return mypkg != mypkg.cp
1828         except InvalidAtom:
1829                 pass
1830
1831         # Fall back to legacy code for backward compatibility.
1832         return not isjustname(mypkg)
1833
1834 def dep_getkey(mydep):
1835         """
1836         Return the category/package-name of a depstring.
1837
1838         Example usage:
1839                 >>> dep_getkey('=media-libs/test-3.0')
1840                 'media-libs/test'
1841
1842         @param mydep: The depstring to retrieve the category/package-name of
1843         @type mydep: String
1844         @rtype: String
1845         @return: The package category/package-name
1846         """
1847         if not isinstance(mydep, Atom):
1848                 mydep = Atom(mydep, allow_wildcard=True, allow_repo=True)
1849
1850         return mydep.cp
1851
1852 def match_to_list(mypkg, mylist):
1853         """
1854         Searches list for entries that matches the package.
1855
1856         @param mypkg: The package atom to match
1857         @type mypkg: String
1858         @param mylist: The list of package atoms to compare against
1859         @param mylist: List
1860         @rtype: List
1861         @return: A unique list of package atoms that match the given package atom
1862         """
1863         matches = set()
1864         result = []
1865         pkgs = [mypkg]
1866         for x in mylist:
1867                 if x not in matches and match_from_list(x, pkgs):
1868                         matches.add(x)
1869                         result.append(x)
1870         return result
1871
1872 def best_match_to_list(mypkg, mylist):
1873         """
1874         Returns the most specific entry that matches the package given.
1875
1876         @param mypkg: The package atom to check
1877         @type mypkg: String
1878         @param mylist: The list of package atoms to check against
1879         @type mylist: List
1880         @rtype: String
1881         @return: The package atom which best matches given the following ordering:
1882                 - =cpv      6
1883                 - ~cpv      5
1884                 - =cpv*     4
1885                 - cp:slot   3
1886                 - >cpv      2
1887                 - <cpv      2
1888                 - >=cpv     2
1889                 - <=cpv     2
1890                 - cp        1
1891                 - cp:slot with extended syntax  0
1892                 - cp with extended syntax       -1
1893         """
1894         operator_values = {'=':6, '~':5, '=*':4,
1895                 '>':2, '<':2, '>=':2, '<=':2, None:1}
1896         maxvalue = -2
1897         bestm  = None
1898         mypkg_cpv = None
1899         for x in match_to_list(mypkg, mylist):
1900                 if x.extended_syntax:
1901                         if dep_getslot(x) is not None:
1902                                 if maxvalue < 0:
1903                                         maxvalue = 0
1904                                         bestm = x
1905                         else:
1906                                 if maxvalue < -1:
1907                                         maxvalue = -1
1908                                         bestm = x
1909                         continue
1910                 if dep_getslot(x) is not None:
1911                         if maxvalue < 3:
1912                                 maxvalue = 3
1913                                 bestm = x
1914                 op_val = operator_values[x.operator]
1915                 if op_val > maxvalue:
1916                         maxvalue = op_val
1917                         bestm  = x
1918                 elif op_val == maxvalue and op_val == 2:
1919                         # For >, <, >=, and <=, the one with the version
1920                         # closest to mypkg is the best match.
1921                         if mypkg_cpv is None:
1922                                 try:
1923                                         mypkg_cpv = mypkg.cpv
1924                                 except AttributeError:
1925                                         mypkg_cpv = _pkg_str(remove_slot(mypkg))
1926                         if bestm.cpv == mypkg_cpv or bestm.cpv == x.cpv:
1927                                 pass
1928                         elif x.cpv == mypkg_cpv:
1929                                 bestm = x
1930                         else:
1931                                 # Sort the cpvs to find the one closest to mypkg_cpv
1932                                 cpv_list = [bestm.cpv, mypkg_cpv, x.cpv]
1933                                 def cmp_cpv(cpv1, cpv2):
1934                                         return vercmp(cpv1.version, cpv2.version)
1935                                 cpv_list.sort(key=cmp_sort_key(cmp_cpv))
1936                                 if cpv_list[0] is mypkg_cpv or cpv_list[-1] is mypkg_cpv:
1937                                         if cpv_list[1] is x.cpv:
1938                                                 bestm = x
1939                                 else:
1940                                         # TODO: handle the case where mypkg_cpv is in the middle
1941                                         pass
1942
1943         return bestm
1944
1945 def match_from_list(mydep, candidate_list):
1946         """
1947         Searches list for entries that matches the package.
1948
1949         @param mydep: The package atom to match
1950         @type mydep: String
1951         @param candidate_list: The list of package atoms to compare against
1952         @param candidate_list: List
1953         @rtype: List
1954         @return: A list of package atoms that match the given package atom
1955         """
1956
1957         if not candidate_list:
1958                 return []
1959
1960         if "!" == mydep[:1]:
1961                 if "!" == mydep[1:2]:
1962                         mydep = mydep[2:]
1963                 else:
1964                         mydep = mydep[1:]
1965         if not isinstance(mydep, Atom):
1966                 mydep = Atom(mydep, allow_wildcard=True, allow_repo=True)
1967
1968         mycpv     = mydep.cpv
1969         mycpv_cps = catpkgsplit(mycpv) # Can be None if not specific
1970         slot      = mydep.slot
1971
1972         if not mycpv_cps:
1973                 cat, pkg = catsplit(mycpv)
1974                 ver      = None
1975                 rev      = None
1976         else:
1977                 cat, pkg, ver, rev = mycpv_cps
1978                 if mydep == mycpv:
1979                         raise KeyError(_("Specific key requires an operator"
1980                                 " (%s) (try adding an '=')") % (mydep))
1981
1982         if ver and rev:
1983                 operator = mydep.operator
1984                 if not operator:
1985                         writemsg(_("!!! Invalid atom: %s\n") % mydep, noiselevel=-1)
1986                         return []
1987         else:
1988                 operator = None
1989
1990         mylist = []
1991
1992         if operator is None:
1993                 for x in candidate_list:
1994                         cp = getattr(x, "cp", None)
1995                         if cp is None:
1996                                 mysplit = catpkgsplit(remove_slot(x))
1997                                 if mysplit is not None:
1998                                         cp = mysplit[0] + '/' + mysplit[1]
1999
2000                         if cp is None:
2001                                 continue
2002
2003                         if cp == mycpv or (mydep.extended_syntax and \
2004                                 extended_cp_match(mydep.cp, cp)):
2005                                 mylist.append(x)
2006
2007         elif operator == "=": # Exact match
2008                 for x in candidate_list:
2009                         xcpv = getattr(x, "cpv", None)
2010                         if xcpv is None:
2011                                 xcpv = remove_slot(x)
2012                         if not cpvequal(xcpv, mycpv):
2013                                 continue
2014                         mylist.append(x)
2015
2016         elif operator == "=*": # glob match
2017                 # XXX: Nasty special casing for leading zeros
2018                 # Required as =* is a literal prefix match, so can't
2019                 # use vercmp
2020                 mysplit = catpkgsplit(mycpv)
2021                 myver = mysplit[2].lstrip("0")
2022                 if not myver or not myver[0].isdigit():
2023                         myver = "0"+myver
2024                 mycpv_cmp = mysplit[0]+"/"+mysplit[1]+"-"+myver
2025                 for x in candidate_list:
2026                         xs = getattr(x, "cpv_split", None)
2027                         if xs is None:
2028                                 xs = catpkgsplit(remove_slot(x))
2029                         myver = xs[2].lstrip("0")
2030                         if not myver or not myver[0].isdigit():
2031                                 myver = "0"+myver
2032                         xcpv = xs[0]+"/"+xs[1]+"-"+myver
2033                         if xcpv.startswith(mycpv_cmp):
2034                                 mylist.append(x)
2035
2036         elif operator == "~": # version, any revision, match
2037                 for x in candidate_list:
2038                         xs = getattr(x, "cpv_split", None)
2039                         if xs is None:
2040                                 xs = catpkgsplit(remove_slot(x))
2041                         if xs is None:
2042                                 raise InvalidData(x)
2043                         if not cpvequal(xs[0]+"/"+xs[1]+"-"+xs[2], mycpv_cps[0]+"/"+mycpv_cps[1]+"-"+mycpv_cps[2]):
2044                                 continue
2045                         if xs[2] != ver:
2046                                 continue
2047                         mylist.append(x)
2048
2049         elif operator in [">", ">=", "<", "<="]:
2050                 for x in candidate_list:
2051                         if hasattr(x, 'cp'):
2052                                 pkg = x
2053                         else:
2054                                 try:
2055                                         pkg = _pkg_str(remove_slot(x))
2056                                 except InvalidData:
2057                                         continue
2058
2059                         if pkg.cp != mydep.cp:
2060                                 continue
2061                         try:
2062                                 result = vercmp(pkg.version, mydep.version)
2063                         except ValueError: # pkgcmp may return ValueError during int() conversion
2064                                 writemsg(_("\nInvalid package name: %s\n") % x, noiselevel=-1)
2065                                 raise
2066                         if result is None:
2067                                 continue
2068                         elif operator == ">":
2069                                 if result > 0:
2070                                         mylist.append(x)
2071                         elif operator == ">=":
2072                                 if result >= 0:
2073                                         mylist.append(x)
2074                         elif operator == "<":
2075                                 if result < 0:
2076                                         mylist.append(x)
2077                         elif operator == "<=":
2078                                 if result <= 0:
2079                                         mylist.append(x)
2080                         else:
2081                                 raise KeyError(_("Unknown operator: %s") % mydep)
2082         else:
2083                 raise KeyError(_("Unknown operator: %s") % mydep)
2084
2085         if slot is not None and not mydep.extended_syntax:
2086                 candidate_list = mylist
2087                 mylist = []
2088                 for x in candidate_list:
2089                         xslot = getattr(x, "slot", False)
2090                         if xslot is False:
2091                                 xslot = dep_getslot(x)
2092                         if xslot is not None and xslot != slot:
2093                                 continue
2094                         mylist.append(x)
2095
2096         if mydep.unevaluated_atom.use:
2097                 candidate_list = mylist
2098                 mylist = []
2099                 for x in candidate_list:
2100                         use = getattr(x, "use", None)
2101                         if use is not None:
2102                                 if mydep.unevaluated_atom.use and \
2103                                         not x.iuse.is_valid_flag(
2104                                         mydep.unevaluated_atom.use.required):
2105                                         continue
2106
2107                                 if mydep.use:
2108
2109                                         missing_enabled = mydep.use.missing_enabled.difference(x.iuse.all)
2110                                         missing_disabled = mydep.use.missing_disabled.difference(x.iuse.all)
2111
2112                                         if mydep.use.enabled:
2113                                                 if any(f in mydep.use.enabled for f in missing_disabled):
2114                                                         continue
2115                                                 need_enabled = mydep.use.enabled.difference(use.enabled)
2116                                                 if need_enabled:
2117                                                         if any(f not in missing_enabled for f in need_enabled):
2118                                                                 continue
2119
2120                                         if mydep.use.disabled:
2121                                                 if any(f in mydep.use.disabled for f in missing_enabled):
2122                                                         continue
2123                                                 need_disabled = mydep.use.disabled.intersection(use.enabled)
2124                                                 if need_disabled:
2125                                                         if any(f not in missing_disabled for f in need_disabled):
2126                                                                 continue
2127
2128                         mylist.append(x)
2129
2130         if mydep.repo:
2131                 candidate_list = mylist
2132                 mylist = []
2133                 for x in candidate_list:
2134                         repo = getattr(x, "repo", False)
2135                         if repo is False:
2136                                 repo = dep_getrepo(x)
2137                         if repo is not None and repo != _unknown_repo and \
2138                                 repo != mydep.repo:
2139                                 continue
2140                         mylist.append(x)
2141
2142         return mylist
2143
2144 def human_readable_required_use(required_use):
2145         return required_use.replace("^^", "exactly-one-of").replace("||", "any-of")
2146
2147 def get_required_use_flags(required_use):
2148         """
2149         Returns a set of use flags that are used in the given REQUIRED_USE string
2150
2151         @param required_use: REQUIRED_USE string
2152         @type required_use: String
2153         @rtype: Set
2154         @return: Set of use flags that are used in the given REQUIRED_USE string
2155         """
2156
2157         mysplit = required_use.split()
2158         level = 0
2159         stack = [[]]
2160         need_bracket = False
2161
2162         used_flags = set()
2163
2164         def register_token(token):
2165                 if token.endswith("?"):
2166                         token = token[:-1]
2167                 if token.startswith("!"):
2168                         token = token[1:]
2169                 used_flags.add(token)
2170
2171         for token in mysplit:
2172                 if token == "(":
2173                         need_bracket = False
2174                         stack.append([])
2175                         level += 1
2176                 elif token == ")":
2177                         if need_bracket:
2178                                 raise InvalidDependString(
2179                                         _("malformed syntax: '%s'") % required_use)
2180                         if level > 0:
2181                                 level -= 1
2182                                 l = stack.pop()
2183                                 ignore = False
2184                                 if stack[level]:
2185                                         if stack[level][-1] in ("||", "^^") or \
2186                                                 (not isinstance(stack[level][-1], bool) and \
2187                                                 stack[level][-1][-1] == "?"):
2188                                                 ignore = True
2189                                                 stack[level].pop()
2190                                                 stack[level].append(True)
2191
2192                                 if l and not ignore:
2193                                         stack[level].append(all(x for x in l))
2194                         else:
2195                                 raise InvalidDependString(
2196                                         _("malformed syntax: '%s'") % required_use)
2197                 elif token in ("||", "^^"):
2198                         if need_bracket:
2199                                 raise InvalidDependString(
2200                                         _("malformed syntax: '%s'") % required_use)
2201                         need_bracket = True
2202                         stack[level].append(token)
2203                 else:
2204                         if need_bracket or "(" in token or ")" in token or \
2205                                 "|" in token or "^" in token:
2206                                 raise InvalidDependString(
2207                                         _("malformed syntax: '%s'") % required_use)
2208
2209                         if token[-1] == "?":
2210                                 need_bracket = True
2211                                 stack[level].append(token)
2212                         else:
2213                                 stack[level].append(True)
2214
2215                         register_token(token)
2216
2217         if level != 0 or need_bracket:
2218                 raise InvalidDependString(
2219                         _("malformed syntax: '%s'") % required_use)
2220
2221         return frozenset(used_flags)
2222
2223 class _RequiredUseLeaf(object):
2224
2225         __slots__ = ('_satisfied', '_token')
2226
2227         def __init__(self, token, satisfied):
2228                 self._token = token
2229                 self._satisfied = satisfied
2230
2231         def tounicode(self):
2232                 return self._token
2233
2234 class _RequiredUseBranch(object):
2235
2236         __slots__ = ('_children', '_operator', '_parent', '_satisfied')
2237
2238         def __init__(self, operator=None, parent=None):
2239                 self._children = []
2240                 self._operator = operator
2241                 self._parent = parent
2242                 self._satisfied = False
2243
2244         def __bool__(self):
2245                 return self._satisfied
2246
2247         def tounicode(self):
2248
2249                 include_parens = self._parent is not None
2250                 tokens = []
2251                 if self._operator is not None:
2252                         tokens.append(self._operator)
2253
2254                 if include_parens:
2255                         tokens.append("(")
2256
2257                 complex_nesting = False
2258                 node = self
2259                 while node != None and not complex_nesting:
2260                         if node._operator in ("||", "^^"):
2261                                 complex_nesting = True
2262                         else:
2263                                 node = node._parent
2264
2265                 if complex_nesting:
2266                         for child in self._children:
2267                                 tokens.append(child.tounicode())
2268                 else:
2269                         for child in self._children:
2270                                 if not child._satisfied:
2271                                         tokens.append(child.tounicode())
2272
2273                 if include_parens:
2274                         tokens.append(")")
2275
2276                 return " ".join(tokens)
2277
2278         if sys.hexversion < 0x3000000:
2279                 __nonzero__ = __bool__
2280
2281 def check_required_use(required_use, use, iuse_match):
2282         """
2283         Checks if the use flags listed in 'use' satisfy all
2284         constraints specified in 'constraints'.
2285
2286         @param required_use: REQUIRED_USE string
2287         @type required_use: String
2288         @param use: Enabled use flags
2289         @param use: List
2290         @param iuse_match: Callable that takes a single flag argument and returns
2291                 True if the flag is matched, false otherwise,
2292         @param iuse_match: Callable
2293         @rtype: Bool
2294         @return: Indicates if REQUIRED_USE constraints are satisfied
2295         """
2296
2297         def is_active(token):
2298                 if token.startswith("!"):
2299                         flag = token[1:]
2300                         is_negated = True
2301                 else:
2302                         flag = token
2303                         is_negated = False
2304
2305                 if not flag or not iuse_match(flag):
2306                         msg = _("USE flag '%s' is not in IUSE") \
2307                                 % (flag,)
2308                         e = InvalidData(msg, category='IUSE.missing')
2309                         raise InvalidDependString(msg, errors=(e,))
2310
2311                 return (flag in use and not is_negated) or \
2312                         (flag not in use and is_negated)
2313
2314         def is_satisfied(operator, argument):
2315                 if not argument:
2316                         #|| ( ) -> True
2317                         return True
2318
2319                 if operator == "||":
2320                         return (True in argument)
2321                 elif operator == "^^":
2322                         return (argument.count(True) == 1)
2323                 elif operator[-1] == "?":
2324                         return (False not in argument)
2325
2326         mysplit = required_use.split()
2327         level = 0
2328         stack = [[]]
2329         tree = _RequiredUseBranch()
2330         node = tree
2331         need_bracket = False
2332
2333         for token in mysplit:
2334                 if token == "(":
2335                         if not need_bracket:
2336                                 child = _RequiredUseBranch(parent=node)
2337                                 node._children.append(child)
2338                                 node = child
2339
2340                         need_bracket = False
2341                         stack.append([])
2342                         level += 1
2343                 elif token == ")":
2344                         if need_bracket:
2345                                 raise InvalidDependString(
2346                                         _("malformed syntax: '%s'") % required_use)
2347                         if level > 0:
2348                                 level -= 1
2349                                 l = stack.pop()
2350                                 op = None
2351                                 if stack[level]:
2352                                         if stack[level][-1] in ("||", "^^"):
2353                                                 op = stack[level].pop()
2354                                                 satisfied = is_satisfied(op, l)
2355                                                 stack[level].append(satisfied)
2356                                                 node._satisfied = satisfied
2357
2358                                         elif not isinstance(stack[level][-1], bool) and \
2359                                                 stack[level][-1][-1] == "?":
2360                                                 op = stack[level].pop()
2361                                                 if is_active(op[:-1]):
2362                                                         satisfied = is_satisfied(op, l)
2363                                                         stack[level].append(satisfied)
2364                                                         node._satisfied = satisfied
2365                                                 else:
2366                                                         node._satisfied = True
2367                                                         last_node = node._parent._children.pop()
2368                                                         if last_node is not node:
2369                                                                 raise AssertionError(
2370                                                                         "node is not last child of parent")
2371                                                         node = node._parent
2372                                                         continue
2373
2374                                 if op is None:
2375                                         satisfied = False not in l
2376                                         node._satisfied = satisfied
2377                                         if l:
2378                                                 stack[level].append(satisfied)
2379
2380                                         if len(node._children) <= 1 or \
2381                                                 node._parent._operator not in ("||", "^^"):
2382                                                 last_node = node._parent._children.pop()
2383                                                 if last_node is not node:
2384                                                         raise AssertionError(
2385                                                                 "node is not last child of parent")
2386                                                 for child in node._children:
2387                                                         node._parent._children.append(child)
2388                                                         if isinstance(child, _RequiredUseBranch):
2389                                                                 child._parent = node._parent
2390
2391                                 elif not node._children:
2392                                         last_node = node._parent._children.pop()
2393                                         if last_node is not node:
2394                                                 raise AssertionError(
2395                                                         "node is not last child of parent")
2396
2397                                 elif len(node._children) == 1 and op in ("||", "^^"):
2398                                         last_node = node._parent._children.pop()
2399                                         if last_node is not node:
2400                                                 raise AssertionError(
2401                                                         "node is not last child of parent")
2402                                         node._parent._children.append(node._children[0])
2403                                         if isinstance(node._children[0], _RequiredUseBranch):
2404                                                 node._children[0]._parent = node._parent
2405                                                 node = node._children[0]
2406                                                 if node._operator is None and \
2407                                                         node._parent._operator not in ("||", "^^"):
2408                                                         last_node = node._parent._children.pop()
2409                                                         if last_node is not node:
2410                                                                 raise AssertionError(
2411                                                                         "node is not last child of parent")
2412                                                         for child in node._children:
2413                                                                 node._parent._children.append(child)
2414                                                                 if isinstance(child, _RequiredUseBranch):
2415                                                                         child._parent = node._parent
2416
2417                                 node = node._parent
2418                         else:
2419                                 raise InvalidDependString(
2420                                         _("malformed syntax: '%s'") % required_use)
2421                 elif token in ("||", "^^"):
2422                         if need_bracket:
2423                                 raise InvalidDependString(
2424                                         _("malformed syntax: '%s'") % required_use)
2425                         need_bracket = True
2426                         stack[level].append(token)
2427                         child = _RequiredUseBranch(operator=token, parent=node)
2428                         node._children.append(child)
2429                         node = child
2430                 else:
2431                         if need_bracket or "(" in token or ")" in token or \
2432                                 "|" in token or "^" in token:
2433                                 raise InvalidDependString(
2434                                         _("malformed syntax: '%s'") % required_use)
2435
2436                         if token[-1] == "?":
2437                                 need_bracket = True
2438                                 stack[level].append(token)
2439                                 child = _RequiredUseBranch(operator=token, parent=node)
2440                                 node._children.append(child)
2441                                 node = child
2442                         else:
2443                                 satisfied = is_active(token)
2444                                 stack[level].append(satisfied)
2445                                 node._children.append(_RequiredUseLeaf(token, satisfied))
2446
2447         if level != 0 or need_bracket:
2448                 raise InvalidDependString(
2449                         _("malformed syntax: '%s'") % required_use)
2450
2451         tree._satisfied = False not in stack[0]
2452         return tree
2453
2454 def extract_affecting_use(mystr, atom, eapi=None):
2455         """
2456         Take a dep string and an atom and return the use flags
2457         that decide if the given atom is in effect.
2458
2459         Example usage:
2460                 >>> extract_use_cond('sasl? ( dev-libs/cyrus-sasl ) \
2461                         !minimal? ( cxx? ( dev-libs/cyrus-sasl ) )', 'dev-libs/cyrus-sasl')
2462                 (['sasl', 'minimal', 'cxx'])
2463
2464         @param dep: The dependency string
2465         @type mystr: String
2466         @param atom: The atom to get into effect
2467         @type atom: String
2468         @rtype: Tuple of two lists of strings
2469         @return: List of use flags that need to be enabled, List of use flag that need to be disabled
2470         """
2471         useflag_re = _get_useflag_re(eapi)
2472         mysplit = mystr.split()
2473         level = 0
2474         stack = [[]]
2475         need_bracket = False
2476         affecting_use = set()
2477
2478         def flag(conditional):
2479                 if conditional[0] == "!":
2480                         flag = conditional[1:-1]
2481                 else:
2482                         flag = conditional[:-1]
2483
2484                 if useflag_re.match(flag) is None:
2485                         raise InvalidDependString(
2486                                 _("invalid use flag '%s' in conditional '%s'") % \
2487                                 (flag, conditional))
2488
2489                 return flag
2490
2491         for token in mysplit:
2492                 if token == "(":
2493                         need_bracket = False
2494                         stack.append([])
2495                         level += 1
2496                 elif token == ")":
2497                         if need_bracket:
2498                                 raise InvalidDependString(
2499                                         _("malformed syntax: '%s'") % mystr)
2500                         if level > 0:
2501                                 level -= 1
2502                                 l = stack.pop()
2503                                 is_single = (len(l) == 1 or (len(l)==2 and (l[0] == "||" or l[0][-1] == "?")))
2504
2505                                 def ends_in_any_of_dep(k):
2506                                         return k>=0 and stack[k] and stack[k][-1] == "||"
2507
2508                                 def ends_in_operator(k):
2509                                         return k>=0 and stack[k] and (stack[k][-1] == "||" or stack[k][-1][-1] == "?")
2510
2511                                 def special_append():
2512                                         """
2513                                         Use extend instead of append if possible. This kills all redundant brackets.
2514                                         """
2515                                         if is_single and (not stack[level] or not stack[level][-1][-1] == "?"):
2516                                                 if len(l) == 1 and isinstance(l[0], list):
2517                                                         # l = [[...]]
2518                                                         stack[level].extend(l[0])
2519                                                 else:
2520                                                         stack[level].extend(l)
2521                                         else:
2522                                                 stack[level].append(l)
2523
2524                                 if l:
2525                                         if not ends_in_any_of_dep(level-1) and not ends_in_operator(level):
2526                                                 #Optimize: ( ( ... ) ) -> ( ... ). Make sure there is no '||' hanging around.
2527                                                 stack[level].extend(l)
2528                                         elif not stack[level]:
2529                                                 #An '||' in the level above forces us to keep to brackets.
2530                                                 special_append()
2531                                         elif len(l) == 1 and ends_in_any_of_dep(level):
2532                                                 #Optimize: || ( A ) -> A
2533                                                 stack[level].pop()
2534                                                 special_append()
2535                                         elif len(l) == 2 and (l[0] == "||" or l[0][-1] == "?") and stack[level][-1] in (l[0], "||"):
2536                                                 #Optimize:      || ( || ( ... ) ) -> || ( ... )
2537                                                 #                       foo? ( foo? ( ... ) ) -> foo? ( ... )
2538                                                 #                       || ( foo? ( ... ) ) -> foo? ( ... )
2539                                                 stack[level].pop()
2540                                                 special_append()
2541                                                 if l[0][-1] == "?":
2542                                                         affecting_use.add(flag(l[0]))
2543                                         else:
2544                                                 if stack[level] and stack[level][-1][-1] == "?":
2545                                                         affecting_use.add(flag(stack[level][-1]))
2546                                                 special_append()
2547                                 else:
2548                                         if stack[level] and (stack[level][-1] == "||" or stack[level][-1][-1] == "?"):
2549                                                 stack[level].pop()
2550                         else:
2551                                 raise InvalidDependString(
2552                                         _("malformed syntax: '%s'") % mystr)
2553                 elif token == "||":
2554                         if need_bracket:
2555                                 raise InvalidDependString(
2556                                         _("malformed syntax: '%s'") % mystr)
2557                         need_bracket = True
2558                         stack[level].append(token)
2559                 else:
2560                         if need_bracket:
2561                                 raise InvalidDependString(
2562                                         _("malformed syntax: '%s'") % mystr)
2563
2564                         if token[-1] == "?":
2565                                 need_bracket = True
2566                                 stack[level].append(token)
2567                         elif token == atom:
2568                                 stack[level].append(token)
2569
2570         if level != 0 or need_bracket:
2571                 raise InvalidDependString(
2572                         _("malformed syntax: '%s'") % mystr)
2573
2574         return affecting_use