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