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