# 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).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 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()