| # a glorified C pre-processor parser | |
| import sys, re, string | |
| from utils import * | |
| from defaults import * | |
| debugTokens = False | |
| debugDirectiveTokenizer = False | |
| debugLineParsing = False | |
| debugCppExpr = False | |
| debugOptimIf01 = False | |
| ##################################################################################### | |
| ##################################################################################### | |
| ##### ##### | |
| ##### C P P T O K E N S ##### | |
| ##### ##### | |
| ##################################################################################### | |
| ##################################################################################### | |
| # the list of supported C-preprocessor tokens | |
| # plus a couple of C tokens as well | |
| tokEOF = "\0" | |
| tokLN = "\n" | |
| tokSTRINGIFY = "#" | |
| tokCONCAT = "##" | |
| tokLOGICAND = "&&" | |
| tokLOGICOR = "||" | |
| tokSHL = "<<" | |
| tokSHR = ">>" | |
| tokEQUAL = "==" | |
| tokNEQUAL = "!=" | |
| tokLT = "<" | |
| tokLTE = "<=" | |
| tokGT = ">" | |
| tokGTE = ">=" | |
| tokELLIPSIS = "..." | |
| tokSPACE = " " | |
| tokDEFINED = "defined" | |
| tokLPAREN = "(" | |
| tokRPAREN = ")" | |
| tokNOT = "!" | |
| tokPLUS = "+" | |
| tokMINUS = "-" | |
| tokMULTIPLY = "*" | |
| tokDIVIDE = "/" | |
| tokMODULUS = "%" | |
| tokBINAND = "&" | |
| tokBINOR = "|" | |
| tokBINXOR = "^" | |
| tokCOMMA = "," | |
| tokLBRACE = "{" | |
| tokRBRACE = "}" | |
| tokARROW = "->" | |
| tokINCREMENT = "++" | |
| tokDECREMENT = "--" | |
| tokNUMBER = "<number>" | |
| tokIDENT = "<ident>" | |
| tokSTRING = "<string>" | |
| class Token: | |
| """a simple class to hold information about a given token. | |
| each token has a position in the source code, as well as | |
| an 'id' and a 'value'. the id is a string that identifies | |
| the token's class, while the value is the string of the | |
| original token itself. | |
| for example, the tokenizer concatenates a series of spaces | |
| and tabs as a single tokSPACE id, whose value if the original | |
| spaces+tabs sequence.""" | |
| def __init__(self): | |
| self.id = None | |
| self.value = None | |
| self.lineno = 0 | |
| self.colno = 0 | |
| def set(self,id,val=None): | |
| self.id = id | |
| if val: | |
| self.value = val | |
| else: | |
| self.value = id | |
| return None | |
| def copyFrom(self,src): | |
| self.id = src.id | |
| self.value = src.value | |
| self.lineno = src.lineno | |
| self.colno = src.colno | |
| def __repr__(self): | |
| if self.id == tokIDENT: | |
| return "(ident %s)" % self.value | |
| if self.id == tokNUMBER: | |
| return "(number %s)" % self.value | |
| if self.id == tokSTRING: | |
| return "(string '%s')" % self.value | |
| if self.id == tokLN: | |
| return "<LN>" | |
| if self.id == tokEOF: | |
| return "<EOF>" | |
| if self.id == tokSPACE and self.value == "\\": | |
| # this corresponds to a trailing \ that was transformed into a tokSPACE | |
| return "<\\>" | |
| return self.id | |
| def __str__(self): | |
| if self.id == tokIDENT: | |
| return self.value | |
| if self.id == tokNUMBER: | |
| return self.value | |
| if self.id == tokSTRING: | |
| return self.value | |
| if self.id == tokEOF: | |
| return "<EOF>" | |
| if self.id == tokSPACE: | |
| if self.value == "\\": # trailing \ | |
| return "\\\n" | |
| else: | |
| return self.value | |
| return self.id | |
| class BadExpectedToken(Exception): | |
| def __init__(self,msg): | |
| print msg | |
| ##################################################################################### | |
| ##################################################################################### | |
| ##### ##### | |
| ##### C P P T O K E N I Z E R ##### | |
| ##### ##### | |
| ##################################################################################### | |
| ##################################################################################### | |
| # list of long symbols, i.e. those that take more than one characters | |
| cppLongSymbols = [ tokCONCAT, tokLOGICAND, tokLOGICOR, tokSHL, tokSHR, tokELLIPSIS, tokEQUAL,\ | |
| tokNEQUAL, tokLTE, tokGTE, tokARROW, tokINCREMENT, tokDECREMENT ] | |
| class CppTokenizer: | |
| """an abstract class used to convert some input text into a list | |
| of tokens. real implementations follow and differ in the format | |
| of the input text only""" | |
| def __init__(self): | |
| """initialize a new CppTokenizer object""" | |
| self.eof = False # end of file reached ? | |
| self.text = None # content of current line, with final \n stripped | |
| self.line = 0 # number of current line | |
| self.pos = 0 # current character position in current line | |
| self.len = 0 # length of current line text | |
| self.held = Token() | |
| def setLineText(self,line): | |
| """set the content of the (next) current line. should be called | |
| by fillLineText() in derived classes""" | |
| self.text = line | |
| self.len = len(line) | |
| self.pos = 0 | |
| def fillLineText(self): | |
| """refresh the content of 'line' with a new line of input""" | |
| # to be overriden | |
| self.eof = True | |
| def markPos(self,tok): | |
| """mark the position of the current token in the source file""" | |
| if self.eof or self.pos > self.len: | |
| tok.lineno = self.line + 1 | |
| tok.colno = 0 | |
| else: | |
| tok.lineno = self.line | |
| tok.colno = self.pos | |
| def peekChar(self): | |
| """return the current token under the cursor without moving it""" | |
| if self.eof: | |
| return tokEOF | |
| if self.pos > self.len: | |
| self.pos = 0 | |
| self.line += 1 | |
| self.fillLineText() | |
| if self.eof: | |
| return tokEOF | |
| if self.pos == self.len: | |
| return tokLN | |
| else: | |
| return self.text[self.pos] | |
| def peekNChar(self,n): | |
| """try to peek the next n chars on the same line""" | |
| if self.pos + n > self.len: | |
| return None | |
| return self.text[self.pos:self.pos+n] | |
| def skipChar(self): | |
| """increment the token cursor position""" | |
| if not self.eof: | |
| self.pos += 1 | |
| def skipNChars(self,n): | |
| if self.pos + n <= self.len: | |
| self.pos += n | |
| else: | |
| while n > 0: | |
| self.skipChar() | |
| n -= 1 | |
| def nextChar(self): | |
| """retrieve the token at the current cursor position, then skip it""" | |
| result = self.peekChar() | |
| self.skipChar() | |
| return result | |
| def getEscape(self): | |
| # try to get all characters after a backslash (\) | |
| result = self.nextChar() | |
| if result == "0": | |
| # octal number ? | |
| num = self.peekNChar(3) | |
| if num != None: | |
| isOctal = True | |
| for d in num: | |
| if not d in "01234567": | |
| isOctal = False | |
| break | |
| if isOctal: | |
| result += num | |
| self.skipNChars(3) | |
| elif result == "x" or result == "X": | |
| # hex number ? | |
| num = self.peekNChar(2) | |
| if num != None: | |
| isHex = True | |
| for d in num: | |
| if not d in "012345678abcdefABCDEF": | |
| isHex = False | |
| break | |
| if isHex: | |
| result += num | |
| self.skipNChars(2) | |
| elif result == "u" or result == "U": | |
| # unicode char ? | |
| num = self.peekNChar(4) | |
| if num != None: | |
| isHex = True | |
| for d in num: | |
| if not d in "012345678abcdefABCDEF": | |
| isHex = False | |
| break | |
| if isHex: | |
| result += num | |
| self.skipNChars(4) | |
| return result | |
| def nextRealToken(self,tok): | |
| """return next CPP token, used internally by nextToken()""" | |
| c = self.nextChar() | |
| if c == tokEOF or c == tokLN: | |
| return tok.set(c) | |
| if c == '/': | |
| c = self.peekChar() | |
| if c == '/': # C++ comment line | |
| self.skipChar() | |
| while 1: | |
| c = self.nextChar() | |
| if c == tokEOF or c == tokLN: | |
| break | |
| return tok.set(tokLN) | |
| if c == '*': # C comment start | |
| self.skipChar() | |
| value = "/*" | |
| prev_c = None | |
| while 1: | |
| c = self.nextChar() | |
| if c == tokEOF: | |
| return tok.set(tokEOF,value) | |
| if c == '/' and prev_c == '*': | |
| break | |
| prev_c = c | |
| value += c | |
| value += "/" | |
| return tok.set(tokSPACE,value) | |
| c = '/' | |
| if c.isspace(): | |
| while 1: | |
| c2 = self.peekChar() | |
| if c2 == tokLN or not c2.isspace(): | |
| break | |
| c += c2 | |
| self.skipChar() | |
| return tok.set(tokSPACE,c) | |
| if c == '\\': | |
| if debugTokens: | |
| print "nextRealToken: \\ found, next token is '%s'" % repr(self.peekChar()) | |
| if self.peekChar() == tokLN: # trailing \ | |
| # eat the tokLN | |
| self.skipChar() | |
| # we replace a trailing \ by a tokSPACE whose value is | |
| # simply "\\". this allows us to detect them later when | |
| # needed. | |
| return tok.set(tokSPACE,"\\") | |
| else: | |
| # treat as a single token here ? | |
| c +=self.getEscape() | |
| return tok.set(c) | |
| if c == "'": # chars | |
| c2 = self.nextChar() | |
| c += c2 | |
| if c2 == '\\': | |
| c += self.getEscape() | |
| while 1: | |
| c2 = self.nextChar() | |
| if c2 == tokEOF: | |
| break | |
| c += c2 | |
| if c2 == "'": | |
| break | |
| return tok.set(tokSTRING, c) | |
| if c == '"': # strings | |
| quote = 0 | |
| while 1: | |
| c2 = self.nextChar() | |
| if c2 == tokEOF: | |
| return tok.set(tokSTRING,c) | |
| c += c2 | |
| if not quote: | |
| if c2 == '"': | |
| return tok.set(tokSTRING,c) | |
| if c2 == "\\": | |
| quote = 1 | |
| else: | |
| quote = 0 | |
| if c >= "0" and c <= "9": # integers ? | |
| while 1: | |
| c2 = self.peekChar() | |
| if c2 == tokLN or (not c2.isalnum() and c2 != "_"): | |
| break | |
| c += c2 | |
| self.skipChar() | |
| return tok.set(tokNUMBER,c) | |
| if c.isalnum() or c == "_": # identifiers ? | |
| while 1: | |
| c2 = self.peekChar() | |
| if c2 == tokLN or (not c2.isalnum() and c2 != "_"): | |
| break | |
| c += c2 | |
| self.skipChar() | |
| if c == tokDEFINED: | |
| return tok.set(tokDEFINED) | |
| else: | |
| return tok.set(tokIDENT,c) | |
| # check special symbols | |
| for sk in cppLongSymbols: | |
| if c == sk[0]: | |
| sklen = len(sk[1:]) | |
| if self.pos + sklen <= self.len and \ | |
| self.text[self.pos:self.pos+sklen] == sk[1:]: | |
| self.pos += sklen | |
| return tok.set(sk) | |
| return tok.set(c) | |
| def nextToken(self,tok): | |
| """return the next token from the input text. this function | |
| really updates 'tok', and does not return a new one""" | |
| self.markPos(tok) | |
| self.nextRealToken(tok) | |
| def getToken(self): | |
| tok = Token() | |
| self.nextToken(tok) | |
| if debugTokens: | |
| print "getTokens: %s" % repr(tok) | |
| return tok | |
| def toTokenList(self): | |
| """convert the input text of a CppTokenizer into a direct | |
| list of token objects. tokEOF is stripped from the result""" | |
| result = [] | |
| while 1: | |
| tok = Token() | |
| self.nextToken(tok) | |
| if tok.id == tokEOF: | |
| break | |
| result.append(tok) | |
| return result | |
| class CppLineTokenizer(CppTokenizer): | |
| """a CppTokenizer derived class that accepts a single line of text as input""" | |
| def __init__(self,line,lineno=1): | |
| CppTokenizer.__init__(self) | |
| self.line = lineno | |
| self.setLineText(line) | |
| class CppLinesTokenizer(CppTokenizer): | |
| """a CppTokenizer derived class that accepts a list of texdt lines as input. | |
| the lines must not have a trailing \n""" | |
| def __init__(self,lines=[],lineno=1): | |
| """initialize a CppLinesTokenizer. you can later add lines using addLines()""" | |
| CppTokenizer.__init__(self) | |
| self.line = lineno | |
| self.lines = lines | |
| self.index = 0 | |
| self.count = len(lines) | |
| if self.count > 0: | |
| self.fillLineText() | |
| else: | |
| self.eof = True | |
| def addLine(self,line): | |
| """add a line to a CppLinesTokenizer. this can be done after tokenization | |
| happens""" | |
| if self.count == 0: | |
| self.setLineText(line) | |
| self.index = 1 | |
| self.lines.append(line) | |
| self.count += 1 | |
| self.eof = False | |
| def fillLineText(self): | |
| if self.index < self.count: | |
| self.setLineText(self.lines[self.index]) | |
| self.index += 1 | |
| else: | |
| self.eof = True | |
| class CppFileTokenizer(CppTokenizer): | |
| def __init__(self,file,lineno=1): | |
| CppTokenizer.__init__(self) | |
| self.file = file | |
| self.line = lineno | |
| def fillLineText(self): | |
| line = self.file.readline() | |
| if len(line) > 0: | |
| if line[-1] == '\n': | |
| line = line[:-1] | |
| if len(line) > 0 and line[-1] == "\r": | |
| line = line[:-1] | |
| self.setLineText(line) | |
| else: | |
| self.eof = True | |
| # Unit testing | |
| # | |
| class CppTokenizerTester: | |
| """a class used to test CppTokenizer classes""" | |
| def __init__(self,tokenizer=None): | |
| self.tokenizer = tokenizer | |
| self.token = Token() | |
| def setTokenizer(self,tokenizer): | |
| self.tokenizer = tokenizer | |
| def expect(self,id): | |
| self.tokenizer.nextToken(self.token) | |
| tokid = self.token.id | |
| if tokid == id: | |
| return | |
| if self.token.value == id and (tokid == tokIDENT or tokid == tokNUMBER): | |
| return | |
| raise BadExpectedToken, "### BAD TOKEN: '%s' expecting '%s'" % (self.token.id,id) | |
| def expectToken(self,id,line,col): | |
| self.expect(id) | |
| if self.token.lineno != line: | |
| raise BadExpectedToken, "### BAD LINENO: token '%s' got '%d' expecting '%d'" % (id,self.token.lineno,line) | |
| if self.token.colno != col: | |
| raise BadExpectedToken, "### BAD COLNO: '%d' expecting '%d'" % (self.token.colno,col) | |
| def expectTokenVal(self,id,value,line,col): | |
| self.expectToken(id,line,col) | |
| if self.token.value != value: | |
| raise BadExpectedToken, "### BAD VALUE: '%s' expecting '%s'" % (self.token.value,value) | |
| def expectList(self,list): | |
| for item in list: | |
| self.expect(item) | |
| def test_CppTokenizer(): | |
| tester = CppTokenizerTester() | |
| tester.setTokenizer( CppLineTokenizer("#an/example && (01923_xy)") ) | |
| tester.expectList( ["#", "an", "/", "example", tokSPACE, tokLOGICAND, tokSPACE, tokLPAREN, "01923_xy", \ | |
| tokRPAREN, tokLN, tokEOF] ) | |
| tester.setTokenizer( CppLineTokenizer("FOO(BAR) && defined(BAZ)") ) | |
| tester.expectList( ["FOO", tokLPAREN, "BAR", tokRPAREN, tokSPACE, tokLOGICAND, tokSPACE, | |
| tokDEFINED, tokLPAREN, "BAZ", tokRPAREN, tokLN, tokEOF] ) | |
| tester.setTokenizer( CppLinesTokenizer( ["/*", "#", "*/"] ) ) | |
| tester.expectList( [ tokSPACE, tokLN, tokEOF ] ) | |
| tester.setTokenizer( CppLinesTokenizer( ["first", "second"] ) ) | |
| tester.expectList( [ "first", tokLN, "second", tokLN, tokEOF ] ) | |
| tester.setTokenizer( CppLinesTokenizer( ["first second", " third"] ) ) | |
| tester.expectToken( "first", 1, 0 ) | |
| tester.expectToken( tokSPACE, 1, 5 ) | |
| tester.expectToken( "second", 1, 6 ) | |
| tester.expectToken( tokLN, 1, 12 ) | |
| tester.expectToken( tokSPACE, 2, 0 ) | |
| tester.expectToken( "third", 2, 2 ) | |
| tester.setTokenizer( CppLinesTokenizer( [ "boo /* what the", "hell */" ] ) ) | |
| tester.expectList( [ "boo", tokSPACE ] ) | |
| tester.expectTokenVal( tokSPACE, "/* what the\nhell */", 1, 4 ) | |
| tester.expectList( [ tokLN, tokEOF ] ) | |
| tester.setTokenizer( CppLinesTokenizer( [ "an \\", " example" ] ) ) | |
| tester.expectToken( "an", 1, 0 ) | |
| tester.expectToken( tokSPACE, 1, 2 ) | |
| tester.expectTokenVal( tokSPACE, "\\", 1, 3 ) | |
| tester.expectToken( tokSPACE, 2, 0 ) | |
| tester.expectToken( "example", 2, 1 ) | |
| tester.expectToken( tokLN, 2, 8 ) | |
| return True | |
| ##################################################################################### | |
| ##################################################################################### | |
| ##### ##### | |
| ##### C P P E X P R E S S I O N S ##### | |
| ##### ##### | |
| ##################################################################################### | |
| ##################################################################################### | |
| class CppExpr: | |
| """a class that models the condition of #if directives into | |
| an expression tree. each node in the tree is of the form (op,arg) or (op,arg1,arg2) | |
| where "op" is a string describing the operation""" | |
| unaries = [ "!", "~" ] | |
| binaries = [ "+", "-", "<", "<=", ">=", ">", "&&", "||", "*", "/", "%", "&", "|", "^", "<<", ">>", "==", "!=", "?", ":" ] | |
| precedences = { | |
| "?": 1, ":": 1, | |
| "||": 2, | |
| "&&": 3, | |
| "|": 4, | |
| "^": 5, | |
| "&": 6, | |
| "==": 7, "!=": 7, | |
| "<": 8, "<=": 8, ">": 8, ">=": 8, | |
| "<<": 9, ">>": 9, | |
| "+": 10, "-": 10, | |
| "*": 11, "/": 11, "%": 11, | |
| "!": 12, "~": 12 | |
| } | |
| re_cpp_constant = re.compile(r"((\d|\w|_)+)") | |
| def __init__(self, tokens): | |
| """initialize a CppExpr. 'tokens' must be a CppToken list""" | |
| self.tok = tokens | |
| self.n = len(tokens) | |
| self.i = 0 | |
| if debugCppExpr: | |
| print "CppExpr: trying to parse %s" % repr(tokens) | |
| self.expr = self.parseExpression(0) | |
| if debugCppExpr: | |
| print "CppExpr: got " + repr(self.expr) | |
| if self.i != self.n: | |
| print 'crap at end of input (%d != %d): %s' % (self.i, self.n, repr(tokens)) | |
| raise | |
| def throw(self, exception, msg): | |
| if self.i < self.n: | |
| tok = self.tok[self.i] | |
| print "%d:%d: %s" % (tok.lineno,tok.colno,msg) | |
| else: | |
| print "EOF: %s" % msg | |
| raise exception(msg) | |
| def skip_spaces(self): | |
| """skip spaces in input token list""" | |
| while self.i < self.n: | |
| t = self.tok[self.i] | |
| if t.id != tokSPACE and t.id != tokLN: | |
| break | |
| self.i += 1 | |
| def expectId(self, id): | |
| """check that a given token id is at the current position, then skip over it""" | |
| self.skip_spaces() | |
| if self.i >= self.n or self.tok[self.i].id != id: | |
| self.throw(BadExpectedToken,self.i,"### expecting '%s' in expression, got '%s'" % (id, self.tok[self.i].id)) | |
| self.i += 1 | |
| def expectIdent(self): | |
| self.skip_spaces() | |
| if self.i >= self.n or self.tok[self.i].id != tokIDENT: | |
| self.throw(BadExpectedToken, self.i,"### expecting identifier in expression, got '%s'" % (id, self.tok[self.i].id)) | |
| self.i += 1 | |
| def is_decimal(self): | |
| v = self.tok[self.i].value[:] | |
| while len(v) > 0 and v[-1] in "ULul": | |
| v = v[:-1] | |
| for digit in v: | |
| if not digit.isdigit(): | |
| return None | |
| self.i += 1 | |
| return ("int", string.atoi(v)) | |
| def is_hexadecimal(self): | |
| v = self.tok[self.i].value[:] | |
| while len(v) > 0 and v[-1] in "ULul": | |
| v = v[:-1] | |
| if len(v) > 2 and (v[0:2] == "0x" or v[0:2] == "0X"): | |
| for digit in v[2:]: | |
| if not digit in "0123456789abcdefABCDEF": | |
| return None | |
| # for a hex expression tuple, the argument | |
| # is the value as an integer | |
| self.i += 1 | |
| return ("hex", int(v[2:], 16)) | |
| return None | |
| def is_integer(self): | |
| if self.tok[self.i].id != tokNUMBER: | |
| return None | |
| c = self.is_decimal() | |
| if c: return c | |
| c = self.is_hexadecimal() | |
| if c: return c | |
| return None | |
| def is_number(self): | |
| t = self.tok[self.i] | |
| if t.id == tokMINUS and self.i+1 < self.n: | |
| self.i += 1 | |
| c = self.is_integer() | |
| if c: | |
| op, val = c | |
| return (op, -val) | |
| if t.id == tokPLUS and self.i+1 < self.n: | |
| c = self.is_integer() | |
| if c: return c | |
| return self.is_integer() | |
| def is_defined(self): | |
| t = self.tok[self.i] | |
| if t.id != tokDEFINED: | |
| return None | |
| # we have the defined keyword, check the rest | |
| self.i += 1 | |
| self.skip_spaces() | |
| used_parens = 0 | |
| if self.i < self.n and self.tok[self.i].id == tokLPAREN: | |
| used_parens = 1 | |
| self.i += 1 | |
| self.skip_spaces() | |
| if self.i >= self.n: | |
| self.throw(CppConstantExpected,i,"### 'defined' must be followed by macro name or left paren") | |
| t = self.tok[self.i] | |
| if t.id != tokIDENT: | |
| self.throw(CppConstantExpected,i,"### 'defined' must be followed by macro name") | |
| self.i += 1 | |
| if used_parens: | |
| self.expectId(tokRPAREN) | |
| return ("defined", t.value) | |
| def is_call_or_ident(self): | |
| self.skip_spaces() | |
| if self.i >= self.n: | |
| return None | |
| t = self.tok[self.i] | |
| if t.id != tokIDENT: | |
| return None | |
| name = t.value | |
| self.i += 1 | |
| self.skip_spaces() | |
| if self.i >= self.n or self.tok[self.i].id != tokLPAREN: | |
| return ("ident", name) | |
| params = [] | |
| depth = 1 | |
| self.i += 1 | |
| j = self.i | |
| while self.i < self.n: | |
| id = self.tok[self.i].id | |
| if id == tokLPAREN: | |
| depth += 1 | |
| elif depth == 1 and (id == tokCOMMA or id == tokRPAREN): | |
| while j < self.i and self.tok[j].id == tokSPACE: | |
| j += 1 | |
| k = self.i | |
| while k > j and self.tok[k-1].id == tokSPACE: | |
| k -= 1 | |
| param = self.tok[j:k] | |
| params.append(param) | |
| if id == tokRPAREN: | |
| break | |
| j = self.i+1 | |
| elif id == tokRPAREN: | |
| depth -= 1 | |
| self.i += 1 | |
| if self.i >= self.n: | |
| return None | |
| self.i += 1 | |
| return ("call", (name, params)) | |
| # Implements the "precedence climbing" algorithm from http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm. | |
| # The "classic" algorithm would be fine if we were using a tool to generate the parser, but we're not. | |
| # Dijkstra's "shunting yard" algorithm hasn't been necessary yet. | |
| def parseExpression(self, minPrecedence): | |
| self.skip_spaces() | |
| if self.i >= self.n: | |
| return None | |
| node = self.parsePrimary() | |
| while self.token() != None and self.isBinary(self.token()) and self.precedence(self.token()) >= minPrecedence: | |
| op = self.token() | |
| self.nextToken() | |
| rhs = self.parseExpression(self.precedence(op) + 1) | |
| node = (op.id, node, rhs) | |
| return node | |
| def parsePrimary(self): | |
| op = self.token() | |
| if self.isUnary(op): | |
| self.nextToken() | |
| return (op.id, self.parseExpression(self.precedence(op))) | |
| primary = None | |
| if op.id == tokLPAREN: | |
| self.nextToken() | |
| primary = self.parseExpression(0) | |
| self.expectId(tokRPAREN) | |
| elif op.id == "?": | |
| self.nextToken() | |
| primary = self.parseExpression(0) | |
| self.expectId(":") | |
| elif op.id == tokNUMBER: | |
| primary = self.is_number() | |
| elif op.id == tokIDENT: | |
| primary = self.is_call_or_ident() | |
| elif op.id == tokDEFINED: | |
| primary = self.is_defined() | |
| else: | |
| self.throw(BadExpectedToken, "didn't expect to see a %s in factor" % (self.tok[self.i].id)) | |
| self.skip_spaces() | |
| return primary; | |
| def isBinary(self, token): | |
| return token.id in self.binaries | |
| def isUnary(self, token): | |
| return token.id in self.unaries | |
| def precedence(self, token): | |
| return self.precedences.get(token.id) | |
| def token(self): | |
| if self.i >= self.n: | |
| return None | |
| return self.tok[self.i] | |
| def nextToken(self): | |
| self.i += 1 | |
| self.skip_spaces() | |
| if self.i >= self.n: | |
| return None | |
| return self.tok[self.i] | |
| def dump_node(self, e): | |
| op = e[0] | |
| line = "(" + op | |
| if op == "int": | |
| line += " %d)" % e[1] | |
| elif op == "hex": | |
| line += " 0x%x)" % e[1] | |
| elif op == "ident": | |
| line += " %s)" % e[1] | |
| elif op == "defined": | |
| line += " %s)" % e[1] | |
| elif op == "call": | |
| arg = e[1] | |
| line += " %s [" % arg[0] | |
| prefix = "" | |
| for param in arg[1]: | |
| par = "" | |
| for tok in param: | |
| par += str(tok) | |
| line += "%s%s" % (prefix, par) | |
| prefix = "," | |
| line += "])" | |
| elif op in CppExpr.unaries: | |
| line += " %s)" % self.dump_node(e[1]) | |
| elif op in CppExpr.binaries: | |
| line += " %s %s)" % (self.dump_node(e[1]), self.dump_node(e[2])) | |
| else: | |
| line += " ?%s)" % repr(e[1]) | |
| return line | |
| def __repr__(self): | |
| return self.dump_node(self.expr) | |
| def source_node(self, e): | |
| op = e[0] | |
| if op == "int": | |
| return "%d" % e[1] | |
| if op == "hex": | |
| return "0x%x" % e[1] | |
| if op == "ident": | |
| # XXX: should try to expand | |
| return e[1] | |
| if op == "defined": | |
| return "defined(%s)" % e[1] | |
| prec = CppExpr.precedences.get(op,1000) | |
| arg = e[1] | |
| if op in CppExpr.unaries: | |
| arg_src = self.source_node(arg) | |
| arg_op = arg[0] | |
| arg_prec = CppExpr.precedences.get(arg[0],1000) | |
| if arg_prec < prec: | |
| return "!(" + arg_src + ")" | |
| else: | |
| return "!" + arg_src | |
| if op in CppExpr.binaries: | |
| arg2 = e[2] | |
| arg1_op = arg[0] | |
| arg2_op = arg2[0] | |
| arg1_src = self.source_node(arg) | |
| arg2_src = self.source_node(arg2) | |
| if CppExpr.precedences.get(arg1_op,1000) < prec: | |
| arg1_src = "(%s)" % arg1_src | |
| if CppExpr.precedences.get(arg2_op,1000) < prec: | |
| arg2_src = "(%s)" % arg2_src | |
| return "%s %s %s" % (arg1_src, op, arg2_src) | |
| return "???" | |
| def __str__(self): | |
| return self.source_node(self.expr) | |
| def int_node(self,e): | |
| if e[0] == "int": | |
| return e[1] | |
| elif e[1] == "hex": | |
| return int(e[1],16) | |
| else: | |
| return None | |
| def toInt(self): | |
| return self.int_node(self.expr) | |
| def optimize_node(self, e, macros={}): | |
| op = e[0] | |
| if op == "defined": | |
| op, name = e | |
| if macros.has_key(name): | |
| if macros[name] == kCppUndefinedMacro: | |
| return ("int", 0) | |
| else: | |
| try: | |
| value = int(macros[name]) | |
| return ("int", value) | |
| except: | |
| return ("defined", macros[name]) | |
| if kernel_remove_config_macros and name.startswith("CONFIG_"): | |
| return ("int", 0) | |
| return e | |
| elif op == "ident": | |
| op, name = e | |
| if macros.has_key(name): | |
| try: | |
| value = int(macros[name]) | |
| expanded = ("int", value) | |
| except: | |
| expanded = ("ident", macros[name]) | |
| return self.optimize_node(expanded, macros) | |
| return e | |
| elif op == "!": | |
| op, v = e | |
| v = self.optimize_node(v, macros) | |
| if v[0] == "int": | |
| if v[1] == 0: | |
| return ("int", 1) | |
| else: | |
| return ("int", 0) | |
| return ('!', v) | |
| elif op == "&&": | |
| op, l, r = e | |
| l = self.optimize_node(l, macros) | |
| r = self.optimize_node(r, macros) | |
| li = self.int_node(l) | |
| ri = self.int_node(r) | |
| if li != None: | |
| if li == 0: | |
| return ("int", 0) | |
| else: | |
| return r | |
| elif ri != None: | |
| if ri == 0: | |
| return ("int", 0) | |
| else: | |
| return l | |
| return (op, l, r) | |
| elif op == "||": | |
| op, l, r = e | |
| l = self.optimize_node(l, macros) | |
| r = self.optimize_node(r, macros) | |
| li = self.int_node(l) | |
| ri = self.int_node(r) | |
| if li != None: | |
| if li == 0: | |
| return r | |
| else: | |
| return ("int", 1) | |
| elif ri != None: | |
| if ri == 0: | |
| return l | |
| else: | |
| return ("int", 1) | |
| return (op, l, r) | |
| else: | |
| return e | |
| def optimize(self,macros={}): | |
| self.expr = self.optimize_node(self.expr, macros) | |
| def is_equal_node(self,e1,e2): | |
| if e1[0] != e2[0] or len(e1) != len(e2): | |
| return False | |
| op = e1[0] | |
| if op == "int" or op == "hex" or op == "!" or op == "defined": | |
| return e1[0] == e2[0] | |
| return self.is_equal_node(e1[1],e2[1]) and self.is_equal_node(e1[2],e2[2]) | |
| def is_equal(self,other): | |
| return self.is_equal_node(self.expr,other.expr) | |
| def test_cpp_expr(expr, expected): | |
| e = CppExpr( CppLineTokenizer( expr ).toTokenList() ) | |
| s1 = repr(e) | |
| if s1 != expected: | |
| print "[FAIL]: expression '%s' generates '%s', should be '%s'" % (expr, s1, expected) | |
| global failure_count | |
| failure_count += 1 | |
| def test_cpp_expr_optim(expr, expected, macros={}): | |
| e = CppExpr( CppLineTokenizer( expr ).toTokenList() ) | |
| e.optimize(macros) | |
| s1 = repr(e) | |
| if s1 != expected: | |
| print "[FAIL]: optimized expression '%s' generates '%s' with macros %s, should be '%s'" % (expr, s1, macros, expected) | |
| global failure_count | |
| failure_count += 1 | |
| def test_cpp_expr_source(expr, expected): | |
| e = CppExpr( CppLineTokenizer( expr ).toTokenList() ) | |
| s1 = str(e) | |
| if s1 != expected: | |
| print "[FAIL]: source expression '%s' generates '%s', should be '%s'" % (expr, s1, expected) | |
| global failure_count | |
| failure_count += 1 | |
| def test_CppExpr(): | |
| test_cpp_expr("0", "(int 0)") | |
| test_cpp_expr("1", "(int 1)") | |
| test_cpp_expr("(0)", "(int 0)") | |
| test_cpp_expr("1 && 1", "(&& (int 1) (int 1))") | |
| test_cpp_expr("1 && 0", "(&& (int 1) (int 0))") | |
| test_cpp_expr("EXAMPLE", "(ident EXAMPLE)") | |
| test_cpp_expr("EXAMPLE - 3", "(- (ident EXAMPLE) (int 3))") | |
| test_cpp_expr("defined(EXAMPLE)", "(defined EXAMPLE)") | |
| test_cpp_expr("defined ( EXAMPLE ) ", "(defined EXAMPLE)") | |
| test_cpp_expr("!defined(EXAMPLE)", "(! (defined EXAMPLE))") | |
| test_cpp_expr("defined(ABC) || defined(BINGO)", "(|| (defined ABC) (defined BINGO))") | |
| test_cpp_expr("FOO(BAR)", "(call FOO [BAR])") | |
| test_cpp_expr("A == 1 || defined(B)", "(|| (== (ident A) (int 1)) (defined B))") | |
| test_cpp_expr_optim("0", "(int 0)") | |
| test_cpp_expr_optim("1", "(int 1)") | |
| test_cpp_expr_optim("1 && 1", "(int 1)") | |
| test_cpp_expr_optim("1 && 0", "(int 0)") | |
| test_cpp_expr_optim("0 && 1", "(int 0)") | |
| test_cpp_expr_optim("0 && 0", "(int 0)") | |
| test_cpp_expr_optim("1 || 1", "(int 1)") | |
| test_cpp_expr_optim("1 || 0", "(int 1)") | |
| test_cpp_expr_optim("0 || 1", "(int 1)") | |
| test_cpp_expr_optim("0 || 0", "(int 0)") | |
| test_cpp_expr_optim("A", "(ident A)") | |
| test_cpp_expr_optim("A", "(int 1)", { "A": 1 }) | |
| test_cpp_expr_optim("A || B", "(int 1)", { "A": 1 }) | |
| test_cpp_expr_optim("A || B", "(int 1)", { "B": 1 }) | |
| test_cpp_expr_optim("A && B", "(ident B)", { "A": 1 }) | |
| test_cpp_expr_optim("A && B", "(ident A)", { "B": 1 }) | |
| test_cpp_expr_optim("A && B", "(&& (ident A) (ident B))") | |
| test_cpp_expr_optim("EXAMPLE", "(ident EXAMPLE)") | |
| test_cpp_expr_optim("EXAMPLE - 3", "(- (ident EXAMPLE) (int 3))") | |
| test_cpp_expr_optim("defined(EXAMPLE)", "(defined EXAMPLE)") | |
| test_cpp_expr_optim("defined(EXAMPLE)", "(defined XOWOE)", { "EXAMPLE": "XOWOE" }) | |
| test_cpp_expr_optim("defined(EXAMPLE)", "(int 0)", { "EXAMPLE": kCppUndefinedMacro}) | |
| test_cpp_expr_optim("!defined(EXAMPLE)", "(! (defined EXAMPLE))") | |
| test_cpp_expr_optim("!defined(EXAMPLE)", "(! (defined XOWOE))", { "EXAMPLE" : "XOWOE" }) | |
| test_cpp_expr_optim("!defined(EXAMPLE)", "(int 1)", { "EXAMPLE" : kCppUndefinedMacro }) | |
| test_cpp_expr_optim("defined(A) || defined(B)", "(|| (defined A) (defined B))") | |
| test_cpp_expr_optim("defined(A) || defined(B)", "(int 1)", { "A" : "1" }) | |
| test_cpp_expr_optim("defined(A) || defined(B)", "(int 1)", { "B" : "1" }) | |
| test_cpp_expr_optim("defined(A) || defined(B)", "(defined A)", { "B" : kCppUndefinedMacro }) | |
| test_cpp_expr_optim("defined(A) || defined(B)", "(int 0)", { "A" : kCppUndefinedMacro, "B" : kCppUndefinedMacro }) | |
| test_cpp_expr_optim("defined(A) && defined(B)", "(&& (defined A) (defined B))") | |
| test_cpp_expr_optim("defined(A) && defined(B)", "(defined B)", { "A" : "1" }) | |
| test_cpp_expr_optim("defined(A) && defined(B)", "(defined A)", { "B" : "1" }) | |
| test_cpp_expr_optim("defined(A) && defined(B)", "(int 0)", { "B" : kCppUndefinedMacro }) | |
| test_cpp_expr_optim("defined(A) && defined(B)", "(int 0)", { "A" : kCppUndefinedMacro }) | |
| test_cpp_expr_optim("A == 1 || defined(B)", "(|| (== (ident A) (int 1)) (defined B))" ) | |
| test_cpp_expr_optim("defined(__KERNEL__) || !defined(__GLIBC__) || (__GLIBC__ < 2)", "(|| (! (defined __GLIBC__)) (< (ident __GLIBC__) (int 2)))", { "__KERNEL__": kCppUndefinedMacro }) | |
| test_cpp_expr_source("0", "0") | |
| test_cpp_expr_source("1", "1") | |
| test_cpp_expr_source("1 && 1", "1 && 1") | |
| test_cpp_expr_source("1 && 0", "1 && 0") | |
| test_cpp_expr_source("0 && 1", "0 && 1") | |
| test_cpp_expr_source("0 && 0", "0 && 0") | |
| test_cpp_expr_source("1 || 1", "1 || 1") | |
| test_cpp_expr_source("1 || 0", "1 || 0") | |
| test_cpp_expr_source("0 || 1", "0 || 1") | |
| test_cpp_expr_source("0 || 0", "0 || 0") | |
| test_cpp_expr_source("EXAMPLE", "EXAMPLE") | |
| test_cpp_expr_source("EXAMPLE - 3", "EXAMPLE - 3") | |
| test_cpp_expr_source("defined(EXAMPLE)", "defined(EXAMPLE)") | |
| test_cpp_expr_source("defined EXAMPLE", "defined(EXAMPLE)") | |
| test_cpp_expr_source("A == 1 || defined(B)", "A == 1 || defined(B)") | |
| ##################################################################################### | |
| ##################################################################################### | |
| ##### ##### | |
| ##### C P P B L O C K ##### | |
| ##### ##### | |
| ##################################################################################### | |
| ##################################################################################### | |
| class Block: | |
| """a class used to model a block of input source text. there are two block types: | |
| - directive blocks: contain the tokens of a single pre-processor directive (e.g. #if) | |
| - text blocks, contain the tokens of non-directive blocks | |
| the cpp parser class below will transform an input source file into a list of Block | |
| objects (grouped in a BlockList object for convenience)""" | |
| def __init__(self,tokens,directive=None,lineno=0): | |
| """initialize a new block, if 'directive' is None, this is a text block | |
| NOTE: this automatically converts '#ifdef MACRO' into '#if defined(MACRO)' | |
| and '#ifndef MACRO' into '#if !defined(MACRO)'""" | |
| if directive == "ifdef": | |
| tok = Token() | |
| tok.set(tokDEFINED) | |
| tokens = [ tok ] + tokens | |
| directive = "if" | |
| elif directive == "ifndef": | |
| tok1 = Token() | |
| tok2 = Token() | |
| tok1.set(tokNOT) | |
| tok2.set(tokDEFINED) | |
| tokens = [ tok1, tok2 ] + tokens | |
| directive = "if" | |
| self.tokens = tokens | |
| self.directive = directive | |
| if lineno > 0: | |
| self.lineno = lineno | |
| else: | |
| self.lineno = self.tokens[0].lineno | |
| if self.isIf(): | |
| self.expr = CppExpr( self.tokens ) | |
| def isDirective(self): | |
| """returns True iff this is a directive block""" | |
| return self.directive != None | |
| def isConditional(self): | |
| """returns True iff this is a conditional directive block""" | |
| return self.directive in ["if","ifdef","ifndef","else","elif","endif"] | |
| def isDefine(self): | |
| """returns the macro name in a #define directive, or None otherwise""" | |
| if self.directive != "define": | |
| return None | |
| return self.tokens[0].value | |
| def isIf(self): | |
| """returns True iff this is an #if-like directive block""" | |
| return self.directive in ["if","ifdef","ifndef","elif"] | |
| def isInclude(self): | |
| """checks whether this is a #include directive. if true, then returns the | |
| corresponding file name (with brackets or double-qoutes). None otherwise""" | |
| if self.directive != "include": | |
| return None | |
| if self.tokens[0].id == tokSTRING: | |
| # a double-quote include, that's easy | |
| return self.tokens[0].value | |
| # we only want the bracket part, not any comments or junk after it | |
| if self.tokens[0].id == "<": | |
| i = 0 | |
| tok = self.tokens | |
| n = len(tok) | |
| while i < n and tok[i].id != ">": | |
| i += 1 | |
| if i >= n: | |
| return None | |
| return string.join([ str(x) for x in tok[:i+1] ],"") | |
| else: | |
| return None | |
| def removeWhiteSpace(self): | |
| # Remove trailing whitespace and empty lines | |
| # All whitespace is also contracted to a single space | |
| if self.directive != None: | |
| return | |
| tokens = [] | |
| line = 0 # index of line start | |
| space = -1 # index of first space, or -1 | |
| ii = 0 | |
| nn = len(self.tokens) | |
| while ii < nn: | |
| tok = self.tokens[ii] | |
| # If we find a space, record its position if this is the first | |
| # one the line start or the previous character. Don't append | |
| # anything to tokens array yet though. | |
| if tok.id == tokSPACE: | |
| if space < 0: | |
| space = ii | |
| ii += 1 | |
| continue | |
| # If this is a line space, ignore the spaces we found previously | |
| # on the line, and remove empty lines. | |
| if tok.id == tokLN: | |
| old_line = line | |
| old_space = space | |
| ii += 1 | |
| line = ii | |
| space = -1 | |
| if old_space == old_line: # line only contains spaces | |
| continue | |
| if ii-1 == old_line: # line is empty | |
| continue | |
| tokens.append(tok) | |
| continue | |
| # Other token, append any space range if any, converting each | |
| # one to a single space character, then append the token. | |
| if space >= 0: | |
| jj = space | |
| space = -1 | |
| while jj < ii: | |
| tok2 = self.tokens[jj] | |
| tok2.value = " " | |
| tokens.append(tok2) | |
| jj += 1 | |
| tokens.append(tok) | |
| ii += 1 | |
| self.tokens = tokens | |
| def writeWithWarning(self,out,warning,left_count,repeat_count): | |
| # removeWhiteSpace() will sometimes creates non-directive blocks | |
| # without any tokens. These come from blocks that only contained | |
| # empty lines and spaces. They should not be printed in the final | |
| # output, and then should not be counted for this operation. | |
| # | |
| if not self.directive and self.tokens == []: | |
| return left_count | |
| if self.directive: | |
| out.write(str(self).rstrip() + "\n") | |
| left_count -= 1 | |
| if left_count == 0: | |
| out.write(warning) | |
| left_count = repeat_count | |
| else: | |
| for tok in self.tokens: | |
| out.write(str(tok)) | |
| if tok.id == tokLN: | |
| left_count -= 1 | |
| if left_count == 0: | |
| out.write(warning) | |
| left_count = repeat_count | |
| return left_count | |
| def __repr__(self): | |
| """generate the representation of a given block""" | |
| if self.directive: | |
| result = "#%s " % self.directive | |
| if self.isIf(): | |
| result += repr(self.expr) | |
| else: | |
| for tok in self.tokens: | |
| result += repr(tok) | |
| else: | |
| result = "" | |
| for tok in self.tokens: | |
| result += repr(tok) | |
| return result | |
| def __str__(self): | |
| """generate the string representation of a given block""" | |
| if self.directive: | |
| if self.directive == "if": | |
| # small optimization to re-generate #ifdef and #ifndef | |
| e = self.expr.expr | |
| op = e[0] | |
| if op == "defined": | |
| result = "#ifdef %s" % e[1] | |
| elif op == "!" and e[1][0] == "defined": | |
| result = "#ifndef %s" % e[1][1] | |
| else: | |
| result = "#if " + str(self.expr) | |
| else: | |
| result = "#%s" % self.directive | |
| if len(self.tokens): | |
| result += " " | |
| for tok in self.tokens: | |
| result += str(tok) | |
| else: | |
| result = "" | |
| for tok in self.tokens: | |
| result += str(tok) | |
| return result | |
| class BlockList: | |
| """a convenience class used to hold and process a list of blocks returned by | |
| the cpp parser""" | |
| def __init__(self,blocks): | |
| self.blocks = blocks | |
| def __len__(self): | |
| return len(self.blocks) | |
| def __getitem__(self,n): | |
| return self.blocks[n] | |
| def __repr__(self): | |
| return repr(self.blocks) | |
| def __str__(self): | |
| result = "" | |
| for b in self.blocks: | |
| result += str(b) | |
| if b.isDirective(): | |
| result = result.rstrip() + '\n' | |
| return result | |
| def optimizeIf01(self): | |
| """remove the code between #if 0 .. #endif in a BlockList""" | |
| self.blocks = optimize_if01(self.blocks) | |
| def optimizeMacros(self, macros): | |
| """remove known defined and undefined macros from a BlockList""" | |
| for b in self.blocks: | |
| if b.isIf(): | |
| b.expr.optimize(macros) | |
| def removeMacroDefines(self,macros): | |
| """remove known macro definitions from a BlockList""" | |
| self.blocks = remove_macro_defines(self.blocks,macros) | |
| def removeWhiteSpace(self): | |
| for b in self.blocks: | |
| b.removeWhiteSpace() | |
| def optimizeAll(self,macros): | |
| self.optimizeMacros(macros) | |
| self.optimizeIf01() | |
| return | |
| def findIncludes(self): | |
| """return the list of included files in a BlockList""" | |
| result = [] | |
| for b in self.blocks: | |
| i = b.isInclude() | |
| if i: | |
| result.append(i) | |
| return result | |
| def write(self,out): | |
| out.write(str(self)) | |
| def writeWithWarning(self,out,warning,repeat_count): | |
| left_count = repeat_count | |
| for b in self.blocks: | |
| left_count = b.writeWithWarning(out,warning,left_count,repeat_count) | |
| def removeComments(self): | |
| for b in self.blocks: | |
| for tok in b.tokens: | |
| if tok.id == tokSPACE: | |
| tok.value = " " | |
| def removeVarsAndFuncs(self,knownStatics=set()): | |
| """remove all extern and static declarations corresponding | |
| to variable and function declarations. we only accept typedefs | |
| and enum/structs/union declarations. | |
| however, we keep the definitions corresponding to the set | |
| of known static inline functions in the set 'knownStatics', | |
| which is useful for optimized byteorder swap functions and | |
| stuff like that. | |
| """ | |
| # state = 0 => normal (i.e. LN + spaces) | |
| # state = 1 => typedef/struct encountered, ends with ";" | |
| # state = 2 => var declaration encountered, ends with ";" | |
| # state = 3 => func declaration encountered, ends with "}" | |
| state = 0 | |
| depth = 0 | |
| blocks2 = [] | |
| skipTokens = False | |
| for b in self.blocks: | |
| if b.isDirective(): | |
| blocks2.append(b) | |
| else: | |
| n = len(b.tokens) | |
| i = 0 | |
| if skipTokens: | |
| first = n | |
| else: | |
| first = 0 | |
| while i < n: | |
| tok = b.tokens[i] | |
| tokid = tok.id | |
| # If we are not looking for the start of a new | |
| # type/var/func, then skip over tokens until | |
| # we find our terminator, managing the depth of | |
| # accolades as we go. | |
| if state > 0: | |
| terminator = False | |
| if tokid == '{': | |
| depth += 1 | |
| elif tokid == '}': | |
| if depth > 0: | |
| depth -= 1 | |
| if (depth == 0) and (state == 3): | |
| terminator = True | |
| elif tokid == ';' and depth == 0: | |
| terminator = True | |
| if terminator: | |
| # we found the terminator | |
| state = 0 | |
| if skipTokens: | |
| skipTokens = False | |
| first = i+1 | |
| i = i+1 | |
| continue | |
| # We are looking for the start of a new type/func/var | |
| # ignore whitespace | |
| if tokid in [tokLN, tokSPACE]: | |
| i = i+1 | |
| continue | |
| # Is it a new type definition, then start recording it | |
| if tok.value in [ 'struct', 'typedef', 'enum', 'union', '__extension__' ]: | |
| state = 1 | |
| i = i+1 | |
| continue | |
| # Is it a variable or function definition. If so, first | |
| # try to determine which type it is, and also extract | |
| # its name. | |
| # | |
| # We're going to parse the next tokens of the same block | |
| # until we find a semi-column or a left parenthesis. | |
| # | |
| # The semi-column corresponds to a variable definition, | |
| # the left-parenthesis to a function definition. | |
| # | |
| # We also assume that the var/func name is the last | |
| # identifier before the terminator. | |
| # | |
| j = i+1 | |
| ident = "" | |
| while j < n: | |
| tokid = b.tokens[j].id | |
| if tokid == '(': # a function declaration | |
| state = 3 | |
| break | |
| elif tokid == ';': # a variable declaration | |
| state = 2 | |
| break | |
| if tokid == tokIDENT: | |
| ident = b.tokens[j].value | |
| j += 1 | |
| if j >= n: | |
| # This can only happen when the declaration | |
| # does not end on the current block (e.g. with | |
| # a directive mixed inside it. | |
| # | |
| # We will treat it as malformed because | |
| # it's very hard to recover from this case | |
| # without making our parser much more | |
| # complex. | |
| # | |
| #print "### skip unterminated static '%s'" % ident | |
| break | |
| if ident in knownStatics: | |
| #print "### keep var/func '%s': %s" % (ident,repr(b.tokens[i:j])) | |
| pass | |
| else: | |
| # We're going to skip the tokens for this declaration | |
| #print "### skip variable /func'%s': %s" % (ident,repr(b.tokens[i:j])) | |
| if i > first: | |
| blocks2.append( Block(b.tokens[first:i])) | |
| skipTokens = True | |
| first = n | |
| i = i+1 | |
| if i > first: | |
| #print "### final '%s'" % repr(b.tokens[first:i]) | |
| blocks2.append( Block(b.tokens[first:i]) ) | |
| self.blocks = blocks2 | |
| def insertDisclaimer(self,disclaimer="/* auto-generated file, DO NOT EDIT */"): | |
| """insert your standard issue disclaimer that this is an | |
| auto-generated file, etc..""" | |
| tokens = CppLineTokenizer( disclaimer ).toTokenList() | |
| tokens = tokens[:-1] # remove trailing tokLN | |
| self.blocks = [ Block(tokens) ] + self.blocks | |
| def replaceTokens(self,replacements): | |
| """replace tokens according to the given dict""" | |
| for b in self.blocks: | |
| made_change = False | |
| if b.isInclude() == None: | |
| for tok in b.tokens: | |
| if tok.id == tokIDENT: | |
| if tok.value in replacements: | |
| tok.value = replacements[tok.value] | |
| made_change = True | |
| if made_change and b.isIf(): | |
| # Keep 'expr' in sync with 'tokens'. | |
| b.expr = CppExpr(b.tokens) | |
| class BlockParser: | |
| """a class used to convert an input source file into a BlockList object""" | |
| def __init__(self,tokzer=None): | |
| """initialize a block parser. the input source is provided through a Tokenizer | |
| object""" | |
| self.reset(tokzer) | |
| def reset(self,tokzer): | |
| self.state = 1 | |
| self.tokzer = tokzer | |
| def getBlocks(self,tokzer=None): | |
| """tokenize and parse the input source, return a BlockList object | |
| NOTE: empty and line-numbering directives are ignored and removed | |
| from the result. as a consequence, it is possible to have | |
| two successive text blocks in the result""" | |
| # state 0 => in source code | |
| # state 1 => in source code, after a LN | |
| # state 2 => in source code, after LN then some space | |
| state = 1 | |
| lastLN = 0 | |
| current = [] | |
| blocks = [] | |
| if tokzer == None: | |
| tokzer = self.tokzer | |
| while 1: | |
| tok = tokzer.getToken() | |
| if tok.id == tokEOF: | |
| break | |
| if tok.id == tokLN: | |
| state = 1 | |
| current.append(tok) | |
| lastLN = len(current) | |
| elif tok.id == tokSPACE: | |
| if state == 1: | |
| state = 2 | |
| current.append(tok) | |
| elif tok.id == "#": | |
| if state > 0: | |
| # this is the start of a directive | |
| if lastLN > 0: | |
| # record previous tokens as text block | |
| block = Block(current[:lastLN]) | |
| blocks.append(block) | |
| lastLN = 0 | |
| current = [] | |
| # skip spaces after the # | |
| while 1: | |
| tok = tokzer.getToken() | |
| if tok.id != tokSPACE: | |
| break | |
| if tok.id != tokIDENT: | |
| # empty or line-numbering, ignore it | |
| if tok.id != tokLN and tok.id != tokEOF: | |
| while 1: | |
| tok = tokzer.getToken() | |
| if tok.id == tokLN or tok.id == tokEOF: | |
| break | |
| continue | |
| directive = tok.value | |
| lineno = tok.lineno | |
| # skip spaces | |
| tok = tokzer.getToken() | |
| while tok.id == tokSPACE: | |
| tok = tokzer.getToken() | |
| # then record tokens until LN | |
| dirtokens = [] | |
| while tok.id != tokLN and tok.id != tokEOF: | |
| dirtokens.append(tok) | |
| tok = tokzer.getToken() | |
| block = Block(dirtokens,directive,lineno) | |
| blocks.append(block) | |
| state = 1 | |
| else: | |
| state = 0 | |
| current.append(tok) | |
| if len(current) > 0: | |
| block = Block(current) | |
| blocks.append(block) | |
| return BlockList(blocks) | |
| def parse(self,tokzer): | |
| return self.getBlocks( tokzer ) | |
| def parseLines(self,lines): | |
| """parse a list of text lines into a BlockList object""" | |
| return self.getBlocks( CppLinesTokenizer(lines) ) | |
| def parseFile(self,path): | |
| """parse a file into a BlockList object""" | |
| file = open(path, "rt") | |
| result = self.getBlocks( CppFileTokenizer(file) ) | |
| file.close() | |
| return result | |
| def test_block_parsing(lines,expected): | |
| blocks = BlockParser().parse( CppLinesTokenizer(lines) ) | |
| if len(blocks) != len(expected): | |
| raise BadExpectedToken, "parser.buildBlocks returned '%s' expecting '%s'" \ | |
| % (str(blocks), repr(expected)) | |
| for n in range(len(blocks)): | |
| if str(blocks[n]) != expected[n]: | |
| raise BadExpectedToken, "parser.buildBlocks()[%d] is '%s', expecting '%s'" \ | |
| % (n, str(blocks[n]), expected[n]) | |
| #for block in blocks: | |
| # print block | |
| def test_BlockParser(): | |
| test_block_parsing(["#error hello"],["#error hello"]) | |
| test_block_parsing([ "foo", "", "bar" ], [ "foo\n\nbar\n" ]) | |
| test_block_parsing([ "foo", " # ", "bar" ], [ "foo\n","bar\n" ]) | |
| test_block_parsing(\ | |
| [ "foo", " # ", " # /* ahah */ if defined(__KERNEL__) ", "bar", "#endif" ], | |
| [ "foo\n", "#ifdef __KERNEL__", "bar\n", "#endif" ] ) | |
| ##################################################################################### | |
| ##################################################################################### | |
| ##### ##### | |
| ##### B L O C K L I S T O P T I M I Z A T I O N ##### | |
| ##### ##### | |
| ##################################################################################### | |
| ##################################################################################### | |
| def remove_macro_defines( blocks, excludedMacros=set() ): | |
| """remove macro definitions like #define <macroName> ....""" | |
| result = [] | |
| for b in blocks: | |
| macroName = b.isDefine() | |
| if macroName == None or not macroName in excludedMacros: | |
| result.append(b) | |
| return result | |
| def find_matching_endif( blocks, i ): | |
| n = len(blocks) | |
| depth = 1 | |
| while i < n: | |
| if blocks[i].isDirective(): | |
| dir = blocks[i].directive | |
| if dir in [ "if", "ifndef", "ifdef" ]: | |
| depth += 1 | |
| elif depth == 1 and dir in [ "else", "elif" ]: | |
| return i | |
| elif dir == "endif": | |
| depth -= 1 | |
| if depth == 0: | |
| return i | |
| i += 1 | |
| return i | |
| def optimize_if01( blocks ): | |
| """remove the code between #if 0 .. #endif in a list of CppBlocks""" | |
| i = 0 | |
| n = len(blocks) | |
| result = [] | |
| while i < n: | |
| j = i | |
| while j < n and not blocks[j].isIf(): | |
| j += 1 | |
| if j > i: | |
| D2("appending lines %d to %d" % (blocks[i].lineno, blocks[j-1].lineno)) | |
| result += blocks[i:j] | |
| if j >= n: | |
| break | |
| expr = blocks[j].expr | |
| r = expr.toInt() | |
| if r == None: | |
| result.append(blocks[j]) | |
| i = j + 1 | |
| continue | |
| if r == 0: | |
| # if 0 => skip everything until the corresponding #endif | |
| j = find_matching_endif( blocks, j+1 ) | |
| if j >= n: | |
| # unterminated #if 0, finish here | |
| break | |
| dir = blocks[j].directive | |
| if dir == "endif": | |
| D2("remove 'if 0' .. 'endif' (lines %d to %d)" % (blocks[i].lineno, blocks[j].lineno)) | |
| i = j + 1 | |
| elif dir == "else": | |
| # convert 'else' into 'if 1' | |
| D2("convert 'if 0' .. 'else' into 'if 1' (lines %d to %d)" % (blocks[i].lineno, blocks[j-1].lineno)) | |
| blocks[j].directive = "if" | |
| blocks[j].expr = CppExpr( CppLineTokenizer("1").toTokenList() ) | |
| i = j | |
| elif dir == "elif": | |
| # convert 'elif' into 'if' | |
| D2("convert 'if 0' .. 'elif' into 'if'") | |
| blocks[j].directive = "if" | |
| i = j | |
| continue | |
| # if 1 => find corresponding endif and remove/transform them | |
| k = find_matching_endif( blocks, j+1 ) | |
| if k >= n: | |
| # unterminated #if 1, finish here | |
| D2("unterminated 'if 1'") | |
| result += blocks[j+1:k] | |
| break | |
| dir = blocks[k].directive | |
| if dir == "endif": | |
| D2("convert 'if 1' .. 'endif' (lines %d to %d)" % (blocks[j].lineno, blocks[k].lineno)) | |
| result += optimize_if01(blocks[j+1:k]) | |
| i = k+1 | |
| elif dir == "else": | |
| # convert 'else' into 'if 0' | |
| D2("convert 'if 1' .. 'else' (lines %d to %d)" % (blocks[j].lineno, blocks[k].lineno)) | |
| result += optimize_if01(blocks[j+1:k]) | |
| blocks[k].directive = "if" | |
| blocks[k].expr = CppExpr( CppLineTokenizer("0").toTokenList() ) | |
| i = k | |
| elif dir == "elif": | |
| # convert 'elif' into 'if 0' | |
| D2("convert 'if 1' .. 'elif' (lines %d to %d)" % (blocks[j].lineno, blocks[k].lineno)) | |
| result += optimize_if01(blocks[j+1:k]) | |
| blocks[k].expr = CppExpr( CppLineTokenizer("0").toTokenList() ) | |
| i = k | |
| return result | |
| def test_optimizeAll(): | |
| text = """\ | |
| #if 1 | |
| #define GOOD_1 | |
| #endif | |
| #if 0 | |
| #define BAD_2 | |
| #define BAD_3 | |
| #endif | |
| #if 1 | |
| #define GOOD_2 | |
| #else | |
| #define BAD_4 | |
| #endif | |
| #if 0 | |
| #define BAD_5 | |
| #else | |
| #define GOOD_3 | |
| #endif | |
| #if defined(__KERNEL__) | |
| #define BAD_KERNEL | |
| #endif | |
| #if defined(__KERNEL__) || !defined(__GLIBC__) || (__GLIBC__ < 2) | |
| #define X | |
| #endif | |
| #ifndef SIGRTMAX | |
| #define SIGRTMAX 123 | |
| #endif /* SIGRTMAX */ | |
| #if 0 | |
| #if 1 | |
| #define BAD_6 | |
| #endif | |
| #endif\ | |
| """ | |
| expected = """\ | |
| #define GOOD_1 | |
| #define GOOD_2 | |
| #define GOOD_3 | |
| #if !defined(__GLIBC__) || __GLIBC__ < 2 | |
| #define X | |
| #endif | |
| #ifndef __SIGRTMAX | |
| #define __SIGRTMAX 123 | |
| #endif | |
| """ | |
| out = StringOutput() | |
| lines = string.split(text, '\n') | |
| list = BlockParser().parse( CppLinesTokenizer(lines) ) | |
| #D_setlevel(2) | |
| list.replaceTokens( kernel_token_replacements ) | |
| list.optimizeAll( {"__KERNEL__":kCppUndefinedMacro} ) | |
| list.write(out) | |
| if out.get() != expected: | |
| print "[FAIL]: macro optimization failed\n" | |
| print "<<<< expecting '", | |
| print expected, | |
| print "'\n>>>> result '" | |
| print out.get(), | |
| print "'\n----" | |
| global failure_count | |
| failure_count += 1 | |
| # -- Always run the unit tests. | |
| def runUnitTests(): | |
| """run all unit tests for this program""" | |
| test_CppTokenizer() | |
| test_CppExpr() | |
| test_optimizeAll() | |
| test_BlockParser() | |
| failure_count = 0 | |
| runUnitTests() | |
| if failure_count != 0: | |
| sys.exit(1) |