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