2

Given a commit SHA, how would one find the oldest common ancestor of all parents using plumbing commands? Specifically - of each of the parent branches (one of which is master), select the oldest two (master and X), and then find the point at which they branched.

I've looked through several similar questions like Finding a branch point with Git?, but those didn't seem to deal with potentially having 3+ commits, or use rev-list --first-parent which I believe doesn't quite get me what I want.

The best I've come up with so far is git merge-base --octopus $(git cat-file -p $(git rev-parse HEAD) | grep parent | awk '{ printf "%s ",$2 }'), however that gets the 'best' ancestor, not the oldest...

Examples:

a) Given Z, who's parents are L, F, and J, how do I find X?

                    K ------- L -------              branch_1
                   /         /         \
                  /         /           \
HISTORY-- X -- A -- B -- C -- D -- F --- Z--->       master
             \     /   \     /          /
              \   /     \   /          /
                G -- H -- I -- J -----/              branch_2

b) Given D, who's parents are C, I, how do I find A?

             G --- H -- I           branch_1
            /     /      \
HISTORY--- A -- B -- C -- D ----    master
Asmodean
  • 339
  • 3
  • 13
  • I think I would need either more examples, or a more clear explanation of what you're trying to find. Generally speaking, if X is a common ancestor of a commit's parents, then X's parent is an older common ancestor of the commit's parents; so this would usually just be the root of the commit tree. But I don't think that's what you mean... – Mark Adelsberger Jul 25 '18 at 19:45
  • I updated the description a bit to hopefully be clearer, and added another example. Does that help? – Asmodean Jul 25 '18 at 20:06
  • you second tree does not fit to the first. Please clean up your "drawings". – Timothy Truckle Jul 25 '18 at 20:10

1 Answers1

3

At first I thought you meant octopus-merge-style merge base as well.

It's clear enough (I think!) what you do mean, but expressing it is a bit tricky. As Mark Adelsberger notes in a comment, the easy description results in regressing to a root commit (or declaring that there is no such ancestor).

What you want is, I think, the newest commit such that all paths backwards from a given commit reach that commit. Hence, given Z, X or any earlier commit suffices because X is an ancestor of every ancestor of Z that is a descendant of X. A does not qualify because, while A is an ancestor of the three ancestors of Z itself, it is not an ancestor of G, while G is an ancestor of Z.

The way to find X is to do a topologically sorted priority-queue walk of the commit graph, starting from all parents of Z in this case, just as git log or git rev-list would do given --topo-order Z^@. When the depth of the priority queue is 1, the commit at the head of the priority queue is the commit you are searching for.

There is no option to git rev-list to spit out just this commit hash. You will pretty much have to write your own code to find this, I think.

torek
  • 448,244
  • 59
  • 642
  • 775
  • Ya, definitely having trouble expressing it correctly, but I think you got it. I was wondering if I'd have to write something to walk the graph myself, but I was hoping not. Ah well. Thanks! – Asmodean Jul 25 '18 at 20:14
  • This is the *intuitive* definition I assumed was in question; but I wanted to press for a precise definition in the hope that it would illuminate a clearer solution. (It did not.) The only things I would add here, are (1) when you say "all paths backwards from a commit", that's still a little ambiguous (because more paths can branch out in the "HISTORY" part of the 2nd example). So I'd say it means, the first time (going backwards) that all paths (to that point) converge on a single commit (after which we stop looking for more paths). The 2nd thing: sometimes there's no solution. – Mark Adelsberger Jul 25 '18 at 20:41