git-imerge: a practical introduction

git-merge on steroids / git-rebase for the masses
This article is a practical introduction to incremental merging using git-imerge: why you need it, what it does, and how to use it.
(Don't fear; this article is not as long as it looks. Most of it consists of big ASCII-art illustrations and example program output.)

Why incremental merge?

The traditional alternatives for combining two branches both have serious problems.

git merge pain

• You need to resolve one big conflict that mixes up a lot of little changes on both sides of the merge. (Resolving big conflicts is hard!)
• Merging is all-or-nothing:
  • There is no way to save a partly-done merge, so
    • You can't record your progress.
    • You can't switch to another branch temporarily.
    • If you make a mistake, you cannot revert only part of the merge.
    If you cannot resolve the whole conflict, there is nothing to do but start over.
    
  • There is no way to test a partly-done merge--the code won't even build until the conflict is completely resolved.
• It is difficult to collaborate on a merge with a colleague.

git rebase pain

• It is very problematic to rebase work that has been published.
  • Rebasing is unfriendly to collaboration.
• You have to reconcile each of the branch commits with all of the changes on master.
• Rebasing is all-or-nothing:
  • It is awkward to interrupt a rebase while it is in progress: you're not even on a branch, and rebase doesn't preserve the relationship between old commits and new.
• Rebasing discards history (namely the old version of the branch).
• Rebasing often requires similar conflicts to be resolved multiple times.

Incremental merge

git-imerge implements a new merging method, incremental merge, that reduces the pain of merging to its essential minimum. git-imerge:

• Presents conflicts pairwise: you only ever need to resolve one commit from each branch at a single time.
  • Small conflicts (much easier to resolve than large conflicts).
  • You can view commit messages and individual diffs to see what each commit was trying to do.
• Records all intermediate merges with their correct ancestry, as commits in your repository. An incremental merge that is in progress
  • ...can be interrupted.
  • ...can be pushed to a server.
  • ...can be pulled by a colleague, worked on, and pushed again.
• Never shows the same conflict twice. Once a conflict has been resolved, it is stored in the DAG to make future merges easier.
• Lets you test every intermediate state. If there is a problem, you can use "git bisect" to find the exact pairwise merge that was faulty. You can redo that merge and continue the incremental merge from there (retaining earlier pairwise merges).
• Is largely automated and surprisingly efficient.
• Allows the final merge to be simplified for the permanent record, omitting the intermediate results.

The basic idea

Suppose you want to merge "branch" into "master":

o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11    ← master
     \
      A - B - C - D - E - F - G - H - I                ← branch

First draw the diagram a bit differently:

o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11    ← master
    |
    A
    |
    B
    |
    C
    |
    D
    |
    E
    |
    F
    |
    G
    |
    H
    |
    I

    ↑
  branch

Now start filling it in, merging one pair at a time:

o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11    ← master
    |   |
    A - A1
    |
    B
    |
    C
    |
    D
    |
    E
    |
    F
    |
    G
    |
    H
    |
    I

    ↑
  branch

"A1" is a merge between a single commit ("1") on master and a single commit ("A") on branch.
Continue...

o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11    ← master
    |   |
    A - A1
    |   |
    B - B1
    |
    C
    |
    D
    |
    E
    |
    F
    |
    G
    |
    H
    |
    I

    ↑
  branch

"B1" is a merge between "A1" and "B". Since "A1" already includes the changes from "1" and "A", this merge only has to add the changes from commit "B", which are hopefully limited in scope. If there is a conflict, it is hopefully small.
Most of these pairwise merges will not conflict, and git-imerge will let do them for you automatically until it finds a conflict:

o - 0 - 1  - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11    ← master
    |   |    |
    A - A1 - A2
    |   |    |
    B - B1 - B2
    |   |    |
    C - C1 - C2
    |   |    |
    D - D1 - D2
    |   |    |
    E - E1 - E2
    |   |
    F - F1   X
    |   |
    G - G1
    |   |
    H - H1
    |   |
    I - I1

    ↑
  branch

Now you have to help resolve the conflict that arose at "X" when merging "E2" and "F1". But Git knows that these two commits share "E1" as a common ancestor ("merge base"), so all you have to do is resolve the change originally made in master commit "2" with the change that was made in branch commit "F":

o - 0 - 1  - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11    ← master
    |   |    |
    A - A1 - A2
    |   |    |
    B - B1 - B2
    |   |    |
    C - C1 - C2
    |   |    |
    D - D1 - D2
    |   |    |
    E - E1 - E2
    |   |    |
    F - F1 - F2
    |   |
    G - G1
    |   |
    H - H1
    |   |
    I - I1

    ↑
  branch

Continue in this manner until the diagram is complete:

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

Done!

Simplifying the results

A completed incremental merge contains all of the information you could possibly want to know about combining two branches; all you need to do now is discard any information that you don't want in your permanent record. For example,

• Commit "I11" is the simple merge of "branch" into "master":

  o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11
      |                                                       |
      A                                                       |
      |                                                       |
      B                                                       |
      |                                                       |
      C                                                       |
      |                                                       |
      D                                                       |
      |                                                       |
      E                                                       |
      |                                                       |
      F                                                       |
      |                                                       |
      G                                                       |
      |                                                       |
      H                                                       |
      |                                                       |
      I ---------------------------------------------------- I11'  ← master
  
      ↑
    branch
  

  (Usually such a diagram is drawn like so:
  

  o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - I11'  ← master
       \                                               /
        A -- B -- C --- D --- E --- F --- G --- H --- I       ← branch
  

  .)
  
• The rightmost column is the rebase of "branch" onto "master":

  o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11    ← master
                                                              |
                                                             A11'
                                                              |
                                                             B11'
                                                              |
                                                             C11'
                                                              |
                                                             D11'
                                                              |
                                                             E11'
                                                              |
                                                             F11'
                                                              |
                                                             G11'
                                                              |
                                                             H11'
                                                              |
                                                             I11'  ← branch
  

• The bottommost row is the rebase of "master" onto "branch":

  o - 0
      |
      A
      |
      B
      |
      C
      |
      D
      |
      E
      |
      F
      |
      G
      |
      H
      |
      I - I1'- I2'- I3'- I4'- I5'- I6'- I7'- I8'- I9'- I10'- I11'  ← master
  
      ↑
    branch
  

• If you have already published branch, consider converting this into a rebase with history:

  o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11    ← master
      |                                                       |
      A ---------------------------------------------------- A11'
      |                                                       |
      B ---------------------------------------------------- B11'
      |                                                       |
      C ---------------------------------------------------- C11'
      |                                                       |
      D ---------------------------------------------------- D11'
      |                                                       |
      E ---------------------------------------------------- E11'
      |                                                       |
      F ---------------------------------------------------- F11'
      |                                                       |
      G ---------------------------------------------------- G11'
      |                                                       |
      H ---------------------------------------------------- H11'
      |                                                       |
      I ---------------------------------------------------- I11'
  
                                                              ↑
                                                            branch
  

  Rebase-with-history is a useful hybrid between rebasing and merging, having the advantages that it retains both the old and the new versions of the rebased commits, and that it is a valid way of rebasing already-published history without the known problems of a simple rebase.
  

Efficiency

In most cases git-imerge does not have to construct the full incremental merge. It uses an efficient algorithm, based on bisection, for filling in large blocks of the incremental merge quickly and homing in on the conflicts. A typical in-progress merge might look like this:

o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11    ← master
    |   |    |    |    |    |    |    |    |    |     |     |
    A -   --   --   --   --   -- A6 -   -- A8 - A9 - A10 - A11
    |   |    |    |    |    |    |    |    |
    B -   --   --   --   --   -- B6 - B7 - B8   X
    |   |    |    |    |    |    |
    C -   --   --   --   --   -- C6   X
    |   |    |    |    |    |    |
    D -   --   --   --   --   -- D6
    |   |    |    |    |    |    |
    E - E1 - E2 - E3 - E4 - E5 - E6
    |   |
    F - F1   X
    |   |
    G - G1
    |   |
    H - H1
    |   |
    I - I1

    ↑
  branch

where the "X"s marks pairwise merges that are known to conflict (i.e., they need user attention), and the cross-hatched rectangles are merges that could be skipped because the merges on the boundaries of the rectangles were all successful.

git-imerge

git-imerge implements incremental merging for Git. This section shows how to use git-imerge to do a simple merge.

• You begin much like with git merge: check out the destination branch and then tell git imerge what branch you want to merge into it:

  $ git checkout master
  $ git imerge start --name=merge-branch --first-parent branch
  

  Multiple imerges can be in progress simultaneously, so you have to give each one a name, in this case "merge-branch".
  
• git-imerge then uses bisection to find pairwise merges that conflict, and asks user to fix them one pair at a time:

  Attempting automerge of 1-1...success.
  Attempting automerge of 1-4...success.
  Attempting automerge of 1-6...success.
  Attempting automerge of 9-6...failure.
  Attempting automerge of 5-6...failure.
  Attempting automerge of 3-6...success.
  Attempting automerge of 4-6...failure.
  Attempting automerge of 4-1...success.
  Attempting automerge of 4-4...failure.
  Attempting automerge of 4-3...failure.
  Attempting automerge of 4-2...success.
  Attempting automerge of 9-2...success.
  Autofilling 1-6...success.
  Autofilling 2-6...success.
  Autofilling 3-1...success.
  Autofilling 3-2...success.
  Autofilling 3-3...success.
  Autofilling 3-4...success.
  Autofilling 3-5...success.
  Autofilling 3-6...success.
  Autofilling 4-2...success.
  Autofilling 5-2...success.
  Autofilling 6-2...success.
  Autofilling 7-2...success.
  Autofilling 8-2...success.
  Autofilling 9-1...success.
  Autofilling 9-2...success.
  Attempting automerge of 4-3...failure.
  Switched to branch 'imerge/c-d'
  Auto-merging conflict.txt
  CONFLICT (add/add): Merge conflict in conflict.txt
  Automatic merge failed; fix conflicts and then commit the result.
  
  Original first commit:
  commit b7fe8a65d0cee2e388e971c4b29be8c6cbb25ee1
  Author: Lou User <luser@example.com>
  Date:   Fri May 3 14:03:05 2013 +0200
  
      c conflict
  
  Original second commit:
  commit bd0373cadae08d872536bcda8214c0631e19945a
  Author: Lou User <luser@example.com>
  Date:   Fri May 3 14:03:05 2013 +0200
  
      d conflict
  
  There was a conflict merging commit 4-3, shown above.
  Please resolve the conflict, commit the result, then type
  
      git-imerge continue
  

  Please note that git-imerge tells you exactly which of the original commits need to be combined in this merge, and displays their log messages.
  
• You can get a diagram of the current state of the merge (it is in crude ASCII-art for now):

  $ git imerge diagram
  **********
  *??|?????|
  *--+-----+
  *??|#?????
  *??|??????
  *??|??????
  *--+??????
  
  Key:
    |,-,+ = rectangles forming current merge frontier
    * = merge done manually
    . = merge done automatically
    # = conflict that is currently blocking progress
    @ = merge was blocked but has been resolved
    ? = no merge recorded
  

• After you fix the indicated conflict and commit the result, run git imerge continue to tell git-imerge to incorporate the result and proceed to the next conflict:

  $ git add ...
  $ git commit
  $ git imerge continue
  Merge has been recorded for merge 4-3.
  Attempting automerge of 5-3...success.
  Attempting automerge of 5-3...success.
  Attempting automerge of 9-3...success.
  Autofilling 5-3...success.
  Autofilling 6-3...success.
  Autofilling 7-3...success.
  Autofilling 8-3...success.
  Autofilling 9-3...success.
  Attempting automerge of 4-4...success.
  Attempting automerge of 4-5...success.
  Attempting automerge of 4-6...success.
  Attempting automerge of 9-6...success.
  Autofilling 4-6...success.
  Autofilling 5-6...success.
  Autofilling 6-6...success.
  Autofilling 7-6...success.
  Autofilling 8-6...success.
  Autofilling 9-4...success.
  Autofilling 9-5...success.
  Autofilling 9-6...success.
  Merge is complete!
  $ git imerge diagram
  **********
  *??.?????|
  *??......|
  *??.*....|
  *??.?????|
  *??.?????|
  *--------+
  
  Key:
    |,-,+ = rectangles forming current merge frontier
    * = merge done manually
    . = merge done automatically
    # = conflict that is currently blocking progress
    @ = merge was blocked but has been resolved
    ? = no merge recorded
  

• When you are done, simplify the incremental merge into a simple merge, a simple rebase, or a rebase-with-history:

  $ git imerge finish --goal=merge
  

  By default, this creates a new branch NAME that points at the result, and checks out that branch:
  

  $ git log -1 --decorate
  commit 79afd870a52e216114596b52c800e45139badf74 (HEAD, merge-branch)
  Merge: 8453321 993a8a9
  Author: Lou User <luser@example.com>
  Date:   Wed May 8 10:08:07 2013 +0200
  
      Merge frobnicator into floobifier.
  

  (It also deletes all of the temporary data.)
  

Intermediate data

During an incremental merge, intermediate results are stored directly in your repository as special references:

refs/imerge/NAME/state

A blob containing a little bit of metadata.

refs/imerge/NAME/manual/M-N

Manual merge including all of the changes through commits M on master and N on branch.

refs/imerge/NAME/auto/M-N

Automatic merge including all of the changes through commits M on master and N on branch.

refs/heads/imerge/NAME

Temporary branch used when resolving merge conflicts.

refs/heads/NAME

Default reference name for storing final results.

Project status

As of this writing, git-imerge is very new and still experimental. Please try it out, but use it cautiously (e.g., on a clone of your main Git repository) and give me your feedback!

Contributing

I have lots of ideas for additional features, and am sure that you do too. See the project TODO list for inspiration, and get involved!

For more information:

• The git-imerge project home page on GitHub.

• Blog articles about incremental merge

• Blog articles about rebase-with-history

Incremental merge vs. direct merge vs. rebase

	Direct merge	Rebase	Incremental merge
Basic commands	git checkout master git merge branch <resolve big conflict> git commit	git checkout branch git rebase master while not done: <resolve smaller conflict> git rebase --continue	git checkout master git-imerge start [...] branch while not done: <resolve pairwise conflict> git commit [...] git-imerge continue git-imerge simplify [...] (This uses the git-imerge tool [1].)
Size of conflicts	All of the changes in master have to be combined with all of the changes in branch in one go. Various changes are mixed up together, even if they were originally committed separately, which can make the conflict large or even intractable.	One step of a rebase requires one change from branch to be resolved with all of the changes from master. This is easier than doing a direct merge in one step, but still mixes up unrelated changes.	At any step, only one change from master has to be combined with one change from branch. The commit messages and deltas from each of the two changes are available to help you understand the two changes.
Effort	The least amount of effort, if there are only a few simple conflicts. Effort increases highly nonlinearly in the size of the conflict.	A bit more effort, if conflicts are simple and isolated. Conflicts tend to be smaller than for direct merge, but more numerous. If there are sequential overlapping conflicts, you might need to resolve similar conflicts multiple times.	More processing power required at start of merge. Conflicts are resolved as lots of little conflicts, so the effort scales closer to linearly with the number of pairwise conflicts [2]. Benefits decrease if original changes were not committed in small, self-contained steps.
Interruptibility	After you start a direct merge, there is no way to record partial results. You are forced to either complete the whole merge and then commit it, or abandon the whole merge using git merge --abort. Progress on a direct merge is all-or-nothing.	Once a rebase is started, it is awkward to interrupt it [3]. It is true that intermediate results are committed, but because the rebase discards the connection between original commits and rebased commits, you have to do the bookkeeping yourself.	Each of the pairwise merges is resolved and committed separately. After each pairwise merge is committed, you can switch branches, do something else for a while, then return later to the incremental merge. Progress on an incremental merge can be locked in in small increments.
Testability, fixability	The results of a direct merge cannot be tested until the whole merge is done. If you mess up one part of the merge, there is no easy way to revert only that part.	The individual rebased commits can be tested. But if there is a failure, it is nontrivial to figure out which of the changes on master interacted badly with the rebased commit.	Each pairwise merge can be tested individually. If one fails testing, it can be discarded and redone without having to discard earlier pairwise merges. If a failure is discovered after the incremental merge is done, it is possible to use git bisect to find out exactly which of the pairwise merges was faulty.
Collaboration	Since an in-progress direct merge is not savable, the only way to get help from a colleague on a direct merge is to call the colleague to your computer and have him/her work in your working copy.	It is strongly recommended that a branch that has been published not be rebased. Thus rebasing is usually applied only to local work done by a single developer. It is awkward to share the work of rebasing a branch [3].	Each pairwise merge commit is a normal commit that can be exchanged with other colleagues via push/fetch/etc. Each pairwise conflict can be resolved by the person most familiar with that part of the code. In fact, if you plan to retain the whole incremental merge in your repository history, then no history rewriting is necessary at all, and there is no problem merging a published branch, or publishing the intermediate merge commits as you go.
Recommendations	In a merge-based workflow, use direct merge for simple merges. If a difficult conflict arises, switch to incremental merge and then simplify the results into a simple merge.	In a rebase-based workflow with unpublished local changes, use rebase to update your work onto upstream changes if you only expect trivial conflicts. If you expect (or, midway through the rebase, encounter) nontrivial conflicts, switch to incremental merge and then simplify the results into a rebase.	Use incremental merge when: a simple merge or rebase is desired but the conflicts are nontrivial you would like to rebase work that has already been published (simplify results to rebase-with-history) you want to retain a permanent record of how conflicts were resolved you want to collaborate on a merge or rebase

Notes:

[1]	git-imerge is a new tool that I am working on to automate incremental merging. It is available as open-source from its public Git repository.

[2]	If development was truly chaotic, and especially if it involved changes that were later reverted, then an incremental merge might be much more effort than a simple merge because it requires you to resolve conflicts between changes that are obsolete.

[3]

(1, 2) To pause and/or share the work of rebasing, add a reference to the last successful rebased commit using git branch rebase-wip before aborting the rebase with git rebase --abort. The result will look something like: o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 ← master | | A A' | | B B' | | C C' | | D D' | E ↑ | rebase-wip F | G | H | I ↑ branch Such an interrupted rebase can be continued using a command like git rebase --onto rebase-wip D branch, where D is the SHA1 of the last commit that was successfully rebased in the first attempt. The work can be shared by publishing tips branch and rebase-wip, but care should be taken when doing so to prevent other people from basing their own work on the pre-rebased branch branch.

One merge to rule them all

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, how to make pictures of the merge conflict frontier, and how to complete a full incremental merge. What can we do with an incremental merge once it is complete?
An incremental merge, once completed, contains all of the information you could possibly want about combining two branches. Specifically, it records how to do each of the N*M pairwise merges, where N and M are the number of commits on each branch. Each of these submerges is stored as a git commit with an ancestry that correctly reflects its contents. In fact, an incremental merge might contain more information than you want to store permanently in your repository. In this article, I will explain how to use an incremental merge to derive a simple merge, a rebase (in either direction), or a rebase-with-history.
In later articles I will provide a table comparing incremental merge with simple merge and simple rebase, explain how to compute an incremental merge more efficiently, and explain git-imerge, a new tool that automates incremental merging.

The starting point

For the purposes of this discussion, we will assume that we have already completed a full incremental merge as described in my previous article and that it looks like this [1]:

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

Remember that commits "0"-"11" are on master, and commits "A"-"I" are on the branch. (It goes without saying that there is nothing special about master; any two branches can be merged in this manner.) The rest of the commits are pairwise merges between the neighbor above and the neighbor to the left. For example, commit "C3" is the pairwise merge between "B3" and "C2", and it includes all of the changes through master commit "C" and branch commit "3".
The most interesting commit is "I11". It contains all of the changes through master commit "11" and branch commit "I". In other words, its contents are the merge of "master" and "branch". By resolving simple pairwise conflicts, we have managed indirectly to resolve the full conflict.
Incremental merging is basically a divide and conquer approach to merging. It replaces the task of resolving one big hairy merge conflict with the task of resolving many little conflicts. Since big conflicts are much harder to resolve than small conflicts, this can be a huge win, and can even make it possible to perform incrementally a merge that would be intractable in a single step.

Using the results of an incremental merge

Now that we have a complete incremental merge, how can we use the results?
In following sections I will explain how to winnow the information from an incremental merge down into any one of the following:

• The simple one-step merge of "master" and "branch"
• "branch" rebased on top of "master"
• "master" rebased on top of "branch"
• Either type of rebase with history

Obtaining one of these results is done by rewriting history to selectively discard the intermediate commits that are not wanted, while adjusting the parentage of the commits that are retained.

Simple merge

If your goal is a simple merge of branch into master, (with none of the intermediate results), then all you need from the incremental merge is commit "I11". Specifically, you need a single, new merge commit with the contents of "I11" but with commits "11" and "I" as parents:

o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11
    |                                                       |
    A                                                       |
    |                                                       |
    B                                                       |
    |                                                       |
    C                                                       |
    |                                                       |
    D                                                       |
    |                                                       |
    E                                                       |
    |                                                       |
    F                                                       |
    |                                                       |
    G                                                       |
    |                                                       |
    H                                                       |
    |                                                       |
    I ---------------------------------------------------- I11'  ← master

    ↑
  branch

It may be easier to recognize this diagram when it is redrawn in the conventional orientation:

o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - I11'  ← master
     \                                               /
      A -- B -- C --- D --- E --- F --- G --- H --- I       ← branch

Rebase of "branch" onto "master" or vice versa

If you prefer to rebase "branch" onto "master", what you want are the contents of commits "A11" through "I11", but with their second parents omitted to convert them from merge commits into simple, linear commits:

o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11    ← master
                                                            |
                                                           A11'
                                                            |
                                                           B11'
                                                            |
                                                           C11'
                                                            |
                                                           D11'
                                                            |
                                                           E11'
                                                            |
                                                           F11'
                                                            |
                                                           G11'
                                                            |
                                                           H11'
                                                            |
                                                           I11'  ← branch

Similarly, it is possible to use the results to rebase "master" onto "branch" (i.e., as if the changes made on "branch" had actually been made earlier in the history of "master") by retaining commits "I1".."I11" with their first parents omitted:

o - 0
    |
    A
    |
    B
    |
    C
    |
    D
    |
    E
    |
    F
    |
    G
    |
    H
    |
    I - I1'- I2'- I3'- I4'- I5'- I6'- I7'- I8'- I9'- I10'- I11'  ← master

    ↑
  branch

Rebase with history

It is also possible to rebase "branch" onto "master", but retaining part of the history. This is a very useful hybrid between rebasing and merging, having the advantages that it retains both the old and the new versions of the rebased commits, and that it is a valid way to rebase already-published history without the known problems of a simple rebase [2]. A rebase with history is extracted from a full incremental merge by retaining commits "A11" through "I11", but adjusting their second parents to point at "A" through "I" respectively:

o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11    ← master
    |                                                       |
    A ---------------------------------------------------- A11'
    |                                                       |
    B ---------------------------------------------------- B11'
    |                                                       |
    C ---------------------------------------------------- C11'
    |                                                       |
    D ---------------------------------------------------- D11'
    |                                                       |
    E ---------------------------------------------------- E11'
    |                                                       |
    F ---------------------------------------------------- F11'
    |                                                       |
    G ---------------------------------------------------- G11'
    |                                                       |
    H ---------------------------------------------------- H11'
    |                                                       |
    I ---------------------------------------------------- I11'

                                                            ↑
                                                          branch

Analogously, it is possible to rebase "master" onto "branch" with history.

Maybe keep everything?

As we have seen, a full incremental merge is quite powerful: it contains enough information to derive all of the common rebase/merge results as special cases.
Come to think of it, why should we have to decide between merge vs. rebase at all? Why not retain all of the intermediate commits in our history? Retaining the full merge history is simple; we just reset the "master" reference to "I11" without rewriting any commits:

o - 0 - 1  - 2  - 3  - 4  - 5  - 6  - 7  - 8  - 9  - 10  - 11
    |   |    |    |    |    |    |    |    |    |     |     |
    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   ← master

    ↑
  branch

The resulting repository holds complete information about how the individual commits were pairwise merged, which conflicts had to be resolved manually, and how they were resolved (hopefully explained in the individual log messages). It contains (as special cases) all of the information that would be recorded for a simple merge, as well as all of the information that would be retained by a rebase of "branch" on "master" or vice versa, with or without history.
However, retaining the whole history of the incremental merge, though arguably the correct approach, causes the permanent retention of a lot of intermediate commits that will--in practice--probably never be needed. Moreover, some git tools (like gitk) aren't able to display such a complicated history very well. Therefore, it is probably best to use incremental merge as a tactic to achieve a more limited result.

Still to come

In future articles I plan to present a sparse variant of the full incremental merge and describe git-imerge, a tool that automates incremental merging.

Notes:

[1]	In most cases it is overkill to complete the full incremental merge, and a sparser variant would be sufficient. But it is easier to understand sparse incremental merges after we have analyzed and discussed the full version. So this article we assume that the full incremental merge is available.

[2]	The problems of rebasing published work is described, for example, in the git-rebase(1) manpage section "Recovering from Upstream Rebase".

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.

Rebase with history -- implementation ideas

In my last blog posts, I discussed and idea for retaining history when rebasing and a concrete example of how it improves on traditional rebasing without history. In this third post in the series, I would like to discuss how rebase with history could be implemented.

First, a reminder of what a simple rebase-with-history looks like:

M0----M1----M2           M0----M1----M2
  \                        \           \
   \               -->      \           B1'---B2'
    \                        \         /     /
     B1----B2                 -------B1----B2

The work B1+B2 on a feature branch as been rebased onto the current version M2 of the master branch, producing two rebased revisions B1' and B2'. A traditional rebase-without-history would discard commits B1 and B2, whereas the point of rebase-with-history is to retain them.

A rebase-with-history can be done manually, today, in any of the DAG-based DVCSs. The algorithm is basically:

1. Ensure that the old parent of the rebased branch (M0 in the example above) is a direct ancestor of the new parent (M2).
2. Create a new temporary branch at M2.
3. For each commit that is to be rebased, merge that commit onto the temporary branch, resolving conflicts if necessary. This creates merge commits B1' then B2'.
4. Designate the last new merge commit (B2') at the head of the temporary branch to be the new head of the feature branch.

Avoiding information overload

Earlier I argued that the full DAG resulting from a rebase-with-history contains more detail than the average user wants to see. After all, many people are happy with the current style of rebase-without-history, which completely discards B1 and B2. So how can we reduce the visual clutter without losing the historical information that is needed to support future merges? In other words, assume that the VCS wants to store the above DAG, but the typical user typically wants to see this:

M0----M1----M2
              \
               B1'---B2'

How can this dualism be implemented?

It is clear that the commits B1 and B2 have to be retained in the DAG rather than recorded in some kind of supplemental metadata. Otherwise, many VCS commands would have to be modified to be aware of this metadata and treat B1 and B2 as if they were in the DAG. It is also necessary to prevent B1 and B2 from being garbage collected. So it is simpler to retain them in the DAG proper.

It is also clear that somehow marking the pre-rebase commits B1 and B2 themselves "historical" is not correct. After all, those commits may be integral to other branches in which they are not "historical". Perhaps the rebased version of the branch will turn out to be a false start and never even be pushed upstream. So it is not the commits themselves that are "historical"; it is only their relationship with the rebased commits B1' and B2' that is "historical".

And that, of course, suggests the correct solution. Commit B1' has two parents, M2 and B1. M2 is always interesting and should be recorded as a normal parent. But B1 is interesting mainly as the historical predecessor of B1', but usually not as part of the visible history in the upstream repository. Therefore, within the B1' node, B1 should be recorded as a parent but with a special "historical" flag.

Similarly, commit B2' has two parents--B1', which is a "normal" parent, and B2, which should be recorded as a "historical" parent.

The "historical" flag would be mainly a hint to GUI-related commands that the linked-to parent can be suppressed in most user views. When walking the DAG for display purposes, "historical" parents would simply not be followed. The historical commits B1 and B2 are only connected to the branch head via "historical" parent links, so they will not be traversed. By this mechanism, the DAG of the branch is displayed just like the DAG of a rebase-without-history. Of course, if commits B1 and B2 are non-historical ancestors of other branches, they will be displayed normally when the ancestry of those branches is displayed.

The GUI-related commands should have an extra --full-history flag to override the default behavior, causing historical parents to be displayed along with non-historical parents. (Optionally, historical links could be flagged somehow to allow them to be colored differently, etc.)

CAVEAT: Please recall that this whole discussion only applies to the "feature branch tracking upstream" class of rebase operations, namely those where:

• the order of commits in the branch is unchanged, and
• the new location of the branch is a descendant of the old location of the branch.

However, this is a common and important class of rebases. Other types of rebases (e.g., those that change the order of commits) cannot be done with history retention, because there is no way to represent such history within a DAG model. (darcs uses different technology and therefore doesn't share this limitation.)

Feedback: I would be very happy to receive feedback about this proposal for "rebase with history". Would it be helpful? Are there corner-cases that would prevent its implementation? Where has it been discussed before? (There's nothing new under the sun, you know...) Please add comments!

[Modified 2009-08-13 to add an outline of the rebase-with-history algorithm.]

Upstream rebase Just Works™ if history is retained

The git-rebase documentation has a section entitled "Recovering from Upstream Rebase" describing how to straighten out the mess that results from an upstream repository doing a rebase. In my last blog post I described how simple rebases can be done with history, and claimed that this makes it possible to share a repository that has been rebased. In this post, I would like to show how the example from the git-rebase manual page work out if rebase history is retained.

First, the example without history. The premise is that you are working on a topic branch that is dependent on a subsystem that somebody else is working on:

m---m---m---m---m---m---m---m  master
     \
      o---o---o---o---o  subsystem
                       \
                        *---*---*  topic

Then the subsystem developer rebases subsystem onto master:

m---m---m---m---m---m---m---m  master
     \                       \
      o---o---o---o---o       o'--o'--o'--o'--o'  subsystem
                       \
                        *---*---*  topic

If you now merge the topic branch to the subsystem branch, a mess results:

m---m---m---m---m---m---m---m  master
     \                       \
      o---o---o---o---o       o'--o'--o'--o'--o'--M  subsystem
                       \                         /
                        *---*---*-..........-*--*  topic

The first problem here is that git has no idea that the two versions of the subsystem revisions, namely "o-o-o-o-o" and "o'-o'-o'-o'-o'", actually contain the same logical changes. Therefore, the merge that creates commit M can result in spurious conflicts. Specifically, git will try to combine the changes in "o-o-o-o-o" with those in "o'-o'-o'-o'-o'", and may or may not be able to make sense out of the situation.

Second, in some (admittedly rather unlikely) situations, git's ignorance can cause problems with future merges.

Finally, there is no easy way to convert the merged topic branch into a series of patches that apply cleanly to the rebased subsystem branch and can therefore be submitted upstream. In this case, the only available patch that applies cleanly to the rebased subsystem branch is the merge patch M, which is a single commit that squashes together the entire topic branch and is therefore difficult to review.

In fact, in the git world you typically wouldn't merge the topic branch into the subsystem branch. Instead, you would rebase the topic branch onto the rebased subsystem branch:

m---m---m---m---m---m---m---m  master
                             \
                              o'--o'--o'--o'--o'  subsystem
                                               \
                                                *'--*'--*'  topic

This gives a usable result, but requires extra effort by the topic branch maintainer (and the maintainers of any other branches that rely on the subsystem branch or the topic branch). Because this rebase is also prone to conflicts unless you explicitly tell git what interval of revisions to rebase, using a command like git rebase --onto subsystem SHA1 topic. SHA1 refers to the last commit in the pre-rebase "o-o-o-o-o" series, and you have to determine it yourself. Rebase-with-history relieves the user from having to do this kind of manual bookkeeping.

If, instead, the subsystem maintainer had retained history when rebasing as described in my earlier post, the DAG would look like this:

m---m---m---m---m---m---m---m  master
     \                       \
      \                       o'--o'--o'--o'--o'  subsystem
       \                     /   /   /   /   /
        --------------------o---o---o---o---o
                                             \
                                              *---*---*  topic

Now you are free to merge the topic branch with the subsystem branch:

m---m---m---m---m---m---m---m  master
     \                       \
      \                       o'--o'--o'--o'--o'  subsystem
       \                     /   /   /   /   / \
        --------------------o---o---o---o---o   ---------
                                             \           \
                                              *---*---*---x  topic

The fact that both the old and new versions of the subsystem revisions are still in the DAG is not a problem, because the dependencies make it clear to git that the old version is already incorporated into the new version, so git will never try to merge them again. But this is also not ideal, because it still doesn't allow the topic branch to be converted into a tidy patch series.

Even better, you can even rebase your changes onto the subsystem branch, preferably also retaining rebase history:

m---m---m---m---m---m---m---m  master
     \                       \
      \                       o'--o'--o'--o'--o'  subsystem
       \                     /   /   /   /   / \
        --------------------o---o---o---o---o   \
                                             \   \
                                              \   *'--*'--*'  topic
                                               \ /   /   /
                                                *---*---*

Whether you retain history during this rebase or not, the rebase is simple because git can figure out for itself what range of revisions to rebase. The result is also a well-formed repository, and will not create any problems for other developers who might have based their work on your topic branch. And when you are ready, you can submit the patches "*'-*'-*'" as-is to the subsystem maintainer.

Remember that just because the old and new versions of rebased revisions are included in the DAG doesn't mean that they have to be displayed in the UI all of the time. If there were a way to mark the old versions "uninteresting", then the "interesting" part of the DAG could be displayed just like in the rebase-without-history case:

m---m---m---m---m---m---m---m  master
                             \
                              o'--o'--o'--o'--o'  subsystem
                                               \
                                                *'--*'--*'  topic

but the retention of the hidden pre-rebase commits enables future rebases and merges to be carried out smoothly.

[Modified 2009-08-16 based on discussion the git mailing list; thanks especially to Björn Steinbrink for his comments.]

See also my related posts:

• an introduction to rebase-with-history
• thoughts about its implementation

A truce in the merge vs. rebase war?

There is a bit of a cultural war going on between the various DVCS communities. Git users love to use "git rebase" to rewrite the history in their local repository before pushing a perfect set of patches upstream, even though they realize that using rebase on work that has already been published causes lots of trouble. Bazaar users, on the other hand, tend to insist that history should be immutable and that merging is preferred over rebasing, and are shocked, SHOCKED at the libertine ways of their git counterparts.

In this blog post, I want to talk about the correspondence between rebasing and merging, and hope to show that there is a middle ground that has some of the advantages of both extremes. I will restrict myself to discussing a very specific kind of rebasing, namely tracking upstream changes while working on a feature branch.

In this post I will use ASCII art to represent repository DAGs; in these drawings, time progresses from left to right.

Suppose somebody is working on a feature branch that is logically developed as several smaller steps B1, B2, ..., and meanwhile development is continuing on master as M1, M2, ....

The problem with repeated merges from master to branch

After the feature branch has been developed for a while, the DAG looks like this.

M0----M1----M2
  \
   \
    \
     B1----B2

If master is merged to the feature branch, we get

M0----M1----M2
  \           \
   \           \
    \           \
     B1----B2----X1

where X1 is a merge commit that "corrects" B1+B2 for the changes that have occurred in master as M1+M2. A little while later, after work has proceeded on both master and the feature branch, the DAG looks like this

M0----M1----M2----M3----M4
  \           \
   \           \
    \           \
     B1----B2----X1----B3----B4

and the next merge changes it to

M0----M1----M2-------M3-------M4
  \           \                 \
   \           \                 \
    \           \                 \
     B1----B2----X1----B3----B4----X2

Where X2 is a merge commit that "corrects" B1+B2+X1+B3+B4 for the changes that occurred in master as M3 and M4.

The problem is that it is very difficult for a reviewer to check changes that are submitted in this form.

The reviewer could review the overall difference between M4 and X2, but then all of the changes would be mashed together and he wouldn't have the benefits of the commit messages explaining the individual steps.

The reviewer could review the changes patch by patch, but

• He is most familiar with the current state of master. But he has to analyze the earlier patches in the context of older versions of master (M0 and M2).
• The merge patches X1 and X2 are especially difficult to analyze. X2, for example, reflects the changes needed to adapt multiple patches (B1+B2+X1+B3+B4) to multiple changes on master (M1+M2+M3+M4). X1 cannot be checked without understanding the changes made between two historical master versions (M0..M2). Can you remember exactly what happened in your code base from four weeks ago until two weeks ago?

What's more, the patch series contains information that is of marginal usefulness to a reviewer. Why should the reviewer care how a logical change would have been made against a historical master revision, when his decision is actually whether to apply a change to the current master revision?

It is true that no information is lost, but the information is not retained in a very convenient form.

---

The problems with rebasing

The same situation, after the first rebase, now looks like this:

M0----M1----M2
              \
               \
                \
                 B1'---B2'

The original patches B1 and B2 have been transformed into patches B1' and B2', which are hopefully logically equivalent.

After further work, the DAG looks like

M0----M1----M2----M3----M4
              \
               \
                \
                 B1'---B2'---B3----B4

which is rebased a second time to

M0----M1----M2----M3----M4
                          \
                           \
                            \
                             B1''--B2''--B3'---B4'

This patch series is all very neat and clean and very easy to review. The patches can all be understood within a single context -- the current state of master -- that the reviewer is presumably most familiar with. The rebased patch series is optimized for the reviewer.

The problem is that rebasing discards history, perhaps not in the strict sense that intermediate commits are gone, but in the sense that there is no useful record of how the rebased patches are related to the original patches.

Specifically, the history of the individual patches has been lost (e.g., B1 -> B1' -> B1''). This loss is particularly unfortunate because these transformations were presumably done automatically by the VCS, which might have introduced errors. The author's original intention, as expressed in the original hand-written patches (B1, B2, B3, B4), has been lost. There is no way for the reviewer to drill down and tell the author, for example, that "when rebasing from B2' to B2'', you forgot to take into account change foo in M3".

Perhaps the worst problem with traditional rebasing is that it prevents collaboration. Somebody who pulls from a repository before and after a rebasing will experience conflicts because the two histories contradict each other. Thus the standard caveat "don't rebase within a published repository", which can be reworded to "don't collaborate on work that you might later want to rebase".

---

How should rebase really work?

For the simplest type of rebasing discussed above, it is simple to get both reviewing convenience and historical accuracy by changing rebase to retain a little bit more information about what it did.

Consider again the first rebasing:

M0----M1----M2          M0----M1----M2
  \                                   \
   \               -->                 \
    \                                   \
     B1----B2                            B1'---B2'

In fact, consider the first step of the first rebasing, in which B1 is "replayed" on top of M2:

M0----M1----M2           M0----M1----M2
  \                        \           \
   \               -->      \           B1'
    \                        \
     B1----B2                 B1----B2

This really involves merging the changes of (M1+M2) with the changes of B1. B1' is really a merge commit. So let's record it like a merge commit, with both of its ancestors:

M0----M1----M2           M0----M1----M2
  \                        \           \
   \               -->      \           B1'
    \                        \         /
     B1----B2                 -------B1----B2

The second step of the rebasing, similarly, merges B2 with (M1+M2+B1'), giving

M0----M1----M2           M0----M1----M2
  \                        \           \
   \               -->      \           B1'---B2'
    \                        \         /     /
     B1----B2                 -------B1----B2

The semantics of the resulting DAG is correct; B1' really does include all of the changes from M0+M1+M2 and also the changes from B1. Similarly, B2' includes the changes from B1' and from B2.

The resulting DAG is certainly more complicated than the one resulting from a traditional rebase, but it includes both the easy-to-review patches B1' and B2' and also the history of the individual patches B1 -> B1' and B2 -> B2'. It is an honest representation of the repository's history.

The key difference between this procedure and the simple merge described above is that the merge is done patch by patch. This avoids the creation of merge patches like X1 and X2 above that mix together the merge work needed for multiple patches.

After further work, the DAG looks like this:

M0----M1----M2----M3----M4
  \           \
   \           B1'---B2'---B3----B4
    \         /     /
     -------B1----B2

Now we rebase a second time:

M0----M1----M2----M3----M4
  \           \           \
   \           \           B1''--B2''--B3'---B4'
    \           \         /     /     /     /
     \           -------B1'---B2'---B3----B4
      \                /     /
       --------------B1----B2

The DAG is yet more complicated, but it is still correct and has the desired properties. It is easy to read off the easy-to-review patches (B1'', B2'', B3', B4'), and it is also easy to read off the history of individual patches (e.g., B1 -> B1' -> B1'').

Now, if somebody pulls from the repository between the two rebases and then again after the second rebase, the right thing will happen. The retention of the merge information allows rebased work to be shared. Indeed, one collaborator can do one rebase and another can do the next.

Maybe neither merging nor rebasing is optimal for maintaining a long-lived feature branch.

Is this overkill?

The DAGs resulting from these history-retaining rebases are quite complicated. Does anybody really want to see all this complexity in their main upstream repository?

Probably not, or at least not usually. So I see two alternatives:

• Retain the rebase history while working on the feature, but discard it when submitting patches upstream. This approach has the advantage that multiple people can collaborate on the feature without stepping on each others feet, but the upstream repository is spared the intermediate complexity. It also doesn't require any changes to the tools, except maybe some simple scripts to help with the iterative merge needed to do a history-retaining rebase.
• Retain the rebase history permanently, but suppress the display of the pre-rebase commits in most cases. This would require tool changes to allow commits to be marked "uninteresting" and to omit them from most types of operations.

See also my followup posts:

• a concrete example of rebasing within a repository that has already been published
• thoughts about the implementation of rebase-with-history