[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

[merge tracking] Handling cyclic merging

From: Daniel Rall <dlr_at_collab.net>
Date: 2007-12-04 02:13:19 CET

On Sun, 02 Dec 2007, Folker Schamel wrote:

> Hi Daniel!
>
> Do I understand you correctly:
> You have a post-1.5 solution in mind solving all merge tracking
> problems discussed lately?

Hi Folker, thanks for the questions.

We do have a concrete idea of how to implement handling for type (b) reflected
revisions (as outlined by me in this thread). Kamesh Jayachandran is currently
working on correcting Subversion 1.5's implementation on the issue-2897 branch;
my initial implementation of this was too naive to handle reflected revisions
in light of potential cherry-picking.

Given Subversion's architecture, handling type (a) reflected revisions for
cyclic merges seem to be even trickier. We basically have to identify
reflected revisions which themselves contain mergeinfo, compare their content
payload against that of the revisions they merged, and create an additional
changeset/revision that represents those differences at commit time (meaning
that commit of a merge is effectively producing N new revisions, rather than
the 1 new revision we produce today). No one's actually tried to do this yet,
and I expect the implementation to get pretty hairy when we actually start
trying to execute on this theory.

> >On Sat, 01 Dec 2007, Blair Zajac wrote:
> >
> >>Ben Collins-Sussman wrote:
> >>>On Nov 30, 2007 4:23 PM, Blair Zajac <blair@orcaware.com> wrote:
> >>>
> >>>>It just works. I mean, you still can get conflicts when you merge back
> >>>>and you
> >>>>resolve those just as you normally would.
> >>>>
> >>>>Thinking about it, I guess you might have to redo conflict resolution
> >>>>again when
> >>>>you merge changes back to trunk.
> >>>Yeah, I wouldn't categorize that as 'just works'. Why should a user
> >>>have to resolve the same conflicts twice? That's an indication that
> >>>there are some changes *not* being tracked that should be.
> >
> >What svnmerge.py does is calculate "merged", "blocked", "phantom", and
> >"reflected" revisions, and subtract those from the list of revisions
> >requested
> >for merge (see the contrib/client-side/svnmerge/svnmerge.py:action_merge()
> >function). Issue #2897 is about proper handling of "reflected" revisions;
> >that is, revisions from the merge source which carry mergeinfo from the
> >merge
> >target as their payload.
> >
> >There are two potential flavors of reflected revisions:
> >
> >a) "Merging revisions", which themselves also carry mergeinfo.
> >b) "Merged revisions", which carry no mergeinfo (a leaf node in a merge
> >DAG).
>
> You define that "reflected revisions" are revisions "which carry mergeinfo",
> but according your definition of b) that kind of "reflected revisions",
> have no mergeinfo, which seems to be a contradiction.
 
I certainly wasn't clear with the terminology.
"Reflected revisions" may or may not carry mergeinfo.
"ReflectING revisions", are effectively pointers to "reflected revisions",
and so always carry mergeinfo.

"Reflecting revisions" are always "merging revisions", but I don't think that
the opposite is always true (since the mergeinfo relationship between the
merge target and source may differ).

> >In Subversion's core Merge Tracking, we've decided that (a) requires
> >additional parents in the DAG to properly represent,
>
> The DAG you are talking about, how exactly it is defined
> in terms of the current mergeinfo scheme?

Mergeinfo describes the contributors to, or merge relationship/ancestry
between, "node revisions" (a noderev is effectively a version of an object)
in the Subversion file system. When mergeinfo is added to a new noderev,
it's saying that the noderev has the added merge source and revisions as a
parent in the change DAG. In ClearCase terminology, you're drawing a merge
arrow; unlike ClearCase, you're only drawing a merge arrow for the revisions
being merged, rather than for the merge source all the way back to its
youngest common ancestor with the merge target (unless the added revisions
encompass all those changes).

This is a fundamental difference between Merge Tracking in Subversion and in
other systems, and what makes Subversion better at cherry-picking than
whole-branch merging. In Subversion, you're effectively always
cherry-picking, but often you cherry-pick all the changes that make a branch
unique from its ancestor (which is how we perform a whole-branch merge).

> What exactly to you want to change in the current mergeinfo schmele
> to add support for "additional parents in the DAG"?
 
