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..dab5e12c426aa8fd4d6f2973266925b9996ee73f
--- /dev/null
+++ b/pydir/bisection-tool.py
@@ -0,0 +1,198 @@
+#!/usr/bin/env python2
+
+import argparse
+import os
+import signal
+import subprocess
+import re
+import math
+
+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")

[Jim Stichnoth, 2016/07/22 13:35:43]

For whatever reason, our scripts prefer 'strings' rather than "strings".

[manasijm, 2016/07/22 15:53:09]

Done.

+
+    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===: " + str(self.estimate(included_ranges))

[Jim Stichnoth, 2016/07/22 13:35:43]

Should probably rephrase the message to convey that it is not an exact step
count.  E.g.
  '===Remaining Steps (approx)===:'

[manasijm, 2016/07/22 15:53:09]

Done.

+    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_crashes(runner, current_interval, include_ranges, find_all):

[Jim Stichnoth, 2016/07/22 13:35:43]

Maybe find_failures?  It finds more than just crashes.

[manasijm, 2016/07/22 15:53:09]

Done.

+  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_crashes(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_crashes(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_crashes(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_crashes(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,

[Jim Stichnoth, 2016/07/22 13:35:42]

Capitalize Subzero

[manasijm, 2016/07/22 15:53:09]

Done.

+  bisection-tool.py --cmd 'pnacl-sz  -translate-only=' --comma-join

[Jim Stichnoth, 2016/07/22 13:35:42]

I think there should be only a single space character after 'pnacl-sz'.

[manasijm, 2016/07/22 15:53:09]

Done.

+  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
+
+  """
+  argparser = argparse.ArgumentParser(main.__doc__)
+  argparser.add_argument('--cmd', required=True,
+                           dest='cmd',

[Jim Stichnoth, 2016/07/22 13:35:43]

Probably append this line to the previous line.

[manasijm, 2016/07/22 15:53:09]

Done.

+                           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', dest='all', action='store_true')

[Jim Stichnoth, 2016/07/22 13:35:42]

Instead of --all and --no-all, you could do something like:

  add_argument('--all', type=int, choices=[0,1], default=1)

This allows:
  --all
  --all=1
  --all=0
and reduces the number of args.

Same for comma-join/separate and template/no-template.

This is what's currently done for 'szbuild.py --force'.

[Jim Stichnoth, 2016/07/22 13:35:43]

All of these args should have help strings.

[manasijm, 2016/07/22 15:53:09]

Done.

+  argparser.add_argument('--no-all', dest='all', action='store_false')
+  argparser.set_defaults(all=True)
+
+  argparser.add_argument('--comma-join', dest='comma_join', action='store_true')
+  argparser.add_argument('--separate', dest='comma_join', action='store_false')
+  argparser.set_defaults(comma_join=False)
+
+  argparser.add_argument('--template', dest='template', action='store_true')
+  argparser.add_argument('--no-template', dest='template', action='store_false')
+  argparser.set_defaults(template=False)
+
+  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_crashes(runner, initial_range, [], args.all)
+  else:
+    print "Pass" # The whole input range works, maybe check subzero build flags?

[Jim Stichnoth, 2016/07/22 13:35:43]

Another possibility is (if you expected it not to pass) is that you should
increase the --end value (if bisecting per-instruction or per-variable
transformations on a large function).

[manasijm, 2016/07/22 15:53:09]

Done.

+
+  if fail_list:
+    print "Failing Functions:"

[Jim Stichnoth, 2016/07/22 13:35:43]

Here and in the comment above, we aren't necessarily talking about functions. 
Maybe "items"?

[manasijm, 2016/07/22 15:53:09]

Done.

+    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)
+  # TODO(manasijm): Pretty print, associate these numbers with filenames

[Jim Stichnoth, 2016/07/22 13:35:43]

I don't think you need this TODO, since this utility is now more general than
just szbuild.py-style "-i" functionality.

[manasijm, 2016/07/22 15:53:09]

Done.

+
+if __name__ == '__main__':
+    main()

[Jim Stichnoth, 2016/07/22 13:35:43]

Indent this only 2 characters?

[manasijm, 2016/07/22 15:53:09]

Done.