t/t6002-rev-list-bisect.sh

   1 #!/bin/sh
   2 #
   3 # Copyright (c) 2005 Jon Seymour
   4 #
   5 test_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 #
  14 test_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
  39 date >path0
  40 git update-index --add path0
  41 save_tag tree git write-tree
  42 on_committer_date "1971-08-16 00:00:00" hide_error save_tag root unique_commit root tree
  43 on_committer_date "1971-08-16 00:00:01" save_tag l0 unique_commit l0 tree -p root
  44 on_committer_date "1971-08-16 00:00:02" save_tag l1 unique_commit l1 tree -p l0
  45 on_committer_date "1971-08-16 00:00:03" save_tag l2 unique_commit l2 tree -p l1
  46 on_committer_date "1971-08-16 00:00:04" save_tag a0 unique_commit a0 tree -p l2
  47 on_committer_date "1971-08-16 00:00:05" save_tag a1 unique_commit a1 tree -p a0
  48 on_committer_date "1971-08-16 00:00:06" save_tag b1 unique_commit b1 tree -p a0
  49 on_committer_date "1971-08-16 00:00:07" save_tag c1 unique_commit c1 tree -p b1
  50 on_committer_date "1971-08-16 00:00:08" save_tag b2 unique_commit b2 tree -p b1
  51 on_committer_date "1971-08-16 00:00:09" save_tag b3 unique_commit b2 tree -p b2
  52 on_committer_date "1971-08-16 00:00:10" save_tag c2 unique_commit c2 tree -p c1 -p b2
  53 on_committer_date "1971-08-16 00:00:11" save_tag c3 unique_commit c3 tree -p c2
  54 on_committer_date "1971-08-16 00:00:12" save_tag a2 unique_commit a2 tree -p a1
  55 on_committer_date "1971-08-16 00:00:13" save_tag a3 unique_commit a3 tree -p a2
  56 on_committer_date "1971-08-16 00:00:14" save_tag b4 unique_commit b4 tree -p b3 -p a3
  57 on_committer_date "1971-08-16 00:00:15" save_tag a4 unique_commit a4 tree -p a3 -p b4 -p c3
  58 on_committer_date "1971-08-16 00:00:16" save_tag l3 unique_commit l3 tree -p a4
  59 on_committer_date "1971-08-16 00:00:17" save_tag l4 unique_commit l4 tree -p l3
  60 on_committer_date "1971-08-16 00:00:18" save_tag l5 unique_commit l5 tree -p l4
  61 git 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
  93 on_committer_date "1971-08-16 00:00:00" hide_error save_tag F unique_commit F tree
  94 on_committer_date "1971-08-16 00:00:01" save_tag e8 unique_commit e8 tree -p F
  95 on_committer_date "1971-08-16 00:00:02" save_tag e7 unique_commit e7 tree -p e8
  96 on_committer_date "1971-08-16 00:00:03" save_tag e6 unique_commit e6 tree -p e7
  97 on_committer_date "1971-08-16 00:00:04" save_tag e5 unique_commit e5 tree -p e6
  98 on_committer_date "1971-08-16 00:00:05" save_tag f4 unique_commit f4 tree -p F
  99 on_committer_date "1971-08-16 00:00:06" save_tag f3 unique_commit f3 tree -p f4
 100 on_committer_date "1971-08-16 00:00:07" save_tag f2 unique_commit f2 tree -p f3
 101 on_committer_date "1971-08-16 00:00:08" save_tag f1 unique_commit f1 tree -p f2
 102 on_committer_date "1971-08-16 00:00:09" save_tag e4 unique_commit e4 tree -p e5
 103 on_committer_date "1971-08-16 00:00:10" save_tag e3 unique_commit e3 tree -p e4
 104 on_committer_date "1971-08-16 00:00:11" save_tag e2 unique_commit e2 tree -p e3
 105 on_committer_date "1971-08-16 00:00:12" save_tag e1 unique_commit e1 tree -p e2
 106 on_committer_date "1971-08-16 00:00:13" save_tag E unique_commit E tree -p e1 -p f1
 107
 108 on_committer_date "1971-08-16 00:00:00" hide_error save_tag U unique_commit U tree
 109 on_committer_date "1971-08-16 00:00:01" save_tag u0 unique_commit u0 tree -p U
 110 on_committer_date "1971-08-16 00:00:01" save_tag u1 unique_commit u1 tree -p u0
 111 on_committer_date "1971-08-16 00:00:02" save_tag u2 unique_commit u2 tree -p u0
 112 on_committer_date "1971-08-16 00:00:03" save_tag u3 unique_commit u3 tree -p u0
 113 on_committer_date "1971-08-16 00:00:04" save_tag u4 unique_commit u4 tree -p u0
 114 on_committer_date "1971-08-16 00:00:05" save_tag u5 unique_commit u5 tree -p u0
 115 on_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
 117 test_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
 166 test_output_expect_success "$_bisect_option l5 ^root" 'git rev-list $_bisect_option l5 ^root' <<EOF
 167 c3
 168 EOF
 169
 170 test_output_expect_success "$_bisect_option l5 ^root ^c3" 'git rev-list $_bisect_option l5 ^root ^c3' <<EOF
 171 b4
 172 EOF
 173
 174 test_output_expect_success "$_bisect_option l5 ^root ^c3 ^b4" 'git rev-list $_bisect_option l5 ^c3 ^b4' <<EOF
 175 l3
 176 EOF
 177
 178 test_output_expect_success "$_bisect_option l3 ^root ^c3 ^b4" 'git rev-list $_bisect_option l3 ^root ^c3 ^b4' <<EOF
 179 a4
 180 EOF
 181
 182 test_output_expect_success "$_bisect_option l5 ^b3 ^a3 ^b4 ^a4" 'git rev-list $_bisect_option l3 ^b3 ^a3 ^a4' <<EOF
 183 l3
 184 EOF
 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
 190 test_output_expect_success "$_bisect_option l4 ^a2 ^a3 ^b ^a4" 'git rev-list $_bisect_option l4 ^a2 ^a3 ^a4' <<EOF
 191 l3
 192 EOF
 193
 194 test_output_expect_success "$_bisect_option l3 ^a2 ^a3 ^b ^a4" 'git rev-list $_bisect_option l3 ^a2 ^a3 ^a4' <<EOF
 195 l3
 196 EOF
 197
 198 # found!
 199
 200 #
 201 # as another example, let's consider a4 to be the bad head, in which case
 202 #
 203
 204 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
 205 c2
 206 EOF
 207
 208 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2" 'git rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2' <<EOF
 209 c3
 210 EOF
 211
 212 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3" 'git rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3' <<EOF
 213 a4
 214 EOF
 215
 216 # found!
 217
 218 #
 219 # or consider c3 to be the bad head
 220 #
 221
 222 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
 223 c2
 224 EOF
 225
 226 test_output_expect_success "$_bisect_option c3 ^a2 ^a3 ^b4 ^c2" 'git rev-list $_bisect_option c3 ^a2 ^a3 ^b4 ^c2' <<EOF
 227 c3
 228 EOF
 229
 230 # found!
 231
 232 }
 233
 234 test_sequence "--bisect"
 235
 236 #
 237 #
 238 test_done