[Svnmerge] Patch for non-reflected bidirectional merging support

[Raman Gupta]

Archie Cobbs wrote:
> Raman Gupta wrote:
> 
>> The second, and far more interesting, patch adds merge-point tracking.
> 
> 
> I think this is a good solution. However, before we "commit" to it
> I'd like to make sure that we've understood all possibilities.

Fair enough.

> I apologize for being only half-connected to the discussion due to
> being busy, but today have had a little time to think more about it.
> 
> Below are some random thoughts attempting to put a little theory
> behind the problem. Hopefully some of it makes sense..
> 
> Problem: avoid mergeing in "reflected" changes.
> 
> Question: what exactly is a "reflected" change?
> 
> First, divide up all commits into two types: "original" and "merged".
> "Original" commits are those in which svnmerge is not involved, i.e.,
> normal changes. "Merged" commits are "svnmerge" commits of merges.
> You can tell these because the "svnmerge-integrated" property changes
> (assuming you know what directory to look at).
> 
> Consider a "merged" commit: it changes the revision list for exactly one
> of the (possibly multiple) branches listed in the "svnmerge-integrated"
> property, and it does so by adding revision(s) to the list.
> 
> For each of those revisions added, you can identify *it* as "original"
> or "merged". In the latter case, you can then recurse...
> 
> Define the "history tree" of a revision as the tree of revisions
> formed by recursively following all merged revisions until all the
> leaves of the tree are "original" revisions: leaves in the tree are
> "original" revisions; interior nodes are "merged" revisions, and their
> children are the revisions that were merged in the "merged" revision.
> 
> First observation: a single svnmerge candidate revision may contain
> some changes which are "reflected" and some which are not. Consider
> this case:
> 
> target  rev     action
> 
> b1      1       normal change
> b2      2       merge b1:1
> b2      3       normal change
> b3      4       merge b2:2-3
> b1      5       merge b3:4
> 
> Look at r5. We merge in r4 from b3 -> b1, but r4 was a merge of r2 and r3
> from b2 -> b3, where r2 is a "merged" commit but r3 is "original". So
> r5 is only partially reflected.
> 
> Here's the history tree for r5:
> 
>      r5
>      |
>      r4
>     /  \
>    r2   r3
>   /
>  r1
> 
> Note that, relative to b1, r1 is reflected but r3 is not.
> 
> The "mixed" case an odd one, and probably one it's safe to punt on,
> i.e., treat is a non-reflected and let the user deal with any conflicts
> for the "reflected" changes therein.

Your analysis is interesting and seems to be correct. But, following on
your "odd" comment, I think that trying to do this for cyclical changes
between more than two branches is difficult, to say the least, and also
not something that would generally be done on a real project. At least I
can't think of any use cases for doing something like this, except
special isolated cases involving specific changes of limited scope. I
don't think we should worry about those because svnmerge is generally
useful only for branches involved with repeated merging.

Therefore, I think we can assume that we only need to support branches
being merged back to their direct ancestors and to their direct
children. So, in your example, b3 would first be merged back to b2 (its
direct ancestor), and then b2 would be merged back to b1 (its direct
ancestor), reducing the problem to a simple bi-directional one. b1 and
b3 would never be involved directly.

> So let's refine our goal to be: avoid merging revisions for which every
> leaf of the history tree was a change to the target branch itself. That
> is, avoid "100% reflected" revisions. This probably covers the majority
> of cases. It should cover all bidirectional cases, because you need at
> least three branches to get "mixed reflected" revisions (I think).

Agreed. I would limit the scope even further -- IMHO, I think if we just
handle the bidirectional cases thats enough because of what I was saying
above. I think the other use cases that require following the entire
history tree are infrequently used and can be supported with
bidirectional integration branches anyway.

> How do you tell what branch an "original" commit was applied to?
> You look at it's parent in the tree, which tells you which branch in
> the "svnmerge-integrated" property was changed (for the root of the
> tree, it's the branch you're merging from).
> 
> Next observation: by doing sufficient work, svnmerge can compute the
> history tree of any revision, today, without requiring dot files, double
> commits, or any other changes to the way it currently works. Then it's
> easy to identify and elide "100% reflected" revisions.

Interesting!

> To compute the history tree, you just implement the obvious recursive
> algorithm: to determine if a revision is "original" or "merged", you
> check whether it involved a change to the "svnmerge-integrated" property
> (the directory to check will be known). If so, then it's a "merged"
> revision and you recurse on the revisions that were added to the list.
>
> Next observation: when computing the history tree, we can prune our
> search at any "merged" revisions that came from the same branch
> we're currently targeting. In the example above, we'd stop at r2.
> This should help, especially in the bidirectional case where it will
> prevent us from going "around the loop" more than once.

If you agree with my assertion above that we only need to think about
bidirectional cases, then we can simplify this *significantly* and
remove the recursion.

> Does this analysis sound correct? Have I missed something?
> Does this algorithm sound like a viable approach?

I think the only downside is that it will be quite a lot slower than the
dot-files implementation because it has to check the remote
svnmerge-integrated property for every candidate revision, instead of
being able to get all of the merged revisions for exclusion in one nice
call (especially if you decide to keep the recursion). However,
personally I'd be willing to live with this performance loss in exchange
for the removal of the dot-files. Also, as a general UI design
principal, the impact of slow operations such as this can be reduced by
providing some sort of progress interface to the user, like

"Checking for reflected changes... 2/9" or similar.

That will be easier without the recursion too, because you will know
upfront how many revisions need to be checked.

Cheers,
Raman