Sunday, May 5, 2013

Git incremental merge

In earlier articles, I explained how to break up a difficult merge into simple pairwise merges, how to efficiently locate the pairwise merges that block the full merge, and how to make pictures of the merge conflict frontier. How can these insights be used to actually resolve a full, nightmare merge?

This article will describe how to incrementally resolve the conflicts in a merge diagram, one pairwise conflict at a time. Each time a conflict is manually resolved, the conflict frontier is pushed back and more of the merge diagram becomes green. When the whole conflict diagram is green, the full incremental merge is done.

The amazing thing is that an incremental merge, once completed, contains all of the information you could possibly want about combining two branches. In my next article I will show, given a full incremental merge, how to derive a simple merge, a rebase (in either direction), or a rebase-with-history.

In future articles I will summarize the differences between incremental merge, git merge, and git rebase, discuss how to reduce the amount of work needed to resolve a merge conflict, and explain git-imerge, a tool that automates the process of incremental merging.

Pushing back the conflict frontier

In an earlier article, I showed how to create a diagram of a merge that was partly blocked by conflicting pairwise merges:

o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11    ← master
    |   |    |    |    |    |    |    |    |    |     |     |
    A - A1 - A2 - A3 - A4 - A5 - A6 - A7 - A8 - A9 - A10 - A11
    |   |    |    |    |    |    |    |    |
    B - B1 - B2 - B3 - B4 - B5 - B6 - B7 - B8   x     x     x
    |   |    |    |    |    |    |
    C - C1 - C2 - C3 - C4 - C5 - C6   x    x    x     x     x
    |   |    |    |    |    |    |
    D - D1 - D2 - D4 - D4 - D5 - D6   x    x    x     x     x
    |   |    |    |    |    |    |
    E - E1 - E2 - E3 - E4 - E5 - E6   x    x    x     x     x
    |   |
    F - F1   x    x    x    x    x    x    x    x     x     x
    |   |
    G - G1   x    x    x    x    x    x    x    x     x     x
    |   |
    H - H1   x    x    x    x    x    x    x    x     x     x
    |   |
    I - I1   x    x    x    x    x    x    x    x     x     x

    ↑
  branch

Remember: in this diagram, commits "0"-"11" are on master and commits "A"-"I" are on the branch. The rest of the diagram shows incremental merges when they are possible; e.g., commit "C3" is a successful merge between commit "C2" and commit "B3". When a pairwise merge fails, the diagram shows an "x"; for example Git was unable to merge "E2" and "F1", which implies that there was some conflict between the changes introduced in master commit "2" and those introduced in branch commit "F".

But you are smarter than Git, so (hopefully) you can merge "E2" and "F1" manually. Among your advantages over Git is that you can understand the commit messages for commits "2" and "F", so you know what those two commits were trying to achieve. Your task is to create a commit "F2" that contains the changes made in both "2" and "F" [1]. Once you resolve those two changes and commit the results as "F2", the diagram is transformed to:

o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11    ← master
    |   |    |    |    |    |    |    |    |    |     |     |
    A - A1 - A2 - A3 - A4 - A5 - A6 - A7 - A8 - A9 - A10 - A11
    |   |    |    |    |    |    |    |    |
    B - B1 - B2 - B3 - B4 - B5 - B6 - B7 - B8   x     x     x
    |   |    |    |    |    |    |
    C - C1 - C2 - C3 - C4 - C5 - C6   x    x    x     x     x
    |   |    |    |    |    |    |
    D - D1 - D2 - D4 - D4 - D5 - D6   x    x    x     x     x
    |   |    |    |    |    |    |
    E - E1 - E2 - E3 - E4 - E5 - E6   x    x    x     x     x
    |   |    |
    F - F1 - F2                       x    x    x     x     x
    |   |
    G - G1                            x    x    x     x     x
    |   |
    H - H1                            x    x    x     x     x
    |   |
    I - I1                            x    x    x     x     x

    ↑
  branch

Not only has "F2" been added to the diagram, but also a white area has opened up below and to the right of "F2". These merges used to be blocked by the conflict at "F2". But since we have merged "F2" manually, it might be that Git can now do some or all of these merges automatically. For example, we can now attempt to merge "E3" and "F2" to create "F3", or merge "F2" and "G1" to create "G2", and continue filling in the white area until we are blocked by new conflicts.

