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 . ../t6000-lib.sh
   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
 117 #
 118 # cd to t/trash and use
 119 #
 120 #    git-rev-list ... 2>&1 | sed "$(cat sed.script)"
 121 #
 122 # if you ever want to manually debug the operation of git-rev-list
 123 #
 124 echo $sed_script > sed.script
 125
 126 test_sequence()
 127 {
 128         _bisect_option=$1
 129
 130         test_bisection_diff 0 $_bisect_option l0 ^root
 131         test_bisection_diff 0 $_bisect_option l1 ^root
 132         test_bisection_diff 0 $_bisect_option l2 ^root
 133         test_bisection_diff 0 $_bisect_option a0 ^root
 134         test_bisection_diff 0 $_bisect_option a1 ^root
 135         test_bisection_diff 0 $_bisect_option a2 ^root
 136         test_bisection_diff 0 $_bisect_option a3 ^root
 137         test_bisection_diff 0 $_bisect_option b1 ^root
 138         test_bisection_diff 0 $_bisect_option b2 ^root
 139         test_bisection_diff 0 $_bisect_option b3 ^root
 140         test_bisection_diff 0 $_bisect_option c1 ^root
 141         test_bisection_diff 0 $_bisect_option c2 ^root
 142         test_bisection_diff 0 $_bisect_option c3 ^root
 143         test_bisection_diff 0 $_bisect_option E ^F
 144         test_bisection_diff 0 $_bisect_option e1 ^F
 145         test_bisection_diff 0 $_bisect_option e2 ^F
 146         test_bisection_diff 0 $_bisect_option e3 ^F
 147         test_bisection_diff 0 $_bisect_option e4 ^F
 148         test_bisection_diff 0 $_bisect_option e5 ^F
 149         test_bisection_diff 0 $_bisect_option e6 ^F
 150         test_bisection_diff 0 $_bisect_option e7 ^F
 151         test_bisection_diff 0 $_bisect_option f1 ^F
 152         test_bisection_diff 0 $_bisect_option f2 ^F
 153         test_bisection_diff 0 $_bisect_option f3 ^F
 154         test_bisection_diff 0 $_bisect_option f4 ^F
 155         test_bisection_diff 0 $_bisect_option E ^F
 156
 157         test_bisection_diff 1 $_bisect_option V ^U
 158         test_bisection_diff 0 $_bisect_option V ^U ^u1 ^u2 ^u3
 159         test_bisection_diff 0 $_bisect_option u1 ^U
 160         test_bisection_diff 0 $_bisect_option u2 ^U
 161         test_bisection_diff 0 $_bisect_option u3 ^U
 162         test_bisection_diff 0 $_bisect_option u4 ^U
 163         test_bisection_diff 0 $_bisect_option u5 ^U
 164
 165 #
 166 # the following illustrate's Linus' binary bug blatt idea.
 167 #
 168 # assume the bug is actually at l3, but you don't know that - all you know is that l3 is broken
 169 # and it wasn't broken before
 170 #
 171 # keep bisecting the list, advancing the "bad" head and accumulating "good" heads until
 172 # the bisection point is the head - this is the bad point.
 173 #
 174
 175 test_output_expect_success "--bisect l5 ^root" 'git-rev-list $_bisect_option l5 ^root' <<EOF
 176 c3
 177 EOF
 178
 179 test_output_expect_success "$_bisect_option l5 ^root ^c3" 'git-rev-list $_bisect_option l5 ^root ^c3' <<EOF
 180 b4
 181 EOF
 182
 183 test_output_expect_success "$_bisect_option l5 ^root ^c3 ^b4" 'git-rev-list $_bisect_option l5 ^c3 ^b4' <<EOF
 184 l3
 185 EOF
 186
 187 test_output_expect_success "$_bisect_option l3 ^root ^c3 ^b4" 'git-rev-list $_bisect_option l3 ^root ^c3 ^b4' <<EOF
 188 a4
 189 EOF
 190
 191 test_output_expect_success "$_bisect_option l5 ^b3 ^a3 ^b4 ^a4" 'git-rev-list $_bisect_option l3 ^b3 ^a3 ^a4' <<EOF
 192 l3
 193 EOF
 194
 195 #
 196 # if l3 is bad, then l4 is bad too - so advance the bad pointer by making b4 the known bad head
 197 #
 198
 199 test_output_expect_success "$_bisect_option l4 ^a2 ^a3 ^b ^a4" 'git-rev-list $_bisect_option l4 ^a2 ^a3 ^a4' <<EOF
 200 l3
 201 EOF
 202
 203 test_output_expect_success "$_bisect_option l3 ^a2 ^a3 ^b ^a4" 'git-rev-list $_bisect_option l3 ^a2 ^a3 ^a4' <<EOF
 204 l3
 205 EOF
 206
 207 # found!
 208
 209 #
 210 # as another example, let's consider a4 to be the bad head, in which case
 211 #
 212
 213 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
 214 c2
 215 EOF
 216
 217 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2' <<EOF
 218 c3
 219 EOF
 220
 221 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4 ^c2 ^c3' <<EOF
 222 a4
 223 EOF
 224
 225 # found!
 226
 227 #
 228 # or consider c3 to be the bad head
 229 #
 230
 231 test_output_expect_success "$_bisect_option a4 ^a2 ^a3 ^b4" 'git-rev-list $_bisect_option a4 ^a2 ^a3 ^b4' <<EOF
 232 c2
 233 EOF
 234
 235 test_output_expect_success "$_bisect_option c3 ^a2 ^a3 ^b4 ^c2" 'git-rev-list $_bisect_option c3 ^a2 ^a3 ^b4 ^c2' <<EOF
 236 c3
 237 EOF
 238
 239 # found!
 240
 241 }
 242
 243 test_sequence "--bisect"
 244
 245 #
 246 #
 247 test_done