Re: Reachability lists in git

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 18, 2014, 21:05 UTC
Message-ID: <xmqqa93ousme.fsf@gitster.dls.corp.google.com>
In-Reply-To: <Pine.LNX.4.44L0.1411181541590.2918-100000@iolanthe.rowland.org>

Alan Stern <stern@rowland.harvard.edu> writes:

Show 24 quoted lines

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