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