How does git follow branch history across a merge commit?

How does git follow branch history across a merge commit?

[Steven E. Harris]

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

Re: How does git follow branch history across a merge commit?

[Junio C Hamano]

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

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

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

Re: How does git follow branch history across a merge commit?

[Junio C Hamano]

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

> "Steven E. Harris" <seh@panix.com> writes:
>
>> Was it just luck that "HEAD^" referred to the predecessor that came from
>> branch "master" rather than branch "competition"?
>
> Yes, if you want the second parent you would say HEAD^2.

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.

Re: How does git follow branch history across a merge commit?

[Steven E. Harris]

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

> 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.

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

Re: How does git follow branch history across a merge commit?

[Junio C Hamano]

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

> Junio C Hamano <gitster@pobox.com> writes:
>
>> 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.
>
> 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/)".

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".

Re: How does git follow branch history across a merge commit?

[Steven E. Harris]

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

> *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".

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.

-- 
Steven E. Harris

Re: How does git follow branch history across a merge commit?

[Björn Steinbrink]

On 2009.08.28 19:50:44 -0400, Steven E. Harris wrote:
> 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?

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