Blame - libc/kernel/tools/cpp.py - platform_bionic

blob: 54ebaf4c2a44c980a9a8b890d15da36d2f32d718 [file] [log] [blame]

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