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

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(-)

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

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(-)

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(-)

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(-)

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

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

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

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

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

Am 24.07.2011 07:57, schrieb Jon Seymour:

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

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?

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

On Sun, Jul 24, 2011 at 6:05 PM, Johannes Sixt <j6t@kdbg.org> wrote:

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.

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.

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.

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

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?

On Mon, Jul 25, 2011 at 4:35 AM, Junio C Hamano <gitster@pobox.com> wrote:

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

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].

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.

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

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

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.

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.

On Tue, Jul 26, 2011 at 4:14 AM, Junio C Hamano <gitster@pobox.com> wrote:

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.

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.

How about a compromise such as:

    --no-checkout[=<ref>]

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

jon.

Am 25.07.2011 11:28, schrieb Jon Seymour:

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

On Tue, Jul 26, 2011 at 4:48 AM, Johannes Sixt <j6t@kdbg.org> wrote:

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.

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.

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

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

2011/7/26 Jakub Narebski <jnareb@gmail.com>:

Ah, yes, I see you are correct.

Sorry!

jon.

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.