Why merges fail and what can be done about it

If you enjoy this article, I’m working on a book explaining the internals of Git through implementation: Building Git.

In Merging with diff3 we saw how diff algorithms are used to compare versions of a file when performing a three-way merge, and in Myers diff in linear space we learned how different diff algorithms can produce wildly different results. Not only are these different results confusing to human readers, they also affect how well merging works. Before we discuss one final diff algorithm, I’d like to show some ways in which diff output can affect the success of a merge.

In the last article, we considered merging Alice and Bob’s modified versions of a shopping list:

         Alice               Original            Bob

      1. celery           1. celery           1. celery
      2. salmon           2. garlic           2. salmon
      3. tomatoes         3. onions           3. garlic
      4. garlic           4. salmon           4. onions
      5. onions           5. tomatoes         5. tomatoes
      6. wine             6. wine             6. wine

Using our linear-space Myers implementation to perform the diff, the diff3 algorithm produced this result with a single conflicted region:

      celery
      <<<<<<< alice.txt
      salmon
      =======
      salmon
      garlic
      onions
      >>>>>>> bob.txt
      tomatoes
      garlic
      onions
      wine

Now, this outcome was based on taking the following diff between the original version and Alice’s changed copy:

         Alice               Original

      1. celery           1. celery
-                         2. garlic                           
-                         3. onions                           
      2. salmon           4. salmon
      3. tomatoes         5. tomatoes
+     4. garlic                                               
+     5. onions                                               
      6. wine             6. wine

However, this is not the only minimal diff between these two versions. An equally valid diff, rather than moving garlic and onions, moves salmon and tomatoes:

         Alice               Original

      1. celery           1. celery
+     2. salmon                                               
+     3. tomatoes                                             
      4. garlic           2. garlic
      5. onions           3. onions
-                         4. salmon                           
-                         5. tomatoes                         
      6. wine             6. wine

If we take this diff, then matching the regions of the files up produces these groups:

         Alice               Original            Bob

      1. celery           1. celery           1. celery         A
      -----------------------------------------------------------
      2. salmon                               2. salmon         B
      3. tomatoes
      -----------------------------------------------------------
      4. garlic           2. garlic           3. garlic         C
      5. onions           3. onions           4. onions
      -----------------------------------------------------------
                          4. salmon           5. tomatoes       D
                          5. tomatoes
      -----------------------------------------------------------
      6. wine             6. wine             6. wine           E

Notice that this grouping includes two conflicted regions: in region B, both Alice and Bob insert new items at the same point in the original version. In region D, Alice removes salmon and tomatoes while Bob is missing only salmon. So the diff3 output based on this alternative diff for Alice will be:

      celery
      <<<<<<< alice.txt
      salmon
      tomatoes
      ======= 
      salmon
      >>>>>>> bob.txt
      garlic
      onions
      <<<<<<< alice.txt
      ======= 
      tomatoes
      >>>>>>> bob.txt
      wine

This is one small and contrived example of how a seemingly innocuous change in a diff can introduce new merge conflicts. In real-world situations, a bad diff can lead to really misleading conflicts that are hard to resolve correctly. In our discussion of linear-space Myers diff, we saw one particularly bad example of some C code that produced a confusing diff when two functions traded places in the source code. Here’s the original again:

// original.c

size_t Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
{
    if (!Chunk_bounds_check(src, src_start, n)) return 0;
    if (!Chunk_bounds_check(dst, dst_start, n)) return 0;

    memcpy(dst->data + dst_start, src->data + src_start, n);

    return n;
}

int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
{
    if (chunk == NULL) return 0;

    size_t length = chunk->length;

    return start <= length && n <= length - start;
}

And this time, let’s say Alice swaps the order of the functions, and makes no other changes, producing this version:

// alice.c

int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
{
    if (chunk == NULL) return 0;

    size_t length = chunk->length;

    return start <= length && n <= length - start;
}

size_t Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
{
    if (!Chunk_bounds_check(src, src_start, n)) return 0;
    if (!Chunk_bounds_check(dst, dst_start, n)) return 0;

    memcpy(dst->data + dst_start, src->data + src_start, n);

    return n;
}

Meanwhile, Bob takes the original version and makes one small change, adding a comment before the memcpy call in the Chunk_copy function.

// bob.c

size_t Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
{
    if (!Chunk_bounds_check(src, src_start, n)) return 0;
    if (!Chunk_bounds_check(dst, dst_start, n)) return 0;

    // copy the bytes
    memcpy(dst->data + dst_start, src->data + src_start, n);

    return n;
}

int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
{
    if (chunk == NULL) return 0;

    size_t length = chunk->length;

    return start <= length && n <= length - start;
}

