abtest.py

#!/usr/bin/env python
#
# Given a previous good compile narrow down miscompiles.
# Expects two directories named "before" and "after" each containing a set of
# assembly or object files where the "after" version is assumed to be broken.
# You also have to provide a script called "link_test". It is called with a
# list of files which should be linked together and result tested. "link_test"
# should returns with exitcode 0 if the linking and testing succeeded.
#
# abtest.py operates by taking all files from the "before" directory and
# in each step replacing one of them with a file from the "bad" directory.
#
# Additionally you can perform the same steps with a single .s file. In this
# mode functions are identified by " -- Begin function FunctionName" and
# " -- End function" markers. The abtest.py then takes all
# function from the file in the "before" directory and replaces one function
# with the corresponding function from the "bad" file in each step.
#
# Example usage to identify miscompiled files:
# 1. Create a link_test script, make it executable. Simple Example:
# clang "$@" -o /tmp/test && /tmp/test || echo "PROBLEM"
# 2. Run the script to figure out which files are miscompiled:
# > ./abtest.py
# somefile.s: ok
# someotherfile.s: skipped: same content
# anotherfile.s: failed: './link_test' exitcode != 0
# ...
# Example usage to identify miscompiled functions inside a file:
# 3. Run the tests on a single file (assuming before/file.s and
# after/file.s exist)
# > ./abtest.py file.s
# funcname1 [0/XX]: ok
# funcname2 [1/XX]: ok
# funcname3 [2/XX]: skipped: same content
# funcname4 [3/XX]: failed: './link_test' exitcode != 0
# ...
fromfnmatchimportfilter
fromsysimportstderr
importargparse
importfilecmp
importos
importsubprocess
importsys


LINKTEST="./link_test"
ESCAPE="\033[%sm"
BOLD=ESCAPE%"1"
RED=ESCAPE%"31"
NORMAL=ESCAPE%"0"
FAILED=RED+"failed"+NORMAL


deffind(dir, file_filter=None):
files= [
walkdir[0]+"/"+file
forwalkdirinos.walk(dir)
forfileinwalkdir[2]
 ]
iffile_filterisnotNone:
files=filter(files, file_filter)
returnsorted(files)


deferror(message):
stderr.write("Error: %s\n"% (message,))


defwarn(message):
stderr.write("Warning: %s\n"% (message,))


definfo(message):
stderr.write("Info: %s\n"% (message,))


defannounce_test(name):
stderr.write("%s%s%s: "% (BOLD, name, NORMAL))
stderr.flush()


defannounce_result(result):
stderr.write(result)
stderr.write("\n")
stderr.flush()


defformat_namelist(l):
result=", ".join(l[0:3])
iflen(l) >3:
result+="... (%d total)"%len(l)
returnresult


defcheck_sanity(choices, perform_test):
announce_test("sanity check A")
all_a= {name: a_b[0] forname, a_binchoices}
res_a=perform_test(all_a)
ifres_aisnotTrue:
error("Picking all choices from A failed to pass the test")
sys.exit(1)

announce_test("sanity check B (expecting failure)")
all_b= {name: a_b[1] forname, a_binchoices}
res_b=perform_test(all_b)
ifres_bisnotFalse:
error("Picking all choices from B did unexpectedly pass the test")
sys.exit(1)


defcheck_sequentially(choices, perform_test):
known_good=set()
all_a= {name: a_b[0] forname, a_binchoices}
n=1
forname, a_binsorted(choices):
picks=dict(all_a)
picks[name] =a_b[1]
announce_test("checking %s [%d/%d]"% (name, n, len(choices)))
n+=1
res=perform_test(picks)
ifresisTrue:
known_good.add(name)
returnknown_good


defcheck_bisect(choices, perform_test):
known_good=set()
iflen(choices) ==0:
returnknown_good

choice_map=dict(choices)
all_a= {name: a_b[0] forname, a_binchoices}

deftest_partition(partition, upcoming_partition):
# Compute the maximum number of checks we have to do in the worst case.
max_remaining_steps=len(partition) *2-1
ifupcoming_partitionisnotNone:
max_remaining_steps+=len(upcoming_partition) *2-1
forxinpartitions_to_split:
max_remaining_steps+= (len(x) -1) *2

picks=dict(all_a)
forxinpartition:
picks[x] =choice_map[x][1]
announce_test("checking %s [<=%d remaining]"%
 (format_namelist(partition), max_remaining_steps))
res=perform_test(picks)
ifresisTrue:
known_good.update(partition)
eliflen(partition) >1:
partitions_to_split.insert(0, partition)

# TODO:
# - We could optimize based on the knowledge that when splitting a failed
# partition into two and one side checks out okay then we can deduce that
# the other partition must be a failure.
all_choice_names= [nameforname, _inchoices]
partitions_to_split= [all_choice_names]
whilelen(partitions_to_split) >0:
partition=partitions_to_split.pop()

middle=len(partition) //2
left=partition[0:middle]
right=partition[middle:]

iflen(left) >0:
test_partition(left, right)
assertlen(right) >0
test_partition(right, None)

returnknown_good


defextract_functions(file):
functions= []
in_function=None
forlineinopen(file):
marker=line.find(" -- Begin function ")
ifmarker!=-1:
ifin_functionisnotNone:
warn("Missing end of function %s"% (in_function,))
funcname=line[marker+19:-1]
in_function=funcname
text=line
continue

