Add script to bisect over files in an rsp file

[aeubanks]

Summary

This is mostly intended to be used to find which file contains a miscompile.

[aeubanks]

address some comments

[hans]

lgtm, thanks for writing this!

llvm/utils/rsp_bisect.py

3

is this needed? the llvm/utils/*.py files i sampled don't have it

91

yes, i think rsp_entries is clearer than rsp :-)

[aeubanks]

remove coding: utf-8

llvm/utils/rsp_bisect.py

+#!/usr/bin/env python3
+#===----------------------------------------------------------------------===##
+#
+# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+# See https://llvm.org/LICENSE.txt for license information.
+# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+#
+#===----------------------------------------------------------------------===##
+"""Script to bisect over files in an rsp file.
+
+This is mostly used for detecting which file contains a miscompile between two
+compiler revisions. It does this by bisecting over an rsp file. Between two
+build directories, this script will make the rsp file reference the current
+build directory's version of some set of the rsp's object files/libraries, and
+reference the other build directory's version of the same files for the
+remaining set of object files/libraries.
+
+Build the target in two separate directories with the two compiler revisions,
+keeping the rsp file around since ninja by default deletes the rsp file after
+building.
+$ ninja -d keeprsp mytarget
+
+Create a script to build the target and run an interesting test. Get the
+command to build the target via
+$ ninja -t commands | grep mytarget
+The command to build the target should reference the rsp file.
+This script doesn't care if the test script returns 0 or 1 for specifically the
+successful or failing test, just that the test script returns a different
+return code for success vs failure.
+Since the command that `ninja -t commands` is run from the build directory,
+usually the test script cd's to the build directory.
+
+$ rsp_bisect.py --test=path/to/test_script --rsp=path/to/build/target.rsp
+    --other_rel_path=../Other
+where --other_rel_path is the relative path from the first build directory to
+the other build directory. This is prepended to files in the rsp.
+
+
+For a full example, if the foo target is suspected to contain a miscompile in
+some file, have two different build directories, buildgood/ and buildbad/ and
+run
+$ ninja -d keeprsp foo
+in both so we have two versions of all relevant object files that may contain a
+miscompile, one built by a good compiler and one by a bad compiler.
+
+In buildgood/, run
+$ ninja -t commands | grep '-o .*foo'
+to get the command to link the files together. It may look something like
+  clang -o foo @foo.rsp
+
+Now create a test script that runs the link step and whatever test reproduces a
+miscompile and returns a non-zero exit code when there is a miscompile. For
+example
+```
+  #!/bin/bash
+  # immediately bail out of script if any command returns a non-zero return code
+  set -e
+  clang -o foo @foo.rsp
+  ./foo
+```
+
+With buildgood/ as the working directory, run
+$ path/to/llvm-project/llvm/utils/rsp_bisect.py \
+    --test=path/to/test_script --rsp=./foo.rsp --other_rel_path=../buildbad/
+If rsp_bisect is successful, it will print the first file in the rsp file that
+when using the bad build directory's version causes the test script to return a
+different return code. foo.rsp.0 and foo.rsp.1 will also be written. foo.rsp.0
+will be a copy of foo.rsp with the relevant file using the version in
+buildgood/, and foo.rsp.1 will be a copy of foo.rsp with the relevant file
+using the version in buildbad/.
+
+"""
+
+import argparse
+import os
+import subprocess
+import sys
+
+
+def is_path(s):
+  return '/' in s
+
+
+def run_test(test):
+  """Runs the test and returns whether it was successful or not."""
+  return subprocess.run([test], capture_output=True).returncode == 0
+
+
+def modify_rsp(rsp_entries, other_rel_path, modify_after_num):
+  """Create a modified rsp file for use in bisection.
+
+  Returns a new list from rsp.
+  For each file in rsp after the first modify_after_num files, prepend
+  other_rel_path.
+  """
+  ret = []
+  for r in rsp_entries:
+    if is_path(r):
+      if modify_after_num == 0:
+        r = os.path.join(other_rel_path, r)
+      else:
+        modify_after_num -= 1
+    ret.append(r)
+  assert modify_after_num == 0
+  return ret
+
+
+def test_modified_rsp(test, modified_rsp_entries, rsp_path):
+  """Write the rsp file to disk and run the test."""
+  with open(rsp_path, 'w') as f:
+    f.write(' '.join(modified_rsp_entries))
+  return run_test(test)
+
+
+def bisect(test, zero_result, rsp_entries, num_files_in_rsp, other_rel_path, rsp_path):
+  """Bisect over rsp entries.
+
+  Args:
+      zero_result: the test result when modify_after_num is 0.
+
+  Returns:
+      The index of the file in the rsp file where the test result changes.
+  """
+  lower = 0
+  upper = num_files_in_rsp
+  while lower != upper - 1:
+    assert lower < upper - 1
+    mid = int((lower + upper) / 2)
+    assert lower != mid and mid != upper
+    print('Trying {} ({}-{})'.format(mid, lower, upper))
+    result = test_modified_rsp(test, modify_rsp(rsp_entries, other_rel_path, mid),
+                               rsp_path)
+    if zero_result == result:
+      lower = mid
+    else:
+      upper = mid
+  return upper
+
+
+def main():
+  parser = argparse.ArgumentParser()
+  parser.add_argument('--test',
+                      help='Binary to test if current setup is good or bad',
+                      required=True)
+  parser.add_argument('--rsp', help='rsp file', required=True)
+  parser.add_argument(
+      '--other-rel-path',
+      help='Relative path from current build directory to other build ' +
+      'directory, e.g. from "out/Default" to "out/Other" specify "../Other"',
+      required=True)
+  args = parser.parse_args()
+
+  with open(args.rsp, 'r') as f:
+    rsp_entries = f.read()
+  rsp_entries = rsp_entries.split()
+  num_files_in_rsp = sum(1 for a in rsp_entries if is_path(a))
+  if num_files_in_rsp == 0:
+    print('No files in rsp?')
+    return 1
+  print('{} files in rsp'.format(num_files_in_rsp))
+
+  try:
+    print('Initial testing')
+    test0 = test_modified_rsp(args.test, modify_rsp(rsp_entries, args.other_rel_path,
+                                                    0), args.rsp)
+    test_all = test_modified_rsp(
+        args.test, modify_rsp(rsp_entries, args.other_rel_path, num_files_in_rsp),
+        args.rsp)
+
+    if test0 == test_all:
+      print('Test returned same exit code for both build directories')
+      return 1
+
+    print('First build directory returned ' + ('0' if test_all else '1'))
+
+    result = bisect(args.test, test0, rsp_entries, num_files_in_rsp,
+                    args.other_rel_path, args.rsp)
+    print('First file change: {} ({})'.format(
+        list(filter(is_path, rsp_entries))[result - 1], result))
+
+    rsp_out_0 = args.rsp + '.0'
+    rsp_out_1 = args.rsp + '.1'
+    with open(rsp_out_0, 'w') as f:
+      f.write(' '.join(modify_rsp(rsp_entries, args.other_rel_path, result - 1)))
+    with open(rsp_out_1, 'w') as f:
+      f.write(' '.join(modify_rsp(rsp_entries, args.other_rel_path, result)))
+    print('Bisection point rsp files written to {} and {}'.format(
+        rsp_out_0, rsp_out_1))
+  finally:
+    # Always make sure to write the original rsp file contents back so it's
+    # less of a pain to rerun this script.
+    with open(args.rsp, 'w') as f:
+      f.write(' '.join(rsp_entries))
+
+
+if __name__ == '__main__':
+  sys.exit(main())

llvm/utils/rsp_bisect_test/test.py

+#!/usr/bin/env python3
+#===----------------------------------------------------------------------===##
+#
+# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+# See https://llvm.org/LICENSE.txt for license information.
+# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+#
+#===----------------------------------------------------------------------===##
+
+import os
+import subprocess
+import sys
+import tempfile
+
+cur_dir = os.path.dirname(os.path.realpath(__file__))
+bisect_script = os.path.join(cur_dir, "..", "rsp_bisect.py")
+test1 = os.path.join(cur_dir, "test_script.py")
+test2 = os.path.join(cur_dir, "test_script_inv.py")
+rsp = os.path.join(cur_dir, "rsp")
+
+
+def run_bisect(success, test_script):
+  args = [
+      bisect_script, '--test', test_script, '--rsp', rsp, '--other-rel-path',
+      '../Other'
+  ]
+  res = subprocess.run(args, capture_output=True, encoding='UTF-8')
+  if len(sys.argv) > 1 and sys.argv[1] == '-v':
+    print('Ran {} with return code {}'.format(args, res.returncode))
+    print('Stdout:')
+    print(res.stdout)
+    print('Stderr:')
+    print(res.stderr)
+  if res.returncode != (0 if success else 1):
+    print(res.stdout)
+    print(res.stderr)
+    raise AssertionError('unexpected bisection return code for ' + str(args))
+  return res.stdout
+
+
+# Test that an empty rsp file fails.
+with open(rsp, 'w') as f:
+  pass
+
+run_bisect(False, test1)
+
+# Test that an rsp file without any paths fails.
+with open(rsp, 'w') as f:
+  f.write('hello\nfoo\n')
+
+run_bisect(False, test1)
+
+# Test that an rsp file with one path succeeds.
+with open(rsp, 'w') as f:
+  f.write('./foo\n')
+
+output = run_bisect(True, test1)
+assert './foo' in output
+
+# Test that an rsp file with one path and one extra arg succeeds.
+with open(rsp, 'w') as f:
+  f.write('hello\n./foo\n')
+
+output = run_bisect(True, test1)
+assert './foo' in output
+
+# Test that an rsp file with three paths and one extra arg succeeds.
+with open(rsp, 'w') as f:
+  f.write('hello\n./foo\n./bar\n./baz\n')
+
+output = run_bisect(True, test1)
+assert './foo' in output
+
+with open(rsp, 'w') as f:
+  f.write('hello\n./bar\n./foo\n./baz\n')
+
+output = run_bisect(True, test1)
+assert './foo' in output
+
+with open(rsp, 'w') as f:
+  f.write('hello\n./bar\n./baz\n./foo\n')
+
+output = run_bisect(True, test1)
+assert './foo' in output
+
+output = run_bisect(True, test2)
+assert './foo' in output
+
+with open(rsp + '.0', 'r') as f:
+  contents = f.read()
+  assert ' ../Other/./foo' in contents
+
+with open(rsp + '.1', 'r') as f:
+  contents = f.read()
+  assert ' ./foo' in contents
+
+os.remove(rsp)
+os.remove(rsp + '.0')
+os.remove(rsp + '.1')
+
+print('Success!')

llvm/utils/rsp_bisect_test/test_script.py

+#!/usr/bin/env python3
+#===----------------------------------------------------------------------===##
+#
+# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+# See https://llvm.org/LICENSE.txt for license information.
+# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+#
+#===----------------------------------------------------------------------===##
+
+import os
+import sys
+
+rsp_path = os.path.join(os.path.dirname(os.path.realpath(__file__)), "rsp")
+
+with open(rsp_path) as f:
+  contents = f.read()
+  print(contents)
+  success = '../Other/./foo' in contents
+
+sys.exit(0 if success else 1)

llvm/utils/rsp_bisect_test/test_script_inv.py

+#!/usr/bin/env python3
+#===----------------------------------------------------------------------===##
+#
+# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+# See https://llvm.org/LICENSE.txt for license information.
+# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+#
+#===----------------------------------------------------------------------===##
+
+import os
+import sys
+
+rsp_path = os.path.join(os.path.dirname(os.path.realpath(__file__)), "rsp")
+
+with open(rsp_path) as f:
+  success = '../Other/./foo' in f.read()
+
+sys.exit(1 if success else 0)