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.)
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' ← branchThe 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 ↑ branchIf 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 | | A ---------------------------------------------------- A11' | | B ---------------------------------------------------- B11' | | C ---------------------------------------------------- C11' | | D ---------------------------------------------------- D11' | | E ---------------------------------------------------- E11' | | F ---------------------------------------------------- F11' | | G ---------------------------------------------------- G11' | | H ---------------------------------------------------- H11' | | I ---------------------------------------------------- I11' ← master ↑ 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 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
| |
A ---------------------------------------------------- A11'
| |
B ---------------------------------------------------- B11'
| |
C ---------------------------------------------------- C11'
| |
D ---------------------------------------------------- D11'
| |
E ---------------------------------------------------- E11'
| |
F ---------------------------------------------------- F11'
| |
G ---------------------------------------------------- G11'
| |
H ---------------------------------------------------- H11'
| |
I ---------------------------------------------------- I11' ← master
↑
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. |
Friday, December 28, 2012
Real-world conflict diagrams
In earlier articles, I described a way to diagram a conflicting merge, and presented an algorithm for efficiently mapping the conflict frontier which is implemented in an experimental program, git-mergemate. In this article, I would like to present a few examples of real-world merge diagrams.
To generate these diagrams, I first used the following command to search for merge commits in "master" that had manually-resolved conflicts:
git rev-list --merges --grep='Conflicts:' master
Assuming that the SHA1 of the merge is stored in $s, the two parents of such a commit can be written as $s^1 and $s^2. So I then ran git-mergemate like so:
git-mergemate diagram $s^1...$s^2
and converted the output from PPM format to PNG using the pnm2png utility [1].
Show me the pixels!
Each pixel in these diagrams represents one pairwise merge. Thus the images are quite compact; the width (in pixels) is the number of commits on "master" after the branch point, and the height is the number of commits on the branch. I am leaving the images at 1:1 scaling so that their relative sizes can easily be seen (hopefully you can zoom them using your browser if you want to see more detail).
A pixel is green if the corresponding merge was successful and red if the merge resulted in a conflict. The merges that were explicitly tested are shown as bright green/red; the other merges were inferred using the assumptions described in the algorithm article. As you can see, it takes very few test merges to compute a whole merge diagram.
Ho-hum
Most of the merge diagrams (about 80% of them) were quite boring.
A typical short branch with a conflict:
A short branch with an early conflict:
A very short branch merged long after it was created:
A longer branch merged soon after it was created, with a conflict with one of its later commits:
Single conflicts
However, about 20% of the merge diagrams were more interesting. The interesting diagrams tend to be bigger because they represent long-lived branches merged a considerable time after they were created.
Several diagrams show merges that might be blocked by a single pairwise conflict:
The conflict at the upper-left corner of the red rectangle might be all that is blocking this merge:
A long branch, merged before much was changed on "master":
A short branch, merged quite a while after it was created:
A branch that has diverged widely from "master", but might have only one pairwise conflict:
Multiple conflicts
Other diagrams are yet more complicated, with merge frontiers shaped by two pairwise conflicts:
A smallish diagram with two early conflict blocks:
Note that the top line in this diagram is green, meaning that the first branch commit doesn't conflict with any of the commits on master:
A larger merge with two early conflict blocks:
The biggest merge of all (281 commits on master, 235 commits on branch). Please note that even though the branch and master have diverged significantly, conflicts did not arise until quite some time after the branch was created:
Conclusion
A merge diagram provides a quick, intuitive overview of a conflicting merge, and highlights the individual commits on each branch that conflict with each other.
Most merge diagrams are simple (in fact I didn't observe any with more than two blocking pairwise merges). Thus there is hope that, by focusing our attention on these critical pairwise merges, we can resolve a nightmare merge with an acceptable level of pain and (more importantly) some confidence in the result.
In upcoming articles I will explore how to use incremental merging to resolve a nightmare merge.
Notes:
| [1] | Putting this all together, we have for s in $(git rev-list --grep='Conflicts:' --merges master) do git-mergemate diagram $s^1...$s^2 | pnmtopng >../diagram-$s.png done If you want to try this with your own git repository, please make a backup first, as the script is only lightly tested! |
Mapping the merge conflict frontier
In my last article, I described how to define a "conflict frontier" for a failed merge and conceptually how to diagram it. In this article, I will describe an automated and efficient way to compute the conflict frontier using git. In my next article, I will show some examples of real-world merge diagrams.
Remember, a merge diagram summarizes the combinations of commits from two branches that can be merged successfully, and which of them conflict. The example used in the previous article looked like this:
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
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", and it contains the logical changes that were originally introduced by commits "0"-"3" on master plus those introduced by commits "A"-"C" on branch. When an incremental merge failed, the diagram shows an "x". The "conflict frontier" is the border between merges that are successful and those that result in conflicts.
This article describes an algorithm for computing the merge frontier efficiently.
Assumptions
In this article we make the following assumptions:
- If a merge can be done directly, then all of the incremental merges above and to the left of the merge can also be done successfully. For example, if we can merge "C" and "3" directly, then we assume that all of the merges "A1", "A2", "A3", "B1", "B2", "B3", "C1", and "C2" could also be done successfully. This is typically (though not always) the case in the real world.
- If a direct merge conflicts, then all of the incremental merges below and to the right of it would also conflict. For example, if a merge of "F" and "2" fails, we assume that the whole rectangle of incremental merges bounded by "F2", "F11", "I11", and "I2" would also conflict. Again, this is typically (though not always) the case in the real world.
- We use "git merge" to define whether a merge is successful. If the command completes without an error, then we assume that the merge is good. (For a more accurate determination of which merges are successful, one could also check whether the merged version builds and passes the project's automated tests.)
Bisection
Given the above assumptions, it is possible to locate the merge frontier in any line or column of the diagram via a process of bisection. For example, to find the merge frontier in row "E" of the diagram:
- Test merging "E" and "6" -> SUCCESS. Merge frontier must be to the right of this entry.
- Test merging "E" and "9" -> CONFLICT. Merge frontier must be to the left of this entry.
- Test merging "E" and "7" -> FAIL. Merge frontier must be between "E6" and "E7".
In the diagram, the bisection look like this:
o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 ← master | A | B | C | D | E E6 x x | F | G | H | I ↑ branch
Filling
Given the results of a bisection, assumptions 1 and 2 allow us to fill in big chunks of the merge diagram. In particular, since merge "E6" was successful, all of the merges in the rectangle above and to the left of "E6" are also successful. And since "E7" conflicts, all of the merges in the rectangle below and to the right of "E7" are also conflicts:
o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 ← master | | | | | | | A - A1 - A2 - A3 - A4 - A5 - A6 | | | | | | | B - B1 - B2 - B3 - B4 - B5 - B6 | | | | | | | C - C1 - C2 - C3 - C4 - C5 - C6 | | | | | | | D - D1 - D2 - D4 - D4 - D5 - D6 | | | | | | | E - E1 - E2 - E3 - E4 - E5 - E6 x x x x x | F x x x x x | G x x x x x | H x x x x x | I x x x x x ↑ branch
The combination of bisection and filling allows the merge frontier to be computed very efficiently.
The zig-zag method
There are many ways to map out the frontier using bisection and filling. The one that I use I call the zig-zag method, because it starts at the bottom-left and zig-zags up the frontier until it reaches the top-right. In pseudo-code, it is roughly:
i1 = 0 i2 = number of commits on branch while True: i1 = index of first failing merge in row i2-1 mark block above and to the left of (i1,i2) as "successful" if i1 == number of commits on master: break i2 = index of first failing merge in column i1 mark block below and to the right of (i1,i2) as "conflict" if i2 == 0: break
Whenever the "index of first failing merge" is needed for a row or a column, it is found by bisection. For our example, the progression looks like this (with the position (i1,i2) marked as *):
o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 ← master | | A - A1 | | B - B1 | | C - C1 | | D - D1 | | E - E1 | | F - F1 | | G - G1 | | H - H1 | | I - I1 * ↑ branch o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 ← master | | A - A1 | | B - B1 | | C - C1 | | D - D1 | | E - E1 | | F - F1 * 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 o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 ← master | | | | | | | A - A1 - A2 - A3 - A4 - A5 - A6 | | | | | | | B - B1 - B2 - B3 - B4 - B5 - B6 | | | | | | | C - C1 - C2 - C3 - C4 - C5 - C6 | | | | | | | D - D1 - D2 - D4 - D4 - D5 - D6 | | | | | | | E - E1 - E2 - E3 - E4 - E5 - E6 * | | 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 o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 ← master | | | | | | | A - A1 - A2 - A3 - A4 - A5 - A6 | | | | | | | B - B1 - B2 - B3 - B4 - B5 - B6 | | | | | | | C - C1 - C2 - C3 - C4 - C5 - C6 * 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 o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 ← master | | | | | | | | | | | | A - A1 - A2 - A3 - A4 - A5 - A6 - A7 - A8 | | | | | | | | | B - B1 - B2 - B3 - B4 - B5 - B6 - B7 - B8 * | | | | | | | 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 o - 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 ← master | | | | | | | | | | | | A - A1 - A2 - A3 - A4 - A5 - A6 - A7 - A8 | | | | | | | | | B - B1 - B2 - B3 - B4 - B5 - B6 - B7 - B8 * 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 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
Using this algorithm, the whole diagram can be computed by doing only O(B * lg max(M,N)) test merges, where B is the number of blocks in the resulting diagram and M and N are the number of commits on master and branch, respectively. In the worst case, B = min(M,N) and the algorithm scales like O(min(M,N) * lg max(M,N)).
I have written an example program, git-mergemate, that computes merge diagrams using the algorithm described here. To use it, put it in your $PATH, switch to your git project working directory (which must be clean), and type
git-mergemate diagram master...branch >diagram.ppm
The output is a PPM file in which successful merges are displayed as green pixels and conflicting merges are displayed as red pixels. Pixels representing merges that were actually tested are displayed as bright red/green; the other pixels are inferred using the assumptions above.
My next article will show some examples of real-world merge diagrams.
Some technical details
- Each of the bisect steps only needs to search the part of the row/column that hasn't already been filled in.
- If the merges are done using git, it is important to do them with git's "rerere" feature turned off. Otherwise the results of test merges are not deterministic because they depend on what information "rerere" has already gathered.
Subscribe to:
Posts (Atom)
