Re: Symmetric Merge -- status

On Fri, May 25, 2012 at 12:08 PM, Julian Foad
<julianfoad_at_btopenworld.com> wrote:
> Hi, all.
>
> I want to update you all on the "symmetric merge" [1] status and my plans,
> and invite your thoughts and any assistance you can give.
>
> I'll be presenting this subject at Elego's SvnDay [2] and at WANdisco events
> in October, but the presentation will be aimed at users and so will
> concentrate on how the end result is better for the user and won't say much
> about the details I'm talking about below.
>
>
> GRAND PLAN
>
> Two main phases.
>
>   Phase 1 (now).
>     Implement in terms of "sync" and "reintegrate".  Accept their
> limitations; that is:
>     - Any "simple" [3] merge will work fine (in either direction).
>     - A non-"simple" merge can be performed only in the same direction as
> the previous merge.
>     - Make Subversion use "symmetric merge" automatically for any merge
> request that we currently handle as a "sync" -- that is when:
>       - it's a forward merge
>       - no revision range is given (at least, no starting revision; an
> ending revision is acceptable)
>       - "--reintegrate" is not specified
>     - For testing purposes, we also make Subversion use the "symmetric
> merge" whenever the test suite requests a "reintegrate".  I don't see any
> reason to make it do that for users; indeed I think it would be bad to make
> this special option start doing things it didn't do before.
>
>   Phase 2 ("later"):
>     Rewrite more of the merge code to alleviate limitations -- to be able to
> skip cherry-picks, support mixed-rev etc. when merging in either direction.
>     - Make the implementation more symmetric.  This involves pretty deep
> changes in the merge code, so much so that I think this task would best be
> combined with a significant revision of the internal merge data structures
> (svn_mergeinfo_t and so on).  Maybe even combined with a revision of the way
> mergeinfo is stored.
>
> Concentrate on getting phase 1 complete and releasable.  I *think* it is
> nearly done.  (See TESTING, below.)  The implementation mimics "sync" or
> "reintegrate" depending on where it finds the most recent base, according to
> the rule that "sync" should be used when merging again in the same direction
> as last time, and "reintegrate" when merging in the opposite direction.  It
> doesn't matter that this implementation has all the limitations of the
> current "reintegrate" merge when changing direction, because that's already
> as good as 1.7 for all 1.7-supported cases AFAIK.  The benefit of it just
> Doing The Right Thing for simple merges, enabling repeated to-and-fro
> merging, seems huge.
>
> Phase 2 is much lower priority and much more a SMOP, with less impact on
> users (documentation etc.).  Phase 2 will bring flexibility that isn't of
> great importance to users AFAIK, since cherry-picking and subtree merging is
> most often used alone -- on a divergent branch (that's not going to be
> reintegrated) -- and rarely on a convergent branch (which is going to be
> reintegrated, so to-and-fro merging is likely).  And phase 1 already enables
> cherry-picks etc. to be accomodated to some extent.
>
>
> CONCERNS
>
> The main concerns a couple of months ago were that it wasn't handling
> subtrees and mixed-rev WCs and so on.  I believe now that it does (in the
> "sync" direction -- that is, whenever merging in the same direction as the
> previous merge).  There are a few tests failing (see below) but from a
> design and implementation point of view I am confident that it should
> support these cases and that these failures must be due to relatively minor
> issues.
>
>
> TESTING
>
> Current test suite:
>
> The following tests fail when merge-cmd.c is patched to call "symmetric
> merge" for sync and reintegrate merges [4]:
> FAIL:  merge_reintegrate_tests.py 10: merge --reintegrate with subtree
> mergeinfo

Let's focus on what this test is doing at a high level and ignore some
unnecessary details. Basically the test case does the following:

1) branch 'A_at_1' is copied to 'A_COPY'

2) changes are made on both 'A' and 'A_COPY'

3) Sync merge ^/A to 'A_COPY', bringing the latter up to r12

4) Do a reverse-subtree-cherry-pick merge: svn merge ^/A/D -c-8 A_COPY/D
This "undoes" part of the sync merge in step 3 creates new subtree
mergeinfo on A_COPY to represent this reversal (Omitting irrelevant
mergeinfo actually found in the test) :

  Properties on 'A_COPY':
    svn:mergeinfo
      /A:2-12
  Properties on 'A_COPY\D':
    svn:mergeinfo
      /A/D:2-7,9-12

