Merge symmetry (was: Tree Conflicts with Subversion 1.7)

[Andreas Krey <a....@gmx.de>]

On Fri, 19 Aug 2011 13:51:40 +0000, Stein Somers wrote:

> Now I realize merges are always asymmetric.

Actually, merging is a symmetric operation. The tree (and copyfrom
info) resulting from a merge should be the same independent of in
which direction the merge is performed. In svn the metadata just looks
completely different depending on the direction of the merge. (It also
is different due to the necessity of --reintegrate.)

Andreas

-- 
"Totally trivial. Famous last words."
From: Linus Torvalds <torvalds@*.org>
Date: Fri, 22 Jan 2010 07:29:21 -0800

Re: Merge symmetry (was: Tree Conflicts with Subversion 1.7)

[Andreas Krey <a....@gmx.de>]

On Mon, 22 Aug 2011 14:36:36 +0000, Stefan Sperling wrote:
...
> In Subversion, a merge is the computation of a delta between two
> arbitary trees, and the application of this delta to some other
> arbitrary tree.

To keep the (vector) addition analogy, you are measuring the difference
from A to B and move C in this direction. Which yields the same as
measuring from A to C and move B in *that* direction. You end up in the
same point. Just once B ends up there, and once C.

Anyway, while that is what you tell, and probably do for directories,
you can't get around using a version of the (symmetrical) diff3 to merge
file contents; that is the only way to sanely apply the delta. An actual
delta (patch) wouldn't generally be applicable to the target file.

> The merge target is *completely independent* of the merge delta.
> There is nothing, in the core algorithm, that would know about stuff
> like merge points and the like.

No, that comes into play when selecting the two revisions and paths that
you need to compute the delta to apply.

> You seem to be basing your mental
> model of merge on tools like git or hg. And that is a very good model.
> But it is very different from what Subversion is doing.

Unfortunately it is not that different from what I expected when
subversion was said to get proper merge support. (I was pampered
by cvsnt, which (once) could do bidirectional merges.)

> There is no merge DAG in Subversion.
> The closest equivalent to a merge DAG is svn:mergeinfo, but it
> doesn't implement a DAG -- it implements a filter that prevents
> the same revisions from being merged twice. That's all.

And unfortunately, it is so simplistic that you need to prod it with
--reintegrate the first (and last) time you merge in the other direction.
(Or it seems so.)

> It is really quite simple at the design level. The implementation
> is not simple because it handles a lot of additional quirks that
> are not reflected in this short and abstract description of what
> Subversion is doing.

Yes, recorded cherrypicking, not to mention all the rename handling.

...
> Let me quote the relevant part of the post I linked to:
...
> Is that clear enough? If not, please ask.

It's not quite. But it seems I need to wade through what actually happens
with the mergeinfo to understand why a backmerge can't deduce the proper
action without --reintegrate, and why the merge info then needs to be
borken for the branch. (Which may be partly simply because you can't
modify the branch's mergeinfo to mark the merge revision on the trunk
as already merged.)

Andreas

-- 
"Totally trivial. Famous last words."
From: Linus Torvalds <torvalds@*.org>
Date: Fri, 22 Jan 2010 07:29:21 -0800

Re: Merge symmetry (was: Tree Conflicts with Subversion 1.7)

[Stefan Sperling <st...@elego.de>]

On Mon, Aug 22, 2011 at 01:49:45PM +0200, Andreas Krey wrote:
> On Mon, 22 Aug 2011 12:38:40 +0000, Stefan Sperling wrote:
> > On Fri, Aug 19, 2011 at 04:15:38PM +0200, Andreas Krey wrote:
> ...
> > > Actually, merging is a symmetric operation. The tree (and copyfrom
> > > info) resulting from a merge should be the same independent of in
> > > which direction the merge is performed.
> > 
> > I agree that symmetry is a nice-to-have property of a merge algorithm.
> 
> I actually think it is essential.
> 
> > But I would be totally happy with asymmetric results, as long as either
> > result is well-defined and repeatable.  I don't see why the behaviour
> > of a merge algorithm must be symmetric.
> 
> Because a merge computes the addition of two changesets/diffs/however you
> name that: The delta from branch point (or last merge point) to trunk,
> and to branch head. I see no reason why the outcome should depend on
> which side I choose as the base of the merge: addition is commutative.

Because that's not how Subversion works.

In Subversion, a merge is the computation of a delta between two
arbitary trees, and the application of this delta to some other
arbitrary tree.

The merge target is *completely independent* of the merge delta.
There is nothing, in the core algorithm, that would know about stuff
like merge points and the like. You seem to be basing your mental
model of merge on tools like git or hg. And that is a very good model.
But it is very different from what Subversion is doing.

There is no merge DAG in Subversion.
The closest equivalent to a merge DAG is svn:mergeinfo, but it
doesn't implement a DAG -- it implements a filter that prevents
the same revisions from being merged twice. That's all.
It is really quite simple at the design level. The implementation
is not simple because it handles a lot of additional quirks that
are not reflected in this short and abstract description of what
Subversion is doing.
 
> > Sounds like you are conflating the UI with the underlying design.
> 
> No, I meant that besides the symmetry issue svn the mergeinfo actually
> encode different information depending on the direction of the merge.

