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