5) The test then tries to reintegrate ^/A_COPY to A. A
1.7/Old-style/Non-symmetric merge notices that the mergeinfo "gap"
created by the reverse merge, '/A/D:8' represents an operative change,

  trunk_at_1342725>svn diff -c8
  Index: A/D/H/omega
  ===================================================================
  --- A/D/H/omega (revision 7)
  +++ A/D/H/omega (revision 8)
  @@ -1 +1 @@
  -This is the file 'omega'.
  +New content
  \ No newline at end of file

and then fails with this error:

trunk_at_1342725>svn merge ^^/A_COPY A --reintegrate
..\..\..\subversion\svn\merge-cmd.c:382: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10746: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10715: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10715: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10653: (apr_err=195016)
svn: E195016: Reintegrate can only be used if revisions 2 through 15
were previously merged from
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_reintegrate_tests-10/A
to the reintegrate source, but this is not the case:
  A_COPY/D
    Missing ranges: /A/D:8

The symmetric merge on the other hand, blissfully ignores this subtree
mergeinfo and lets the "reintegrate" succeed...

trunk_at_1342725>svn merge ^^/A_COPY A --reintegrate --symmetric
DBG: merge.c:11461: base on source:
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_reintegrate_tests-10/A_at_1
DBG: merge.c:11462: base on target:
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_reintegrate_tests-10/A_at_12
DBG: merge.c:11567: yca
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_reintegrate_tests-10/A_at_1
DBG: merge.c:11568: base
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_reintegrate_tests-10/A_at_12
DBG: merge.c:11570: mid
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_reintegrate_tests-10/A_at_12
DBG: merge.c:11571: right
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_reintegrate_tests-10/A_COPY_at_15
--- Merging differences between repository URLs into 'A':
U A\B\E\alpha
UU A\mu
U A\D\H\omega
 U A\D
--- Recording mergeinfo for merge between repository URLs into 'A':
 U A
 U A\D
 G A\mu

...which means that r8 is reverse merged from 'A' now too (which is
quite likely *not* what the user expected):

trunk_at_1342725>svn diff A\D\H\omega
Index: A/D/H/omega
===================================================================
--- A/D/H/omega (revision 14)
+++ A/D/H/omega (working copy)
@@ -1 +1 @@
-New content
\ No newline at end of file
+This is the file 'omega'.

