binary search tool: Fix off by one bug, add stress tests

Revert change that introduced bug when bad item is very last item in
list. Add tests that stress limits of binary search tool and try to look
for these off-by-one errors. Specifically one test checks for the bad
item being in every index of the binary search. Another tests checks for
if every single item is bad.

TEST=Add two new stress tests, run all unit tests

Change-Id: I2d5a0bda035b2c2b4994b0378aa416da19db651d
Reviewed-on: https://chrome-internal-review.googlesource.com/271916
Commit-Ready: Cassidy Burden <cburden@google.com>
Tested-by: Cassidy Burden <cburden@google.com>
Reviewed-by: Caroline Tice <cmtice@google.com>

3 files changed, 89 insertions, 13 deletions

diff --git a/binary_search_tool/binary_search_state.py b/binary_search_tool/binary_search_state.py
index 62acd759..ef276fab 100755
--- a/binary_search_tool/binary_search_state.py
+++ b/binary_search_tool/binary_search_state.py
@@ -222,6 +222,12 @@ class BinarySearchState(object):
       # Prune is set.
       prune_index = self.binary_search.current
 
+      # If found item is last item, no new items can be found
+      if prune_index == len(self.all_items) - 1:
+        self.l.LogOutput('First bad item is the last item. Breaking.')
+        self.l.LogOutput('Bad items are: %s' % self.all_items[-1])
+        break
+
       # If already seen item we have no new bad items to find, finish up
       if self.all_items[prune_index] in self.found_items:
         self.l.LogOutput(('Found item already found before: %s. '
diff --git a/binary_search_tool/test/binary_search_tool_tester.py b/binary_search_tool/test/binary_search_tool_tester.py
index 8488e9e0..4ec920b8 100755
--- a/binary_search_tool/test/binary_search_tool_tester.py
+++ b/binary_search_tool/test/binary_search_tool_tester.py
@@ -336,6 +336,60 @@ class BisectingUtilsTest(unittest.TestCase):
     self.assertEqual(actual_result, expected_result)
 
 
+class BisectStressTest(unittest.TestCase):
+  """Stress tests for bisecting tool."""
+
+  def test_every_obj_bad(self):
+    amt = 25
+    gen_obj.Main(['--obj_num', str(amt), '--bad_obj_num', str(amt)])
+    ret = binary_search_state.Run(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=True,
+                                  file_args=True,
+                                  verify_level=0)
+    self.assertEquals(ret, 0)
+    self.check_output()
+
+  def test_every_index_is_bad(self):
+    amt = 25
+    for i in range(amt):
+      obj_list = ['0'] * amt
+      obj_list[i] = '1'
+      obj_list = ','.join(obj_list)
+      gen_obj.Main(['--obj_list', obj_list])
+      ret = binary_search_state.Run(get_initial_items='./gen_init_list.py',
+                                    switch_to_good='./switch_to_good.py',
+                                    switch_to_bad='./switch_to_bad.py',
+                                    install_script='./install.py',
+                                    test_script='./is_good.py',
+                                    prune=True,
+                                    file_args=True)
+      self.assertEquals(ret, 0)
+      self.check_output()
+
+
+  def check_output(self):
+    _, out, _ = command_executer.GetCommandExecuter().RunCommandWOutput(
+        ('grep "Bad items are: " logs/binary_search_tool_tester.py.out | '
+         'tail -n1'))
+    ls = out.splitlines()
+    self.assertEqual(len(ls), 1)
+    line = ls[0]
+
+    _, _, bad_ones = line.partition('Bad items are: ')
+    bad_ones = bad_ones.split()
+    expected_result = common.ReadObjectsFile()
+
+    # Reconstruct objects file from bad_ones and compare
+    actual_result = [0] * len(expected_result)
+    for bad_obj in bad_ones:
+      actual_result[int(bad_obj)] = 1
+
+    self.assertEqual(actual_result, expected_result)
+
+
 def Main(argv):
   num_tests = 2
   if len(argv) > 1:
@@ -357,6 +411,8 @@ def Main(argv):
   suite.addTest(BisectingUtilsTest('test_set_file'))
   suite.addTest(BisectingUtilsTest('test_noincremental_prune'))
   suite.addTest(BisectTest('test_full_bisector'))
+  suite.addTest(BisectStressTest('test_every_obj_bad'))
+  suite.addTest(BisectStressTest('test_every_index_is_bad'))
   runner = unittest.TextTestRunner()
   runner.run(suite)
 
diff --git a/binary_search_tool/test/gen_obj.py b/binary_search_tool/test/gen_obj.py
index 6fb9a908..1c060e01 100755
--- a/binary_search_tool/test/gen_obj.py
+++ b/binary_search_tool/test/gen_obj.py
@@ -40,23 +40,34 @@ def Main(argv):
                       help=('Number of bad objects. Must be great than or '
                             'equal to zero and less than total object '
                             'number.'))
+  parser.add_argument('-o',
+                      '--obj_list',
+                      dest='obj_list',
+                      default='',
+                      help=('List of comma seperated objects to generate. '
+                            'A 0 means the object is good, a 1 means the '
+                            'object is bad.'))
   options = parser.parse_args(argv)
 
   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
+  obj_list = options.obj_list
+  if not obj_list:
+    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
+  else:
+    obj_list = obj_list.split(',')
 
   if os.path.isfile(common.OBJECTS_FILE):
     os.remove(common.OBJECTS_FILE)
@@ -70,8 +81,11 @@ def Main(argv):
     w.write('{0}\n'.format(i))
   f.close()
 
+  obj_num = len(obj_list)
+  bad_obj_num = obj_list.count('1')
   print('Generated {0} object files, with {1} bad ones.'.format(
-      options.obj_num, options.bad_obj_num))
+      obj_num, bad_obj_num))
+
 
   return 0