What Subversion won't do today is add multiple noderevs at commit time
(cmpilato will whack me if I get the terminology wrong here ;). In addition
to committing a "merging revision" (which contains mergeinfo added during a
merge, plus the unadulterated changes from that merge), we also need to add
additional parents (noderevs) to Subversion's FS DAG, to represent any local
changes commited along with the result of a merge (e.g. due to conflict
resolution). These additional changes would be referenced by a revision
number separate from that produced by the commit of the result of the
merge, allowing the reflected revision to be filtered out when subsequently
doing a cyclic merge, while the additional changes -- needed for conflict
resolution or whatever -- would remain mergable.

This (theoretically) both avoids the repeated merge problem for reflected
revisions, and avoids dropping additional changes committed along with the
result of a merge (e.g. your conflict resolution, necessary semantic changes,
or sloppy development practices).

> >and currently punt by
> >repeating merges in this case for the sake of correctness. The plan has
> >been to address this post-1.5. (b) is what Kamesh has been working on, and
> >is something that needs to be addressed before releasing 1.5. Without (a),
> >we're still in *much* better shape than in pre-1.5 releases; you can avoid
> >specifying revision ranges when performing merges, and the only repeated
> >merges you hit are when performing cyclic merging (M -> F -> M).
> >
> >svnmerge.py makes no distinction between these two types of reflected
> >revisions, instead filtering out both (a) and (b), which can miss merging
> >changes when pushing a branch which has been kept in sync with a mainline
> >back
> >into that mainline.
>
> You seem to have a "post-1.5" approach in mind.
> How exactly does this approach handle the case described in
> http://svn.haxx.se/dev/archive-2007-11/1265.shtml ?

After reading the above, please tell me what you think (preferably, think it
through before reading further).

Below is my take on what should happen with your scenario once complete
handling for cyclic merging -- of which type (a) reflected revisions is a
part -- is implemented:

--- snip ---
r1: Create branch "release" from "trunk"
r2: Create branch "stable" from "trunk"
r3: Create branch "feature" from "trunk"
r4: Commit change "T" to trunk
r5: Commit change "R" to release. R is overlapping with T.
r6: Commit change "S" to stable. S is overlapping with R (but not with T).
r7: Commit change "F" to feature. F is not overlapping with any other change.

Repository:
     trunk = T
     release = R
     stable = S
     feature = F

r8: Merge (with merge-tracking) from release into stable.
     This gives a conflict, which is manually resolved by change "RSfix".

Repository:
     trunk = T.
     release = R
     stable = R+S+RSfix, mergeinfo=release:1-5
     feature = F

r9: Merge (with merge-tracking) from stable into trunk.
     This gives a conflict, which is manually resolved by change "RSTfix".

Repository:
     trunk = (R+S+RSfix)+T+RSTfix, mergeinfo=stable:1-8,release:1-5(indirect)
     release = R
     stable = R+S+RSfix, mergeinfo=release:1-5
     feature = F

r10: Merge (with merge-tracking) from stable into feature.
     No conflicts.

Repository:
     trunk = (R+S+RSfix)+T+RSTfix, mergeinfo=stable:1-8,release:1-5(indirect)
     release = R
     stable = R+S+RSfix, mergeinfo=release:1-5
     feature = (R+S+RSfix)+F, mergeinfo=stable:1-9,release:1-5(indirect)

r11: Merge (with merge-tracking) from trunk into feature.
     This is the interesting step.

The expected result of r11 is (R+S+RSfix)+T+RSTfix+F [for feature].
--- snip ---

'svn merge' will first merge r4 (change T) from trunk. It will then consider
whether r9 from trunk is a "reflecting revision" (a revision composed entirely
of changes already in the target's history or mergeinfo). As r9 contains the
revisions corresponding to feature's "reflected" changes (R+S+RSfix), its
merge won't be repeated. 'svn merge' will also see an additional, unmerged
noderev of trunk (as I discussed above), which is not listed in your scenario,
containing the change RSTfix (produced during the commit of the merge that
created r9). This additional trunk revision for RSTfix will be merged, leaving
you with the correct content for r11.

  • application/pgp-signature attachment: stored
Received on Tue Dec 4 01:12:23 2007

This is an archived mail posted to the Subversion Dev mailing list.