token-delta.py source code [clang_source_code/utils/token-delta.py]

1	#!/usr/bin/env python
2
3	from __future__ import absolute_import, division, print_function
4	import os
5	import re
6	import subprocess
7	import sys
8	import tempfile
9
10	###
11
12	class DeltaAlgorithm(object):
13	def __init__(self):
14	self.cache = set()
15
16	def test(self, changes):
17	abstract
18
19	###
20
21	def getTestResult(self, changes):
22	# There is no reason to cache successful tests because we will
23	# always reduce the changeset when we see one.
24
25	changeset = frozenset(changes)
26	if changeset in self.cache:
27	return False
28	elif not self.test(changes):
29	self.cache.add(changeset)
30	return False
31	else:
32	return True
33
34	def run(self, changes, force=False):
35	# Make sure the initial test passes, if not then (a) either
36	# the user doesn't expect monotonicity, and we may end up
37	# doing O(N^2) tests, or (b) the test is wrong. Avoid the
38	# O(N^2) case unless user requests it.
39	if not force:
40	if not self.getTestResult(changes):
41	raise ValueError('Initial test passed to delta fails.')
42
43	# Check empty set first to quickly find poor test functions.
44	if self.getTestResult(set()):
45	return set()
46	else:
47	return self.delta(changes, self.split(changes))
48
49	def split(self, S):
50	"""split(set) -> [sets]
51
52	Partition a set into one or two pieces.
53	"""
54
55	# There are many ways to split, we could do a better job with more
56	# context information (but then the API becomes grosser).
57	L = list(S)
58	mid = len(L)//2
59	if mid==0:
60	return L,
61	else:
62	return L[:mid],L[mid:]
63
64	def delta(self, c, sets):
65	# assert(reduce(set.union, sets, set()) == c)
66
67	# If there is nothing left we can remove, we are done.
68	if len(sets) <= 1:
69	return c
70
71	# Look for a passing subset.
72	res = self.search(c, sets)
73	if res is not None:
74	return res
75
76	# Otherwise, partition sets if possible; if not we are done.
77	refined = sum(map(list, map(self.split, sets)), [])
78	if len(refined) == len(sets):
79	return c
80
81	return self.delta(c, refined)
82
83	def search(self, c, sets):
84	for i,S in enumerate(sets):
85	# If test passes on this subset alone, recurse.
86	if self.getTestResult(S):
87	return self.delta(S, self.split(S))
88
89	# Otherwise if we have more than two sets, see if test
90	# pases without this subset.
91	if len(sets) > 2:
92	complement = sum(sets[:i] + sets[i+1:],[])
93	if self.getTestResult(complement):
94	return self.delta(complement, sets[:i] + sets[i+1:])
95
96	###
97
98	class Token(object):
99	def __init__(self, type, data, flags, file, line, column):
100	self.type = type
101	self.data = data
102	self.flags = flags
103	self.file = file
104	self.line = line
105	self.column = column
106
107	kTokenRE = re.compile(r"""([a-z_]+) '(.)'\t(.)\tLoc=<(.):(.):(.*)>""",
108	re.DOTALL \| re.MULTILINE)
109
110	def getTokens(path):
111	p = subprocess.Popen(['clang','-dump-raw-tokens',path],
112	stdin=subprocess.PIPE,
113	stdout=subprocess.PIPE,
114	stderr=subprocess.PIPE)
115	out,err = p.communicate()
116
117	tokens = []
118	collect = None
119	for ln in err.split('\n'):
120	# Silly programmers refuse to print in simple machine readable
121	# formats. Whatever.
122	if collect is None:
123	collect = ln
124	else:
125	collect = collect + '\n' + ln
126	if 'Loc=<' in ln and ln.endswith('>'):
127	ln,collect = collect,None
128	tokens.append(Token(*kTokenRE.match(ln).groups()))
129
130	return tokens
131
132	###
133
134	class TMBDDelta(DeltaAlgorithm):
135	def __init__(self, testProgram, tokenLists, log):
136	def patchName(name, suffix):
137	base,ext = os.path.splitext(name)
138	return base + '.' + suffix + ext
139	super(TMBDDelta, self).__init__()
140	self.testProgram = testProgram
141	self.tokenLists = tokenLists
142	self.tempFiles = [patchName(f,'tmp')
143	for f,_ in self.tokenLists]
144	self.targetFiles = [patchName(f,'ok')
145	for f,_ in self.tokenLists]
146	self.log = log
147	self.numTests = 0
148
149	def writeFiles(self, changes, fileNames):
150	assert len(fileNames) == len(self.tokenLists)
151	byFile = [[] for i in self.tokenLists]
152	for i,j in changes:
153	byFile[i].append(j)
154
155	for i,(file,tokens) in enumerate(self.tokenLists):
156	f = open(fileNames[i],'w')
157	for j in byFile[i]:
158	f.write(tokens[j])
159	f.close()
160
161	return byFile
162
163	def test(self, changes):
164	self.numTests += 1
165
166	byFile = self.writeFiles(changes, self.tempFiles)
167
168	if self.log:
169	print('TEST - ', end=' ', file=sys.stderr)
170	if self.log > 1:
171	for i,(file,_) in enumerate(self.tokenLists):
172	indices = byFile[i]
173	if i:
174	sys.stderr.write('\n ')
175	sys.stderr.write('%s:%d tokens: [' % (file,len(byFile[i])))
176	prev = None
177	for j in byFile[i]:
178	if prev is None or j != prev + 1:
179	if prev:
180	sys.stderr.write('%d][' % prev)
181	sys.stderr.write(str(j))
182	sys.stderr.write(':')
183	prev = j
184	if byFile[i]:
185	sys.stderr.write(str(byFile[i][-1]))
186	sys.stderr.write('] ')
187	else:
188	print(', '.join(['%s:%d tokens' % (file, len(byFile[i]))
189	for i,(file,_) in enumerate(self.tokenLists)]), end=' ', file=sys.stderr)
190
191	p = subprocess.Popen([self.testProgram] + self.tempFiles)
192	res = p.wait() == 0
193
194	if res:
195	self.writeFiles(changes, self.targetFiles)
196
197	if self.log:
198	print('=> %s' % res, file=sys.stderr)
199	else:
200	if res:
201	print('\nSUCCESS (%d tokens)' % len(changes))
202	else:
203	sys.stderr.write('.')
204
205	return res
206
207	def run(self):
208	res = super(TMBDDelta, self).run([(i,j)
209	for i,(file,tokens) in enumerate(self.tokenLists)
210	for j in range(len(tokens))])
211	self.writeFiles(res, self.targetFiles)
212	if not self.log:
213	print(file=sys.stderr)
214	return res
215
216	def tokenBasedMultiDelta(program, files, log):
217	# Read in the lists of tokens.
218	tokenLists = [(file, [t.data for t in getTokens(file)])
219	for file in files]
220
221	numTokens = sum([len(tokens) for _,tokens in tokenLists])
222	print("Delta on %s with %d tokens." % (', '.join(files), numTokens))
223
224	tbmd = TMBDDelta(program, tokenLists, log)
225
226	res = tbmd.run()
227
228	print("Finished %s with %d tokens (in %d tests)." % (', '.join(tbmd.targetFiles),
229	len(res),
230	tbmd.numTests))
231
232	def main():
233	from optparse import OptionParser, OptionGroup
234	parser = OptionParser("%prog <test program> {files+}")
235	parser.add_option("", "--debug", dest="debugLevel",
236	help="set debug level [default %default]",
237	action="store", type=int, default=0)
238	(opts, args) = parser.parse_args()
239
240	if len(args) <= 1:
241	parser.error('Invalid number of arguments.')
242
243	program,files = args[0],args[1:]
244
245	md = tokenBasedMultiDelta(program, files, log=opts.debugLevel)
246
247	if __name__ == '__main__':
248	try:
249	main()
250	except KeyboardInterrupt:
251	print('Interrupted.', file=sys.stderr)
252	os._exit(1) # Avoid freeing our giant cache.
253

Clang Project