*** UNDER CONSTRUCTION ***
Merge tracking functional specification. Describes Subversion 1.5.0, except where noted as unimplemented.
TODO: Describe how each requirement will actually function for Subversion. Remove redundancies.
Output is shown the same as pre-Merge Tracking, except for:
Copy and move operations handle two types of merge info:
svn:mergeinfo
property on the source path.Copy/move operations which contact the repository include:
These operations always propogate both explicit and implicit merge info. Other than the inclusion of merge info, operation is effectively the same as pre-Merge Tracking.
Pre-Merge Tracking, WC to WC operations occurred offline (e.g. with no repository access). This is a typical behavior of refactoring tools (e.g. IDEs like Eclipse), and is very useful when offline (e.g. on an airplane or subway, or at a cafe).
However, to propogate merge info during copy/move operations, access to both a path's comprehensive merge info and its history is necessary. To preserve offline operation, the Merge Tracking implementation supports two modes:
This behavior is comparable to the difference between svn
status and svn status -u.
While some state indicating delayed merge info retrieval and handling could instead be stored in WC to preserve offline operation, there are complications with this when subsequent uncommited revert operations should change the merge info (we'd have to store negative merge info in the WC).
Merge Tracking meta data is stored in housekeeping properties
(e.g. svn:mergeinfo).
While direct manipulation of housekeeping properties can be used to change merge info, commands to manipulate this information have been provided. Either style of operation supports adjustment of merge info when manual merges occur, and can also be used to fulfill block changes undesired for merge (later, this might be better-addressed by a separate housekeeping property).
merge --record-only adds (or subtracts, if a
reversed revision range is supplied) merge info for a path
without performing the actual merge.propedit/propset changes merge info
for a path.propdel removes mere info for a path.TODO: Describe how each will work (unimplemented, and not currently targeted for 1.5.0)
log and blame)There are two general schemes for solving the repeated merge problem. Subversion 1.5 uses the Most Recent Common Ancestor (MRCA) approach. If a later version of Subversion (e.g. 2.0) overhauls the Merge Tracking implementation, it'll likely use the Ancestry Set (AS) approach.
Either solution also supports the cherry picking, rollback, and property merging use cases. A merge preview which is lighter-weight than an uncommitted merge into a WC is not supported.
In this scheme, An optional set of merge sources in each
node-revision. When asked to do a merge with only one source (that
is, just svn merge URL, with no second argument), you
compute the most recent ancestor and do a three-way merge between the
common ancestor, the given URL, and the WC.
To compute the most recent ancestor, you chain off the immediate predecessors of each node-revision. The immediate predecessors are the direct predecessor (the most recent node-revision within the node) and the merge sources. An interleaved breadth-first search should find the most recent common ancestor.
In this scheme, you record the full ancestry set for each node-revision -- that is, the set of all changes which are accounted for in that node-revision. (How you store this ancestry set is unimportant; the point is, you need a reasonably efficient way of determining it when asked.) If you are asked to "svn merge URL", you apply the changes present in URL's ancestry but absent in WC's ancestry. Note that this is not a single three-way merge; you may have to apply a large number of disjoint changes to the WC.
For a longer description of this approach, see the "Merging and Ancestry" section of the original design doc.
Make 'hunks' of contextually-merged text sensitive to ancestry.
A high-resolution version of repeated merge. Rather than tracking whole changesets, we track the lineage of specific lines of code within a file. The basic idea is that when re-merging a particular hunk of code, the contextual-merging process is aware that certain lines of code already represent the merging of particular lines of development. Jack Repenning has a great example of this from ClearCase (see ASCII diagram below).
See the variance
adjusted patching document for an extended discussion of how to
implement this by composing diffs; see svn_diff_diff4() for an implementation of same. We
may be closer to ancestry-sensitive merging than we think.
Here's an example demonstrating how individual lines of code can be tracked. In this diagram, we're drawing the lineage of a single file, with time flowing downwards. The file begins life with three lines of text, "1\n2\n\3\n". The file then splits into two lines of development.
1
2
3
/ \
/ \
/ \
one 1
two 2.5
three 3
| \ |
| \ |
| \ |
| \ |
| \ one ## This node is a human's
| two-point-five ## merge of two sides.
| three
| |
| |
| |
one one
Two two-point-five
three newline
\ three
\ |
\ |
\ |
\ |
\ |
\ |
\ |
\ |
one ## This node is a human's
Two-point-five ## merge of the changes
newline ## since the last merge.
three
It's the second merge that's important here.
In a system like Subversion, the second merge of the left branch to the right will fail miserably: the whole file's contents will be placed within conflict markers. That's because it's trying to dumbly apply a patch that changes "1\n2\n3" to "one\nTwo\nthree", and the target file has no matching lines at all.
A smarter system (like Clearcase) would remember that the previous merge had happened, and specifically notice that the lines "one" and "three" are the results of that previous merge. Therefore, it would ask the human only to deal with the "Two" versus "two-point-five" conflict; the earlier changes ("1\n2\n3" to "one\ntwo\nthree") would already be accounted for.
AS allows you to merge changes from a branch out of order, without doing any bookkeeping. MRCA requires you to merge changes from a branch in order.
MRCA is simpler to implement, since it results in a three-way merge (which is well-understood by Subversion). However, it may not handle all edge cases. For instance, it may break down faster if the merging topology is not hierarchical.
MRCA may be easier for users to understand, even though AS is probably simpler to a mathematician.
Consistency with other modern version controls systems is desirable.
If a user asks to merge a directory, should we apply MRCA or AS to each subdirectory and file to determine what ancestor(s) to use? Or should we apply MRCA or AS just once, to the directory itself? The latter approach seems simpler and more efficient, but will break down quickly if the user wants to merge subdirectories of a branch in advance of merging in the whole thing.
Merging inevitably produces conflicts which cannot be resolved by an algorithm alone. In such a case, human intervention is required to resolve the conflicts. The merge algorithm used by Subversion's Merge Tracking implementation makes this problem worse, since it breaks a requested merge range into several merges to avoid repeating merges which have already been applied to a merge target or its children.
To help alleviate the pain of conflict resolution, a merge conflict resolution callback can be employed by Subversion clients (unimplemented). This callback is invoked whenever merge conflicts are encountered, and can takes steps like launching a graphical merge tool (for interactive conflict resolution), or following a pre-specified directive like "always use the version from my merge source". This last implementation can be used to support the SCM automated merge use case.
The command-line client supplies a default merge conflict resolution callback which will behavior much like svk, when in interactive mode displaying some context for each conflict and prompting for how to resolve it, or when in non-interactive mode, taking directives beforehand (unimplemented).
Related discussion from the dev@ mailing list can be found here:
No explicit facility is provided for distribution of conflict resolution. To support this use case, developers can co-ordinate with each other to resolve merge conflicts on portions of a tree, and trade patches.