Yes, that's true.

> > --reintegrate is a UI issue and has nothing to do with symmetry
> > or correctness.
> 
> I still don't quite understand why exactly --reintegrate is necessary.
> 
> Is it just because 'svn merge ^/branch' once meant 'take all changes of
> branch since the branch point and merge them into trunk', and it shall
> still mean that so we need --reintegrate to look closer onto the merge
> info to use the source of the last sync merge instead of the branch
> point as merge base? (But then we would need a 'merge --sync' as well.)
> 
> If it's not that, I don't see how the necessity of --reintegrate is an
> UI issue and not a result of a suboptimal mergeinfo design, along with
> the deadness of a branch after reintegration.

Let me quote the relevant part of the post I linked to:

[[[
Essentially, all merges in Subversion are 2-URL merges.
svn merge generates some delta and applies that to a working copy.
There is no other way, right now, that a merge could work.

A two-URL merge needs the following parameters:

  PATH1, REV1 (left side of the delta)
  PATH2, REV2 (right side of the delta)
  TARGET (working copy of some PATH3, up-to-date enough for commit)

The reintegrate merge automatically fills in all required parameters 
expect PATH2, and we get:

  PATH1 = trunk, REV1 = rX
  PATH2 = feature, REV2 = HEAD
  TARGET = working copy of trunk (generally speaking @HEAD)

A sync merge can fill in the all parameters as well, except PATH2.
However, it needs to do so in a different way. With a sync merge
PATH1 and PATH2 are the same so the delta between trunk@REV1 and
trunk@REV2 is merged into a working copy of the feature branch
In case of reintegrate PATH1 and PATH2 are not the same!

So svn merge needs the special --reintegrate option because just
'svn merge ^/branch' would be ambiguous.
]]]

Is that clear enough? If not, please ask.

Re: Merge symmetry (was: Tree Conflicts with Subversion 1.7)

[Andreas Krey <a....@gmx.de>]

On Mon, 22 Aug 2011 12:38:40 +0000, Stefan Sperling wrote:
> On Fri, Aug 19, 2011 at 04:15:38PM +0200, Andreas Krey wrote:
...
> > Actually, merging is a symmetric operation. The tree (and copyfrom
> > info) resulting from a merge should be the same independent of in
> > which direction the merge is performed.
> 
> I agree that symmetry is a nice-to-have property of a merge algorithm.

I actually think it is essential.

> But I would be totally happy with asymmetric results, as long as either
> result is well-defined and repeatable.  I don't see why the behaviour
> of a merge algorithm must be symmetric.

Because a merge computes the addition of two changesets/diffs/however you
name that: The delta from branch point (or last merge point) to trunk,
and to branch head. I see no reason why the outcome should depend on
which side I choose as the base of the merge: addition is commutative.

Although the 'addition' part may be seen as wordplay, I'd like to see
a case where a merge could reasonably not be symmetric (barring cases
with conflicts, where the conflict presentation usually is unsymmetric).

> > In svn the metadata just looks
> > completely different depending on the direction of the merge. (It also
> > is different due to the necessity of --reintegrate.)
> 
> Sounds like you are conflating the UI with the underlying design.

No, I meant that besides the symmetry issue svn the mergeinfo actually
encode different information depending on the direction of the merge.

> --reintegrate is a UI issue and has nothing to do with symmetry
> or correctness.

I still don't quite understand why exactly --reintegrate is necessary.

Is it just because 'svn merge ^/branch' once meant 'take all changes of
branch since the branch point and merge them into trunk', and it shall
still mean that so we need --reintegrate to look closer onto the merge
info to use the source of the last sync merge instead of the branch
point as merge base? (But then we would need a 'merge --sync' as well.)

If it's not that, I don't see how the necessity of --reintegrate is an
UI issue and not a result of a suboptimal mergeinfo design, along with
the deadness of a branch after reintegration.

Andreas

-- 
"Totally trivial. Famous last words."
From: Linus Torvalds <torvalds@*.org>
Date: Fri, 22 Jan 2010 07:29:21 -0800

Re: Merge symmetry (was: Tree Conflicts with Subversion 1.7)

[Stefan Sperling <st...@elego.de>]

On Fri, Aug 19, 2011 at 04:15:38PM +0200, Andreas Krey wrote:
> On Fri, 19 Aug 2011 13:51:40 +0000, Stein Somers wrote:
> 
> > Now I realize merges are always asymmetric.
> 
> Actually, merging is a symmetric operation. The tree (and copyfrom
> info) resulting from a merge should be the same independent of in
> which direction the merge is performed.

I agree that symmetry is a nice-to-have property of a merge algorithm.

But I would be totally happy with asymmetric results, as long as either
result is well-defined and repeatable.  I don't see why the behaviour
of a merge algorithm must be symmetric.

> In svn the metadata just looks
> completely different depending on the direction of the merge. (It also
> is different due to the necessity of --reintegrate.)

Sounds like you are conflating the UI with the underlying design.
--reintegrate is a UI issue and has nothing to do with symmetry
or correctness.
See http://mail-archives.apache.org/mod_mbox/subversion-dev/201107.mbox/%3C20110720124721.GA7557@ted.stsp.name%3E