From 9f199b159580545c39716fd87038f8ff7cd0eace Mon Sep 17 00:00:00 2001 From: Christian Couder Date: Sat, 21 Feb 2009 09:26:01 +0100 Subject: rev-list: estimate number of bisection step left This patch teaches "git rev-list --bisect-vars" to output an estimate of the number of bisection step left _after the current one_ along with the other variables it already outputs. This patch also makes "git-bisect.sh" display this number of steps left _after the current one_, along with the estimate of the number of revisions left to test (after the current one). Here is a table to help analyse what should be the best estimate for the number of bisect steps left. N : linear case --> probabilities --> best ------------------------------------------------------------- 1 : G-B --> 0 --> 0 2 : G-U1-B --> 0 --> 0 3 : G-U1-U2-B --> 0(1/3) 1(2/3) --> 1 4 : G-U1-U2-U3-B --> 1 --> 1 5 : G-U1-U2-U3-U4-B --> 1(3/5) 2(2/5) --> 1 6 : G-U1-U2-U3-U4-U5-B --> 1(2/6) 2(4/6) --> 2 7 : G-U1-U2-U3-U4-U5-U6-B --> 1(1/7) 2(6/7) --> 2 8 : G-U1-U2-U3-U4-U5-U6-U7-B --> 2 --> 2 9 : G-U1-U2-U3-U4-U5-U6-U7-U8-B --> 2(7/9) 3(2/9) --> 2 10: G-U1-U2-U3-U4-U5-U6-U7-U8-U9-B --> 2(6/10)3(4/10)--> 2 In the column "N", there is the number of revisions that could _now_ be the first bad commit we are looking for. The "linear case" column describes the linear history corresponding to the number in column N. G means good, B means bad, and Ux means unknown. Note that the first bad revision we are looking for can be any Ux or B. In the "probabilities" column, there are the different outcomes in number of steps with the odds of each outcome in parenthesis corresponding to the linear case. The "best" column gives the most accurate estimate among the different outcomes in the "probabilities" column. We have the following: best(2^n) == n - 1 and for any x between 0 included and 2^n excluded, the probability for n - 1 steps left looks like: P(2^n + x) == (2^n - x) / (2^n + x) and P(2^n + x) < 0.5 means 2^n < 3x So the algorithm used in this patch calculates 2^n and x, and then choose between returning n - 1 and n. Signed-off-by: Christian Couder Signed-off-by: Junio C Hamano --- git-bisect.sh | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'git-bisect.sh') diff --git a/git-bisect.sh b/git-bisect.sh index 10ad340920..e313bdea70 100755 --- a/git-bisect.sh +++ b/git-bisect.sh @@ -512,7 +512,7 @@ bisect_next() { # commit is also a "skip" commit (see above). exit_if_skipped_commits "$bisect_rev" - bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this" + bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this (roughly $bisect_steps steps)" } bisect_visualize() { -- cgit v1.2.1 From f3a186ffade15f793ea17713a10e10ec4f26ff11 Mon Sep 17 00:00:00 2001 From: Christian Couder Date: Sat, 4 Apr 2009 22:02:26 +0200 Subject: bisect: improve error message when branch checkout fails In "git-bisect.sh" the "git checkout" command is only used to change the current branch, but it is used like this: git checkout "$branch" which will output the following misleading error message when it fails: error: pathspec 'foo' did not match any file(s) known to git. This patch change the way we use "git checkout" like this: git checkout "$branch" -- so that we will get the following error message: fatal: invalid reference: foo which is better. Signed-off-by: Christian Couder Signed-off-by: Junio C Hamano --- git-bisect.sh | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'git-bisect.sh') diff --git a/git-bisect.sh b/git-bisect.sh index e313bdea70..df0ae63b4e 100755 --- a/git-bisect.sh +++ b/git-bisect.sh @@ -77,7 +77,7 @@ bisect_start() { then # Reset to the rev from where we started. start_head=$(cat "$GIT_DIR/BISECT_START") - git checkout "$start_head" || exit + git checkout "$start_head" -- || exit else # Get rev from where we start. case "$head" in @@ -370,7 +370,7 @@ bisect_checkout() { _msg="$2" echo "Bisecting: $_msg" mark_expected_rev "$_rev" - git checkout -q "$_rev" || exit + git checkout -q "$_rev" -- || exit git show-branch "$_rev" } @@ -549,7 +549,7 @@ bisect_reset() { *) usage ;; esac - git checkout "$branch" && bisect_clean_state + git checkout "$branch" -- && bisect_clean_state } bisect_clean_state() { -- cgit v1.2.1 From 23b5f18b50c15155f79618522b5721b880eceb65 Mon Sep 17 00:00:00 2001 From: Christian Couder Date: Thu, 26 Mar 2009 05:56:02 +0100 Subject: bisect: use "bisect--helper" and remove "filter_skipped" function Use the new "git bisect--helper" builtin. It should be faster and safer instead of the old "filter_skipped" shell function. And it is a first step to move more shell code to C. As the output is a little bit different we have to change the code that interpret the results. But these changes improve code clarity. Signed-off-by: Christian Couder Signed-off-by: Junio C Hamano --- git-bisect.sh | 89 ++++++++--------------------------------------------------- 1 file changed, 12 insertions(+), 77 deletions(-) (limited to 'git-bisect.sh') diff --git a/git-bisect.sh b/git-bisect.sh index e313bdea70..0f7590dfc2 100755 --- a/git-bisect.sh +++ b/git-bisect.sh @@ -279,76 +279,13 @@ bisect_auto_next() { bisect_next_check && bisect_next || : } -filter_skipped() { +eval_and_string_together() { _eval="$1" - _skip="$2" - - if [ -z "$_skip" ]; then - eval "$_eval" | { - while read line - do - echo "$line &&" - done - echo ':' - } - return - fi - # Let's parse the output of: - # "git rev-list --bisect-vars --bisect-all ..." eval "$_eval" | { - VARS= FOUND= TRIED= - while read hash line + while read line do - case "$VARS,$FOUND,$TRIED,$hash" in - 1,*,*,*) - # "bisect_foo=bar" read from rev-list output. - echo "$hash &&" - ;; - ,*,*,---*) - # Separator - ;; - ,,,bisect_rev*) - # We had nothing to search. - echo "bisect_rev= &&" - VARS=1 - ;; - ,,*,bisect_rev*) - # We did not find a good bisect rev. - # This should happen only if the "bad" - # commit is also a "skip" commit. - echo "bisect_rev='$TRIED' &&" - VARS=1 - ;; - ,,*,*) - # We are searching. - TRIED="${TRIED:+$TRIED|}$hash" - case "$_skip" in - *$hash*) ;; - *) - echo "bisect_rev=$hash &&" - echo "bisect_tried='$TRIED' &&" - FOUND=1 - ;; - esac - ;; - ,1,*,bisect_rev*) - # We have already found a rev to be tested. - VARS=1 - ;; - ,1,*,*) - ;; - *) - # Unexpected input - echo "die 'filter_skipped error'" - die "filter_skipped error " \ - "VARS: '$VARS' " \ - "FOUND: '$FOUND' " \ - "TRIED: '$TRIED' " \ - "hash: '$hash' " \ - "line: '$line'" - ;; - esac + echo "$line &&" done echo ':' } @@ -356,10 +293,12 @@ filter_skipped() { exit_if_skipped_commits () { _tried=$1 - if expr "$_tried" : ".*[|].*" > /dev/null ; then + _bad=$2 + if test -n "$_tried" ; then echo "There are only 'skip'ped commit left to test." echo "The first bad commit could be any of:" echo "$_tried" | tr '[|]' '[\012]' + test -n "$_bad" && echo "$_bad" echo "We cannot bisect more!" exit 2 fi @@ -490,28 +429,24 @@ bisect_next() { test "$?" -eq "1" && return # Get bisection information - BISECT_OPT='' - test -n "$skip" && BISECT_OPT='--bisect-all' - eval="git rev-list --bisect-vars $BISECT_OPT $good $bad --" && - eval="$eval $(cat "$GIT_DIR/BISECT_NAMES")" && - eval=$(filter_skipped "$eval" "$skip") && + eval="git bisect--helper --next-vars" && + eval=$(eval_and_string_together "$eval") && eval "$eval" || exit if [ -z "$bisect_rev" ]; then + # We should exit here only if the "bad" + # commit is also a "skip" commit (see above). + exit_if_skipped_commits "$bisect_tried" echo "$bad was both good and bad" exit 1 fi if [ "$bisect_rev" = "$bad" ]; then - exit_if_skipped_commits "$bisect_tried" + exit_if_skipped_commits "$bisect_tried" "$bad" echo "$bisect_rev is first bad commit" git diff-tree --pretty $bisect_rev exit 0 fi - # We should exit here only if the "bad" - # commit is also a "skip" commit (see above). - exit_if_skipped_commits "$bisect_rev" - bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this (roughly $bisect_steps steps)" } -- cgit v1.2.1 From e89aa6d2f546b2d4f2d88c15ce7e343751d6922f Mon Sep 17 00:00:00 2001 From: Christian Couder Date: Mon, 30 Mar 2009 06:59:59 +0200 Subject: bisect--helper: string output variables together with "&&" When doing: eval "git bisect--helper --next-vars" | { while read line do echo "$line &&" done echo ':' } the result code comes from the last "echo ':'", not from running "git bisect--helper --next-vars". This patch gets rid of the need to string together the line from the output of "git bisect--helper" with "&&" in the calling script by making "git bisect--helper --next-vars" return output variables already in that format. Signed-off-by: Christian Couder Signed-off-by: Junio C Hamano --- git-bisect.sh | 15 +-------------- 1 file changed, 1 insertion(+), 14 deletions(-) (limited to 'git-bisect.sh') diff --git a/git-bisect.sh b/git-bisect.sh index 0f7590dfc2..5074dda451 100755 --- a/git-bisect.sh +++ b/git-bisect.sh @@ -279,18 +279,6 @@ bisect_auto_next() { bisect_next_check && bisect_next || : } -eval_and_string_together() { - _eval="$1" - - eval "$_eval" | { - while read line - do - echo "$line &&" - done - echo ':' - } -} - exit_if_skipped_commits () { _tried=$1 _bad=$2 @@ -429,8 +417,7 @@ bisect_next() { test "$?" -eq "1" && return # Get bisection information - eval="git bisect--helper --next-vars" && - eval=$(eval_and_string_together "$eval") && + eval=$(eval "git bisect--helper --next-vars") && eval "$eval" || exit if [ -z "$bisect_rev" ]; then -- cgit v1.2.1 From 5a1d31c7e43a54c3a5275266745488de7208d871 Mon Sep 17 00:00:00 2001 From: Christian Couder Date: Sun, 19 Apr 2009 11:56:16 +0200 Subject: bisect: use "git bisect--helper --next-exit" in "git-bisect.sh" instead of "git bisect--helper --next-vars". Signed-off-by: Christian Couder Signed-off-by: Junio C Hamano --- git-bisect.sh | 39 +++++++++------------------------------ 1 file changed, 9 insertions(+), 30 deletions(-) (limited to 'git-bisect.sh') diff --git a/git-bisect.sh b/git-bisect.sh index 24712ff304..e1f300bed1 100755 --- a/git-bisect.sh +++ b/git-bisect.sh @@ -279,19 +279,6 @@ bisect_auto_next() { bisect_next_check && bisect_next || : } -exit_if_skipped_commits () { - _tried=$1 - _bad=$2 - if test -n "$_tried" ; then - echo "There are only 'skip'ped commit left to test." - echo "The first bad commit could be any of:" - echo "$_tried" | tr '[|]' '[\012]' - test -n "$_bad" && echo "$_bad" - echo "We cannot bisect more!" - exit 2 - fi -} - bisect_checkout() { _rev="$1" _msg="$2" @@ -416,25 +403,17 @@ bisect_next() { # Return now if a checkout has already been done test "$?" -eq "1" && return - # Get bisection information - eval=$(eval "git bisect--helper --next-vars") && - eval "$eval" || exit + # Perform bisection computation, display and checkout + git bisect--helper --next-exit + res=$? - if [ -z "$bisect_rev" ]; then - # We should exit here only if the "bad" - # commit is also a "skip" commit (see above). - exit_if_skipped_commits "$bisect_tried" - echo "$bad was both good and bad" - exit 1 - fi - if [ "$bisect_rev" = "$bad" ]; then - exit_if_skipped_commits "$bisect_tried" "$bad" - echo "$bisect_rev is first bad commit" - git diff-tree --pretty $bisect_rev - exit 0 - fi + # Check if we should exit because bisection is finished + test $res -eq 10 && exit 0 - bisect_checkout "$bisect_rev" "$bisect_nr revisions left to test after this (roughly $bisect_steps steps)" + # Check for an error in the bisection process + test $res -ne 0 && exit $res + + return 0 } bisect_visualize() { -- cgit v1.2.1 From de52f5a806f58c6b73b2e24768530213fab5a635 Mon Sep 17 00:00:00 2001 From: Christian Couder Date: Fri, 24 Apr 2009 08:29:00 +0200 Subject: bisect: use "git rev-parse --sq-quote" instead of a custom "sq" function As the "sq" function was the only place using Perl in "git-bisect.sh", this removes the Perl dependency in this script. While at it, we also remove the sed instruction in the Makefile that substituted @@PERL@@ with the Perl path in shell scripts, as this is not needed anymore. (It is now only needed in "git-instaweb.sh" but this command is dealt with separately in the Makefile.) Signed-off-by: Christian Couder Signed-off-by: Junio C Hamano --- git-bisect.sh | 16 +++------------- 1 file changed, 3 insertions(+), 13 deletions(-) (limited to 'git-bisect.sh') diff --git a/git-bisect.sh b/git-bisect.sh index e1f300bed1..786b7b9110 100755 --- a/git-bisect.sh +++ b/git-bisect.sh @@ -33,16 +33,6 @@ require_work_tree _x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]' _x40="$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40" -sq() { - @@PERL@@ -e ' - for (@ARGV) { - s/'\''/'\'\\\\\'\''/g; - print " '\''$_'\''"; - } - print "\n"; - ' "$@" -} - bisect_autostart() { test -s "$GIT_DIR/BISECT_START" || { echo >&2 'You need to start by "git bisect start"' @@ -107,7 +97,7 @@ bisect_start() { for arg; do case "$arg" in --) has_double_dash=1; break ;; esac done - orig_args=$(sq "$@") + orig_args=$(git rev-parse --sq-quote "$@") bad_seen=0 eval='' while [ $# -gt 0 ]; do @@ -147,7 +137,7 @@ bisect_start() { # Write new start state. # echo "$start_head" >"$GIT_DIR/BISECT_START" && - sq "$@" >"$GIT_DIR/BISECT_NAMES" && + git rev-parse --sq-quote "$@" >"$GIT_DIR/BISECT_NAMES" && eval "$eval" && echo "git bisect start$orig_args" >>"$GIT_DIR/BISECT_LOG" || exit # @@ -199,7 +189,7 @@ bisect_skip() { *..*) revs=$(git rev-list "$arg") || die "Bad rev input: $arg" ;; *) - revs=$(sq "$arg") ;; + revs=$(git rev-parse --sq-quote "$arg") ;; esac all="$all $revs" done -- cgit v1.2.1 From 0871984d304c9201b85897743eae583cd165106d Mon Sep 17 00:00:00 2001 From: Christian Couder Date: Sat, 9 May 2009 17:55:47 +0200 Subject: bisect: make "git bisect" use new "--next-all" bisect-helper function This patch replace the "--next-exit" option of "git bisect--helper" with a "--next-all" option that does merge base checking using the "check_good_are_ancestors_of_bad" function implemented in "bisect.c" in a former patch. The new "--next-all" option is then used in "git-bisect.sh" instead of the "--next-exit" option, and all the shell functions in "git-bisect.sh" that are now unused are removed. Signed-off-by: Christian Couder Signed-off-by: Junio C Hamano --- git-bisect.sh | 127 +--------------------------------------------------------- 1 file changed, 2 insertions(+), 125 deletions(-) (limited to 'git-bisect.sh') diff --git a/git-bisect.sh b/git-bisect.sh index 786b7b9110..8969553658 100755 --- a/git-bisect.sh +++ b/git-bisect.sh @@ -167,10 +167,6 @@ is_expected_rev() { test "$1" = $(cat "$GIT_DIR/BISECT_EXPECTED_REV") } -mark_expected_rev() { - echo "$1" > "$GIT_DIR/BISECT_EXPECTED_REV" -} - check_expected_revs() { for _rev in "$@"; do if ! is_expected_rev "$_rev"; then @@ -269,132 +265,13 @@ bisect_auto_next() { bisect_next_check && bisect_next || : } -bisect_checkout() { - _rev="$1" - _msg="$2" - echo "Bisecting: $_msg" - mark_expected_rev "$_rev" - git checkout -q "$_rev" -- || exit - git show-branch "$_rev" -} - -is_among() { - _rev="$1" - _list="$2" - case "$_list" in *$_rev*) return 0 ;; esac - return 1 -} - -handle_bad_merge_base() { - _badmb="$1" - _good="$2" - if is_expected_rev "$_badmb"; then - cat >&2 <&2 <&2 < "$GIT_DIR/BISECT_ANCESTORS_OK" - - return 0 -} - bisect_next() { case "$#" in 0) ;; *) usage ;; esac bisect_autostart bisect_next_check good - # Get bad, good and skipped revs - bad=$(git rev-parse --verify refs/bisect/bad) && - good=$(git for-each-ref --format='^%(objectname)' \ - "refs/bisect/good-*" | tr '\012' ' ') && - skip=$(git for-each-ref --format='%(objectname)' \ - "refs/bisect/skip-*" | tr '\012' ' ') || exit - - # Maybe some merge bases must be tested first - check_good_are_ancestors_of_bad "$bad" "$good" "$skip" - # Return now if a checkout has already been done - test "$?" -eq "1" && return - - # Perform bisection computation, display and checkout - git bisect--helper --next-exit + # Perform all bisection computation, display and checkout + git bisect--helper --next-all res=$? # Check if we should exit because bisection is finished -- cgit v1.2.1