Andrew's git - gitweb.git/blob - t/t6002-rev-list-bisect.sh

   1#!/bin/sh
   2#
   3# Copyright (c) 2005 Jon Seymour
   4#
   5test_description='Tests git-rev-list --bisect functionality'
   6
   7. ./test-lib.sh
   8. ../t6000lib.sh # t6xxx specific functions
   9
  10# usage: test_bisection max-diff bisect-option head ^prune...
  11#
  12# e.g. test_bisection 1 --bisect l1 ^l0
  13#
  14test_bisection_diff()
  15{
  16        _max_diff=$1
  17        _bisect_option=$2
  18        shift 2
  19        _bisection=$(git-rev-list $_bisect_option "$@")
  20        _list_size=$(git-rev-list "$@" | wc -l)
  21        _head=$1
  22        shift 1
  23        _bisection_size=$(git-rev-list $_bisection "$@" | wc -l)
  24        [ -n "$_list_size" -a -n "$_bisection_size" ] ||
  25        error "test_bisection_diff failed"
  26
  27        # Test if bisection size is close to half of list size within
  28        # tolerance.
  29        # 
  30        _bisect_err=`expr $_list_size - $_bisection_size \* 2`
  31        test "$_bisect_err" -lt 0 && _bisect_err=`expr 0 - $_bisect_err`
  32        _bisect_err=`expr $_bisect_err / 2` ; # floor
  33
  34        test_expect_success \
  35        "bisection diff $_bisect_option $_head $* <= $_max_diff" \
  36        'test $_bisect_err -le $_max_diff'
  37}
  38
  39date >path0
  40git-update-index --add path0
  41save_tag tree git-write-tree
  42on_committer_date "1971-08-16 00:00:00" hide_error save_tag root unique_commit root tree
  43on_committer_date "1971-08-16 00:00:01" save_tag l0 unique_commit l0 tree -p root
  44on_committer_date "1971-08-16 00:00:02" save_tag l1 unique_commit l1 tree -p l0
  45on_committer_date "1971-08-16 00:00:03" save_tag l2 unique_commit l2 tree -p l1
  46on_committer_date "1971-08-16 00:00:04" save_tag a0 unique_commit a0 tree -p l2
  47on_committer_date "1971-08-16 00:00:05" save_tag a1 unique_commit a1 tree -p a0
  48on_committer_date "1971-08-16 00:00:06" save_tag b1 unique_commit b1 tree -p a0
  49on_committer_date "1971-08-16 00:00:07" save_tag c1 unique_commit c1 tree -p b1
  50on_committer_date "1971-08-16 00:00:08" save_tag b2 unique_commit b2 tree -p b1
  51on_committer_date "1971-08-16 00:00:09" save_tag b3 unique_commit b2 tree -p b2
  52on_committer_date "1971-08-16 00:00:10" save_tag c2 unique_commit c2 tree -p c1 -p b2
  53on_committer_date "1971-08-16 00:00:11" save_tag c3 unique_commit c3 tree -p c2
  54on_committer_date "1971-08-16 00:00:12" save_tag a2 unique_commit a2 tree -p a1
  55on_committer_date "1971-08-16 00:00:13" save_tag a3 unique_commit a3 tree -p a2
  56on_committer_date "1971-08-16 00:00:14" save_tag b4 unique_commit b4 tree -p b3 -p a3
  57on_committer_date "1971-08-16 00:00:15" save_tag a4 unique_commit a4 tree -p a3 -p b4 -p c3
  58on_committer_date "1971-08-16 00:00:16" save_tag l3 unique_commit l3 tree -p a4
  59on_committer_date "1971-08-16 00:00:17" save_tag l4 unique_commit l4 tree -p l3
  60on_committer_date "1971-08-16 00:00:18" save_tag l5 unique_commit l5 tree -p l4
  61git-update-ref HEAD $(tag l5)
  62
  63
  64#     E
  65#    / \
  66#   e1  |
  67#   |   |
  68#   e2  |
  69#   |   |
  70#   e3  |
  71#   |   |
  72#   e4  |
  73#   |   |
  74#   |   f1
  75#   |   |
  76#   |   f2
  77#   |   |
  78#   |   f3
  79#   |   |
  80#   |   f4
  81#   |   |
  82#   e5  |
  83#   |   |
  84#   e6  |
  85#   |   |
  86#   e7  |
  87#   |   |
  88#   e8  |
  89#    \ /
  90#     F
  91
  92
  93on_committer_date "1971-08-16 00:00:00" hide_error save_tag F unique_commit F tree
  94on_committer_date "1971-08-16 00:00:01" save_tag e8 unique_commit e8 tree -p F
  95on_committer_date "1971-08-16 00:00:02" save_tag e7 unique_commit e7 tree -p e8
  96on_committer_date "1971-08-16 00:00:03" save_tag e6 unique_commit e6 tree -p e7
  97on_committer_date "1971-08-16 00:00:04" save_tag e5 unique_commit e5 tree -p e6
  98on_committer_date "1971-08-16 00:00:05" save_tag f4 unique_commit f4 tree -p F
  99on_committer_date "1971-08-16 00:00:06" save_tag f3 unique_commit f3 tree -p f4
 100on_committer_date "1971-08-16 00:00:07" save_tag f2 unique_commit f2 tree -p f3
 101on_committer_date "1971-08-16 00:00:08" save_tag f1 unique_commit f1 tree -p f2
 102on_committer_date "1971-08-16 00:00:09" save_tag e4 unique_commit e4 tree -p e5
 103on_committer_date "1971-08-16 00:00:10" save_tag e3 unique_commit e3 tree -p e4
 104on_committer_date "1971-08-16 00:00:11" save_tag e2 unique_commit e2 tree -p e3
 105on_committer_date "1971-08-16 00:00:12" save_tag e1 unique_commit e1 tree -p e2
 106on_committer_date "1971-08-16 00:00:13" save_tag E unique_commit E tree -p e1 -p f1
 107
 108on_committer_date "1971-08-16 00:00:00" hide_error save_tag U unique_commit U tree
 109on_committer_date "1971-08-16 00:00:01" save_tag u0 unique_commit u0 tree -p U
 110on_committer_date "1971-08-16 00:00:01" save_tag u1 unique_commit u1 tree -p u0
 111on_committer_date "1971-08-16 00:00:02" save_tag u2 unique_commit u2 tree -p u0
 112on_committer_date "1971-08-16 00:00:03" save_tag u3 unique_commit u3 tree -p u0
 113on_committer_date "1971-08-16 00:00:04" save_tag u4 unique_commit u4 tree -p u0
 114on_committer_date "1971-08-16 00:00:05" save_tag u5 unique_commit u5 tree -p u0
 115on_committer_date "1971-08-16 00:00:06" save_tag V unique_commit V tree -p u1 -p u2 -p u3 -p u4 -p u5
 116
 117test_sequence()
 118{
 119        _bisect_option=$1       
 120        
 121        test_bisection_diff 0 $_bisect_option l0 ^root
 122        test_bisection_diff 0 $_bisect_option l1 ^root
 123        test_bisection_diff 0 $_bisect_option l2 ^root
 124        test_bisection_diff 0 $_bisect_option a0 ^root
 125        test_bisection_diff 0 $_bisect_option a1 ^root
 126        test_bisection_diff 0 $_bisect_option a2 ^root
 127        test_bisection_diff 0 $_bisect_option a3 ^root
 128        test_bisection_diff 0 $_bisect_option b1 ^root
 129        test_bisection_diff 0 $_bisect_option b2 ^root
 130        test_bisection_diff 0 $_bisect_option b3 ^root
 131        test_bisection_diff 0 $_bisect_option c1 ^root
 132        test_bisection_diff 0 $_bisect_option c2 ^root
 133        test_bisection_diff 0 $_bisect_option c3 ^root
 134        test_bisection_diff 0 $_bisect_option E ^F
 135        test_bisection_diff 0 $_bisect_option e1 ^F
 136        test_bisection_diff 0 $_bisect_option e2 ^F
 137        test_bisection_diff 0 $_bisect_option e3 ^F
 138        test_bisection_diff 0 $_bisect_option e4 ^F
 139        test_bisection_diff 0 $_bisect_option e5 ^F
 140        test_bisection_diff 0 $_bisect_option e6 ^F
 141        test_bisection_diff 0 $_bisect_option e7 ^F
 142        test_bisection_diff 0 $_bisect_option f1 ^F
 143        test_bisection_diff 0 $_bisect_option f2 ^F
 144        test_bisection_diff 0 $_bisect_option f3 ^F
 145        test_bisection_diff 0 $_bisect_option f4 ^F
 146        test_bisection_diff 0 $_bisect_option E ^F
 147
 148        test_bisection_diff 1 $_bisect_option V ^U
 149        test_bisection_diff 0 $_bisect_option V ^U ^u1 ^u2 ^u3
 150        test_bisection_diff 0 $_bisect_option u1 ^U
 151        test_bisection_diff 0 $_bisect_option u2 ^U
 152        test_bisection_diff 0 $_bisect_option u3 ^U
 153        test_bisection_diff 0 $_bisect_option u4 ^U
 154        test_bisection_diff 0 $_bisect_option u5 ^U
 155        
 156#
 157# the following illustrates Linus' binary bug blatt idea.
 158#
 159# assume the bug is actually at l3, but you don't know that - all you know is that l3 is broken
 160# and it wasn't broken before
 161#
 162# keep bisecting the list, advancing the "bad" head and accumulating "good" heads until
 163# the bisection point is the head - this is the bad point.
 164#
 165
 166test_output_expect_success "$_bisect_option l5 ^root" 'git-rev-list $_bisect_option l5 ^root' <<EOF
 167c3
 168EOF
 169
 170test_output_expect_success "$_bisect_option l5 ^root ^c3" 'git-rev-list $_bisect_option l5 ^root ^c3' <<EOF
 171b4
 172EOF
 173
 174test_output_expect_success "$_bisect_option l5 ^root ^c3 ^b4" 'git-rev-list $_bisect_option l5 ^c3 ^b4' <<EOF
 175l3
 176EOF
 177
 178test_output_expect_success "$_bisect_option l3 ^root ^c3 ^b4" 'git-rev-list $_bisect_option l3 ^root ^c3 ^b4' <<EOF
 179a4
 180EOF
 181
 182test_output_expect_success "$_bisect_option l5 ^b3 ^a3 ^b4 ^a4" 'git-rev-list $_bisect_option l3 ^b3 ^a3 ^a4' <<EOF
 183l3
 184EOF
 185
 186#
 187# if l3 is bad, then l4 is bad too - so advance the bad pointer by making b4 the known bad head
 188#
 189
 190test_output_expect_success "$_bisect_option l4 ^a2 ^a3 ^b ^a4" 'git-rev-list $_bisect_option l4 ^a2 ^a3 ^a4' <<EOF
 191l3
 192EOF
 193
 194test_output_expect_success "$_bisect_option l3 ^a2 ^a3 ^b ^a4" 'git-rev-list $_bisect_option l3 ^a2 ^a3 ^a4' <<EOF
 195l3
 196EOF
 197
 198# found!
 199
 200#
 201# as another example, let's consider a4 to be the bad head, in which case
 202#
 203
 204test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
 205c2
 206EOF
 207
 208test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2' <<EOF
 209c3
 210EOF
 211
 212test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3' <<EOF
 213a4
 214EOF
 215
 216# found!
 217
 218#
 219# or consider c3 to be the bad head
 220#
 221
 222test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
 223c2
 224EOF
 225
 226test_output_expect_success "$_bisect_option c3 ^a2 ^a3 ^b4 ^c2" 'git-rev-list $_bisect_option c3 ^a2 ^a3 ^b4 ^c2' <<EOF
 227c3
 228EOF
 229
 230# found!
 231
 232}
 233
 234test_sequence "--bisect"
 235
 236#
 237#
 238test_done