Re: [merge tracking] Handling cyclic merging

From: Folker Schamel <schamel23_at_spinor.com>
Date: 2007-12-04 23:33:48 CET

Folker Schamel wrote:
>
> To clarify my merge-tracking proposal more in detail:
>
> It seems to me that the important aspect is that mergeinfo
> should contain only entries from *direct* merges.
> In this way, the mergeinfo build a tree.
> (This merge history tree information is missing in the
> current mergeinfo scheme, which contains both direct
> *and* indirect merges.)
>
> def smart_merge(source, -r X:Y, target):
>
> def is_1_contained_in_tree_2(path1@r1, path2@r2):
> if path1@r1 == path2@r2:
> return True
> for each subpath@subr which is in mergeinfo of path2@r2,
> but not in mergeinfo of path2@(r2-1):
> if is_1_contained_in_tree_2(path1@r1, subpath@subr):
> return True
> return False
>
> def undo_existing_changes_1_in_2(path1@r1, path2@r2):
> if is_1_contained_in_tree_2(path1@r1, path2@r2):
> merge path1 -r r1:(r1-1) from target
> else:
> for each subpath@subr which is in mergeinfo of path1@r1,
> but not in mergeinfo of path1@(r1-1)
> in reverse(!) revision order:
> undo_existing_changes_1_in_2(subpath@subr, path2@r2)
>
> for i2 = LATEST_REV downto 1:
> for i1 = Y downto X+1:
> if mergeinfo of target does not contain source@i1:
> undo_existing_changes_1_in_2(source@i1, target@i2)
>
> for i1 = X+1 to Y:
> if mergeinfo of target does not contain source@i1:
> merge source -r i1-1:i1 into target
> add source@i1 to mergeinfo of target.
>
> This should handle both
> http://svn.haxx.se/dev/archive-2007-12/0134.shtml
> and
> http://svn.haxx.se/dev/archive-2007-11/1265.shtml
> correctly.
>
> This is a brute-force implementation, which of course could be optmized
> to work on revision ranges instead of individual revisions.
> But this is "only" an implementation detail.
>
> The above pseudo-code is just quickly written down
> and may be buggy, but I think you get the idea.

The above algorithm is also not perfect:
There is plenty room for further improvements for
avoiding conficts.
For example, you can avoid to unmerge and then merge
exactly the same revisions in reverse order,
which obviously helps avoiding conflicts.

However, the basic idea is the following:
Once you have all necessary information about the merge
history tree, then you can implement smarter merging
algorithms at any time later step by step,
while keeping this scheme and while being backwards compatible.
Therefore my advocation for changing the mergeinfo scheme
to include that tree information.

Cheers,
Folker

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Tue Dec 4 23:35:11 2007

This is an archived mail posted to the Subversion Dev mailing list.