How to find whether a given commit is on the first-parent chain of a branch

Question

I'm trying to script a way to tell if a given commit is on the first-parent chain of a given branch. So, for example, merge-base won't fly, as the commit might have been merged in. I want to know whether the exact commit was ever the tip of the branch.

Note: The branch in question is subject to a no-fast-forward merge strategy.

Answer 1

This is a performance friendly one-liner:

git rev-parse HEAD~"$( git rev-list --count --first-parent --ancestry-path <commit>..HEAD )"

If the output is your <commit>, then it's a first-parent ancestor.

The idea is that we measure the shortest path between the two commits with rev-list --count --ancestry-path, then get the commit at this position in the first-parent chain. Obviously, these must be the same if the inspected commit was a first-parent ancestor. Suppressed errors (e. g. first-parent chain is too short) are irrelevant.

To make it more sophisticated, you could rather create a git alias backed by a pretty readable shell script.

First write the script file:

#!/bin/sh

ref="$1"
head="$2"
if [ -z "$head" ]; then
    head="HEAD"
fi

commit=$( git rev-parse "$ref"^{commit} )
distance="$( git rev-list --count --ancestry-path --first-parent "$commit".."$head" )"
found="$( git rev-parse HEAD~"$distance" )"

if [ "$commit" != "$found" ]; then
    echo "${ref} is not a first-parent ancestor of ${head}"
    exit 1
fi

echo "${ref} is a first-parent ancestor of ${head} at a distance of ${distance}"
exit 0

Save it to an appropriate location on your system, make it executable, then set it as a git alias:

git config --global alias.fp '!<script-path>'

Replace fp with anything what's more comfortable for you. Substitute <script-path> with your script file's location, but keep the ! character, it's necessary to use external files.

After this, you can use the new alias like a normal git command:

$ git fp 66e339c
66e339c is a first-parent ancestor of HEAD at a distance of 45

Answer 2

The fancy way

A simple "is ancestor" test obviously won't do, as commits down 2nd-or-later parent chains are also ancestors:

...o--o--A--o--o--o--T
    \            /
 ...-o--*--B----o
         \
          C

Both A and B are ancestors of T, but you want to accept A while rejecting B and C. (Assume --first-parent is the top line here.)

Using git merge-base, however, will actually do part of the job. You don't need the --is-ancestor mode of git merge-base, though, and do need some additional processing.

Note that, regardless of the path between T and some ancestor, the merge base of T and that ancestor (such as A or B) is either the ancestor itself (A or B respectively here), or some ancestor of the ancestor, such as commit * if we look at T and C as a pair. (This holds even in the case of multiple merge bases, although I leave constructing a proof of that to you.)

If the, or any arbitrarily chosen one of the set of all, merge base(s) of the test commit and the branch-tip is not already the test-commit, we have a case like C and can reject it out of hand. (Or, we can use --is-ancestor to reject it, or ... well, see below.) If not, we must enumerate the commits in the ancestry path between the commit in question and the branch tip. For A this is:

         o--o--*--T

and for B this is:

               *--T
              /
             o

If any such commit is a merge commit, as is the one marked *, we need to make sure that the first parent includes one of the commit(s) listed along this path. The toughest cases are those topologically similar to:

       o--o
      /    \
...--A      o--T
      \    /
       o--o

since the --ancestry-path between these includes a merge and two ways to reach A, one of which is a first-parent path and one of which is not. (This is true if T itself is a merge as well.)

We don't actually need to find the merge base in the first place, though. We're only using the merge base in order to examine the ancestry path. If the merge base is not the test commit itself, then the test commit is not an ancestor of the tip commit, and testcommit..tipcommit will not include testcommit itself. Moreover, adding --ancestry-path—which discards all commits that are not themselves children of the left hand side here—will then discard all commits in the git rev-list output: a case like C has no descendants that are ancestors of T (if it did, C would be a merge base).

Hence, what we want is to examine the commits in git rev-list --ancestry-path testcommit..branchtip. If this list is empty, the test commit is not an ancestor of the branch tip in the first place. We have a case like commit C; so we have our answer. If the list is non-empty, reduce it to its merge components (run again with --merges, or feed the list to git rev-list --stdin --merges, to produce the shrunken list). If this list is non-empty, check each merge by finding its --first-parent ID and making sure the result is in the first list.

In actual (albeit untested) shell-script code:

TF=$(mktemp) || exit 1
trap "rm -f $TF" 0 1 2 3 15
git rev-list --ancestry-path $testcommit..$branch > $TF
test -s $TF || exit 1  # not ancestor
git rev-list --stdin --merges < $TF | while read hash; do
    parent1=$(git rev-parse ${hash}^1)
    grep "$parent1" $TF >/dev/null || exit 1 # on wrong path
done
exit 0 # on correct path

The brute-force way

The above tests as few commits as possible, but it would be a lot more practical, in a sense, to just run:

git rev-list --first-parent ${testcommit}^@..$branch

If the output includes $testcommit itself, then $testcommit is reachable, by first-parent only, from branch. (We use ^@ to exclude all parents of $testcommit so that this works even for the root commit; for other commits, ${testcommit}^ suffices since we're using --first-parent.) Moreover, if we make sure this is done in topological order, the last commit ID emitted from the git rev-list command will be $testcommit itself if and only if $testcommit is reachable from $branch. Hence:

hash=$(git rev-parse "$testcommit") || exit 1
t=$(git rev-list --first-parent --topo-order $branch --not ${hash}^@ | tail -1)
test $hash = "$t"

should do the trick. The quotes around $t are in case it expands to the empty string.

Answer 3

The no-fast-forward strategy means you can probably grep in git log --first-parent. You probably want only the hashes, so you can use git rev-list instead

git rev-list --first-parent | grep <commit hash>

Otherwise use --format with git log to display the data you want.

Edit: This post could give you some ideas

How can I tell if one commit is an ancestor of another commit (or vice-versa)?