| # 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 C U R S O R ##### |
| ##### ##### |
| ##################################################################################### |
| ##################################################################################### |
| |
| class TokenCursor: |
| """a small class to iterate over a list of Token objects""" |
| def __init__(self,tokens): |
| self.tokens = tokens |
| self.n = 0 |
| self.count = len(tokens) |
| |
| def set(self,n): |
| """set the current position""" |
| if n < 0: |
| n = 0 |
| if n > self.count: |
| n = self.count |
| self.n = n |
| |
| def peekId(self): |
| """retrieve the id of the current token""" |
| if (self.n >= self.count): |
| return None |
| return self.tokens[self.n].id |
| |
| def peek(self): |
| """retrieve the current token. does not change position""" |
| if (self.n >= self.count): |
| return None |
| return self.tokens[self.n] |
| |
| def skip(self): |
| """increase current token position""" |
| if (self.n < self.count): |
| self.n += 1 |
| |
| def skipSpaces(self): |
| """skip over all space tokens, this includes tokSPACE and tokLN""" |
| while 1: |
| tok = self.peekId() |
| if tok != tokSPACE and tok != tokLN: |
| break |
| self.skip() |
| |
| def skipIfId(self,id): |
| """skip an optional token""" |
| if self.peekId() == id: |
| self.skip() |
| |
| def expectId(self,id): |
| """raise an exception if the current token hasn't a given id. |
| otherwise skip over it""" |
| tok = self.peek() |
| if tok.id != id: |
| raise BadExpectedToken, "%d:%d: '%s' expected, received '%s'" % (tok.lineno, tok.colno, id, tok.id) |
| self.skip() |
| |
| def remain(self): |
| """return the list of remaining tokens""" |
| return self.tokens[self.n:] |
| |
| |
| ##################################################################################### |
| ##################################################################################### |
| ##### ##### |
| ##### 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: |
| #print "## EOF after '%s'" % value |
| return tok.set(tokEOF,value) |
| if c == '/' and prev_c == '*': |
| break |
| prev_c = c |
| value += c |
| |
| value += "/" |
| #print "## COMMENT: '%s'" % 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(): |
| print "running CppTokenizer tests" |
| 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 ##### |
| ##### ##### |
| ##################################################################################### |
| ##################################################################################### |
| |
| # Cpp expressions are modeled by tuples of the form (op,arg) or (op,arg1,arg2), etc.. |
| # op is an "operator" string |
| |
| class Expr: |
| """a class used to model a CPP expression""" |
| opInteger = "int" |
| opIdent = "ident" |
| opCall = "call" |
| opDefined = "defined" |
| opTest = "?" |
| opLogicNot = "!" |
| opNot = "~" |
| opNeg = "[-]" |
| opUnaryPlus = "[+]" |
| opAdd = "+" |
| opSub = "-" |
| opMul = "*" |
| opDiv = "/" |
| opMod = "%" |
| opAnd = "&" |
| opOr = "|" |
| opXor = "^" |
| opLogicAnd = "&&" |
| opLogicOr = "||" |
| opEqual = "==" |
| opNotEqual = "!=" |
| opLess = "<" |
| opLessEq = "<=" |
| opGreater = ">" |
| opGreaterEq = ">=" |
| opShl = "<<" |
| opShr = ">>" |
| |
| unaries = [ opLogicNot, opNot, opNeg, opUnaryPlus ] |
| binaries = [ opAdd, opSub, opMul, opDiv, opMod, opAnd, opOr, opXor, opLogicAnd, opLogicOr, |
| opEqual, opNotEqual, opLess, opLessEq, opGreater, opGreaterEq ] |
| |
| precedences = { |
| opTest: 0, |
| opLogicOr: 1, |
| opLogicNot: 2, |
| opOr : 3, |
| opXor: 4, |
| opAnd: 5, |
| opEqual: 6, opNotEqual: 6, |
| opLess:7, opLessEq:7, opGreater:7, opGreaterEq:7, |
| opShl:8, opShr:8, |
| opAdd:9, opSub:9, |
| opMul:10, opDiv:10, opMod:10, |
| opLogicNot:11, |
| opNot: 12, |
| } |
| |
| def __init__(self,op): |
| self.op = op |
| |
| def __repr__(self): |
| return "(%s)" % self.op |
| |
| def __str__(self): |
| return "operator(%s)" % self.op |
| |
| def precedence(self): |
| """return the precedence of a given operator""" |
| return Expr.precedences.get(self.op, 1000) |
| |
| def isUnary(self): |
| return self.op in Expr.unaries |
| |
| def isBinary(self): |
| return self.op in Expr.binaries |
| |
| def isDefined(self): |
| return self.op is opDefined |
| |
| def toInt(self): |
| """return the integer value of a given expression. only valid for integer expressions |
| will return None otherwise""" |
| return None |
| |
| class IntExpr(Expr): |
| def __init__(self,value): |
| Expr.__init__(self,opInteger) |
| self.arg = value |
| |
| def __repr__(self): |
| return "(int %s)" % self.arg |
| |
| def __str__(self): |
| return self.arg |
| |
| def toInt(self): |
| s = self.arg # string value |
| # get rid of U or L suffixes |
| while len(s) > 0 and s[-1] in "LUlu": |
| s = s[:-1] |
| return string.atoi(s) |
| |
| class IdentExpr(Expr): |
| def __init__(self,name): |
| Expr.__init__(self,opIdent) |
| self.name = name |
| |
| def __repr__(self): |
| return "(ident %s)" % self.name |
| |
| def __str__(self): |
| return self.name |
| |
| class CallExpr(Expr): |
| def __init__(self,funcname,params): |
| Expr.__init__(self,opCall) |
| self.funcname = funcname |
| self.params = params |
| |
| def __repr__(self): |
| result = "(call %s [" % self.funcname |
| comma = "" |
| for param in self.params: |
| result += "%s%s" % (comma, repr(param)) |
| comma = "," |
| result += "])" |
| return result |
| |
| def __str__(self): |
| result = "%s(" % self.funcname |
| comma = "" |
| for param in self.params: |
| result += "%s%s" % (comma, str(param)) |
| comma = "," |
| |
| result += ")" |
| return result |
| |
| class TestExpr(Expr): |
| def __init__(self,cond,iftrue,iffalse): |
| Expr.__init__(self,opTest) |
| self.cond = cond |
| self.iftrue = iftrue |
| self.iffalse = iffalse |
| |
| def __repr__(self): |
| return "(?: %s %s %s)" % (repr(self.cond),repr(self.iftrue),repr(self.iffalse)) |
| |
| def __str__(self): |
| return "(%s) ? (%s) : (%s)" % (self.cond, self.iftrue, self.iffalse) |
| |
| class SingleArgExpr(Expr): |
| def __init__(self,op,arg): |
| Expr.__init__(self,op) |
| self.arg = arg |
| |
| def __repr__(self): |
| return "(%s %s)" % (self.op, repr(self.arg)) |
| |
| class DefinedExpr(SingleArgExpr): |
| def __init__(self,op,macroname): |
| SingleArgExpr.__init__(self.opDefined,macroname) |
| |
| def __str__(self): |
| return "defined(%s)" % self.arg |
| |
| |
| class UnaryExpr(SingleArgExpr): |
| def __init__(self,op,arg,opstr=None): |
| SingleArgExpr.__init__(self,op,arg) |
| if not opstr: |
| opstr = op |
| self.opstr = opstr |
| |
| def __str__(self): |
| arg_s = str(self.arg) |
| arg_prec = self.arg.precedence() |
| self_prec = self.precedence() |
| if arg_prec < self_prec: |
| return "%s(%s)" % (self.opstr,arg_s) |
| else: |
| return "%s%s" % (self.opstr, arg_s) |
| |
| class TwoArgExpr(Expr): |
| def __init__(self,op,arg1,arg2): |
| Expr.__init__(self,op) |
| self.arg1 = arg1 |
| self.arg2 = arg2 |
| |
| def __repr__(self): |
| return "(%s %s %s)" % (self.op, repr(self.arg1), repr(self.arg2)) |
| |
| class BinaryExpr(TwoArgExpr): |
| def __init__(self,op,arg1,arg2,opstr=None): |
| TwoArgExpr.__init__(self,op,arg1,arg2) |
| if not opstr: |
| opstr = op |
| self.opstr = opstr |
| |
| def __str__(self): |
| arg1_s = str(self.arg1) |
| arg2_s = str(self.arg2) |
| arg1_prec = self.arg1.precedence() |
| arg2_prec = self.arg2.precedence() |
| self_prec = self.precedence() |
| |
| result = "" |
| if arg1_prec < self_prec: |
| result += "(%s)" % arg1_s |
| else: |
| result += arg1_s |
| |
| result += " %s " % self.opstr |
| |
| if arg2_prec < self_prec: |
| result += "(%s)" % arg2_s |
| else: |
| result += arg2_s |
| |
| return result |
| |
| ##################################################################################### |
| ##################################################################################### |
| ##### ##### |
| ##### C P P E X P R E S S I O N P A R S E R ##### |
| ##### ##### |
| ##################################################################################### |
| ##################################################################################### |
| |
| |
| class ExprParser: |
| """a class used to convert a list of tokens into a cpp Expr object""" |
| |
| re_octal = re.compile(r"\s*\(0[0-7]+\).*") |
| re_decimal = re.compile(r"\s*\(\d+[ulUL]*\).*") |
| re_hexadecimal = re.compile(r"\s*\(0[xX][0-9a-fA-F]*\).*") |
| |
| def __init__(self,tokens): |
| self.tok = tokens |
| self.n = len(self.tok) |
| self.i = 0 |
| |
| def mark(self): |
| return self.i |
| |
| def release(self,pos): |
| self.i = pos |
| |
| def peekId(self): |
| if self.i < self.n: |
| return self.tok[self.i].id |
| return None |
| |
| def peek(self): |
| if self.i < self.n: |
| return self.tok[self.i] |
| return None |
| |
| def skip(self): |
| if self.i < self.n: |
| self.i += 1 |
| |
| def skipOptional(self,id): |
| if self.i < self.n and self.tok[self.i].id == id: |
| self.i += 1 |
| |
| def skipSpaces(self): |
| i = self.i |
| n = self.n |
| tok = self.tok |
| while i < n and (tok[i] == tokSPACE or tok[i] == tokLN): |
| i += 1 |
| self.i = i |
| |
| # all the isXXX functions returns a (expr,nextpos) pair if a match is found |
| # or None if not |
| |
| def is_integer(self): |
| id = self.tok[self.i].id |
| c = id[0] |
| if c < '0' or c > '9': |
| return None |
| |
| m = ExprParser.re_octal.match(id) |
| if m: |
| return (IntExpr(id), m.end(1)) |
| |
| m = ExprParser.re_decimal.match(id) |
| if m: |
| return (IntExpr(id), m.end(1)) |
| |
| m = ExprParser.re_hexadecimal(id) |
| if m: |
| return (IntExpr(id), m.end(1)) |
| |
| return None |
| |
| def is_defined(self): |
| id = self.tok[self.i].id |
| if id != "defined": |
| return None |
| |
| pos = self.mark() |
| |
| use_paren = 0 |
| if self.peekId() == tokLPAREN: |
| self.skip() |
| use_paren = 1 |
| |
| if self.peekId() != tokIDENT: |
| self.throw( BadExpectedToken, "identifier expected") |
| |
| macroname = self.peek().value |
| self.skip() |
| if use_paren: |
| self.skipSpaces() |
| if self.peekId() != tokRPAREN: |
| self.throw( BadExpectedToken, "missing right-paren after 'defined' directive") |
| self.skip() |
| |
| i = self.i |
| return (DefinedExpr(macroname),i+1) |
| |
| def is_call_or_ident(self): |
| pass |
| |
| def parse(self, i): |
| return None |
| |
| ##################################################################################### |
| ##################################################################################### |
| ##### ##### |
| ##### C P P E X P R E S S I O N S ##### |
| ##### ##### |
| ##################################################################################### |
| ##################################################################################### |
| |
| class CppInvalidExpression(Exception): |
| """an exception raised when an invalid/unsupported cpp expression is detected""" |
| pass |
| |
| 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, |
| "&&": 2, |
| "|": 3, |
| "^": 4, |
| "&": 5, |
| "==":6, "!=":6, |
| "<":7, "<=":7, ">":7, ">=":7, |
| "<<":8, ">>":8, |
| "+":9, "-":9, |
| "*":10, "/":10, "%":10, |
| "!":11, "~":12 |
| } |
| |
| def __init__(self, tokens): |
| """initialize a CppExpr. 'tokens' must be a CppToken list""" |
| self.tok = tokens |
| self.n = len(tokens) |
| if debugCppExpr: |
| print "CppExpr: trying to parse %s" % repr(tokens) |
| expr = self.is_expr(0) |
| if debugCppExpr: |
| print "CppExpr: got " + repr(expr) |
| self.expr = expr[0] |
| |
| re_cpp_constant = re.compile(r"((\d|\w|_)+)") |
| |
| def throw(self,exception,i,msg): |
| if i < self.n: |
| tok = self.tok[i] |
| print "%d:%d: %s" % (tok.lineno,tok.colno,msg) |
| else: |
| print "EOF: %s" % msg |
| raise exception |
| |
| def skip_spaces(self,i): |
| """skip spaces in input token list""" |
| while i < self.n: |
| t = self.tok[i] |
| if t.id != tokSPACE and t.id != tokLN: |
| break |
| i += 1 |
| return i |
| |
| def expectId(self,i,id): |
| """check that a given token id is at the current position, then skip over it""" |
| i = self.skip_spaces(i) |
| if i >= self.n or self.tok[i].id != id: |
| self.throw(BadExpectedToken,i,"### expecting '%s' in expression, got '%s'" % (id, self.tok[i].id)) |
| return i+1 |
| |
| def expectIdent(self,i): |
| i = self.skip_spaces(i) |
| if i >= self.n or self.tok[i].id != tokIDENT: |
| self.throw(BadExpectedToken,i,"### expecting identifier in expression, got '%s'" % (id, self.tok[i].id)) |
| return i+1 |
| |
| # the is_xxxxx function returns either None or a pair (e,nextpos) |
| # where 'e' is an expression tuple (e.g. (op,arg)) and 'nextpos' is |
| # the corresponding next position in the input token list |
| # |
| |
| def is_decimal(self,i): |
| v = self.tok[i].value[:] |
| while len(v) > 0 and v[-1] in "ULul": |
| v = v[:-1] |
| for digit in v: |
| if not digit.isdigit(): |
| return None |
| |
| # for an integer expression tuple, the argument |
| # is simply the value as an integer |
| val = string.atoi(v) |
| return ("int", val), i+1 |
| |
| def is_hexadecimal(self,i): |
| v = self.tok[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 an hex expression tuple, the argument |
| # is the value as an integer |
| val = int(v[2:], 16) |
| return ("hex", val), i+1 |
| |
| return None |
| |
| def is_integer(self,i): |
| if self.tok[i].id != tokNUMBER: |
| return None |
| |
| c = self.is_decimal(i) |
| if c: return c |
| |
| c = self.is_hexadecimal(i) |
| if c: return c |
| |
| return None |
| |
| def is_number(self,i): |
| t = self.tok[i] |
| if t.id == tokMINUS and i+1 < self.n: |
| c = self.is_integer(i+1) |
| if c: |
| e, i2 = c |
| op, val = e |
| return (op, -val), i2 |
| if t.id == tokPLUS and i+1 < self.n: |
| c = self.is_integer(i+1) |
| if c: return c |
| |
| return self.is_integer(i) |
| |
| |
| def is_alnum(self,i): |
| """test wether a given token is alpha-numeric""" |
| i = self.skip_spaces(i) |
| if i >= self.n: |
| return None |
| t = self.tok[i] |
| m = CppExpr.re_cpp_constant.match(t.id) |
| if m: |
| #print "... alnum '%s'" % m.group(1) |
| r = m.group(1) |
| return ("ident", r), i+1 |
| return None |
| |
| def is_defined(self,i): |
| t = self.tok[i] |
| if t.id != tokDEFINED: |
| return None |
| |
| # we have the defined keyword, check the rest |
| i = self.skip_spaces(i+1) |
| use_parens = 0 |
| if i < self.n and self.tok[i].id == tokLPAREN: |
| use_parens = 1 |
| i = self.skip_spaces(i+1) |
| |
| if i >= self.n: |
| self.throw(CppConstantExpected,i,"### 'defined' must be followed by macro name or left paren") |
| |
| t = self.tok[i] |
| if t.id != tokIDENT: |
| self.throw(CppConstantExpected,i,"### 'defined' must be followed by macro name") |
| |
| i += 1 |
| if use_parens: |
| i = self.expectId(i,tokRPAREN) |
| |
| return ("defined",t.value), i |
| |
| |
| def is_call_or_ident(self,i): |
| i = self.skip_spaces(i) |
| if i >= self.n: |
| return None |
| |
| t = self.tok[i] |
| if t.id != tokIDENT: |
| return None |
| |
| name = t.value |
| |
| i = self.skip_spaces(i+1) |
| if i >= self.n or self.tok[i].id != tokLPAREN: |
| return ("ident", name), i |
| |
| params = [] |
| depth = 1 |
| i += 1 |
| j = i |
| while i < self.n: |
| id = self.tok[i].id |
| if id == tokLPAREN: |
| depth += 1 |
| elif depth == 1 and (id == tokCOMMA or id == tokRPAREN): |
| while j < i and self.tok[j].id == tokSPACE: |
| j += 1 |
| k = 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 = i+1 |
| elif id == tokRPAREN: |
| depth -= 1 |
| i += 1 |
| |
| if i >= self.n: |
| return None |
| |
| return ("call", (name, params)), i+1 |
| |
| def is_token(self,i,token): |
| i = self.skip_spaces(i) |
| if i >= self.n or self.tok[i].id != token: |
| return None |
| return token, i+1 |
| |
| |
| def is_value(self,i): |
| t = self.tok[i] |
| if t.id == tokSTRING: |
| return ("string", t.value), i+1 |
| |
| c = self.is_number(i) |
| if c: return c |
| |
| c = self.is_defined(i) |
| if c: return c |
| |
| c = self.is_call_or_ident(i) |
| if c: return c |
| |
| i = self.skip_spaces(i) |
| if i >= self.n or self.tok[i].id != tokLPAREN: |
| return None |
| |
| popcount = 1 |
| i2 = i+1 |
| while i2 < self.n: |
| t = self.tok[i2] |
| if t.id == tokLPAREN: |
| popcount += 1 |
| elif t.id == tokRPAREN: |
| popcount -= 1 |
| if popcount == 0: |
| break |
| i2 += 1 |
| |
| if popcount != 0: |
| self.throw(CppInvalidExpression, i, "expression missing closing parenthesis") |
| |
| if debugCppExpr: |
| print "CppExpr: trying to parse sub-expression %s" % repr(self.tok[i+1:i2]) |
| oldcount = self.n |
| self.n = i2 |
| c = self.is_expr(i+1) |
| self.n = oldcount |
| if not c: |
| self.throw(CppInvalidExpression, i, "invalid expression within parenthesis") |
| |
| e, i = c |
| return e, i2+1 |
| |
| def is_unary(self,i): |
| i = self.skip_spaces(i) |
| if i >= self.n: |
| return None |
| |
| t = self.tok[i] |
| if t.id in CppExpr.unaries: |
| c = self.is_unary(i+1) |
| if not c: |
| self.throw(CppInvalidExpression, i, "%s operator must be followed by value" % t.id) |
| e, i = c |
| return (t.id, e), i |
| |
| return self.is_value(i) |
| |
| def is_binary(self,i): |
| i = self.skip_spaces(i) |
| if i >= self.n: |
| return None |
| |
| c = self.is_unary(i) |
| if not c: |
| return None |
| |
| e1, i2 = c |
| i2 = self.skip_spaces(i2) |
| if i2 >= self.n: |
| return c |
| |
| t = self.tok[i2] |
| if t.id in CppExpr.binaries: |
| c = self.is_binary(i2+1) |
| if not c: |
| self.throw(CppInvalidExpression, i,"### %s operator must be followed by value" % t.id ) |
| e2, i3 = c |
| return (t.id, e1, e2), i3 |
| |
| return None |
| |
| def is_expr(self,i): |
| return self.is_binary(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": |
| name = e[1] |
| if macros.has_key(name): |
| if macros[name] == kCppUndefinedMacro: |
| return ("int", 0) |
| else: |
| return ("int", 1) |
| |
| if kernel_remove_config_macros and name.startswith("CONFIG_"): |
| return ("int", 0) |
| |
| 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) |
| |
| 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 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 e |
| |
| def optimize(self,macros={}): |
| self.expr = self.optimize_node(self.expr,macros) |
| |
| def removePrefixedNode(self,e,prefix,names): |
| op = e[0] |
| if op == "defined": |
| name = e[1] |
| if name.startswith(prefix): |
| if names.has_key[name] and names[name] == "y": |
| return ("int", 1) |
| else: |
| return ("int", 0) |
| |
| elif op in CppExpr.unaries: |
| op, v = e |
| v = self.removePrefixedNode(v,prefix,names) |
| return (op, v) |
| elif op in CppExpr.binaries: |
| op, v1, v2 = e |
| v1 = self.removePrefixedNode(v1,prefix,names) |
| v2 = self.removePrefixedNode(v2,prefix,names) |
| return (op, v1, v2) |
| elif op == "call": |
| func, params = e[1] |
| params2 = [] |
| for param in params: |
| params2.append( self.removePrefixedNode(param,prefix,names) ) |
| return (op, (func, params2)) |
| |
| return e |
| |
| def removePrefixed(self,prefix,names={}): |
| self.expr = self.removePrefixedNode(self.expr,prefix,names) |
| |
| 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() ) |
| #print repr(e.expr) |
| s1 = repr(e) |
| if s1 != expected: |
| print "KO: expression '%s' generates '%s', should be '%s'" % (expr, s1, expected) |
| else: |
| #print "OK: expression '%s'" % expr |
| pass |
| |
| def test_cpp_expr_optim(expr, expected, macros={}): |
| e = CppExpr( CppLineTokenizer( expr ).toTokenList() ) |
| e.optimize(macros) |
| |
| s1 = repr(e) |
| if s1 != expected: |
| print "KO: optimized expression '%s' generates '%s', should be '%s'" % (expr, s1, expected) |
| else: |
| #print "OK: optmized expression '%s'" % expr |
| pass |
| |
| def test_cpp_expr_source(expr, expected): |
| e = CppExpr( CppLineTokenizer( expr ).toTokenList() ) |
| s1 = str(e) |
| if s1 != expected: |
| print "KO: source expression '%s' generates '%s', should be '%s'" % (expr, s1, expected) |
| else: |
| #print "OK: source expression '%s'" % expr |
| pass |
| |
| def test_CppExpr(): |
| print "testing CppExpr" |
| test_cpp_expr( "0", "(int 0)" ) |
| test_cpp_expr( "1", "(int 1)" ) |
| 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(ABC) || defined(BINGO)", "(|| (defined ABC) (defined BINGO))" ) |
| test_cpp_expr( "FOO(BAR)", "(call FOO [BAR])" ) |
| |
| 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( "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)", "(int 1)", { "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)", "(int 0)", { "EXAMPLE" : "XOWOE" } ) |
| test_cpp_expr_optim( "!defined(EXAMPLE)", "(int 1)", { "EXAMPLE" : kCppUndefinedMacro } ) |
| test_cpp_expr_optim( "defined(ABC) || defined(BINGO)", "(|| (defined ABC) (defined BINGO))" ) |
| test_cpp_expr_optim( "defined(ABC) || defined(BINGO)", "(int 1)", { "ABC" : "1" } ) |
| test_cpp_expr_optim( "defined(ABC) || defined(BINGO)", "(int 1)", { "BINGO" : "1" } ) |
| test_cpp_expr_optim( "defined(ABC) || defined(BINGO)", "(defined ABC)", { "BINGO" : kCppUndefinedMacro } ) |
| test_cpp_expr_optim( "defined(ABC) || defined(BINGO)", "(int 0)", { "ABC" : kCppUndefinedMacro, "BINGO" : 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)" ) |
| |
| |
| ##################################################################################### |
| ##################################################################################### |
| ##### ##### |
| ##### 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 wether 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 |
| |
| #print "iii " + repr(self.tokens) |
| 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 |
| #print "N line=%d space=%d ii=%d" % (line, space, ii) |
| ii += 1 |
| line = ii |
| space = -1 |
| if old_space == old_line: # line only contains spaces |
| #print "-s" |
| continue |
| if ii-1 == old_line: # line is empty |
| #print "-e" |
| 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) + "\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 += '\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 removePrefixed(self,prefix,names): |
| for b in self.blocks: |
| if b.isIf(): |
| b.expr.removePrefixed(prefix,names) |
| |
| 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__' ]: |
| #print "$$$ keep type declr" + repr(b.tokens[i:]) |
| 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=dict()): |
| """replace tokens according to the given dict |
| """ |
| for b in self.blocks: |
| if not b.isDirective(): |
| for tok in b.tokens: |
| if tok.id == tokIDENT: |
| if tok.value in replacements: |
| tok.value = replacements[tok.value] |
| |
| 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 0 |
| #if 1 |
| #define BAD_6 |
| #endif |
| #endif\ |
| """ |
| |
| expected = """\ |
| #define GOOD_1 |
| |
| #define GOOD_2 |
| |
| #define GOOD_3 |
| |
| """ |
| |
| print "running test_BlockList.optimizeAll" |
| out = StringOutput() |
| lines = string.split(text, '\n') |
| list = BlockParser().parse( CppLinesTokenizer(lines) ) |
| #D_setlevel(2) |
| list.optimizeAll( {"__KERNEL__":kCppUndefinedMacro} ) |
| #print repr(list) |
| list.write(out) |
| if out.get() != expected: |
| print "KO: macro optimization failed\n" |
| print "<<<< expecting '", |
| print expected, |
| print "'\n>>>> result '" |
| print out.get(), |
| print "'\n----" |
| |
| |
| ##################################################################################### |
| ##################################################################################### |
| ##### ##### |
| ##### ##### |
| ##### ##### |
| ##################################################################################### |
| ##################################################################################### |
| |
| def runUnitTests(): |
| """run all unit tests for this program""" |
| print "running unit tests" |
| test_CppTokenizer() |
| test_CppExpr() |
| test_optimizeAll() |
| test_BlockParser() |
| print "OK" |
| |
| if __name__ == "__main__": |
| runUnitTests() |
