From 1cc48481a2ca530bab04999da78eddc8a1b98adb Mon Sep 17 00:00:00 2001 From: Caroline Tice Date: Mon, 6 Feb 2017 14:54:28 -0800 Subject: [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 Tested-by: Caroline Tice Reviewed-by: Yunlian Jiang --- .../full_bisect_test/bad-objects-permanent/_LIST | 7 + .../full_bisect_test/bad-output-1.txt | 11 ++ .../full_bisect_test/bad-output-2.txt | 11 ++ .../full_bisect_test/bad-output-3.txt | 11 ++ binary_search_tool/full_bisect_test/bin-trees.h | 29 ++++ binary_search_tool/full_bisect_test/build.c | 23 +++ binary_search_tool/full_bisect_test/build.sh | 22 +++ binary_search_tool/full_bisect_test/cleanup.sh | 8 ++ .../full_bisect_test/get_initial_items.sh | 9 ++ .../full_bisect_test/good-objects-permanent/_LIST | 7 + .../full_bisect_test/good-output.txt | 11 ++ binary_search_tool/full_bisect_test/inorder.c | 22 +++ .../full_bisect_test/inorder_norecurse.c.bad | 42 ++++++ .../full_bisect_test/inorder_norecurse.c.good | 42 ++++++ .../full_bisect_test/interactive_test.sh | 56 ++++++++ .../full_bisect_test/main-bisect-test.sh | 104 ++++++++++++++ binary_search_tool/full_bisect_test/main.c | 30 ++++ .../full_bisect_test/make_sources_bad.sh | 15 ++ .../full_bisect_test/make_sources_good.sh | 15 ++ binary_search_tool/full_bisect_test/preorder.c | 23 +++ .../full_bisect_test/preorder_norecurse.c.bad | 29 ++++ .../full_bisect_test/preorder_norecurse.c.good | 31 +++++ .../full_bisect_test/run-test-nowrapper.sh | 69 +++++++++ binary_search_tool/full_bisect_test/setup.sh | 36 +++++ binary_search_tool/full_bisect_test/stack.c | 25 ++++ .../full_bisect_test/switch_to_bad.sh | 53 +++++++ .../full_bisect_test/switch_to_good.sh | 56 ++++++++ binary_search_tool/full_bisect_test/test_setup.sh | 16 +++ binary_search_tool/run_bisect_test.py | 155 +++++++++++++++++++++ 29 files changed, 968 insertions(+) create mode 100644 binary_search_tool/full_bisect_test/bad-objects-permanent/_LIST create mode 100644 binary_search_tool/full_bisect_test/bad-output-1.txt create mode 100644 binary_search_tool/full_bisect_test/bad-output-2.txt create mode 100644 binary_search_tool/full_bisect_test/bad-output-3.txt create mode 100644 binary_search_tool/full_bisect_test/bin-trees.h create mode 100644 binary_search_tool/full_bisect_test/build.c create mode 100755 binary_search_tool/full_bisect_test/build.sh create mode 100755 binary_search_tool/full_bisect_test/cleanup.sh create mode 100755 binary_search_tool/full_bisect_test/get_initial_items.sh create mode 100644 binary_search_tool/full_bisect_test/good-objects-permanent/_LIST create mode 100644 binary_search_tool/full_bisect_test/good-output.txt create mode 100644 binary_search_tool/full_bisect_test/inorder.c create mode 100644 binary_search_tool/full_bisect_test/inorder_norecurse.c.bad create mode 100644 binary_search_tool/full_bisect_test/inorder_norecurse.c.good create mode 100755 binary_search_tool/full_bisect_test/interactive_test.sh create mode 100755 binary_search_tool/full_bisect_test/main-bisect-test.sh create mode 100644 binary_search_tool/full_bisect_test/main.c create mode 100755 binary_search_tool/full_bisect_test/make_sources_bad.sh create mode 100755 binary_search_tool/full_bisect_test/make_sources_good.sh create mode 100644 binary_search_tool/full_bisect_test/preorder.c create mode 100644 binary_search_tool/full_bisect_test/preorder_norecurse.c.bad create mode 100644 binary_search_tool/full_bisect_test/preorder_norecurse.c.good create mode 100755 binary_search_tool/full_bisect_test/run-test-nowrapper.sh create mode 100755 binary_search_tool/full_bisect_test/setup.sh create mode 100644 binary_search_tool/full_bisect_test/stack.c create mode 100755 binary_search_tool/full_bisect_test/switch_to_bad.sh create mode 100755 binary_search_tool/full_bisect_test/switch_to_good.sh create mode 100755 binary_search_tool/full_bisect_test/test_setup.sh create mode 100755 binary_search_tool/run_bisect_test.py (limited to 'binary_search_tool') 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 +#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 +#include +#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 +#include +#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 +#include +#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 +#include +#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 +#include +#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 +#include +#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 +#include +#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 +#include +#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) -- cgit v1.2.3