marker=line.find(" -- End function")
ifmarker!=-1:
text+=line
functions.append((in_function, text))
in_function=None
continue

ifin_functionisnotNone:
text+=line
returnfunctions


defreplace_functions(source, dest, replacements):
out=open(dest, "w")
skip=False
in_function=None
forlineinopen(source):
marker=line.find(" -- Begin function ")
ifmarker!=-1:
ifin_functionisnotNone:
warn("Missing end of function %s"% (in_function,))
funcname=line[marker+19:-1]
in_function=funcname
replacement=replacements.get(in_function)
ifreplacementisnotNone:
out.write(replacement)
skip=True
else:
marker=line.find(" -- End function")
ifmarker!=-1:
in_function=None
ifskip:
skip=False
continue

ifnotskip:
out.write(line)


deftestrun(files):
linkline="%s %s"% (LINKTEST, " ".join(files),)
res=subprocess.call(linkline, shell=True)
ifres!=0:
announce_result(FAILED+": '%s' exitcode != 0"%LINKTEST)
returnFalse
else:
announce_result("ok")
returnTrue


defprepare_files(gooddir, baddir):
files_a=find(gooddir, "*")
files_b=find(baddir, "*")

basenames_a=set(map(os.path.basename, files_a))
basenames_b=set(map(os.path.basename, files_b))

fornameinfiles_b:
basename=os.path.basename(name)
ifbasenamenotinbasenames_a:
warn("There is no corresponding file to '%s' in %s"%
 (name, gooddir))
choices= []
skipped= []
fornameinfiles_a:
basename=os.path.basename(name)
ifbasenamenotinbasenames_b:
warn("There is no corresponding file to '%s' in %s"%
 (name, baddir))

file_a=gooddir+"/"+basename
file_b=baddir+"/"+basename
iffilecmp.cmp(file_a, file_b):
skipped.append(basename)
continue

choice= (basename, (file_a, file_b))
choices.append(choice)

iflen(skipped) >0:
info("Skipped (same content): %s"%format_namelist(skipped))

defperform_test(picks):
files= []
# Note that we iterate over files_a so we don't change the order
# (cannot use `picks` as it is a dictionary without order)
forxinfiles_a:
basename=os.path.basename(x)
picked=picks.get(basename)
ifpickedisNone:
assertbasenameinskipped
files.append(x)
else:
files.append(picked)
returntestrun(files)

returnperform_test, choices


defprepare_functions(to_check, gooddir, goodfile, badfile):
files_good=find(gooddir, "*")

functions_a=extract_functions(goodfile)
functions_a_map=dict(functions_a)
functions_b_map=dict(extract_functions(badfile))

fornameinfunctions_b_map.keys():
ifnamenotinfunctions_a_map:
warn("Function '%s' missing from good file"%name)
choices= []
skipped= []
forname, candidate_ainfunctions_a:
candidate_b=functions_b_map.get(name)
ifcandidate_bisNone:
warn("Function '%s' missing from bad file"%name)
continue
ifcandidate_a==candidate_b:
skipped.append(name)
continue
choice=name, (candidate_a, candidate_b)
choices.append(choice)

iflen(skipped) >0:
info("Skipped (same content): %s"%format_namelist(skipped))

combined_file='/tmp/combined2.s'
files= []
found_good_file=False
forcinfiles_good:
ifos.path.basename(c) ==to_check:
found_good_file=True
files.append(combined_file)
continue
files.append(c)
assertfound_good_file

defperform_test(picks):
forname, xinpicks.items():
assertx==functions_a_map[name] orx==functions_b_map[name]
replace_functions(goodfile, combined_file, picks)
returntestrun(files)
returnperform_test, choices


defmain():
parser=argparse.ArgumentParser()
parser.add_argument('--a', dest='dir_a', default='before')
parser.add_argument('--b', dest='dir_b', default='after')
parser.add_argument('--insane', help='Skip sanity check',
action='store_true')
parser.add_argument('--seq',
help='Check sequentially instead of bisection',
action='store_true')
parser.add_argument('file', metavar='file', nargs='?')
config=parser.parse_args()

gooddir=config.dir_a
baddir=config.dir_b

# Preparation phase: Creates a dictionary mapping names to a list of two
# choices each. The bisection algorithm will pick one choice for each name
# and then run the perform_test function on it.
ifconfig.fileisnotNone:
goodfile=gooddir+"/"+config.file
badfile=baddir+"/"+config.file
perform_test, choices=prepare_functions(config.file, gooddir,
goodfile, badfile)
else:
perform_test, choices=prepare_files(gooddir, baddir)

info("%d bisection choices"%len(choices))

# "Checking whether build environment is sane ..."
ifnotconfig.insane:
ifnotos.access(LINKTEST, os.X_OK):
error("Expect '%s' to be present and executable"% (LINKTEST,))
exit(1)

check_sanity(choices, perform_test)

ifconfig.seq:
known_good=check_sequentially(choices, perform_test)
else:
known_good=check_bisect(choices, perform_test)

stderr.write("")
iflen(known_good) !=len(choices):
stderr.write("== Failing ==\n")
forname, _inchoices:
ifnamenotinknown_good:
stderr.write("%s\n"%name)
else:
# This shouldn't happen when the sanity check works...
# Maybe link_test isn't deterministic?
stderr.write("Could not identify failing parts?!?")


if__name__=='__main__':
main()