[RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Jon Seymour]

Currently git bisect assumes that the respository to be undamaged. This limits the usefulness
of git bisect when working with damaged repositories.

This series introduces an option, --ignore-checkout-failure, which can be used with 
"git bisect start" to indicate that checkout failures should be tolerated for the life
of the (new) bisection process. This allows git bisect to be used on damaged repositories. In
particular, it allows git bisect to be used to locate commits containing damaged trees.

If the --ignore-checkout-failure option is specified, then if git checkout fails either 
at the start of the bisection process or later while probing a new trial commit, then the 
checkout failure will be noisily ignored and the HEAD reference will be updated to the 
intended commit. This may leave the working tree and index in an inconsistent state
w.r.t the HEAD commit.

"git bisect reset" uses the same logic to restore the original HEAD reference. This allows
"git bisect reset" to work in circumstances where it might otherwise fail (for example, if 
the current HEAD contains a damaged tree).

Jon Seymour (9):
  bisect: add tests to document expected behaviour in presence of
    broken trees.
  bisect: introduce a --ignore-checkout-failure option to
    bisect--helper.
  bisect: implement support for --ignore-checkout-failure option
  bisect: introduce a helper function to tolerate checkout failures.
  bisect: replace existing calls to git checkout with
    bisect_checkout_with_ignore
  bisect: enable --ignore-checkout-failure in the porcelain.
  bisect: better diagnostics, in case of mis-typed option.
  bisect: add tests for --ignore-checkout-failure option.
  bisect: add documentation for --ignore-checkout-failure option.

 Documentation/git-bisect.txt |   13 ++++-
 bisect.c                     |   18 ++++++-
 bisect.h                     |    2 +-
 builtin/bisect--helper.c     |    8 ++-
 git-bisect.sh                |   36 +++++++++++--
 t/t6030-bisect-porcelain.sh  |  119 ++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 186 insertions(+), 10 deletions(-)

-- 
1.7.6.347.g96e0b.dirty

[PATCH 1/9] bisect: add tests to document expected behaviour in presence of broken trees.

[Jon Seymour]

Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
 t/t6030-bisect-porcelain.sh |   50 +++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 50 insertions(+), 0 deletions(-)

diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh
index b5063b6..2c14fb0 100755
--- a/t/t6030-bisect-porcelain.sh
+++ b/t/t6030-bisect-porcelain.sh
@@ -573,5 +573,55 @@ test_expect_success 'erroring out when using bad path parameters' '
 '
 
 #
+# This creates a broken branch which cannot be checked out because
+# the tree created has been deleted.
 #
+# H1-H2-H3-H4-H5-H6-H7  <--other
+#            \
+#             S5-S6'-S7'-S8'-S9  <--broken
+#
+# Commits marked with ' have a missing tree.
+#
+test_expect_success 'broken branch creation' '
+        git bisect reset &&
+        git checkout -b broken $HASH4 &&
+        add_line_into_file "5(broken): first line on a broken branch" hello2 &&
+        BROKEN_HASH5=$(git rev-parse --verify HEAD) &&
+        mkdir missing &&
+        :> missing/MISSING &&
+        git add missing/MISSING &&
+        git commit -m "Added file that will be deleted"
+        BROKEN_HASH6=$(git rev-parse --verify HEAD) &&
+        add_line_into_file "6(broken): second line on a broken branch" hello2 &&
+        BROKEN_HASH7=$(git rev-parse --verify HEAD) &&
+        add_line_into_file "7(broken): third line on a broken branch" hello2 &&
+        BROKEN_HASH8=$(git rev-parse --verify HEAD) &&
+        git rm missing/MISSING &&
+        git commit -m "Remove missing file"
+        BROKEN_HASH9=$(git rev-parse --verify HEAD) &&
+        rm .git/objects/39/f7e61a724187ab767d2e08442d9b6b9dab587d
+'
+
+echo "" > expected.ok
+cat > expected.missing-tree.default <<EOF
+fatal: unable to read tree 39f7e61a724187ab767d2e08442d9b6b9dab587d
+EOF
+cat > expected.missing-tree.ignored <<EOF
+fatal: unable to read tree 39f7e61a724187ab767d2e08442d9b6b9dab587d
+warn: checkout failed. Updating HEAD directly. The working tree and index may be inconsistent.
+EOF
+
+test_expect_success 'bisect fails if tree is broken on start commit' '
+        git bisect reset &&
+        test_must_fail git bisect start $BROKEN_HASH7 $HASH4 2>error.txt &&
+        test_cmp expected.missing-tree.default error.txt
+'
+
+test_expect_success 'bisect fails if tree is broken on trial commit' '
+        git bisect reset &&
+        test_must_fail git bisect start $BROKEN_HASH9 $HASH4 2>error.txt &&
+        git update-ref --no-deref HEAD broken &&
+        test_cmp expected.missing-tree.default error.txt
+'
+
 test_done
-- 
1.7.6.347.g96e0b.dirty

[PATCH 2/9] bisect: introduce a --ignore-checkout-failure option to bisect--helper.

[Jon Seymour]

This commit introduces an option --ignore-checkout-failure which will
allow git-bisect to tolerate checkout failures.

This commit simply parses the option, but does not otherwise process it.

Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
 bisect.c                 |    5 ++++-
 bisect.h                 |    2 +-
 builtin/bisect--helper.c |    8 ++++++--
 3 files changed, 11 insertions(+), 4 deletions(-)

