[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>
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 0000000..07bc1aa
--- /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 0000000..dfd0bfc
--- /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 0000000..e35ebdd
--- /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 0000000..5f3bfef
--- /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 0000000..1c4fa19
--- /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 0000000..ea1c8b4
--- /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 0000000..9d40fb5
--- /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 0000000..48b44f3
--- /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 0000000..4c4043f
--- /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 0000000..07bc1aa
--- /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 0000000..4db15eb
--- /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 0000000..ad093f3
--- /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 0000000..27f0bb1
--- /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 0000000..a03f481
--- /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 0000000..064e4ae
--- /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 0000000..af01c19
--- /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 0000000..55abc44
--- /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 0000000..507e8ca
--- /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 0000000..611e944
--- /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 0000000..11fe93a
--- /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 0000000..a8b4b48
--- /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 0000000..98f4091
--- /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 0000000..94876e7
--- /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 0000000..1214de9
--- /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 0000000..f8d0568
--- /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 0000000..f5ae79d
--- /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 0000000..ed7b822
--- /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 0000000..bb31383
--- /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 0000000..c2776cc
--- /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)
