Fixing merge - Subtree, Cyclic, and Tree Change cases

[Paul Burba]

http://blogs.collab.net/subversion/2008/07/subversion-merg/
I found the article to be a good overview of the issues.  I think that we
need help from Mark.   On the other hand, I have seen that Mark sometimes
makes discouraging comments.   My work is apparently “hand wavey” and
“proprietary”.   I’m used to this treatment because I have 25 developers who
work for me who often think that I am full of crap.  However, it might have
a discouraging effect on other contributors.  For example, you can see in
this great ticket thread -
http://subversion.tigris.org/issues/show_bug.cgi?id=2897 - he states "I do
not think it is possible in this design....I think we need to accept the
limitations of the current design and work towards doing the best we can
within that design”  Apparently that was enough to kill progress.   I think
we should keep a more open mind going forward.
I’m going to make some claims that some problems have “straightforward”
solutions.  That doesn’t mean they are simple solutions.  Handling all of
the merge cases is going to be hard.  However, they are straightforward in
the sense that we can discuss the strategy at the high level used in Mark’s
article.
Let’s consider three issues:  Subtree merginfo, cyclic merge, and tree
change operations
SUBTREE MERGINFO
 Mark notes that reintegrate does not work if you have subtree merginfo.
 The subtrees potentially make the top-level  mergeinfo inaccurate.

Hi Andy,

The blog you reference is three years old. A lot has changed since
then. You might want to take a look at
https://svn.apache.org/repos/asf/subversion/branches/1.7.x/CHANGES for
the items related to merging.

So,
basically everyone that has looked at merge problems in the past four years,
including Mark, has tried to get rid of subtree merginfo.

On that note: As far back as 1.5.5 (12/2008) reintegrate merges
tolerated subtree mergeinfo if all previous sync merges occurred at
the root of the branch. The forthcoming 1.7 release supports
reintegrate merges even if some of the sync merges were done at the
subtree level, as long as the branch is effectively synced -- see this
issue for more info:
http://subversion.tigris.org/issues/show_bug.cgi?id=3577

This is why one of my first requests on your earlier thread was for
the *specific* use-cases where the current merge-tracking
implementation doesn't work (and preferably some test patches for
these use cases).

It’s amazing that
Subversion still tries to support this feature.  It can’t be supported in
NewMerge.

To clarify, when you say "This feature" you mean what?

A) The ability to do subtree merges at all

B) Recording mergeinfo describing subtree merges (i.e. subtree
merges are still allowed, but not tracked).

C) Other

In the following sections, we will also see that the merginfo data is too
sparse, and we need to replace it with something bigger and more extensible.

