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_PASSES_SANITIZE_LEAK=true
   8 . ./test-lib.sh
   9 . "$TEST_DIRECTORY"/lib-t6000.sh # t6xxx specific functions
  10
  11 # usage: test_bisection max-diff bisect-option head ^prune...
  12 #
  13 # e.g. test_bisection 1 --bisect l1 ^l0
  14 #
  15 test_bisection_diff()
  16 {
  17         _max_diff=$1
  18         _bisect_option=$2
  19         shift 2
  20         _bisection=$(git rev-list $_bisect_option "$@")
  21         _list_size=$(git rev-list "$@" | wc -l)
  22         _head=$1
  23         shift 1
  24         _bisection_size=$(git rev-list $_bisection "$@" | wc -l)
  25         [ -n "$_list_size" -a -n "$_bisection_size" ] ||
  26         error "test_bisection_diff failed"
  27
  28         # Test if bisection size is close to half of list size within
  29         # tolerance.
  30         #
  31         _bisect_err=$(expr $_list_size - $_bisection_size \* 2)
  32         test "$_bisect_err" -lt 0 && _bisect_err=$(expr 0 - $_bisect_err)
  33         _bisect_err=$(expr $_bisect_err / 2) ; # floor
  34
  35         test_expect_success \
  36         "bisection diff $_bisect_option $_head $* <= $_max_diff" \
  37         'test $_bisect_err -le $_max_diff'
  38 }
  39
  40 date >path0
  41 git update-index --add path0
  42 save_tag tree git write-tree
  43 on_committer_date "00:00" hide_error save_tag root unique_commit root tree
  44 on_committer_date "00:01" save_tag l0 unique_commit l0 tree -p root
  45 on_committer_date "00:02" save_tag l1 unique_commit l1 tree -p l0
  46 on_committer_date "00:03" save_tag l2 unique_commit l2 tree -p l1
  47 on_committer_date "00:04" save_tag a0 unique_commit a0 tree -p l2
  48 on_committer_date "00:05" save_tag a1 unique_commit a1 tree -p a0
  49 on_committer_date "00:06" save_tag b1 unique_commit b1 tree -p a0
  50 on_committer_date "00:07" save_tag c1 unique_commit c1 tree -p b1
  51 on_committer_date "00:08" save_tag b2 unique_commit b2 tree -p b1
  52 on_committer_date "00:09" save_tag b3 unique_commit b2 tree -p b2
  53 on_committer_date "00:10" save_tag c2 unique_commit c2 tree -p c1 -p b2
  54 on_committer_date "00:11" save_tag c3 unique_commit c3 tree -p c2
  55 on_committer_date "00:12" save_tag a2 unique_commit a2 tree -p a1
  56 on_committer_date "00:13" save_tag a3 unique_commit a3 tree -p a2
  57 on_committer_date "00:14" save_tag b4 unique_commit b4 tree -p b3 -p a3
  58 on_committer_date "00:15" save_tag a4 unique_commit a4 tree -p a3 -p b4 -p c3
  59 on_committer_date "00:16" save_tag l3 unique_commit l3 tree -p a4
  60 on_committer_date "00:17" save_tag l4 unique_commit l4 tree -p l3
  61 on_committer_date "00:18" save_tag l5 unique_commit l5 tree -p l4
  62 git update-ref HEAD $(tag l5)
  63
  64
  65 #     E
  66 #    / \
  67 #   e1  |
  68 #   |   |
  69 #   e2  |
  70 #   |   |
  71 #   e3  |
  72 #   |   |
  73 #   e4  |
  74 #   |   |
  75 #   |   f1
  76 #   |   |
  77 #   |   f2
  78 #   |   |
  79 #   |   f3
  80 #   |   |
  81 #   |   f4
  82 #   |   |
  83 #   e5  |
  84 #   |   |
  85 #   e6  |
  86 #   |   |
  87 #   e7  |
  88 #   |   |
  89 #   e8  |
  90 #    \ /
  91 #     F
  92
  93
  94 on_committer_date "00:00" hide_error save_tag F unique_commit F tree
  95 on_committer_date "00:01" save_tag e8 unique_commit e8 tree -p F
  96 on_committer_date "00:02" save_tag e7 unique_commit e7 tree -p e8
  97 on_committer_date "00:03" save_tag e6 unique_commit e6 tree -p e7
  98 on_committer_date "00:04" save_tag e5 unique_commit e5 tree -p e6
  99 on_committer_date "00:05" save_tag f4 unique_commit f4 tree -p F
 100 on_committer_date "00:06" save_tag f3 unique_commit f3 tree -p f4
 101 on_committer_date "00:07" save_tag f2 unique_commit f2 tree -p f3
 102 on_committer_date "00:08" save_tag f1 unique_commit f1 tree -p f2
 103 on_committer_date "00:09" save_tag e4 unique_commit e4 tree -p e5
 104 on_committer_date "00:10" save_tag e3 unique_commit e3 tree -p e4
 105 on_committer_date "00:11" save_tag e2 unique_commit e2 tree -p e3
 106 on_committer_date "00:12" save_tag e1 unique_commit e1 tree -p e2
 107 on_committer_date "00:13" save_tag E unique_commit E tree -p e1 -p f1
 108
 109 on_committer_date "00:00" hide_error save_tag U unique_commit U tree
 110 on_committer_date "00:01" save_tag u0 unique_commit u0 tree -p U
 111 on_committer_date "00:01" save_tag u1 unique_commit u1 tree -p u0
 112 on_committer_date "00:02" save_tag u2 unique_commit u2 tree -p u0
 113 on_committer_date "00:03" save_tag u3 unique_commit u3 tree -p u0
 114 on_committer_date "00:04" save_tag u4 unique_commit u4 tree -p u0
 115 on_committer_date "00:05" save_tag u5 unique_commit u5 tree -p u0
 116 on_committer_date "00:06" save_tag V unique_commit V tree -p u1 -p u2 -p u3 -p u4 -p u5
 117
 118 test_sequence()
 119 {
 120         _bisect_option=$1
 121
 122         test_bisection_diff 0 $_bisect_option l0 ^root
 123         test_bisection_diff 0 $_bisect_option l1 ^root
 124         test_bisection_diff 0 $_bisect_option l2 ^root
 125         test_bisection_diff 0 $_bisect_option a0 ^root
 126         test_bisection_diff 0 $_bisect_option a1 ^root
 127         test_bisection_diff 0 $_bisect_option a2 ^root
 128         test_bisection_diff 0 $_bisect_option a3 ^root
 129         test_bisection_diff 0 $_bisect_option b1 ^root
 130         test_bisection_diff 0 $_bisect_option b2 ^root
 131         test_bisection_diff 0 $_bisect_option b3 ^root
 132         test_bisection_diff 0 $_bisect_option c1 ^root
 133         test_bisection_diff 0 $_bisect_option c2 ^root
 134         test_bisection_diff 0 $_bisect_option c3 ^root
 135         test_bisection_diff 0 $_bisect_option E ^F
 136         test_bisection_diff 0 $_bisect_option e1 ^F
 137         test_bisection_diff 0 $_bisect_option e2 ^F
 138         test_bisection_diff 0 $_bisect_option e3 ^F
 139         test_bisection_diff 0 $_bisect_option e4 ^F
 140         test_bisection_diff 0 $_bisect_option e5 ^F
 141         test_bisection_diff 0 $_bisect_option e6 ^F
 142         test_bisection_diff 0 $_bisect_option e7 ^F
 143         test_bisection_diff 0 $_bisect_option f1 ^F
 144         test_bisection_diff 0 $_bisect_option f2 ^F
 145         test_bisection_diff 0 $_bisect_option f3 ^F
 146         test_bisection_diff 0 $_bisect_option f4 ^F
 147         test_bisection_diff 0 $_bisect_option E ^F
 148
 149         test_bisection_diff 1 $_bisect_option V ^U
 150         test_bisection_diff 0 $_bisect_option V ^U ^u1 ^u2 ^u3
 151         test_bisection_diff 0 $_bisect_option u1 ^U
 152         test_bisection_diff 0 $_bisect_option u2 ^U
 153         test_bisection_diff 0 $_bisect_option u3 ^U
 154         test_bisection_diff 0 $_bisect_option u4 ^U
 155         test_bisection_diff 0 $_bisect_option u5 ^U
 156
 157 #
 158 # the following illustrates Linus' binary bug blatt idea.
 159 #
 160 # assume the bug is actually at l3, but you don't know that - all you know is that l3 is broken
 161 # and it wasn't broken before
 162 #
 163 # keep bisecting the list, advancing the "bad" head and accumulating "good" heads until
 164 # the bisection point is the head - this is the bad point.
 165 #
 166
 167 test_output_expect_success "$_bisect_option l5 ^root" 'git rev-list $_bisect_option l5 ^root' <<EOF
 168 c3
 169 EOF
 170
 171 test_output_expect_success "$_bisect_option l5 ^root ^c3" 'git rev-list $_bisect_option l5 ^root ^c3' <<EOF
 172 b4
 173 EOF
 174
 175 test_output_expect_success "$_bisect_option l5 ^root ^c3 ^b4" 'git rev-list $_bisect_option l5 ^c3 ^b4' <<EOF
 176 l3
 177 EOF
 178
 179 test_output_expect_success "$_bisect_option l3 ^root ^c3 ^b4" 'git rev-list $_bisect_option l3 ^root ^c3 ^b4' <<EOF
 180 a4
 181 EOF
 182
 183 test_output_expect_success "$_bisect_option l5 ^b3 ^a3 ^b4 ^a4" 'git rev-list $_bisect_option l3 ^b3 ^a3 ^a4' <<EOF
 184 l3
 185 EOF
 186
 187 #
 188 # if l3 is bad, then l4 is bad too - so advance the bad pointer by making b4 the known bad head
 189 #
 190
 191 test_output_expect_success "$_bisect_option l4 ^a2 ^a3 ^b ^a4" 'git rev-list $_bisect_option l4 ^a2 ^a3 ^a4' <<EOF
 192 l3
 193 EOF
 194
 195 test_output_expect_success "$_bisect_option l3 ^a2 ^a3 ^b ^a4" 'git rev-list $_bisect_option l3 ^a2 ^a3 ^a4' <<EOF
 196 l3
 197 EOF
 198
 199 # found!
 200
 201 #
 202 # as another example, let's consider a4 to be the bad head, in which case
 203 #
 204
 205 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
 206 c2
 207 EOF
 208
 209 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2" 'git rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2' <<EOF
 210 c3
 211 EOF
 212
 213 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3" 'git rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3' <<EOF
 214 a4
 215 EOF
 216
 217 # found!
 218
 219 #
 220 # or consider c3 to be the bad head
 221 #
 222
 223 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
 224 c2
 225 EOF
 226
 227 test_output_expect_success "$_bisect_option c3 ^a2 ^a3 ^b4 ^c2" 'git rev-list $_bisect_option c3 ^a2 ^a3 ^b4 ^c2' <<EOF
 228 c3
 229 EOF
 230
 231 # found!
 232
 233 }
 234
 235 test_sequence "--bisect"
 236
 237 #
 238 #
 239
 240 test_expect_success 'set up fake --bisect refs' '
 241         git update-ref refs/bisect/bad c3 &&
 242         good=$(git rev-parse b1) &&
 243         git update-ref refs/bisect/good-$good $good &&
 244         good=$(git rev-parse c1) &&
 245         git update-ref refs/bisect/good-$good $good
 246 '
 247
 248 test_expect_success 'rev-list --bisect can default to good/bad refs' '
 249         # the only thing between c3 and c1 is c2
 250         git rev-parse c2 >expect &&
 251         git rev-list --bisect >actual &&
 252         test_cmp expect actual
 253 '
 254
 255 test_expect_success 'rev-parse --bisect can default to good/bad refs' '
 256         git rev-parse c3 ^b1 ^c1 >expect &&
 257         git rev-parse --bisect >actual &&
 258
 259         # output order depends on the refnames, which in turn depends on
 260         # the exact sha1s. We just want to make sure we have the same set
 261         # of lines in any order.
 262         sort <expect >expect.sorted &&
 263         sort <actual >actual.sorted &&
 264         test_cmp expect.sorted actual.sorted
 265 '
 266
 267 test_output_expect_success '--bisect --first-parent' 'git rev-list --bisect --first-parent E ^F' <<EOF
 268 e4
 269 EOF
 270
 271 test_output_expect_success '--first-parent' 'git rev-list --first-parent E ^F' <<EOF
 272 E
 273 e1
 274 e2
 275 e3
 276 e4
 277 e5
 278 e6
 279 e7
 280 e8
 281 EOF
 282
 283 test_output_expect_success '--bisect-vars --first-parent' 'git rev-list --bisect-vars --first-parent E ^F' <<EOF
 284 bisect_rev='e5'
 285 bisect_nr=4
 286 bisect_good=4
 287 bisect_bad=3
 288 bisect_all=9
 289 bisect_steps=2
 290 EOF
 291
 292 test_expect_success '--bisect-all --first-parent' '
 293         cat >expect.unsorted <<-EOF &&
 294         $(git rev-parse E) (tag: E, dist=0)
 295         $(git rev-parse e1) (tag: e1, dist=1)
 296         $(git rev-parse e2) (tag: e2, dist=2)
 297         $(git rev-parse e3) (tag: e3, dist=3)
 298         $(git rev-parse e4) (tag: e4, dist=4)
 299         $(git rev-parse e5) (tag: e5, dist=4)
 300         $(git rev-parse e6) (tag: e6, dist=3)
 301         $(git rev-parse e7) (tag: e7, dist=2)
 302         $(git rev-parse e8) (tag: e8, dist=1)
 303         EOF
 304
 305         # expect results to be ordered by distance (descending),
 306         # commit hash (ascending)
 307         sort -k4,4r -k1,1 expect.unsorted >expect &&
 308         git rev-list --bisect-all --first-parent E ^F >actual &&
 309         test_cmp expect actual
 310 '
 311
 312 test_done