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>

12 files changed, 1026 insertions, 0 deletions

diff --git a/binary_search_tool/.gitignore b/binary_search_tool/.gitignore
new file mode 100644
index 00000000..e4b79a81
--- /dev/null
+++ b/binary_search_tool/.gitignore
@@ -0,0 +1,5 @@
+log
+*.pyc
+working_set.txt
+objects.txt
+
diff --git a/binary_search_tool/__init__.py b/binary_search_tool/__init__.py
new file mode 100755
index 00000000..e69de29b
--- /dev/null
+++ b/binary_search_tool/__init__.py
diff --git a/binary_search_tool/binary_search_perforce.py b/binary_search_tool/binary_search_perforce.py
new file mode 100755
index 00000000..3bfa2b12
--- /dev/null
+++ b/binary_search_tool/binary_search_perforce.py
@@ -0,0 +1,410 @@
+import math
+import optparse
+import os
+import re
+import subprocess
+import sys
+import tempfile
+
+from utils import command_executer
+from utils import logger
+from utils import misc
+
+def _GetP4ClientSpec(client_name, p4_paths):
+  p4_string = ""
+  for p4_path in p4_paths:
+    if " " not in p4_path:
+      p4_string += " -a %s" % p4_path
+    else:
+      p4_string += " -a \"" + (" //" + client_name + "/").join(p4_path) + "\""
+
+  return p4_string
+
+
+def GetP4Command(client_name, p4_port, p4_paths, revision, checkoutdir, p4_snapshot=""):
+  command = ""
+
+  if p4_snapshot:
+    command += "mkdir -p " + checkoutdir
+    for p4_path in p4_paths:
+      real_path = p4_path[1]
+      if real_path.endswith("..."):
+        real_path = real_path.replace("/...", "")
+        command += ("; mkdir -p " + checkoutdir + "/" +
+                    os.path.dirname(real_path))
+        command += ("&& rsync -lr " + p4_snapshot + "/" + real_path +
+                  " " + checkoutdir + "/" + os.path.dirname(real_path))
+    return command
+
+  command += " export P4CONFIG=.p4config"
+  command += " && mkdir -p " + checkoutdir
+  command += " && cd " + checkoutdir
+  command += " && cp ${HOME}/.p4config ."
+  command += " && chmod u+w .p4config"
+  command += " && echo \"P4PORT=" + p4_port + "\" >> .p4config"
+  command += " && echo \"P4CLIENT=" + client_name + "\" >> .p4config"
+  command += (" && g4 client " +
+              _GetP4ClientSpec(client_name, p4_paths))
+  command += " && g4 sync "
+  command += " && cd -"
+  return command
+
+class BinarySearchPoint:
+  def __init__(self, revision, status, tag=None):
+    self.revision = revision
+    self.status = status
+    self.tag = tag
+
+class BinarySearcher:
+  def __init__(self):
+    self.sorted_list = []
+    self.index_log = []
+    self.status_log = []
+    self.skipped_indices = []
+    self.current = 0
+    self.points = {}
+    pass
+
+  def SetSortedList(self, sorted_list):
+    assert(len(sorted_list) > 0)
+    self.sorted_list = sorted_list
+    self.index_log = []
+    self.hi = len(sorted_list) - 1
+    self.lo = 0
+    self.points = {}
+    for i in range(len(self.sorted_list)):
+      bsp = BinarySearchPoint(self.sorted_list[i], -1, "Not yet done.")
+      self.points[i] = bsp
+
+  def SetStatus(self, status, tag=None):
+    message = ("Revision: %s index: %d returned: %d" %
+               (self.sorted_list[self.current],
+                self.current,
+                status))
+    logger.GetLogger().LogOutput(message)
+    assert(status == 0 or status == 1 or status == 2)
+    self.index_log.append(self.current)
+    self.status_log.append(status)
+    bsp = BinarySearchPoint(self.sorted_list[self.current], status, tag)
+    self.points[self.current] = bsp
+
+    if status == 2:
+      self.skipped_indices.append(self.current)
+
+    if status == 0 or status == 1:
+      if status == 0:
+        self.lo = self.current + 1
+      elif status == 1:
+        self.hi = self.current
+      logger.GetLogger().LogOutput("lo: %d hi: %d\n" % (self.lo, self.hi))
+      self.current = (self.lo + self.hi)/2
+
+    if self.lo == self.hi:
+      message = ("Search complete. First bad version: %s"
+                  " at index: %d" %
+                  (self.sorted_list[self.current],
+                   self.lo))
+      logger.GetLogger().LogOutput(message)
+      return True
+
+    for index in range(self.lo, self.hi):
+      if index not in self.skipped_indices:
+        return False
+    logger.GetLogger().LogOutput(
+        "All skipped indices between: %d and %d\n" % (self.lo, self.hi))
+    return True
+
+  # Does a better job with chromeos flakiness.
+  def GetNextFlakyBinary(self):
+    t = (self.lo, self.current, self.hi)
+    q = [t]
+    while len(q):
+      element = q.pop(0)
+      if element[1] in self.skipped_indices:
+        # Go top
+        to_add = (element[0], (element[0] + element[1]) / 2, element[1])
+        q.append(to_add)
+        # Go bottom
+        to_add = (element[1], (element[1] + element[2]) / 2, element[2])
+        q.append(to_add)
+      else:
+        self.current = element[1]
+        return
+    assert len(q), "Queue should never be 0-size!"
+
+  def GetNextFlakyLinear(self):
+      current_hi = self.current
+      current_lo = self.current
+      while True:
+        if current_hi < self.hi and current_hi not in self.skipped_indices:
+          self.current = current_hi
+          break
+        if current_lo >= self.lo and current_lo not in self.skipped_indices:
+          self.current = current_lo
+          break
+        if current_lo < self.lo and current_hi >= self.hi:
+          break
+
+        current_hi += 1
+        current_lo -= 1
+
+  def GetNext(self):
+    self.current = (self.hi + self.lo) / 2
+    # Try going forward if current is skipped.
+    if self.current in self.skipped_indices:
+      self.GetNextFlakyBinary()
+
+    # TODO: Add an estimated time remaining as well.
+    message = ("Estimated tries: min: %d max: %d\n" %
+               (1 + math.log(self.hi - self.lo, 2),
+                self.hi - self.lo - len(self.skipped_indices)))
+    logger.GetLogger().LogOutput(message)
+    message = ("lo: %d hi: %d current: %d version: %s\n" %
+               (self.lo, self.hi, self.current,
+                self.sorted_list[self.current]))
+    logger.GetLogger().LogOutput(message)
+    logger.GetLogger().LogOutput(str(self))
+    return self.sorted_list[self.current]
+
+  def SetLoRevision(self, lo_revision):
+    self.lo = self.sorted_list.index(lo_revision)
+  def SetHiRevision(self, hi_revision):
+    self.hi = self.sorted_list.index(hi_revision)
+  def GetAllPoints(self):
+    to_return = ""
+    for i in range(len(self.sorted_list)):
+      to_return += ("%d %d %s\n" %
+                    (self.points[i].status,
+                     i,
+                     self.points[i].revision))
+
+    return to_return
+  def __str__(self):
+    to_return = ""
+    to_return += "Current: %d\n" % self.current
+    to_return += str(self.index_log) + "\n"
+    revision_log = []
+    for index in self.index_log:
+      revision_log.append(self.sorted_list[index])
+    to_return += str(revision_log) + "\n"
+    to_return += str(self.status_log) + "\n"
+    to_return += "Skipped indices:\n"
+    to_return += str(self.skipped_indices) + "\n"
+    to_return += self.GetAllPoints()
+    return to_return
+
+class RevisionInfo:
+  def __init__(self, date, client, description):
+    self.date = date
+    self.client = client
+    self.description = description
+    self.status = -1
+
+class VCSBinarySearcher:
+  def __init__(self):
+    self.bs = BinarySearcher()
+    self.rim = {}
+    self.current_ce = None
+    self.checkout_dir = None
+    self.current_revision = None
+    pass
+  def Initialize(self):
+    pass
+  def GetNextRevision(self):
+    pass
+  def CheckoutRevision(self, revision):
+    pass
+  def SetStatus(self, status):
+    pass
+  def Cleanup(self):
+    pass
+  def SetGoodRevision(self, revision):
+    if revision is None:
+      return
+    assert(revision in self.bs.sorted_list)
+    self.bs.SetLoRevision(revision)
+  def SetBadRevision(self, revision):
+    if revision is None:
+      return
+    assert(revision in self.bs.sorted_list)
+    self.bs.SetHiRevision(revision)
+
+class P4BinarySearcher(VCSBinarySearcher):
+  def __init__(self, p4_port, p4_paths, test_command):
+    VCSBinarySearcher.__init__(self)
+    self.p4_port = p4_port
+    self.p4_paths = p4_paths
+    self.test_command = test_command
+    self.checkout_dir = tempfile.mkdtemp()
+    self.ce = command_executer.GetCommandExecuter()
+    self.client_name = "binary-searcher-$HOSTNAME-$USER"
+    self.job_log_root = "/home/asharif/www/coreboot_triage/"
+  def Initialize(self, good_revision=None, bad_revision=None):
+    self.Cleanup()
+    command = GetP4Command(self.client_name, self.p4_port, self.p4_paths, 1, self.checkout_dir)
+    self.ce.RunCommand(command)
+    command = "cd %s && g4 changes ..." % self.checkout_dir
+    [retval, out, err] = self.ce.RunCommand(command, True)
+    self.changes = re.findall("Change (\d+)", out)
+    change_infos = re.findall("Change (\d+) on ([\d/]+) by ([^\s]+) ('[^']*')", out)
+    for change_info in change_infos:
+      ri = RevisionInfo(change_info[1], change_info[2], change_info[3])
+      self.rim[change_info[0]] = ri
+    # g4 gives changes in reverse chronological order.
+    self.changes.reverse()
+    self.bs.SetSortedList(self.changes)
+  def SetStatus(self, status):
+    self.rim[self.current_revision].status = status
+    return self.bs.SetStatus(status)
+  def GetNextRevision(self):
+    next_revision = self.bs.GetNext()
+    self.current_revision = next_revision
+    return next_revision
+  def CleanupCLs(self):
+    if not os.path.isfile(self.checkout_dir + "/.p4config"):
+      command = "cd %s" % self.checkout_dir
+      command += " && cp ${HOME}/.p4config ."
+      command += " && echo \"P4PORT=" + self.p4_port + "\" >> .p4config"
+      command += " && echo \"P4CLIENT=" + self.client_name + "\" >> .p4config"
+      self.ce.RunCommand(command)
+    command = "cd %s" % self.checkout_dir
+    command += "; g4 changes -c %s" % self.client_name
+    [retval, out, err] = self.ce.RunCommand(command, True)
+    changes = re.findall("Change (\d+)", out)
+    if len(changes) != 0:
+      command = "cd %s" % self.checkout_dir
+      for change in changes:
+        command += "; g4 revert -c %s" % change
+      self.ce.RunCommand(command)
+
+  def CleanupClient(self):
+    command = "cd %s" % self.checkout_dir
+    command += "; g4 revert ..."
+    command += "; g4 client -d %s" % self.client_name
+    self.ce.RunCommand(command)
+
+  def Cleanup(self):
+    self.CleanupCLs()
+    self.CleanupClient()
+
+  def __str__(self):
+    to_return = ""
+    for change in self.changes:
+      ri = self.rim[change]
+      if ri.status == -1:
+        to_return = "%s\t%d\n" % (change, ri.status)
+      else:
+        to_return += ("%s\t%d\t%s\t%s\t%s\t%s\t%s\t%s\n" %
+               (change,
+                ri.status,
+                ri.date,
+                ri.client,
+                ri.description,
+                self.job_log_root + change + ".cmd",
+                self.job_log_root + change + ".out",
+                self.job_log_root + change + ".err"))
+    return to_return
+
+
+
+class P4GCCBinarySearcher(P4BinarySearcher):
+  # TODO: eventually get these patches from g4 instead of creating them manually
+  def HandleBrokenCLs(self, current_revision):
+    cr = int(current_revision)
+    problematic_ranges = []
+    problematic_ranges.append([44528, 44539])
+    problematic_ranges.append([44528, 44760])
+    problematic_ranges.append([44335, 44882])
+    command = "pwd"
+    for pr in problematic_ranges:
+      if cr in range(pr[0], pr[1]):
+        patch_file = "/home/asharif/triage_tool/%d-%d.patch" % (pr[0], pr[1])
+        f = open(patch_file)
+        patch = f.read()
+        f.close()
+        files = re.findall("--- (//.*)", patch)
+        command += "; cd %s" % self.checkout_dir
+        for f in files:
+          command += "; g4 open %s" % f
+        command += "; patch -p2 < %s" % patch_file
+    self.current_ce.RunCommand(command)
+
+  def CheckoutRevision(self, current_revision):
+    job_logger = logger.Logger(self.job_log_root,
+                               current_revision,
+                               True, subdir="")
+    self.current_ce = command_executer.GetCommandExecuter(job_logger)
+
+    self.CleanupCLs()
+    # Change the revision of only the gcc part of the toolchain.
+    command = ("cd %s/gcctools/google_vendor_src_branch/gcc && g4 revert ...; g4 sync @%s" % 
+               (self.checkout_dir, current_revision))
+    self.current_ce.RunCommand(command)
+
+    self.HandleBrokenCLs(current_revision)
+
+
+def Main(argv):
+  """The main function."""
+  # Common initializations
+###  command_executer.InitCommandExecuter(True)
+  ce = command_executer.GetCommandExecuter()
+  rootdir = misc.GetRoot(sys.argv[0])[0]
+
+  parser = optparse.OptionParser()
+  parser.add_option("-n", "--num_tries", dest="num_tries",
+                    default="100",
+                    help="Number of tries.")
+  parser.add_option("-g", "--good_revision", dest="good_revision",
+                    help="Last known good revision.")
+  parser.add_option("-b", "--bad_revision", dest="bad_revision",
+                    help="Last known bad revision.")
+  parser.add_option("-s",
+                    "--script",
+                    dest="script",
+                    help="Script to run for every version.")
+  [options, args] = parser.parse_args(argv)
+  # First get all revisions
+###  p4_paths = ["//depot2/gcctools/google_vendor_src_branch/gcc/gcc-4.4.3/README.google"]
+  p4_paths = ["//depot2/gcctools/google_vendor_src_branch/gcc/gcc-4.4.3/...",
+              "//depot2/gcctools/google_vendor_src_branch/binutils/binutils-2.20.1-mobile/...",
+              "//depot2/gcctools/google_vendor_src_branch/binutils/binutils-20100303/..."]
+  p4gccbs = P4GCCBinarySearcher("perforce2:2666", p4_paths, "")
+
+
+  # Main loop:
+  terminated = False
+  num_tries = int(options.num_tries)
+  test_dir = tempfile.mkdtemp()
+  script = os.path.expanduser(options.script)
+
+  try:
+    p4gccbs.Initialize()
+    p4gccbs.SetGoodRevision(options.good_revision)
+    p4gccbs.SetBadRevision(options.bad_revision)
+    while not terminated and num_tries > 0:
+      current_revision = p4gccbs.GetNextRevision()
+
+      # Now run command to get the status
+      ce = command_executer.GetCommandExecuter()
+      command = "%s %s" % (script, p4gccbs.checkout_dir)
+      status = ce.RunCommand(command)
+      message = ("Revision: %s produced: %d status\n" %
+                 (current_revision, status))
+      logger.GetLogger().LogOutput(message)
+      terminated = p4gccbs.SetStatus(status)
+      num_tries -= 1
+      logger.GetLogger().LogOutput(str(p4gccbs))
+
+    if not terminated:
+      logger.GetLogger().LogOutput("Tries: %d expired." % num_tries)
+    logger.GetLogger().LogOutput(str(p4gccbs.bs))
+  except (KeyboardInterrupt, SystemExit):
+    logger.GetLogger().LogOutput("Cleaning up...")
+  finally:
+    logger.GetLogger().LogOutput(str(p4gccbs.bs))
+    status = p4gccbs.Cleanup()
+
+
+if __name__ == "__main__":
+  Main(sys.argv)
diff --git a/binary_search_tool/binary_search_state.py b/binary_search_tool/binary_search_state.py
new file mode 100755
index 00000000..7c85b975
--- /dev/null
+++ b/binary_search_tool/binary_search_state.py
@@ -0,0 +1,334 @@
+#!/usr/bin/python
+
+import optparse
+import os
+import pickle
+import sys
+import tempfile
+
+# Programtically adding utils python path to PYTHONPATH
+if os.path.isabs(sys.argv[0]):
+  utils_pythonpath = os.path.abspath(
+      '{0}/..'.format(os.path.dirname(sys.argv[0])))
+else:
+  wdir = os.getcwd()
+  utils_pythonpath = os.path.abspath(
+      '{0}/{1}/..'.format(wdir, os.path.dirname(sys.argv[0])))
+sys.path.append(utils_pythonpath)
+# Now we do import from utils
+from utils import command_executer
+from utils import logger
+
+import binary_search_perforce
+
+STATE_FILE = "%s.state" % sys.argv[0]
+
+
+class BinarySearchState(object):
+  def __init__(self, get_initial_items, switch_to_good, switch_to_bad,
+               test_script, incremental, prune, iterations, prune_iterations,
+               verify_level, file_args):
+    self.get_initial_items = get_initial_items
+    self.switch_to_good = switch_to_good
+    self.switch_to_bad = switch_to_bad
+    self.test_script = test_script
+    self.incremental = incremental
+    self.prune = prune
+    self.iterations = iterations
+    self.prune_iterations = prune_iterations
+    self.verify_level = verify_level
+    self.file_args = file_args
+
+    self.l = logger.GetLogger()
+    self.ce = command_executer.GetCommandExecuter()
+
+    self.bs = None
+    self.PopulateItemsUsingCommand(self.get_initial_items)
+    self.currently_good_items = set([])
+    self.currently_bad_items = set([])
+
+  def SwitchToGood(self, item_list):
+    if self.incremental:
+      self.l.LogOutput(
+          "Incremental set. Wanted to switch %s to good" % str(item_list))
+      incremental_items = [
+          item for item in item_list if item not in self.currently_good_items]
+      item_list = incremental_items
+      self.l.LogOutput(
+          "Incremental set. Actually switching %s to good" % str(item_list))
+
+    if not item_list:
+      return
+
+    self.l.LogOutput("Switching %s to good" % str(item_list))
+    self.RunSwitchScript(self.switch_to_good, item_list)
+    self.currently_good_items = self.currently_good_items.union(set(item_list))
+    self.currently_bad_items.difference_update(set(item_list))
+
+  def SwitchToBad(self, item_list):
+    if self.incremental:
+      self.l.LogOutput(
+          "Incremental set. Wanted to switch %s to bad" % str(item_list))
+      incremental_items = [
+          item for item in item_list if item not in self.currently_bad_items]
+      item_list = incremental_items
+      self.l.LogOutput(
+          "Incremental set. Actually switching %s to bad" % str(item_list))
+
+    if not item_list:
+      return
+
+    self.l.LogOutput("Switching %s to bad" % str(item_list))
+    self.RunSwitchScript(self.switch_to_bad, item_list)
+    self.currently_bad_items = self.currently_bad_items.union(set(item_list))
+    self.currently_good_items.difference_update(set(item_list))
+
+  def RunSwitchScript(self, switch_script, item_list):
+    if self.file_args:
+      temp_file = tempfile.mktemp()
+      f = open(temp_file, "wb")
+      f.write("\n".join(item_list))
+      f.close()
+      command = "%s %s" % (switch_script, temp_file)
+    else:
+      command = "%s %s" % (switch_script, " ".join(item_list))
+    ret = self.ce.RunCommand(command)
+    assert ret == 0, "Switch script %s returned %d" % (switch_script, ret)
+
+  def TestScript(self):
+    command = self.test_script
+    return self.ce.RunCommand(command)
+
+  def DoVerify(self):
+    for _ in range(int(self.verify_level)):
+      self.l.LogOutput("Resetting all items to good to verify.")
+      self.SwitchToGood(self.all_items)
+      status = self.TestScript()
+      assert status == 0, "When reset_to_good, status should be 0."
+
+      self.l.LogOutput("Resetting all items to bad to verify.")
+      self.SwitchToBad(self.all_items)
+      status = self.TestScript()
+      assert status == 1, "When reset_to_bad, status should be 1."
+
+  def DoSearch(self):
+    num_bad_items_history = []
+    i = 0
+    while True and len(self.all_items) > 1 and i < self.prune_iterations:
+      i += 1
+      terminated = self.DoBinarySearch()
+      if not terminated:
+        break
+      if not self.prune:
+        self.l.LogOutput("Not continuning further, --prune is not set")
+        break
+      # Prune is set.
+      prune_index = self.bs.current
+
+      if prune_index == len(self.all_items) - 1:
+        self.l.LogOutput("First bad item is the last item. Breaking.")
+        self.l.LogOutput("Only bad item is: %s" % self.all_items[-1])
+        break
+
+      num_bad_items = len(self.all_items) - prune_index
+      num_bad_items_history.append(num_bad_items)
+
+      if (num_bad_items_history[-num_bad_items:] ==
+          [num_bad_items for _ in range(num_bad_items)]):
+        self.l.LogOutput("num_bad_items_history: %s for past %d iterations. "
+                         "Breaking." %
+                         (str(num_bad_items_history),
+                          num_bad_items))
+        self.l.LogOutput(
+            "Bad items are: %s" % " ".join(self.all_items[prune_index:]))
+        break
+
+      new_all_items = list(self.all_items)
+      # Move prune item to the end of the list.
+      new_all_items.append(new_all_items.pop(prune_index))
+
+      if prune_index:
+        new_all_items = new_all_items[prune_index - 1:]
+
+      self.l.LogOutput("Old list: %s. New list: %s" %
+                       (str(self.all_items),
+                        str(new_all_items)))
+
+      # FIXME: Do we need to Convert the currently good items to bad
+      self.PopulateItemsUsingList(new_all_items)
+
+  def DoBinarySearch(self):
+    i = 0
+    terminated = False
+    while i < self.iterations and not terminated:
+      i += 1
+      [bad_items, good_items] = self.GetNextItems(self.incremental)
+
+      # TODO: bad_items should come first.
+      self.SwitchToGood(good_items)
+      self.SwitchToBad(bad_items)
+      status = self.TestScript()
+      terminated = self.bs.SetStatus(status)
+
+      if terminated:
+        self.l.LogOutput("Terminated!")
+    if not terminated:
+      self.l.LogOutput("Ran out of iterations searching...")
+    self.l.LogOutput(str(self))
+    return terminated
+
+  def PopulateItemsUsingCommand(self, command):
+    ce = command_executer.GetCommandExecuter()
+    [_, out, _] = ce.RunCommand(command, return_output=True)
+    all_items = out.split()
+    self.PopulateItemsUsingList(all_items)
+
+  def PopulateItemsUsingList(self, all_items):
+    self.all_items = all_items
+    self.bs = binary_search_perforce.BinarySearcher()
+    self.bs.SetSortedList(self.all_items)
+
+  def SaveState(self):
+    self.l = None
+    self.ce = None
+    # TODO Implement save/restore
+###    return
+    f = open(STATE_FILE, "wb")
+    pickle.dump(self, f)
+    f.close()
+
+  @classmethod
+  def LoadState(cls):
+    if not os.path.isfile(STATE_FILE):
+      return None
+    return pickle.load(file(STATE_FILE))
+
+  @classmethod
+  def GetInstance(cls, command):
+    # Disable state loading for now.
+    # obj = cls.LoadState()
+    obj = None
+    if not obj:
+      obj = cls()
+      return obj
+    return obj
+
+  def GetNextItems(self, incremental=True):
+    border_item = self.bs.GetNext()
+    index = self.all_items.index(border_item)
+
+    next_bad_items = self.all_items[:index+1]
+    next_good_items = self.all_items[index+1:]
+
+    return [next_bad_items, next_good_items]
+
+  def __str__(self):
+    ret = ""
+    ret += "all: %s\n" % str(self.all_items)
+    ret += "currently_good: %s\n" % str(self.currently_good_items)
+    ret += "currently_bad: %s\n" % str(self.currently_bad_items)
+    ret += str(self.bs)
+    return ret
+
+
+def _CanonicalizeScript(script_name):
+  script_name = os.path.expanduser(script_name)
+  if not script_name.startswith("/"):
+    return os.path.join(".", script_name)
+
+
+def Main(argv):
+  """The main function."""
+  # Common initializations
+
+  parser = optparse.OptionParser()
+  parser.add_option("-n",
+                    "--iterations",
+                    dest="iterations",
+                    help="Number of iterations to try in the search.",
+                    default="50")
+  parser.add_option("-i",
+                    "--get_initial_items",
+                    dest="get_initial_items",
+                    help="Script to run to get the initial objects.")
+  parser.add_option("-g",
+                    "--switch_to_good",
+                    dest="switch_to_good",
+                    help="Script to run to switch to good.")
+  parser.add_option("-b",
+                    "--switch_to_bad",
+                    dest="switch_to_bad",
+                    help="Script to run to switch to bad.")
+  parser.add_option("-t",
+                    "--test_script",
+                    dest="test_script",
+                    help=("Script to run to test the "
+                          "output after packages are built."))
+  parser.add_option("-p",
+                    "--prune",
+                    dest="prune",
+                    action="store_true",
+                    default=False,
+                    help=("Script to run to test the output after "
+                          "packages are built."))
+  parser.add_option("-c",
+                    "--noincremental",
+                    dest="noincremental",
+                    action="store_true",
+                    default=False,
+                    help="Do not propagate good/bad changes incrementally.")
+  parser.add_option("-f",
+                    "--file_args",
+                    dest="file_args",
+                    action="store_true",
+                    default=False,
+                    help="Use a file to pass arguments to scripts.")
+  parser.add_option("-v",
+                    "--verify_level",
+                    dest="verify_level",
+                    default="1",
+                    help=("Check binary search assumptions N times "
+                          "before starting."))
+  parser.add_option("-N",
+                    "--prune_iterations",
+                    dest="prune_iterations",
+                    help="Number of prune iterations to try in the search.",
+                    default="100")
+
+  logger.GetLogger().LogOutput(" ".join(argv))
+  [options, _] = parser.parse_args(argv)
+
+  if not (options.get_initial_items and options.switch_to_good and
+          options.switch_to_bad and options.test_script):
+    parser.print_help()
+    return 1
+
+  iterations = int(options.iterations)
+  switch_to_good = _CanonicalizeScript(options.switch_to_good)
+  switch_to_bad = _CanonicalizeScript(options.switch_to_bad)
+  test_script = _CanonicalizeScript(options.test_script)
+  get_initial_items = _CanonicalizeScript(options.get_initial_items)
+  prune = options.prune
+  prune_iterations = options.prune_iterations
+  verify_level = options.verify_level
+  file_args = options.file_args
+
+  if options.noincremental:
+    incremental = False
+  else:
+    incremental = True
+
+  try:
+    bss = BinarySearchState(get_initial_items, switch_to_good, switch_to_bad,
+                            test_script, incremental, prune, iterations,
+                            prune_iterations, verify_level, file_args)
+    bss.DoVerify()
+    bss.DoSearch()
+
+  except (KeyboardInterrupt, SystemExit):
+    print "C-c pressed"
+    bss.SaveState()
+  return 0
+
+if __name__ == "__main__":
+  sys.exit(Main(sys.argv))
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)