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