Revision 2 as of 2005-08-09 04:45:54

Clear message

At some level, all merge algorithms are making a guess about how a human would combine two sets of changes. There are usually some cases which cause a merge algorithm to become confused and produce a result which a human would reject upon inspection. This page has a few examples of ways to confuse a merge algorihtm.

Changing a Functions vs. Renaming a Function

([http://zooko.com/ zooko] came up with this excellent example.)

Suppose you have this initial version:

int square(int x) {
        int y = x;
        for (int i = 0; i < x; i++) y += x;
        return y;
}

One user decides to turn this into two different functions:

int fast_square(int x) {
        int y = x;
        return y * x;
}

int slow_square(int x) {
        int y = x;
        for (int i = 0; i < x; i++) y += x;
        return y;
}

Another user spots a bug in the function and fixes it:

int square(int x) {
        int y = 0;
        for (int i = 0; i < x; i++) y += x;
        return y;
}

When combining these two changes, some implementations of simple 3-way merge (and probably other algorithms as well) will produce a strange result:

int fast_square(int x) {
        int y = 0;
        return y * x;
}

int slow_square(int x) {
        int y = x;
        for (int i = 0; i < x; i++) y += x;
        return y;
}

This happens because merging requires matching portions of the different versions of the file against the others. Because the "int y = x;" line appears twice, it's not clear to the merge algortihm which one the user intended to change.

Or, to look at it another way, the merge algorithm has to compare each new version to the version it's based upon and convert the edit into some sequence of changes. In the case of the first change (adding fast_square and renaming square to slow_square), the edit can be viewed as:

  1. Changing the first line (i.e. renaming square to fast_square)

  2. Inserting several new lines (which happen to include a close brace and the beginning of the function slow_square)