This isn't surprising since AFAICT
merge.c:svn_client__find_symmetric_merge and
merge.c:svn_client__do_symmetric_merge completely ignore subtree
mergeinfo on the source. The "old" non-symmetric code path checks
that the entire mergeinfo catalog on the source (i.e. both the
explicit mergeinfo on the source and the source's subtree mergeinfo)
represent a fully synced source (see merge.c:find_unsynced_ranges).

If this test's particular use-case strikes you as too contrived, see
the attached patch which adds a new merge_symmetric test that
demonstrates a more (IMO) plausible use-case (one that uses only
forward sync merges).

> FAIL:  merge_tests.py 88: subtree merges dont cause spurious conflicts

This failure is similar to merge_reintegrate_tests.py 10 in that
subtree mergeinfo is ignored by the symmetric merge and only the
mergeinfo on the target itself is considered.

Briefly, right before the failure we have this mergeinfo on the branch target:

trunk_at_1343721>svn pl -vR
Properties on 'A_COPY':
  svn:mergeinfo
    /A:2-7
Properties on 'A_COPY\D\H\psi':
  svn:mergeinfo
    /A/D/H/psi:2,4-7

If we, as symmetric merge does, consider only the mergeinfo on the
root of the merge target, then the only operative revision eligible
for merging is r8:

  trunk_at_1343721>svn mergeinfo --show-revs eligible ^^/A A_COPY
  r8

But if we consider subtree mergeinfo then we see that r3 is also
eligible for a subtree (a file) of the target:

  trunk_at_1343721>svn mergeinfo --show-revs eligible ^^/A A_COPY -R
  r3*
  r8

  trunk_at_1343721>svn mergeinfo --show-revs eligible ^^/A/D/H/psi A_COPY/D/H/psi
  r3

The old merge code takes notice of the subtree mergeinfo and drives
the editor such that r3 is applied only to A_COPY/D/H/psi:

trunk_at_1343721>svn merge ^^/A A_COPY
--- Merging r3 into 'A_COPY\D\H\psi':
U A_COPY\D\H\psi
--- Merging r8 through r9 into 'A_COPY':
U A_COPY\D\G\rho
--- Recording mergeinfo for merge of r3 through r9 into 'A_COPY':
 U A_COPY
--- Recording mergeinfo for merge of r3 through r9 into 'A_COPY\D\H\psi':
 U A_COPY\D\H\psi
--- Eliding mergeinfo from 'A_COPY\D\H\psi':
 U A_COPY\D\H\psi

trunk_at_1343721>svn st
 M A_COPY
M A_COPY\D\G\rho
MM A_COPY\D\H\psi

trunk_at_1343721>svn pl -vR
Properties on 'A_COPY':
  svn:mergeinfo
    /A:2-9

trunk_at_1343721>svn revert -R . -q

The symmetric merge, ignoring the subtree mergeinfo on A_COPY/D/H/psi,
thinks only r8 needs to be merged:

trunk_at_1343721>svn merge ^^/A A_COPY --symmetric
DBG: merge.c:11461: base on source:
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88/A_at_7
DBG: merge.c:11462: base on target:
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88/A_at_1
DBG: merge.c:11567: yca
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88/A_at_1
DBG: merge.c:11568: base
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88/A_at_7
DBG: merge.c:11571: right
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88/A_at_9
--- Merging r8 through r9 into 'A_COPY':
U A_COPY\D\G\rho
--- Recording mergeinfo for merge of r8 through r9 into 'A_COPY':
 U A_COPY

trunk_at_1343721>svn st
 M A_COPY
M A_COPY\D\G\rho

trunk_at_1343721>svn pl -vR
Properties on 'A_COPY':
  svn:mergeinfo
    /A:2-9
Properties on 'A_COPY\D\H\psi':
  svn:mergeinfo
    /A/D/H/psi:2,4-7

So we can sync all day with the symmetric code path and r3 will never
get merged.
C:\SVN\src-trunk\Debug\subversion\tests\cmdline\svn-test-work\working_copies\merge_tests-88>

> FAIL:  merge_tests.py 89: target and subtrees need nonintersecting revs

I won't go into any details here, this is exactly the same problem as
merge_tests.py 89.

> FAIL: merge_tests.py 78: dont merge revs into a subtree that predate it

Similar problem here to the other two merge tests, except that the
problem is obscured a bit by the fact that:

1) The target itself has no mergeinfo, only the subtree does.
2) The resulting working copy state is identical regardless of whether
the subtree mergeinfo is considered, so the test only fails because
the notification headers differ:

Symmetric Merge:

trunk_at_1343721>svn st
MM H_COPY\nu

trunk_at_1343721>svn pl -vR
Properties on 'H_COPY\nu':
  svn:mergeinfo
    /A/D/H/nu:7

trunk_at_1343721>svn merge ^^/A/D/H H_COPY --force --symmetric
DBG: merge.c:11461: base on source:
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-78/A/D/H_at_5
DBG: merge.c:11462: base on target:
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-78/A/D/H_at_5
DBG: merge.c:11567: yca
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-78/A/D/H_at_5
DBG: merge.c:11568: base
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-78/A/D/H_at_5
DBG: merge.c:11571: right
file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-78/A/D/H_at_9
--- Merging r7 through r9 into 'H_COPY':
U H_COPY\psi
D H_COPY\nu
--- Recording mergeinfo for merge of r6 through r9 into 'H_COPY':
 U H_COPY

trunk_at_1343721>svn st
 M H_COPY
D H_COPY\nu
M H_COPY\psi

trunk_at_1343721>svn pl -vR
Properties on 'H_COPY':
  svn:mergeinfo
    /A/D/H:6-9

trunk_at_1343721>svn revert -R .
Reverted 'H_COPY'
Reverted 'H_COPY\psi'
Reverted 'H_COPY\nu'

trunk_at_1343721>cd ..

trunk_at_1343721>cd merge_tests-78

Old merge:

trunk_at_1343721>svn st
MM H_COPY\nu

trunk_at_1343721>svn pl -vR
Properties on 'H_COPY\nu':
  svn:mergeinfo
    /A/D/H/nu:7

trunk_at_1343721>svn merge ^^/A/D/H H_COPY --force
--- Merging r6 through r9 into 'H_COPY':
                 ^^^^^
       r6 rather than r7, everything else is the same.
U H_COPY\psi
D H_COPY\nu
--- Recording mergeinfo for merge of r6 through r9 into 'H_COPY':
 U H_COPY