Using the linear-space Myers algorithm, the diff between the original and Alice’s version, rather than clearly showing the functions trading places, is the following (this is the diff Git produces by default):

- size_t Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
+ int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
  {
-     if (!Chunk_bounds_check(src, src_start, n)) return 0;
-     if (!Chunk_bounds_check(dst, dst_start, n)) return 0;
+     if (chunk == NULL) return 0;

-     memcpy(dst->data + dst_start, src->data + src_start, n);
+     size_t length = chunk->length;

-     return n;
+     return start <= length && n <= length - start;
  }

- int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
+ size_t Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
  {
-     if (chunk == NULL) return 0;
+     if (!Chunk_bounds_check(src, src_start, n)) return 0;
+     if (!Chunk_bounds_check(dst, dst_start, n)) return 0;

-     size_t length = chunk->length;
+     memcpy(dst->data + dst_start, src->data + src_start, n);

-     return start <= length && n <= length - start;
+     return n;
  }

The important thing about this diff from the point of view of the diff3 merge algorithm is that it has a very fragmented view of which regions of the file remain unchanged. Rather than showing one function not changing while the other is deleted and inserted somewhere else, this diff shows many isolated lines matching up, and most of those matches are common boilerplate like blank lines and braces rather than meaningfully distinct pieces of code.

This means that diff3 will struggle to meaningfully match up content in Alice and Bob’s versions, so conflicts are much more likely, and Bob’s extra comment will be positioned relative to the matching blank lines and braces, rather than relative to distinct program statements.

Indeed, when we merge these two versions using linear-space Myers as the diff algorithm, this is the result:

int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
{
    if (chunk == NULL) return 0;

<<<<<<< alice.c
    size_t length = chunk->length;
======= 
    // copy the bytes
    memcpy(dst->data + dst_start, src->data + src_start, n);
>>>>>>> bob.c

    return start <= length && n <= length - start;
}

size_t Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
{
    if (!Chunk_bounds_check(src, src_start, n)) return 0;
    if (!Chunk_bounds_check(dst, dst_start, n)) return 0;

    memcpy(dst->data + dst_start, src->data + src_start, n);

    return n;
}

(Again, this is what Git will give you if you make it perform this merge without telling it to use an alternative diff algorithm.)

Although the conflict here is surprisingly small given the messy diff above, the conflict is incredibly misleading: it suggests that the memcpy call and the comment Bob added appear in the Chunk_bounds_check function, not the Chunk_copy function as is the case. If this merge is being resolved by somebody who is not familiar with this code, they could easily keep Bob’s addition in its suggested place, introducing a bug into the program.

This conflict happens because diff3 has matched up the blank lines and braces from Alice’s diff with the blank lines and braces in Bob’s copy. Bob’s added comment appears after one opening brace and one blank line in his version, while after one matching opening brace and one blank line in the diff, Alice has the change:

-     memcpy(dst->data + dst_start, src->data + src_start, n);
+     size_t length = chunk->length;

Therefore, Bob’s comment is considered to conflict with this change of Alice’s. A better outcome would be to just keep Alice’s version here – the size_t length = chunk->length line – and add Bob’s comment to Chunk_copy, with the functions having traded places:

int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
{
    if (chunk == NULL) return 0;

    size_t length = chunk->length;

    return start <= length && n <= length - start;
}

size_t Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
{
    if (!Chunk_bounds_check(src, src_start, n)) return 0;
    if (!Chunk_bounds_check(dst, dst_start, n)) return 0;

    // copy the bytes
    memcpy(dst->data + dst_start, src->data + src_start, n);

    return n;
}

This is perfectly possible if we obtain a diff for Alice that leaves more distinct lines of code unchanged, for example the diff given by our original Myers implementation that more clearly shows one function moving while the other does not change:

+ int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
+ {
+     if (chunk == NULL) return 0;
+
+     size_t length = chunk->length;
+
+     return start <= length && n <= length - start;
+ }
+
  size_t Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
  {
      if (!Chunk_bounds_check(src, src_start, n)) return 0;
      if (!Chunk_bounds_check(dst, dst_start, n)) return 0;

      memcpy(dst->data + dst_start, src->data + src_start, n);

      return n;
  }
-
- int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
- {
-     if (chunk == NULL) return 0;
-
-     size_t length = chunk->length;
-
-     return start <= length && n <= length - start;
- }

With this diff, much of the body of the Chunk_copy function will be matched up with the corresponding lines in Bob’s version, and Bob’s comment can easily be inserted at the correct place.

If you weren’t aware of how the merge process works, you might see the conflicted merge that places Bob’s comment inside the Chunk_bounds_check function and be tempted to ask why something so obviously wrong could happen. Hopefully the above makes it clear: diff and merge algorithms don’t have any understanding of C or of any other programming language or format, and so they don’t recognise Bob’s comment as being inside any particular function. They don’t even know what comments and functions are! All they are doing is matching up equal lines of text, and the lines that the diff denotes as equal determine the outcome.

