Git merge alogithm

Question

When I merge two branches, (as per my knowledge) one of following things would happen:

1. Fast-farward
2. Conflicts
3. Auto-merge

Also, how git decides if it needs to fast-farward or auto-merge or a manual conflict resolution is required ?

Answer 1

fast-forward

While fast-forward is one of the things the merge command can do, I generally think of the operation of "fast-forward" as an alternative to the operation of performing a merge - a shortcut.

git will perform a fast-forward when two things are true:

1) You haven't told it not to by giving the --no-ff option

2) The checked-out branch is "reachable" (by parent pointers) from the commit being merged in. That is, if git knows due to the commit graph that every change in the current branch is also in the target branch, then a fast-forward would produce the right result so will be done if allowed.

For example, if I have

x -- x - O <--(master)
          \
           A -- B -- C <--(feature)

master (at O) is reachable from feature (at C), meaning that every change that was ever made to master is already "accounted for" in C. The result of a merge would have the same content as C, so "fast forward" is a valid solution. But if additional changes had been made to master after O, as in

x -- x - O -- D <--(master)
          \
           A -- B -- C <--(feature)

now there are two lines of mutually exclusive changes, so a true merge is required.

merges and conflicts

If fast-forward is not an option (because the user said --no-ff, or because the branches have diverged as noted in the second example above), then git attempts an auto-merge.

At this point it doesn't "decide" whether conflict resolution is needed; either it encounters a conflict, or it doesn't. If it does, it tells the user to resolve it; if not, it completes the merge automatically.

So what is a conflict?

A merge is an attempt to combine two (or more, but lets leave octopus merges out of this for now since conflict resolution isn't attempted for them) patches:

A) The patch from the merge base to what's currently checked out (ours)

B) The patch from the merge base to what's being merged in (theirs)

If both of these patches would change the same hunk of code, there is a conflict over that hunk.

Generally that means both patches try to add, delete, or modify the same line. (It can also mean adjacent lines.)

Answer 2

• Fast-forward

You are merging with a branch where you only have commits ahead and no commit behind.

• Auto-merge

Git successfully applied (with the patches constituting the changes introduced by the commits) all the changes for each commits merged.

That means that the changes in the 2 branches has not been made at the same places in the same files.

• Conflicts

Git tried but didn't successfully applied all the changes for each commits merged.

That means that the changes in the 2 branches has been made at the same places in the same files and git is asking you what is the good way to merge the 2 changes made on the same lines of the same file.