I just heard on GitMinutes #07 that Mercurial will soon have a feature that records the relationship between old and new versions of changesets when a changeset is rewritten. This is a topic that I find very interesting, so I did some reading.
Each "obsolete marker" is a many-to-one record stating that changesets [A1,A2,...] obsolete changeset A. This information can be shared between repositories. The obsolete changeset is retained as long as any non-obsolete changesets depend on it, after which it can be discarded. (Though it wasn't clear to me how repository 1 can know whether repository 2 contains commits based on a commit that has been marked obsolete in repository 1; perhaps human-to-human communication is required?)
Unlike regular parent relationships, these markers have no implications for commit ancestry. That is, the fact that changeset A' obsoletes changeset A does not imply that commit A' includes all of the ancestors of commit A. Because of this, obsolete markers can be used even if changesets are reordered, split, or squashed--actions that cannot be represented in an ancestry-only DAG.
If I understand correctly, obsolete markers should really be thought of as relationships between changesets (i.e., the deltas introduced by commits) as opposed to the commits (and tree states) themselves. It appears that they are intended mostly for transitional use before the history has solidified, and not as a permanent part of the record.
Because obsolete markers introduce a new type of "history", they complicate the history model. There are new types of conflicts that can arise because of them, and such conflicts have to be resolved in new ways.
I'm very curious how obsolete markers pan out in practice. It's definitely a feature that is worth keeping an eye on.
Wednesday, May 15, 2013
Wednesday, May 8, 2013
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.)
Continue...
Most of these pairwise merges will not conflict, and git-imerge will let do them for you automatically until it finds a conflict:
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.
- 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' ↑ branchRebase-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 continuePlease 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.
Sunday, May 5, 2013
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:
|
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 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.
In following sections I will explain how to winnow the information from an incremental merge down into any one of the following:
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.
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:
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.
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:
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. |
Subscribe to:
Posts (Atom)