{"thread":{"id":"973","subject":"[PATCH 1/1] git-bug-blatt-script - a script to automate bug finding using Linus' bug blatt algorithm.","startedAt":"2005-06-19T09:22:28Z","lastAt":"2005-06-19T09:22:28Z","messageCount":1,"participants":["Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"5034","messageId":"20050619092228.18175.qmail@blackcubes.dyndns.org","threadId":"973","inReplyTo":null,"subject":"[PATCH 1/1] git-bug-blatt-script - a script to automate bug finding using Linus' bug blatt algorithm.","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-19T09:22:28Z","receivedAt":"2005-06-19T09:22:28Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"\nThis script uses Linus' bug-blatt algorithm to locate a commit which introduced a bug.\n\nTo use this script you need to have the following:\n\n    - a script that will seek, build and install a specified commit\n    - a script that will test a build and determine whether it contains a bug\n\nAn example test script is included which will simulate an injected bug at a given\ncommit.\n\nTo run this test, use:\n\n    count=$(git-rev-list HEAD | wc -l)\n    root=$(git-rev-list HEAD | tail -1)\n    # choose an example, 1/3 of the way through the list.\n    bug=$(git-rev-list HEAD | head -$(echo $count 3 / | dc) | tail -1)\n    # use \"\" in second argument to specify a null build\n    git bug-blatt \"\" \"t/simulate-bug-at $bug\" HEAD $root 2>/dev/null\n\nA test case for git-bug-blatt-script has been included in t/t6002-bug-blatt.sh\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n---\n\n git-bug-blatt-script            |   91 +++++++++++++\n t/simulate-bug-at               |   11 ++\n t/t6002-git-bug-blatt-script.sh |  280 +++++++++++++++++++++++++++++++++++++++\n 3 files changed, 382 insertions(+), 0 deletions(-)\n\ndiff --git a/git-bug-blatt-script b/git-bug-blatt-script\nnew file mode 100755\n--- /dev/null\n+++ b/git-bug-blatt-script\n@@ -0,0 +1,91 @@\n+#!/bin/sh\n+#\n+# (C) Linus Torvalds, Jon Seymour 2005\n+#\n+# Based on an algorithm posted to the git-list by Linus\n+# Torvalds.\n+#\n+\n+die()\n+{\n+\techo \"$*\" 1>&2\n+\texit 1\n+}\n+\n+info()\n+{\n+    echo \"$@\" 1>&2\n+}\n+\n+build_commit()\n+{\n+\t_commit=$1\n+\tinfo -n \"build @ $_commit...\"\n+\t[ -n \"$build\" ] || build=\"echo\"\n+\tif eval \"$build $_commit\" >/dev/null 2>&1 \n+\tthen\n+\t    info \"ok\"\n+        else\n+\t    info \"bad\"\n+\t    die \"git-bug-blatt-script: build failed @ $_commit\"\n+        fi\n+}\n+\n+test_commit()\n+{\n+        _commit=$1\n+\tinfo -n \"test @ $_commit...\"\n+\teval \"$test $_commit\" >/dev/null 2>&1\n+\tif [ $? -eq 0 ]\n+\tthen\n+\t\tinfo \"ok\"\n+\t\treturn 0\n+\telse\n+\t\tinfo \"failed\"\n+\t\treturn 1\n+\tfi\t\t\t\t\n+}\n+\n+build=$1\n+test=$2\n+known_bad=$3\n+shift 3\n+known_goods=\"$*\"\n+\n+[ -n \"$known_goods\" ] || die \"usage: git-bug-blatt-script build-cmd test-cmd known-bad known-good ...\";\n+\n+(\n+build_commit $known_bad \n+test_commit $known_bad  && die \"$known_bad doesn't actually look bad - please check the test\"\t\n+\n+good_args=\"\"\n+for g in $known_goods\n+do\n+\tbuild_commit $g\n+\ttest_commit $g || die \"$g isn't actually good - please check the test\"\n+\tgood_args=${good_args}${good_args+ }^$g\n+done\n+\n+start_size=$(git-rev-list $known_bad $good_args | wc -l)\n+iterations=0\n+while true\n+do\n+\titerations=`expr $iterations + 1`\n+\tbisection=$(git-rev-list --bisect $known_bad $good_args)\n+\tif [ \"$bisection\" == \"$known_bad\" ] \t\n+\tthen\n+\t\tinfo \"bug found @ $bisection in $iterations iterations\" \n+\t\techo $bisection\n+\t\texit 0\n+\tfi\n+\tbuild_commit $bisection\n+\tif test_commit $bisection\n+\tthen\n+\t\tgood_args=${good_args}${good_args+ }\"^$bisection\"\n+\telse\n+\t\tknown_bad=${bisection}\t\t\n+\tfi\n+done\n+)\n+rc=$?\n+exit $rc\ndiff --git a/t/simulate-bug-at b/t/simulate-bug-at\nnew file mode 100755\n--- /dev/null\n+++ b/t/simulate-bug-at\n@@ -0,0 +1,11 @@\n+#!/bin/sh\n+bug=$1\n+commit=$2\n+if git-rev-list $commit | grep \"$bug\"\n+then\n+\techo \"simulated test failed at $commit\"\n+\texit 1;\n+else\n+        echo \"simulated test ok at $commit\"\n+\texit 0;\n+fi\ndiff --git a/t/t6002-git-bug-blatt-script.sh b/t/t6002-git-bug-blatt-script.sh\nnew file mode 100755\n--- /dev/null\n+++ b/t/t6002-git-bug-blatt-script.sh\n@@ -0,0 +1,280 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2005 Jon Seymour\n+#\n+\n+test_description='Tests git-bug-blatt and --bisect functionality'\n+\n+. ./test-lib.sh\n+\n+\n+on_committer_date()\n+{\n+    _date=$1\n+    shift 1\n+    GIT_COMMITTER_DATE=$_date \"$@\"\n+}\n+\n+#\n+# TODO: move the following block (upto --- end ...) into testlib.sh\n+#\n+[ -d .git/refs/tags ] || mkdir -p .git/refs/tags\n+\n+sed_script=\"\";\n+\n+# Answer the sha1 has associated with the tag. The tag must exist in .git or .git/refs/tags\n+tag()\n+{\n+\t_tag=$1\n+\t[ -f .git/refs/tags/$_tag ] || error \"tag: \\\"$_tag\\\" does not exist\"\n+\tcat .git/refs/tags/$_tag\n+}\n+\n+# Generate a commit using the text specified to make it unique and the tree\n+# named by the tag specified.\n+unique_commit()\n+{\n+\t_text=$1\n+        _tree=$2\n+\tshift 2\n+    \techo $_text | git-commit-tree $(tag $_tree) \"$@\"\n+}\n+\n+# Save the output of a command into the tag specified. Prepend\n+# a substitution script for the tag onto the front of $sed_script\n+save_tag()\n+{\n+\t_tag=$1\t\n+\t[ -n \"$_tag\" ] || error \"usage: save_tag tag commit-args ...\"\n+\tshift 1\n+    \t\"$@\" >.git/refs/tags/$_tag\n+    \tsed_script=\"s/$(tag $_tag)/$_tag/g${sed_script+;}$sed_script\"\n+}\n+\n+# Replace unhelpful sha1 hashses with their symbolic equivalents \n+entag()\n+{\n+\tsed \"$sed_script\"\n+}\n+\n+# Execute a command and suppress any error output.\n+hide_error()\n+{\n+\t\"$@\" 2>/dev/null\n+}\n+\n+check_output()\n+{\n+\t_name=$1\n+\tshift 1\n+\tif \"$@\" | entag > $_name.actual\n+\tthen\n+\t\tdiff $_name.expected $_name.actual\n+\telse\n+\t\treturn 1;\n+\tfi\n+\t\n+}\n+\n+# Turn a reasonable test description into a reasonable test name.\n+# All alphanums translated into -'s which are then compressed and stripped\n+# from front and back.\n+name_from_description()\n+{\n+        tr \"'\" '-' | tr '~`!@#$%^&*()_+={}[]|\\;:\"<>,/? ' '-' | tr -s '-' | tr '[A-Z]' '[a-z]' | sed \"s/^-*//;s/-*\\$//\"\n+}\n+\n+\n+# Execute the test described by the first argument, by eval'ing\n+# command line specified in the 2nd argument. Check the status code\n+# is zero and that the output matches the stream read from \n+# stdin.\n+test_output_expect_success()\n+{\t\n+\t_description=$1\n+        _test=$2\n+        [ $# -eq 2 ] || error \"usage: test_output_expect_success description test <<EOF ... EOF\"\n+        _name=$(echo $_description | name_from_description)\n+\tcat > $_name.expected\n+\ttest_expect_success \"$_description\" \"check_output $_name $_test\" \n+}\n+\n+# --- end of stuff to move ---\n+\n+date >path0\n+git-update-cache --add path0\n+save_tag tree git-write-tree\n+on_committer_date \"1971-08-16 00:00:00\" hide_error save_tag root unique_commit root tree\n+on_committer_date \"1971-08-16 00:00:01\" save_tag l0 unique_commit l0 tree -p root\n+on_committer_date \"1971-08-16 00:00:02\" save_tag l1 unique_commit l1 tree -p l0\n+on_committer_date \"1971-08-16 00:00:03\" save_tag l2 unique_commit l2 tree -p l1\n+on_committer_date \"1971-08-16 00:00:04\" save_tag a0 unique_commit a0 tree -p l2\n+on_committer_date \"1971-08-16 00:00:05\" save_tag a1 unique_commit a1 tree -p a0\n+on_committer_date \"1971-08-16 00:00:06\" save_tag b1 unique_commit b1 tree -p a0\n+on_committer_date \"1971-08-16 00:00:07\" save_tag c1 unique_commit c1 tree -p b1\n+on_committer_date \"1971-08-16 00:00:08\" save_tag b2 unique_commit b2 tree -p b1\n+on_committer_date \"1971-08-16 00:00:09\" save_tag b3 unique_commit b2 tree -p b2\n+on_committer_date \"1971-08-16 00:00:10\" save_tag c2 unique_commit c2 tree -p c1 -p b2\n+on_committer_date \"1971-08-16 00:00:11\" save_tag c3 unique_commit c3 tree -p c2\n+on_committer_date \"1971-08-16 00:00:12\" save_tag a2 unique_commit a2 tree -p a1\n+on_committer_date \"1971-08-16 00:00:13\" save_tag a3 unique_commit a3 tree -p a2\n+on_committer_date \"1971-08-16 00:00:14\" save_tag b4 unique_commit b4 tree -p b3 -p a3\n+on_committer_date \"1971-08-16 00:00:15\" save_tag a4 unique_commit a4 tree -p a3 -p b4 -p c3\n+on_committer_date \"1971-08-16 00:00:16\" save_tag l3 unique_commit l3 tree -p a4\n+on_committer_date \"1971-08-16 00:00:17\" save_tag l4 unique_commit l4 tree -p l3\n+on_committer_date \"1971-08-16 00:00:18\" save_tag l5 unique_commit l5 tree -p l4\n+tag l5 > .git/HEAD\n+\n+\n+#     E\n+#    / \\\n+#   e1  |\n+#   |   |\n+#   e2  |\n+#   |   |\n+#   e3  |\n+#   |   |\n+#   e4  |\n+#   |   |\n+#   |   f1\n+#   |   |\n+#   |   f2\n+#   |   |\n+#   |   f3\n+#   |   |\n+#   |   f4\n+#   |   |\n+#   e5  |\n+#   |   |\n+#   e6  |\n+#   |   |\n+#   e7  |\n+#   |   |\n+#   e8  |\n+#    \\ /\n+#     F\n+\n+\n+on_committer_date \"1971-08-16 00:00:00\" hide_error save_tag F unique_commit F tree\n+on_committer_date \"1971-08-16 00:00:01\" save_tag e8 unique_commit e8 tree -p F\n+on_committer_date \"1971-08-16 00:00:02\" save_tag e7 unique_commit e7 tree -p e8\n+on_committer_date \"1971-08-16 00:00:03\" save_tag e6 unique_commit e6 tree -p e7\n+on_committer_date \"1971-08-16 00:00:04\" save_tag e5 unique_commit e5 tree -p e6\n+on_committer_date \"1971-08-16 00:00:05\" save_tag f4 unique_commit f4 tree -p F\n+on_committer_date \"1971-08-16 00:00:06\" save_tag f3 unique_commit f3 tree -p f4\n+on_committer_date \"1971-08-16 00:00:07\" save_tag f2 unique_commit f2 tree -p f3\n+on_committer_date \"1971-08-16 00:00:08\" save_tag f1 unique_commit f1 tree -p f2\n+on_committer_date \"1971-08-16 00:00:09\" save_tag e4 unique_commit e4 tree -p e5\n+on_committer_date \"1971-08-16 00:00:10\" save_tag e3 unique_commit e3 tree -p e4\n+on_committer_date \"1971-08-16 00:00:11\" save_tag e2 unique_commit e2 tree -p e3\n+on_committer_date \"1971-08-16 00:00:12\" save_tag e1 unique_commit e1 tree -p e2\n+on_committer_date \"1971-08-16 00:00:13\" save_tag E unique_commit E tree -p e1 -p f1\n+\n+\n+test_bug_blatt()\n+{\n+     _bug=$1\n+     shift 1\n+     git bug-blatt '' \"../simulate-bug-at $_bug\" \"$@\" 2>/dev/null\n+}\n+\n+#\n+# cd to t/trash and use \n+#\n+#    git-rev-list ... 2>&1 | sed \"$(cat sed.script)\" \n+#\n+# if you ever want to manually debug the operation of git-rev-list\n+#\n+echo $sed_script > sed.script\n+\n+#\n+# the following illustrate's Linus' binary bug blatt idea. \n+#\n+# assume the bug is actually at l3, but you don't know that - all you know is that l3 is broken\n+# and it wasn't broken before\n+#\n+# keep bisecting the list, advancing the \"bad\" head and accumulating \"good\" heads until\n+# the bisection point is the head - this is the bad point.\n+#\n+\n+test_output_expect_success \"--bisect l5 ^root\" 'git-rev-list --bisect l5 ^root' <<EOF\n+c3\n+EOF\n+\n+test_output_expect_success \"--bisect l5 ^root ^c3\" 'git-rev-list --bisect l5 ^root ^c3' <<EOF\n+b4\n+EOF\n+\n+test_output_expect_success \"--bisect l5 ^root ^c3 ^b4\" 'git-rev-list --bisect l5 ^c3 ^b4' <<EOF\n+l3\n+EOF\n+\n+test_output_expect_success \"--bisect l3 ^root ^c3 ^b4\" 'git-rev-list --bisect l3 ^root ^c3 ^b4' <<EOF\n+a4\n+EOF\n+\n+test_output_expect_success \"--bisect l5 ^b3 ^a3 ^b4 ^a4\" 'git-rev-list --bisect l3 ^b3 ^a3 ^a4' <<EOF\n+l3\n+EOF\n+\n+#\n+# if l3 is bad, then l4 is bad too - so advance the bad pointer by making b4 the known bad head\n+#\n+\n+test_output_expect_success \"--bisect l4 ^a2 ^a3 ^b ^a4\" 'git-rev-list --bisect l4 ^a2 ^a3 ^a4' <<EOF\n+l3\n+EOF\n+\n+test_output_expect_success \"--bisect l3 ^a2 ^a3 ^b ^a4\" 'git-rev-list --bisect l3 ^a2 ^a3 ^a4' <<EOF\n+l3\n+EOF\n+\n+# found!\n+\n+#\n+# as another example, let's consider a4 to be the bad head, in which case\n+#\n+\n+test_output_expect_success \"--bisect a4 ^a2 ^a3 ^b4\" 'git-rev-list --bisect a4 ^a2 ^a3 ^b4' <<EOF\n+c2\n+EOF\n+\n+test_output_expect_success \"--bisect a4 ^a2 ^a3 ^b4 ^c2\" 'git-rev-list --bisect a4 ^a2 ^a3 ^b4 ^c2' <<EOF\n+c3\n+EOF\n+\n+test_output_expect_success \"--bisect a4 ^a2 ^a3 ^b4 ^c2 ^c3\" 'git-rev-list --bisect a4 ^a2 ^a3 ^b4 ^c2 ^c3' <<EOF\n+a4\n+EOF\n+\n+# found!\n+\n+#\n+# or consider c3 to be the bad head\n+#\n+\n+test_output_expect_success \"--bisect a4 ^a2 ^a3 ^b4\" 'git-rev-list --bisect a4 ^a2 ^a3 ^b4' <<EOF\n+c2\n+EOF\n+\n+test_output_expect_success \"--bisect c3 ^a2 ^a3 ^b4 ^c2\" 'git-rev-list --bisect c3 ^a2 ^a3 ^b4 ^c2' <<EOF\n+c3\n+EOF\n+\n+# found!\n+\n+test_output_expect_success \"bug-blatt l5 @ l3\" \"test_bug_blatt $(tag l3) $(tag l5) root\" <<EOF\n+l3\n+EOF\n+\n+test_output_expect_success \"bug-blatt l5 @ a4\" \"test_bug_blatt $(tag a4) $(tag l5) root\" <<EOF\n+a4\n+EOF\n+\n+test_output_expect_success \"bug-blatt l5 @ c3\" \"test_bug_blatt $(tag c3) $(tag l5) root\" <<EOF\n+c3\n+EOF\n+\n+#\n+#\n+test_done\n------------\n"}]}