Bisection debugging helper script

pydir/bisection-tool.py

Index: pydir/bisection-tool.py
diff --git a/pydir/bisection-tool.py b/pydir/bisection-tool.py
new file mode 100755
index 0000000000000000000000000000000000000000..6e6c6662f4b09ba4a421440fcf77dc59fe41f135
--- /dev/null
+++ b/pydir/bisection-tool.py
@@ -0,0 +1,201 @@
+#!/usr/bin/env python2
+
+import argparse
+import math
+import os
+import re
+import signal
+import subprocess
+
+class Runner(object):
+  def __init__(self, input_cmd, timeout, comma_join, template, find_all):
+    self._input_cmd = input_cmd
+    self._timeout = timeout
+    self._num_tries = 0
+    self._comma_join = comma_join
+    self._template = template
+    self._find_all = find_all
+
+  def estimate(self, included_ranges):
+    result = 0
+    for i in included_ranges:
+      if isinstance(i, int):
+        result += 1
+      else:
+        if i[1] - i[0] > 2:
+          result += int(math.log(i[1] - i[0], 2))
+        else:
+          result += (i[1] - i[0])
+    if self._find_all:
+      return 2 * result
+    else:
+      return result
+
+  def Run(self, included_ranges):
+    def timeout_handler(signum, frame):
+      raise RuntimeError('Timeout')
+
+    self._num_tries += 1
+    cmd_addition = ''
+    for i in included_ranges:
+      if isinstance(i, int):
+        range_str = str(i)
+      else:
+        range_str = '{start}:{end}'.format(start=i[0], end=i[1])
+      if self._comma_join:
+        cmd_addition += ',' + range_str
+      else:
+        cmd_addition += ' -i ' + range_str
+
+    if self._template:
+      cmd = cmd_addition.join(re.split(r'%i' ,self._input_cmd))
+    else:
+      cmd = self._input_cmd + cmd_addition
+
+    print cmd
+    p = subprocess.Popen(cmd, shell = True, cwd = None,
+      stdout = subprocess.PIPE, stderr = subprocess.PIPE, env = None)
+    if self._timeout != -1:
+      signal.signal(signal.SIGALRM, timeout_handler)
+      signal.alarm(self._timeout)
+
+    try:
+      _, _ = p.communicate()
+      if self._timeout != -1:
+        signal.alarm(0)
+    except:
+      try:
+        os.kill(p.pid, signal.SIGKILL)
+      except OSError:
+        pass
+      print 'Timeout'
+      return -9
+    print '===Return Code===: ' + str(p.returncode)
+    print '===Remaining Steps (approx)===: ' \
+      + str(self.estimate(included_ranges))
+    return p.returncode
+
+def flatten(tree):
+  if isinstance(tree, list):
+    result = []
+    for node in tree:
+      result.extend(flatten(node))
+    return result
+  else:
+    return [tree] # leaf
+
+def find_failures(runner, current_interval, include_ranges, find_all):
+  if current_interval[0] == current_interval[1]:
+    return []
+  mid = (current_interval[0] + current_interval[1]) / 2
+
+  first_half = (current_interval[0], mid)
+  second_half = (mid, current_interval[1])
+
+  exit_code_2 = 0
+
+  exit_code_1 = runner.Run([first_half] + include_ranges)
+  if find_all or exit_code_1 == 0:
+    exit_code_2 = runner.Run([second_half] + include_ranges)
+
+  if exit_code_1 == 0 and exit_code_2 == 0:
+    # Whole range fails but both halves pass
+    # So, some conjunction of functions cause a failure, but none individually.
+    partial_result = flatten(find_failures(runner, first_half, [second_half]
+                             + include_ranges, find_all))
+    # Heavy list concatenation, but this is insignificant compared to the
+    # process run times
+    partial_result.extend(flatten(find_failures(runner, second_half,
+                          partial_result + include_ranges, find_all)))
+    return [partial_result]
+  else:
+    result = []
+    if exit_code_1 != 0:
+      if first_half[1] == first_half[0] + 1:
+        result.append(first_half[0])
+      else:
+        result.extend(find_failures(runner, first_half,
+                                     include_ranges, find_all))
+    if exit_code_2 != 0:
+      if second_half[1] == second_half[0] + 1:
+        result.append(second_half[0])
+      else:
+        result.extend(find_failures(runner, second_half,
+                                     include_ranges, find_all))
+    return result
+
+
+def main():
+  '''
+  Helper Script for Automating Bisection Debugging
+
+  Example Invocation:
+  bisection-tool.py --cmd 'bisection-test.py -c 2x3' --end 1000 --timeout 60
+
+  This will invoke 'bisection-test.py -c 2x3' starting with the range -i 0:1000
+  If that fails, it will subdivide the range (initially 0:500 and 500:1000)
+  recursively to pinpoint a combination of singletons that are needed to cause
+  the input to return a non zero exit code or timeout.
+
+  For investigating an error in the generated code:
+  bisection-tool.py --cmd './pydir/szbuild_spec2k.py --run 188.ammp'
+
+  For Subzero itself crashing,
+  bisection-tool.py --cmd 'pnacl-sz -translate-only=' --comma-join=1
+  The --comma-join flag ensures the ranges are formatted in the manner pnacl-sz
+  expects.
+
+  If the range specification is not to be appended on the input:
+  bisection-tool.py --cmd 'echo %i; cmd-main %i; cmd-post' --template=1
+
+  '''
+  argparser = argparse.ArgumentParser(main.__doc__)
+  argparser.add_argument('--cmd', required=True,  dest='cmd',
+                           help='Runnable command')
+
+  argparser.add_argument('--start', dest='start', default=0,
+                           help='Start of initial range')
+
+  argparser.add_argument('--end', dest='end', default=50000,
+                           help='End of initial range')
+
+  argparser.add_argument('--timeout', dest='timeout', default=60,
+                           help='Timeout for each invocation of the input')
+
+  argparser.add_argument('--all', type=int, choices=[0,1], default=1,
+                           dest='all', help='Find all failures')
+
+  argparser.add_argument('--comma-join', type=int, choices=[0,1], default=0,
+                           dest='comma_join', help='Use comma to join ranges')
+
+  argparser.add_argument('--template', type=int, choices=[0,1], default=0,
+                           dest='template',
+                           help='Replace %%i in the cmd string with the ranges')
+
+
+  args = argparser.parse_args()
+
+  fail_list = []
+
+  initial_range = (int(args.start), int(args.end))
+  timeout = int(args.timeout)
+  runner = Runner(args.cmd, timeout, args.comma_join, args.template, args.all)
+  if runner.Run([initial_range]) != 0:
+    fail_list = find_failures(runner, initial_range, [], args.all)
+  else:
+    print 'Pass'
+    # The whole input range works, maybe check subzero build flags?
+    # Also consider widening the initial range (control with --start and --end)
+
+  if fail_list:
+    print 'Failing Items:'
+    for fail in fail_list:
+      if isinstance(fail, list):
+        fail.sort()
+        print '[' + ','.join(str(x) for x in fail) + ']'
+      else:
+        print fail
+  print 'Number of tries: ' + str(runner._num_tries)
+
+if __name__ == '__main__':
+  main()