Move binary search tool to toolchain-utils with a comprehensive test suite.

We now can test the binary search tool with -
  ./binary_search_tool_tester.py
This will generate a set of object files with some bad ones, and call
the binary search tool to find them out.

TEST=gpylint and passed my test suite
BUG=None

Change-Id: I56fbda7f75fe3bc239e456161c48b7611c3a315d
Reviewed-on: https://chrome-internal-review.googlesource.com/150255
Reviewed-by: Luis Lozano <llozano@chromium.org>
Commit-Queue: Han Shen <shenhan@google.com>
Tested-by: Han Shen <shenhan@google.com>

8 files changed, 277 insertions, 0 deletions

diff --git a/binary_search_tool/test/__init__.py b/binary_search_tool/test/__init__.py
new file mode 100755
index 00000000..e69de29b
--- /dev/null
+++ b/binary_search_tool/test/__init__.py
diff --git a/binary_search_tool/test/binary_search_tool_tester.py b/binary_search_tool/test/binary_search_tool_tester.py
new file mode 100755
index 00000000..211c16f2
--- /dev/null
+++ b/binary_search_tool/test/binary_search_tool_tester.py
@@ -0,0 +1,71 @@
+#!/usr/bin/python
+
+# Copyright 2012 Google Inc. All Rights Reserved.
+
+"""Tests for bisecting tool."""
+
+__author__ = 'shenhan@google.com (Han Shen)'
+
+import os
+import random
+import sys
+import unittest
+
+from utils import command_executer
+from binary_search_tool import binary_search_state
+
+import common
+import gen_obj
+
+
+class BisectingUtilsTest(unittest.TestCase):
+
+  def setUp(self):
+    """Generate [100-1000] object files, and 1-5% of which are bad ones."""
+    obj_num = random.randint(100, 1000)
+    bad_obj_num = random.randint(obj_num / 100, obj_num / 20)
+    if bad_obj_num == 0:
+      bad_obj_num = 1
+    gen_obj.Main(['--obj_num', str(obj_num), '--bad_obj_num', str(bad_obj_num)])
+
+  def tearDown(self):
+    """Cleanup temp files."""
+    os.remove(common.OBJECTS_FILE)
+    os.remove(common.WORKING_SET_FILE)
+    print 'Deleted "{0}" and "{1}"'.format(
+        common.OBJECTS_FILE, common.WORKING_SET_FILE)
+
+  def runTest(self):
+    args = ['--get_initial_items', './gen_init_list.py',
+            '--switch_to_good', './switch_to_good.py',
+            '--switch_to_bad', './switch_to_bad.py',
+            '--test_script', './is_good.py',
+            '--prune', '--file_args']
+    binary_search_state.Main(args)
+
+    _, out, _ = command_executer.GetCommandExecuter().RunCommand(
+        'tail -n 10 logs/binary_search_state.py.out', return_output=True)
+    ls = out.splitlines()
+    for l in ls:
+      t = l.find('Bad items are: ')
+      if t > 0:
+        bad_ones = l[(t + len('Bad items are: ')):].split()
+        objects_file = common.ReadObjectsFile()
+        for b in bad_ones:
+          self.assertEqual(objects_file[int(b)], 1)
+
+
+def Main(argv):
+  num_tests = 2
+  if len(argv) > 1:
+    num_tests = int(argv[1])
+
+  suite = unittest.TestSuite()
+  for _ in range(0, num_tests):
+    suite.addTest(BisectingUtilsTest())
+  runner = unittest.TextTestRunner()
+  runner.run(suite)
+
+
+if __name__ == '__main__':
+  Main(sys.argv)
diff --git a/binary_search_tool/test/common.py b/binary_search_tool/test/common.py
new file mode 100755
index 00000000..c0e1a3b3
--- /dev/null
+++ b/binary_search_tool/test/common.py
@@ -0,0 +1,39 @@
+#!/usr/bin/python
+
+DEFAULT_OBJECT_NUMBER = 1238
+DEFAULT_BAD_OBJECT_NUMBER = 23
+OBJECTS_FILE = 'objects.txt'
+WORKING_SET_FILE = 'working_set.txt'
+
+def ReadWorkingSet():
+  working_set = []
+  f = open(WORKING_SET_FILE, 'r')
+  for l in f:
+    working_set.append(int(l))
+  f.close()
+  return working_set
+
+
+def WriteWorkingSet(working_set):
+  f = open(WORKING_SET_FILE, 'w')
+  for o in working_set:
+    f.write('{0}\n'.format(o))
+  f.close()
+
+
+def ReadObjectsFile():
+  objects_file = []
+  f = open(OBJECTS_FILE, 'r')
+  for l in f:
+    objects_file.append(int(l))
+  f.close()
+  return objects_file
+
+
+def ReadObjectIndex(filename):
+  object_index = []
+  f = open(filename, 'r')
+  for o in f:
+    object_index.append(int(o))
+  f.close()
+  return object_index
diff --git a/binary_search_tool/test/gen_init_list.py b/binary_search_tool/test/gen_init_list.py
new file mode 100755
index 00000000..ce72d632
--- /dev/null
+++ b/binary_search_tool/test/gen_init_list.py
@@ -0,0 +1,20 @@
+#!/usr/bin/python
+"""Prints out index for every object file, starting from 0."""
+
+import sys
+
+from utils import command_executer
+import common
+
+
+def Main():
+  ce = command_executer.GetCommandExecuter()
+  _, l, _ = ce.RunCommand('cat {0} | wc -l'.format(common.OBJECTS_FILE),
+                          return_output=True, print_to_console=False)
+  for i in range(0, int(l)):
+    print i
+
+
+if __name__ == '__main__':
+  Main()
+  sys.exit(0)
diff --git a/binary_search_tool/test/gen_obj.py b/binary_search_tool/test/gen_obj.py
new file mode 100755
index 00000000..3d1e32f9
--- /dev/null
+++ b/binary_search_tool/test/gen_obj.py
@@ -0,0 +1,74 @@
+#!/usr/bin/python
+"""Script to generate a list of object files.
+
+0 represents a good object file.
+1 represents a bad object file.
+"""
+
+import optparse
+import os
+import random
+import sys
+
+import common
+
+
+def Main(argv):
+  """Generates a list, the value of each element is 0 or 1.
+
+  The number of 1s in the list is specified by bad_obj_num.
+  The others are all 0s. The total number of 0s and 1s is specified by obj_num.
+
+  Args:
+    argv: argument from command line
+  Returns:
+    0 always.
+  """
+  parser = optparse.OptionParser()
+  parser.add_option('-n', '--obj_num', dest='obj_num',
+                    default=common.DEFAULT_OBJECT_NUMBER,
+                    help=('Number of total objects.'))
+  parser.add_option('-b', '--bad_obj_num', dest='bad_obj_num',
+                    default=common.DEFAULT_BAD_OBJECT_NUMBER,
+                    help=('Number of bad objects. Must be great than or equal '
+                          'to zero and less than total object number.'))
+  options = parser.parse_args(argv)[0]
+
+  obj_num = int(options.obj_num)
+  bad_obj_num = int(options.bad_obj_num)
+  bad_to_gen = int(options.bad_obj_num)
+  obj_list = []
+  for i in range(obj_num):
+    if (bad_to_gen > 0 and
+        random.randint(1, obj_num) <= bad_obj_num):
+      obj_list.append(1)
+      bad_to_gen -= 1
+    else:
+      obj_list.append(0)
+  while bad_to_gen > 0:
+    t = random.randint(0, obj_num - 1)
+    if obj_list[t] == 0:
+      obj_list[t] = 1
+      bad_to_gen -= 1
+
+  if os.path.isfile(common.OBJECTS_FILE):
+    os.remove(common.OBJECTS_FILE)
+  if os.path.isfile(common.WORKING_SET_FILE):
+    os.remove(common.WORKING_SET_FILE)
+
+  f = open(common.OBJECTS_FILE, 'w')
+  w = open(common.WORKING_SET_FILE, 'w')
+  for i in obj_list:
+    f.write('{0}\n'.format(i))
+    w.write('{0}\n'.format(i))
+  f.close()
+
+  print 'Generated {0} object files, with {1} bad ones.'.format(
+      options.obj_num, options.bad_obj_num)
+
+  return 0
+
+
+if __name__ == '__main__':
+  retval = Main(sys.argv)
+  sys.exit(retval)
diff --git a/binary_search_tool/test/is_good.py b/binary_search_tool/test/is_good.py
new file mode 100755
index 00000000..60b2b50d
--- /dev/null
+++ b/binary_search_tool/test/is_good.py
@@ -0,0 +1,20 @@
+#!/usr/bin/python
+"""Check to see if the working set produces a good executable."""
+
+import sys
+
+import common
+
+
+def Main():
+  working_set = common.ReadWorkingSet()
+  for w in working_set:
+    if w == 1:
+      return 1  ## False, linking failure
+  return 0
+
+
+if __name__ == '__main__':
+  retval = Main()
+  sys.exit(retval)
+
diff --git a/binary_search_tool/test/switch_to_bad.py b/binary_search_tool/test/switch_to_bad.py
new file mode 100755
index 00000000..b253eb87
--- /dev/null
+++ b/binary_search_tool/test/switch_to_bad.py
@@ -0,0 +1,25 @@
+#!/usr/bin/python
+"""Switch part of the objects file in working set to (possible) bad ones."""
+
+import sys
+
+import common
+
+
+def Main(argv):
+  """Switch part of the objects file in working set to (possible) bad ones."""
+  working_set = common.ReadWorkingSet()
+  objects_file = common.ReadObjectsFile()
+  object_index = common.ReadObjectIndex(argv[1])
+
+  for oi in object_index:
+    working_set[oi] = objects_file[oi]
+
+  common.WriteWorkingSet(working_set)
+
+  return 0
+
+
+if __name__ == '__main__':
+  retval = Main(sys.argv)
+  sys.exit(retval)
diff --git a/binary_search_tool/test/switch_to_good.py b/binary_search_tool/test/switch_to_good.py
new file mode 100755
index 00000000..71180e1e
--- /dev/null
+++ b/binary_search_tool/test/switch_to_good.py
@@ -0,0 +1,28 @@
+#!/usr/bin/python
+"""Change portions of the object files to good.
+
+The "portion" is defined by the file (which is passed as the only argument to
+this script) content. Every line in the file is an object index, which will be
+set to good (mark as 0).
+"""
+
+import sys
+
+import common
+
+
+def Main(argv):
+  working_set = common.ReadWorkingSet()
+  object_index = common.ReadObjectIndex(argv[1])
+
+  for oi in object_index:
+    working_set[int(oi)] = 0
+
+  common.WriteWorkingSet(working_set)
+
+  return 0
+
+
+if __name__ == '__main__':
+  retval = Main(sys.argv)
+  sys.exit(retval)