Re: Finding a branch point in git

From: Jeff King <peff@peff.net>
Date: May 28, 2012, 06:20 UTC
Message-ID: <20120528062026.GB11174@sigill.intra.peff.net>
In-Reply-To: <CAMP44s0f7AJPQSTDgvy0U7vx8nxzq2a3vMhSr2Tcc61fetFkJA@mail.gmail.com>

On Sun, May 27, 2012 at 02:37:32PM +0200, Felipe Contreras wrote:

Show 20 quoted lines

> When discussing git vs. mercurial, and what can mercurial do that git
> can't, I inevitably see somebody mention that mercurial branches can
> be used to find the branch point (the point at which a branch started;
> even if it's a long-lived one that has been merged to 'master'
> multiple times).
> 
> There have been a few solutions in stackoverflow[1], but none that
> work in all cases.
> 
> But I think I've found an ad-hoc one that uses the commit messages to
> find the first merge of a branch, and then the merge-base.
> 
> For reference, if somebody is interested:
> 
> ---
> [alias]
>     branch-point = !sh -c 'merge=$(git rev-list --min-parents=2
> --grep="Merge.*$1" --all | tail -1) && git merge-base $merge^1
> $merge^2'
> ---

I think this approach works for two-branch cases, but there is some subtlety with the regex. My initial thought was that you were looking for "Merge 'branch_A'" in the commit message (and that is what is implied by your stackoverflow response). If you always merge the topic into the main branch, then you will find the first merge. But imagine this history:

-- X -- A -- B -- C -- D --  E  (master)
         \         \        /
          \         \      /
           G -- H -- I -- J  (branch A)

where I is a merge from master to branch A (e.g., for testing), and then E is a merge from branch A to master (the actual integration).

Searching for "Merge 'branch_A'" will find E, and then you will take the merge base of J and D, which is C. But the answer you want is A. However, we also say "Merge master into 'branch_A'" when HEAD is not master. So your regex _would_ catch that, and would find I, for which the merge base is A.

What about a history with multiple branches?

--X--A--B--C--D----E  (master)
      \           /
       G--H--I---J   (branch X)
           \    /
            K--L    (branch Y)

where Y is merged to X (commit J), and then X is merged to master (commit E). Searching for the earliest merge mentioning X will find J, the merge between X and Y. But the merge base of its parents is H.

You can improve your regex by specifying a pair of branches and looking for "Merge X into master" and "Merge master into X" (IOW, make sure we don't see merges between X and other branches). Then you would find E, which yields the correct answer.

There are also even more complex cases. It doesn't make much sense to ask about where branch Y split from master, since it actually came from branch X in the above example. But let's say we branched straight from master, merged our result to X, which got merged to master, and then we built some more commits on Y and merged them to master. Like:

--X--A--B--C--D----E--F (master)
     |\           /  /
     | \         /  /
      \ G--H----I  /  (branch X)
       \       /  /
        K--L--M--O  (branch Y)

The only merge between master and X is F, but its merge base is M. We missed the earlier merge to master because it actually happened across two different commits.

-Peff