Determining commit reachability

Determining commit reachability

[Artur Skawina]

Given commit C, refs (branches) R, S and T what would be the best way
to test whether 'C' is reachable from any of the heads?

Checking if `git rev-list -n1 O ^R ^S ^T` produces any output is what
i came up with; is there a better (ie faster) solution?

artur

Re: Determining commit reachability

[Jeff King]

On Sun, Sep 05, 2010 at 10:34:11PM +0200, Artur Skawina wrote:

> Given commit C, refs (branches) R, S and T what would be the best way
> to test whether 'C' is reachable from any of the heads?
> 
> Checking if `git rev-list -n1 O ^R ^S ^T` produces any output is what
> i came up with; is there a better (ie faster) solution?

I think that is about as fast as you will get. You could try something
with git-merge-base, but it should be about the same speed.

Note that neither will tell you _which_ head the target was reachable
from. For that, given the current interface you have to test each head
individually. If you write some C code, you can do it all in a single
traversal. See this thread for some discussion of how "git tag
--contains" can be sped up:

  http://article.gmane.org/gmane.comp.version-control.git/150039

-Peff

Re: Determining commit reachability

[Artur Skawina]

On 09/06/10 05:17, Jeff King wrote:
> On Sun, Sep 05, 2010 at 10:34:11PM +0200, Artur Skawina wrote:
> 
>> Given commit C, refs (branches) R, S and T what would be the best way
>> to test whether 'C' is reachable from any of the heads?
>>
>> Checking if `git rev-list -n1 O ^R ^S ^T` produces any output is what
>> i came up with; is there a better (ie faster) solution?
> 
> I think that is about as fast as you will get. You could try something
> with git-merge-base, but it should be about the same speed.
> 
> Note that neither will tell you _which_ head the target was reachable
> from. For that, given the current interface you have to test each head

As i think i'll only need this to prevent leaking (private) commits that
wouldn't be reachable from the (public) heads, just  catching the
unreachable ones should be enough.

$ time git rev-list -n1 v2.6.12 ^v33 ^v35
0m2.333s user   0m0.040s system   0m2.379s elapsed   99.77% CPU
$ time git rev-list -n1 v2.6.36-rc2 ^v33 ^v35
76be97c1fc945db08aae1f1b746012662d643e97
0m0.500s user   0m0.010s system   0m0.514s elapsed   99.13% CPU

A bit expensive, but I guess should it become a problem I could cache
the result and/or blacklist the client.

Thanks,

artur

Re: Determining commit reachability

[Junio C Hamano]

Artur Skawina <art.08.09@gmail.com> writes:

> Given commit C, refs (branches) R, S and T what would be the best way
> to test whether 'C' is reachable from any of the heads?

Depends on the definition of "best", but I often find myself typing

    git branch --with C

where C often is somewhere between 'master' and 'ko/master' (the 'master'
branch everybody else has already seen on k.org).  When I have second
thoughts sometime after applying a patch directly on top of 'master', I
need to see if I have built a new topic branch forking from the faulty
commit before rewinding it, as such a topic branch also needs to be
rewound.

Re: Determining commit reachability

[Sverre Rabbelier]

Heya,

On Mon, Sep 6, 2010 at 01:47, Junio C Hamano <gitster@pobox.com> wrote:
> Depends on the definition of "best", but I often find myself typing
>
>    git branch --with C

In case anyone else is wondering, '--with' is a hidden alias for '--contains'.

-- 
Cheers,

Sverre Rabbelier

Re: Determining commit reachability

[Ævar Arnfjörð Bjarmason]

On Mon, Sep 6, 2010 at 20:45, Sverre Rabbelier <srabbelier@gmail.com> wrote:
> Heya,
>
> On Mon, Sep 6, 2010 at 01:47, Junio C Hamano <gitster@pobox.com> wrote:
>> Depends on the definition of "best", but I often find myself typing
>>
>>    git branch --with C
>
> In case anyone else is wondering, '--with' is a hidden alias for '--contains'.

Maybe it should be documented?

Re: Determining commit reachability

[Sverre Rabbelier]

Heya,

On Mon, Sep 6, 2010 at 15:53, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
> On Mon, Sep 6, 2010 at 20:45, Sverre Rabbelier <srabbelier@gmail.com> wrote:
>> In case anyone else is wondering, '--with' is a hidden alias for '--contains'.
>
> Maybe it should be documented?

Junio added it that way back in "git-branch --contains=commit"
v1.5.3.6-879-g694a577 (Nov 7 2007) when the feature was added. Junio,
do you remember why you added "--with" as a hidden alias?

-- 
Cheers,

Sverre Rabbelier

Re: Determining commit reachability

[Junio C Hamano]

Sverre Rabbelier <srabbelier@gmail.com> writes:

> On Mon, Sep 6, 2010 at 15:53, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>> On Mon, Sep 6, 2010 at 20:45, Sverre Rabbelier <srabbelier@gmail.com> wrote:
>>> In case anyone else is wondering, '--with' is a hidden alias for '--contains'.
>>
>> Maybe it should be documented?
>
> Junio added it that way back in "git-branch --contains=commit"
> v1.5.3.6-879-g694a577 (Nov 7 2007) when the feature was added. Junio,
> do you remember why you added "--with" as a hidden alias?

