[binary search tool] Add bisecting tests.

Add real bisection testing, for use with or without compiler wrapper
script.

BUG=https://b.corp.google.com/issues/34888940
TEST=Tested wtih & without the compiler wrapper in my source tree.

Change-Id: I72329b458b5c93f8e7f03f9970c755018390cc3c
Reviewed-on: https://chromium-review.googlesource.com/438666
Commit-Ready: Caroline Tice <cmtice@chromium.org>
Tested-by: Caroline Tice <cmtice@chromium.org>
Reviewed-by: Yunlian Jiang <yunlian@chromium.org>

29 files changed, 968 insertions, 0 deletions

diff --git a/binary_search_tool/full_bisect_test/bad-objects-permanent/_LIST b/binary_search_tool/full_bisect_test/bad-objects-permanent/_LIST
new file mode 100644
index 00000000..07bc1aa9
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/bad-objects-permanent/_LIST
@@ -0,0 +1,7 @@
+build.o
+inorder_norecurse.o
+inorder.o
+main.o
+preorder_norecurse.o
+preorder.o
+stack.o
diff --git a/binary_search_tool/full_bisect_test/bad-output-1.txt b/binary_search_tool/full_bisect_test/bad-output-1.txt
new file mode 100644
index 00000000..dfd0bfc6
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/bad-output-1.txt
@@ -0,0 +1,11 @@
+pre-order traversal, with recursion: 
+35 28 20 25 23 26 30 60 70 65 64 68 
+
+pre-order traversal, without recursion: 
+35 28 20 25 23 26 30 60 70 65 64 68 
+
+in-order traversal, with recursion: 
+20 23 25 26 28 30 35 60 64 65 68 70 
+
+in-order traversal, without recursion: 
+28 30 35 60 65 68 70 
diff --git a/binary_search_tool/full_bisect_test/bad-output-2.txt b/binary_search_tool/full_bisect_test/bad-output-2.txt
new file mode 100644
index 00000000..e35ebddc
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/bad-output-2.txt
@@ -0,0 +1,11 @@
+pre-order traversal, with recursion: 
+35 28 20 25 23 26 30 60 70 65 64 68 
+
+pre-order traversal, without recursion: 
+35 60 70 
+
+in-order traversal, with recursion: 
+20 23 25 26 28 30 35 60 64 65 68 70 
+
+in-order traversal, without recursion: 
+20 23 25 26 28 30 35 60 64 65 68 70 
diff --git a/binary_search_tool/full_bisect_test/bad-output-3.txt b/binary_search_tool/full_bisect_test/bad-output-3.txt
new file mode 100644
index 00000000..5f3bfef5
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/bad-output-3.txt
@@ -0,0 +1,11 @@
+pre-order traversal, with recursion: 
+35 28 20 25 23 26 30 60 70 65 64 68 
+
+pre-order traversal, without recursion: 
+35 60 70 
+
+in-order traversal, with recursion: 
+20 23 25 26 28 30 35 60 64 65 68 70 
+
+in-order traversal, without recursion: 
+28 30 35 60 65 68 70 
diff --git a/binary_search_tool/full_bisect_test/bin-trees.h b/binary_search_tool/full_bisect_test/bin-trees.h
new file mode 100644
index 00000000..1c4fa199
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/bin-trees.h
@@ -0,0 +1,29 @@
+#ifndef _BIN_TREES_H
+#define _BIN_TREES_H
+
+
+struct bin_tree_struct {
+  int data;
+  char c_data;
+  struct bin_tree_struct *left;
+  struct bin_tree_struct *right;
+};
+
+typedef struct bin_tree_struct * tree_ptr;
+
+
+struct stack_struct {
+  tree_ptr data;
+  struct stack_struct *next;
+};
+
+
+void search_tree_insert (tree_ptr *, int);
+void pre_order_traverse (tree_ptr);
+void pre_order_traverse_no_recurse (tree_ptr);
+void in_order_traverse (tree_ptr);
+void in_order_traverse_no_recurse (tree_ptr);
+void push (struct stack_struct **, tree_ptr);
+tree_ptr pop (struct stack_struct **);
+
+#endif /* _BIN_TREES_H */
diff --git a/binary_search_tool/full_bisect_test/build.c b/binary_search_tool/full_bisect_test/build.c
new file mode 100644
index 00000000..ea1c8b49
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/build.c
@@ -0,0 +1,23 @@
+#include <stdlib.h>
+#include "bin-trees.h"
+
+tree_ptr
+new_node (int value)
+{
+  tree_ptr node = (tree_ptr) malloc (sizeof (tree_ptr));
+  node->data = value;
+  node->left = NULL;
+  node->right = NULL;
+  return node;
+}
+
+void
+search_tree_insert (tree_ptr *root, int value)
+{
+  if (*root == NULL)
+    *root = new_node (value);
+  else if (value < (*root)->data)
+    search_tree_insert (&((*root)->left), value);
+  else if (value > (*root)->data)
+    search_tree_insert (&((*root)->right), value);
+}
diff --git a/binary_search_tool/full_bisect_test/build.sh b/binary_search_tool/full_bisect_test/build.sh
new file mode 100755
index 00000000..9d40fb55
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/build.sh
@@ -0,0 +1,22 @@
+#!/bin/bash
+
+# This file compiles all the source files into .o files, then links them to form
+# the test binary, 'bin-trees'.  The .o files all go into the 'work' directory.
+# There are 'good' and 'bad' versions of inorder_norecurse and preorder_norecurse
+# (e.g. inorder_norecurse.c.good and inorder_norecurse.c.bad).  This script
+# assumes that the desired versions of those files have been copied into
+# inorder_norecurse.c and preorder_norecurse.c.  The script files
+# make_sources_good.sh and make_sources_bad.sh are meant to handle this.
+#
+#  This script is meant to be run directly in the full_bisect_test directory.
+#  Most other scripts assume they are being run from the parent directory.
+
+gcc -c build.c -o work/build.o
+gcc -c preorder.c -o work/preorder.o
+gcc -c inorder.c -o work/inorder.o
+gcc -c main.c -o work/main.o
+gcc -c stack.c -o work/stack.o 
+gcc -c preorder_norecurse.c -o work/preorder_norecurse.o
+gcc -c inorder_norecurse.c -o work/inorder_norecurse.o
+gcc -o bin-trees work/main.o work/preorder.o work/inorder.o work/build.o work/preorder_norecurse.o work/inorder_norecurse.o work/stack.o
+
diff --git a/binary_search_tool/full_bisect_test/cleanup.sh b/binary_search_tool/full_bisect_test/cleanup.sh
new file mode 100755
index 00000000..48b44f30
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/cleanup.sh
@@ -0,0 +1,8 @@
+#!/bin/bash
+
+# In keeping with the normal way of doing bisectin, this script is meant to
+# remove files specific to the particular run of the bisector.
+#
+# This file is called from main-bisect-test.sh
+
+rm full_bisect_test/common.sh
diff --git a/binary_search_tool/full_bisect_test/get_initial_items.sh b/binary_search_tool/full_bisect_test/get_initial_items.sh
new file mode 100755
index 00000000..4c4043f1
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/get_initial_items.sh
@@ -0,0 +1,9 @@
+#!/bin/bash -u
+#
+# This is one of the test scripts that needs to be passed to
+# binary_search_state.py.
+
+source full_bisect_test/common.sh
+
+cat ${BISECT_GOOD_BUILD}/_LIST
+
diff --git a/binary_search_tool/full_bisect_test/good-objects-permanent/_LIST b/binary_search_tool/full_bisect_test/good-objects-permanent/_LIST
new file mode 100644
index 00000000..07bc1aa9
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/good-objects-permanent/_LIST
@@ -0,0 +1,7 @@
+build.o
+inorder_norecurse.o
+inorder.o
+main.o
+preorder_norecurse.o
+preorder.o
+stack.o
diff --git a/binary_search_tool/full_bisect_test/good-output.txt b/binary_search_tool/full_bisect_test/good-output.txt
new file mode 100644
index 00000000..4db15eb2
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/good-output.txt
@@ -0,0 +1,11 @@
+pre-order traversal, with recursion: 
+35 28 20 25 23 26 30 60 70 65 64 68 
+
+pre-order traversal, without recursion: 
+35 28 20 25 23 26 30 60 70 65 64 68 
+
+in-order traversal, with recursion: 
+20 23 25 26 28 30 35 60 64 65 68 70 
+
+in-order traversal, without recursion: 
+20 23 25 26 28 30 35 60 64 65 68 70 
diff --git a/binary_search_tool/full_bisect_test/inorder.c b/binary_search_tool/full_bisect_test/inorder.c
new file mode 100644
index 00000000..ad093f3c
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/inorder.c
@@ -0,0 +1,22 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "bin-trees.h"
+
+static void
+real_inorder (tree_ptr root)
+{
+  if (root == NULL)
+    return;
+
+  real_inorder (root->left);
+  printf ("%d ", root->data);
+  real_inorder (root->right);
+}
+
+void
+in_order_traverse (tree_ptr root)
+{
+  printf ("in-order traversal, with recursion: \n");
+  real_inorder (root);
+  printf ("\n");
+}
diff --git a/binary_search_tool/full_bisect_test/inorder_norecurse.c.bad b/binary_search_tool/full_bisect_test/inorder_norecurse.c.bad
new file mode 100644
index 00000000..27f0bb16
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/inorder_norecurse.c.bad
@@ -0,0 +1,42 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "bin-trees.h"
+
+static void
+real_in_order_traverse_no_recurse (tree_ptr root)
+{
+  struct stack_struct *stack = NULL;
+  tree_ptr current= root;
+  int going_left = 1;   /* boolean variable */
+  while (current != NULL)
+  {
+    if ((current->left != NULL) && going_left)
+    {
+      push (&stack, current);
+      current = current->left;
+    }
+
+    printf ("%d ", current->data);
+    if (current->right)
+    {
+      current = current->right;
+      going_left = 1;
+    }
+    else if (stack != NULL)
+    {
+      current = pop(&stack);
+      going_left = 0;
+    }
+    else
+      current = NULL;
+  }
+}
+
+void
+in_order_traverse_no_recurse (tree_ptr root)
+{
+  printf ("in-order traversal, without recursion: \n");
+  real_in_order_traverse_no_recurse (root);
+  printf ("\n");
+  return;
+}
diff --git a/binary_search_tool/full_bisect_test/inorder_norecurse.c.good b/binary_search_tool/full_bisect_test/inorder_norecurse.c.good
new file mode 100644
index 00000000..a03f4818
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/inorder_norecurse.c.good
@@ -0,0 +1,42 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "bin-trees.h"
+
+static void
+real_in_order_traverse_no_recurse (tree_ptr root)
+{
+  struct stack_struct *stack = NULL;
+  tree_ptr current= root;
+  int going_left = 1;   /* boolean variable */
+  while (current != NULL)
+  {
+    while ((current->left != NULL) && going_left)
+    {
+      push (&stack, current);
+      current = current->left;
+    }
+
+    printf ("%d ", current->data);
+    if (current->right)
+    {
+      current = current->right;
+      going_left = 1;
+    }
+    else if (stack != NULL)
+    {
+      current = pop(&stack);
+      going_left = 0;
+    }
+    else
+      current = NULL;
+  }
+}
+
+void
+in_order_traverse_no_recurse (tree_ptr root)
+{
+  printf ("in-order traversal, without recursion: \n");
+  real_in_order_traverse_no_recurse (root);
+  printf ("\n");
+  return;
+}
diff --git a/binary_search_tool/full_bisect_test/interactive_test.sh b/binary_search_tool/full_bisect_test/interactive_test.sh
new file mode 100755
index 00000000..064e4ae5
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/interactive_test.sh
@@ -0,0 +1,56 @@
+#!/bin/bash -u
+#
+# This script is one of the required scripts that get passed to
+# binary_search_state.py.  It's job is to test the executable that
+# was generated by mixing/matching good & bad object files, and determine
+# whether the resulting binary is good or bad.
+#
+# In this particular case, the generated binary is 'bin-trees'.  This
+# script runs the binary, captures its output, and compares the output
+# to a file containg the correct (good) output, and three files containing
+# what the bad output might look like, depending on if one of the two
+# possile bad .o files was used, or if both bad .o files were used.
+#
+# If the output matches the known good output, this returns 0.
+# If the output matches any known bad output, this returns 1.
+# If the output does not match the good or bad outputs, this returns 125.
+#
+
+source full_bisect_test/common.sh
+
+full_bisect_test/bin-trees > full_bisect_test/temp_output.txt
+
+diff full_bisect_test/temp_output.txt full_bisect_test/good-output.txt &> /dev/null
+retval=$?
+
+if [[ ${retval} -eq 0 ]]; then
+  rm -f full_bisect_test/temp_output.txt
+  exit 0
+fi
+
+diff full_bisect_test/temp_output.txt full_bisect_test/bad-output-1.txt &> /dev/null
+retval=$?
+
+if [[ ${retval} -eq 0 ]]; then
+  rm -f full_bisect_test/temp_output.txt
+  exit 1
+else
+  diff full_bisect_test/temp_output.txt full_bisect_test/bad-output-2.txt &> /dev/null
+  retval=$?
+  if [[ ${retval} -eq 0 ]]; then
+    rm -f full_bisect_test/temp_output.txt
+    exit 1
+  else
+    diff full_bisect_test/temp_output.txt full_bisect_test/bad-output-3.txt &> /dev/null
+    retval=$?
+    if [[ ${retval} -eq 0 ]]; then
+      rm -f full_bisect_test/temp_output.txt
+      exit 1
+    fi
+  fi
+fi
+
+rm -f full_bisect_test/temp_output.txt
+exit 125
+
+
diff --git a/binary_search_tool/full_bisect_test/main-bisect-test.sh b/binary_search_tool/full_bisect_test/main-bisect-test.sh
new file mode 100755
index 00000000..af01c19c
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/main-bisect-test.sh
@@ -0,0 +1,104 @@
+#!/bin/bash
+#
+#  This script is the heart of the bisection test.  It assumes the good-objects
+#  and bad-objects directories have been created and populated.  It runs three
+#  bisection tests:
+#   Test 1.  use --file_args, and no pruning, which passes the object file list
+#            in a file, and stops as soon as it finds the first bad file.
+#   Test 2.  do not use --file_args, and no pruning.  The object files are passed
+#            directly on the command line; stop as soon as it finds the first
+#            bad file.
+#   Test 3.  use --file_args and --prune.  Pass the object file list in a file
+#            and run until it finds ALL the bad files (there are two of them).
+#
+
+SAVE_DIR=`pwd`
+
+DIR=full_bisect_test
+
+# Make sure you are running this script from the parent directory.
+if [[ ! -f "${DIR}/setup.sh" ]] ; then
+  echo "Cannot find ${DIR}/setup.sh.  You are running this from the wrong directory."
+  echo "You need to run this from toolchain-utils/binary_search_tool ."
+  exit 1
+fi
+
+# Run Test 1.
+${DIR}/setup.sh
+
+./binary_search_state.py --get_initial_items="${DIR}/get_initial_items.sh" \
+  --switch_to_good="${DIR}/switch_to_good.sh" \
+  --switch_to_bad="${DIR}/switch_to_bad.sh" \
+  --test_setup_script="${DIR}/test_setup.sh" \
+  --test_script="${DIR}/interactive_test.sh" \
+  --file_args &> /tmp/full_bisect_test.log
+
+${DIR}/cleanup.sh
+
+grep "Search complete. First bad version: " /tmp/full_bisect_test.log &> /dev/null
+test_status=$?
+
+if [[ ${test_status} -ne 0 ]] ; then
+  echo "Test 1 FAILED. See /tmp/full_bisect_test.log for details."
+  exit 1
+else
+  echo "Test 1 passed."
+fi
+
+cd ${SAVE_DIR}
+
+# Run Test 2.
+${DIR}/setup.sh
+
+./binary_search_state.py --get_initial_items="${DIR}/get_initial_items.sh" \
+  --switch_to_good="${DIR}/switch_to_good.sh" \
+  --switch_to_bad="${DIR}/switch_to_bad.sh" \
+  --test_setup_script="${DIR}/test_setup.sh" \
+  --test_script="${DIR}/interactive_test.sh" \
+  &> /tmp/full_bisect_test.log
+
+${DIR}/cleanup.sh
+
+grep "Search complete. First bad version: " /tmp/full_bisect_test.log &> /dev/null
+test_status=$?
+
+if [[ ${test_status} -ne 0 ]] ; then
+  echo "Test 2 FAILED. See /tmp/full_bisect_test.log for details."
+  exit 1
+else
+  echo "Test 2 passed."
+fi
+
+cd ${SAVE_DIR}
+
+# Run Test 3.
+${DIR}/setup.sh
+
+./binary_search_state.py --get_initial_items="${DIR}/get_initial_items.sh" \
+  --switch_to_good="${DIR}/switch_to_good.sh" \
+  --switch_to_bad="${DIR}/switch_to_bad.sh" \
+  --test_setup_script="${DIR}/test_setup.sh" \
+  --test_script="${DIR}/interactive_test.sh" \
+  --file_args --prune &> /tmp/full_bisect_test.log
+
+${DIR}/cleanup.sh
+
+grep "Bad items are: " /tmp/full_bisect_test.log | grep inorder_norecurse.o &> /dev/null
+test_status_1=$?
+
+grep "Bad items are: " /tmp/full_bisect_test.log | grep preorder_norecurse.o &> /dev/null
+test_status_2=$?
+
+if [[ ${test_status_1} -ne 0 ]] ; then
+  echo "Test 3 FAILED. See /tmp/full_bisect_test.log for details."
+  exit 1
+elif [[ ${test_status_2} -ne 0 ]] ; then
+  echo "Test 3 FAILED. See /tmp/full_bisect_test.log for details."
+  exit 1
+else
+  echo "Test 3 passed."
+fi
+
+# All tests passed!
+exit 0
+
diff --git a/binary_search_tool/full_bisect_test/main.c b/binary_search_tool/full_bisect_test/main.c
new file mode 100644
index 00000000..55abc44b
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/main.c
@@ -0,0 +1,30 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "bin-trees.h"
+
+int integers[] = {35, 28, 20, 30, 25, 23, 26, 60, 70, 65, 64, 68 };
+
+char pre_order[] = { '/', '-', '+', '*', 'a', '^', 'x', '2', '&', 'b', 'y',
+                     'c', '3' };
+char in_order[]  = { 'a', '*', 'x', '^', '2', '+', 'b', '&', 'y', '-', 'c',
+                     '/', '3' };
+
+int
+main (int argc, char ** argv)
+{
+  int intlist_size = 12;
+  int i;
+  tree_ptr root = NULL;
+  for (i = 0; i < intlist_size; ++i)
+    {
+      search_tree_insert (&root, integers[i]);
+    }
+  pre_order_traverse (root);
+  printf ("\n");
+  pre_order_traverse_no_recurse (root);
+  printf ("\n");
+  in_order_traverse (root);
+  printf ("\n");
+  in_order_traverse_no_recurse (root);
+  return 0;
+}
diff --git a/binary_search_tool/full_bisect_test/make_sources_bad.sh b/binary_search_tool/full_bisect_test/make_sources_bad.sh
new file mode 100755
index 00000000..507e8ca8
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/make_sources_bad.sh
@@ -0,0 +1,15 @@
+#!/bin/bash -u
+#
+#  There are two versions (good & bad) of inorder_norecurse.c and
+#  preorder_norecurse.c.  This script makes sure the bad versions
+#  are copied into the .c files that will be built and copied into
+#  the bad-objects directory, for the bisection test. It is called
+#  from run-test-nowrapper.sh.
+#
+
+pushd full_bisect_test
+
+cp inorder_norecurse.c.bad inorder_norecurse.c
+cp preorder_norecurse.c.bad preorder_norecurse.c
+
+popd
diff --git a/binary_search_tool/full_bisect_test/make_sources_good.sh b/binary_search_tool/full_bisect_test/make_sources_good.sh
new file mode 100755
index 00000000..611e9442
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/make_sources_good.sh
@@ -0,0 +1,15 @@
+#!/bin/bash -u
+#
+#  There are two versions (good & bad) of inorder_norecurse.c and
+#  preorder_norecurse.c.  This script makes sure the good versions
+#  are copied into the .c files that will be built and copied into
+#  the good-objects directory, for the bisection test.  It is called
+#  from run-test-nowrapper.sh.
+#
+
+pushd full_bisect_test
+
+cp inorder_norecurse.c.good inorder_norecurse.c
+cp preorder_norecurse.c.good preorder_norecurse.c
+
+popd
diff --git a/binary_search_tool/full_bisect_test/preorder.c b/binary_search_tool/full_bisect_test/preorder.c
new file mode 100644
index 00000000..11fe93a3
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/preorder.c
@@ -0,0 +1,23 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "bin-trees.h"
+
+static void
+real_preorder (tree_ptr root)
+{
+  if (root == NULL)
+    return;
+
+  printf ("%d ", root->data);
+  real_preorder (root->left);
+  real_preorder (root->right);
+}
+
+
+void
+pre_order_traverse (tree_ptr root)
+{
+  printf ("pre-order traversal, with recursion: \n");
+  real_preorder (root) ;
+  printf ("\n");
+}
diff --git a/binary_search_tool/full_bisect_test/preorder_norecurse.c.bad b/binary_search_tool/full_bisect_test/preorder_norecurse.c.bad
new file mode 100644
index 00000000..a8b4b487
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/preorder_norecurse.c.bad
@@ -0,0 +1,29 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "bin-trees.h"
+
+static void
+real_pre_order_traverse_no_recurse (tree_ptr root)
+{
+  struct stack_struct *stack = NULL;
+
+  if (root != NULL)
+    push (&stack, root);
+
+  while (stack != NULL)
+  {
+    tree_ptr current = pop (&stack);
+    printf ("%d ", current->data);
+    if (current->right != NULL)
+      push (&stack, current->right);
+  }
+  return;
+}
+
+void
+pre_order_traverse_no_recurse (tree_ptr root)
+{
+  printf ("pre-order traversal, without recursion: \n");
+  real_pre_order_traverse_no_recurse (root);
+  printf ("\n");
+}
diff --git a/binary_search_tool/full_bisect_test/preorder_norecurse.c.good b/binary_search_tool/full_bisect_test/preorder_norecurse.c.good
new file mode 100644
index 00000000..98f40913
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/preorder_norecurse.c.good
@@ -0,0 +1,31 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "bin-trees.h"
+
+static void
+real_pre_order_traverse_no_recurse (tree_ptr root)
+{
+  struct stack_struct *stack = NULL;
+
+  if (root != NULL)
+    push (&stack, root);
+
+  while (stack != NULL)
+  {
+    tree_ptr current = pop (&stack);
+    printf ("%d ", current->data);
+    if (current->right != NULL)
+      push (&stack, current->right);
+    if (current->left != NULL)
+      push (&stack, current->left);
+  }
+  return;
+}
+
+void
+pre_order_traverse_no_recurse (tree_ptr root)
+{
+  printf ("pre-order traversal, without recursion: \n");
+  real_pre_order_traverse_no_recurse (root);
+  printf ("\n");
+}
diff --git a/binary_search_tool/full_bisect_test/run-test-nowrapper.sh b/binary_search_tool/full_bisect_test/run-test-nowrapper.sh
new file mode 100755
index 00000000..94876e70
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/run-test-nowrapper.sh
@@ -0,0 +1,69 @@
+#!/bin/bash
+#
+# This script is one of the two main driver scripts for testing the bisector.
+# It should be used to test the bisection tool, if you do NOT want to test
+# the compiler wrapper (e.g. don't bother with POPULATE_GOOD & POPULATE_BAD
+# stages).
+#
+# It makes sure the good & bad object directories exist (soft links); checks
+# to see if it needs to compile the good & bad sources & populate the
+# directories; does so if needed.
+#
+# Then it calls main-bisect-test, which runs the actual bisection tests.  This
+# script assumes it is being run from the parent directory.
+#
+# NOTE: Your PYTHONPATH environment variable needs to include both the
+# toolchain-utils directory and the
+# toolchain-utils/binary_search_tool directory for these testers to work.
+#
+
+SAVE_DIR=`pwd`
+
+DIR=full_bisect_test
+
+if [[ ! -d "${DIR}" ]] ; then
+  echo "Cannot find ${DIR}; you are running this script from the wrong place."
+  echo "You need to run this from toolchain-utils/binary_search_tool ."
+  exit 1
+fi
+
+# Set up object file soft links
+cd ${DIR}
+
+rm -f good-objects
+rm -f bad-objects
+
+ln -s good-objects-permanent good-objects
+ln -s bad-objects-permanent bad-objects
+
+if [[ ! -d work ]] ; then
+  mkdir work
+fi
+
+# Check to see if the object files need to be built.
+if [[ ! -f good-objects-permanent/build.o ]] ; then
+  # 'make clean'
+  rm -f work/*.o
+  # skip populate stages in bisect wrapper
+  unset BISECT_STAGE
+  SAVE_DIR=`pwd`
+  # Set up the 'good' source files.
+  cd ..
+  ${DIR}/make_sources_good.sh
+  cd ${SAVE_DIR}
+  # Build the 'good' .o files & copy to appropriate directory.
+  ./build.sh
+  mv work/*.o good-objects-permanent/.
+  # Set up the 'bad' source files.
+  cd ..
+  ${DIR}/make_sources_bad.sh
+  cd ${SAVE_DIR}
+  # Build the 'bad' .o files & copy to appropriate directory.
+  ./build.sh
+  mv work/*.o bad-objects-permanent/.
+fi
+
+# Now we're ready for the main test.
+
+cd ${SAVE_DIR}
+${DIR}/main-bisect-test.sh
diff --git a/binary_search_tool/full_bisect_test/setup.sh b/binary_search_tool/full_bisect_test/setup.sh
new file mode 100755
index 00000000..1214de92
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/setup.sh
@@ -0,0 +1,36 @@
+#!/bin/bash
+#
+# This script creates common.sh, which will be sourced by all the other
+# scripts, to set up the necessary environment variables for the bisection
+# to work properly.  It is called from main-bisect-test.sh.
+#
+
+DIR=`pwd`/"full_bisect_test"
+
+GOOD_BUILD=${DIR}/good-objects
+BAD_BUILD=${DIR}/bad-objects
+
+mkdir -p ${DIR}/work
+
+WORK_BUILD=${DIR}/work
+
+rm -f ${WORK_BUILD}/*
+
+COMMON_FILE="${DIR}/common.sh"
+
+cat <<-EOF > ${COMMON_FILE}
+
+BISECT_GOOD_BUILD=${GOOD_BUILD}
+BISECT_BAD_BUILD=${BAD_BUILD}
+BISECT_WORK_BUILD=${WORK_BUILD}
+
+BISECT_GOOD_SET=${GOOD_BUILD}/_LIST
+BISECT_BAD_BAD=${BAD_BUILD}/_LIST
+
+BISECT_STAGE="TRIAGE"
+
+EOF
+
+chmod 755 ${COMMON_FILE}
+
+exit 0
diff --git a/binary_search_tool/full_bisect_test/stack.c b/binary_search_tool/full_bisect_test/stack.c
new file mode 100644
index 00000000..f8d0568f
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/stack.c
@@ -0,0 +1,25 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "bin-trees.h"
+
+tree_ptr
+pop (struct stack_struct **stack)
+{
+  if (*stack == NULL)
+    return NULL;
+  else
+    {
+      tree_ptr value = (*stack)->data;
+      (*stack) = (*stack)->next;
+      return value;
+    }
+}
+
+void
+push (struct stack_struct **stack, tree_ptr value)
+{
+  struct stack_struct *new_node = (struct stack_struct *) malloc (sizeof (struct stack_struct *));
+  new_node->data = value;
+  new_node->next = *stack;
+  *stack = new_node;
+}
diff --git a/binary_search_tool/full_bisect_test/switch_to_bad.sh b/binary_search_tool/full_bisect_test/switch_to_bad.sh
new file mode 100755
index 00000000..f5ae79d7
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/switch_to_bad.sh
@@ -0,0 +1,53 @@
+#!/bin/bash -u
+#
+# This is one of the scripts that is passed to binary_search_state.py to do
+# the bisection.  This one takes a list of object files (either a real list or
+# a file containing the list) and copies the files from the bad objects
+# directory to the working directory.
+#
+
+source full_bisect_test/common.sh
+
+pushd ${BISECT_WORK_BUILD}
+
+OBJ_LIST_FILES=$1
+FILE_ARGS=0
+
+if [[ -f ${OBJ_LIST_FILES} ]] ; then
+  file ${OBJ_LIST_FILES} &> ${BISECT_WORK_BUILD}/file_type.tmp
+  grep "ASCII text" ${BISECT_WORK_BUILD}/file_type.tmp
+  result=$?
+  if [[ ${result} -eq 0 ]] ; then
+    FILE_ARGS=1
+  fi
+  rm ${BISECT_WORK_BUILD}/file_type.tmp
+fi
+
+overall_status=0
+
+if [[ ${FILE_ARGS} -eq 1 ]] ; then
+  while read obj || [[ -n "${obj}" ]];
+  do
+    cp ${BISECT_BAD_BUILD}/${obj} ${BISECT_WORK_BUILD}
+    status=$?
+    if [[ ${status} -ne 0 ]] ; then
+      echo "Failed to copy ${obj} to work build tree."
+      overall_status=2
+    fi
+  done < ${OBJ_LIST_FILES}
+else
+
+  for o in "$@"
+  do
+    cp ${BISECT_BAD_BUILD}/${o} ${BISECT_WORK_BUILD}
+    status=$?
+    if [[ ${status} -ne 0 ]] ; then
+      echo "Failed to copy ${o} to work build tree."
+      overall_status=2
+    fi
+  done
+fi
+
+popd
+
+exit ${overall_status}
diff --git a/binary_search_tool/full_bisect_test/switch_to_good.sh b/binary_search_tool/full_bisect_test/switch_to_good.sh
new file mode 100755
index 00000000..ed7b822a
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/switch_to_good.sh
@@ -0,0 +1,56 @@
+#!/bin/bash -u
+#
+# This is one of the scripts that is passed to binary_search_state.py to do
+# the bisection.  This one takes a list of object files (either a real list or
+# a file containing the list) and copies the files from the good objects
+# directory to the working directory.
+#
+
+
+source full_bisect_test/common.sh
+
+pushd ${BISECT_WORK_BUILD}
+
+OBJ_LIST_FILES=$1
+FILE_ARGS=0
+
+if [[ -f ${OBJ_LIST_FILES} ]] ; then
+  file ${OBJ_LIST_FILES} &> ${BISECT_WORK_BUILD}/file_type.tmp
+  grep "ASCII text" ${BISECT_WORK_BUILD}/file_type.tmp
+  result=$?
+  if [[ ${result} -eq 0 ]] ; then
+    FILE_ARGS=1
+  fi
+  rm ${BISECT_WORK_BUILD}/file_type.tmp
+fi
+
+overall_status=0
+
+if [[ ${FILE_ARGS} -eq 1 ]] ; then
+  while read obj || [[ -n "${obj}" ]];
+  do
+    echo "Copying {BISECT_GOOD_BUILD}/${obj} to ${BISECT_WORK_BUILD}"
+    cp ${BISECT_GOOD_BUILD}/${obj} ${BISECT_WORK_BUILD}
+#    cp ${obj} ${BISECT_WORK_BUILD}/.
+    status=$?
+    if [[ ${status} -ne 0 ]] ; then
+      echo "Failed to copy ${obj} to work build tree."
+      overall_status=2
+    fi
+  done < ${OBJ_LIST_FILES}
+else
+
+  for o in "$@"
+  do
+    cp ${BISECT_GOOD_BUILD}/${o} ${BISECT_WORK_BUILD}
+    status=$?
+    if [[ ${status} -ne 0 ]] ; then
+      echo "Failed to copy ${o} to work build tree."
+      overall_status=2
+    fi
+  done
+fi
+
+popd
+
+exit ${overall_status}
diff --git a/binary_search_tool/full_bisect_test/test_setup.sh b/binary_search_tool/full_bisect_test/test_setup.sh
new file mode 100755
index 00000000..bb313831
--- /dev/null
+++ b/binary_search_tool/full_bisect_test/test_setup.sh
@@ -0,0 +1,16 @@
+#!/bin/bash
+#
+# This is one of the scripts that gets passed to binary_search_state.py.
+# It's supposed to generate the binary to be tested, from the mix of
+# good & bad object files.
+#
+source full_bisect_test/common.sh
+
+WD=`pwd`
+
+cd full_bisect_test
+
+echo "BUILDING IMAGE"
+
+gcc -o bin-trees work/*.o
+
diff --git a/binary_search_tool/run_bisect_test.py b/binary_search_tool/run_bisect_test.py
new file mode 100755
index 00000000..c2776cce
--- /dev/null
+++ b/binary_search_tool/run_bisect_test.py
@@ -0,0 +1,155 @@
+#!/usr/bin/python2
+
+from __future__ import print_function
+
+import argparse
+import os
+import sys
+
+from cros_utils import command_executer
+
+TEST_DIR = 'full_bisect_test'
+DEFAULT_BISECT_DIR = os.path.expanduser('~/ANDROID_BISECT')
+
+
+def populate_good_files(top_dir, ce, bisect_dir=DEFAULT_BISECT_DIR):
+  # 'make clean'
+  work_dir = os.path.join(top_dir, TEST_DIR, 'work')
+  cmd = 'rm -f %s/*.o' % work_dir
+  status = ce.RunCommand(cmd)
+  if status != 0:
+    print('Error trying to clean out work directory: %s' % cmd)
+    return status
+
+  # set up the 'good' source files
+  script = os.path.join(top_dir, TEST_DIR, 'make_sources_good.sh')
+  status = ce.RunCommand(script)
+  if status != 0:
+    print('Error setting up "good" source files: %s' % script)
+    return status
+
+  export_bisect = ''
+  if bisect_dir != DEFAULT_BISECT_DIR:
+    export_bisect = 'export BISECT_DIR=%s; ' % bisect_dir
+  # build the good source files
+  script_path = os.path.join(top_dir, TEST_DIR)
+  cmd = ('%s export BISECT_STAGE=POPULATE_GOOD; pushd %s; ./build.sh; popd' %
+         (export_bisect, script_path))
+  status = ce.RunCommand(cmd)
+  return status
+
+
+def populate_bad_files(top_dir, ce, bisect_dir=DEFAULT_BISECT_DIR):
+  # 'make clean'
+  work_dir = os.path.join(top_dir, TEST_DIR, 'work')
+  cmd = 'rm -f %s/*.o' % work_dir
+  status = ce.RunCommand(cmd)
+  if status != 0:
+    print('Error trying to clean out work directory: %s' % cmd)
+    return status
+
+  # set up the 'bad' source files
+  script = os.path.join(top_dir, TEST_DIR, 'make_sources_bad.sh')
+  status = ce.RunCommand(script)
+  if status != 0:
+    print('Error setting up "bad" source files: %s' % script)
+    return status
+
+  export_bisect = ''
+  if bisect_dir != DEFAULT_BISECT_DIR:
+    export_bisect = 'export BISECT_DIR=%s; ' % bisect_dir
+  # build the bad source files
+  script_path = os.path.join(top_dir, TEST_DIR)
+  cmd = ('%s export BISECT_STAGE=POPULATE_BAD; pushd %s; ./build.sh ; popd' %
+         (export_bisect, script_path))
+  status = ce.RunCommand(cmd)
+  return status
+
+
+def run_main_bisection_test(top_dir, ce):
+  test_script = os.path.join(top_dir, TEST_DIR, 'main-bisect-test.sh')
+  status = ce.RunCommand(test_script)
+  return status
+
+
+def verify_compiler_and_wrapper():
+  message = """
+*** IMPORTANT --- READ THIS CAREFULLY!! ***
+
+This test uses the command 'gcc' to compile the good/bad versions of the
+source program.  BEFORE you can run this script you must make sure that
+your compiler wrapper is in the right place, with the right name, so that
+a call to 'gcc' will go through your compiler wrapper and "do the right
+thing".
+
+Is your compiler wrapper properly set up? [Y/n]
+"""
+
+  print(message)
+  inp = sys.stdin.readline()
+  inp = inp.strip()
+  inp = inp.lower()
+  return (not inp or inp == 'y' or inp == 'yes')
+
+
+def Main(argv):
+  parser = argparse.ArgumentParser()
+  parser.add_argument(
+      '--dir',
+      dest='directory',
+      help='Bisection work tree, where good  & bad object '
+      'files go.  Default is ~/ANDROID_BISECT')
+
+  options = parser.parse_args(argv)
+
+  # Make sure the compiler wrapper & soft links are properly set up.
+  wrapper_is_setup = verify_compiler_and_wrapper()
+  if not wrapper_is_setup:
+    print('Exiting now.  Please re-run after you have set up the compiler '
+          'wrapper.')
+    return 0
+
+  # Make sure we're in the correct directory for running this test.
+  cwd = os.getcwd()
+  if not os.path.exists(os.path.join(cwd, 'full_bisect_test')):
+    print('Error:  Wrong directory.  This script must be run from the top level'
+          ' of the binary_search_tool tree (under toolchain_utils).')
+    return 1
+
+  ce = command_executer.GetCommandExecuter()
+  bisect_dir = options.directory
+  if not bisect_dir:
+    bisect_dir = DEFAULT_BISECT_DIR
+
+  retval = populate_good_files(cwd, ce, bisect_dir)
+  if retval != 0:
+    return retval
+
+  retval = populate_bad_files(cwd, ce, bisect_dir)
+  if retval != 0:
+    return retval
+
+  # Set up good/bad work soft links
+  cmd = ('rm -f %s/%s/good-objects; ln -s %s/good %s/%s/good-objects' %
+         (cwd, TEST_DIR, bisect_dir, cwd, TEST_DIR))
+
+  status = ce.RunCommand(cmd)
+  if status != 0:
+    print('Error executing: %s; exiting now.' % cmd)
+    return status
+
+  cmd = ('rm -f %s/%s/bad-objects; ln -s %s/bad %s/%s/bad-objects' %
+         (cwd, TEST_DIR, bisect_dir, cwd, TEST_DIR))
+
+  status = ce.RunCommand(cmd)
+  if status != 0:
+    print('Error executing: %s; exiting now.' % cmd)
+    return status
+
+  retval = run_main_bisection_test(cwd, ce)
+  return retval
+
+
+if __name__ == '__main__':
+  retval = Main(sys.argv[1:])
+  sys.exit(retval)