git-merge-recursive: documentation and implementation notes

Hi,

This mail contains the promised documentation for the recursive merge strategy. I don't really know where or even if this belongs in the Git repository, so I am not posting it as a patch. If it is understandable it might be appropriate for Documentaion/technical.

This note is supposed to describe how the recursive merge strategy works. As I am not a native English speaker comments regarding spelling and grammar are more than welcome. Comments on the content is, of course, even more welcome :)

The fundamental merge problem that the recursive strategy tries to solve is when there are more than one common ancestor of the branches we want to merge. This happens, for example, in the "criss-cross" merge case:

A
|\
| \
|  \
|   \
|    \
|     \
|      \
B8      C3
|\     /|
| \   / |
|  \ /  |
|   X   |
|  / \  |
| /   \ |
|/     \|
D8      E3
 \      |
  \     |
   \    |
    \   |
     \  |
      \ |
       \|
        M

(This example and the ASCII graphic are from Bram Cohen's excellent description of the criss-cross case in http://marc.theaimsgroup.com/?l=git&m=111463358500362&w=2)

We have a common base A, at commit B and D line 8 was changed and at commit C and E line 3 was changed. There is only one file, so the same file is modified in B, C, D and E. The result of the merge is called M.

If we do a classical three-way merge of D and E with either A, B or C as the common ancestor we will get conflicts. Theoretically this shouldn't happen as both the D branch and the E branch knows about the changes made at both B and C, the theoretical clean merge should therefore contain line number 3 from E and line number 8 from D.

The recursive merge strategy solves this problem by recursively merging any common ancestors. Hence, in the criss-cross scenario above the code will detect that D and E has both B and C as their common ancestor. It will then recursively merge B with C. The common ancestor of B and C is A. When there is only one common ancestor an ordinary three-way merge is done (modulo renames, will talk about those below). So in this case we will merge B and C with A as the common ancestor to create a temporary tree. This new tree will then be used as the common ancestor for a merge of D and E.

In some cases there are more than two common ancestor, for example 44583d380d189095fa959ec8ba87f0cb6deb15f5 in Thomas Gleixner's historical Linux kernel repository has no less than six common ancestors.

The recursive strategy also has some support for renamed objects. Consider the following ancestry graph:

   O
  / \
 /   \
A     B

Let the file 'foo' be renamed to 'bar' in A. In the B branch 'foo' is modified. The result of a merge of A and B will contain a file 'bar' with whatever contents merge(1) produced given A/bar and B/foo as the files to be merged and O/foo as the ancestor. Renames are detected by executing 'git-diff-tree -M --diff-filter=R <branch> <ancestor>' for both branches. The rename processing may be seen as a pre-processing step to the three-way merge procedure in the sense that renames are processed first and then the ordinary file-level merging is done.

There are, essentially, only two merge scenarios which involves renames that are cleanly merged. The first one is the case described above when a file is renamed (and possibly modified) in one branch and modified in the other branch. The other scenario is when the same file is renamed to the same new name in both branches. However, there are several scenarios which causes conflicts, if for example we are going to merge the branches A and B then the following table contain a few of the conflict cases:

In A In B ------------------------------------- rename a -> b rename a -> c rename a -> b rename c -> b add a rename b -> a delete a rename a -> b

(Each line should be interpreted as an individual scenario, file names on different lines do not have anything in common.)

There is currently no support for directory renames. If a directory is renamed it will be processed as if every file in the directory was renamed. This will cause clean merges of certain cases which probably should be conflicts. (Such as: directory 'foo' is renamed to 'bar' in one branch, in the other branch a new file 'foo/baz' is added. With the current code we will end up with both a 'foo' directory, containing 'foo/baz', and a 'bar' directory containing whatever 'foo' contained in the common ancestor. A better outcome would probably be to flag this as a conflict.)

The code tries, as far as possible, to let the user know what happens in the conflict cases. The idea is that the user shouldn't have to guess what the algorithm has done when she stumbles upon some strange corner case. For example, if a file 'foo/bar' is added in the branch 'testing' and 'baz' is renamed to 'foo' in the branch 'release' then the user will be given the message:

    CONFLICT (rename/directory): Rename baz => foo in branch release directory foo added in testing
    Renaming baz to foo~release instead

(The file name 'foo~release' is carefully constructed to not overwrite any existing files.)

What follows is pseudo code which describes the algorithm from a high-level point of view. Text within [brackets] is either a name of a Python function where the real code can be found or a short description of where the code can be found. Currently, the code is contained in two files, git-merge-recursive.py and gitMergeCommon.py.

[merge]
merge(A, B)
{
    [getCommonAncestors]
    commonAncestors = getCommonAncestors(A, B)

    mergeCommonAncestor = commonAncestors[0]
    for(i = 1; i < length(commonAncestors); i++) {
        mergedCommonAncestor = merge(mergedCommonAncestor, commonAncestors[i])
    }

    [in mergeTrees]
    git-read-tree -m mergeCommonAncestor A B

    [loop in mergeTrees, git-diff-tree execution in getRenames]
    for each file in either
        'git-diff-tree -M --diff-filter=R -r mergeCommonAncestor A' or
        'git-diff-tree -M --diff-filter=R -r mergeCommonAncestor B':
        
	[processRenames]
        All rename processing is done here. This includes detection of
        various conflict cases and merge the 'rename in one branch and
        modified in the other'-case 
        
        [processRenames]
        For every file which is merged cleanly update the index

    [loop in mergeTrees]
    for each file which is still 'unmerged' in the index:

        [processEntry]
        Do a file-level merge. This is more or less the same thing as
        git-merge-one-file does, but it is implemented in Python.

    Return the new merged tree. 
}

Please note that the pseudo code above just is a sketch of the real code. One important difference is that in the real code a resulting tree is always returned from the 'merge'-function as soon as the 'merge'-function has been called recursively.

Lets assume there is a merge conflict when we merge B and C in the criss-cross case above. Then both D and E must resolve this conflict. If they have done it in the same way we wont get a merge conflict at M, if they have resolved it differently we will get a merge conflict. In the first case there is no merge conflict at M, in the second case the user has to pick which one of the two different resolutions she wants.

Note that the algorithm will happily write non-clean merge results to the object database during the "merge common ancestors" stage. Hence, when we are merging B and C "internally" we will _not_ ask the user to resolve any eventual merge conflicts.

The temporary trees and non-cleanly merged files which are written to the object database are not removed when the merge is finished. Hence, in some cases, there will be unreachable objects in the database after a merge.

- Fredrik

  Hi,

Dear diary, on Sat, Nov 12, 2005 at 09:34:57PM CET, I got a letter where Fredrik Kuivinen <freku045@student.liu.se> said that...

  I find this part somewhat unclear. So how does the user pick which of
the two different resolution she wants if we will not ask the user to
resolve any conflicts?

On Sat, Nov 12, 2005 at 10:03:06PM +0100, Petr Baudis wrote:

If we have a conflict when we merge B and C we will get a file with conflict markers from merge(1) in it, so it will look something like

    1
    2
    3
    <<<<<<
    4
    5
    ======
    6
    7
    >>>>>>
    8
    9

This file will be stored in the object database and the temporary tree which is created by the merge of B and C will refer to it.

The algorithm will then merge D and E and use the file above as the common ancestor. There are now two cases to consider, the first one is that both D and E resolve the conflict above in the same way (and possible make other changes which can be cleanly merged), we end up with something like

    1
    2
    3
    4
    5
    8
    9

in both D and E. This will be merged cleanly into M. The other case is that D and E either resolves the conflict differently or that they do other modifications which aren't possible to merge automatically. In this case we will let the user do the conflict resolution.

So, what I meant was that during the first merge, of B and C, the user do not have to do anything with any eventual conflicts. However, in the top-level merge, conflict resolution works in the same way as it does for the 'resolve' strategy, i.e., the output of merge(1) is stored in the working directory and the index is updated to make 'git diff' useful.

- Fredrik