Reachability lists in git

Reachability lists in git

[Alan Stern]

The "git rev-list A ^B" command lists all the commits that are
reachable from A but not from B.  Is there a comparable command for the
converse relation, that is, a command to list all the commits that A is
reachable from but B isn't?

And if there is such a command, can the output be limited to just the 
latest commits?  That is, list commit X if and only if A is reachable 
from X, B isn't reachable from X, and B is reachable from each of X's 
children?

Thanks,

Alan Stern

Re: Reachability lists in git

[Jonathan Nieder]

Hi,

Alan Stern wrote:

> The "git rev-list A ^B" command lists all the commits that are
> reachable from A but not from B.  Is there a comparable command for the
> converse relation, that is, a command to list all the commits that A is
> reachable from but B isn't?
>
> And if there is such a command, can the output be limited to just the
> latest commits?  That is, list commit X if and only if A is reachable
> from X, B isn't reachable from X, and B is reachable from each of X's
> children?

Someone else can answer your direct question, but you've got my
curiosity.  What is the application?

--ancestry-path is my current favorite tool for walking-forward needs.

Curious,
Jonathan

Re: Reachability lists in git

[Junio C Hamano]

Jonathan Nieder <jrnieder@gmail.com> writes:

> --ancestry-path is my current favorite tool for walking-forward needs.

Curious.  I often want to answer this question:

    Commit 982ac87 was reported to be faulty.  What topic was it on
    and at which point was it merged to 'master'?

     - What is the 'bottom' of the topic, that is, the commit
       reachable from the faulty commit that was already on 'master'
       when the faulty commit was written the first time?

     - What is the 'top' of the topic, that is, were there more
       commits made on top to build on the faulty commit on the
       topic before the whole thing was merged to 'master'?

     - Were there follow-up fixes and enhancements on the topic
       after the topic was merged to 'master' (this is harder)?

And my experiments with --ancestry-path has been less than ideal.

Re: Reachability lists in git

[Jonathan Nieder]

Junio C Hamano wrote:
> Jonathan Nieder <jrnieder@gmail.com> writes:

>> --ancestry-path is my current favorite tool for walking-forward needs.
>
> Curious.  I often want to answer this question:
[...]
> And my experiments with --ancestry-path has been less than ideal.

Thanks for an example.  I've found it works okay interactively, less
so for scripted use (so I wish there were something better, though I
haven't sketched out what that something better would look like).

>     Commit 982ac87 was reported to be faulty.  What topic was it on
>     and at which point was it merged to 'master'?

 $ git log --graph --ancestry-path 982ac87^..origin/master
[...]
 * | commit f30366b27a91dbc18328bccf3067cdfad4f0cfbc
 |/  Merge: 97fefaf efa5f82
 |   Author: Junio C Hamano <gitster@pobox.com>
 |   Date:   Wed Apr 3 09:34:04 2013 -0700
 |
 |       Merge branch 'jc/directory-attrs-regression-fix'
 |
 |       Fix 1.8.1.x regression that stopped matching "dir" (without
 |       trailing slash) to a directory "dir".
 |
 |       * jc/directory-attrs-regression-fix:
 |         t: check that a pattern without trailing slash matches a directory
 |         dir.c::match_pathname(): pay attention to the length of string parameters
 |         dir.c::match_pathname(): adjust patternlen when shifting pattern
 |         dir.c::match_basename(): pay attention to the length of string parameters
 |         attr.c::path_matches(): special case paths that end with a slash
 |         attr.c::path_matches(): the basename is part of the pathname
[...]
 |
 * commit 982ac87316a1cf5126888157bdcbfa32268ebe47
   Author: Jeff King <peff@peff.net>
   Date:   Thu Mar 28 17:47:47 2013 -0400

       dir.c::match_pathname(): adjust patternlen when shifting pattern

>      - What is the 'bottom' of the topic, that is, the commit
>        reachable from the faulty commit that was already on 'master'
>        when the faulty commit was written the first time?

 $ git tag the-merge f30366b27a91dbc18328bccf3067cdfad4f0cfbc
 $ git merge-base 982ac87 the-merge^
 9db9eecfe5c2490d17c0d4bd5452e4cb1d0948c5

>      - What is the 'top' of the topic, that is, were there more
>        commits made on top to build on the faulty commit on the
>        topic before the whole thing was merged to 'master'?

 $ git log --oneline 982ac87..the-merge^2
 efa5f82 t: check that a pattern without trailing slash matches a directory
 ab3aebc dir.c::match_pathname(): pay attention to the length of string parameters

>      - Were there follow-up fixes and enhancements on the topic
>        after the topic was merged to 'master' (this is harder)?

There's only one line coming out of the-merge^2 in the ancestry-path
graph, so there were no such follow-up fixes.

Jonathan

Re: Reachability lists in git

[Jonathan Nieder]

Jonathan Nieder wrote:
> Junio C Hamano wrote:

>>      - Were there follow-up fixes and enhancements on the topic
>>        after the topic was merged to 'master' (this is harder)?
>
> There's only one line coming out of the-merge^2 in the ancestry-path
> graph, so there were no such follow-up fixes.

Or rather, there are two lines, but the second is just a merge of the
same topic to maint-1.8.1.

And here following the railroad tracks becomes tedious.  gitk has a
nicer interface for "list children" and "go to child".

Re: Reachability lists in git

[Junio C Hamano]

Jonathan Nieder <jrnieder@gmail.com> writes:

> Junio C Hamano wrote:
>> Jonathan Nieder <jrnieder@gmail.com> writes:
>
>>> --ancestry-path is my current favorite tool for walking-forward needs.
>>
>> Curious.  I often want to answer this question:
> [...]
>> And my experiments with --ancestry-path has been less than ideal.
>
> Thanks for an example.  I've found it works okay interactively, less
> so for scripted use (so I wish there were something better, though I
> haven't sketched out what that something better would look like).
>
>>     Commit 982ac87 was reported to be faulty.  What topic was it on
>>     and at which point was it merged to 'master'?
>
>  $ git log --graph --ancestry-path 982ac87^..origin/master

Yup, that is what I've been using and was wishing that there would
be better alternatives.

Re: Reachability lists in git

[Alan Stern]

On Tue, 18 Nov 2014, Jonathan Nieder wrote:

> Hi,
> 
> Alan Stern wrote:
> 
> > The "git rev-list A ^B" command lists all the commits that are
> > reachable from A but not from B.  Is there a comparable command for the
> > converse relation, that is, a command to list all the commits that A is
> > reachable from but B isn't?
> >
> > And if there is such a command, can the output be limited to just the
> > latest commits?  That is, list commit X if and only if A is reachable
> > from X, B isn't reachable from X, and B is reachable from each of X's
> > children?
> 
> Someone else can answer your direct question, but you've got my
> curiosity.  What is the application?

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).  This is also important in cases where there are
multiple bugs and you want to investigate only the commits that don't
include one of the bugs.

Alan Stern

Re: Reachability lists in git

[Jonathan Nieder]

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

Re: Reachability lists in git

[Alan Stern]

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).  Therefore 
Y is the unique maximal commit which B is not reachable from.

