BaseTools/Source/Python/Common/RangeExpression.py

   1 # # @file
   2 # This file is used to parse and evaluate range expression in Pcd declaration.
   3 #
   4 # Copyright (c) 2015 - 2018, Intel Corporation. All rights reserved.<BR>
   5 # This program and the accompanying materials
   6 # are licensed and made available under the terms and conditions of the BSD License
   7 # which accompanies this distribution.    The full text of the license may be found at
   8 # http://opensource.org/licenses/bsd-license.php
   9 #
  10 # THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  12
  13 # # Import Modules
  14 #
  15 from Common.GlobalData import *
  16 from CommonDataClass.Exceptions import BadExpression
  17 from CommonDataClass.Exceptions import WrnExpression
  18 import uuid
  19 from Common.Expression import PcdPattern
  20
  21 ERR_STRING_EXPR = 'This operator cannot be used in string expression: [%s].'
  22 ERR_SNYTAX = 'Syntax error, the rest of expression cannot be evaluated: [%s].'
  23 ERR_MATCH = 'No matching right parenthesis.'
  24 ERR_STRING_TOKEN = 'Bad string token: [%s].'
  25 ERR_MACRO_TOKEN = 'Bad macro token: [%s].'
  26 ERR_EMPTY_TOKEN = 'Empty token is not allowed.'
  27 ERR_PCD_RESOLVE = 'PCD token cannot be resolved: [%s].'
  28 ERR_VALID_TOKEN = 'No more valid token found from rest of string: [%s].'
  29 ERR_EXPR_TYPE = 'Different types found in expression.'
  30 ERR_OPERATOR_UNSUPPORT = 'Unsupported operator: [%s]'
  31 ERR_REL_NOT_IN = 'Expect "IN" after "not" operator.'
  32 WRN_BOOL_EXPR = 'Operand of boolean type cannot be used in arithmetic expression.'
  33 WRN_EQCMP_STR_OTHERS = '== Comparison between Operand of string type and Boolean/Number Type always return False.'
  34 WRN_NECMP_STR_OTHERS = '!= Comparison between Operand of string type and Boolean/Number Type always return True.'
  35 ERR_RELCMP_STR_OTHERS = 'Operator taking Operand of string type and Boolean/Number Type is not allowed: [%s].'
  36 ERR_STRING_CMP = 'Unicode string and general string cannot be compared: [%s %s %s]'
  37 ERR_ARRAY_TOKEN = 'Bad C array or C format GUID token: [%s].'
  38 ERR_ARRAY_ELE = 'This must be HEX value for NList or Array: [%s].'
  39 ERR_EMPTY_EXPR = 'Empty expression is not allowed.'
  40 ERR_IN_OPERAND = 'Macro after IN operator can only be: $(FAMILY), $(ARCH), $(TOOL_CHAIN_TAG) and $(TARGET).'
  41
  42 def MaxOfType(DataType):
  43     if DataType == 'UINT8':
  44         return int('0xFF', 16)
  45     if DataType == 'UINT16':
  46         return int('0xFFFF', 16)
  47     if DataType == 'UINT32':
  48         return int('0xFFFFFFFF', 16)
  49     if DataType == 'UINT64':
  50         return int('0xFFFFFFFFFFFFFFFF', 16)
  51
  52 class RangeObject(object):
  53     def __init__(self, start, end, empty = False):
  54
  55         if int(start) < int(end):
  56             self.start = int(start)
  57             self.end = int(end)
  58         else:
  59             self.start = int(end)
  60             self.end = int(start)
  61         self.empty = empty
  62
  63 class RangeContainer(object):
  64     def __init__(self):
  65         self.rangelist = []
  66
  67     def push(self, RangeObject):
  68         self.rangelist.append(RangeObject)
  69         self.rangelist = sorted(self.rangelist, key = lambda rangeobj : rangeobj.start)
  70         self.merge()
  71
  72     def pop(self):
  73         for item in self.rangelist:
  74             yield item
  75
  76     def __clean__(self):
  77         newrangelist = []
  78         for rangeobj in self.rangelist:
  79             if rangeobj.empty == True:
  80                 continue
  81             else:
  82                 newrangelist.append(rangeobj)
  83         self.rangelist = newrangelist
  84     def merge(self):
  85         self.__clean__()
  86         for i in range(0, len(self.rangelist) - 1):
  87             if self.rangelist[i + 1].start > self.rangelist[i].end:
  88                 continue
  89             else:
  90                 self.rangelist[i + 1].start = self.rangelist[i].start
  91                 self.rangelist[i + 1].end = self.rangelist[i + 1].end > self.rangelist[i].end and self.rangelist[i + 1].end or self.rangelist[i].end
  92                 self.rangelist[i].empty = True
  93
  94         self.__clean__()
  95
  96     def dump(self):
  97         print "----------------------"
  98         rangelist = ""
  99         for object in self.rangelist:
 100             rangelist = rangelist + "[%d , %d]" % (object.start, object.end)
 101         print rangelist
 102
 103
 104 class XOROperatorObject(object):
 105     def __init__(self):
 106         pass
 107     def Calculate(self, Operand, DataType, SymbolTable):
 108         if type(Operand) == type('') and not Operand.isalnum():
 109             Expr = "XOR ..."
 110             raise BadExpression(ERR_SNYTAX % Expr)
 111         rangeId = str(uuid.uuid1())
 112         rangeContainer = RangeContainer()
 113         rangeContainer.push(RangeObject(0, int(Operand) - 1))
 114         rangeContainer.push(RangeObject(int(Operand) + 1, MaxOfType(DataType)))
 115         SymbolTable[rangeId] = rangeContainer
 116         return rangeId
 117
 118 class LEOperatorObject(object):
 119     def __init__(self):
 120         pass
 121     def Calculate(self, Operand, DataType, SymbolTable):
 122         if type(Operand) == type('') and not Operand.isalnum():
 123             Expr = "LE ..."
 124             raise BadExpression(ERR_SNYTAX % Expr)
 125         rangeId1 = str(uuid.uuid1())
 126         rangeContainer = RangeContainer()
 127         rangeContainer.push(RangeObject(0, int(Operand)))
 128         SymbolTable[rangeId1] = rangeContainer
 129         return rangeId1
 130 class LTOperatorObject(object):
 131     def __init__(self):
 132         pass
 133     def Calculate(self, Operand, DataType, SymbolTable):
 134         if type(Operand) == type('') and not Operand.isalnum():
 135             Expr = "LT ..."
 136             raise BadExpression(ERR_SNYTAX % Expr)
 137         rangeId1 = str(uuid.uuid1())
 138         rangeContainer = RangeContainer()
 139         rangeContainer.push(RangeObject(0, int(Operand) - 1))
 140         SymbolTable[rangeId1] = rangeContainer
 141         return rangeId1
 142
 143 class GEOperatorObject(object):
 144     def __init__(self):
 145         pass
 146     def Calculate(self, Operand, DataType, SymbolTable):
 147         if type(Operand) == type('') and not Operand.isalnum():
 148             Expr = "GE ..."
 149             raise BadExpression(ERR_SNYTAX % Expr)
 150         rangeId1 = str(uuid.uuid1())
 151         rangeContainer = RangeContainer()
 152         rangeContainer.push(RangeObject(int(Operand), MaxOfType(DataType)))
 153         SymbolTable[rangeId1] = rangeContainer
 154         return rangeId1
 155
 156 class GTOperatorObject(object):
 157     def __init__(self):
 158         pass
 159     def Calculate(self, Operand, DataType, SymbolTable):
 160         if type(Operand) == type('') and not Operand.isalnum():
 161             Expr = "GT ..."
 162             raise BadExpression(ERR_SNYTAX % Expr)
 163         rangeId1 = str(uuid.uuid1())
 164         rangeContainer = RangeContainer()
 165         rangeContainer.push(RangeObject(int(Operand) + 1, MaxOfType(DataType)))
 166         SymbolTable[rangeId1] = rangeContainer
 167         return rangeId1
 168
 169 class EQOperatorObject(object):
 170     def __init__(self):
 171         pass
 172     def Calculate(self, Operand, DataType, SymbolTable):
 173         if type(Operand) == type('') and not Operand.isalnum():
 174             Expr = "EQ ..."
 175             raise BadExpression(ERR_SNYTAX % Expr)
 176         rangeId1 = str(uuid.uuid1())
 177         rangeContainer = RangeContainer()
 178         rangeContainer.push(RangeObject(int(Operand) , int(Operand)))
 179         SymbolTable[rangeId1] = rangeContainer
 180         return rangeId1
 181
 182 def GetOperatorObject(Operator):
 183     if Operator == '>':
 184         return GTOperatorObject()
 185     elif Operator == '>=':
 186         return GEOperatorObject()
 187     elif Operator == '<':
 188         return LTOperatorObject()
 189     elif Operator == '<=':
 190         return LEOperatorObject()
 191     elif Operator == '==':
 192         return EQOperatorObject()
 193     elif Operator == '^':
 194         return XOROperatorObject()
 195     else:
 196         raise BadExpression("Bad Operator")
 197
 198 class RangeExpression(object):
 199     # Logical operator mapping
 200     LogicalOperators = {
 201         '&&' : 'and', '||' : 'or',
 202         '!'  : 'not', 'AND': 'and',
 203         'OR' : 'or' , 'NOT': 'not',
 204         'XOR': '^'  , 'xor': '^',
 205         'EQ' : '==' , 'NE' : '!=',
 206         'GT' : '>'  , 'LT' : '<',
 207         'GE' : '>=' , 'LE' : '<=',
 208         'IN' : 'in'
 209     }
 210
 211     NonLetterOpLst = ['+', '-', '&', '|', '^', '!', '=', '>', '<']
 212
 213     RangePattern = re.compile(r'[0-9]+ - [0-9]+')
 214
 215     def preProcessRangeExpr(self, expr):
 216         # convert hex to int
 217         # convert interval to object index. ex. 1 - 10 to a GUID
 218         expr = expr.strip()
 219         NumberDict = {}
 220         for HexNumber in gHexPattern.findall(expr):
 221             Number = str(int(HexNumber, 16))
 222             NumberDict[HexNumber] = Number
 223         for HexNum in NumberDict:
 224             expr = expr.replace(HexNum, NumberDict[HexNum])
 225
 226         rangedict = {}
 227         for validrange in self.RangePattern.findall(expr):
 228             start, end = validrange.split(" - ")
 229             start = start.strip()
 230             end = end.strip()
 231             rangeid = str(uuid.uuid1())
 232             rangeContainer = RangeContainer()
 233             rangeContainer.push(RangeObject(start, end))
 234             self.operanddict[str(rangeid)] = rangeContainer
 235             rangedict[validrange] = str(rangeid)
 236
 237         for validrange in rangedict:
 238             expr = expr.replace(validrange, rangedict[validrange])
 239
 240         self._Expr = expr
 241         return expr
 242
 243
 244     def EvalRange(self, Operator, Oprand):
 245
 246         operatorobj = GetOperatorObject(Operator)
 247         return operatorobj.Calculate(Oprand, self.PcdDataType, self.operanddict)
 248
 249     def Rangeintersection(self, Oprand1, Oprand2):
 250         rangeContainer1 = self.operanddict[Oprand1]
 251         rangeContainer2 = self.operanddict[Oprand2]
 252         rangeContainer = RangeContainer()
 253         for range1 in rangeContainer1.pop():
 254             for range2 in rangeContainer2.pop():
 255                 start1 = range1.start
 256                 end1 = range1.end
 257                 start2 = range2.start
 258                 end2 = range2.end
 259                 if start1 >= start2:
 260                     start1, start2 = start2, start1
 261                     end1, end2 = end2, end1
 262                 if range1.empty:
 263                     rangeid = str(uuid.uuid1())
 264                     rangeContainer.push(RangeObject(0, 0, True))
 265                 if end1 < start2:
 266                     rangeid = str(uuid.uuid1())
 267                     rangeContainer.push(RangeObject(0, 0, True))
 268                 elif end1 == start2:
 269                     rangeid = str(uuid.uuid1())
 270                     rangeContainer.push(RangeObject(end1, end1))
 271                 elif end1 <= end2 and end1 > start2:
 272                     rangeid = str(uuid.uuid1())
 273                     rangeContainer.push(RangeObject(start2, end1))
 274                 elif end1 >= end2:
 275                     rangeid = str(uuid.uuid1())
 276                     rangeContainer.push(RangeObject(start2, end2))
 277
 278         self.operanddict[rangeid] = rangeContainer
 279 #        rangeContainer.dump()
 280         return rangeid
 281
 282     def Rangecollections(self, Oprand1, Oprand2):
 283
 284         rangeContainer1 = self.operanddict[Oprand1]
 285         rangeContainer2 = self.operanddict[Oprand2]
 286         rangeContainer = RangeContainer()
 287
 288         for rangeobj in rangeContainer2.pop():
 289             rangeContainer.push(rangeobj)
 290         for rangeobj in rangeContainer1.pop():
 291             rangeContainer.push(rangeobj)
 292
 293         rangeid = str(uuid.uuid1())
 294         self.operanddict[rangeid] = rangeContainer
 295
 296 #        rangeContainer.dump()
 297         return rangeid
 298
 299
 300     def NegtiveRange(self, Oprand1):
 301         rangeContainer1 = self.operanddict[Oprand1]
 302
 303
 304         rangeids = []
 305
 306         for rangeobj in rangeContainer1.pop():
 307             rangeContainer = RangeContainer()
 308             rangeid = str(uuid.uuid1())
 309             if rangeobj.empty:
 310                 rangeContainer.push(RangeObject(0, MaxOfType(self.PcdDataType)))
 311             else:
 312                 if rangeobj.start > 0:
 313                     rangeContainer.push(RangeObject(0, rangeobj.start - 1))
 314                 if rangeobj.end < MaxOfType(self.PcdDataType):
 315                     rangeContainer.push(RangeObject(rangeobj.end + 1, MaxOfType(self.PcdDataType)))
 316             self.operanddict[rangeid] = rangeContainer
 317             rangeids.append(rangeid)
 318
 319         if len(rangeids) == 0:
 320             rangeContainer = RangeContainer()
 321             rangeContainer.push(RangeObject(0, MaxOfType(self.PcdDataType)))
 322             rangeid = str(uuid.uuid1())
 323             self.operanddict[rangeid] = rangeContainer
 324             return rangeid
 325
 326         if len(rangeids) == 1:
 327             return rangeids[0]
 328
 329         re = self.Rangeintersection(rangeids[0], rangeids[1])
 330         for i in range(2, len(rangeids)):
 331             re = self.Rangeintersection(re, rangeids[i])
 332
 333         rangeid2 = str(uuid.uuid1())
 334         self.operanddict[rangeid2] = self.operanddict[re]
 335         return rangeid2
 336
 337     def Eval(self, Operator, Oprand1, Oprand2 = None):
 338
 339         if Operator in ["!", "NOT", "not"]:
 340             if not gGuidPattern.match(Oprand1.strip()):
 341                 raise BadExpression(ERR_STRING_EXPR % Operator)
 342             return self.NegtiveRange(Oprand1)
 343         else:
 344             if Operator in ["==", ">=", "<=", ">", "<", '^']:
 345                 return self.EvalRange(Operator, Oprand1)
 346             elif Operator == 'and' :
 347                 if not gGuidPatternEnd.match(Oprand1.strip()) or not gGuidPatternEnd.match(Oprand2.strip()):
 348                     raise BadExpression(ERR_STRING_EXPR % Operator)
 349                 return self.Rangeintersection(Oprand1, Oprand2)
 350             elif Operator == 'or':
 351                 if not gGuidPatternEnd.match(Oprand1.strip()) or not gGuidPatternEnd.match(Oprand2.strip()):
 352                     raise BadExpression(ERR_STRING_EXPR % Operator)
 353                 return self.Rangecollections(Oprand1, Oprand2)
 354             else:
 355                 raise BadExpression(ERR_STRING_EXPR % Operator)
 356
 357
 358     def __init__(self, Expression, PcdDataType, SymbolTable = {}):
 359         self._NoProcess = False
 360         if type(Expression) != type(''):
 361             self._Expr = Expression
 362             self._NoProcess = True
 363             return
 364
 365         self._Expr = Expression.strip()
 366
 367         if not self._Expr.strip():
 368             raise BadExpression(ERR_EMPTY_EXPR)
 369
 370         #
 371         # The symbol table including PCD and macro mapping
 372         #
 373         self._Symb = SymbolTable
 374         self._Symb.update(self.LogicalOperators)
 375         self._Idx = 0
 376         self._Len = len(self._Expr)
 377         self._Token = ''
 378         self._WarnExcept = None
 379
 380
 381         # Literal token without any conversion
 382         self._LiteralToken = ''
 383
 384         # store the operand object
 385         self.operanddict = {}
 386         # The Pcd max value depends on PcdDataType
 387         self.PcdDataType = PcdDataType
 388
 389     # Public entry for this class
 390     #   @param RealValue: False: only evaluate if the expression is true or false, used for conditional expression
 391     #                     True : return the evaluated str(value), used for PCD value
 392     #
 393     #   @return: True or False if RealValue is False
 394     #            Evaluated value of string format if RealValue is True
 395     #
 396     def __call__(self, RealValue = False, Depth = 0):
 397         if self._NoProcess:
 398             return self._Expr
 399
 400         self._Depth = Depth
 401
 402         self._Expr = self._Expr.strip()
 403
 404         self.preProcessRangeExpr(self._Expr)
 405
 406         # check if the expression does not need to evaluate
 407         if RealValue and Depth == 0:
 408             self._Token = self._Expr
 409             if gGuidPatternEnd.match(self._Expr):
 410                 return [self.operanddict[self._Expr] ]
 411
 412             self._Idx = 0
 413             self._Token = ''
 414
 415         Val = self._OrExpr()
 416         RealVal = Val
 417
 418         RangeIdList = RealVal.split("or")
 419         RangeList = []
 420         for rangeid in RangeIdList:
 421             RangeList.append(self.operanddict[rangeid.strip()])
 422
 423         return RangeList
 424
 425     # Template function to parse binary operators which have same precedence
 426     # Expr [Operator Expr]*
 427     def _ExprFuncTemplate(self, EvalFunc, OpLst):
 428         Val = EvalFunc()
 429         while self._IsOperator(OpLst):
 430             Op = self._Token
 431             try:
 432                 Val = self.Eval(Op, Val, EvalFunc())
 433             except WrnExpression, Warn:
 434                 self._WarnExcept = Warn
 435                 Val = Warn.result
 436         return Val
 437
 438     # A [|| B]*
 439     def _OrExpr(self):
 440         return self._ExprFuncTemplate(self._AndExpr, ["OR", "or"])
 441
 442     # A [&& B]*
 443     def _AndExpr(self):
 444         return self._ExprFuncTemplate(self._NeExpr, ["AND", "and"])
 445
 446     def _NeExpr(self):
 447         Val = self._RelExpr()
 448         while self._IsOperator([ "!=", "NOT", "not"]):
 449             Op = self._Token
 450             if Op in ["!", "NOT", "not"]:
 451                 if not self._IsOperator(["IN", "in"]):
 452                     raise BadExpression(ERR_REL_NOT_IN)
 453                 Op += ' ' + self._Token
 454             try:
 455                 Val = self.Eval(Op, Val, self._RelExpr())
 456             except WrnExpression, Warn:
 457                 self._WarnExcept = Warn
 458                 Val = Warn.result
 459         return Val
 460
 461     # [!]*A
 462     def _RelExpr(self):
 463         if self._IsOperator(["NOT" , "LE", "GE", "LT", "GT", "EQ", "XOR"]):
 464             Token = self._Token
 465             Val = self._NeExpr()
 466             try:
 467                 return self.Eval(Token, Val)
 468             except WrnExpression, Warn:
 469                 self._WarnExcept = Warn
 470                 return Warn.result
 471         return self._IdenExpr()
 472
 473     # Parse identifier or encapsulated expression
 474     def _IdenExpr(self):
 475         Tk = self._GetToken()
 476         if Tk == '(':
 477             Val = self._OrExpr()
 478             try:
 479                 # _GetToken may also raise BadExpression
 480                 if self._GetToken() != ')':
 481                     raise BadExpression(ERR_MATCH)
 482             except BadExpression:
 483                 raise BadExpression(ERR_MATCH)
 484             return Val
 485         return Tk
 486
 487     # Skip whitespace or tab
 488     def __SkipWS(self):
 489         for Char in self._Expr[self._Idx:]:
 490             if Char not in ' \t':
 491                 break
 492             self._Idx += 1
 493
 494     # Try to convert string to number
 495     def __IsNumberToken(self):
 496         Radix = 10
 497         if self._Token.lower()[0:2] == '0x' and len(self._Token) > 2:
 498             Radix = 16
 499         try:
 500             self._Token = int(self._Token, Radix)
 501             return True
 502         except ValueError:
 503             return False
 504         except TypeError:
 505             return False
 506
 507     # Parse array: {...}
 508     def __GetArray(self):
 509         Token = '{'
 510         self._Idx += 1
 511         self.__GetNList(True)
 512         Token += self._LiteralToken
 513         if self._Idx >= self._Len or self._Expr[self._Idx] != '}':
 514             raise BadExpression(ERR_ARRAY_TOKEN % Token)
 515         Token += '}'
 516
 517         # All whitespace and tabs in array are already stripped.
 518         IsArray = IsGuid = False
 519         if len(Token.split(',')) == 11 and len(Token.split(',{')) == 2 \
 520             and len(Token.split('},')) == 1:
 521             HexLen = [11, 6, 6, 5, 4, 4, 4, 4, 4, 4, 6]
 522             HexList = Token.split(',')
 523             if HexList[3].startswith('{') and \
 524                 not [Index for Index, Hex in enumerate(HexList) if len(Hex) > HexLen[Index]]:
 525                 IsGuid = True
 526         if Token.lstrip('{').rstrip('}').find('{') == -1:
 527             if not [Hex for Hex in Token.lstrip('{').rstrip('}').split(',') if len(Hex) > 4]:
 528                 IsArray = True
 529         if not IsArray and not IsGuid:
 530             raise BadExpression(ERR_ARRAY_TOKEN % Token)
 531         self._Idx += 1
 532         self._Token = self._LiteralToken = Token
 533         return self._Token
 534
 535     # Parse string, the format must be: "..."
 536     def __GetString(self):
 537         Idx = self._Idx
 538
 539         # Skip left quote
 540         self._Idx += 1
 541
 542         # Replace escape \\\", \"
 543         Expr = self._Expr[self._Idx:].replace('\\\\', '//').replace('\\\"', '\\\'')
 544         for Ch in Expr:
 545             self._Idx += 1
 546             if Ch == '"':
 547                 break
 548         self._Token = self._LiteralToken = self._Expr[Idx:self._Idx]
 549         if not self._Token.endswith('"'):
 550             raise BadExpression(ERR_STRING_TOKEN % self._Token)
 551         self._Token = self._Token[1:-1]
 552         return self._Token
 553
 554     # Get token that is comprised by alphanumeric, underscore or dot(used by PCD)
 555     # @param IsAlphaOp: Indicate if parsing general token or script operator(EQ, NE...)
 556     def __GetIdToken(self, IsAlphaOp = False):
 557         IdToken = ''
 558         for Ch in self._Expr[self._Idx:]:
 559             if not self.__IsIdChar(Ch):
 560                 break
 561             self._Idx += 1
 562             IdToken += Ch
 563
 564         self._Token = self._LiteralToken = IdToken
 565         if not IsAlphaOp:
 566             self.__ResolveToken()
 567         return self._Token
 568
 569     # Try to resolve token
 570     def __ResolveToken(self):
 571         if not self._Token:
 572             raise BadExpression(ERR_EMPTY_TOKEN)
 573
 574         # PCD token
 575         if PcdPattern.match(self._Token):
 576             if self._Token not in self._Symb:
 577                 Ex = BadExpression(ERR_PCD_RESOLVE % self._Token)
 578                 Ex.Pcd = self._Token
 579                 raise Ex
 580             self._Token = RangeExpression(self._Symb[self._Token], self._Symb)(True, self._Depth + 1)
 581             if type(self._Token) != type(''):
 582                 self._LiteralToken = hex(self._Token)
 583                 return
 584
 585         if self._Token.startswith('"'):
 586             self._Token = self._Token[1:-1]
 587         elif self._Token in ["FALSE", "false", "False"]:
 588             self._Token = False
 589         elif self._Token in ["TRUE", "true", "True"]:
 590             self._Token = True
 591         else:
 592             self.__IsNumberToken()
 593
 594     def __GetNList(self, InArray = False):
 595         self._GetSingleToken()
 596         if not self.__IsHexLiteral():
 597             if InArray:
 598                 raise BadExpression(ERR_ARRAY_ELE % self._Token)
 599             return self._Token
 600
 601         self.__SkipWS()
 602         Expr = self._Expr[self._Idx:]
 603         if not Expr.startswith(','):
 604             return self._Token
 605
 606         NList = self._LiteralToken
 607         while Expr.startswith(','):
 608             NList += ','
 609             self._Idx += 1
 610             self.__SkipWS()
 611             self._GetSingleToken()
 612             if not self.__IsHexLiteral():
 613                 raise BadExpression(ERR_ARRAY_ELE % self._Token)
 614             NList += self._LiteralToken
 615             self.__SkipWS()
 616             Expr = self._Expr[self._Idx:]
 617         self._Token = self._LiteralToken = NList
 618         return self._Token
 619
 620     def __IsHexLiteral(self):
 621         if self._LiteralToken.startswith('{') and \
 622             self._LiteralToken.endswith('}'):
 623             return True
 624
 625         if gHexPattern.match(self._LiteralToken):
 626             Token = self._LiteralToken[2:]
 627             Token = Token.lstrip('0')
 628             if not Token:
 629                 self._LiteralToken = '0x0'
 630             else:
 631                 self._LiteralToken = '0x' + Token.lower()
 632             return True
 633         return False
 634
 635     def _GetToken(self):
 636         return self.__GetNList()
 637
 638     @staticmethod
 639     def __IsIdChar(Ch):
 640         return Ch in '._/:' or Ch.isalnum()
 641
 642     # Parse operand
 643     def _GetSingleToken(self):
 644         self.__SkipWS()
 645         Expr = self._Expr[self._Idx:]
 646         if Expr.startswith('L"'):
 647             # Skip L
 648             self._Idx += 1
 649             UStr = self.__GetString()
 650             self._Token = 'L"' + UStr + '"'
 651             return self._Token
 652
 653         self._Token = ''
 654         if Expr:
 655             Ch = Expr[0]
 656             Match = gGuidPattern.match(Expr)
 657             if Match and not Expr[Match.end():Match.end() + 1].isalnum() \
 658                 and Expr[Match.end():Match.end() + 1] != '_':
 659                 self._Idx += Match.end()
 660                 self._Token = Expr[0:Match.end()]
 661                 return self._Token
 662             elif self.__IsIdChar(Ch):
 663                 return self.__GetIdToken()
 664             elif Ch == '(' or Ch == ')':
 665                 self._Idx += 1
 666                 self._Token = Ch
 667                 return self._Token
 668
 669         raise BadExpression(ERR_VALID_TOKEN % Expr)
 670
 671     # Parse operator
 672     def _GetOperator(self):
 673         self.__SkipWS()
 674         LegalOpLst = ['&&', '||', '!=', '==', '>=', '<='] + self.NonLetterOpLst
 675
 676         self._Token = ''
 677         Expr = self._Expr[self._Idx:]
 678
 679         # Reach end of expression
 680         if not Expr:
 681             return ''
 682
 683         # Script operator: LT, GT, LE, GE, EQ, NE, and, or, xor, not
 684         if Expr[0].isalpha():
 685             return self.__GetIdToken(True)
 686
 687         # Start to get regular operator: +, -, <, > ...
 688         if Expr[0] not in self.NonLetterOpLst:
 689             return ''
 690
 691         OpToken = ''
 692         for Ch in Expr:
 693             if Ch in self.NonLetterOpLst:
 694                 if '!' == Ch and OpToken:
 695                     break
 696                 self._Idx += 1
 697                 OpToken += Ch
 698             else:
 699                 break
 700
 701         if OpToken not in LegalOpLst:
 702             raise BadExpression(ERR_OPERATOR_UNSUPPORT % OpToken)
 703         self._Token = OpToken
 704         return OpToken
 705
 706     # Check if current token matches the operators given from OpList
 707     def _IsOperator(self, OpList):
 708         Idx = self._Idx
 709         self._GetOperator()
 710         if self._Token in OpList:
 711             if self._Token in self.LogicalOperators:
 712                 self._Token = self.LogicalOperators[self._Token]
 713             return True
 714         self._Idx = Idx
 715         return False
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726 #    UTRangeList()