diff --git a/bisect.c b/bisect.c
index dd7e8ed..ce04092 100644
--- a/bisect.c
+++ b/bisect.c
@@ -24,6 +24,7 @@ struct argv_array {
 
 static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
 static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
+static int module_ignore_checkout_failure = 0;
 
 /* bits #0-15 in revision.h */
 
@@ -909,7 +910,7 @@ static void show_diff_tree(const char *prefix, struct commit *commit)
  * the bisection process finished successfully.
  * In this case the calling shell script should exit 0.
  */
-int bisect_next_all(const char *prefix)
+int bisect_next_all(const char *prefix, const int ignore_checkout_failure)
 {
 	struct rev_info revs;
 	struct commit_list *tried;
@@ -917,6 +918,8 @@ int bisect_next_all(const char *prefix)
 	const unsigned char *bisect_rev;
 	char bisect_rev_hex[41];
 
+	module_ignore_checkout_failure = ignore_checkout_failure;
+
 	if (read_bisect_refs())
 		die("reading bisect refs failed");
 
diff --git a/bisect.h b/bisect.h
index 0862ce5..4851310 100644
--- a/bisect.h
+++ b/bisect.h
@@ -27,7 +27,7 @@ struct rev_list_info {
 	const char *header_prefix;
 };
 
-extern int bisect_next_all(const char *prefix);
+extern int bisect_next_all(const char *prefix, const int ignore_checkout_failure);
 
 extern int estimate_bisect_steps(int all);
 
diff --git a/builtin/bisect--helper.c b/builtin/bisect--helper.c
index 5b22639..f531458 100644
--- a/builtin/bisect--helper.c
+++ b/builtin/bisect--helper.c
@@ -3,17 +3,21 @@
 #include "parse-options.h"
 #include "bisect.h"
 
+
 static const char * const git_bisect_helper_usage[] = {
-	"git bisect--helper --next-all",
+	"git bisect--helper --next-all [ --ignore-checkout-failure ]",
 	NULL
 };
 
 int cmd_bisect__helper(int argc, const char **argv, const char *prefix)
 {
 	int next_all = 0;
+	int ignore_checkout_failure = 0;
 	struct option options[] = {
 		OPT_BOOLEAN(0, "next-all", &next_all,
 			    "perform 'git bisect next'"),
+		OPT_BOOLEAN(0, "ignore-checkout-failure", &ignore_checkout_failure,
+			    "ignore checkout failure"),
 		OPT_END()
 	};
 
@@ -24,5 +28,5 @@ int cmd_bisect__helper(int argc, const char **argv, const char *prefix)
 		usage_with_options(git_bisect_helper_usage, options);
 
 	/* next-all */
-	return bisect_next_all(prefix);
+	return bisect_next_all(prefix, ignore_checkout_failure);
 }
-- 
1.7.6.347.g96e0b.dirty

[PATCH 3/9] bisect: implement support for --ignore-checkout-failure option

[Jon Seymour]

If the option is not specified, git bisect has the current behaviour
in case of checkout failure. Specifically, it will exit immediately
with a non-zero status code.

With this commit, we allow checkout failures of damaged trees
to be ignored. To allow the bisect to proceed, as expected we
fall back to updating the HEAD ref directly.

This will leave the working tree and index in an inconsistent state, but
the user of --ignore-checkout-failure should expect that.

Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
 bisect.c |   13 ++++++++++++-
 1 files changed, 12 insertions(+), 1 deletions(-)

diff --git a/bisect.c b/bisect.c
index ce04092..993c48b 100644
--- a/bisect.c
+++ b/bisect.c
@@ -24,6 +24,7 @@ struct argv_array {
 
 static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
 static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
+static const char *argv_update_ref[] = {"update-ref", "--no-deref", "HEAD", NULL, NULL};
 static int module_ignore_checkout_failure = 0;
 
 /* bits #0-15 in revision.h */
@@ -716,8 +717,18 @@ static int bisect_checkout(char *bisect_rev_hex)
 
 	argv_checkout[2] = bisect_rev_hex;
 	res = run_command_v_opt(argv_checkout, RUN_GIT_CMD);
-	if (res)
+	if (res) {
+	  if (!module_ignore_checkout_failure) {
 		exit(res);
+	  } else {
+	    fprintf(stderr, "warn: checkout failed. Updating HEAD directly. The working tree and index may be inconsistent.\n");
+	    argv_update_ref[3] = bisect_rev_hex;
+	    res = run_command_v_opt(argv_update_ref, RUN_GIT_CMD);
+	    if (res) {
+	      die("update-ref --no-deref HEAD failed on %s", bisect_rev_hex);
+	    }
+	  }
+	}
 
 	argv_show_branch[1] = bisect_rev_hex;
 	return run_command_v_opt(argv_show_branch, RUN_GIT_CMD);
-- 
1.7.6.347.g96e0b.dirty

[PATCH 4/9] bisect: introduce a helper function to tolerate checkout failures.

[Jon Seymour]

In the case that git bisect is being used on a repo with damaged trees,
git checkout may not succeed.

This function allows checkout to succeed even if the current commit
references a damaged tree. This will be useful for git bisect reset, for example.

Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
 git-bisect.sh |   19 +++++++++++++++++++
 1 files changed, 19 insertions(+), 0 deletions(-)

diff --git a/git-bisect.sh b/git-bisect.sh
index b2186a8..486a860 100755
--- a/git-bisect.sh
+++ b/git-bisect.sh
@@ -34,6 +34,8 @@ 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"
 
+IGNORE_CHECKOUT_FAILURE=$(test -f "${GIT_DIR}/BISECT_IGNORE_CHECKOUT_FAILURE" && cat "${GIT_DIR}/BISECT_IGNORE_CHECKOUT_FAILURE")
+
 bisect_autostart() {
 	test -s "$GIT_DIR/BISECT_START" || {
 		(
@@ -325,6 +327,23 @@ bisect_visualize() {
 	eval '"$@"' --bisect -- $(cat "$GIT_DIR/BISECT_NAMES")
 }
 
+bisect_checkout_with_ignore()
+{
+    ref=$1
+    if test -z "$IGNORE_CHECKOUT_FAILURE"; then
+	git checkout "$ref" -- || exit
+    else
+	if git checkout "$ref" -- 2>/dev/null; then
+	# If the current tree contains missing objects
+	# git checkout will fail. It might be
+	# possible to recover from this if we update
+	# the HEAD first.
+	    git update-ref --no-deref HEAD "$ref" &&
+	    git checkout "$ref" -- || exit
+	fi
+    fi
+}
+
 bisect_reset() {
 	test -s "$GIT_DIR/BISECT_START" || {
 		gettext "We are not bisecting."; echo
-- 
1.7.6.347.g96e0b.dirty

[PATCH 5/9] bisect: replace existing calls to git checkout with bisect_checkout_with_ignore

[Jon Seymour]

Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
 git-bisect.sh |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/git-bisect.sh b/git-bisect.sh
index 486a860..ecbd5bf 100755
--- a/git-bisect.sh
+++ b/git-bisect.sh
@@ -76,7 +76,7 @@ bisect_start() {
 	then
 		# Reset to the rev from where we started.
 		start_head=$(cat "$GIT_DIR/BISECT_START")
-		git checkout "$start_head" -- || exit
+		bisect_checkout_with_ignore "$start_head"
 	else
 		# Get rev from where we start.
 		case "$head" in
@@ -359,7 +359,7 @@ bisect_reset() {
 	*)
 	    usage ;;
 	esac
-	if git checkout "$branch" -- ; then
+	if ( bisect_checkout_with_ignore "$branch" ) ; then
 		bisect_clean_state
 	else
 		die "$(eval_gettext "Could not check out original HEAD '\$branch'.
-- 
1.7.6.347.g96e0b.dirty

[PATCH 6/9] bisect: enable --ignore-checkout-failure in the porcelain.

[Jon Seymour]

Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
 git-bisect.sh |   10 ++++++++--
 1 files changed, 8 insertions(+), 2 deletions(-)

diff --git a/git-bisect.sh b/git-bisect.sh
index ecbd5bf..f3913ba 100755
--- a/git-bisect.sh
+++ b/git-bisect.sh
@@ -3,7 +3,7 @@
 USAGE='[help|start|bad|good|skip|next|reset|visualize|replay|log|run]'
 LONG_USAGE='git bisect help
         print this long help message.
-git bisect start [<bad> [<good>...]] [--] [<pathspec>...]
+git bisect start [--ignore-checkout-failure] [<bad> [<good>...]] [--] [<pathspec>...]
         reset bisect state and start bisection.
 git bisect bad [<rev>]
         mark <rev> a known-bad revision.
@@ -116,6 +116,11 @@ bisect_start() {
 		shift
 		break
 		;;
+	    --ignore-checkout-failure)
+		IGNORE_CHECKOUT_FAILURE=$arg
+		echo "$arg" > $GIT_DIR/BISECT_IGNORE_CHECKOUT_FAILURE
+		shift
+		;;
 	    *)
 		rev=$(git rev-parse -q --verify "$arg^{commit}") || {
 		    test $has_double_dash -eq 1 &&
@@ -293,7 +298,7 @@ bisect_next() {
 	bisect_next_check good
 
 	# Perform all bisection computation, display and checkout
-	git bisect--helper --next-all
+	git bisect--helper --next-all ${IGNORE_CHECKOUT_FAILURE}
 	res=$?
 
         # Check if we should exit because bisection is finished
@@ -379,6 +384,7 @@ bisect_clean_state() {
 	rm -f "$GIT_DIR/BISECT_LOG" &&
 	rm -f "$GIT_DIR/BISECT_NAMES" &&
 	rm -f "$GIT_DIR/BISECT_RUN" &&
+	rm -f "$GIT_DIR/BISECT_IGNORE_CHECKOUT_FAILURE" &&
 	# Cleanup head-name if it got left by an old version of git-bisect
 	rm -f "$GIT_DIR/head-name" &&
 
-- 
1.7.6.347.g96e0b.dirty

[PATCH 7/9] bisect: better diagnostics, in case of mis-typed option.

[Jon Seymour]

Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
 git-bisect.sh |    3 +++
 1 files changed, 3 insertions(+), 0 deletions(-)

diff --git a/git-bisect.sh b/git-bisect.sh
index f3913ba..3ae1aa9 100755
--- a/git-bisect.sh
+++ b/git-bisect.sh
@@ -121,6 +121,9 @@ bisect_start() {
 		echo "$arg" > $GIT_DIR/BISECT_IGNORE_CHECKOUT_FAILURE
 		shift
 		;;
+	    --*)
+		die "unrecognised option: $arg"
+		;;
 	    *)
 		rev=$(git rev-parse -q --verify "$arg^{commit}") || {
 		    test $has_double_dash -eq 1 &&
-- 
1.7.6.347.g96e0b.dirty

[PATCH 8/9] bisect: add tests for --ignore-checkout-failure option.

[Jon Seymour]

Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
 t/t6030-bisect-porcelain.sh |   69 +++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 69 insertions(+), 0 deletions(-)

diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh
index 2c14fb0..32fb434 100755
--- a/t/t6030-bisect-porcelain.sh
+++ b/t/t6030-bisect-porcelain.sh
@@ -624,4 +624,73 @@ test_expect_success 'bisect fails if tree is broken on trial commit' '
         test_cmp expected.missing-tree.default error.txt
 '
 
+test_expect_success 'bisect: --ignore-checkout-failure - start commit bad' '
+        git bisect reset &&
+        git bisect start $BROKEN_HASH7 $HASH4 --ignore-checkout-failure 2>error.txt
+        test_cmp expected.missing-tree.ignored error.txt &&
+        broken6=$(git rev-parse HEAD) &&
+        test "$broken6" = "$BROKEN_HASH6" &&
+        git bisect reset
+'
+
+test_expect_success 'bisect: --ignore-checkout-failure - trial commit bad' '
+        git bisect reset &&
+        git bisect start broken $HASH4 --ignore-checkout-failure 2>error.txt
+        test_cmp expected.missing-tree.ignored error.txt &&
+        broken6=$(git rev-parse HEAD) &&
+        test "$broken6" = "$BROKEN_HASH6" &&
+        git bisect reset
+'
+
+test_expect_success 'bisect: --ignore-checkout-failure - target before breakage' '
+        git bisect reset &&
+        git bisect start broken $HASH4 --ignore-checkout-failure 2>error.txt
+        test_cmp expected.missing-tree.ignored error.txt &&
+        broken6=$(git rev-parse HEAD) &&
+        test "$broken6" = "$BROKEN_HASH6" &&
+        git bisect bad HEAD &&
+        broken5=$(git rev-parse HEAD) &&
+        test "$broken5" = "$BROKEN_HASH5" &&
+        git bisect bad HEAD > my_bisect_log.txt &&
+        broken4=$(git rev-parse HEAD) &&
+        test "$broken4" = "$HASH4" &&
+        echo "$BROKEN_HASH5 is the first bad commit" > expected.txt &&
+        test_cmp expected.txt my_bisect_log.txt
+        git bisect reset
+'
+
+test_expect_success 'bisect: --ignore-checkout-failure - target in breakage' '
+        git bisect reset &&
+        git bisect start broken $HASH4 --ignore-checkout-failure 2>error.txt
+        test_cmp expected.missing-tree.ignored error.txt &&
+        broken6=$(git rev-parse HEAD) &&
+        test "$broken6" = "$BROKEN_HASH6" &&
+        git bisect bad HEAD &&
+        broken5=$(git rev-parse HEAD) &&
+        test "$broken5" = "$BROKEN_HASH5" &&
+        git bisect good HEAD > my_bisect_log.txt &&
+        broken6=$(git rev-parse HEAD) &&
+        test "$broken6" = "$BROKEN_HASH6" &&
+        echo "$BROKEN_HASH6 is the first bad commit" > expected.txt &&
+        test_cmp expected.txt my_bisect_log.txt
+        git bisect reset
+'
+
+test_expect_success 'bisect: --ignore-checkout-failure - target after breakage' '
+        git bisect reset &&
+        git bisect start broken $HASH4 --ignore-checkout-failure 2>error.txt
+        test_cmp expected.missing-tree.ignored error.txt &&
+        broken6=$(git rev-parse HEAD) &&
+        test "$broken6" = "$BROKEN_HASH6" &&
+        git bisect good HEAD &&
+        broken8=$(git rev-parse HEAD) &&
+        test "$broken8" = "$BROKEN_HASH8" &&
+        git bisect good HEAD > my_bisect_log.txt &&
+        broken9=$(git rev-parse HEAD) &&
+        test "$broken9" = "$BROKEN_HASH9" &&
+        echo "$BROKEN_HASH9 is the first bad commit" > expected.txt &&
+        test_cmp expected.txt my_bisect_log.txt
+        git bisect reset
+'
+
 test_done
-- 
1.7.6.347.g96e0b.dirty

[PATCH 9/9] bisect: add documentation for --ignore-checkout-failure option.

[Jon Seymour]

Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
 Documentation/git-bisect.txt |   13 ++++++++++++-
 1 files changed, 12 insertions(+), 1 deletions(-)

diff --git a/Documentation/git-bisect.txt b/Documentation/git-bisect.txt
index ab60a18..f7412a1 100644
--- a/Documentation/git-bisect.txt
+++ b/Documentation/git-bisect.txt
@@ -17,7 +17,7 @@ The command takes various subcommands, and different options depending
 on the subcommand:
 
  git bisect help
- git bisect start [<bad> [<good>...]] [--] [<paths>...]
+ git bisect start [--ignore-checkout-failure] [<bad> [<good>...]] [--] [<paths>...]
  git bisect bad [<rev>]
  git bisect good [<rev>...]
  git bisect skip [(<rev>|<range>)...]
@@ -263,6 +263,17 @@ rewind the tree to the pristine state.  Finally the script should exit
 with the status of the real test to let the "git bisect run" command loop
 determine the eventual outcome of the bisect session.
 
+OPTIONS
+-------
+--ignore-checkout-failure::
++
+This option, specified on the "git bisect start" subcommand, causes
+bisect to ignore checkout failures during the bisection process. This allows
+git bisect to be used on repositories that contain damaged trees. The
+user should expect that, in cases where checkout fails, the detached
+HEAD refers to the trial commit, but the working tree and index
+may differ from that commit.
+
 EXAMPLES
 --------
 
-- 
1.7.6.347.g96e0b.dirty

Re: [RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Johannes Sixt]

Am 24.07.2011 07:57, schrieb Jon Seymour:
> Currently git bisect assumes that the respository to be undamaged. This limits the usefulness
> of git bisect when working with damaged repositories.

So, what? Isn't a broken repository also (almost) useless w.r.t. log,
checkout, rebase, reset, push, fetch...?

> This series introduces an option, --ignore-checkout-failure, which can be used with 
> "git bisect start" to indicate that checkout failures should be tolerated for the life
> of the (new) bisection process. This allows git bisect to be used on damaged repositories. In
> particular, it allows git bisect to be used to locate commits containing damaged trees.

I have to wonder: why do you care only about git-bisect? If you want to
be able to use a broken repository, aren't there many more commands that
fail and for which you also want to have a similar work-around? Or is
git-bisect the only one where the work-around was missing?

> If the --ignore-checkout-failure option is specified, then if git checkout fails either 
> at the start of the bisection process or later while probing a new trial commit, then the 
> checkout failure will be noisily ignored and the HEAD reference will be updated to the 
> intended commit. This may leave the working tree and index in an inconsistent state
> w.r.t the HEAD commit.

But what is an inconsistent state good for? In general, it makes no
sense to decide whether the result is "good" or "bad" when you know in
advance that the checked-out state is inconsistent.

-- Hannes

Re: [RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Jon Seymour]

On Sun, Jul 24, 2011 at 6:05 PM, Johannes Sixt <j6t@kdbg.org> wrote:
> Am 24.07.2011 07:57, schrieb Jon Seymour:
>> Currently git bisect assumes that the respository to be undamaged. This limits the usefulness
>> of git bisect when working with damaged repositories.
>
> So, what? Isn't a broken repository also (almost) useless w.r.t. log,
> checkout, rebase, reset, push, fetch...?
>

The broken or missing commits in a broken repository are useless, but
all the other
commits and the things they reach may still be useful.

When trying to recover such things, git bisect could be a useful tool,
since it would allow one to automate discovery of the broken regions
of the graph. Once the broken regions have been isolated, grafts can
be used to cauterize the damaged regions, the remainder can be rescued
with git-filter-branch  and life goes on.

>> This series introduces an option, --ignore-checkout-failure, which can be used with
>> "git bisect start" to indicate that checkout failures should be tolerated for the life
>> of the (new) bisection process. This allows git bisect to be used on damaged repositories. In
>> particular, it allows git bisect to be used to locate commits containing damaged trees.
>
> I have to wonder: why do you care only about git-bisect? If you want to
> be able to use a broken repository, aren't there many more commands that
> fail and for which you also want to have a similar work-around? Or is
> git-bisect the only one where the work-around was missing?
>

git bisect is, in principle, a very useful tool for identifying
regions of damage in a broken repo.

I don't want to have to write another tool that does exactly what git
bisect does except for the checkout function which, for the purpose of
repo rescue, I do not need.

>
> But what is an inconsistent state good for? In general, it makes no
> sense to decide whether the result is "good" or "bad" when you know in
> advance that the checked-out state is inconsistent.
>

The inconsistent state is useful because I can use that state to
progress the bisection. In particular, I can write a test which checks
to see whether this particular commit is broken (can't reach its
parents or its tree). In fact, git status does just nicely for this
purpose.

And by using that test with git bisect I can discover the precise
boundaries of the broken regions of the graph.

Of course, I have no intention of doing any kind of development with a
repo in that state - the point is to only to make an existing tool
even more useful - by helping it deal with broken repos too.

jon.

Re: [RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Junio C Hamano]

Jon Seymour <jon.seymour@gmail.com> writes:

> ... In particular, it
> allows git bisect to be used to locate commits containing damaged trees.

I am afraid it wouldn't allow it, and I am not going to take this series
that adds an option to bisect to ignore errors during checkout.

Remember that bisection is to find a single event in the history whose
effect consistently persists in all the commits into the future from that
point.  For example, if you have this history:

    ---A---B---C

and there is a bitflip in a blob contained in the commit B's tree, you may
not be able to check it out. But that does _not_ mean you cannot check C
out due to a corrupt object in B. The change going from B to C may be to
remove that blob, for example. "A tree that refers to a corrupt object was
introduced by this commit" is not a single event whose effect cascades
through the history into the future [*1*].

Besides, if you have a corrupt commit, your history traversal may not even
be correct, as we won't be reading its parent pointers correctly.

Having said that, an option to bisect that does _not_ touch the index nor
the working tree at all may be a useful thing to have. The test you want
to run on the candidate revisions bisect suggests may not need a working
tree (e.g. it may be built around "git grep -e foo $revision -- $path"),
and it may work just as well for the bisection you wanted to do in your
broken repository.

[Footnote]

*1* Theoretically, you could turn it into such by using a test that wants
to traverse and verify all the objects reachable from the candidate
commit, e.g.

    $ git rev-list --objects $rev | git pack-objects --stdout >/dev/null

which would succeed on A, and fail on B and all the commits that reach B,
including C. Was that what you had in mind?

Re: [RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Jon Seymour]

On Mon, Jul 25, 2011 at 4:35 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Jon Seymour <jon.seymour@gmail.com> writes:
>
>> ... In particular, it
>> allows git bisect to be used to locate commits containing damaged trees.
>
> I am afraid it wouldn't allow it, and I am not going to take this series
> that adds an option to bisect to ignore errors during checkout.

Understand that you don't wish to accept the series, but I do think
you are mistaken about whether it will work.

>
> Remember that bisection is to find a single event in the history whose
> effect consistently persists in all the commits into the future from that
> point.  For example, if you have this history:
>
>    ---A---B---C
>
> and there is a bitflip in a blob contained in the commit B's tree, you may
> not be able to check it out. But that does _not_ mean you cannot check C
> out due to a corrupt object in B. The change going from B to C may be to
> remove that blob, for example. "A tree that refers to a corrupt object was
> introduced by this commit" is not a single event whose effect cascades
> through the history into the future [*1*].

I don't think you understood my intention. Suppose, I have

B4 - B5 - B6' - B7' - B8' - B9

such that B6 and B7 and B8 all contain a damaged tree, but B4, B5 and B9 don't
since it contains a different tree, then:

        git bisect start B8' B4 --ignore-checkout-failure &&
	git bisect run eval "git status >/dev/null 2>&1 || false"

will stop with bisect/bad = B6'

This is exactly the result I wanted, and I discover B6' with a binary
search, rather than a linear search.

(I could also discover B8' with a binary search by reversing the sense
of the test).

In other words, I don't understand why you say that it won't work -
since it clearly does work for the purposes which I intended.

For a real example, see [1].

>
> Besides, if you have a corrupt commit, your history traversal may not even
> be correct, as we won't be reading its parent pointers correctly.
>

Agreed. This only works when you have dealt with broken commits by
applying suitable grafts.

I noticed a neat heuristic for doing this is to compute the diff
between the first good commit after the broken
region and the first good dangling commit (as reported by fsck) - the
one with the smallest delta may well be
a suitable object to use as one end of the graft. [ needs to be sanity
checked, of course ]. It may not be perfect,
but when the objective is to get a consistent (in the sense of fsck),
if incomplete repository, it may well do.

> Having said that, an option to bisect that does _not_ touch the index nor
> the working tree at all may be a useful thing to have. The test you want
> to run on the candidate revisions bisect suggests may not need a working
> tree (e.g. it may be built around "git grep -e foo $revision -- $path"),
> and it may work just as well for the bisection you wanted to do in your
> broken repository.
>

I am happy to do this, since clearly enables a superset of the cases
handled by --ignore-checkout-failure.

I propose to do this with a new ref (perhaps BISECT_CURSOR) which will
be used in place of HEAD
for the purposes of driving the bisection algorithm if --no-checkout
has been specified on the
git bisect start command.

Any comments?

jon.

----------------
[1] a test execution that shows that the bisection does, in fact, help
to identify the boundaries of a broken region.

(Note NEAREST could also be discovered with a binary search, but this
isn't done in this example).

expecting success:
        git bisect reset &&
	NEAREST=$(git rev-list broken | while read c
	do
	    git ls-tree -r $c >/dev/null || {
	    	echo $c;
		exit 0;
	    }
	done) &&
        git bisect start $NEAREST $HASH1 --ignore-checkout-failure &&
	git bisect run eval "git status >/dev/null 2>&1 || false" >
my_bisect_log.txt &&
        grep "$BROKEN_HASH6 is the first bad commit" my_bisect_log.txt

We are not bisecting.
error: Could not read 39f7e61a724187ab767d2e08442d9b6b9dab587d
Bisecting: 3 revisions left to test after this (roughly 2 steps)
fatal: unable to read tree 39f7e61a724187ab767d2e08442d9b6b9dab587d
warn: checkout failed. Updating HEAD directly. The working tree and
index may be inconsistent.
[32a594a3fdac2d57cf6d02987e30eec68511498c] Add <4: Ciao for now> into <hello>.
fatal: unable to read tree 39f7e61a724187ab767d2e08442d9b6b9dab587d
warn: checkout failed. Updating HEAD directly. The working tree and
index may be inconsistent.
fatal: unable to read tree 39f7e61a724187ab767d2e08442d9b6b9dab587d
warn: checkout failed. Updating HEAD directly. The working tree and
index may be inconsistent.
1b0312df05d867dc49f5d9f82617ee42cce1430d is the first bad commit
ok 49 - bisect: find the first inconsistent commit

Re: [RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Junio C Hamano]

Jon Seymour <jon.seymour@gmail.com> writes:

> I don't think you understood my intention. Suppose, I have
>
> B4 - B5 - B6' - B7' - B8' - B9
>
> such that B6 and B7 and B8 all contain a damaged tree, but B4, B5 and B9 don't
> since it contains a different tree, then:

What prevents your disk from corrupting a blob that was in B6, modified by
commit B7, and then _reverted_ by commit B8? Then your checkout would fail
at B6 and B8 but B7 will be fine.

As I wrote in my footnote, if your test is to find the most recent commit,
starting from which all the objects reachable from it are not corrupt (by
using "rev-list --objects $commit | pack-objects"), you could run your
bisect by somehow first finding a good commit (B5) that passes the test,
and after knowing a bad commit (B8) that does not pass (because it is
missing the single blob that is unreadable for B6 and B8), and then bisect
using a slightly less expensive test

	rev-list --objects B5..$commit | pack-objects

to find it in theory, but "Being unable to check-out" is not an isolated
event and cannot be used as the check as you seem to think.

>> Having said that, an option to bisect that does _not_ touch the index nor
>> the working tree at all may be a useful thing to have. The test you want
>> to run on the candidate revisions bisect suggests may not need a working
>> tree (e.g. it may be built around "git grep -e foo $revision -- $path"),
>> and it may work just as well for the bisection you wanted to do in your
>> broken repository.
>
> I am happy to do this, since clearly enables a superset of the cases
> handled by --ignore-checkout-failure.
>
> I propose to do this with a new ref (perhaps BISECT_CURSOR) which will
> be used in place of HEAD for the purposes of driving the bisection
> algorithm if --no-checkout has been specified on the git bisect start
> command.

Pros of using HEAD (i.e. the only change under the new mode would be that
we do not touch the index nor the working tree) is that the test you would
need to run in each step of bisection can use the familiar HEAD ref
instead of a strange BISECT_CURSOR, "bisect reset" will take you back from
the tentative detached HEAD state the usual way, and most likely the
necessary change to git-bisect.sh would be smaller. Cons of using HEAD
would be that the index and the working tree will be totally out-of-sync
with respect to HEAD during the bisection (by definition---as that is the
point of this new mode). One could argue that a naïve user might get
confused, but I am not sure how big a practical downside it would be.

Re: [RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Johannes Sixt]

Am 25.07.2011 11:28, schrieb Jon Seymour:
> On Mon, Jul 25, 2011 at 4:35 AM, Junio C Hamano <gitster@pobox.com> wrote:
>> Jon Seymour <jon.seymour@gmail.com> writes:
>>
>>> ... In particular, it
>>> allows git bisect to be used to locate commits containing damaged trees.
>>
>> I am afraid it wouldn't allow it, and I am not going to take this series
>> that adds an option to bisect to ignore errors during checkout.
> 
> Understand that you don't wish to accept the series, but I do think
> you are mistaken about whether it will work.
> 
>>
>> Remember that bisection is to find a single event in the history whose
>> effect consistently persists in all the commits into the future from that
>> point.  For example, if you have this history:
>>
>>    ---A---B---C
>>
>> and there is a bitflip in a blob contained in the commit B's tree, you may
>> not be able to check it out. But that does _not_ mean you cannot check C
>> out due to a corrupt object in B. The change going from B to C may be to
>> remove that blob, for example. "A tree that refers to a corrupt object was
>> introduced by this commit" is not a single event whose effect cascades
>> through the history into the future [*1*].
> 
> I don't think you understood my intention. Suppose, I have
> 
> B4 - B5 - B6' - B7' - B8' - B9
> 
> such that B6 and B7 and B8 all contain a damaged tree, but B4, B5 and B9 don't
> since it contains a different tree, then:
> 
>         git bisect start B8' B4 --ignore-checkout-failure &&
> 	git bisect run eval "git status >/dev/null 2>&1 || false"
> 
> will stop with bisect/bad = B6'
> 
> This is exactly the result I wanted, and I discover B6' with a binary
> search, rather than a linear search.
> 
> (I could also discover B8' with a binary search by reversing the sense
> of the test).

The fundamental preconditions of bisection are: that there is a single
event in the sequence, and that the effects of the event propagate to
the end of the sequence.

Junio explainded, that the second precondition is violated. Therefore,
you cannot apply git-bisect to find brokenness in a repository *in general*.

Of course, there may be special cases where stronger assumptions are
justifiable, and your case may have been one of them.

-- Hannes

Re: [RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Jon Seymour]

On Tue, Jul 26, 2011 at 4:14 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Jon Seymour <jon.seymour@gmail.com> writes:
>
>> I don't think you understood my intention. Suppose, I have
>>
>> B4 - B5 - B6' - B7' - B8' - B9
>>
>> such that B6 and B7 and B8 all contain a damaged tree, but B4, B5 and B9 don't
>> since it contains a different tree, then:
>
> What prevents your disk from corrupting a blob that was in B6, modified by
> commit B7, and then _reverted_ by commit B8? Then your checkout would fail
> at B6 and B8 but B7 will be fine.

But that's ok.

If B7's tree is fine, then the tree at B7 (if not the exact history
leading to the tree)
can be recovered by suitable grafts.

Also, the intent was not to use failure of git checkout as the test -
the intent was merely
to prevent a failure of git checkout from progressing the bisection.

The test for badness is something that would be run at each point in
the process.

I admit that git status is not a good test, since it is possible that
git update-ref --no-deref <target>
 && git checkout <target> will not restore a clean working tree and
index at each step,
even for good commits.

Of course, this is all rather academic since I agree your suggestion
of a --no-checkout option is a more general purpose solution
which can do all that --ignore-checkout-failure does and more.

>
> As I wrote in my footnote, if your test is to find the most recent commit,
> starting from which all the objects reachable from it are not corrupt (by
> using "rev-list --objects $commit | pack-objects"), you could run your
> bisect by somehow first finding a good commit (B5) that passes the test,
> and after knowing a bad commit (B8) that does not pass (because it is
> missing the single blob that is unreadable for B6 and B8), and then bisect
> using a slightly less expensive test
>
>        rev-list --objects B5..$commit | pack-objects
>
> to find it in theory, but "Being unable to check-out" is not an isolated
> event and cannot be used as the check as you seem to think.
>

I agree - a test that actually traverses the graph reachable from the
commits each tree and visits each object is better.

I'd tweak your snippet with --max-count=1, so that amount of work per
commit is limited.

Note that running git bisect --no-checkout will still be useful here
since it will limit the number of iterations that need to
be tested in order to find B5, for example.

>
> Pros of using HEAD (i.e. the only change under the new mode would be that
> we do not touch the index nor the working tree) is that the test you would
> need to run in each step of bisection can use the familiar HEAD ref
> instead of a strange BISECT_CURSOR, "bisect reset" will take you back from
> the tentative detached HEAD state the usual way, and most likely the
> necessary change to git-bisect.sh would be smaller. Cons of using HEAD
> would be that the index and the working tree will be totally out-of-sync
> with respect to HEAD during the bisection (by definition---as that is the
> point of this new mode). One could argue that a naïve user might get
> confused, but I am not sure how big a practical downside it would be.
>
>

How about a compromise such as:

    --no-checkout[=<ref>]

which defaults to HEAD, but can be specified as something else?

jon.

Re: [RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Jon Seymour]

On Tue, Jul 26, 2011 at 4:48 AM, Johannes Sixt <j6t@kdbg.org> wrote:
> Am 25.07.2011 11:28, schrieb Jon Seymour:
>> On Mon, Jul 25, 2011 at 4:35 AM, Junio C Hamano <gitster@pobox.com> wrote:
>>> Jon Seymour <jon.seymour@gmail.com> writes:
>
> The fundamental preconditions of bisection are: that there is a single
> event in the sequence, and that the effects of the event propagate to
> the end of the sequence.

More correctly: the fundamental pre-condition of a single round of
bisection finding an
event of interest is as you say.

There is nothing that prevents multiple rounds of bisection being
used, if required.

So, in my examples, may produce a limit commit such that the graph
between the limit and the tip
contains two regions of good commits and two regions of bad commits.
So, you keep applying rounds
of bisection until the bad regions identified have no good commits.

>
> Junio explainded, that the second precondition is violated. Therefore,
> you cannot apply git-bisect to find brokenness in a repository *in general*.
>

I never claimed that a single round of biseciton would be enough, in
general. Only that it would be useful to be able
to apply a bisection algorithm to broken repositories.

It seems clear to me that bisection is a very useful tool for probling
the extent of corruption in a broken repo.
It is certainly not the only tool, may not work in all cases (broken
commits) and may not be all you need.

Anyway, I agree that Junio's suggestion (e.g. --no-checkout) is a
better and more generally applicable than my original
(--ignore-checkout-failure) suggestion.

jon.

Re: [RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Jakub Narebski]

Jon Seymour <jon.seymour@gmail.com> writes:
> On Tue, Jul 26, 2011 at 4:48 AM, Johannes Sixt <j6t@kdbg.org> wrote:
>> Am 25.07.2011 11:28, schrieb Jon Seymour:
>>> On Mon, Jul 25, 2011 at 4:35 AM, Junio C Hamano <gitster@pobox.com> wrote:
>>>> Jon Seymour <jon.seymour@gmail.com> writes:
>>
>> The fundamental preconditions of bisection are: that there is a single
>> event in the sequence, and that the effects of the event propagate to
>> the end of the sequence.
> 
> More correctly: the fundamental pre-condition of a single round of
> bisection finding an event of interest is as you say.
> 
> There is nothing that prevents multiple rounds of bisection being
> used, if required.

No, it is not true.  Think of bisection as in original application, as
numerical methods used to find root of one dimensional function.  It
works if there is single root between starting endpoints, or rather if
endpoints have different signs.

Which means that it works in this case:


                        bad bad bad
                   BAD
   good good good


but won't work in this case:



   good good good               good good good
                   bad bad bad

-- 
Jakub Narębski

Re: [RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Jon Seymour]

2011/7/26 Jakub Narebski <jnareb@gmail.com>:
> No, it is not true.  Think of bisection as in original application, as
> numerical methods used to find root of one dimensional function.  It
> works if there is single root between starting endpoints, or rather if
> endpoints have different signs.
>

Ah, yes, I see you are correct.

Sorry!

jon.

Re: [RFC 0/9] bisect: allow git bisect to be used with repos containing damaged trees.

[Jon Seymour]

> Which means that it works in this case:
>
>
>                        bad bad bad
>                   BAD
>   good good good
>
>
> but won't work in this case:
>
>
>
>   good good good               good good good
>                   bad bad bad
>

Of course, this doesn't mean that bisection is useless, only that you
have to choose the right kind of test!

So, while it is true that a commit local test such as those I was
proposing (e.g. git ls-tree or even my suggested tweak git rev-list
--objects --max-count=1) will be useless unless you happen to start
with the tip at the bad commit, it is not true that bisection in
general is useless.

For example, Junio's unconstrained git rev-list --objects | git
pack-objects test will be sufficient because a history that is

    good good good bad bad bad good good good

according to a commit local test, will be:

     bad bad bad bad bad bad bad good good good

from the point of view of a test that reaches the entire graph
reachable from a commit.

It will still be beneficial to do log(N) executions of git rev-list
--objects instead of  N executions of the same.

jon.