threads / discuss / 29408

[Q] Determing if a commit is reachable from the HEAD ?

Subject: [Q] Determing if a commit is reachable from the HEAD ?

## tl;dr

12 messages between Jan 20, 2012 and Jan 24, 2012.

replies: 11people: 5as markdown or json

Brian Foster· Jan 20, 2012, 13:33 UTC · lore
Hello,
 Whilst I have found answers to my question on the Web,
 only one seems to do exactly what I want ....
                         x---Y---y---y---y  HEAD
                        /
  ...--o---o---C---o---S
                        \
                         n---n---N---*---*  other
 In a script, how can I determine commit Y is reachable
 from the current HEAD ?   And, much more importantly
 for my purposes, that commit N is _not_-reachable from
 the current HEAD ?  "A is reachable from B" meaning B
 is an ancestor of A (B could possibly part of a merge
 (not shown in the above diagram)):
  ✓ Commits o(all), C, S, x, y(all), and Y: YES  (reachable).
  ✗ Commits n(all), N, and *(all): NO  (not-reachable).
 The only readily script-able answer I've found is to use
 `git branch --contains=Y' and check to see if the current
 branch (conveniently marked `*') is/isn't included in the
 output.  That is probably Ok, but I'm wondering if there
 is some "better" method (with the IMPORTANT caveat it must
 work with GIT 1.5.x or later  ;-\ ).
 git-rev-list(1) may be a answer (see script below), but ....
 `git rev-list ^Y HEAD' lists all the y commits, which is Ok
 (correct for my purposes).  However, `git rev-list ^N HEAD'
 lists commits x, Y, and y(all) on branch "other", which is
 not-Ok:  As per above, the answer I want is "NO".
 Apologies if I've overlooked something totally obvious !
cheers,
	-blf-

=====(cut here and below)=====reach02.sh===== #!/bin/bash # # x---Y---y---y---y HEAD # / # ...--o---o---C---o---S # \ # n---n---N---*---* other #

: ${GIT:=git}	# Allow use of different installed GIT versions.
update_file() {
	date +"%c: $*" >>file
	$GIT add file  &&  $GIT commit -m "$*" file
}
set -e		# Terminate if problem creating diagrammed situation.

rm -rf -- reachable mkdir -- reachable cd reachable

$GIT version $GIT init

update_file o1 update_file o2 update_file "C (o3)"; $GIT tag C update_file o4 update_file "S (o5)"; $GIT tag S

$GIT checkout -b other update_file n1 update_file n2 update_file "N (n3)"; $GIT tag N update_file "*1" update_file "*2"

$GIT checkout master update_file x update_file "Y (y1)"; $GIT tag Y update_file y2 update_file y3 update_file y4

declare -i wrong=0
echo "Is Y reachable from HEAD?  Wanted answer: Yes."
$GIT log --oneline ^Y HEAD
if $GIT rev-list --quiet ^Y HEAD; then
	echo "rev-list: YES (wanted answer)!"
else
	echo "rev-list: No! *** not-wanted, oops... ***"
	wrong=$(( wrong + 1 ))
fi
if $GIT branch --contains=Y | grep -q -e '^\*'; then
	echo "contains: YES (wanted answer)!"
else
	echo "contains: No! *** not-wanted, oops... ***"
	wrong=$(( wrong + 1 ))
fi
echo "Is N reachable from HEAD?  Wanted answer: No."
$GIT log --oneline ^N HEAD
if $GIT rev-list --quiet ^N HEAD; then
	echo "rev-list: YES? *** not-wanted, oops... ***"
	wrong=$(( wrong + 1 ))
else
	echo "rev-list: No (wanted answer)!"
fi
if $GIT branch --contains=N | grep -q -e '^\*'; then
	echo "contains: YES? *** not-wanted, oops... ***"
	wrong=$(( wrong + 1 ))
else
	echo "contains: No (wanted answer)!"
fi

exit $wrong =====(cut here and above)=====reach02.sh=====

-- 
Brian Foster
Principal MTS, Software        |  La Ciotat, France
Maxim Integrated Products      |  Web:  http://www.maxim-ic.com/
Andreas Schwab· Jan 20, 2012, 14:13 UTC · re: Brian Foster · lore

Re: [Q] Determing if a commit is reachable from the HEAD ?

Brian Foster <brian.foster@maxim-ic.com> writes:
>  In a script, how can I determine commit Y is reachable
>  from the current HEAD ?
test $(git merge-base HEAD Y) = $(git rev-parse Y)
>  And, much more importantly
>  for my purposes, that commit N is _not_-reachable from
>  the current HEAD ?
test $(git merge-base HEAD N) != $(git rev-parse N)
Andreas.
-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."
David Brown· Jan 20, 2012, 18:06 UTC · re: Andreas Schwab · lore

Re: [Q] Determing if a commit is reachable from the HEAD ?

