1 #!/usr/bin/env python 2 3 import os 4 import re 5 import subprocess 6 import sys 7 import tempfile 8 9 ### 10 11 class 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 97 class 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 106 kTokenRE = re.compile(r"""([a-z_]+) '(.*)'\t(.*)\tLoc=<(.*):(.*):(.*)>""", 107 re.DOTALL | re.MULTILINE) 108 109 def 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 133 class 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 215 def 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 231 def 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 246 if __name__ == '__main__': 247 try: 248 main() 249 except KeyboardInterrupt: 250 print >>sys.stderr,'Interrupted.' 251 os._exit(1) # Avoid freeing our giant cache. 252
