1## @file 2# This file is used to parse and evaluate expression in directive or PCD value. 3# 4# Copyright (c) 2011 - 2016, 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# 15from Common.GlobalData import * 16from CommonDataClass.Exceptions import BadExpression 17from CommonDataClass.Exceptions import WrnExpression 18from Misc import GuidStringToGuidStructureString 19 20ERR_STRING_EXPR = 'This operator cannot be used in string expression: [%s].' 21ERR_SNYTAX = 'Syntax error, the rest of expression cannot be evaluated: [%s].' 22ERR_MATCH = 'No matching right parenthesis.' 23ERR_STRING_TOKEN = 'Bad string token: [%s].' 24ERR_MACRO_TOKEN = 'Bad macro token: [%s].' 25ERR_EMPTY_TOKEN = 'Empty token is not allowed.' 26ERR_PCD_RESOLVE = 'PCD token cannot be resolved: [%s].' 27ERR_VALID_TOKEN = 'No more valid token found from rest of string: [%s].' 28ERR_EXPR_TYPE = 'Different types found in expression.' 29ERR_OPERATOR_UNSUPPORT = 'Unsupported operator: [%s]' 30ERR_REL_NOT_IN = 'Expect "IN" after "not" operator.' 31WRN_BOOL_EXPR = 'Operand of boolean type cannot be used in arithmetic expression.' 32WRN_EQCMP_STR_OTHERS = '== Comparison between Operand of string type and Boolean/Number Type always return False.' 33WRN_NECMP_STR_OTHERS = '!= Comparison between Operand of string type and Boolean/Number Type always return True.' 34ERR_RELCMP_STR_OTHERS = 'Operator taking Operand of string type and Boolean/Number Type is not allowed: [%s].' 35ERR_STRING_CMP = 'Unicode string and general string cannot be compared: [%s %s %s]' 36ERR_ARRAY_TOKEN = 'Bad C array or C format GUID token: [%s].' 37ERR_ARRAY_ELE = 'This must be HEX value for NList or Array: [%s].' 38ERR_EMPTY_EXPR = 'Empty expression is not allowed.' 39ERR_IN_OPERAND = 'Macro after IN operator can only be: $(FAMILY), $(ARCH), $(TOOL_CHAIN_TAG) and $(TARGET).' 40 41## SplitString 42# Split string to list according double quote 43# For example: abc"de\"f"ghi"jkl"mn will be: ['abc', '"de\"f"', 'ghi', '"jkl"', 'mn'] 44# 45def SplitString(String): 46 # There might be escaped quote: "abc\"def\\\"ghi" 47 Str = String.replace('\\\\', '//').replace('\\\"', '\\\'') 48 RetList = [] 49 InQuote = False 50 Item = '' 51 for i, ch in enumerate(Str): 52 if ch == '"': 53 InQuote = not InQuote 54 if not InQuote: 55 Item += String[i] 56 RetList.append(Item) 57 Item = '' 58 continue 59 if Item: 60 RetList.append(Item) 61 Item = '' 62 Item += String[i] 63 if InQuote: 64 raise BadExpression(ERR_STRING_TOKEN % Item) 65 if Item: 66 RetList.append(Item) 67 return RetList 68 69## ReplaceExprMacro 70# 71def ReplaceExprMacro(String, Macros, ExceptionList = None): 72 StrList = SplitString(String) 73 for i, String in enumerate(StrList): 74 InQuote = False 75 if String.startswith('"'): 76 InQuote = True 77 MacroStartPos = String.find('$(') 78 if MacroStartPos < 0: 79 for Pcd in gPlatformPcds.keys(): 80 if Pcd in String: 81 if Pcd not in gConditionalPcds: 82 gConditionalPcds.append(Pcd) 83 continue 84 RetStr = '' 85 while MacroStartPos >= 0: 86 RetStr = String[0:MacroStartPos] 87 MacroEndPos = String.find(')', MacroStartPos) 88 if MacroEndPos < 0: 89 raise BadExpression(ERR_MACRO_TOKEN % String[MacroStartPos:]) 90 Macro = String[MacroStartPos+2:MacroEndPos] 91 if Macro not in Macros: 92 # From C reference manual: 93 # If an undefined macro name appears in the constant-expression of 94 # !if or !elif, it is replaced by the integer constant 0. 95 RetStr += '0' 96 elif not InQuote: 97 Tklst = RetStr.split() 98 if Tklst and Tklst[-1] in ['IN', 'in'] and ExceptionList and Macro not in ExceptionList: 99 raise BadExpression(ERR_IN_OPERAND) 100 # Make sure the macro in exception list is encapsulated by double quote 101 # For example: DEFINE ARCH = IA32 X64 102 # $(ARCH) is replaced with "IA32 X64" 103 if ExceptionList and Macro in ExceptionList: 104 RetStr += '"' + Macros[Macro] + '"' 105 elif Macros[Macro].strip(): 106 RetStr += Macros[Macro] 107 else: 108 RetStr += '""' 109 else: 110 RetStr += Macros[Macro] 111 RetStr += String[MacroEndPos+1:] 112 String = RetStr 113 MacroStartPos = String.find('$(') 114 StrList[i] = RetStr 115 return ''.join(StrList) 116 117SupportedInMacroList = ['TARGET', 'TOOL_CHAIN_TAG', 'ARCH', 'FAMILY'] 118 119class ValueExpression(object): 120 # Logical operator mapping 121 LogicalOperators = { 122 '&&' : 'and', '||' : 'or', 123 '!' : 'not', 'AND': 'and', 124 'OR' : 'or' , 'NOT': 'not', 125 'XOR': '^' , 'xor': '^', 126 'EQ' : '==' , 'NE' : '!=', 127 'GT' : '>' , 'LT' : '<', 128 'GE' : '>=' , 'LE' : '<=', 129 'IN' : 'in' 130 } 131 132 NonLetterOpLst = ['+', '-', '&', '|', '^', '!', '=', '>', '<'] 133 134 PcdPattern = re.compile(r'[_a-zA-Z][0-9A-Za-z_]*\.[_a-zA-Z][0-9A-Za-z_]*$') 135 HexPattern = re.compile(r'0[xX][0-9a-fA-F]+$') 136 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}') 137 138 SymbolPattern = re.compile("(" 139 "\$\([A-Z][A-Z0-9_]*\)|\$\(\w+\.\w+\)|\w+\.\w+|" 140 "&&|\|\||!(?!=)|" 141 "(?<=\W)AND(?=\W)|(?<=\W)OR(?=\W)|(?<=\W)NOT(?=\W)|(?<=\W)XOR(?=\W)|" 142 "(?<=\W)EQ(?=\W)|(?<=\W)NE(?=\W)|(?<=\W)GT(?=\W)|(?<=\W)LT(?=\W)|(?<=\W)GE(?=\W)|(?<=\W)LE(?=\W)" 143 ")") 144 145 @staticmethod 146 def Eval(Operator, Oprand1, Oprand2 = None): 147 WrnExp = None 148 149 if Operator not in ["==", "!=", ">=", "<=", ">", "<", "in", "not in"] and \ 150 (type(Oprand1) == type('') or type(Oprand2) == type('')): 151 raise BadExpression(ERR_STRING_EXPR % Operator) 152 153 TypeDict = { 154 type(0) : 0, 155 type(0L) : 0, 156 type('') : 1, 157 type(True) : 2 158 } 159 160 EvalStr = '' 161 if Operator in ["!", "NOT", "not"]: 162 if type(Oprand1) == type(''): 163 raise BadExpression(ERR_STRING_EXPR % Operator) 164 EvalStr = 'not Oprand1' 165 else: 166 if Operator in ["+", "-"] and (type(True) in [type(Oprand1), type(Oprand2)]): 167 # Boolean in '+'/'-' will be evaluated but raise warning 168 WrnExp = WrnExpression(WRN_BOOL_EXPR) 169 elif type('') in [type(Oprand1), type(Oprand2)] and type(Oprand1)!= type(Oprand2): 170 # == between string and number/boolean will always return False, != return True 171 if Operator == "==": 172 WrnExp = WrnExpression(WRN_EQCMP_STR_OTHERS) 173 WrnExp.result = False 174 raise WrnExp 175 elif Operator == "!=": 176 WrnExp = WrnExpression(WRN_NECMP_STR_OTHERS) 177 WrnExp.result = True 178 raise WrnExp 179 else: 180 raise BadExpression(ERR_RELCMP_STR_OTHERS % Operator) 181 elif TypeDict[type(Oprand1)] != TypeDict[type(Oprand2)]: 182 if Operator in ["==", "!=", ">=", "<=", ">", "<"] and set((TypeDict[type(Oprand1)], TypeDict[type(Oprand2)])) == set((TypeDict[type(True)], TypeDict[type(0)])): 183 # comparison between number and boolean is allowed 184 pass 185 elif Operator in ['&', '|', '^', "and", "or"] and set((TypeDict[type(Oprand1)], TypeDict[type(Oprand2)])) == set((TypeDict[type(True)], TypeDict[type(0)])): 186 # bitwise and logical operation between number and boolean is allowed 187 pass 188 else: 189 raise BadExpression(ERR_EXPR_TYPE) 190 if type(Oprand1) == type('') and type(Oprand2) == type(''): 191 if (Oprand1.startswith('L"') and not Oprand2.startswith('L"')) or \ 192 (not Oprand1.startswith('L"') and Oprand2.startswith('L"')): 193 raise BadExpression(ERR_STRING_CMP % (Oprand1, Operator, Oprand2)) 194 if 'in' in Operator and type(Oprand2) == type(''): 195 Oprand2 = Oprand2.split() 196 EvalStr = 'Oprand1 ' + Operator + ' Oprand2' 197 198 # Local symbols used by built in eval function 199 Dict = { 200 'Oprand1' : Oprand1, 201 'Oprand2' : Oprand2 202 } 203 try: 204 Val = eval(EvalStr, {}, Dict) 205 except Exception, Excpt: 206 raise BadExpression(str(Excpt)) 207 208 if Operator in ['and', 'or']: 209 if Val: 210 Val = True 211 else: 212 Val = False 213 214 if WrnExp: 215 WrnExp.result = Val 216 raise WrnExp 217 return Val 218 219 def __init__(self, Expression, SymbolTable={}): 220 self._NoProcess = False 221 if type(Expression) != type(''): 222 self._Expr = Expression 223 self._NoProcess = True 224 return 225 226 self._Expr = ReplaceExprMacro(Expression.strip(), 227 SymbolTable, 228 SupportedInMacroList) 229 230 if not self._Expr.strip(): 231 raise BadExpression(ERR_EMPTY_EXPR) 232 233 # 234 # The symbol table including PCD and macro mapping 235 # 236 self._Symb = SymbolTable 237 self._Symb.update(self.LogicalOperators) 238 self._Idx = 0 239 self._Len = len(self._Expr) 240 self._Token = '' 241 self._WarnExcept = None 242 243 # Literal token without any conversion 244 self._LiteralToken = '' 245 246 # Public entry for this class 247 # @param RealValue: False: only evaluate if the expression is true or false, used for conditional expression 248 # True : return the evaluated str(value), used for PCD value 249 # 250 # @return: True or False if RealValue is False 251 # Evaluated value of string format if RealValue is True 252 # 253 def __call__(self, RealValue=False, Depth=0): 254 if self._NoProcess: 255 return self._Expr 256 257 self._Depth = Depth 258 259 self._Expr = self._Expr.strip() 260 if RealValue and Depth == 0: 261 self._Token = self._Expr 262 if self.__IsNumberToken(): 263 return self._Expr 264 265 try: 266 Token = self._GetToken() 267 if type(Token) == type('') and Token.startswith('{') and Token.endswith('}') and self._Idx >= self._Len: 268 return self._Expr 269 except BadExpression: 270 pass 271 272 self._Idx = 0 273 self._Token = '' 274 275 Val = self._OrExpr() 276 RealVal = Val 277 if type(Val) == type(''): 278 if Val == 'L""': 279 Val = False 280 elif not Val: 281 Val = False 282 RealVal = '""' 283 elif not Val.startswith('L"') and not Val.startswith('{'): 284 Val = True 285 RealVal = '"' + RealVal + '"' 286 287 # The expression has been parsed, but the end of expression is not reached 288 # It means the rest does not comply EBNF of <Expression> 289 if self._Idx != self._Len: 290 raise BadExpression(ERR_SNYTAX % self._Expr[self._Idx:]) 291 292 if RealValue: 293 RetVal = str(RealVal) 294 elif Val: 295 RetVal = True 296 else: 297 RetVal = False 298 299 if self._WarnExcept: 300 self._WarnExcept.result = RetVal 301 raise self._WarnExcept 302 else: 303 return RetVal 304 305 # Template function to parse binary operators which have same precedence 306 # Expr [Operator Expr]* 307 def _ExprFuncTemplate(self, EvalFunc, OpLst): 308 Val = EvalFunc() 309 while self._IsOperator(OpLst): 310 Op = self._Token 311 try: 312 Val = self.Eval(Op, Val, EvalFunc()) 313 except WrnExpression, Warn: 314 self._WarnExcept = Warn 315 Val = Warn.result 316 return Val 317 318 # A [|| B]* 319 def _OrExpr(self): 320 return self._ExprFuncTemplate(self._AndExpr, ["OR", "or", "||"]) 321 322 # A [&& B]* 323 def _AndExpr(self): 324 return self._ExprFuncTemplate(self._BitOr, ["AND", "and", "&&"]) 325 326 # A [ | B]* 327 def _BitOr(self): 328 return self._ExprFuncTemplate(self._BitXor, ["|"]) 329 330 # A [ ^ B]* 331 def _BitXor(self): 332 return self._ExprFuncTemplate(self._BitAnd, ["XOR", "xor", "^"]) 333 334 # A [ & B]* 335 def _BitAnd(self): 336 return self._ExprFuncTemplate(self._EqExpr, ["&"]) 337 338 # A [ == B]* 339 def _EqExpr(self): 340 Val = self._RelExpr() 341 while self._IsOperator(["==", "!=", "EQ", "NE", "IN", "in", "!", "NOT", "not"]): 342 Op = self._Token 343 if Op in ["!", "NOT", "not"]: 344 if not self._IsOperator(["IN", "in"]): 345 raise BadExpression(ERR_REL_NOT_IN) 346 Op += ' ' + self._Token 347 try: 348 Val = self.Eval(Op, Val, self._RelExpr()) 349 except WrnExpression, Warn: 350 self._WarnExcept = Warn 351 Val = Warn.result 352 return Val 353 354 # A [ > B]* 355 def _RelExpr(self): 356 return self._ExprFuncTemplate(self._AddExpr, ["<=", ">=", "<", ">", "LE", "GE", "LT", "GT"]) 357 358 # A [ + B]* 359 def _AddExpr(self): 360 return self._ExprFuncTemplate(self._UnaryExpr, ["+", "-"]) 361 362 # [!]*A 363 def _UnaryExpr(self): 364 if self._IsOperator(["!", "NOT", "not"]): 365 Val = self._UnaryExpr() 366 try: 367 return self.Eval('not', Val) 368 except WrnExpression, Warn: 369 self._WarnExcept = Warn 370 return Warn.result 371 return self._IdenExpr() 372 373 # Parse identifier or encapsulated expression 374 def _IdenExpr(self): 375 Tk = self._GetToken() 376 if Tk == '(': 377 Val = self._OrExpr() 378 try: 379 # _GetToken may also raise BadExpression 380 if self._GetToken() != ')': 381 raise BadExpression(ERR_MATCH) 382 except BadExpression: 383 raise BadExpression(ERR_MATCH) 384 return Val 385 return Tk 386 387 # Skip whitespace or tab 388 def __SkipWS(self): 389 for Char in self._Expr[self._Idx:]: 390 if Char not in ' \t': 391 break 392 self._Idx += 1 393 394 # Try to convert string to number 395 def __IsNumberToken(self): 396 Radix = 10 397 if self._Token.lower()[0:2] == '0x' and len(self._Token) > 2: 398 Radix = 16 399 try: 400 self._Token = int(self._Token, Radix) 401 return True 402 except ValueError: 403 return False 404 except TypeError: 405 return False 406 407 # Parse array: {...} 408 def __GetArray(self): 409 Token = '{' 410 self._Idx += 1 411 self.__GetNList(True) 412 Token += self._LiteralToken 413 if self._Idx >= self._Len or self._Expr[self._Idx] != '}': 414 raise BadExpression(ERR_ARRAY_TOKEN % Token) 415 Token += '}' 416 417 # All whitespace and tabs in array are already stripped. 418 IsArray = IsGuid = False 419 if len(Token.split(',')) == 11 and len(Token.split(',{')) == 2 \ 420 and len(Token.split('},')) == 1: 421 HexLen = [11,6,6,5,4,4,4,4,4,4,6] 422 HexList= Token.split(',') 423 if HexList[3].startswith('{') and \ 424 not [Index for Index, Hex in enumerate(HexList) if len(Hex) > HexLen[Index]]: 425 IsGuid = True 426 if Token.lstrip('{').rstrip('}').find('{') == -1: 427 if not [Hex for Hex in Token.lstrip('{').rstrip('}').split(',') if len(Hex) > 4]: 428 IsArray = True 429 if not IsArray and not IsGuid: 430 raise BadExpression(ERR_ARRAY_TOKEN % Token) 431 self._Idx += 1 432 self._Token = self._LiteralToken = Token 433 return self._Token 434 435 # Parse string, the format must be: "..." 436 def __GetString(self): 437 Idx = self._Idx 438 439 # Skip left quote 440 self._Idx += 1 441 442 # Replace escape \\\", \" 443 Expr = self._Expr[self._Idx:].replace('\\\\', '//').replace('\\\"', '\\\'') 444 for Ch in Expr: 445 self._Idx += 1 446 if Ch == '"': 447 break 448 self._Token = self._LiteralToken = self._Expr[Idx:self._Idx] 449 if not self._Token.endswith('"'): 450 raise BadExpression(ERR_STRING_TOKEN % self._Token) 451 self._Token = self._Token[1:-1] 452 return self._Token 453 454 # Get token that is comprised by alphanumeric, underscore or dot(used by PCD) 455 # @param IsAlphaOp: Indicate if parsing general token or script operator(EQ, NE...) 456 def __GetIdToken(self, IsAlphaOp = False): 457 IdToken = '' 458 for Ch in self._Expr[self._Idx:]: 459 if not self.__IsIdChar(Ch): 460 break 461 self._Idx += 1 462 IdToken += Ch 463 464 self._Token = self._LiteralToken = IdToken 465 if not IsAlphaOp: 466 self.__ResolveToken() 467 return self._Token 468 469 # Try to resolve token 470 def __ResolveToken(self): 471 if not self._Token: 472 raise BadExpression(ERR_EMPTY_TOKEN) 473 474 # PCD token 475 if self.PcdPattern.match(self._Token): 476 if self._Token not in self._Symb: 477 Ex = BadExpression(ERR_PCD_RESOLVE % self._Token) 478 Ex.Pcd = self._Token 479 raise Ex 480 self._Token = ValueExpression(self._Symb[self._Token], self._Symb)(True, self._Depth+1) 481 if type(self._Token) != type(''): 482 self._LiteralToken = hex(self._Token) 483 return 484 485 if self._Token.startswith('"'): 486 self._Token = self._Token[1:-1] 487 elif self._Token in ["FALSE", "false", "False"]: 488 self._Token = False 489 elif self._Token in ["TRUE", "true", "True"]: 490 self._Token = True 491 else: 492 self.__IsNumberToken() 493 494 def __GetNList(self, InArray=False): 495 self._GetSingleToken() 496 if not self.__IsHexLiteral(): 497 if InArray: 498 raise BadExpression(ERR_ARRAY_ELE % self._Token) 499 return self._Token 500 501 self.__SkipWS() 502 Expr = self._Expr[self._Idx:] 503 if not Expr.startswith(','): 504 return self._Token 505 506 NList = self._LiteralToken 507 while Expr.startswith(','): 508 NList += ',' 509 self._Idx += 1 510 self.__SkipWS() 511 self._GetSingleToken() 512 if not self.__IsHexLiteral(): 513 raise BadExpression(ERR_ARRAY_ELE % self._Token) 514 NList += self._LiteralToken 515 self.__SkipWS() 516 Expr = self._Expr[self._Idx:] 517 self._Token = self._LiteralToken = NList 518 return self._Token 519 520 def __IsHexLiteral(self): 521 if self._LiteralToken.startswith('{') and \ 522 self._LiteralToken.endswith('}'): 523 return True 524 525 if self.HexPattern.match(self._LiteralToken): 526 Token = self._LiteralToken[2:] 527 Token = Token.lstrip('0') 528 if not Token: 529 self._LiteralToken = '0x0' 530 else: 531 self._LiteralToken = '0x' + Token.lower() 532 return True 533 return False 534 535 def _GetToken(self): 536 return self.__GetNList() 537 538 @staticmethod 539 def __IsIdChar(Ch): 540 return Ch in '._/:' or Ch.isalnum() 541 542 # Parse operand 543 def _GetSingleToken(self): 544 self.__SkipWS() 545 Expr = self._Expr[self._Idx:] 546 if Expr.startswith('L"'): 547 # Skip L 548 self._Idx += 1 549 UStr = self.__GetString() 550 self._Token = 'L"' + UStr + '"' 551 return self._Token 552 553 self._Token = '' 554 if Expr: 555 Ch = Expr[0] 556 Match = self.RegGuidPattern.match(Expr) 557 if Match and not Expr[Match.end():Match.end()+1].isalnum() \ 558 and Expr[Match.end():Match.end()+1] != '_': 559 self._Idx += Match.end() 560 self._Token = ValueExpression(GuidStringToGuidStructureString(Expr[0:Match.end()]))(True, self._Depth+1) 561 return self._Token 562 elif self.__IsIdChar(Ch): 563 return self.__GetIdToken() 564 elif Ch == '"': 565 return self.__GetString() 566 elif Ch == '{': 567 return self.__GetArray() 568 elif Ch == '(' or Ch == ')': 569 self._Idx += 1 570 self._Token = Ch 571 return self._Token 572 573 raise BadExpression(ERR_VALID_TOKEN % Expr) 574 575 # Parse operator 576 def _GetOperator(self): 577 self.__SkipWS() 578 LegalOpLst = ['&&', '||', '!=', '==', '>=', '<='] + self.NonLetterOpLst 579 580 self._Token = '' 581 Expr = self._Expr[self._Idx:] 582 583 # Reach end of expression 584 if not Expr: 585 return '' 586 587 # Script operator: LT, GT, LE, GE, EQ, NE, and, or, xor, not 588 if Expr[0].isalpha(): 589 return self.__GetIdToken(True) 590 591 # Start to get regular operator: +, -, <, > ... 592 if Expr[0] not in self.NonLetterOpLst: 593 return '' 594 595 OpToken = '' 596 for Ch in Expr: 597 if Ch in self.NonLetterOpLst: 598 if '!' == Ch and OpToken: 599 break 600 self._Idx += 1 601 OpToken += Ch 602 else: 603 break 604 605 if OpToken not in LegalOpLst: 606 raise BadExpression(ERR_OPERATOR_UNSUPPORT % OpToken) 607 self._Token = OpToken 608 return OpToken 609 610 # Check if current token matches the operators given from OpList 611 def _IsOperator(self, OpList): 612 Idx = self._Idx 613 self._GetOperator() 614 if self._Token in OpList: 615 if self._Token in self.LogicalOperators: 616 self._Token = self.LogicalOperators[self._Token] 617 return True 618 self._Idx = Idx 619 return False 620 621if __name__ == '__main__': 622 pass 623 while True: 624 input = raw_input('Input expr: ') 625 if input in 'qQ': 626 break 627 try: 628 print ValueExpression(input)(True) 629 print ValueExpression(input)(False) 630 except WrnExpression, Ex: 631 print Ex.result 632 print str(Ex) 633 except Exception, Ex: 634 print str(Ex) 635