How does 'git merge' work in details?

Solution 1:

You might be best off looking for a description of a 3-way merge algorithm. A high-level description would go something like this:

1. Find a suitable merge base B - a version of the file that is an ancestor of both of the new versions (X and Y), and usually the most recent such base (although there are cases where it will have to go back further, which is one of the features of gits default recursive merge)
2. Perform diffs of X with B and Y with B.
3. Walk through the change blocks identified in the two diffs. If both sides introduce the same change in the same spot, accept either one; if one introduces a change and the other leaves that region alone, introduce the change in the final; if both introduce changes in a spot, but they don't match, mark a conflict to be resolved manually.

The full algorithm deals with this in a lot more detail, and even has some documentation (https://github.com/git/git/blob/master/Documentation/technical/trivial-merge.txt for one, along with the git help XXX pages, where XXX is one of merge-base, merge-file, merge, merge-one-file and possibly a few others). If that's not deep enough, there's always source code...

Solution 2:

How does git perform when there are multiple common bases for merging branches?

This article was very helpful: http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html (here is part 2).

Recursive uses diff3 recursively to generate a virtual branch which will be used as the ancestor.

E.g.:

(A)----(B)----(C)-----(F)
        |      |       |
        |      |   +---+
        |      |   |
        |      +-------+
        |          |   |
        |      +---+   |
        |      |       |
        +-----(D)-----(E)

Then:

git checkout E
git merge F

There are 2 best common ancestors (common ancestors that are not ancestors of any other), C and D. Git merges them into a new virtual branch V, and then uses V as the base.

(A)----(B)----(C)--------(F)
        |      |          |
        |      |      +---+
        |      |      |
        |      +----------+
        |      |      |   |
        |      +--(V) |   |
        |          |  |   |
        |      +---+  |   |
        |      |      |   |
        |      +------+   |
        |      |          |
        +-----(D)--------(E)

I suppose Git would just continue with the if there were more best common ancestors, merging V with the next one.

The article says that if there is a merge conflict while generating the virtual branch Git just leaves the conflict markers where they are and continues.

What happens when I merge multiple branches at once?

As @Nevik Rehnel explained, it depends on the strategy, it is well explained on man git-merge MERGE STRATEGIES section.

Only octopus and ours / theirs support merging multiple branches at once, recursive for example does not.

octopus refuses to merge if there would be conflicts, and ours is a trivial merge so there can be no conflicts.

Those commands generate a new commit will have more than 2 parents.

I did one merge -X octopus on Git 1.8.5 without conflicts to see how it goes.

Initial state:

   +--B
   |
A--+--C
   |
   +--D

Action:

git checkout B
git merge -Xoctopus C D

New state:

   +--B--+
   |     |
A--+--C--+--E
   |     |
   +--D--+

As expected, E has 3 parents.

TODO: how exactly octopus operates on a single file modifications. Recursive two-by-two 3-way merges?

How does git perform when there is no common base for merging branches?

@Torek mentions that since 2.9, merge fails without --allow-unrelated-histories.

I tried it out empirically on on Git 1.8.5:

git init
printf 'a\nc\n' > a
git add .
git commit -m a

git checkout --orphan b
printf 'a\nb\nc\n' > a
git add .
git commit -m b
git merge master

a contains:

a
<<<<<<< ours
b
=======
>>>>>>> theirs
c

Then:

git checkout --conflict=diff3 -- .

a contains:

<<<<<<< ours
a
b
c
||||||| base
=======
a
c
>>>>>>> theirs

Interpretation:

• the base is empty
• when the base is empty, it is not possible to resolve any modification on a single file; only things like new file addition can be resolved. The above conflict would be solved on a 3-way merge with base a\nc\n as a single line addition
• I think that a 3-way merge without a base file is called a 2-way merge, which is just a diff