bisect: test merge base if good rev is not an ancestor of bad rev
[git/git.git] / git-bisect.sh
CommitLineData
8cc6a083 1#!/bin/sh
d025524d 2
243a60fb
CC
3USAGE='[help|start|bad|good|skip|next|reset|visualize|replay|log|run]'
4LONG_USAGE='git bisect help
5 print this long help message.
6git bisect start [<bad> [<good>...]] [--] [<pathspec>...]
38a47fd6
CC
7 reset bisect state and start bisection.
8git bisect bad [<rev>]
9 mark <rev> a known-bad revision.
10git bisect good [<rev>...]
11 mark <rev>... known-good revisions.
6ca8b977
CC
12git bisect skip [<rev>...]
13 mark <rev>... untestable revisions.
38a47fd6
CC
14git bisect next
15 find next bisection to test and check it out.
16git bisect reset [<branch>]
17 finish bisection search and go back to branch.
18git bisect visualize
19 show bisect status in gitk.
20git bisect replay <logfile>
21 replay bisection log.
22git bisect log
23 show bisect log.
24git bisect run <cmd>...
243a60fb
CC
25 use <cmd>... to automatically bisect.
26
27Please use "git help bisect" to get the full man page.'
d025524d 28
8f321a39 29OPTIONS_SPEC=
ae2b0f15 30. git-sh-setup
4c550686 31require_work_tree
8cc6a083 32
ce32660e
JS
33_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
34_x40="$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40"
35
e9a45d75 36sq() {
d9bffc08 37 @@PERL@@ -e '
e9a45d75
JH
38 for (@ARGV) {
39 s/'\''/'\'\\\\\'\''/g;
40 print " '\''$_'\''";
41 }
42 print "\n";
43 ' "$@"
44}
45
8cc6a083 46bisect_autostart() {
823ea121 47 test -s "$GIT_DIR/BISECT_START" || {
8cc6a083
LT
48 echo >&2 'You need to start by "git bisect start"'
49 if test -t 0
50 then
51 echo >&2 -n 'Do you want me to do it for you [Y/n]? '
52 read yesno
53 case "$yesno" in
54 [Nn]*)
55 exit ;;
56 esac
57 bisect_start
58 else
59 exit 1
60 fi
61 }
62}
63
64bisect_start() {
8cc6a083 65 #
634f2464 66 # Verify HEAD.
8cc6a083 67 #
48949a18 68 head=$(GIT_DIR="$GIT_DIR" git symbolic-ref -q HEAD) ||
ce32660e
JS
69 head=$(GIT_DIR="$GIT_DIR" git rev-parse --verify HEAD) ||
70 die "Bad HEAD - I need a HEAD"
634f2464 71
ee831f7d 72 #
634f2464 73 # Check if we are bisecting.
ee831f7d 74 #
d3e54c88 75 start_head=''
634f2464
CC
76 if test -s "$GIT_DIR/BISECT_START"
77 then
78 # Reset to the rev from where we started.
9d0cd91c
CC
79 start_head=$(cat "$GIT_DIR/BISECT_START")
80 git checkout "$start_head" || exit
634f2464
CC
81 else
82 # Get rev from where we start.
83 case "$head" in
84 refs/heads/*|$_x40)
85 # This error message should only be triggered by
86 # cogito usage, and cogito users should understand
87 # it relates to cg-seek.
88 [ -s "$GIT_DIR/head-name" ] &&
89 die "won't bisect on seeked tree"
90 start_head="${head#refs/heads/}"
91 ;;
92 *)
93 die "Bad HEAD - strange symbolic ref"
94 ;;
95 esac
96 fi
8cc6a083
LT
97
98 #
634f2464 99 # Get rid of any old bisect state.
8cc6a083 100 #
823ea121 101 bisect_clean_state || exit
38a47fd6
CC
102
103 #
104 # Check for one bad and then some good revisions.
105 #
106 has_double_dash=0
107 for arg; do
108 case "$arg" in --) has_double_dash=1; break ;; esac
109 done
110 orig_args=$(sq "$@")
111 bad_seen=0
d3e54c88 112 eval=''
38a47fd6
CC
113 while [ $# -gt 0 ]; do
114 arg="$1"
115 case "$arg" in
116 --)
8fe26f44 117 shift
38a47fd6
CC
118 break
119 ;;
120 *)
634f2464 121 rev=$(git rev-parse -q --verify "$arg^{commit}") || {
38a47fd6
CC
122 test $has_double_dash -eq 1 &&
123 die "'$arg' does not appear to be a valid revision"
124 break
125 }
737c74ee
CC
126 case $bad_seen in
127 0) state='bad' ; bad_seen=1 ;;
128 *) state='good' ;;
129 esac
d3e54c88 130 eval="$eval bisect_write '$state' '$rev' 'nolog'; "
8fe26f44 131 shift
38a47fd6
CC
132 ;;
133 esac
8fe26f44 134 done
38a47fd6 135
ba963de8
CC
136 #
137 # Change state.
138 # In case of mistaken revs or checkout error, or signals received,
139 # "bisect_auto_next" below may exit or misbehave.
140 # We have to trap this to be able to clean up using
141 # "bisect_clean_state".
142 #
143 trap 'bisect_clean_state' 0
144 trap 'exit 255' 1 2 3 15
145
146 #
147 # Write new start state.
148 #
ba963de8 149 echo "$start_head" >"$GIT_DIR/BISECT_START" &&
823ea121 150 sq "$@" >"$GIT_DIR/BISECT_NAMES" &&
ba963de8 151 eval "$eval" &&
6c98c054 152 echo "git bisect start$orig_args" >>"$GIT_DIR/BISECT_LOG" || exit
ba963de8
CC
153 #
154 # Check if we can proceed to the next bisect state.
155 #
38a47fd6 156 bisect_auto_next
ba963de8
CC
157
158 trap '-' 0
8cc6a083
LT
159}
160
55624f9a
CC
161bisect_write() {
162 state="$1"
163 rev="$2"
737c74ee 164 nolog="$3"
55624f9a
CC
165 case "$state" in
166 bad) tag="$state" ;;
167 good|skip) tag="$state"-"$rev" ;;
168 *) die "Bad bisect_write argument: $state" ;;
169 esac
ba963de8 170 git update-ref "refs/bisect/$tag" "$rev" || exit
f454cdc4 171 echo "# $state: $(git show-branch $rev)" >>"$GIT_DIR/BISECT_LOG"
6c98c054 172 test -n "$nolog" || echo "git bisect $state $rev" >>"$GIT_DIR/BISECT_LOG"
55624f9a
CC
173}
174
155fc795 175bisect_state() {
8cc6a083 176 bisect_autostart
155fc795
CC
177 state=$1
178 case "$#,$state" in
179 0,*)
180 die "Please call 'bisect_state' with at least one argument." ;;
181 1,bad|1,good|1,skip)
182 rev=$(git rev-parse --verify HEAD) ||
183 die "Bad rev input: HEAD"
184 bisect_write "$state" "$rev" ;;
e3389075 185 2,bad|*,good|*,skip)
155fc795 186 shift
d3e54c88 187 eval=''
e3389075 188 for rev in "$@"
155fc795 189 do
a179a303 190 sha=$(git rev-parse --verify "$rev^{commit}") ||
e3389075 191 die "Bad rev input: $rev"
d3e54c88
CC
192 eval="$eval bisect_write '$state' '$sha'; "
193 done
194 eval "$eval" ;;
e3389075
CC
195 *,bad)
196 die "'git bisect bad' can take only one argument." ;;
cc9f24d0
JH
197 *)
198 usage ;;
8cc6a083 199 esac
97e1c51e
CC
200 bisect_auto_next
201}
202
8cc6a083 203bisect_next_check() {
0a5280a9
JH
204 missing_good= missing_bad=
205 git show-ref -q --verify refs/bisect/bad || missing_bad=t
206 test -n "$(git for-each-ref "refs/bisect/good-*")" || missing_good=t
6fecf191 207
0a5280a9
JH
208 case "$missing_good,$missing_bad,$1" in
209 ,,*)
210 : have both good and bad - ok
211 ;;
212 *,)
213 # do not have both but not asked to fail - just report.
214 false
215 ;;
216 t,,good)
217 # have bad but not good. we could bisect although
218 # this is less optimum.
219 echo >&2 'Warning: bisecting only with a bad commit.'
220 if test -t 0
221 then
222 printf >&2 'Are you sure [Y/n]? '
e5d3afd7
FM
223 read yesno
224 case "$yesno" in [Nn]*) exit 1 ;; esac
0a5280a9
JH
225 fi
226 : bisect without good...
227 ;;
8cc6a083 228 *)
0a5280a9 229 THEN=''
823ea121 230 test -s "$GIT_DIR/BISECT_START" || {
0a5280a9
JH
231 echo >&2 'You need to start by "git bisect start".'
232 THEN='then '
233 }
234 echo >&2 'You '$THEN'need to give me at least one good' \
235 'and one bad revisions.'
236 echo >&2 '(You can use "git bisect bad" and' \
237 '"git bisect good" for that.)'
238 exit 1 ;;
8cc6a083
LT
239 esac
240}
241
242bisect_auto_next() {
434d036f 243 bisect_next_check && bisect_next || :
8cc6a083
LT
244}
245
97e1c51e
CC
246filter_skipped() {
247 _eval="$1"
248 _skip="$2"
249
250 if [ -z "$_skip" ]; then
f821d089 251 eval "$_eval"
97e1c51e
CC
252 return
253 fi
254
255 # Let's parse the output of:
256 # "git rev-list --bisect-vars --bisect-all ..."
f821d089 257 eval "$_eval" | while read hash line
97e1c51e
CC
258 do
259 case "$VARS,$FOUND,$TRIED,$hash" in
260 # We display some vars.
261 1,*,*,*) echo "$hash $line" ;;
262
263 # Split line.
264 ,*,*,---*) ;;
265
266 # We had nothing to search.
267 ,,,bisect_rev*)
268 echo "bisect_rev="
269 VARS=1
270 ;;
271
272 # We did not find a good bisect rev.
273 # This should happen only if the "bad"
274 # commit is also a "skip" commit.
275 ,,*,bisect_rev*)
276 echo "bisect_rev=$TRIED"
277 VARS=1
278 ;;
279
280 # We are searching.
281 ,,*,*)
282 TRIED="${TRIED:+$TRIED|}$hash"
283 case "$_skip" in
284 *$hash*) ;;
285 *)
286 echo "bisect_rev=$hash"
287 echo "bisect_tried=\"$TRIED\""
288 FOUND=1
289 ;;
290 esac
291 ;;
292
293 # We have already found a rev to be tested.
294 ,1,*,bisect_rev*) VARS=1 ;;
295 ,1,*,*) ;;
296
297 # ???
298 *) die "filter_skipped error " \
299 "VARS: '$VARS' " \
300 "FOUND: '$FOUND' " \
301 "TRIED: '$TRIED' " \
302 "hash: '$hash' " \
303 "line: '$line'"
304 ;;
305 esac
306 done
307}
308
309exit_if_skipped_commits () {
310 _tried=$1
311 if expr "$_tried" : ".*[|].*" > /dev/null ; then
312 echo "There are only 'skip'ped commit left to test."
313 echo "The first bad commit could be any of:"
e23cb8c0 314 echo "$_tried" | tr '[|]' '[\012]'
97e1c51e
CC
315 echo "We cannot bisect more!"
316 exit 2
317 fi
318}
319
f821d089
CC
320bisect_checkout() {
321 _rev="$1"
322 _msg="$2"
323 echo "Bisecting: $_msg"
324 git checkout -q "$_rev" || exit
325 git show-branch "$_rev"
326}
327
328is_among() {
329 _rev="$1"
330 _list="$2"
331 case "$_list" in *$_rev*) return 0 ;; esac
332 return 1
333}
334
335is_testing_merge_base() {
336 grep "^testing $1$" "$GIT_DIR/BISECT_MERGE_BASES" >/dev/null 2>&1
337}
338
339mark_testing_merge_base() {
340 echo "testing $1" >> "$GIT_DIR/BISECT_MERGE_BASES"
341}
342
343handle_bad_merge_base() {
344 _badmb="$1"
345 _good="$2"
346 if is_testing_merge_base "$_badmb"; then
347 cat >&2 <<EOF
348The merge base $_badmb is bad.
349This means the bug has been fixed between $_badmb and [$_good].
350EOF
351 exit 3
352 else
353 cat >&2 <<EOF
354Some good revs are not ancestor of the bad rev.
355git bisect cannot work properly in this case.
356Maybe you mistake good and bad revs?
357EOF
358 exit 1
359 fi
360}
361
362handle_skipped_merge_base() {
363 _mb="$1"
364 _bad="$2"
365 _good="$3"
366 cat >&2 <<EOF
367Warning: the merge base between $_bad and [$_good] must be skipped.
368So we cannot be sure the first bad commit is between $_mb and $_bad.
369We continue anyway.
370EOF
371}
372
373check_merge_bases() {
374 _bad="$1"
375 _good="$2"
376 _skip="$3"
377 for _mb in $(git merge-base --all $_bad $_good)
378 do
379 if is_among "$_mb" "$_good"; then
380 continue
381 elif test "$_mb" = "$_bad"; then
382 handle_bad_merge_base "$_bad" "$_good"
383 elif is_among "$_mb" "$_skip"; then
384 handle_skipped_merge_base "$_mb" "$_bad" "$_good"
385 else
386 mark_testing_merge_base "$_mb"
387 bisect_checkout "$_mb" "a merge base must be tested"
388 checkout_done=1
389 return
390 fi
391 done
392}
393
394check_good_are_ancestors_of_bad() {
395 _bad="$1"
396 _good=$(echo $2 | sed -e 's/\^//g')
397 _skip="$3"
398
399 # Bisecting with no good rev is ok
400 test -z "$_good" && return
401
402 _side=$(git rev-list $_good ^$_bad)
403 if test -n "$_side"; then
404 check_merge_bases "$_bad" "$_good" "$_skip"
405 fi
406}
407
8cc6a083 408bisect_next() {
8fe26f44 409 case "$#" in 0) ;; *) usage ;; esac
8cc6a083 410 bisect_autostart
0a5280a9
JH
411 bisect_next_check good
412
f821d089
CC
413 # Get bad, good and skipped revs
414 bad=$(git rev-parse --verify refs/bisect/bad) &&
415 good=$(git for-each-ref --format='^%(objectname)' \
416 "refs/bisect/good-*" | tr '\012' ' ') &&
97e1c51e 417 skip=$(git for-each-ref --format='%(objectname)' \
f821d089 418 "refs/bisect/skip-*" | tr '\012' ' ') &&
97e1c51e 419
f821d089
CC
420 # Maybe some merge bases must be tested first
421 check_good_are_ancestors_of_bad "$bad" "$good" "$skip" || exit
422 test "$checkout_done" -eq "1" && checkout_done='' && return
423
424 # Get bisection information
97e1c51e
CC
425 BISECT_OPT=''
426 test -n "$skip" && BISECT_OPT='--bisect-all'
97e1c51e 427 eval="git rev-list --bisect-vars $BISECT_OPT $good $bad --" &&
0a5280a9 428 eval="$eval $(cat "$GIT_DIR/BISECT_NAMES")" &&
97e1c51e 429 eval=$(filter_skipped "$eval" "$skip") &&
0a5280a9
JH
430 eval "$eval" || exit
431
432 if [ -z "$bisect_rev" ]; then
433 echo "$bad was both good and bad"
434 exit 1
670f5fe3 435 fi
0a5280a9 436 if [ "$bisect_rev" = "$bad" ]; then
97e1c51e 437 exit_if_skipped_commits "$bisect_tried"
0a5280a9 438 echo "$bisect_rev is first bad commit"
5be60078 439 git diff-tree --pretty $bisect_rev
0a5280a9 440 exit 0
8cc6a083 441 fi
0a5280a9 442
97e1c51e
CC
443 # We should exit here only if the "bad"
444 # commit is also a "skip" commit (see above).
445 exit_if_skipped_commits "$bisect_rev"
446
f821d089 447 bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this"
8cc6a083
LT
448}
449
cc9f24d0
JH
450bisect_visualize() {
451 bisect_next_check fail
235997c9
JH
452
453 if test $# = 0
454 then
508e84a7 455 case "${DISPLAY+set}${MSYSTEM+set}${SECURITYSESSIONID+set}" in
235997c9 456 '') set git log ;;
508e84a7 457 set*) set gitk ;;
235997c9
JH
458 esac
459 else
460 case "$1" in
461 git*|tig) ;;
462 -*) set git log "$@" ;;
463 *) set git "$@" ;;
464 esac
465 fi
466
e3f062bf 467 not=$(git for-each-ref --format='%(refname)' "refs/bisect/good-*")
235997c9 468 eval '"$@"' refs/bisect/bad --not $not -- $(cat "$GIT_DIR/BISECT_NAMES")
cc9f24d0
JH
469}
470
8cc6a083 471bisect_reset() {
823ea121 472 test -s "$GIT_DIR/BISECT_START" || {
fce0499f
CC
473 echo "We are not bisecting."
474 return
475 }
8cc6a083 476 case "$#" in
823ea121 477 0) branch=$(cat "$GIT_DIR/BISECT_START") ;;
737c74ee
CC
478 1) git show-ref --verify --quiet -- "refs/heads/$1" ||
479 die "$1 does not seem to be a valid branch"
8cc6a083 480 branch="$1" ;;
8fe26f44 481 *)
8cc6a083
LT
482 usage ;;
483 esac
9d0cd91c 484 git checkout "$branch" && bisect_clean_state
e204de28
JH
485}
486
38a47fd6 487bisect_clean_state() {
947a604b 488 # There may be some refs packed during bisection.
634f2464 489 git for-each-ref --format='%(refname) %(objectname)' refs/bisect/\* |
947a604b
CC
490 while read ref hash
491 do
823ea121 492 git update-ref -d $ref $hash || exit
947a604b 493 done
f821d089 494 rm -f "$GIT_DIR/BISECT_MERGE_BASES" &&
823ea121
CC
495 rm -f "$GIT_DIR/BISECT_LOG" &&
496 rm -f "$GIT_DIR/BISECT_NAMES" &&
497 rm -f "$GIT_DIR/BISECT_RUN" &&
9d0cd91c 498 # Cleanup head-name if it got left by an old version of git-bisect
823ea121
CC
499 rm -f "$GIT_DIR/head-name" &&
500
501 rm -f "$GIT_DIR/BISECT_START"
38a47fd6
CC
502}
503
e204de28 504bisect_replay () {
737c74ee 505 test -r "$1" || die "cannot read $1 for replaying"
e204de28 506 bisect_reset
6c98c054 507 while read git bisect command rev
e204de28 508 do
6c98c054
MV
509 test "$git $bisect" = "git bisect" -o "$git" = "git-bisect" || continue
510 if test "$git" = "git-bisect"; then
511 rev="$command"
512 command="$bisect"
513 fi
e204de28
JH
514 case "$command" in
515 start)
e9a45d75 516 cmd="bisect_start $rev"
737c74ee
CC
517 eval "$cmd" ;;
518 good|bad|skip)
519 bisect_write "$command" "$rev" ;;
e204de28 520 *)
737c74ee 521 die "?? what are you talking about?" ;;
e204de28
JH
522 esac
523 done <"$1"
524 bisect_auto_next
8cc6a083
LT
525}
526
a17c4101 527bisect_run () {
83020120
CC
528 bisect_next_check fail
529
a17c4101
CC
530 while true
531 do
532 echo "running $@"
533 "$@"
534 res=$?
535
536 # Check for really bad run error.
537 if [ $res -lt 0 -o $res -ge 128 ]; then
538 echo >&2 "bisect run failed:"
539 echo >&2 "exit code $res from '$@' is < 0 or >= 128"
540 exit $res
541 fi
542
155fc795 543 # Find current state depending on run success or failure.
71b0251c
CC
544 # A special exit code of 125 means cannot test.
545 if [ $res -eq 125 ]; then
546 state='skip'
547 elif [ $res -gt 0 ]; then
155fc795 548 state='bad'
a17c4101 549 else
155fc795 550 state='good'
a17c4101
CC
551 fi
552
155fc795
CC
553 # We have to use a subshell because "bisect_state" can exit.
554 ( bisect_state $state > "$GIT_DIR/BISECT_RUN" )
a17c4101
CC
555 res=$?
556
557 cat "$GIT_DIR/BISECT_RUN"
558
71b0251c
CC
559 if grep "first bad commit could be any of" "$GIT_DIR/BISECT_RUN" \
560 > /dev/null; then
561 echo >&2 "bisect run cannot continue any more"
562 exit $res
563 fi
564
a17c4101
CC
565 if [ $res -ne 0 ]; then
566 echo >&2 "bisect run failed:"
155fc795 567 echo >&2 "'bisect_state $state' exited with error code $res"
a17c4101
CC
568 exit $res
569 fi
570
571 if grep "is first bad commit" "$GIT_DIR/BISECT_RUN" > /dev/null; then
572 echo "bisect run success"
573 exit 0;
574 fi
575
576 done
577}
578
579
8cc6a083
LT
580case "$#" in
5810)
582 usage ;;
583*)
584 cmd="$1"
585 shift
586 case "$cmd" in
243a60fb
CC
587 help)
588 git bisect -h ;;
8cc6a083
LT
589 start)
590 bisect_start "$@" ;;
155fc795
CC
591 bad|good|skip)
592 bisect_state "$cmd" "$@" ;;
8cc6a083
LT
593 next)
594 # Not sure we want "next" at the UI level anymore.
595 bisect_next "$@" ;;
235997c9 596 visualize|view)
cc9f24d0 597 bisect_visualize "$@" ;;
8cc6a083
LT
598 reset)
599 bisect_reset "$@" ;;
e204de28
JH
600 replay)
601 bisect_replay "$@" ;;
602 log)
603 cat "$GIT_DIR/BISECT_LOG" ;;
a17c4101
CC
604 run)
605 bisect_run "$@" ;;
8cc6a083
LT
606 *)
607 usage ;;
608 esac
609esac