If we are lucky, the conflict "F2" was isolated and the whole block is now mergeable:

o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11    ← master
    |   |    |    |    |    |    |    |    |    |     |     |
    A - A1 - A2 - A3 - A4 - A5 - A6 - A7 - A8 - A9 - A10 - A11
    |   |    |    |    |    |    |    |    |
    B - B1 - B2 - B3 - B4 - B5 - B6 - B7 - B8   x     x     x
    |   |    |    |    |    |    |
    C - C1 - C2 - C3 - C4 - C5 - C6   x    x    x     x     x
    |   |    |    |    |    |    |
    D - D1 - D2 - D4 - D4 - D5 - D6   x    x    x     x     x
    |   |    |    |    |    |    |
    E - E1 - E2 - E3 - E4 - E5 - E6   x    x    x     x     x
    |   |    |    |    |    |    |
    F - F1 - F2 - F3 - F4 - F5 - F6   x    x    x     x     x
    |   |    |    |    |    |    |
    G - G1 - G2 - G3 - G4 - G5 - G6   x    x    x     x     x
    |   |    |    |    |    |    |
    H - H1 - H2 - H3 - H4 - H5 - H6   x    x    x     x     x
    |   |    |    |    |    |    |
    I - I1 - I2 - I3 - I4 - I5 - I6   x    x    x     x     x

    ↑
  branch

Of course we might not be so lucky, and new conflicts might be revealed in the rectangle previously blocked by "F2". But either way, we have made at least some progress in pushing back the conflict frontier.

If we continue merging commits pairwise--automatically when possible, manually when necessary--eventually we will clear the whole diagram of conflicts. When this is accomplished, the incremental merge is done:

o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11    ← master
    |   |    |    |    |    |    |    |    |    |     |     |
    A - A1 - A2 - A3 - A4 - A5 - A6 - A7 - A8 - A9 - A10 - A11
    |   |    |    |    |    |    |    |    |    |     |     |
    B - B1 - B2 - B3 - B4 - B5 - B6 - B7 - B8 - B9 - B10 - B11
    |   |    |    |    |    |    |    |    |    |     |     |
    C - C1 - C2 - C3 - C4 - C5 - C6 - C7 - C8 - C9 - C10 - C11
    |   |    |    |    |    |    |    |    |    |     |     |
    D - D1 - D2 - D3 - D4 - D5 - D6 - D7 - D8 - D9 - D10 - D11
    |   |    |    |    |    |    |    |    |    |     |     |
    E - E1 - E2 - E3 - E4 - E5 - E6 - E7 - E8 - E9 - E10 - E11
    |   |    |    |    |    |    |    |    |    |     |     |
    F - F1 - F2 - F3 - F4 - F5 - F6 - F7 - F8 - F9 - F10 - F11
    |   |    |    |    |    |    |    |    |    |     |     |
    G - G1 - G2 - G3 - G4 - G5 - G6 - G7 - G8 - G9 - G10 - G11
    |   |    |    |    |    |    |    |    |    |     |     |
    H - H1 - H2 - H3 - H4 - H5 - H6 - H7 - H8 - H9 - H10 - H11
    |   |    |    |    |    |    |    |    |    |     |     |
    I - I1 - I2 - I3 - I4 - I5 - I6 - I7 - I8 - I9 - I10 - I11

    ↑
  branch

But when the incremental merge is done, the full merge is also done! Commit "I11" combines all of the changes from "master" with all of the changes from "branch"; in other words, it is the merge of "master" and "branch". The merge nightmare is over.

Still to come

My next article will explain how to convert an incremental merge into a simple merge, a simple rebase, or a rebase with history. In future articles I will compare the available merge alternatives, present less exhaustive variants of the full incremental merge and describe git-imerge, a tool that automates incremental merging.

Notes:

[1]The technical reason why merging "E2" and "F1" into "F2" is simpler than merging "2" and "F" directly is that "E2" and "F1" share nearby commit "E1" as a merge base (see the documentation for git-merge-base(1)). By contrast, the merge base of "2" and "F" is commit "0", which is further away from the commits to be merged.

No comments: