1 # a glorified C pre-processor parser 2 3 import sys, re, string 4 from utils import * 5 from defaults import * 6 7 debugTokens = False 8 debugDirectiveTokenizer = False 9 debugLineParsing = False 10 debugCppExpr = False 11 debugOptimIf01 = False 12 13 ##################################################################################### 14 ##################################################################################### 15 ##### ##### 16 ##### C P P T O K E N S ##### 17 ##### ##### 18 ##################################################################################### 19 ##################################################################################### 20 21 # the list of supported C-preprocessor tokens 22 # plus a couple of C tokens as well 23 tokEOF = "\0" 24 tokLN = "\n" 25 tokSTRINGIFY = "#" 26 tokCONCAT = "##" 27 tokLOGICAND = "&&" 28 tokLOGICOR = "||" 29 tokSHL = "<<" 30 tokSHR = ">>" 31 tokEQUAL = "==" 32 tokNEQUAL = "!=" 33 tokLT = "<" 34 tokLTE = "<=" 35 tokGT = ">" 36 tokGTE = ">=" 37 tokELLIPSIS = "..." 38 tokSPACE = " " 39 tokDEFINED = "defined" 40 tokLPAREN = "(" 41 tokRPAREN = ")" 42 tokNOT = "!" 43 tokPLUS = "+" 44 tokMINUS = "-" 45 tokMULTIPLY = "*" 46 tokDIVIDE = "/" 47 tokMODULUS = "%" 48 tokBINAND = "&" 49 tokBINOR = "|" 50 tokBINXOR = "^" 51 tokCOMMA = "," 52 tokLBRACE = "{" 53 tokRBRACE = "}" 54 tokARROW = "->" 55 tokINCREMENT = "++" 56 tokDECREMENT = "--" 57 tokNUMBER = "<number>" 58 tokIDENT = "<ident>" 59 tokSTRING = "<string>" 60 61 class Token: 62 """a simple class to hold information about a given token. 63 each token has a position in the source code, as well as 64 an 'id' and a 'value'. the id is a string that identifies 65 the token's class, while the value is the string of the 66 original token itself. 67 68 for example, the tokenizer concatenates a series of spaces 69 and tabs as a single tokSPACE id, whose value if the original 70 spaces+tabs sequence.""" 71 72 def __init__(self): 73 self.id = None 74 self.value = None 75 self.lineno = 0 76 self.colno = 0 77 78 def set(self,id,val=None): 79 self.id = id 80 if val: 81 self.value = val 82 else: 83 self.value = id 84 return None 85 86 def copyFrom(self,src): 87 self.id = src.id 88 self.value = src.value 89 self.lineno = src.lineno 90 self.colno = src.colno 91 92 def __repr__(self): 93 if self.id == tokIDENT: 94 return "(ident %s)" % self.value 95 if self.id == tokNUMBER: 96 return "(number %s)" % self.value 97 if self.id == tokSTRING: 98 return "(string '%s')" % self.value 99 if self.id == tokLN: 100 return "<LN>" 101 if self.id == tokEOF: 102 return "<EOF>" 103 if self.id == tokSPACE and self.value == "\\": 104 # this corresponds to a trailing \ that was transformed into a tokSPACE 105 return "<\\>" 106 107 return self.id 108 109 def __str__(self): 110 if self.id == tokIDENT: 111 return self.value 112 if self.id == tokNUMBER: 113 return self.value 114 if self.id == tokSTRING: 115 return self.value 116 if self.id == tokEOF: 117 return "<EOF>" 118 if self.id == tokSPACE: 119 if self.value == "\\": # trailing \ 120 return "\\\n" 121 else: 122 return self.value 123 124 return self.id 125 126 class BadExpectedToken(Exception): 127 def __init__(self,msg): 128 print msg 129 130 ##################################################################################### 131 ##################################################################################### 132 ##### ##### 133 ##### C P P T O K E N C U R S O R ##### 134 ##### ##### 135 ##################################################################################### 136 ##################################################################################### 137 138 class TokenCursor: 139 """a small class to iterate over a list of Token objects""" 140 def __init__(self,tokens): 141 self.tokens = tokens 142 self.n = 0 143 self.count = len(tokens) 144 145 def set(self,n): 146 """set the current position""" 147 if n < 0: 148 n = 0 149 if n > self.count: 150 n = self.count 151 self.n = n 152 153 def peekId(self): 154 """retrieve the id of the current token""" 155 if (self.n >= self.count): 156 return None 157 return self.tokens[self.n].id 158 159 def peek(self): 160 """retrieve the current token. does not change position""" 161 if (self.n >= self.count): 162 return None 163 return self.tokens[self.n] 164 165 def skip(self): 166 """increase current token position""" 167 if (self.n < self.count): 168 self.n += 1 169 170 def skipSpaces(self): 171 """skip over all space tokens, this includes tokSPACE and tokLN""" 172 while 1: 173 tok = self.peekId() 174 if tok != tokSPACE and tok != tokLN: 175 break 176 self.skip() 177 178 def skipIfId(self,id): 179 """skip an optional token""" 180 if self.peekId() == id: 181 self.skip() 182 183 def expectId(self,id): 184 """raise an exception if the current token hasn't a given id. 185 otherwise skip over it""" 186 tok = self.peek() 187 if tok.id != id: 188 raise BadExpectedToken, "%d:%d: '%s' expected, received '%s'" % (tok.lineno, tok.colno, id, tok.id) 189 self.skip() 190 191 def remain(self): 192 """return the list of remaining tokens""" 193 return self.tokens[self.n:] 194 195 196 ##################################################################################### 197 ##################################################################################### 198 ##### ##### 199 ##### C P P T O K E N I Z E R ##### 200 ##### ##### 201 ##################################################################################### 202 ##################################################################################### 203 204 # list of long symbols, i.e. those that take more than one characters 205 cppLongSymbols = [ tokCONCAT, tokLOGICAND, tokLOGICOR, tokSHL, tokSHR, tokELLIPSIS, tokEQUAL,\ 206 tokNEQUAL, tokLTE, tokGTE, tokARROW, tokINCREMENT, tokDECREMENT ] 207 208 class CppTokenizer: 209 """an abstract class used to convert some input text into a list 210 of tokens. real implementations follow and differ in the format 211 of the input text only""" 212 213 def __init__(self): 214 """initialize a new CppTokenizer object""" 215 self.eof = False # end of file reached ? 216 self.text = None # content of current line, with final \n stripped 217 self.line = 0 # number of current line 218 self.pos = 0 # current character position in current line 219 self.len = 0 # length of current line text 220 self.held = Token() 221 222 def setLineText(self,line): 223 """set the content of the (next) current line. should be called 224 by fillLineText() in derived classes""" 225 self.text = line 226 self.len = len(line) 227 self.pos = 0 228 229 def fillLineText(self): 230 """refresh the content of 'line' with a new line of input""" 231 # to be overriden 232 self.eof = True 233 234 def markPos(self,tok): 235 """mark the position of the current token in the source file""" 236 if self.eof or self.pos > self.len: 237 tok.lineno = self.line + 1 238 tok.colno = 0 239 else: 240 tok.lineno = self.line 241 tok.colno = self.pos 242 243 def peekChar(self): 244 """return the current token under the cursor without moving it""" 245 if self.eof: 246 return tokEOF 247 248 if self.pos > self.len: 249 self.pos = 0 250 self.line += 1 251 self.fillLineText() 252 if self.eof: 253 return tokEOF 254 255 if self.pos == self.len: 256 return tokLN 257 else: 258 return self.text[self.pos] 259 260 def peekNChar(self,n): 261 """try to peek the next n chars on the same line""" 262 if self.pos + n > self.len: 263 return None 264 return self.text[self.pos:self.pos+n] 265 266 def skipChar(self): 267 """increment the token cursor position""" 268 if not self.eof: 269 self.pos += 1 270 271 def skipNChars(self,n): 272 if self.pos + n <= self.len: 273 self.pos += n 274 else: 275 while n > 0: 276 self.skipChar() 277 n -= 1 278 279 def nextChar(self): 280 """retrieve the token at the current cursor position, then skip it""" 281 result = self.peekChar() 282 self.skipChar() 283 return result 284 285 def getEscape(self): 286 # try to get all characters after a backslash (\) 287 result = self.nextChar() 288 if result == "0": 289 # octal number ? 290 num = self.peekNChar(3) 291 if num != None: 292 isOctal = True 293 for d in num: 294 if not d in "01234567": 295 isOctal = False 296 break 297 if isOctal: 298 result += num 299 self.skipNChars(3) 300 elif result == "x" or result == "X": 301 # hex number ? 302 num = self.peekNChar(2) 303 if num != None: 304 isHex = True 305 for d in num: 306 if not d in "012345678abcdefABCDEF": 307 isHex = False 308 break 309 if isHex: 310 result += num 311 self.skipNChars(2) 312 elif result == "u" or result == "U": 313 # unicode char ? 314 num = self.peekNChar(4) 315 if num != None: 316 isHex = True 317 for d in num: 318 if not d in "012345678abcdefABCDEF": 319 isHex = False 320 break 321 if isHex: 322 result += num 323 self.skipNChars(4) 324 325 return result 326 327 def nextRealToken(self,tok): 328 """return next CPP token, used internally by nextToken()""" 329 c = self.nextChar() 330 if c == tokEOF or c == tokLN: 331 return tok.set(c) 332 333 if c == '/': 334 c = self.peekChar() 335 if c == '/': # C++ comment line 336 self.skipChar() 337 while 1: 338 c = self.nextChar() 339 if c == tokEOF or c == tokLN: 340 break 341 return tok.set(tokLN) 342 if c == '*': # C comment start 343 self.skipChar() 344 value = "/*" 345 prev_c = None 346 while 1: 347 c = self.nextChar() 348 if c == tokEOF: 349 #print "## EOF after '%s'" % value 350 return tok.set(tokEOF,value) 351 if c == '/' and prev_c == '*': 352 break 353 prev_c = c 354 value += c 355 356 value += "/" 357 #print "## COMMENT: '%s'" % value 358 return tok.set(tokSPACE,value) 359 c = '/' 360 361 if c.isspace(): 362 while 1: 363 c2 = self.peekChar() 364 if c2 == tokLN or not c2.isspace(): 365 break 366 c += c2 367 self.skipChar() 368 return tok.set(tokSPACE,c) 369 370 if c == '\\': 371 if debugTokens: 372 print "nextRealToken: \\ found, next token is '%s'" % repr(self.peekChar()) 373 if self.peekChar() == tokLN: # trailing \ 374 # eat the tokLN 375 self.skipChar() 376 # we replace a trailing \ by a tokSPACE whose value is 377 # simply "\\". this allows us to detect them later when 378 # needed. 379 return tok.set(tokSPACE,"\\") 380 else: 381 # treat as a single token here ? 382 c +=self.getEscape() 383 return tok.set(c) 384 385 if c == "'": # chars 386 c2 = self.nextChar() 387 c += c2 388 if c2 == '\\': 389 c += self.getEscape() 390 391 while 1: 392 c2 = self.nextChar() 393 if c2 == tokEOF: 394 break 395 c += c2 396 if c2 == "'": 397 break 398 399 return tok.set(tokSTRING, c) 400 401 if c == '"': # strings 402 quote = 0 403 while 1: 404 c2 = self.nextChar() 405 if c2 == tokEOF: 406 return tok.set(tokSTRING,c) 407 408 c += c2 409 if not quote: 410 if c2 == '"': 411 return tok.set(tokSTRING,c) 412 if c2 == "\\": 413 quote = 1 414 else: 415 quote = 0 416 417 if c >= "0" and c <= "9": # integers ? 418 while 1: 419 c2 = self.peekChar() 420 if c2 == tokLN or (not c2.isalnum() and c2 != "_"): 421 break 422 c += c2 423 self.skipChar() 424 return tok.set(tokNUMBER,c) 425 426 if c.isalnum() or c == "_": # identifiers ? 427 while 1: 428 c2 = self.peekChar() 429 if c2 == tokLN or (not c2.isalnum() and c2 != "_"): 430 break 431 c += c2 432 self.skipChar() 433 if c == tokDEFINED: 434 return tok.set(tokDEFINED) 435 else: 436 return tok.set(tokIDENT,c) 437 438 # check special symbols 439 for sk in cppLongSymbols: 440 if c == sk[0]: 441 sklen = len(sk[1:]) 442 if self.pos + sklen <= self.len and \ 443 self.text[self.pos:self.pos+sklen] == sk[1:]: 444 self.pos += sklen 445 return tok.set(sk) 446 447 return tok.set(c) 448 449 def nextToken(self,tok): 450 """return the next token from the input text. this function 451 really updates 'tok', and does not return a new one""" 452 self.markPos(tok) 453 self.nextRealToken(tok) 454 455 def getToken(self): 456 tok = Token() 457 self.nextToken(tok) 458 if debugTokens: 459 print "getTokens: %s" % repr(tok) 460 return tok 461 462 def toTokenList(self): 463 """convert the input text of a CppTokenizer into a direct 464 list of token objects. tokEOF is stripped from the result""" 465 result = [] 466 while 1: 467 tok = Token() 468 self.nextToken(tok) 469 if tok.id == tokEOF: 470 break 471 result.append(tok) 472 return result 473 474 class CppLineTokenizer(CppTokenizer): 475 """a CppTokenizer derived class that accepts a single line of text as input""" 476 def __init__(self,line,lineno=1): 477 CppTokenizer.__init__(self) 478 self.line = lineno 479 self.setLineText(line) 480 481 482 class CppLinesTokenizer(CppTokenizer): 483 """a CppTokenizer derived class that accepts a list of texdt lines as input. 484 the lines must not have a trailing \n""" 485 def __init__(self,lines=[],lineno=1): 486 """initialize a CppLinesTokenizer. you can later add lines using addLines()""" 487 CppTokenizer.__init__(self) 488 self.line = lineno 489 self.lines = lines 490 self.index = 0 491 self.count = len(lines) 492 493 if self.count > 0: 494 self.fillLineText() 495 else: 496 self.eof = True 497 498 def addLine(self,line): 499 """add a line to a CppLinesTokenizer. this can be done after tokenization 500 happens""" 501 if self.count == 0: 502 self.setLineText(line) 503 self.index = 1 504 self.lines.append(line) 505 self.count += 1 506 self.eof = False 507 508 def fillLineText(self): 509 if self.index < self.count: 510 self.setLineText(self.lines[self.index]) 511 self.index += 1 512 else: 513 self.eof = True 514 515 516 class CppFileTokenizer(CppTokenizer): 517 def __init__(self,file,lineno=1): 518 CppTokenizer.__init__(self) 519 self.file = file 520 self.line = lineno 521 522 def fillLineText(self): 523 line = self.file.readline() 524 if len(line) > 0: 525 if line[-1] == '\n': 526 line = line[:-1] 527 if len(line) > 0 and line[-1] == "\r": 528 line = line[:-1] 529 self.setLineText(line) 530 else: 531 self.eof = True 532 533 # Unit testing 534 # 535 class CppTokenizerTester: 536 """a class used to test CppTokenizer classes""" 537 def __init__(self,tokenizer=None): 538 self.tokenizer = tokenizer 539 self.token = Token() 540 541 def setTokenizer(self,tokenizer): 542 self.tokenizer = tokenizer 543 544 def expect(self,id): 545 self.tokenizer.nextToken(self.token) 546 tokid = self.token.id 547 if tokid == id: 548 return 549 if self.token.value == id and (tokid == tokIDENT or tokid == tokNUMBER): 550 return 551 raise BadExpectedToken, "### BAD TOKEN: '%s' expecting '%s'" % (self.token.id,id) 552 553 def expectToken(self,id,line,col): 554 self.expect(id) 555 if self.token.lineno != line: 556 raise BadExpectedToken, "### BAD LINENO: token '%s' got '%d' expecting '%d'" % (id,self.token.lineno,line) 557 if self.token.colno != col: 558 raise BadExpectedToken, "### BAD COLNO: '%d' expecting '%d'" % (self.token.colno,col) 559 560 def expectTokenVal(self,id,value,line,col): 561 self.expectToken(id,line,col) 562 if self.token.value != value: 563 raise BadExpectedToken, "### BAD VALUE: '%s' expecting '%s'" % (self.token.value,value) 564 565 def expectList(self,list): 566 for item in list: 567 self.expect(item) 568 569 def test_CppTokenizer(): 570 print "running CppTokenizer tests" 571 tester = CppTokenizerTester() 572 573 tester.setTokenizer( CppLineTokenizer("#an/example && (01923_xy)") ) 574 tester.expectList( ["#", "an", "/", "example", tokSPACE, tokLOGICAND, tokSPACE, tokLPAREN, "01923_xy", \ 575 tokRPAREN, tokLN, tokEOF] ) 576 577 tester.setTokenizer( CppLineTokenizer("FOO(BAR) && defined(BAZ)") ) 578 tester.expectList( ["FOO", tokLPAREN, "BAR", tokRPAREN, tokSPACE, tokLOGICAND, tokSPACE, 579 tokDEFINED, tokLPAREN, "BAZ", tokRPAREN, tokLN, tokEOF] ) 580 581 tester.setTokenizer( CppLinesTokenizer( ["/*", "#", "*/"] ) ) 582 tester.expectList( [ tokSPACE, tokLN, tokEOF ] ) 583 584 tester.setTokenizer( CppLinesTokenizer( ["first", "second"] ) ) 585 tester.expectList( [ "first", tokLN, "second", tokLN, tokEOF ] ) 586 587 tester.setTokenizer( CppLinesTokenizer( ["first second", " third"] ) ) 588 tester.expectToken( "first", 1, 0 ) 589 tester.expectToken( tokSPACE, 1, 5 ) 590 tester.expectToken( "second", 1, 6 ) 591 tester.expectToken( tokLN, 1, 12 ) 592 tester.expectToken( tokSPACE, 2, 0 ) 593 tester.expectToken( "third", 2, 2 ) 594 595 tester.setTokenizer( CppLinesTokenizer( [ "boo /* what the", "hell */" ] ) ) 596 tester.expectList( [ "boo", tokSPACE ] ) 597 tester.expectTokenVal( tokSPACE, "/* what the\nhell */", 1, 4 ) 598 tester.expectList( [ tokLN, tokEOF ] ) 599 600 tester.setTokenizer( CppLinesTokenizer( [ "an \\", " example" ] ) ) 601 tester.expectToken( "an", 1, 0 ) 602 tester.expectToken( tokSPACE, 1, 2 ) 603 tester.expectTokenVal( tokSPACE, "\\", 1, 3 ) 604 tester.expectToken( tokSPACE, 2, 0 ) 605 tester.expectToken( "example", 2, 1 ) 606 tester.expectToken( tokLN, 2, 8 ) 607 608 return True 609 610 611 ##################################################################################### 612 ##################################################################################### 613 ##### ##### 614 ##### C P P E X P R E S S I O N S ##### 615 ##### ##### 616 ##################################################################################### 617 ##################################################################################### 618 619 # Cpp expressions are modeled by tuples of the form (op,arg) or (op,arg1,arg2), etc.. 620 # op is an "operator" string 621 622 class Expr: 623 """a class used to model a CPP expression""" 624 opInteger = "int" 625 opIdent = "ident" 626 opCall = "call" 627 opDefined = "defined" 628 opTest = "?" 629 opLogicNot = "!" 630 opNot = "~" 631 opNeg = "[-]" 632 opUnaryPlus = "[+]" 633 opAdd = "+" 634 opSub = "-" 635 opMul = "*" 636 opDiv = "/" 637 opMod = "%" 638 opAnd = "&" 639 opOr = "|" 640 opXor = "^" 641 opLogicAnd = "&&" 642 opLogicOr = "||" 643 opEqual = "==" 644 opNotEqual = "!=" 645 opLess = "<" 646 opLessEq = "<=" 647 opGreater = ">" 648 opGreaterEq = ">=" 649 opShl = "<<" 650 opShr = ">>" 651 652 unaries = [ opLogicNot, opNot, opNeg, opUnaryPlus ] 653 binaries = [ opAdd, opSub, opMul, opDiv, opMod, opAnd, opOr, opXor, opLogicAnd, opLogicOr, 654 opEqual, opNotEqual, opLess, opLessEq, opGreater, opGreaterEq ] 655 656 precedences = { 657 opTest: 0, 658 opLogicOr: 1, 659 opLogicNot: 2, 660 opOr : 3, 661 opXor: 4, 662 opAnd: 5, 663 opEqual: 6, opNotEqual: 6, 664 opLess:7, opLessEq:7, opGreater:7, opGreaterEq:7, 665 opShl:8, opShr:8, 666 opAdd:9, opSub:9, 667 opMul:10, opDiv:10, opMod:10, 668 opLogicNot:11, 669 opNot: 12, 670 } 671 672 def __init__(self,op): 673 self.op = op 674 675 def __repr__(self): 676 return "(%s)" % self.op 677 678 def __str__(self): 679 return "operator(%s)" % self.op 680 681 def precedence(self): 682 """return the precedence of a given operator""" 683 return Expr.precedences.get(self.op, 1000) 684 685 def isUnary(self): 686 return self.op in Expr.unaries 687 688 def isBinary(self): 689 return self.op in Expr.binaries 690 691 def isDefined(self): 692 return self.op is opDefined 693 694 def toInt(self): 695 """return the integer value of a given expression. only valid for integer expressions 696 will return None otherwise""" 697 return None 698 699 class IntExpr(Expr): 700 def __init__(self,value): 701 Expr.__init__(self,opInteger) 702 self.arg = value 703 704 def __repr__(self): 705 return "(int %s)" % self.arg 706 707 def __str__(self): 708 return self.arg 709 710 def toInt(self): 711 s = self.arg # string value 712 # get rid of U or L suffixes 713 while len(s) > 0 and s[-1] in "LUlu": 714 s = s[:-1] 715 return string.atoi(s) 716 717 class IdentExpr(Expr): 718 def __init__(self,name): 719 Expr.__init__(self,opIdent) 720 self.name = name 721 722 def __repr__(self): 723 return "(ident %s)" % self.name 724 725 def __str__(self): 726 return self.name 727 728 class CallExpr(Expr): 729 def __init__(self,funcname,params): 730 Expr.__init__(self,opCall) 731 self.funcname = funcname 732 self.params = params 733 734 def __repr__(self): 735 result = "(call %s [" % self.funcname 736 comma = "" 737 for param in self.params: 738 result += "%s%s" % (comma, repr(param)) 739 comma = "," 740 result += "])" 741 return result 742 743 def __str__(self): 744 result = "%s(" % self.funcname 745 comma = "" 746 for param in self.params: 747 result += "%s%s" % (comma, str(param)) 748 comma = "," 749 750 result += ")" 751 return result 752 753 class TestExpr(Expr): 754 def __init__(self,cond,iftrue,iffalse): 755 Expr.__init__(self,opTest) 756 self.cond = cond 757 self.iftrue = iftrue 758 self.iffalse = iffalse 759 760 def __repr__(self): 761 return "(?: %s %s %s)" % (repr(self.cond),repr(self.iftrue),repr(self.iffalse)) 762 763 def __str__(self): 764 return "(%s) ? (%s) : (%s)" % (self.cond, self.iftrue, self.iffalse) 765 766 class SingleArgExpr(Expr): 767 def __init__(self,op,arg): 768 Expr.__init__(self,op) 769 self.arg = arg 770 771 def __repr__(self): 772 return "(%s %s)" % (self.op, repr(self.arg)) 773 774 class DefinedExpr(SingleArgExpr): 775 def __init__(self,op,macroname): 776 SingleArgExpr.__init__(self.opDefined,macroname) 777 778 def __str__(self): 779 return "defined(%s)" % self.arg 780 781 782 class UnaryExpr(SingleArgExpr): 783 def __init__(self,op,arg,opstr=None): 784 SingleArgExpr.__init__(self,op,arg) 785 if not opstr: 786 opstr = op 787 self.opstr = opstr 788 789 def __str__(self): 790 arg_s = str(self.arg) 791 arg_prec = self.arg.precedence() 792 self_prec = self.precedence() 793 if arg_prec < self_prec: 794 return "%s(%s)" % (self.opstr,arg_s) 795 else: 796 return "%s%s" % (self.opstr, arg_s) 797 798 class TwoArgExpr(Expr): 799 def __init__(self,op,arg1,arg2): 800 Expr.__init__(self,op) 801 self.arg1 = arg1 802 self.arg2 = arg2 803 804 def __repr__(self): 805 return "(%s %s %s)" % (self.op, repr(self.arg1), repr(self.arg2)) 806 807 class BinaryExpr(TwoArgExpr): 808 def __init__(self,op,arg1,arg2,opstr=None): 809 TwoArgExpr.__init__(self,op,arg1,arg2) 810 if not opstr: 811 opstr = op 812 self.opstr = opstr 813 814 def __str__(self): 815 arg1_s = str(self.arg1) 816 arg2_s = str(self.arg2) 817 arg1_prec = self.arg1.precedence() 818 arg2_prec = self.arg2.precedence() 819 self_prec = self.precedence() 820 821 result = "" 822 if arg1_prec < self_prec: 823 result += "(%s)" % arg1_s 824 else: 825 result += arg1_s 826 827 result += " %s " % self.opstr 828 829 if arg2_prec < self_prec: 830 result += "(%s)" % arg2_s 831 else: 832 result += arg2_s 833 834 return result 835 836 ##################################################################################### 837 ##################################################################################### 838 ##### ##### 839 ##### C P P E X P R E S S I O N P A R S E R ##### 840 ##### ##### 841 ##################################################################################### 842 ##################################################################################### 843 844 845 class ExprParser: 846 """a class used to convert a list of tokens into a cpp Expr object""" 847 848 re_octal = re.compile(r"\s*\(0[0-7]+\).*") 849 re_decimal = re.compile(r"\s*\(\d+[ulUL]*\).*") 850 re_hexadecimal = re.compile(r"\s*\(0[xX][0-9a-fA-F]*\).*") 851 852 def __init__(self,tokens): 853 self.tok = tokens 854 self.n = len(self.tok) 855 self.i = 0 856 857 def mark(self): 858 return self.i 859 860 def release(self,pos): 861 self.i = pos 862 863 def peekId(self): 864 if self.i < self.n: 865 return self.tok[self.i].id 866 return None 867 868 def peek(self): 869 if self.i < self.n: 870 return self.tok[self.i] 871 return None 872 873 def skip(self): 874 if self.i < self.n: 875 self.i += 1 876 877 def skipOptional(self,id): 878 if self.i < self.n and self.tok[self.i].id == id: 879 self.i += 1 880 881 def skipSpaces(self): 882 i = self.i 883 n = self.n 884 tok = self.tok 885 while i < n and (tok[i] == tokSPACE or tok[i] == tokLN): 886 i += 1 887 self.i = i 888 889 # all the isXXX functions returns a (expr,nextpos) pair if a match is found 890 # or None if not 891 892 def is_integer(self): 893 id = self.tok[self.i].id 894 c = id[0] 895 if c < '0' or c > '9': 896 return None 897 898 m = ExprParser.re_octal.match(id) 899 if m: 900 return (IntExpr(id), m.end(1)) 901 902 m = ExprParser.re_decimal.match(id) 903 if m: 904 return (IntExpr(id), m.end(1)) 905 906 m = ExprParser.re_hexadecimal(id) 907 if m: 908 return (IntExpr(id), m.end(1)) 909 910 return None 911 912 def is_defined(self): 913 id = self.tok[self.i].id 914 if id != "defined": 915 return None 916 917 pos = self.mark() 918 919 use_paren = 0 920 if self.peekId() == tokLPAREN: 921 self.skip() 922 use_paren = 1 923 924 if self.peekId() != tokIDENT: 925 self.throw( BadExpectedToken, "identifier expected") 926 927 macroname = self.peek().value 928 self.skip() 929 if use_paren: 930 self.skipSpaces() 931 if self.peekId() != tokRPAREN: 932 self.throw( BadExpectedToken, "missing right-paren after 'defined' directive") 933 self.skip() 934 935 i = self.i 936 return (DefinedExpr(macroname),i+1) 937 938 def is_call_or_ident(self): 939 pass 940 941 def parse(self, i): 942 return None 943 944 ##################################################################################### 945 ##################################################################################### 946 ##### ##### 947 ##### C P P E X P R E S S I O N S ##### 948 ##### ##### 949 ##################################################################################### 950 ##################################################################################### 951 952 class CppInvalidExpression(Exception): 953 """an exception raised when an invalid/unsupported cpp expression is detected""" 954 pass 955 956 class CppExpr: 957 """a class that models the condition of #if directives into 958 an expression tree. each node in the tree is of the form (op,arg) or (op,arg1,arg2) 959 where "op" is a string describing the operation""" 960 961 unaries = [ "!", "~" ] 962 binaries = [ "+", "-", "<", "<=", ">=", ">", "&&", "||", "*", "/", "%", "&", "|", "^", "<<", ">>", "==", "!=" ] 963 precedences = { "||": 1, 964 "&&": 2, 965 "|": 3, 966 "^": 4, 967 "&": 5, 968 "==":6, "!=":6, 969 "<":7, "<=":7, ">":7, ">=":7, 970 "<<":8, ">>":8, 971 "+":9, "-":9, 972 "*":10, "/":10, "%":10, 973 "!":11, "~":12 974 } 975 976 def __init__(self, tokens): 977 """initialize a CppExpr. 'tokens' must be a CppToken list""" 978 self.tok = tokens 979 self.n = len(tokens) 980 if debugCppExpr: 981 print "CppExpr: trying to parse %s" % repr(tokens) 982 expr = self.is_expr(0) 983 if debugCppExpr: 984 print "CppExpr: got " + repr(expr) 985 self.expr = expr[0] 986 987 re_cpp_constant = re.compile(r"((\d|\w|_)+)") 988 989 def throw(self,exception,i,msg): 990 if i < self.n: 991 tok = self.tok[i] 992 print "%d:%d: %s" % (tok.lineno,tok.colno,msg) 993 else: 994 print "EOF: %s" % msg 995 raise exception 996 997 def skip_spaces(self,i): 998 """skip spaces in input token list""" 999 while i < self.n: 1000 t = self.tok[i] 1001 if t.id != tokSPACE and t.id != tokLN: 1002 break 1003 i += 1 1004 return i 1005 1006 def expectId(self,i,id): 1007 """check that a given token id is at the current position, then skip over it""" 1008 i = self.skip_spaces(i) 1009 if i >= self.n or self.tok[i].id != id: 1010 self.throw(BadExpectedToken,i,"### expecting '%s' in expression, got '%s'" % (id, self.tok[i].id)) 1011 return i+1 1012 1013 def expectIdent(self,i): 1014 i = self.skip_spaces(i) 1015 if i >= self.n or self.tok[i].id != tokIDENT: 1016 self.throw(BadExpectedToken,i,"### expecting identifier in expression, got '%s'" % (id, self.tok[i].id)) 1017 return i+1 1018 1019 # the is_xxxxx function returns either None or a pair (e,nextpos) 1020 # where 'e' is an expression tuple (e.g. (op,arg)) and 'nextpos' is 1021 # the corresponding next position in the input token list 1022 # 1023 1024 def is_decimal(self,i): 1025 v = self.tok[i].value[:] 1026 while len(v) > 0 and v[-1] in "ULul": 1027 v = v[:-1] 1028 for digit in v: 1029 if not digit.isdigit(): 1030 return None 1031 1032 # for an integer expression tuple, the argument 1033 # is simply the value as an integer 1034 val = string.atoi(v) 1035 return ("int", val), i+1 1036 1037 def is_hexadecimal(self,i): 1038 v = self.tok[i].value[:] 1039 while len(v) > 0 and v[-1] in "ULul": 1040 v = v[:-1] 1041 if len(v) > 2 and (v[0:2] == "0x" or v[0:2] == "0X"): 1042 for digit in v[2:]: 1043 if not digit in "0123456789abcdefABCDEF": 1044 return None 1045 1046 # for an hex expression tuple, the argument 1047 # is the value as an integer 1048 val = int(v[2:], 16) 1049 return ("hex", val), i+1 1050 1051 return None 1052 1053 def is_integer(self,i): 1054 if self.tok[i].id != tokNUMBER: 1055 return None 1056 1057 c = self.is_decimal(i) 1058 if c: return c 1059 1060 c = self.is_hexadecimal(i) 1061 if c: return c 1062 1063 return None 1064 1065 def is_number(self,i): 1066 t = self.tok[i] 1067 if t.id == tokMINUS and i+1 < self.n: 1068 c = self.is_integer(i+1) 1069 if c: 1070 e, i2 = c 1071 op, val = e 1072 return (op, -val), i2 1073 if t.id == tokPLUS and i+1 < self.n: 1074 c = self.is_integer(i+1) 1075 if c: return c 1076 1077 return self.is_integer(i) 1078 1079 1080 def is_alnum(self,i): 1081 """test wether a given token is alpha-numeric""" 1082 i = self.skip_spaces(i) 1083 if i >= self.n: 1084 return None 1085 t = self.tok[i] 1086 m = CppExpr.re_cpp_constant.match(t.id) 1087 if m: 1088 #print "... alnum '%s'" % m.group(1) 1089 r = m.group(1) 1090 return ("ident", r), i+1 1091 return None 1092 1093 def is_defined(self,i): 1094 t = self.tok[i] 1095 if t.id != tokDEFINED: 1096 return None 1097 1098 # we have the defined keyword, check the rest 1099 i = self.skip_spaces(i+1) 1100 use_parens = 0 1101 if i < self.n and self.tok[i].id == tokLPAREN: 1102 use_parens = 1 1103 i = self.skip_spaces(i+1) 1104 1105 if i >= self.n: 1106 self.throw(CppConstantExpected,i,"### 'defined' must be followed by macro name or left paren") 1107 1108 t = self.tok[i] 1109 if t.id != tokIDENT: 1110 self.throw(CppConstantExpected,i,"### 'defined' must be followed by macro name") 1111 1112 i += 1 1113 if use_parens: 1114 i = self.expectId(i,tokRPAREN) 1115 1116 return ("defined",t.value), i 1117 1118 1119 def is_call_or_ident(self,i): 1120 i = self.skip_spaces(i) 1121 if i >= self.n: 1122 return None 1123 1124 t = self.tok[i] 1125 if t.id != tokIDENT: 1126 return None 1127 1128 name = t.value 1129 1130 i = self.skip_spaces(i+1) 1131 if i >= self.n or self.tok[i].id != tokLPAREN: 1132 return ("ident", name), i 1133 1134 params = [] 1135 depth = 1 1136 i += 1 1137 j = i 1138 while i < self.n: 1139 id = self.tok[i].id 1140 if id == tokLPAREN: 1141 depth += 1 1142 elif depth == 1 and (id == tokCOMMA or id == tokRPAREN): 1143 while j < i and self.tok[j].id == tokSPACE: 1144 j += 1 1145 k = i 1146 while k > j and self.tok[k-1].id == tokSPACE: 1147 k -= 1 1148 param = self.tok[j:k] 1149 params.append( param ) 1150 if id == tokRPAREN: 1151 break 1152 j = i+1 1153 elif id == tokRPAREN: 1154 depth -= 1 1155 i += 1 1156 1157 if i >= self.n: 1158 return None 1159 1160 return ("call", (name, params)), i+1 1161 1162 def is_token(self,i,token): 1163 i = self.skip_spaces(i) 1164 if i >= self.n or self.tok[i].id != token: 1165 return None 1166 return token, i+1 1167 1168 1169 def is_value(self,i): 1170 t = self.tok[i] 1171 if t.id == tokSTRING: 1172 return ("string", t.value), i+1 1173 1174 c = self.is_number(i) 1175 if c: return c 1176 1177 c = self.is_defined(i) 1178 if c: return c 1179 1180 c = self.is_call_or_ident(i) 1181 if c: return c 1182 1183 i = self.skip_spaces(i) 1184 if i >= self.n or self.tok[i].id != tokLPAREN: 1185 return None 1186 1187 popcount = 1 1188 i2 = i+1 1189 while i2 < self.n: 1190 t = self.tok[i2] 1191 if t.id == tokLPAREN: 1192 popcount += 1 1193 elif t.id == tokRPAREN: 1194 popcount -= 1 1195 if popcount == 0: 1196 break 1197 i2 += 1 1198 1199 if popcount != 0: 1200 self.throw(CppInvalidExpression, i, "expression missing closing parenthesis") 1201 1202 if debugCppExpr: 1203 print "CppExpr: trying to parse sub-expression %s" % repr(self.tok[i+1:i2]) 1204 oldcount = self.n 1205 self.n = i2 1206 c = self.is_expr(i+1) 1207 self.n = oldcount 1208 if not c: 1209 self.throw(CppInvalidExpression, i, "invalid expression within parenthesis") 1210 1211 e, i = c 1212 return e, i2+1 1213 1214 def is_unary(self,i): 1215 i = self.skip_spaces(i) 1216 if i >= self.n: 1217 return None 1218 1219 t = self.tok[i] 1220 if t.id in CppExpr.unaries: 1221 c = self.is_unary(i+1) 1222 if not c: 1223 self.throw(CppInvalidExpression, i, "%s operator must be followed by value" % t.id) 1224 e, i = c 1225 return (t.id, e), i 1226 1227 return self.is_value(i) 1228 1229 def is_binary(self,i): 1230 i = self.skip_spaces(i) 1231 if i >= self.n: 1232 return None 1233 1234 c = self.is_unary(i) 1235 if not c: 1236 return None 1237 1238 e1, i2 = c 1239 i2 = self.skip_spaces(i2) 1240 if i2 >= self.n: 1241 return c 1242 1243 t = self.tok[i2] 1244 if t.id in CppExpr.binaries: 1245 c = self.is_binary(i2+1) 1246 if not c: 1247 self.throw(CppInvalidExpression, i,"### %s operator must be followed by value" % t.id ) 1248 e2, i3 = c 1249 return (t.id, e1, e2), i3 1250 1251 return None 1252 1253 def is_expr(self,i): 1254 return self.is_binary(i) 1255 1256 def dump_node(self,e): 1257 op = e[0] 1258 line = "(" + op 1259 if op == "int": 1260 line += " %d)" % e[1] 1261 elif op == "hex": 1262 line += " 0x%x)" % e[1] 1263 elif op == "ident": 1264 line += " %s)" % e[1] 1265 elif op == "defined": 1266 line += " %s)" % e[1] 1267 elif op == "call": 1268 arg = e[1] 1269 line += " %s [" % arg[0] 1270 prefix = "" 1271 for param in arg[1]: 1272 par = "" 1273 for tok in param: 1274 par += str(tok) 1275 line += "%s%s" % (prefix, par) 1276 prefix = "," 1277 line += "])" 1278 elif op in CppExpr.unaries: 1279 line += " %s)" % self.dump_node(e[1]) 1280 elif op in CppExpr.binaries: 1281 line += " %s %s)" % (self.dump_node(e[1]), self.dump_node(e[2])) 1282 else: 1283 line += " ?%s)" % repr(e[1]) 1284 1285 return line 1286 1287 def __repr__(self): 1288 return self.dump_node(self.expr) 1289 1290 def source_node(self,e): 1291 op = e[0] 1292 if op == "int": 1293 return "%d" % e[1] 1294 if op == "hex": 1295 return "0x%x" % e[1] 1296 if op == "ident": 1297 # XXX: should try to expand 1298 return e[1] 1299 if op == "defined": 1300 return "defined(%s)" % e[1] 1301 1302 prec = CppExpr.precedences.get(op,1000) 1303 arg = e[1] 1304 if op in CppExpr.unaries: 1305 arg_src = self.source_node(arg) 1306 arg_op = arg[0] 1307 arg_prec = CppExpr.precedences.get(arg[0],1000) 1308 if arg_prec < prec: 1309 return "!(" + arg_src + ")" 1310 else: 1311 return "!" + arg_src 1312 if op in CppExpr.binaries: 1313 arg2 = e[2] 1314 arg1_op = arg[0] 1315 arg2_op = arg2[0] 1316 arg1_src = self.source_node(arg) 1317 arg2_src = self.source_node(arg2) 1318 if CppExpr.precedences.get(arg1_op,1000) < prec: 1319 arg1_src = "(%s)" % arg1_src 1320 if CppExpr.precedences.get(arg2_op,1000) < prec: 1321 arg2_src = "(%s)" % arg2_src 1322 1323 return "%s %s %s" % (arg1_src, op, arg2_src) 1324 return "???" 1325 1326 def __str__(self): 1327 return self.source_node(self.expr) 1328 1329 def int_node(self,e): 1330 if e[0] == "int": 1331 return e[1] 1332 elif e[1] == "hex": 1333 return int(e[1],16) 1334 else: 1335 return None 1336 1337 def toInt(self): 1338 return self.int_node(self.expr) 1339 1340 def optimize_node(self,e,macros={}): 1341 op = e[0] 1342 if op == "defined": 1343 name = e[1] 1344 if macros.has_key(name): 1345 if macros[name] == kCppUndefinedMacro: 1346 return ("int", 0) 1347 else: 1348 return ("int", 1) 1349 1350 if kernel_remove_config_macros and name.startswith("CONFIG_"): 1351 return ("int", 0) 1352 1353 elif op == "!": 1354 op, v = e 1355 v = self.optimize_node(v, macros) 1356 if v[0] == "int": 1357 if v[1] == 0: 1358 return ("int", 1) 1359 else: 1360 return ("int", 0) 1361 1362 elif op == "&&": 1363 op, l, r = e 1364 l = self.optimize_node(l, macros) 1365 r = self.optimize_node(r, macros) 1366 li = self.int_node(l) 1367 ri = self.int_node(r) 1368 if li != None: 1369 if li == 0: 1370 return ("int", 0) 1371 else: 1372 return r 1373 1374 elif op == "||": 1375 op, l, r = e 1376 l = self.optimize_node(l, macros) 1377 r = self.optimize_node(r, macros) 1378 li = self.int_node(l) 1379 ri = self.int_node(r) 1380 if li != None: 1381 if li == 0: 1382 return r 1383 else: 1384 return ("int", 1) 1385 elif ri != None: 1386 if ri == 0: 1387 return l 1388 else: 1389 return ("int", 1) 1390 return e 1391 1392 def optimize(self,macros={}): 1393 self.expr = self.optimize_node(self.expr,macros) 1394 1395 def removePrefixedNode(self,e,prefix,names): 1396 op = e[0] 1397 if op == "defined": 1398 name = e[1] 1399 if name.startswith(prefix): 1400 if names.has_key[name] and names[name] == "y": 1401 return ("int", 1) 1402 else: 1403 return ("int", 0) 1404 1405 elif op in CppExpr.unaries: 1406 op, v = e 1407 v = self.removePrefixedNode(v,prefix,names) 1408 return (op, v) 1409 elif op in CppExpr.binaries: 1410 op, v1, v2 = e 1411 v1 = self.removePrefixedNode(v1,prefix,names) 1412 v2 = self.removePrefixedNode(v2,prefix,names) 1413 return (op, v1, v2) 1414 elif op == "call": 1415 func, params = e[1] 1416 params2 = [] 1417 for param in params: 1418 params2.append( self.removePrefixedNode(param,prefix,names) ) 1419 return (op, (func, params2)) 1420 1421 return e 1422 1423 def removePrefixed(self,prefix,names={}): 1424 self.expr = self.removePrefixedNode(self.expr,prefix,names) 1425 1426 def is_equal_node(self,e1,e2): 1427 if e1[0] != e2[0] or len(e1) != len(e2): 1428 return False 1429 1430 op = e1[0] 1431 if op == "int" or op == "hex" or op == "!" or op == "defined": 1432 return e1[0] == e2[0] 1433 1434 return self.is_equal_node(e1[1],e2[1]) and self.is_equal_node(e1[2],e2[2]) 1435 1436 def is_equal(self,other): 1437 return self.is_equal_node(self.expr,other.expr) 1438 1439 def test_cpp_expr(expr, expected): 1440 e = CppExpr( CppLineTokenizer( expr ).toTokenList() ) 1441 #print repr(e.expr) 1442 s1 = repr(e) 1443 if s1 != expected: 1444 print "KO: expression '%s' generates '%s', should be '%s'" % (expr, s1, expected) 1445 else: 1446 #print "OK: expression '%s'" % expr 1447 pass 1448 1449 def test_cpp_expr_optim(expr, expected, macros={}): 1450 e = CppExpr( CppLineTokenizer( expr ).toTokenList() ) 1451 e.optimize(macros) 1452 1453 s1 = repr(e) 1454 if s1 != expected: 1455 print "KO: optimized expression '%s' generates '%s', should be '%s'" % (expr, s1, expected) 1456 else: 1457 #print "OK: optmized expression '%s'" % expr 1458 pass 1459 1460 def test_cpp_expr_source(expr, expected): 1461 e = CppExpr( CppLineTokenizer( expr ).toTokenList() ) 1462 s1 = str(e) 1463 if s1 != expected: 1464 print "KO: source expression '%s' generates '%s', should be '%s'" % (expr, s1, expected) 1465 else: 1466 #print "OK: source expression '%s'" % expr 1467 pass 1468 1469 def test_CppExpr(): 1470 print "testing CppExpr" 1471 test_cpp_expr( "0", "(int 0)" ) 1472 test_cpp_expr( "1", "(int 1)" ) 1473 test_cpp_expr( "1 && 1", "(&& (int 1) (int 1))" ) 1474 test_cpp_expr( "1 && 0", "(&& (int 1) (int 0))" ) 1475 test_cpp_expr( "EXAMPLE", "(ident EXAMPLE)" ) 1476 test_cpp_expr( "EXAMPLE - 3", "(- (ident EXAMPLE) (int 3))" ) 1477 test_cpp_expr( "defined(EXAMPLE)", "(defined EXAMPLE)" ) 1478 test_cpp_expr( "!defined(EXAMPLE)", "(! (defined EXAMPLE))" ) 1479 test_cpp_expr( "defined(ABC) || defined(BINGO)", "(|| (defined ABC) (defined BINGO))" ) 1480 test_cpp_expr( "FOO(BAR)", "(call FOO [BAR])" ) 1481 1482 test_cpp_expr_optim( "0", "(int 0)" ) 1483 test_cpp_expr_optim( "1", "(int 1)" ) 1484 test_cpp_expr_optim( "1 && 1", "(int 1)" ) 1485 test_cpp_expr_optim( "1 && 0", "(int 0)" ) 1486 test_cpp_expr_optim( "0 && 1", "(int 0)" ) 1487 test_cpp_expr_optim( "0 && 0", "(int 0)" ) 1488 test_cpp_expr_optim( "1 || 1", "(int 1)" ) 1489 test_cpp_expr_optim( "1 || 0", "(int 1)" ) 1490 test_cpp_expr_optim( "0 || 1", "(int 1)" ) 1491 test_cpp_expr_optim( "0 || 0", "(int 0)" ) 1492 test_cpp_expr_optim( "EXAMPLE", "(ident EXAMPLE)" ) 1493 test_cpp_expr_optim( "EXAMPLE - 3", "(- (ident EXAMPLE) (int 3))" ) 1494 test_cpp_expr_optim( "defined(EXAMPLE)", "(defined EXAMPLE)" ) 1495 test_cpp_expr_optim( "defined(EXAMPLE)", "(int 1)", { "EXAMPLE": "XOWOE" } ) 1496 test_cpp_expr_optim( "defined(EXAMPLE)", "(int 0)", { "EXAMPLE": kCppUndefinedMacro} ) 1497 test_cpp_expr_optim( "!defined(EXAMPLE)", "(! (defined EXAMPLE))" ) 1498 test_cpp_expr_optim( "!defined(EXAMPLE)", "(int 0)", { "EXAMPLE" : "XOWOE" } ) 1499 test_cpp_expr_optim( "!defined(EXAMPLE)", "(int 1)", { "EXAMPLE" : kCppUndefinedMacro } ) 1500 test_cpp_expr_optim( "defined(ABC) || defined(BINGO)", "(|| (defined ABC) (defined BINGO))" ) 1501 test_cpp_expr_optim( "defined(ABC) || defined(BINGO)", "(int 1)", { "ABC" : "1" } ) 1502 test_cpp_expr_optim( "defined(ABC) || defined(BINGO)", "(int 1)", { "BINGO" : "1" } ) 1503 test_cpp_expr_optim( "defined(ABC) || defined(BINGO)", "(defined ABC)", { "BINGO" : kCppUndefinedMacro } ) 1504 test_cpp_expr_optim( "defined(ABC) || defined(BINGO)", "(int 0)", { "ABC" : kCppUndefinedMacro, "BINGO" : kCppUndefinedMacro } ) 1505 1506 test_cpp_expr_source( "0", "0" ) 1507 test_cpp_expr_source( "1", "1" ) 1508 test_cpp_expr_source( "1 && 1", "1 && 1" ) 1509 test_cpp_expr_source( "1 && 0", "1 && 0" ) 1510 test_cpp_expr_source( "0 && 1", "0 && 1" ) 1511 test_cpp_expr_source( "0 && 0", "0 && 0" ) 1512 test_cpp_expr_source( "1 || 1", "1 || 1" ) 1513 test_cpp_expr_source( "1 || 0", "1 || 0" ) 1514 test_cpp_expr_source( "0 || 1", "0 || 1" ) 1515 test_cpp_expr_source( "0 || 0", "0 || 0" ) 1516 test_cpp_expr_source( "EXAMPLE", "EXAMPLE" ) 1517 test_cpp_expr_source( "EXAMPLE - 3", "EXAMPLE - 3" ) 1518 test_cpp_expr_source( "defined(EXAMPLE)", "defined(EXAMPLE)" ) 1519 test_cpp_expr_source( "defined EXAMPLE", "defined(EXAMPLE)" ) 1520 1521 1522 ##################################################################################### 1523 ##################################################################################### 1524 ##### ##### 1525 ##### C P P B L O C K ##### 1526 ##### ##### 1527 ##################################################################################### 1528 ##################################################################################### 1529 1530 class Block: 1531 """a class used to model a block of input source text. there are two block types: 1532 - direcive blocks: contain the tokens of a single pre-processor directive (e.g. #if) 1533 - text blocks, contain the tokens of non-directive blocks 1534 1535 the cpp parser class below will transform an input source file into a list of Block 1536 objects (grouped in a BlockList object for convenience)""" 1537 1538 def __init__(self,tokens,directive=None,lineno=0): 1539 """initialize a new block, if 'directive' is None, this is a text block 1540 NOTE: this automatically converts '#ifdef MACRO' into '#if defined(MACRO)' 1541 and '#ifndef MACRO' into '#if !defined(MACRO)'""" 1542 if directive == "ifdef": 1543 tok = Token() 1544 tok.set(tokDEFINED) 1545 tokens = [ tok ] + tokens 1546 directive = "if" 1547 1548 elif directive == "ifndef": 1549 tok1 = Token() 1550 tok2 = Token() 1551 tok1.set(tokNOT) 1552 tok2.set(tokDEFINED) 1553 tokens = [ tok1, tok2 ] + tokens 1554 directive = "if" 1555 1556 self.tokens = tokens 1557 self.directive = directive 1558 if lineno > 0: 1559 self.lineno = lineno 1560 else: 1561 self.lineno = self.tokens[0].lineno 1562 1563 if self.isIf(): 1564 self.expr = CppExpr( self.tokens ) 1565 1566 def isDirective(self): 1567 """returns True iff this is a directive block""" 1568 return self.directive != None 1569 1570 def isConditional(self): 1571 """returns True iff this is a conditional directive block""" 1572 return self.directive in ["if","ifdef","ifndef","else","elif","endif"] 1573 1574 def isDefine(self): 1575 """returns the macro name in a #define directive, or None otherwise""" 1576 if self.directive != "define": 1577 return None 1578 1579 return self.tokens[0].value 1580 1581 def isIf(self): 1582 """returns True iff this is an #if-like directive block""" 1583 return self.directive in ["if","ifdef","ifndef","elif"] 1584 1585 def isInclude(self): 1586 """checks wether this is a #include directive. if true, then returns the 1587 corresponding file name (with brackets or double-qoutes). None otherwise""" 1588 if self.directive != "include": 1589 return None 1590 1591 #print "iii " + repr(self.tokens) 1592 if self.tokens[0].id == tokSTRING: 1593 # a double-quote include, that's easy 1594 return self.tokens[0].value 1595 1596 # we only want the bracket part, not any comments or junk after it 1597 if self.tokens[0].id == "<": 1598 i = 0 1599 tok = self.tokens 1600 n = len(tok) 1601 while i < n and tok[i].id != ">": 1602 i += 1 1603 1604 if i >= n: 1605 return None 1606 1607 return string.join([ str(x) for x in tok[:i+1] ],"") 1608 1609 else: 1610 return None 1611 1612 def __repr__(self): 1613 """generate the representation of a given block""" 1614 if self.directive: 1615 result = "#%s " % self.directive 1616 if self.isIf(): 1617 result += repr(self.expr) 1618 else: 1619 for tok in self.tokens: 1620 result += repr(tok) 1621 else: 1622 result = "" 1623 for tok in self.tokens: 1624 result += repr(tok) 1625 1626 return result 1627 1628 def __str__(self): 1629 """generate the string representation of a given block""" 1630 if self.directive: 1631 if self.directive == "if": 1632 # small optimization to re-generate #ifdef and #ifndef 1633 e = self.expr.expr 1634 op = e[0] 1635 if op == "defined": 1636 result = "#ifdef %s" % e[1] 1637 elif op == "!" and e[1][0] == "defined": 1638 result = "#ifndef %s" % e[1][1] 1639 else: 1640 result = "#if " + str(self.expr) 1641 else: 1642 result = "#%s" % self.directive 1643 if len(self.tokens): 1644 result += " " 1645 for tok in self.tokens: 1646 result += str(tok) 1647 else: 1648 result = "" 1649 for tok in self.tokens: 1650 result += str(tok) 1651 1652 return result 1653 1654 1655 class BlockList: 1656 """a convenience class used to hold and process a list of blocks returned by 1657 the cpp parser""" 1658 def __init__(self,blocks): 1659 self.blocks = blocks 1660 1661 def __len__(self): 1662 return len(self.blocks) 1663 1664 def __getitem__(self,n): 1665 return self.blocks[n] 1666 1667 def __repr__(self): 1668 return repr(self.blocks) 1669 1670 def __str__(self): 1671 result = "" 1672 for b in self.blocks: 1673 result += str(b) 1674 if b.isDirective(): 1675 result += '\n' 1676 return result 1677 1678 def optimizeIf01(self): 1679 """remove the code between #if 0 .. #endif in a BlockList""" 1680 self.blocks = optimize_if01(self.blocks) 1681 1682 def optimizeMacros(self, macros): 1683 """remove known defined and undefined macros from a BlockList""" 1684 for b in self.blocks: 1685 if b.isIf(): 1686 b.expr.optimize(macros) 1687 1688 def removeMacroDefines(self,macros): 1689 """remove known macro definitions from a BlockList""" 1690 self.blocks = remove_macro_defines(self.blocks,macros) 1691 1692 def removePrefixed(self,prefix,names): 1693 for b in self.blocks: 1694 if b.isIf(): 1695 b.expr.removePrefixed(prefix,names) 1696 1697 def optimizeAll(self,macros): 1698 self.optimizeMacros(macros) 1699 self.optimizeIf01() 1700 return 1701 1702 def findIncludes(self): 1703 """return the list of included files in a BlockList""" 1704 result = [] 1705 for b in self.blocks: 1706 i = b.isInclude() 1707 if i: 1708 result.append(i) 1709 1710 return result 1711 1712 1713 def write(self,out): 1714 out.write(str(self)) 1715 1716 def removeComments(self): 1717 for b in self.blocks: 1718 for tok in b.tokens: 1719 if tok.id == tokSPACE: 1720 tok.value = " " 1721 1722 def removeEmptyLines(self): 1723 # state = 1 => previous line was tokLN 1724 # state = 0 => previous line was directive 1725 state = 1 1726 for b in self.blocks: 1727 if b.isDirective(): 1728 #print "$$$ directive %s" % str(b) 1729 state = 0 1730 else: 1731 # a tokLN followed by spaces is replaced by a single tokLN 1732 # several successive tokLN are replaced by a single one 1733 # 1734 dst = [] 1735 src = b.tokens 1736 n = len(src) 1737 i = 0 1738 #print "$$$ parsing %s" % repr(src) 1739 while i < n: 1740 # find final tokLN 1741 j = i 1742 while j < n and src[j].id != tokLN: 1743 j += 1 1744 1745 if j >= n: 1746 # uhhh 1747 dst += src[i:] 1748 break 1749 1750 if src[i].id == tokSPACE: 1751 k = i+1 1752 while src[k].id == tokSPACE: 1753 k += 1 1754 1755 if k == j: # empty lines with spaces in it 1756 i = j # remove the spaces 1757 1758 if i == j: 1759 # an empty line 1760 if state == 1: 1761 i += 1 # remove it 1762 else: 1763 state = 1 1764 dst.append(src[i]) 1765 i += 1 1766 else: 1767 # this line is not empty, remove trailing spaces 1768 k = j 1769 while k > i and src[k-1].id == tokSPACE: 1770 k -= 1 1771 1772 nn = i 1773 while nn < k: 1774 dst.append(src[nn]) 1775 nn += 1 1776 dst.append(src[j]) 1777 state = 0 1778 i = j+1 1779 1780 b.tokens = dst 1781 1782 def removeVarsAndFuncs(self,knownStatics=set()): 1783 """remove all extern and static declarations corresponding 1784 to variable and function declarations. we only accept typedefs 1785 and enum/structs/union declarations. 1786 1787 however, we keep the definitions corresponding to the set 1788 of known static inline functions in the set 'knownStatics', 1789 which is useful for optimized byteorder swap functions and 1790 stuff like that. 1791 """ 1792 # state = 1 => typedef/struct encountered 1793 # state = 2 => vars or func declaration encountered, skipping until ";" 1794 # state = 0 => normal (i.e. LN + spaces) 1795 state = 0 1796 depth = 0 1797 blocks2 = [] 1798 for b in self.blocks: 1799 if b.isDirective(): 1800 blocks2.append(b) 1801 else: 1802 n = len(b.tokens) 1803 i = 0 1804 first = 0 1805 if state == 2: 1806 first = n 1807 while i < n: 1808 tok = b.tokens[i] 1809 if state == 0: 1810 bad = 0 1811 if tok.id in [tokLN, tokSPACE]: 1812 pass 1813 elif tok.value in [ 'struct', 'typedef', 'enum', 'union', '__extension__' ]: 1814 state = 1 1815 else: 1816 if tok.value in [ 'static', 'extern', '__KINLINE' ]: 1817 j = i+1 1818 ident = "" 1819 while j < n and not (b.tokens[j].id in [ '(', ';' ]): 1820 if b.tokens[j].id == tokIDENT: 1821 ident = b.tokens[j].value 1822 j += 1 1823 if j < n and ident in knownStatics: 1824 # this is a known static, we're going to keep its 1825 # definition in the final output 1826 state = 1 1827 else: 1828 #print "### skip static '%s'" % ident 1829 pass 1830 1831 if state == 0: 1832 if i > first: 1833 #print "### intermediate from '%s': '%s'" % (tok.value, repr(b.tokens[first:i])) 1834 blocks2.append( Block(b.tokens[first:i]) ) 1835 state = 2 1836 first = n 1837 1838 else: # state > 0 1839 if tok.id == '{': 1840 depth += 1 1841 1842 elif tok.id == '}': 1843 if depth > 0: 1844 depth -= 1 1845 1846 elif depth == 0 and tok.id == ';': 1847 if state == 2: 1848 first = i+1 1849 state = 0 1850 1851 i += 1 1852 1853 if i > first: 1854 #print "### final '%s'" % repr(b.tokens[first:i]) 1855 blocks2.append( Block(b.tokens[first:i]) ) 1856 1857 self.blocks = blocks2 1858 1859 def insertDisclaimer(self,disclaimer="/* auto-generated file, DO NOT EDIT */"): 1860 """insert your standard issue disclaimer that this is an 1861 auto-generated file, etc..""" 1862 tokens = CppLineTokenizer( disclaimer ).toTokenList() 1863 tokens = tokens[:-1] # remove trailing tokLN 1864 self.blocks = [ Block(tokens) ] + self.blocks 1865 1866 class BlockParser: 1867 """a class used to convert an input source file into a BlockList object""" 1868 1869 def __init__(self,tokzer=None): 1870 """initialize a block parser. the input source is provided through a Tokenizer 1871 object""" 1872 self.reset(tokzer) 1873 1874 def reset(self,tokzer): 1875 self.state = 1 1876 self.tokzer = tokzer 1877 1878 def getBlocks(self,tokzer=None): 1879 """tokenize and parse the input source, return a BlockList object 1880 NOTE: empty and line-numbering directives are ignored and removed 1881 from the result. as a consequence, it is possible to have 1882 two successive text blocks in the result""" 1883 # state 0 => in source code 1884 # state 1 => in source code, after a LN 1885 # state 2 => in source code, after LN then some space 1886 state = 1 1887 lastLN = 0 1888 current = [] 1889 blocks = [] 1890 1891 if tokzer == None: 1892 tokzer = self.tokzer 1893 1894 while 1: 1895 tok = tokzer.getToken() 1896 if tok.id == tokEOF: 1897 break 1898 1899 if tok.id == tokLN: 1900 state = 1 1901 current.append(tok) 1902 lastLN = len(current) 1903 1904 elif tok.id == tokSPACE: 1905 if state == 1: 1906 state = 2 1907 current.append(tok) 1908 1909 elif tok.id == "#": 1910 if state > 0: 1911 # this is the start of a directive 1912 1913 if lastLN > 0: 1914 # record previous tokens as text block 1915 block = Block(current[:lastLN]) 1916 blocks.append(block) 1917 lastLN = 0 1918 1919 current = [] 1920 1921 # skip spaces after the # 1922 while 1: 1923 tok = tokzer.getToken() 1924 if tok.id != tokSPACE: 1925 break 1926 1927 if tok.id != tokIDENT: 1928 # empty or line-numbering, ignore it 1929 if tok.id != tokLN and tok.id != tokEOF: 1930 while 1: 1931 tok = tokzer.getToken() 1932 if tok.id == tokLN or tok.id == tokEOF: 1933 break 1934 continue 1935 1936 directive = tok.value 1937 lineno = tok.lineno 1938 1939 # skip spaces 1940 tok = tokzer.getToken() 1941 while tok.id == tokSPACE: 1942 tok = tokzer.getToken() 1943 1944 # then record tokens until LN 1945 dirtokens = [] 1946 while tok.id != tokLN and tok.id != tokEOF: 1947 dirtokens.append(tok) 1948 tok = tokzer.getToken() 1949 1950 block = Block(dirtokens,directive,lineno) 1951 blocks.append(block) 1952 state = 1 1953 1954 else: 1955 state = 0 1956 current.append(tok) 1957 1958 if len(current) > 0: 1959 block = Block(current) 1960 blocks.append(block) 1961 1962 return BlockList(blocks) 1963 1964 def parse(self,tokzer): 1965 return self.getBlocks( tokzer ) 1966 1967 def parseLines(self,lines): 1968 """parse a list of text lines into a BlockList object""" 1969 return self.getBlocks( CppLinesTokenizer(lines) ) 1970 1971 def parseFile(self,path): 1972 """parse a file into a BlockList object""" 1973 file = open(path, "rt") 1974 result = self.getBlocks( CppFileTokenizer(file) ) 1975 file.close() 1976 return result 1977 1978 1979 def test_block_parsing(lines,expected): 1980 blocks = BlockParser().parse( CppLinesTokenizer(lines) ) 1981 if len(blocks) != len(expected): 1982 raise BadExpectedToken, "parser.buildBlocks returned '%s' expecting '%s'" \ 1983 % (str(blocks), repr(expected)) 1984 for n in range(len(blocks)): 1985 if str(blocks[n]) != expected[n]: 1986 raise BadExpectedToken, "parser.buildBlocks()[%d] is '%s', expecting '%s'" \ 1987 % (n, str(blocks[n]), expected[n]) 1988 #for block in blocks: 1989 # print block 1990 1991 def test_BlockParser(): 1992 test_block_parsing(["#error hello"],["#error hello"]) 1993 test_block_parsing([ "foo", "", "bar" ], [ "foo\n\nbar\n" ]) 1994 test_block_parsing([ "foo", " # ", "bar" ], [ "foo\n","bar\n" ]) 1995 test_block_parsing(\ 1996 [ "foo", " # ", " # /* ahah */ if defined(__KERNEL__) ", "bar", "#endif" ], 1997 [ "foo\n", "#ifdef __KERNEL__", "bar\n", "#endif" ] ) 1998 1999 2000 ##################################################################################### 2001 ##################################################################################### 2002 ##### ##### 2003 ##### B L O C K L I S T O P T I M I Z A T I O N ##### 2004 ##### ##### 2005 ##################################################################################### 2006 ##################################################################################### 2007 2008 def remove_macro_defines( blocks, excludedMacros=set() ): 2009 """remove macro definitions like #define <macroName> ....""" 2010 result = [] 2011 for b in blocks: 2012 macroName = b.isDefine() 2013 if macroName == None or not macroName in excludedMacros: 2014 result.append(b) 2015 2016 return result 2017 2018 def find_matching_endif( blocks, i ): 2019 n = len(blocks) 2020 depth = 1 2021 while i < n: 2022 if blocks[i].isDirective(): 2023 dir = blocks[i].directive 2024 if dir in [ "if", "ifndef", "ifdef" ]: 2025 depth += 1 2026 elif depth == 1 and dir in [ "else", "elif" ]: 2027 return i 2028 elif dir == "endif": 2029 depth -= 1 2030 if depth == 0: 2031 return i 2032 i += 1 2033 return i 2034 2035 def optimize_if01( blocks ): 2036 """remove the code between #if 0 .. #endif in a list of CppBlocks""" 2037 i = 0 2038 n = len(blocks) 2039 result = [] 2040 while i < n: 2041 j = i 2042 while j < n and not blocks[j].isIf(): 2043 j += 1 2044 if j > i: 2045 D2("appending lines %d to %d" % (blocks[i].lineno, blocks[j-1].lineno)) 2046 result += blocks[i:j] 2047 if j >= n: 2048 break 2049 expr = blocks[j].expr 2050 r = expr.toInt() 2051 if r == None: 2052 result.append(blocks[j]) 2053 i = j + 1 2054 continue 2055 2056 if r == 0: 2057 # if 0 => skip everything until the corresponding #endif 2058 j = find_matching_endif( blocks, j+1 ) 2059 if j >= n: 2060 # unterminated #if 0, finish here 2061 break 2062 dir = blocks[j].directive 2063 if dir == "endif": 2064 D2("remove 'if 0' .. 'endif' (lines %d to %d)" % (blocks[i].lineno, blocks[j].lineno)) 2065 i = j + 1 2066 elif dir == "else": 2067 # convert 'else' into 'if 1' 2068 D2("convert 'if 0' .. 'else' into 'if 1' (lines %d to %d)" % (blocks[i].lineno, blocks[j-1].lineno)) 2069 blocks[j].directive = "if" 2070 blocks[j].expr = CppExpr( CppLineTokenizer("1").toTokenList() ) 2071 i = j 2072 elif dir == "elif": 2073 # convert 'elif' into 'if' 2074 D2("convert 'if 0' .. 'elif' into 'if'") 2075 blocks[j].directive = "if" 2076 i = j 2077 continue 2078 2079 # if 1 => find corresponding endif and remove/transform them 2080 k = find_matching_endif( blocks, j+1 ) 2081 if k >= n: 2082 # unterminated #if 1, finish here 2083 D2("unterminated 'if 1'") 2084 result += blocks[j+1:k] 2085 break 2086 2087 dir = blocks[k].directive 2088 if dir == "endif": 2089 D2("convert 'if 1' .. 'endif' (lines %d to %d)" % (blocks[j].lineno, blocks[k].lineno)) 2090 result += optimize_if01(blocks[j+1:k]) 2091 i = k+1 2092 elif dir == "else": 2093 # convert 'else' into 'if 0' 2094 D2("convert 'if 1' .. 'else' (lines %d to %d)" % (blocks[j].lineno, blocks[k].lineno)) 2095 result += optimize_if01(blocks[j+1:k]) 2096 blocks[k].directive = "if" 2097 blocks[k].expr = CppExpr( CppLineTokenizer("0").toTokenList() ) 2098 i = k 2099 elif dir == "elif": 2100 # convert 'elif' into 'if 0' 2101 D2("convert 'if 1' .. 'elif' (lines %d to %d)" % (blocks[j].lineno, blocks[k].lineno)) 2102 result += optimize_if01(blocks[j+1:k]) 2103 blocks[k].expr = CppExpr( CppLineTokenizer("0").toTokenList() ) 2104 i = k 2105 return result 2106 2107 def test_optimizeAll(): 2108 text = """\ 2109 #if 1 2110 #define GOOD_1 2111 #endif 2112 #if 0 2113 #define BAD_2 2114 #define BAD_3 2115 #endif 2116 2117 #if 1 2118 #define GOOD_2 2119 #else 2120 #define BAD_4 2121 #endif 2122 2123 #if 0 2124 #define BAD_5 2125 #else 2126 #define GOOD_3 2127 #endif 2128 2129 #if 0 2130 #if 1 2131 #define BAD_6 2132 #endif 2133 #endif\ 2134 """ 2135 2136 expected = """\ 2137 #define GOOD_1 2138 2139 #define GOOD_2 2140 2141 #define GOOD_3 2142 2143 """ 2144 2145 print "running test_BlockList.optimizeAll" 2146 out = StringOutput() 2147 lines = string.split(text, '\n') 2148 list = BlockParser().parse( CppLinesTokenizer(lines) ) 2149 #D_setlevel(2) 2150 list.optimizeAll( {"__KERNEL__":kCppUndefinedMacro} ) 2151 #print repr(list) 2152 list.write(out) 2153 if out.get() != expected: 2154 print "KO: macro optimization failed\n" 2155 print "<<<< expecting '", 2156 print expected, 2157 print "'\n>>>> result '" 2158 print out.get(), 2159 print "'\n----" 2160 2161 2162 ##################################################################################### 2163 ##################################################################################### 2164 ##### ##### 2165 ##### ##### 2166 ##### ##### 2167 ##################################################################################### 2168 ##################################################################################### 2169 2170 def runUnitTests(): 2171 """run all unit tests for this program""" 2172 print "running unit tests" 2173 test_CppTokenizer() 2174 test_CppExpr() 2175 test_optimizeAll() 2176 test_BlockParser() 2177 print "OK" 2178 2179 if __name__ == "__main__": 2180 runUnitTests() 2181
