path: root/libc/kernel/tools/cpp.py

# 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:
        - direcive 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 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 __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 removePrefixed(self,prefix,names):
        for b in self.blocks:
            if b.isIf():
                b.expr.removePrefixed(prefix,names)

    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 removeComments(self):
        for b in self.blocks:
            for tok in b.tokens:
                if tok.id == tokSPACE:
                    tok.value = " "

    def removeEmptyLines(self):
        # state = 1 => previous line was tokLN
        # state = 0 => previous line was directive
        state  = 1
        for b in self.blocks:
            if b.isDirective():
                #print "$$$ directive %s" % str(b)
                state = 0
            else:
                # a tokLN followed by spaces is replaced by a single tokLN
                # several successive tokLN are replaced by a single one
                #
                dst   = []
                src   = b.tokens
                n     = len(src)
                i     = 0
                #print "$$$ parsing %s" % repr(src)
                while i < n:
                    # find final tokLN
                    j = i
                    while j < n and src[j].id != tokLN:
                        j += 1

                    if j >= n:
                        # uhhh
                        dst += src[i:]
                        break

                    if src[i].id == tokSPACE:
                        k = i+1
                        while src[k].id == tokSPACE:
                            k += 1

                        if k == j: # empty lines with spaces in it
                            i = j  # remove the spaces

                    if i == j:
                        # an empty line
                        if state == 1:
                            i += 1   # remove it
                        else:
                            state = 1
                            dst.append(src[i])
                            i   += 1
                    else:
                        # this line is not empty, remove trailing spaces
                        k = j
                        while k > i and src[k-1].id == tokSPACE:
                            k -= 1

                        nn = i
                        while nn < k:
                            dst.append(src[nn])
                            nn += 1
                        dst.append(src[j])
                        state = 0
                        i = j+1

                b.tokens = dst

    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 = 1 => typedef/struct encountered
        # state = 2 => vars or func declaration encountered, skipping until ";"
        # state = 0 => normal (i.e. LN + spaces)
        state      = 0
        depth      = 0
        blocks2    = []
        for b in self.blocks:
            if b.isDirective():
                blocks2.append(b)
            else:
                n     = len(b.tokens)
                i     = 0
                first = 0
                if state == 2:
                    first = n
                while i < n:
                    tok = b.tokens[i]
                    if state == 0:
                        bad = 0
                        if tok.id in [tokLN, tokSPACE]:
                            pass
                        elif tok.value in [ 'struct', 'typedef', 'enum', 'union' ]:
                            state = 1
                        else:
                            if tok.value in [ 'static', 'extern', '__KINLINE' ]:
                                j = i+1
                                ident = ""
                                while j < n and not (b.tokens[j].id in [ '(', ';' ]):
                                    if b.tokens[j].id == tokIDENT:
                                        ident = b.tokens[j].value
                                    j += 1
                                if j < n and ident in knownStatics:
                                    # this is a known static, we're going to keep its
                                    # definition in the final output
                                    state = 1
                                else:
                                    #print "### skip static '%s'" % ident
                                    pass

                            if state == 0:
                                if i > first:
                                    #print "### intermediate from '%s': '%s'" % (tok.value, repr(b.tokens[first:i]))
                                    blocks2.append( Block(b.tokens[first:i]) )
                                state = 2
                                first = n

                    else:  # state > 0
                        if tok.id == '{':
                            depth += 1

                        elif tok.id == '}':
                            if depth > 0:
                                depth -= 1

                        elif depth == 0 and tok.id == ';':
                            if state == 2:
                                first = i+1
                            state = 0

                    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

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