On Fri, Jan 20, 2012 at 03:13:58PM +0100, Andreas Schwab wrote:
Show 6 quoted lines
> Brian Foster <brian.foster@maxim-ic.com> writes:
> 
> >  In a script, how can I determine commit Y is reachable
> >  from the current HEAD ?
> 
> test $(git merge-base HEAD Y) = $(git rev-parse Y)

Almost. It works as long as there is only one merge base. You really need to check if $(git rev-parse Y) is one of $(git merge-base --all HEAD Y)

if HEAD is a named branch, you can do
  git name-rev --refs=refs/heads/branchname Y

which will give you Y relative to branchname if it is contained within it.

David
-- 
Sent by an employee of the Qualcomm Innovation Center, Inc.
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.
Junio C Hamano· Jan 20, 2012, 19:18 UTC · re: David Brown · lore

Re: [Q] Determing if a commit is reachable from the HEAD ?

David Brown <davidb@codeaurora.org> writes:
Show 11 quoted lines
> On Fri, Jan 20, 2012 at 03:13:58PM +0100, Andreas Schwab wrote:
>> Brian Foster <brian.foster@maxim-ic.com> writes:
>> 
>> >  In a script, how can I determine commit Y is reachable
>> >  from the current HEAD ?
>> 
>> test $(git merge-base HEAD Y) = $(git rev-parse Y)
>
> Almost.  It works as long as there is only one merge base.  You really
> need to check if $(git rev-parse Y) is one of $(git merge-base --all
> HEAD Y)

Can you give us an example of a topology to which "merge-base --all HEAD Y" gives more than one output and Y is still reachable from HEAD?

It is my understanding that merge-base computation will give only Y and nothing else when Y is reachable from HEAD. I also think this assumption is used by some of the internal code in Git, and that is why I care.

David Brown· Jan 20, 2012, 23:33 UTC · re: Junio C Hamano · lore

Re: [Q] Determing if a commit is reachable from the HEAD ?

On Fri, Jan 20, 2012 at 11:18:50AM -0800, Junio C Hamano wrote:
Show 20 quoted lines
> David Brown <davidb@codeaurora.org> writes:
> 
> > On Fri, Jan 20, 2012 at 03:13:58PM +0100, Andreas Schwab wrote:
> >> Brian Foster <brian.foster@maxim-ic.com> writes:
> >> 
> >> >  In a script, how can I determine commit Y is reachable
> >> >  from the current HEAD ?
> >> 
> >> test $(git merge-base HEAD Y) = $(git rev-parse Y)
> >
> > Almost.  It works as long as there is only one merge base.  You really
> > need to check if $(git rev-parse Y) is one of $(git merge-base --all
> > HEAD Y)
> 
> Can you give us an example of a topology to which "merge-base --all HEAD Y"
> gives more than one output and Y is still reachable from HEAD?
> 
> It is my understanding that merge-base computation will give only Y and
> nothing else when Y is reachable from HEAD. I also think this assumption
> is used by some of the internal code in Git, and that is why I care.

Hmm, I thought I'd convinced myself that this was possible. Now, I can't come up with a way of doing it that doesn't involve improper commits with earlier timestamps than their parents.

Sorry about that, David

-- 
Sent by an employee of the Qualcomm Innovation Center, Inc.
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.
Junio C Hamano· Jan 21, 2012, 00:04 UTC · re: David Brown · lore

Re: [Q] Determing if a commit is reachable from the HEAD ?

David Brown <davidb@codeaurora.org> writes:
> Hmm, I thought I'd convinced myself that this was possible.  Now, I
> can't come up with a way of doing it that doesn't involve improper
> commits with earlier timestamps than their parents.

I'd actually want to see a way to do so that *does* involve timestamp skew.

David Brown· Jan 21, 2012, 04:58 UTC · re: Junio C Hamano · lore

Re: [Q] Determing if a commit is reachable from the HEAD ?

On Fri, Jan 20, 2012 at 04:04:50PM -0800, Junio C Hamano wrote:
Show 8 quoted lines
> David Brown <davidb@codeaurora.org> writes:
> 
> > Hmm, I thought I'd convinced myself that this was possible.  Now, I
> > can't come up with a way of doing it that doesn't involve improper
> > commits with earlier timestamps than their parents.
> 
> I'd actually want to see a way to do so that *does* involve timestamp
> skew.

Sorry, I guess I shouldn't tried this with a recent version of git. I can't cause this, and it looks like there's some pretty sophisticated stuff in there to deal with this.

David
-- 
Sent by an employee of the Qualcomm Innovation Center, Inc.
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.
Sitaram Chamarty· Jan 20, 2012, 22:50 UTC · re: Brian Foster · lore

Re: [Q] Determing if a commit is reachable from the HEAD ?

On Fri, Jan 20, 2012 at 7:03 PM, Brian Foster <brian.foster@maxim-ic.com> wrote:
Show 14 quoted lines
>
> Hello,
>
>  Whilst I have found answers to my question on the Web,
>  only one seems to do exactly what I want ....
>
>                         x---Y---y---y---y  HEAD
>                        /
>  ...--o---o---C---o---S
>                        \
>                         n---n---N---*---*  other
>
>  In a script, how can I determine commit Y is reachable
>  from the current HEAD ?   And, much more importantly

