Merge branch 'jc/better-conflict-resolution'
[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>...]
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_state() {
195         bisect_autostart
196         state=$1
197         case "$#,$state" in
198         0,*)
199                 die "Please call 'bisect_state' with at least one argument." ;;
200         1,bad|1,good|1,skip)
201                 rev=$(git rev-parse --verify HEAD) ||
202                         die "Bad rev input: HEAD"
203                 bisect_write "$state" "$rev"
204                 check_expected_revs "$rev" ;;
205         2,bad|*,good|*,skip)
206                 shift
207                 eval=''
208                 for rev in "$@"
209                 do
210                         sha=$(git rev-parse --verify "$rev^{commit}") ||
211                                 die "Bad rev input: $rev"
212                         eval="$eval bisect_write '$state' '$sha'; "
213                 done
214                 eval "$eval"
215                 check_expected_revs "$@" ;;
216         *,bad)
217                 die "'git bisect bad' can take only one argument." ;;
218         *)
219                 usage ;;
220         esac
221         bisect_auto_next
222 }
223
224 bisect_next_check() {
225         missing_good= missing_bad=
226         git show-ref -q --verify refs/bisect/bad || missing_bad=t
227         test -n "$(git for-each-ref "refs/bisect/good-*")" || missing_good=t
228
229         case "$missing_good,$missing_bad,$1" in
230         ,,*)
231                 : have both good and bad - ok
232                 ;;
233         *,)
234                 # do not have both but not asked to fail - just report.
235                 false
236                 ;;
237         t,,good)
238                 # have bad but not good.  we could bisect although
239                 # this is less optimum.
240                 echo >&2 'Warning: bisecting only with a bad commit.'
241                 if test -t 0
242                 then
243                         printf >&2 'Are you sure [Y/n]? '
244                         read yesno
245                         case "$yesno" in [Nn]*) exit 1 ;; esac
246                 fi
247                 : bisect without good...
248                 ;;
249         *)
250                 THEN=''
251                 test -s "$GIT_DIR/BISECT_START" || {
252                         echo >&2 'You need to start by "git bisect start".'
253                         THEN='then '
254                 }
255                 echo >&2 'You '$THEN'need to give me at least one good' \
256                         'and one bad revisions.'
257                 echo >&2 '(You can use "git bisect bad" and' \
258                         '"git bisect good" for that.)'
259                 exit 1 ;;
260         esac
261 }
262
263 bisect_auto_next() {
264         bisect_next_check && bisect_next || :
265 }
266
267 filter_skipped() {
268         _eval="$1"
269         _skip="$2"
270
271         if [ -z "$_skip" ]; then
272                 eval "$_eval"
273                 return
274         fi
275
276         # Let's parse the output of:
277         # "git rev-list --bisect-vars --bisect-all ..."
278         eval "$_eval" | while read hash line
279         do
280                 case "$VARS,$FOUND,$TRIED,$hash" in
281                         # We display some vars.
282                         1,*,*,*) echo "$hash $line" ;;
283
284                         # Split line.
285                         ,*,*,---*) ;;
286
287                         # We had nothing to search.
288                         ,,,bisect_rev*)
289                                 echo "bisect_rev="
290                                 VARS=1
291                                 ;;
292
293                         # We did not find a good bisect rev.
294                         # This should happen only if the "bad"
295                         # commit is also a "skip" commit.
296                         ,,*,bisect_rev*)
297                                 echo "bisect_rev=$TRIED"
298                                 VARS=1
299                                 ;;
300
301                         # We are searching.
302                         ,,*,*)
303                                 TRIED="${TRIED:+$TRIED|}$hash"
304                                 case "$_skip" in
305                                 *$hash*) ;;
306                                 *)
307                                         echo "bisect_rev=$hash"
308                                         echo "bisect_tried=\"$TRIED\""
309                                         FOUND=1
310                                         ;;
311                                 esac
312                                 ;;
313
314                         # We have already found a rev to be tested.
315                         ,1,*,bisect_rev*) VARS=1 ;;
316                         ,1,*,*) ;;
317
318                         # ???
319                         *) die "filter_skipped error " \
320                             "VARS: '$VARS' " \
321                             "FOUND: '$FOUND' " \
322                             "TRIED: '$TRIED' " \
323                             "hash: '$hash' " \
324                             "line: '$line'"
325                         ;;
326                 esac
327         done
328 }
329
330 exit_if_skipped_commits () {
331         _tried=$1
332         if expr "$_tried" : ".*[|].*" > /dev/null ; then
333                 echo "There are only 'skip'ped commit left to test."
334                 echo "The first bad commit could be any of:"
335                 echo "$_tried" | tr '[|]' '[\012]'
336                 echo "We cannot bisect more!"
337                 exit 2
338         fi
339 }
340
341 bisect_checkout() {
342         _rev="$1"
343         _msg="$2"
344         echo "Bisecting: $_msg"
345         mark_expected_rev "$_rev"
346         git checkout -q "$_rev" || exit
347         git show-branch "$_rev"
348 }
349
350 is_among() {
351         _rev="$1"
352         _list="$2"
353         case "$_list" in *$_rev*) return 0 ;; esac
354         return 1
355 }
356
357 handle_bad_merge_base() {
358         _badmb="$1"
359         _good="$2"
360         if is_expected_rev "$_badmb"; then
361                 cat >&2 <<EOF
362 The merge base $_badmb is bad.
363 This means the bug has been fixed between $_badmb and [$_good].
364 EOF
365                 exit 3
366         else
367                 cat >&2 <<EOF
368 Some good revs are not ancestor of the bad rev.
369 git bisect cannot work properly in this case.
370 Maybe you mistake good and bad revs?
371 EOF
372                 exit 1
373         fi
374 }
375
376 handle_skipped_merge_base() {
377         _mb="$1"
378         _bad="$2"
379         _good="$3"
380         cat >&2 <<EOF
381 Warning: the merge base between $_bad and [$_good] must be skipped.
382 So we cannot be sure the first bad commit is between $_mb and $_bad.
383 We continue anyway.
384 EOF
385 }
386
387 #
388 # "check_merge_bases" checks that merge bases are not "bad".
389 #
390 # - If one is "good", that's good, we have nothing to do.
391 # - If one is "bad", it means the user assumed something wrong
392 # and we must exit.
393 # - If one is "skipped", we can't know but we should warn.
394 # - If we don't know, we should check it out and ask the user to test.
395 #
396 # In the last case we will return 1, and otherwise 0.
397 #
398 check_merge_bases() {
399         _bad="$1"
400         _good="$2"
401         _skip="$3"
402         for _mb in $(git merge-base --all $_bad $_good)
403         do
404                 if is_among "$_mb" "$_good"; then
405                         continue
406                 elif test "$_mb" = "$_bad"; then
407                         handle_bad_merge_base "$_bad" "$_good"
408                 elif is_among "$_mb" "$_skip"; then
409                         handle_skipped_merge_base "$_mb" "$_bad" "$_good"
410                 else
411                         bisect_checkout "$_mb" "a merge base must be tested"
412                         return 1
413                 fi
414         done
415         return 0
416 }
417
418 #
419 # "check_good_are_ancestors_of_bad" checks that all "good" revs are
420 # ancestor of the "bad" rev.
421 #
422 # If that's not the case, we need to check the merge bases.
423 # If a merge base must be tested by the user we return 1 and
424 # otherwise 0.
425 #
426 check_good_are_ancestors_of_bad() {
427         test -f "$GIT_DIR/BISECT_ANCESTORS_OK" &&
428                 return
429
430         _bad="$1"
431         _good=$(echo $2 | sed -e 's/\^//g')
432         _skip="$3"
433
434         # Bisecting with no good rev is ok
435         test -z "$_good" && return
436
437         _side=$(git rev-list $_good ^$_bad)
438         if test -n "$_side"; then
439                 # Return if a checkout was done
440                 check_merge_bases "$_bad" "$_good" "$_skip" || return
441         fi
442
443         : > "$GIT_DIR/BISECT_ANCESTORS_OK"
444
445         return 0
446 }
447
448 bisect_next() {
449         case "$#" in 0) ;; *) usage ;; esac
450         bisect_autostart
451         bisect_next_check good
452
453         # Get bad, good and skipped revs
454         bad=$(git rev-parse --verify refs/bisect/bad) &&
455         good=$(git for-each-ref --format='^%(objectname)' \
456                 "refs/bisect/good-*" | tr '\012' ' ') &&
457         skip=$(git for-each-ref --format='%(objectname)' \
458                 "refs/bisect/skip-*" | tr '\012' ' ') &&
459
460         # Maybe some merge bases must be tested first
461         check_good_are_ancestors_of_bad "$bad" "$good" "$skip"
462         # Return now if a checkout has already been done
463         test "$?" -eq "1" && return
464
465         # Get bisection information
466         BISECT_OPT=''
467         test -n "$skip" && BISECT_OPT='--bisect-all'
468         eval="git rev-list --bisect-vars $BISECT_OPT $good $bad --" &&
469         eval="$eval $(cat "$GIT_DIR/BISECT_NAMES")" &&
470         eval=$(filter_skipped "$eval" "$skip") &&
471         eval "$eval" || exit
472
473         if [ -z "$bisect_rev" ]; then
474                 echo "$bad was both good and bad"
475                 exit 1
476         fi
477         if [ "$bisect_rev" = "$bad" ]; then
478                 exit_if_skipped_commits "$bisect_tried"
479                 echo "$bisect_rev is first bad commit"
480                 git diff-tree --pretty $bisect_rev
481                 exit 0
482         fi
483
484         # We should exit here only if the "bad"
485         # commit is also a "skip" commit (see above).
486         exit_if_skipped_commits "$bisect_rev"
487
488         bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this"
489 }
490
491 bisect_visualize() {
492         bisect_next_check fail
493
494         if test $# = 0
495         then
496                 case "${DISPLAY+set}${MSYSTEM+set}${SECURITYSESSIONID+set}" in
497                 '')     set git log ;;
498                 set*)   set gitk ;;
499                 esac
500         else
501                 case "$1" in
502                 git*|tig) ;;
503                 -*)     set git log "$@" ;;
504                 *)      set git "$@" ;;
505                 esac
506         fi
507
508         not=$(git for-each-ref --format='%(refname)' "refs/bisect/good-*")
509         eval '"$@"' refs/bisect/bad --not $not -- $(cat "$GIT_DIR/BISECT_NAMES")
510 }
511
512 bisect_reset() {
513         test -s "$GIT_DIR/BISECT_START" || {
514                 echo "We are not bisecting."
515                 return
516         }
517         case "$#" in
518         0) branch=$(cat "$GIT_DIR/BISECT_START") ;;
519         1) git show-ref --verify --quiet -- "refs/heads/$1" ||
520                die "$1 does not seem to be a valid branch"
521            branch="$1" ;;
522         *)
523             usage ;;
524         esac
525         git checkout "$branch" && bisect_clean_state
526 }
527
528 bisect_clean_state() {
529         # There may be some refs packed during bisection.
530         git for-each-ref --format='%(refname) %(objectname)' refs/bisect/\* |
531         while read ref hash
532         do
533                 git update-ref -d $ref $hash || exit
534         done
535         rm -f "$GIT_DIR/BISECT_EXPECTED_REV" &&
536         rm -f "$GIT_DIR/BISECT_ANCESTORS_OK" &&
537         rm -f "$GIT_DIR/BISECT_LOG" &&
538         rm -f "$GIT_DIR/BISECT_NAMES" &&
539         rm -f "$GIT_DIR/BISECT_RUN" &&
540         # Cleanup head-name if it got left by an old version of git-bisect
541         rm -f "$GIT_DIR/head-name" &&
542
543         rm -f "$GIT_DIR/BISECT_START"
544 }
545
546 bisect_replay () {
547         test -r "$1" || die "cannot read $1 for replaying"
548         bisect_reset
549         while read git bisect command rev
550         do
551                 test "$git $bisect" = "git bisect" -o "$git" = "git-bisect" || continue
552                 if test "$git" = "git-bisect"; then
553                         rev="$command"
554                         command="$bisect"
555                 fi
556                 case "$command" in
557                 start)
558                         cmd="bisect_start $rev"
559                         eval "$cmd" ;;
560                 good|bad|skip)
561                         bisect_write "$command" "$rev" ;;
562                 *)
563                         die "?? what are you talking about?" ;;
564                 esac
565         done <"$1"
566         bisect_auto_next
567 }
568
569 bisect_run () {
570     bisect_next_check fail
571
572     while true
573     do
574       echo "running $@"
575       "$@"
576       res=$?
577
578       # Check for really bad run error.
579       if [ $res -lt 0 -o $res -ge 128 ]; then
580           echo >&2 "bisect run failed:"
581           echo >&2 "exit code $res from '$@' is < 0 or >= 128"
582           exit $res
583       fi
584
585       # Find current state depending on run success or failure.
586       # A special exit code of 125 means cannot test.
587       if [ $res -eq 125 ]; then
588           state='skip'
589       elif [ $res -gt 0 ]; then
590           state='bad'
591       else
592           state='good'
593       fi
594
595       # We have to use a subshell because "bisect_state" can exit.
596       ( bisect_state $state > "$GIT_DIR/BISECT_RUN" )
597       res=$?
598
599       cat "$GIT_DIR/BISECT_RUN"
600
601       if grep "first bad commit could be any of" "$GIT_DIR/BISECT_RUN" \
602                 > /dev/null; then
603           echo >&2 "bisect run cannot continue any more"
604           exit $res
605       fi
606
607       if [ $res -ne 0 ]; then
608           echo >&2 "bisect run failed:"
609           echo >&2 "'bisect_state $state' exited with error code $res"
610           exit $res
611       fi
612
613       if grep "is first bad commit" "$GIT_DIR/BISECT_RUN" > /dev/null; then
614           echo "bisect run success"
615           exit 0;
616       fi
617
618     done
619 }
620
621
622 case "$#" in
623 0)
624     usage ;;
625 *)
626     cmd="$1"
627     shift
628     case "$cmd" in
629     help)
630         git bisect -h ;;
631     start)
632         bisect_start "$@" ;;
633     bad|good|skip)
634         bisect_state "$cmd" "$@" ;;
635     next)
636         # Not sure we want "next" at the UI level anymore.
637         bisect_next "$@" ;;
638     visualize|view)
639         bisect_visualize "$@" ;;
640     reset)
641         bisect_reset "$@" ;;
642     replay)
643         bisect_replay "$@" ;;
644     log)
645         cat "$GIT_DIR/BISECT_LOG" ;;
646     run)
647         bisect_run "$@" ;;
648     *)
649         usage ;;
650     esac
651 esac