utils/abtest.py

   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 #       ...
  37 from fnmatch import filter
  38 from sys import stderr
  39 import argparse
  40 import filecmp
  41 import os
  42 import subprocess
  43 import sys
  44
  45
  46 LINKTEST = "./link_test"
  47 ESCAPE = "\033[%sm"
  48 BOLD = ESCAPE % "1"
  49 RED = ESCAPE % "31"
  50 NORMAL = ESCAPE % "0"
  51 FAILED = RED + "failed" + NORMAL
  52
  53
  54 def 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
  65 def error(message):
  66     stderr.write("Error: %s\n" % (message,))
  67
  68
  69 def warn(message):
  70     stderr.write("Warning: %s\n" % (message,))
  71
  72
  73 def info(message):
  74     stderr.write("Info: %s\n" % (message,))
  75
  76
  77 def announce_test(name):
  78     stderr.write("%s%s%s: " % (BOLD, name, NORMAL))
  79     stderr.flush()
  80
  81
  82 def announce_result(result):
  83     stderr.write(result)
  84     stderr.write("\n")
  85     stderr.flush()
  86
  87
  88 def 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
  95 def 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
 111 def 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
 126 def 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
 174 def 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
 199 def 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
 226 def 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
 237 def 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
 286 def 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
 331 def 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
 384 if __name__ == '__main__':
 385     main()