1#!/usr/bin/env python 2# 3# Given a previous good compile narrow down miscompiles. 4# Expects two directories named "before" and "after" each containing a set of 5# assembly or object files where the "after" version is assumed to be broken. 6# You also have to provide a script called "link_test". It is called with a 7# list of files which should be linked together and result tested. "link_test" 8# should returns with exitcode 0 if the linking and testing succeeded. 9# 10# abtest.py operates by taking all files from the "before" directory and 11# in each step replacing one of them with a file from the "bad" directory. 12# 13# Additionally you can perform the same steps with a single .s file. In this 14# mode functions are identified by " -- Begin function FunctionName" and 15# " -- End function" markers. The abtest.py then takes all 16# function from the file in the "before" directory and replaces one function 17# with the corresponding function from the "bad" file in each step. 18# 19# Example usage to identify miscompiled files: 20# 1. Create a link_test script, make it executable. Simple Example: 21# clang "$@" -o /tmp/test && /tmp/test || echo "PROBLEM" 22# 2. Run the script to figure out which files are miscompiled: 23# > ./abtest.py 24# somefile.s: ok 25# someotherfile.s: skipped: same content 26# anotherfile.s: failed: './link_test' exitcode != 0 27# ... 28# Example usage to identify miscompiled functions inside a file: 29# 3. Run the tests on a single file (assuming before/file.s and 30# after/file.s exist) 31# > ./abtest.py file.s 32# funcname1 [0/XX]: ok 33# funcname2 [1/XX]: ok 34# funcname3 [2/XX]: skipped: same content 35# funcname4 [3/XX]: failed: './link_test' exitcode != 0 36# ... 37from fnmatch import filter 38from sys import stderr 39import argparse 40import filecmp 41import os 42import subprocess 43import sys 44 45 46LINKTEST = "./link_test" 47ESCAPE = "\033[%sm" 48BOLD = ESCAPE % "1" 49RED = ESCAPE % "31" 50NORMAL = ESCAPE % "0" 51FAILED = RED + "failed" + NORMAL 52 53 54def find(dir, file_filter=None): 55 files = [ 56 walkdir[0]+"/"+file 57 for walkdir in os.walk(dir) 58 for file in walkdir[2] 59 ] 60 if file_filter is not None: 61 files = filter(files, file_filter) 62 return sorted(files) 63 64 65def error(message): 66 stderr.write("Error: %s\n" % (message,)) 67 68 69def warn(message): 70 stderr.write("Warning: %s\n" % (message,)) 71 72 73def info(message): 74 stderr.write("Info: %s\n" % (message,)) 75 76 77def announce_test(name): 78 stderr.write("%s%s%s: " % (BOLD, name, NORMAL)) 79 stderr.flush() 80 81 82def announce_result(result): 83 stderr.write(result) 84 stderr.write("\n") 85 stderr.flush() 86 87 88def format_namelist(l): 89 result = ", ".join(l[0:3]) 90 if len(l) > 3: 91 result += "... (%d total)" % len(l) 92 return result 93 94 95def check_sanity(choices, perform_test): 96 announce_test("sanity check A") 97 all_a = {name: a_b[0] for name, a_b in choices} 98 res_a = perform_test(all_a) 99 if res_a is not True: 100 error("Picking all choices from A failed to pass the test") 101 sys.exit(1) 102 103 announce_test("sanity check B (expecting failure)") 104 all_b = {name: a_b[1] for name, a_b in choices} 105 res_b = perform_test(all_b) 106 if res_b is not False: 107 error("Picking all choices from B did unexpectedly pass the test") 108 sys.exit(1) 109 110 111def check_sequentially(choices, perform_test): 112 known_good = set() 113 all_a = {name: a_b[0] for name, a_b in choices} 114 n = 1 115 for name, a_b in sorted(choices): 116 picks = dict(all_a) 117 picks[name] = a_b[1] 118 announce_test("checking %s [%d/%d]" % (name, n, len(choices))) 119 n += 1 120 res = perform_test(picks) 121 if res is True: 122 known_good.add(name) 123 return known_good 124 125 126def check_bisect(choices, perform_test): 127 known_good = set() 128 if len(choices) == 0: 129 return known_good 130 131 choice_map = dict(choices) 132 all_a = {name: a_b[0] for name, a_b in choices} 133 134 def test_partition(partition, upcoming_partition): 135 # Compute the maximum number of checks we have to do in the worst case. 136 max_remaining_steps = len(partition) * 2 - 1 137 if upcoming_partition is not None: 138 max_remaining_steps += len(upcoming_partition) * 2 - 1 139 for x in partitions_to_split: 140 max_remaining_steps += (len(x) - 1) * 2 141 142 picks = dict(all_a) 143 for x in partition: 144 picks[x] = choice_map[x][1] 145 announce_test("checking %s [<=%d remaining]" % 146 (format_namelist(partition), max_remaining_steps)) 147 res = perform_test(picks) 148 if res is True: 149 known_good.update(partition) 150 elif len(partition) > 1: 151 partitions_to_split.insert(0, partition) 152 153 # TODO: 154 # - We could optimize based on the knowledge that when splitting a failed 155 # partition into two and one side checks out okay then we can deduce that 156 # the other partition must be a failure. 157 all_choice_names = [name for name, _ in choices] 158 partitions_to_split = [all_choice_names] 159 while len(partitions_to_split) > 0: 160 partition = partitions_to_split.pop() 161 162 middle = len(partition) // 2 163 left = partition[0:middle] 164 right = partition[middle:] 165 166 if len(left) > 0: 167 test_partition(left, right) 168 assert len(right) > 0 169 test_partition(right, None) 170 171 return known_good 172 173 174def extract_functions(file): 175 functions = [] 176 in_function = None 177 for line in open(file): 178 marker = line.find(" -- Begin function ") 179 if marker != -1: 180 if in_function is not None: 181 warn("Missing end of function %s" % (in_function,)) 182 funcname = line[marker + 19:-1] 183 in_function = funcname 184 text = line 185 continue 186 187 marker = line.find(" -- End function") 188 if marker != -1: 189 text += line 190 functions.append((in_function, text)) 191 in_function = None 192 continue 193 194 if in_function is not None: 195 text += line 196 return functions 197 198 199def replace_functions(source, dest, replacements): 200 out = open(dest, "w") 201 skip = False 202 in_function = None 203 for line in open(source): 204 marker = line.find(" -- Begin function ") 205 if marker != -1: 206 if in_function is not None: 207 warn("Missing end of function %s" % (in_function,)) 208 funcname = line[marker + 19:-1] 209 in_function = funcname 210 replacement = replacements.get(in_function) 211 if replacement is not None: 212 out.write(replacement) 213 skip = True 214 else: 215 marker = line.find(" -- End function") 216 if marker != -1: 217 in_function = None 218 if skip: 219 skip = False 220 continue 221 222 if not skip: 223 out.write(line) 224 225 226def testrun(files): 227 linkline = "%s %s" % (LINKTEST, " ".join(files),) 228 res = subprocess.call(linkline, shell=True) 229 if res != 0: 230 announce_result(FAILED + ": '%s' exitcode != 0" % LINKTEST) 231 return False 232 else: 233 announce_result("ok") 234 return True 235 236 237def prepare_files(gooddir, baddir): 238 files_a = find(gooddir, "*") 239 files_b = find(baddir, "*") 240 241 basenames_a = set(map(os.path.basename, files_a)) 242 basenames_b = set(map(os.path.basename, files_b)) 243 244 for name in files_b: 245 basename = os.path.basename(name) 246 if basename not in basenames_a: 247 warn("There is no corresponding file to '%s' in %s" % 248 (name, gooddir)) 249 choices = [] 250 skipped = [] 251 for name in files_a: 252 basename = os.path.basename(name) 253 if basename not in basenames_b: 254 warn("There is no corresponding file to '%s' in %s" % 255 (name, baddir)) 256 257 file_a = gooddir + "/" + basename 258 file_b = baddir + "/" + basename 259 if filecmp.cmp(file_a, file_b): 260 skipped.append(basename) 261 continue 262 263 choice = (basename, (file_a, file_b)) 264 choices.append(choice) 265 266 if len(skipped) > 0: 267 info("Skipped (same content): %s" % format_namelist(skipped)) 268 269 def perform_test(picks): 270 files = [] 271 # Note that we iterate over files_a so we don't change the order 272 # (cannot use `picks` as it is a dictionary without order) 273 for x in files_a: 274 basename = os.path.basename(x) 275 picked = picks.get(basename) 276 if picked is None: 277 assert basename in skipped 278 files.append(x) 279 else: 280 files.append(picked) 281 return testrun(files) 282 283 return perform_test, choices 284 285 286def prepare_functions(to_check, gooddir, goodfile, badfile): 287 files_good = find(gooddir, "*") 288 289 functions_a = extract_functions(goodfile) 290 functions_a_map = dict(functions_a) 291 functions_b_map = dict(extract_functions(badfile)) 292 293 for name in functions_b_map.keys(): 294 if name not in functions_a_map: 295 warn("Function '%s' missing from good file" % name) 296 choices = [] 297 skipped = [] 298 for name, candidate_a in functions_a: 299 candidate_b = functions_b_map.get(name) 300 if candidate_b is None: 301 warn("Function '%s' missing from bad file" % name) 302 continue 303 if candidate_a == candidate_b: 304 skipped.append(name) 305 continue 306 choice = name, (candidate_a, candidate_b) 307 choices.append(choice) 308 309 if len(skipped) > 0: 310 info("Skipped (same content): %s" % format_namelist(skipped)) 311 312 combined_file = '/tmp/combined2.s' 313 files = [] 314 found_good_file = False 315 for c in files_good: 316 if os.path.basename(c) == to_check: 317 found_good_file = True 318 files.append(combined_file) 319 continue 320 files.append(c) 321 assert found_good_file 322 323 def perform_test(picks): 324 for name, x in picks.items(): 325 assert x == functions_a_map[name] or x == functions_b_map[name] 326 replace_functions(goodfile, combined_file, picks) 327 return testrun(files) 328 return perform_test, choices 329 330 331def main(): 332 parser = argparse.ArgumentParser() 333 parser.add_argument('--a', dest='dir_a', default='before') 334 parser.add_argument('--b', dest='dir_b', default='after') 335 parser.add_argument('--insane', help='Skip sanity check', 336 action='store_true') 337 parser.add_argument('--seq', 338 help='Check sequentially instead of bisection', 339 action='store_true') 340 parser.add_argument('file', metavar='file', nargs='?') 341 config = parser.parse_args() 342 343 gooddir = config.dir_a 344 baddir = config.dir_b 345 346 # Preparation phase: Creates a dictionary mapping names to a list of two 347 # choices each. The bisection algorithm will pick one choice for each name 348 # and then run the perform_test function on it. 349 if config.file is not None: 350 goodfile = gooddir + "/" + config.file 351 badfile = baddir + "/" + config.file 352 perform_test, choices = prepare_functions(config.file, gooddir, 353 goodfile, badfile) 354 else: 355 perform_test, choices = prepare_files(gooddir, baddir) 356 357 info("%d bisection choices" % len(choices)) 358 359 # "Checking whether build environment is sane ..." 360 if not config.insane: 361 if not os.access(LINKTEST, os.X_OK): 362 error("Expect '%s' to be present and executable" % (LINKTEST,)) 363 exit(1) 364 365 check_sanity(choices, perform_test) 366 367 if config.seq: 368 known_good = check_sequentially(choices, perform_test) 369 else: 370 known_good = check_bisect(choices, perform_test) 371 372 stderr.write("") 373 if len(known_good) != len(choices): 374 stderr.write("== Failing ==\n") 375 for name, _ in choices: 376 if name not in known_good: 377 stderr.write("%s\n" % name) 378 else: 379 # This shouldn't happen when the sanity check works... 380 # Maybe link_test isn't deterministic? 381 stderr.write("Could not identify failing parts?!?") 382 383 384if __name__ == '__main__': 385 main() 386