Subject: Re: Reachability lists in git

From: Junio C Hamano <[email-masked]>
Date: Tue, 18 Nov 2014 13:05:29 -0800

Alan Stern <[email-masked]> writes:

> On Tue, 18 Nov 2014, Jonathan Nieder wrote:
>
>> Alan Stern wrote:
>> 
>> > Tracking down regressions.  Bisection isn't perfect.  Suppose a
>> > bisection run ends up saying that B is the first bad commit.  It's easy
>> > enough to build B and test it, to verify that it really is bad.
>> >
>> > But to be sure that B introduced the fault, it would help to find the
>> > latest commit that doesn't include B's changes -- that is, the latest
>> > commit that B isn't reachable from (or the maximal elements in the set
>> > of all such commits).
>> 
>> Isn't that B^ (or B^ and B^2, if B is a merge)?
>
> No.  Here's a simple example:
>
>             Y
>            /
>           /
>          X--B
>
> In this diagram, X = B^.  But B isn't reachable from either X or Y, 
> whereas it is reachable from one of X's children (namely Y).

Around here when we draw history horizontally we place parents on
the left hand side and the children on the right hand side.  X is
B's parent and does not include B's changes.  Y is not B's parent.
Y is a child of X so it has all the imperfection of X inherited to
it (except the ones that is fixed by Y itself), but there is no way
it inherited the bug B introduced relative to X.

Why do you say B is reachable from Y?

If you mean that B is a merge between X and Y, then that is already
covered by what Jonathan wrote "(or B^ and B^2 if B is a merge)".

    X----Y
     \    \
      .----B

Admittedly it is a needless merge (there should normally be one or
more commits between X and B on the other branch to make a merge B
worthwhile---you could just have fast forwarded Y to B), but that
does not break the reachability or bisectability in any way.

Confused...