How does git follow branch history across a merge commit?

This question concerns git's representation of merge commits.

I understand that branches in git are references to commit vertices in a graph, that each of these vertices have zero or more reference edges to a parent (predecessor) vertex, and that merges create vertices with at least two parents. Walking back in time from a branch head involves traversing parent edges.

But what happens when such traversal reaches a merge commit? If one asks git to move back, say, in time by a few days, or so many predecessors, how does it know (or choose) which way to go upon reaching a merge commit?

I set up an experiment with two competing branches that require merging back together:

,----
| mkdir gitexp && cd gitexp && git init
| $EDITOR file1.txt
| git add file1.txt
| git commit -m'Initial impound.'
| $EDITOR file1.txt
| git commit -a -m'Added a second line.'
| 
| git checkout -b competition
| $EDITOR file1.txt
| git commit -a -m'Extended second line.'
| 
| git checkout master
| $EDITOR file1.txt
| git commit -a -m'Added third line.'
| 
| git checkout competition
| $EDITOR file1.txt
| git commit -a -m'Edited second line.'
| $EDITOR file1.txt
| git commit -a -m'Added an alternate third line.'
| 
| git checkout master
| git merge competition
| # Edit to resolve conflict:
| $EDITOR file1.txt
| git commit -a
| 
| git checkout 'HEAD^'
| # At this point, git picked the predecessor along branch "master".
`----

Was it just luck that "HEAD^" referred to the predecessor that came from branch "master" rather than branch "competition"?

"Steven E. Harris" <seh@panix.com> writes:

Yes, if you want the second parent you would say HEAD^2.

Junio C Hamano <gitster@pobox.com> writes:

Ahh, I misread your question. No, it is not luck. If you merge competition into your master, the resulting commit will have your master as its first parent. If check out competition and merge master in your example, the resulting merge will have compatition as the first parent.

Junio C Hamano <gitster@pobox.com> writes:

I see, having run a few more experiments to confirm this.

I missed the point that merge commits are not "predecessor neutral"; they apparently have a bias indicating "/this branch/ received content from /that branch/ (or /those branches/)".

To try to recreate my confusing scenario, I tried this:

,----
| git checkout competition
| git merge master
| # This fast-forwarded "competition" be equivalent to "master".
| git checkout 'HEAD^'
| # This wound up again at "master"'s predecessor, not "competition"'s.
`----

It seems that since fast-forward merges don't produce a commit, the merge record remains in place recording that branch "competition" came into branch "master". Even though we're checked out to branch "competition" here, following its history back in time requires some manual intervention. Do you concur, or is my example perhaps flawed?

"Steven E. Harris" <seh@panix.com> writes:

We are in principle pretty much neutral, but in certain places you obviously cannot avoid tiebreaking. A commit object has to record parents in a bytestream in its representation, and inevitably one parent must come before another one.

You also must give your users some way to refer to each of its parents, so naturally we count from one, and call them $it^ (== $it^1), $it^2, etc. We do not have "$it^?" that lets you pick its parents at random, as we haven't found a good use case for such a feature.

One place we tiebreak favoring earlier parents over later ones, even though there is no logical reason to do so, is merge simplification [*1*]. When more than one parents have the same tree, with respect to pathspec given, while traversing the history, we pick the earliest one, because that is just as good as choosing one at random, and would give us a reproducible result. For a similar reason, when blame follows a merge from identical parents, it assigns blame to earlier parents.

And at the end-user workflow level, people tend to think "I merge others work into mine", so the log family of commands have --first-parent option to follow only that ancestry, but that logic kicks in only while browsing, not while building histories.

[Footnote]

*1* If you do not know what a merge simplification is, refer to e.g. http://gitster.livejournal.com/35628.html and notice there is a place where we follow "a parent that is the same as the merge result".

Junio C Hamano <gitster@pobox.com> writes:

I read this article today with great interest. Had I known of it beforehand, it would have changed some of my flawed assumptions evident in my post. Thanks for writing that. I'll be looking into the rest of the articles there to learn more.

On 2009.08.28 19:50:44 -0400, Steven E. Harris wrote:

As there is no merge commit, there's no "merge record" either. "competition" just got updated to reference the same commit as "master". Branch "competition" did not "come into" branch "master" either. "competition" and "master" are just the names of the branch heads. And those just reference commits, which actually form the history and have no record of belonging to any branch head on their own.

IOW: "master" and "competition" aren't branches as in "a series of
commits with a fixed relation to each other", but just branch heads,
referencing the tips where the branches grow.

Scenario A:

Given this history:

A---B---C (master)
 \
  D---E (competition)

If you now merge "master" to "competition" you get:

A---B---C (master)
 \       \
  D---E---M (competition)

Where M is a merge commit with two parents, E being the first one, C being the second one. And that's everything that git knows, that M is a merged of C and E. That E is the first parent is just a smart choice, nothing else.

Scenario B:

Given this history:

A (competition)
 \
  B---C (master)

If you ask git to merge "master" to "competition", it will see that there aren't any commits reachable through "competition" that aren't reachable through "master". So simply fast-forwarding "competition won't make you lose anything. Thus you get:

A---B---C (master) (competition)

There's no trace of any merge, because it wasn't required. You can't even tell that a fast-forward happened from that history. You could as well just have created "competition".

That said, if you want to force a merge commit (which can sometimes be useful), you can use the --no-ff flag:

git checkout competition git merge --no-ff master

And this leads to:

A------M (competition)
 \    /
  B---C (master)

With M's first parent being A, and the second parent being C.

(Assuming that "competition" is a topic branch, this would be a bit weird though, as you produce a totally pointless merge commit, before you even started working on your topic branch. OTOH doing this the other way around, i.e. forcing a merge commit when you merge a topic branch to "master" _can_ be useful. Don't over do it though).

HTH Björn