I've been using 'git rev-list HEAD..Y'. If it produces any output, Y is not reachable from HEAD (there is something in Y that is not in HEAD).

Brian Foster· Jan 23, 2012, 09:20 UTC · re: Sitaram Chamarty · lore

Re: [Q] Determing if a commit is reachable from the HEAD ?

On Friday 20 January 2012 23:50:23 Sitaram Chamarty wrote:
Show 14 quoted lines
> On Fri, Jan 20, 2012 at 7:03 PM, Brian Foster <brian.foster@maxim-ic.com> wrote:
>[ ... ]
> >                         x---Y---y---y---y  HEAD
> >                        /
> >  ...--o---o---C---o---S
> >                        \
> >                         n---n---N---*---*  other
> >
> >  In a script, how can I determine commit Y is reachable
> >  from the current HEAD ?   [ ... ]
> 
> I've been using 'git rev-list HEAD..Y'.  If it produces any output,
> Y is not reachable from HEAD (there is something in Y that is not
> in HEAD).
 What's interesting about this solution, at least
 with GIT v1.7.6.1 (I haven't tried other versions),
 is ‘git rev-list HEAD..Y’ does seem to work (if
 there is any output, then Y is not reachable from
 HEAD), but ‘git rev-list --quiet HEAD..Y’ does _not_
 work (it seems to always(?) exit status 0).
 I am probably misunderstanding ‘--quiet’, which the
 man page cryptically describes as “... allow the
 caller to test the exit status to see if a range
 of objects is fully connected (or not).”  What is
 meant here by “fully connected” ?
cheers!
	-blf-
-- 
Brian Foster
Principal MTS, Software        |  La Ciotat, France
Maxim Integrated Products      |  Web:  http://www.maxim-ic.com/
Junio C Hamano· Jan 23, 2012, 16:09 UTC · re: Brian Foster · lore

Re: [Q] Determing if a commit is reachable from the HEAD ?

Brian Foster <brian.foster@maxim-ic.com> writes:
Show 5 quoted lines
>  I am probably misunderstanding ‘--quiet’, which the
>  man page cryptically describes as “... allow the
>  caller to test the exit status to see if a range
>  of objects is fully connected (or not).”  What is
>  meant here by “fully connected” ?
If the real history looks like this:
 ---Y---x---HEAD

i.e. the commit at HEAD says "parent x" in it, and your lacks "x" for whatever reason, Y..HEAD is not fully connected.

Brian Foster· Jan 24, 2012, 08:16 UTC · re: Junio C Hamano · lore

Re: [Q] Determing if a commit is reachable from the HEAD ?

On Monday 23 January 2012 17:09:38 Junio C Hamano wrote:
Show 13 quoted lines
> Brian Foster <brian.foster@maxim-ic.com> writes:
> >  I am probably misunderstanding ‘--quiet’, which the
> >  man page cryptically describes as “... allow the
> >  caller to test the exit status to see if a range
> >  of objects is fully connected (or not).”  What is
> >  meant here by “fully connected” ?
> 
> If the real history looks like this:
> 
>  ---Y---x---HEAD
> 
> i.e. the commit at HEAD says "parent x" in it, and your lacks "x"
> for whatever reason, Y..HEAD is not fully connected.
Junio, and my _what_ lacks "x"?  Sorry, it looks like
 you typo'ed, but I cannot decipher what you meant.
cheers!
	-blf-
-- 
Brian Foster
Principal MTS, Software        |  La Ciotat, France
Maxim Integrated Products      |  Web:  http://www.maxim-ic.com/
Brian Foster· Jan 24, 2012, 08:56 UTC · re: Junio C Hamano · lore

Re: [Q] Determing if a commit is reachable from the HEAD ?

On Monday 23 January 2012 17:09:38 Junio C Hamano wrote:
Show 13 quoted lines
> Brian Foster <brian.foster@maxim-ic.com> writes:
> >  I am probably misunderstanding ‘--quiet’, which the
> >  man page cryptically describes as “... allow the
> >  caller to test the exit status to see if a range
> >  of objects is fully connected (or not).”  What is
> >  meant here by “fully connected” ?
> 
> If the real history looks like this:
> 
>  ---Y---x---HEAD
> 
> i.e. the commit at HEAD says "parent x" in it, and your [repository]
> lacks "x" for whatever reason, Y..HEAD is not fully connected.
 Ah, Ok.  Thanks!  Then YES, I misunderstood ‘--quiet’.
 The man page caused me to think it was functionally
 equivalent to ‘git rev-list STUFF >/dev/null’.
cheers!
	-blf-
-- 
Brian Foster
Principal MTS, Software        |  La Ciotat, France
Maxim Integrated Products      |  Web:  http://www.maxim-ic.com/

← back to recent threads