Sidebar: You might want to use another term besides "sparse" when
talking about mergeinfo granularity. We typically use "sparse" to
refer to the depth of a working copy (e.g. 'svn co %URL% wc --depth
immediates wc-path) or the operative depth of an operation (e.g. 'svn
propget svn:mergeinfo %URL% --depth empty'). Sparse merges and sparse
merge targets can both result in subtree mergeinfo, so there is the
potential for some confusion for anybody following this casually.

CYCLIC MERGE
The case where we merge back and forth between a development or deployment
branch, and trunk, is the base case for merge.  It should be supported.
Subversion only supports it with special instructions.  This is the “cyclic
merge” problem.
It seems that we have two basic ways to do a merge.  We can grab all of the
changes that we are trying to merge in one big diff between the branch we
are merging from and the branch we are merging into - the reintegrate merge
as described in Mark’s article.  Or, we can sequentially apply or “replay”
each of the changes that we want to merge into our working copy - the
“recursive” strategy that is the default for git.

If each of these sequential "replays" is a separate editor drive (see
the svn_delta_editor_t in
https://svn.apache.org/repos/asf/subversion/trunk/subversion/include/svn_diff.h)
you might need to consider the impact of performance for merges over a
WAN. If a single editor drive turns into multiple editor drives it
will certainly be slower. How much slower obviously depends on a lot
of factors, but it is something to keep in mind since this isn't git
and we don't have the entire repository history locally available.

It seems to me that the “one big diff” and the replay strategy are closely
related.  When you are replaying, you grab all of the changes in any
sequence of revisions that doesn’t include a merge as one big diff.  So, the
current “one big diff” strategy is a special case of the replay strategy
that applies when there are no intermediate merges from other branches or
cherrypicks.
But wait!  According to this article, we can’t use the replay strategy
because we are missing part of the replay.  We lose information that was
used to resolve a merge when composing merge commits.  If we had that
information, we could replay individual merges, and handle a higher
percentage of the cyclic merge cases.
This problem seems to have a straightforward solution.  When we commit the
merge, we can stuff the changeset that represents the difference between the
merge, and the commit, into the merge_history.  We just need an extensible
merge_history format to hold it.
It’s totally not clear to me why you need to say “reintegrate” when you
merge to trunk,

You don't need to; reintegrate is simply a shortcut for a two-URL
merge. The blog you reference explains this.

and why you need to update the branch after you do a
reintegrate merge from it.  The computer should be able to remember the
history of merges and it should be obvious which things have been merged and
which revisions have been committed on both branches.  The only reason that
I can think if is that that the mergeinfo is so sparse that the computer
doesn’t remember enough about the merge history.  Would a bigger and more
extensible data format give us a straightforward way to solve that problem?

I think you are asking, at a very high level, "The svn:mergeinfo
property tracks merges down to the revision level. Would a
finer-grained tracking solution allow us to solve the remaining cyclic
merge problems and do away with the need for the reintegrate option
and the workflow that goes with it?"

If that is a fair representation of your core question then I can say,
at an equally high level, "yes, it probably can".

TREE CHANGE
We can identify tree changes by pattern matching.  This is the same tactic
that git uses, without any other tree change tracking.

Could you provide a bit more explanation of what you mean here? For
those of us not familiar with the inner workings of git.

We can identify when
this match is successful because the match is applied, examined by the
merger, and then the merge is committed.
In this case we could write the
tree map into the merge_history so that  we can map changes bi-directionally
during future merges without guessing again.   This is another case of
saving information that we need to replay a merge.
I think we could get a similar effect by generating a move operation (normal
copy & delete form) as part of the merge.  I think that this mapping would
need to be done by updates as well as by explicit merges.
EXPERTISE
Who on this list knows enough about the core algorithm used in merge to
critique these suggestions and point to places in the code or documentation?

If you haven't already read this I'd start here:
http://subversion.apache.org/docs/community-guide/

See svn_client_merge_peg4, svn_client_merge4, and
svn_client_merge_reintegrate in
https://svn.apache.org/repos/asf/subversion/trunk/subversion/include/svn_client.h

As I mentioned above, see the svn_delta_editor_t in
https://svn.apache.org/repos/asf/subversion/trunk/subversion/include/svn_diff.h

See all of https://svn.apache.org/repos/asf/subversion/trunk/subversion/libsvn_client/merge.c.
Though much of this is dedicated to the current merge tracking
implementation so you can probably skip a lot of it since you want to
be rid or it :-)

You might want to try some merges with the --ignore-ancestry option.
This disables merge tracking and performs the merge in what amounts to
a pre-1.5 manner and will allow you to get your head around the
essentials of how Subversion does a merge without worrying about
mergeinfo stuffs.

Paul

[Peter Samuelson]

Post by Paul Burba

TREE CHANGE
We can identify tree changes by pattern matching.  This is the same tactic
that git uses, without any other tree change tracking.

[Paul Burba]

Post by Paul Burba
Could you provide a bit more explanation of what you mean here? For
those of us not familiar with the inner workings of git.

I'm not terribly familiar with git internals, but I think what he's
getting at is that git does not track tree changes, but instead,
_deduces_ tree changes from changesets. If, within a single commit,
one file disappears and another file appears with similar content, git
interprets, after the fact, as a move.

There are several ramifications. One, I'm not sure how well this works
if the delete and the add are in separate commits - i.e., a file is
resurrected from history. Maybe that is tracked in some other way.

Two, git attempts to reconstruct _content_ moves, not just tree moves.
That is, if a significant chunk of a file (say, a function) disappears
and reappears in another file, this is tracked as well, even if it's
not the whole file. So, a file rename is really just a special case of
content moving between files.

Note that the complexity of this approach (deducing content moves after
the fact, rather than tracking tree changes) scales by the size of the
commit, not the size of the tree. So the assumption is that even in
large trees, any given commit is relatively limited in scope.

[Folker Schamel]

Hi Andy,

two thoughts about cyclic merges:

1. Merging should not skip cyclic merges (like this old
svnmerge tool), but must subtract (reverse-merge) the original
change first, and then add (merge) the cyclic merge, in order
to not loose adaptions of changes.

For example, suppose you have two branches A and B.
c100 is a change in A.
c101 is a change in B.
B merges c1 into B (maybe with or without conflict),
but has to adapt this change to get it compatible with c101,
resulting into c102.
Now, A merges all changes from B to A.
Then just merging c101 would loose the adaptions made in c102.
So the correct behavior is to subtract c100 and then add c101 and c102.
Note that if the changesets are not overlapping, the order
of the reverse-merges and merges does not matter.
But if the changesets are overlapping, then the correct of
reverse-merges and merges can matter.

2. Supporting cyclic merges correctly requires that merge-info
only records the direct merge info without carrying over
existing merge info.

See for example
http://subversion.tigris.org/ds/viewMessage.do?dsForumId=462&dsMessageId=948427

Cheers,
Folker

http://blogs.collab.net/subversion/2008/07/subversion-merg/
I found the article to be a good overview of the issues.I think that we
need help from Mark.On the other hand, I have seen that Mark sometimes
makes discouraging comments. My work is apparently “hand wavey” and
“proprietary”.I’m used to this treatment because I have 25 developers
who work for me who often think that I am full of crap.However, it might
have a discouraging effect on other contributors.For example, you can
see in this great ticket thread -
http://subversion.tigris.org/issues/show_bug.cgi?id=2897 - he states "I
do not think it is possible in this design....I think we need to accept
the limitations of the current design and work towards doing the best we
can within that design” Apparently that was enough to kill progress.I
think we should keep a more open mind going forward.
I’m going to make some claims that some problems have “straightforward”
solutions.That doesn’t mean they are simple solutions.Handling all of
the merge cases is going to be hard.However, they are straightforward in
the sense that we can discuss the strategy at the high level used in
Mark’s article.
Let’s consider three issues:Subtree merginfo, cyclic merge, and tree
change operations
SUBTREE MERGINFO
Mark notes that reintegrate does not work if you have subtree merginfo.
The subtrees potentially make the top-level mergeinfo inaccurate.So,
basically everyone that has looked at merge problems in the past four
years, including Mark, has tried to get rid of subtree merginfo.It’s
amazing that Subversion still tries to support this feature.It can’t be
supported in NewMerge.
In the following sections, we will also see that the merginfo data is
too sparse, and we need to replace it with something bigger and more
extensible.
CYCLIC MERGE
The case where we merge back and forth between a development or
deployment branch, and trunk, is the base case for merge.It should be
supported.Subversion only supports it with special instructions.This is
the “cyclic merge” problem.
It seems that we have two basic ways to do a merge.We can grab all of
the changes that we are trying to merge in one big diff between the
branch we are merging from and the branch we are merging into - the
reintegrate merge as described in Mark’s article.Or, we can sequentially
apply or “replay” each of the changes that we want to merge into our
working copy - the “recursive” strategy that is the default for git.
It seems to me that the “one big diff” and the replay strategy are
closely related.When you are replaying, you grab all of the changes in
any sequence of revisions that doesn’t include a merge as one big
diff.So, the current “one big diff” strategy is a special case of the
replay strategy that applies when there are no intermediate merges from
other branches or cherrypicks.
But wait!According to this article, we can’t use the replay strategy
because we are missing part of the replay.We lose information that was
used to resolve a merge when composing merge commits.If we had that
information, we could replay individual merges, and handle a higher
percentage of the cyclic merge cases.
This problem seems to have a straightforward solution.When we commit the
merge, we can stuff the changeset that represents the difference between
the merge, and the commit, into the merge_history.We just need an
extensible merge_history format to hold it.
It’s totally not clear to me why you need to say “reintegrate” when you
merge to trunk, and why you need to update the branch after you do a
reintegrate merge from it.The computer should be able to remember the
history of merges and it should be obvious which things have been merged
and which revisions have been committed on both branches.The only reason
that I can think if is that that the mergeinfo is so sparse that the
computer doesn’t remember enough about the merge history.Would a bigger
and more extensible data format give us a straightforward way to solve
that problem?
TREE CHANGE
We can identify tree changes by pattern matching.This is the same tactic
that git uses, without any other tree change tracking.We can identify
when this match is successful because the match is applied, examined by
the merger, and then the merge is committed.In this case we could write
thetree map into the merge_history so thatwe can map changes
bi-directionally during future merges without guessing again.This is
another case of saving information that we need to replay a merge.
I think we could get a similar effect by generating a move operation
(normal copy & delete form) as part of the merge.I think that this
mapping would need to be done by updates as well as by explicit merges.
EXPERTISE
Who on this list knows enough about the core algorithm used in merge to
critique these suggestions and point to places in the code or documentation?

[Andy Singleton]

Post by Paul Burba
Hi Andy,
1. Merging should not skip cyclic merges (like this old
svnmerge tool), but must subtract (reverse-merge) the original
change first, and then add (merge) the cyclic merge, in order
to not loose adaptions of changes.

I made a different proposal to solve the same problem. Following your
example, let's say we are merging
Trunk = (R+S+RSFix) + (T + RSTfix)
--- where RSTFix is changes to resolve a merge conflict
into Feature = (R+S+RSFix) + F

In your proposal, you "unmerge" (R+S+RSFix) to get F. Then, having
separated the stuff that is duplicate from the stuff that is new, you
can do the "one big diff" style merge from Trunk.

In my proposal, we save RSTfix in our expandable merge_history file, and
then we can in many cases apply T and RSTFix separately, without any
duplicates.

Do you think that might be easier?

Post by Paul Burba
For example, suppose you have two branches A and B.
c100 is a change in A.
c101 is a change in B.
B merges c1 into B (maybe with or without conflict),
but has to adapt this change to get it compatible with c101,
resulting into c102.
Now, A merges all changes from B to A.
Then just merging c101 would loose the adaptions made in c102.
So the correct behavior is to subtract c100 and then add c101 and c102.
Note that if the changesets are not overlapping, the order
of the reverse-merges and merges does not matter.
But if the changesets are overlapping, then the correct of
reverse-merges and merges can matter.
2. Supporting cyclic merges correctly requires that merge-info
only records the direct merge info without carrying over
existing merge info.
See for example
http://subversion.tigris.org/ds/viewMessage.do?dsForumId=462&dsMessageId=948427

I completely agree that "svn newmerge" should be able to handle the case
that you posted in that message.

I also agree that some of the problems in this merge case come from the
inadequate data in merginfo. As you point out, we can read mergeinfo
carefully, and we don't even know the common ancestor of two branches
being merged. If you know the common ancestor - which is often not that
far back in this workflow - you can ignore everything before that
point. Why isn't there a record dropped in with every merge that says
"We merged X (server + branch + revision) and (all of this other merge
history from there) at time Y"? This would get dragged into the next
branch it gets merged with. You could read back through the merge
tree/graph to find common ancestors. We could be saving those records
in a new and expanded merge_history.

