Merge branch 'dm/maint-docco'
[git] / git-bisect.sh
1 #!/bin/sh
2
3 USAGE='[help|start|bad|good|skip|next|reset|visualize|replay|log|run]'
4 LONG_USAGE='git bisect help
5         print this long help message.
6 git bisect start [<bad> [<good>...]] [--] [<pathspec>...]
7         reset bisect state and start bisection.
8 git bisect bad [<rev>]
9         mark <rev> a known-bad revision.
10 git bisect good [<rev>...]
11         mark <rev>... known-good revisions.
12 git bisect skip [(<rev>|<range>)...]
13         mark <rev>... untestable revisions.
14 git bisect next
15         find next bisection to test and check it out.
16 git bisect reset [<branch>]
17         finish bisection search and go back to branch.
18 git bisect visualize
19         show bisect status in gitk.
20 git bisect replay <logfile>
21         replay bisection log.
22 git bisect log
23         show bisect log.
24 git bisect run <cmd>...
25         use <cmd>... to automatically bisect.
26
27 Please use "git help bisect" to get the full man page.'
28
29 OPTIONS_SPEC=
30 . git-sh-setup
31 require_work_tree
32
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
36 sq() {
37         @@PERL@@ -e '
38                 for (@ARGV) {
39                         s/'\''/'\'\\\\\'\''/g;
40                         print " '\''$_'\''";
41                 }
42                 print "\n";
43         ' "$@"
44 }
45
46 bisect_autostart() {
47         test -s "$GIT_DIR/BISECT_START" || {
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
64 bisect_start() {
65         #
66         # Verify HEAD.
67         #
68         head=$(GIT_DIR="$GIT_DIR" git symbolic-ref -q HEAD) ||
69         head=$(GIT_DIR="$GIT_DIR" git rev-parse --verify HEAD) ||
70         die "Bad HEAD - I need a HEAD"
71
72         #
73         # Check if we are bisecting.
74         #
75         start_head=''
76         if test -s "$GIT_DIR/BISECT_START"
77         then
78                 # Reset to the rev from where we started.
79                 start_head=$(cat "$GIT_DIR/BISECT_START")
80                 git checkout "$start_head" || exit
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
97
98         #
99         # Get rid of any old bisect state.
100         #
101         bisect_clean_state || exit
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
112         eval=''
113         while [ $# -gt 0 ]; do
114             arg="$1"
115             case "$arg" in
116             --)
117                 shift
118                 break
119                 ;;
120             *)
121                 rev=$(git rev-parse -q --verify "$arg^{commit}") || {
122                     test $has_double_dash -eq 1 &&
123                         die "'$arg' does not appear to be a valid revision"
124                     break
125                 }
126                 case $bad_seen in
127                 0) state='bad' ; bad_seen=1 ;;
128                 *) state='good' ;;
129                 esac
130                 eval="$eval bisect_write '$state' '$rev' 'nolog'; "
131                 shift
132                 ;;
133             esac
134         done
135
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         #
149         echo "$start_head" >"$GIT_DIR/BISECT_START" &&
150         sq "$@" >"$GIT_DIR/BISECT_NAMES" &&
151         eval "$eval" &&
152         echo "git bisect start$orig_args" >>"$GIT_DIR/BISECT_LOG" || exit
153         #
154         # Check if we can proceed to the next bisect state.
155         #
156         bisect_auto_next
157
158         trap '-' 0
159 }
160
161 bisect_write() {
162         state="$1"
163         rev="$2"
164         nolog="$3"
165         case "$state" in
166                 bad)            tag="$state" ;;
167                 good|skip)      tag="$state"-"$rev" ;;
168                 *)              die "Bad bisect_write argument: $state" ;;
169         esac
170         git update-ref "refs/bisect/$tag" "$rev" || exit
171         echo "# $state: $(git show-branch $rev)" >>"$GIT_DIR/BISECT_LOG"
172         test -n "$nolog" || echo "git bisect $state $rev" >>"$GIT_DIR/BISECT_LOG"
173 }
174
175 is_expected_rev() {
176         test -f "$GIT_DIR/BISECT_EXPECTED_REV" &&
177         test "$1" = $(cat "$GIT_DIR/BISECT_EXPECTED_REV")
178 }
179
180 mark_expected_rev() {
181         echo "$1" > "$GIT_DIR/BISECT_EXPECTED_REV"
182 }
183
184 check_expected_revs() {
185         for _rev in "$@"; do
186                 if ! is_expected_rev "$_rev"; then
187                         rm -f "$GIT_DIR/BISECT_ANCESTORS_OK"
188                         rm -f "$GIT_DIR/BISECT_EXPECTED_REV"
189                         return
190                 fi
191         done
192 }
193
194 bisect_skip() {
195         all=''
196         for arg in "$@"
197         do
198             case "$arg" in
199             *..*)
200                 revs=$(git rev-list "$arg") || die "Bad rev input: $arg" ;;
201             *)
202                 revs=$(sq "$arg") ;;
203             esac
204             all="$all $revs"
205         done
206         eval bisect_state 'skip' $all
207 }
208
209 bisect_state() {
210         bisect_autostart
211         state=$1
212         case "$#,$state" in
213         0,*)
214                 die "Please call 'bisect_state' with at least one argument." ;;
215         1,bad|1,good|1,skip)
216                 rev=$(git rev-parse --verify HEAD) ||
217                         die "Bad rev input: HEAD"
218                 bisect_write "$state" "$rev"
219                 check_expected_revs "$rev" ;;
220         2,bad|*,good|*,skip)
221                 shift
222                 eval=''
223                 for rev in "$@"
224                 do
225                         sha=$(git rev-parse --verify "$rev^{commit}") ||
226                                 die "Bad rev input: $rev"
227                         eval="$eval bisect_write '$state' '$sha'; "
228                 done
229                 eval "$eval"
230                 check_expected_revs "$@" ;;
231         *,bad)
232                 die "'git bisect bad' can take only one argument." ;;
233         *)
234                 usage ;;
235         esac
236         bisect_auto_next
237 }
238
239 bisect_next_check() {
240         missing_good= missing_bad=
241         git show-ref -q --verify refs/bisect/bad || missing_bad=t
242         test -n "$(git for-each-ref "refs/bisect/good-*")" || missing_good=t
243
244         case "$missing_good,$missing_bad,$1" in
245         ,,*)
246                 : have both good and bad - ok
247                 ;;
248         *,)
249                 # do not have both but not asked to fail - just report.
250                 false
251                 ;;
252         t,,good)
253                 # have bad but not good.  we could bisect although
254                 # this is less optimum.
255                 echo >&2 'Warning: bisecting only with a bad commit.'
256                 if test -t 0
257                 then
258                         printf >&2 'Are you sure [Y/n]? '
259                         read yesno
260                         case "$yesno" in [Nn]*) exit 1 ;; esac
261                 fi
262                 : bisect without good...
263                 ;;
264         *)
265                 THEN=''
266                 test -s "$GIT_DIR/BISECT_START" || {
267                         echo >&2 'You need to start by "git bisect start".'
268                         THEN='then '
269                 }
270                 echo >&2 'You '$THEN'need to give me at least one good' \
271                         'and one bad revisions.'
272                 echo >&2 '(You can use "git bisect bad" and' \
273                         '"git bisect good" for that.)'
274                 exit 1 ;;
275         esac
276 }
277
278 bisect_auto_next() {
279         bisect_next_check && bisect_next || :
280 }
281
282 filter_skipped() {
283         _eval="$1"
284         _skip="$2"
285
286         if [ -z "$_skip" ]; then
287                 eval "$_eval" | {
288                         while read line
289                         do
290                                 echo "$line &&"
291                         done
292                         echo ':'
293                 }
294                 return
295         fi
296
297         # Let's parse the output of:
298         # "git rev-list --bisect-vars --bisect-all ..."
299         eval "$_eval" | {
300                 VARS= FOUND= TRIED=
301                 while read hash line
302                 do
303                         case "$VARS,$FOUND,$TRIED,$hash" in
304                         1,*,*,*)
305                                 # "bisect_foo=bar" read from rev-list output.
306                                 echo "$hash &&"
307                                 ;;
308                         ,*,*,---*)
309                                 # Separator
310                                 ;;
311                         ,,,bisect_rev*)
312                                 # We had nothing to search.
313                                 echo "bisect_rev= &&"
314                                 VARS=1
315                                 ;;
316                         ,,*,bisect_rev*)
317                                 # We did not find a good bisect rev.
318                                 # This should happen only if the "bad"
319                                 # commit is also a "skip" commit.
320                                 echo "bisect_rev='$TRIED' &&"
321                                 VARS=1
322                                 ;;
323                         ,,*,*)
324                                 # We are searching.
325                                 TRIED="${TRIED:+$TRIED|}$hash"
326                                 case "$_skip" in
327                                 *$hash*) ;;
328                                 *)
329                                         echo "bisect_rev=$hash &&"
330                                         echo "bisect_tried='$TRIED' &&"
331                                         FOUND=1
332                                         ;;
333                                 esac
334                                 ;;
335                         ,1,*,bisect_rev*)
336                                 # We have already found a rev to be tested.
337                                 VARS=1
338                                 ;;
339                         ,1,*,*)
340                                 ;;
341                         *)
342                                 # Unexpected input
343                                 echo "die 'filter_skipped error'"
344                                 die "filter_skipped error " \
345                                     "VARS: '$VARS' " \
346                                     "FOUND: '$FOUND' " \
347                                     "TRIED: '$TRIED' " \
348                                     "hash: '$hash' " \
349                                     "line: '$line'"
350                                 ;;
351                         esac
352                 done
353                 echo ':'
354         }
355 }
356
357 exit_if_skipped_commits () {
358         _tried=$1
359         if expr "$_tried" : ".*[|].*" > /dev/null ; then
360                 echo "There are only 'skip'ped commit left to test."
361                 echo "The first bad commit could be any of:"
362                 echo "$_tried" | tr '[|]' '[\012]'
363                 echo "We cannot bisect more!"
364                 exit 2
365         fi
366 }
367
368 bisect_checkout() {
369         _rev="$1"
370         _msg="$2"
371         echo "Bisecting: $_msg"
372         mark_expected_rev "$_rev"
373         git checkout -q "$_rev" || exit
374         git show-branch "$_rev"
375 }
376
377 is_among() {
378         _rev="$1"
379         _list="$2"
380         case "$_list" in *$_rev*) return 0 ;; esac
381         return 1
382 }
383
384 handle_bad_merge_base() {
385         _badmb="$1"
386         _good="$2"
387         if is_expected_rev "$_badmb"; then
388                 cat >&2 <<EOF
389 The merge base $_badmb is bad.
390 This means the bug has been fixed between $_badmb and [$_good].
391 EOF
392                 exit 3
393         else
394                 cat >&2 <<EOF
395 Some good revs are not ancestor of the bad rev.
396 git bisect cannot work properly in this case.
397 Maybe you mistake good and bad revs?
398 EOF
399                 exit 1
400         fi
401 }
402
403 handle_skipped_merge_base() {
404         _mb="$1"
405         _bad="$2"
406         _good="$3"
407         cat >&2 <<EOF
408 Warning: the merge base between $_bad and [$_good] must be skipped.
409 So we cannot be sure the first bad commit is between $_mb and $_bad.
410 We continue anyway.
411 EOF
412 }
413
414 #
415 # "check_merge_bases" checks that merge bases are not "bad".
416 #
417 # - If one is "good", that's good, we have nothing to do.
418 # - If one is "bad", it means the user assumed something wrong
419 # and we must exit.
420 # - If one is "skipped", we can't know but we should warn.
421 # - If we don't know, we should check it out and ask the user to test.
422 #
423 # In the last case we will return 1, and otherwise 0.
424 #
425 check_merge_bases() {
426         _bad="$1"
427         _good="$2"
428         _skip="$3"
429         for _mb in $(git merge-base --all $_bad $_good)
430         do
431                 if is_among "$_mb" "$_good"; then
432                         continue
433                 elif test "$_mb" = "$_bad"; then
434                         handle_bad_merge_base "$_bad" "$_good"
435                 elif is_among "$_mb" "$_skip"; then
436                         handle_skipped_merge_base "$_mb" "$_bad" "$_good"
437                 else
438                         bisect_checkout "$_mb" "a merge base must be tested"
439                         return 1
440                 fi
441         done
442         return 0
443 }
444
445 #
446 # "check_good_are_ancestors_of_bad" checks that all "good" revs are
447 # ancestor of the "bad" rev.
448 #
449 # If that's not the case, we need to check the merge bases.
450 # If a merge base must be tested by the user we return 1 and
451 # otherwise 0.
452 #
453 check_good_are_ancestors_of_bad() {
454         test -f "$GIT_DIR/BISECT_ANCESTORS_OK" &&
455                 return
456
457         _bad="$1"
458         _good=$(echo $2 | sed -e 's/\^//g')
459         _skip="$3"
460
461         # Bisecting with no good rev is ok
462         test -z "$_good" && return
463
464         _side=$(git rev-list $_good ^$_bad)
465         if test -n "$_side"; then
466                 # Return if a checkout was done
467                 check_merge_bases "$_bad" "$_good" "$_skip" || return
468         fi
469
470         : > "$GIT_DIR/BISECT_ANCESTORS_OK"
471
472         return 0
473 }
474
475 bisect_next() {
476         case "$#" in 0) ;; *) usage ;; esac
477         bisect_autostart
478         bisect_next_check good
479
480         # Get bad, good and skipped revs
481         bad=$(git rev-parse --verify refs/bisect/bad) &&
482         good=$(git for-each-ref --format='^%(objectname)' \
483                 "refs/bisect/good-*" | tr '\012' ' ') &&
484         skip=$(git for-each-ref --format='%(objectname)' \
485                 "refs/bisect/skip-*" | tr '\012' ' ') || exit
486
487         # Maybe some merge bases must be tested first
488         check_good_are_ancestors_of_bad "$bad" "$good" "$skip"
489         # Return now if a checkout has already been done
490         test "$?" -eq "1" && return
491
492         # Get bisection information
493         BISECT_OPT=''
494         test -n "$skip" && BISECT_OPT='--bisect-all'
495         eval="git rev-list --bisect-vars $BISECT_OPT $good $bad --" &&
496         eval="$eval $(cat "$GIT_DIR/BISECT_NAMES")" &&
497         eval=$(filter_skipped "$eval" "$skip") &&
498         eval "$eval" || exit
499
500         if [ -z "$bisect_rev" ]; then
501                 echo "$bad was both good and bad"
502                 exit 1
503         fi
504         if [ "$bisect_rev" = "$bad" ]; then
505                 exit_if_skipped_commits "$bisect_tried"
506                 echo "$bisect_rev is first bad commit"
507                 git diff-tree --pretty $bisect_rev
508                 exit 0
509         fi
510
511         # We should exit here only if the "bad"
512         # commit is also a "skip" commit (see above).
513         exit_if_skipped_commits "$bisect_rev"
514
515         bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this (roughly $bisect_steps steps)"
516 }
517
518 bisect_visualize() {
519         bisect_next_check fail
520
521         if test $# = 0
522         then
523                 case "${DISPLAY+set}${SESSIONNAME+set}${MSYSTEM+set}${SECURITYSESSIONID+set}" in
524                 '')     set git log ;;
525                 set*)   set gitk ;;
526                 esac
527         else
528                 case "$1" in
529                 git*|tig) ;;
530                 -*)     set git log "$@" ;;
531                 *)      set git "$@" ;;
532                 esac
533         fi
534
535         not=$(git for-each-ref --format='%(refname)' "refs/bisect/good-*")
536         eval '"$@"' refs/bisect/bad --not $not -- $(cat "$GIT_DIR/BISECT_NAMES")
537 }
538
539 bisect_reset() {
540         test -s "$GIT_DIR/BISECT_START" || {
541                 echo "We are not bisecting."
542                 return
543         }
544         case "$#" in
545         0) branch=$(cat "$GIT_DIR/BISECT_START") ;;
546         1) git show-ref --verify --quiet -- "refs/heads/$1" ||
547                die "$1 does not seem to be a valid branch"
548            branch="$1" ;;
549         *)
550             usage ;;
551         esac
552         git checkout "$branch" && bisect_clean_state
553 }
554
555 bisect_clean_state() {
556         # There may be some refs packed during bisection.
557         git for-each-ref --format='%(refname) %(objectname)' refs/bisect/\* |
558         while read ref hash
559         do
560                 git update-ref -d $ref $hash || exit
561         done
562         rm -f "$GIT_DIR/BISECT_EXPECTED_REV" &&
563         rm -f "$GIT_DIR/BISECT_ANCESTORS_OK" &&
564         rm -f "$GIT_DIR/BISECT_LOG" &&
565         rm -f "$GIT_DIR/BISECT_NAMES" &&
566         rm -f "$GIT_DIR/BISECT_RUN" &&
567         # Cleanup head-name if it got left by an old version of git-bisect
568         rm -f "$GIT_DIR/head-name" &&
569
570         rm -f "$GIT_DIR/BISECT_START"
571 }
572
573 bisect_replay () {
574         test -r "$1" || die "cannot read $1 for replaying"
575         bisect_reset
576         while read git bisect command rev
577         do
578                 test "$git $bisect" = "git bisect" -o "$git" = "git-bisect" || continue
579                 if test "$git" = "git-bisect"; then
580                         rev="$command"
581                         command="$bisect"
582                 fi
583                 case "$command" in
584                 start)
585                         cmd="bisect_start $rev"
586                         eval "$cmd" ;;
587                 good|bad|skip)
588                         bisect_write "$command" "$rev" ;;
589                 *)
590                         die "?? what are you talking about?" ;;
591                 esac
592         done <"$1"
593         bisect_auto_next
594 }
595
596 bisect_run () {
597     bisect_next_check fail
598
599     while true
600     do
601       echo "running $@"
602       "$@"
603       res=$?
604
605       # Check for really bad run error.
606       if [ $res -lt 0 -o $res -ge 128 ]; then
607           echo >&2 "bisect run failed:"
608           echo >&2 "exit code $res from '$@' is < 0 or >= 128"
609           exit $res
610       fi
611
612       # Find current state depending on run success or failure.
613       # A special exit code of 125 means cannot test.
614       if [ $res -eq 125 ]; then
615           state='skip'
616       elif [ $res -gt 0 ]; then
617           state='bad'
618       else
619           state='good'
620       fi
621
622       # We have to use a subshell because "bisect_state" can exit.
623       ( bisect_state $state > "$GIT_DIR/BISECT_RUN" )
624       res=$?
625
626       cat "$GIT_DIR/BISECT_RUN"
627
628       if grep "first bad commit could be any of" "$GIT_DIR/BISECT_RUN" \
629                 > /dev/null; then
630           echo >&2 "bisect run cannot continue any more"
631           exit $res
632       fi
633
634       if [ $res -ne 0 ]; then
635           echo >&2 "bisect run failed:"
636           echo >&2 "'bisect_state $state' exited with error code $res"
637           exit $res
638       fi
639
640       if grep "is first bad commit" "$GIT_DIR/BISECT_RUN" > /dev/null; then
641           echo "bisect run success"
642           exit 0;
643       fi
644
645     done
646 }
647
648
649 case "$#" in
650 0)
651     usage ;;
652 *)
653     cmd="$1"
654     shift
655     case "$cmd" in
656     help)
657         git bisect -h ;;
658     start)
659         bisect_start "$@" ;;
660     bad|good)
661         bisect_state "$cmd" "$@" ;;
662     skip)
663         bisect_skip "$@" ;;
664     next)
665         # Not sure we want "next" at the UI level anymore.
666         bisect_next "$@" ;;
667     visualize|view)
668         bisect_visualize "$@" ;;
669     reset)
670         bisect_reset "$@" ;;
671     replay)
672         bisect_replay "$@" ;;
673     log)
674         cat "$GIT_DIR/BISECT_LOG" ;;
675     run)
676         bisect_run "$@" ;;
677     *)
678         usage ;;
679     esac
680 esac