[Svnmerge] Patch for non-reflected bidirectional merging support

[Archie Cobbs]

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.

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.

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).

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.

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.

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

-Archie

__________________________________________________________________________
Archie Cobbs      *        CTO, Awarix        *      http://www.awarix.com