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