It was originally called --with.  I wrote it to help me in the exact use
case in this thread, and the option was naturally named --with, as the
request I wanted to make was "Give me branches _with_ this commit, so that
I know which ones I need to rewind before reintegrating and publishing".

Somehow people wanted to see an option with a longer name, but by that
time my fingers were well trained, so I kept "--with" but didn't bother
advertising duplicated options.

[PATCH] Documentation: explain "git branch --with"

[Jonathan Nieder]

Junio C Hamano wrote:

> It was originally called --with.  I wrote it to help me in the exact use
> case in this thread, and the option was naturally named --with, as the
> request I wanted to make was "Give me branches _with_ this commit, so that
> I know which ones I need to rewind before reintegrating and publishing".
> 
> Somehow people wanted to see an option with a longer name, but by that
> time my fingers were well trained, so I kept "--with" but didn't bother
> advertising duplicated options.

More precisely, it is advertised by "git branch --help-all" but not
the manual or "git branch -h".

How about adding it to the man page so people can look up this option
after encountering it in the wild?

Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
---
 Documentation/git-branch.txt |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/Documentation/git-branch.txt b/Documentation/git-branch.txt
index 1940256..f479e2f 100644
--- a/Documentation/git-branch.txt
+++ b/Documentation/git-branch.txt
@@ -142,6 +142,7 @@ start-point is either a local or remote branch.
 	branch points to is not changed.
 
 --contains <commit>::
+--with <commit>::
 	Only list branches which contain the specified commit.
 
 --merged [<commit>]::
-- 
1.7.2.3

Re: [PATCH] Documentation: explain "git branch --with"

[Ævar Arnfjörð Bjarmason]

On Tue, Sep 7, 2010 at 05:52, Jonathan Nieder <jrnieder@gmail.com> wrote:
> How about adding it to the man page so people can look up this option
> after encountering it in the wild?

Much better, thanks.

Re: [PATCH] Documentation: explain "git branch --with"

[Junio C Hamano]

Jonathan Nieder <jrnieder@gmail.com> writes:

> More precisely, it is advertised by "git branch --help-all" but not
> the manual or "git branch -h".

Sorry, but I don't understand what you are trying to say here.  Isn't it
the whole point of distinction between --help-all vs -h (aka
PARSE_OPT_HIDDEN)?

Some interesting findings after a quick "grep" to see which ones are
hidden (potential bugs below might be good for janitors).

* apply --allow-binary-replacement, --binary

  These are always on, and are no-op (even --no-binary is a no-op);
  documented.

* archive -[2-8]

  git-archive manual page mentions -0 thru -9 can be used as "zip backend
  option", while explicitly describing -0 and -9.  "git archive -h" gives
  special description for -1 as well.  Perhaps we should be consistent and
  document -1 in the manual page.
  
* checkout --[no-]guess

  Controls the "dwim 'git checkout x' to 'git checkout -b x remote/x' when
  'x' cannot possibly name anything other than a branch that we copied
  from a remote repository uniquely"; since the dwimming is on by default,
  the only use case is to say --no-guess; not documented.

* clone --naked

  An old name used during the development for the current --bare option;
  not documented.

* commit --allow-empty --allow-empty-message

  Documented; hidden primarily to discourage their uses and also to keep
  output from 'commit -h' short.

* fmt-merge-msg --summary

  An old name used during the development for the current --log option;
  documented.

* grep --help-all, show-ref --help-all

  I do not know why an entry for this needs to be in the struct option []
  for the command.  It is not (and should not be) documented in the manual
  page of the individual commands.

* show-ref -h

  "-h" was meant to be a historical synonym for "--head" (i.e. tells the
  command include HEAD in the output not just under refs/ hierarchy), but
  it seems that we broke it somewhere between v1.6.5 and v1.7.0; it now
  shows the help text.

* write-tree --ignore-cache-tree

  A debugging aid; not documented.


It seems that our use of OPT_HIDDEN or if a hidden option is documented
are not entirely consistent. The "--with" under discussion is similar to
"clone --naked" and "fmt-merge-msg --summary".

I am Ok with a policy to document historical synonyms that are hidden, but
if we were to document them, I suspect that we would need to explicitly
state they are synonyms.  Otherwise, somebody who saw this...

>  --contains <commit>::
> +--with <commit>::
>  	Only list branches which contain the specified commit.

... for the first time is bound to ask what the differences are between
the two.

Re: Determining commit reachability

[Nguyen Thai Ngoc Duy]

On Tue, Sep 7, 2010 at 9:38 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Somehow people wanted to see an option with a longer name, but by that
> time my fingers were well trained, so I kept "--with" but didn't bother
> advertising duplicated options.

But do you object a document patch for that option? I ask because I
found another undocumented option, --clear-resolve-undo in
update-index and was wondering if it's worth a patch.
-- 
Duy

Re: Determining commit reachability

[Nguyen Thai Ngoc Duy]

On Tue, Sep 7, 2010 at 11:04 PM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
> On Tue, Sep 7, 2010 at 9:38 AM, Junio C Hamano <gitster@pobox.com> wrote:
>> Somehow people wanted to see an option with a longer name, but by that
>> time my fingers were well trained, so I kept "--with" but didn't bother
>> advertising duplicated options.
>
> But do you object a document patch for that option? I ask because I
> found another undocumented option, --clear-resolve-undo in
> update-index and was wondering if it's worth a patch.

Hmm.. just saw Jonathan's patch. I guess I just go ahead and make a patch then.
-- 
Duy