Post by Paul Burba
Cheers,
Folker

http://blogs.collab.net/subversion/2008/07/subversion-merg/
I found the article to be a good overview of the issues.I think that we
need help from Mark.On the other hand, I have seen that Mark sometimes
makes discouraging comments. My work is apparently “hand wavey” and
“proprietary”.I’m used to this treatment because I have 25 developers
who work for me who often think that I am full of crap.However, it might
have a discouraging effect on other contributors.For example, you can
see in this great ticket thread -
http://subversion.tigris.org/issues/show_bug.cgi?id=2897 - he states "I
do not think it is possible in this design....I think we need to accept
the limitations of the current design and work towards doing the best we
can within that design” Apparently that was enough to kill progress.I
think we should keep a more open mind going forward.
I’m going to make some claims that some problems have “straightforward”
solutions.That doesn’t mean they are simple solutions.Handling all of
the merge cases is going to be hard.However, they are straightforward in
the sense that we can discuss the strategy at the high level used in
Mark’s article.
Let’s consider three issues:Subtree merginfo, cyclic merge, and tree
change operations
SUBTREE MERGINFO
Mark notes that reintegrate does not work if you have subtree merginfo.
The subtrees potentially make the top-level mergeinfo inaccurate.So,
basically everyone that has looked at merge problems in the past four
years, including Mark, has tried to get rid of subtree merginfo.It’s
amazing that Subversion still tries to support this feature.It can’t be
supported in NewMerge.
In the following sections, we will also see that the merginfo data is
too sparse, and we need to replace it with something bigger and more
extensible.
CYCLIC MERGE
The case where we merge back and forth between a development or
deployment branch, and trunk, is the base case for merge.It should be
supported.Subversion only supports it with special instructions.This is
the “cyclic merge” problem.
It seems that we have two basic ways to do a merge.We can grab all of
the changes that we are trying to merge in one big diff between the
branch we are merging from and the branch we are merging into - the
reintegrate merge as described in Mark’s article.Or, we can sequentially
apply or “replay” each of the changes that we want to merge into our
working copy - the “recursive” strategy that is the default for git.
It seems to me that the “one big diff” and the replay strategy are
closely related.When you are replaying, you grab all of the changes in
any sequence of revisions that doesn’t include a merge as one big
diff.So, the current “one big diff” strategy is a special case of the
replay strategy that applies when there are no intermediate merges from
other branches or cherrypicks.
But wait!According to this article, we can’t use the replay strategy
because we are missing part of the replay.We lose information that was
used to resolve a merge when composing merge commits.If we had that
information, we could replay individual merges, and handle a higher
percentage of the cyclic merge cases.
This problem seems to have a straightforward solution.When we commit the
merge, we can stuff the changeset that represents the difference between
the merge, and the commit, into the merge_history.We just need an
extensible merge_history format to hold it.
It’s totally not clear to me why you need to say “reintegrate” when you
merge to trunk, and why you need to update the branch after you do a
reintegrate merge from it.The computer should be able to remember the
history of merges and it should be obvious which things have been merged
and which revisions have been committed on both branches.The only reason
that I can think if is that that the mergeinfo is so sparse that the
computer doesn’t remember enough about the merge history.Would a bigger
and more extensible data format give us a straightforward way to solve
that problem?
TREE CHANGE
We can identify tree changes by pattern matching.This is the same tactic
that git uses, without any other tree change tracking.We can identify
when this match is successful because the match is applied, examined by
the merger, and then the merge is committed.In this case we could write
thetree map into the merge_history so thatwe can map changes
bi-directionally during future merges without guessing again.This is
another case of saving information that we need to replay a merge.
I think we could get a similar effect by generating a move operation
(normal copy & delete form) as part of the merge.I think that this
mapping would need to be done by updates as well as by explicit merges.
EXPERTISE
Who on this list knows enough about the core algorithm used in merge to
critique these suggestions and point to places in the code or
documentation?