Alan Stern

Re: Reachability lists in git

[Junio C Hamano]

Alan Stern <stern@rowland.harvard.edu> 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...

Re: Reachability lists in git

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Alan Stern <stern@rowland.harvard.edu> 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).
> ...
>
> 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
> ...

No, that cannot be what you meant.  I was confused.  The above
picture does not make B reachable from Y (it is the other way
around: B reaches Y).  The topology where B isn't reachable from
either X or Y and is reachable from Y would be

	X---Y	i.e. B = Y^2, X = Y^1 = B^1 
         \ /  
          B

If B is broken, and X is not, then Y would be contaminated by the
breakage B introduces relative to X, unless Y is an evil merge and
fixed that breakage while merging.

In any case, even if Y is found to be broken, its parent B is
already broken, so that does not place the blame on Y, does it?

Still confused why you feel Y is any significant...

Re: Reachability lists in git

[Alan Stern]

On Tue, 18 Nov 2014, Junio C Hamano wrote:

> Alan Stern <stern@rowland.harvard.edu> 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?

I omitted a negation by mistake, sorry.  I meant to say: "But B isn't
reachable from either X or Y, and it isn't reachable from one of X's
children (namely Y)."

Thus, if B introduced a bug, that bug would not be present in Y.  But Y 
might be better for testing than X, because Y might fix some other 
problems that are present in X.

Alan Stern

Re: Reachability lists in git

[Junio C Hamano]

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

>> > 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).
> ...
> Thus, if B introduced a bug, that bug would not be present in Y.  But Y 
> might be better for testing than X, because Y might fix some other 
> problems that are present in X.

The problem with that line of reasoning is that in real life there
will be unbound number of Y's that forked from a point before
somebody wrote B.  Which one among these Y's would you pick and why?

If Y has fixed another problem that is present in X and make it
easier to test, Z, a direct descendant of Y (i.e. Z^1 = Y), may have
fixed yet another problem that is unrelated to the problem B
introduced and it may make the result even easier to test.  Where do
you stop?

Still confused...

Re: Reachability lists in git

[Alan Stern]

On Tue, 18 Nov 2014, Junio C Hamano wrote:

> Alan Stern <stern@rowland.harvard.edu> writes:
> 
> >> > 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).
> > ...
> > Thus, if B introduced a bug, that bug would not be present in Y.  But Y 
> > might be better for testing than X, because Y might fix some other 
> > problems that are present in X.
> 
> The problem with that line of reasoning is that in real life there
> will be unbound number of Y's that forked from a point before
> somebody wrote B.  Which one among these Y's would you pick and why?

I don't know.  But I would like to see what is available.  I might even 
merge all those commits and test that (if there aren't any bad 
conflicts).

> If Y has fixed another problem that is present in X and make it
> easier to test, Z, a direct descendant of Y (i.e. Z^1 = Y), may have
> fixed yet another problem that is unrelated to the problem B
> introduced and it may make the result even easier to test.  Where do
> you stop?

If Y is maximal among the comments that B isn't reachable from and Z^ = 
Y then, by definition, B _is_ reachable from Z.  Therefore the bug 
introduced in B will be present in Z, unless it got fixed somewhere in 
between.  Either way, Z is not a good candidate for testing whereas Y 
is.

Alan Stern