trunk_at_1343721>svn st
 M H_COPY
D H_COPY\nu
M H_COPY\psi

trunk_at_1343721>svn pl -vR
Properties on 'H_COPY':
  svn:mergeinfo
    /A/D/H:6-9

> Clearly there's something up with subtree merges,

Let's jump back to the simple example in merge_tests.py 88 to take a
closer look at what's going on. Recall prior to the merge we have
this mergeinfo on our merge target:

trunk_at_1343721>svn pl -vR
Properties on 'A_COPY':
  svn:mergeinfo
    /A:2-7
Properties on 'A_COPY\D\H\psi':
  svn:mergeinfo
    /A/D/H/psi:2,4-7

An old-style merge feeds merge.c:do_merge() a single merge_source_t:

  source
    loc1
      repos_root_url
"file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88"
      repos_uuid "3c093481-932f-b94f-a0fe-b71a763dd933"
      rev 1
      url "file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88/A"
    loc2
      repos_root_url
"file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88"
      repos_uuid "3c093481-932f-b94f-a0fe-b71a763dd933"
      rev 9
      url "file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88/A"
    ancestral 1

Your symmetric merge on the other hand passes this single merge_source_t:

  source
    loc1
      repos_root_url
"file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88"
      repos_uuid "3c093481-932f-b94f-a0fe-b71a763dd933"
      rev 7
      url "file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88/A"
    loc2
      repos_root_url
"file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88"
      repos_uuid "3c093481-932f-b94f-a0fe-b71a763dd933"
      rev 9
      url "file:///C:/SVN/src-trunk/Debug/subversion/tests/cmdline/svn-test-work/repositories/merge_tests-88/A"
    ancestral 1

Notice that source->loc1->rev is r1 in the first case and r7 in the
second (symmetric) case. Because the symmetric merge doesn't consider
r1-6, all the subtree mergeinfo logic that exists within do_merge and
it's helpers never even has the chance to consider /A:1-6 as part of
the requested merge.

So what to do? Maybe make merge.c:find_symmetric_merge() retrieve the
subtree mergeinfo for s_t->target->abspath, not just the
explicit/inherited mergeinfo (i.e. call
svn_client__get_wc_or_repos_mergeinfo_catalog rather than
svn_client__get_wc_or_repos_mergeinfo). It could then evaluate the
totality of mergeinfo on/under the target when determining "the latest
revision of A synced to B and the latest revision of B synced to A."
Yes, I'm doing a lot of hand-waving here :-)

-- 
Paul T. Burba
CollabNet, Inc. -- www.collab.net -- Enterprise Cloud Development
Skype: ptburba
> but, as I said above, I
> have reason to believe that it's not fundamentally broken or unsupported.
>
> New tests:
>
> I've started "merge_symmetric_tests.py".
>
> Are any new tests required to ensure existing scenarios aren't broken, that
> may not be tested yet?
>
>   - The "keep-alive dance".  For completeness, we should check how that will
> behave, as we can assume some people will have adopted practices that
> incorporate it.  I do NOT think we should continue to support that
> work-around: if it continues to behave as now, that's fine, and if its
> behaviour changes, I expect to be able to claim that as an intentional
> behaviour change for the better.  That is, to be plain, if anyone's relying
> on that, they may need to change their practice.
>
>   - The tests I have at the moment are pretty small cases.  It would be good
> to create a test that exercises a series of much bigger merges.
>
>   - Any other scenario?
>
>
> PERFORMANCE
>
>   - Performance (in terms of network traffic, in particular).  After a
> series of (same direction or to-and-fro) merges, is the cost of the
> base-finding algorithm proportional to time since the YCA of the branches
> (i.e., ever increasing), or only proportional to time since last merge?
>
>   - Any other performance concern?
>
>
> Please let me know any thoughts you have.  And if you might be able to take
> on the investigation of one of the test failures, or writing a new test
> (whether pseudo-code or actual code), or checking the performance, that
> would be awesome.
>
> - Julian
>
>
> [1] <http://wiki.apache.org/subversion/SymmetricMerge>
> [2] <http://www.elego.de/svnday2012>
> [3] Define a "simple" merge as one that does not find any subtree merges,
> cherry picks, mixed-rev/switched/sparse WC.
> [4] Attached patch, "use-symmetric-merge-1.patch", makes all (?) sync and
> reint merge requests use the 'symmetric' code.