But then you might ask: why organise things around lines? Why not some other unit like characters or words, or why not have tools that do understand programming languages and can perform diffs and merges on parse trees rather than flat text? Well, it all comes down to trade-offs. Let’s look at merging based on words first. We can take a sentence, and create two versions of it with more words added, and merge those versions just fine:

o = %w[the fox jumps over the dog]
a = %w[the quick brown fox jumps over the dog]
b = %w[the fox jumps over the lazy dog]

merged = Diff3.merge(o, a, b)

puts merged.chunks.flat_map(&:content).join(" ")
# => "the quick brown fox jumps over the lazy dog"

This works because the two inserted phrases are clearly separated by a list of words that haven’t changed, so they can be matched up between versions in such a way that the two new words can both be added at the right place. But, it makes a big assumption about what a word is. In some languages, edit-distance is a single variable name, while in others it is an expression meaning “edit minus distance”. The concept of word is too language-dependent for a general-purpose tool like Git to make a reasonable choice that will work for all users. Given this ambiguity, you could diff at the character level, but that’s more likely to result in unconflicted merges whose result is meaningless code.

Going in the opposite direction and diffing on parse trees rather than simple text units has a similar problem of generality: rather than one diff program that anyone can use, every language out there would need its own diff tools, and they would all need to interoperate since most non-trivial projects contain code in multiple languages. This would clearly be a lot more work than having a single version control system for everybody, and the added complexity may result in more bugs and confusion than it’s worth, especially when you consider that programming languages change over time and we’d need a way to tell which version we were parsing and a new parser for each version. It’s not impossible, but it would be more expensive to build and maintain than a general-purpose tool.

And so, while diffing based on lines is by no means perfect, especially when dealing with formatting changes like changing indentation, it’s good enough considering the cost of implementing anything significantly better. In most programming languages, a line of code is a reasonable unit to talk about adding or removing, and so diffing on lines will work reasonably well for most use cases. It works well enough while being simple to implement, making it a good trade-off for a general-purpose tool.

So, if we can’t change the basis unit of text that we calculate diffs on, what else can we do to make merges more likely to succeed? The answer is to use better diff algorithms. Let’s take a look at how you can do this in Git, using our C example from above. We’ll make a new directory, start a Git repository in it, and commit the file original.c from above:

$ mkdir src
$ cd src
$ git init
# put code in file.c
$ git add file.c
$ git commit -m "first commit"

Now, let’s start a new branch for Alice’s changes. Create this branch, edit file.c to change the order of the two functions, then commit:

$ git checkout --branch alice
# edit file.c
$ git commit -am "swap functions"

If you run git show at this point, you’ll see the messy diff that matches blank lines and braces, rather than the one that clearly shows one function moving. However, if you instead run this:

$ git show --diff-algorithm=patience

Then you’ll see a much better diff, where Chunk_bounds_check is clearly removed from after Chunk_copy and inserted before it.

Now, fork another branch off of master and add a comment before memcpy, just as Bob did:

$ git checkout master
$ git checkout --branch bob
# edit file.c
$ git commit -am "add comment"

Then switch back to the alice branch and try to merge:

$ git checkout alice
Switched to branch 'alice'

$ git merge bob
Auto-merging file.c
CONFLICT (content): Merge conflict in file.c
Automatic merge failed; fix conflicts and then commit the result.

Because Git’s default diff algorithm generates a messy diff for Alice’s changes, the merge conflicts just as we saw above. Looking at the file, we see the exact same merge conflict that we generated using our own implementations:

<<<<<<< HEAD
    size_t length = chunk->length;
=======
    // copy the bytes
    memcpy(dst->data + dst_start, src->data + src_start, n);
>>>>>>> bob

Finally, let’s throw this merge away and try again with a different algorithm:

$ git reset --hard
$ git merge -Xdiff-algorithm=patience bob
Auto-merging file.c
Merge made by the 'recursive' strategy.
 file.c | 1 +
 1 file changed, 1 insertion(+)

By changing the diff algorithm, we’ve made Git perform the merge without conflicts. That doesn’t necessarily mean the code will be correct – merges can be unconflicted but still result in broken code – but it’s certainly better than the misleading conflict we got from the messy diff.

In the next and final article in this series on Git diffs, we’ll take a look at the Patience algorithm and find out why it produces better diff and merge results.

If you’ve enjoyed this article, you might enjoy my recently published book JavaScript Testing Recipes. It’s full of simple techniques for writing modular, maintainable JavaScript apps in the browser and on the server.