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

Re: [merge tracking] [RFC] New merging algorithm

From: Peter Lundblad <plundblad_at_google.com>
Date: 2007-03-09 23:37:55 CET

Mark Phippard writes:
> On 3/9/07, Peter Lundblad <plundblad@google.com> wrote:
> >
> > Hi,
> >
> > I've spent some time looking into the algorithm in
> > /branches/merge-tracking/subversion/libsvn_client/diff.c
> > that tries to do the mergeinfo-sensitive merging and I think I have a
> > better
> > algorithm. Let me first recap my understanding of the current algorithm,
> > then discuss problems with it and, after that, I'll sketch my version
> > of the solution.
> Not going to quote any more as my question is a little off to the side of
> the details. One thing your proposal does not talk about is how it changes
> the usability equation in terms of what happens when conflicts are
> encountered. Does your proposal allow the merge to always run to completion
> or are you allowing the merge process to do more and also improving the
> overall consistency of the working copy when it does encounter a conflict
> and needs to bail? I think it is the latter.

Hi, Mark,

It tries to keep the working copy more consistent when merging
by merging more in revision order. It can bail after each group of merges with
the same end revision, or it can continue til the end skipping the
parts of the subtree where we have conflicts.

Let me try to clarify with some examples:
Say we have the following tree with revisions to merge.
Note that the ranges are inclusive to ease the discussion.
A (1-10)
A/B (1-9, 11-20)

Here, we will merge:
A/B 1-9
and then
A (1-20) (excluding A/B (1-10)

If we get a conflict in the first merge, we leave an inconsistent tree
where A/B have revisions that the rest of A don't have.
OTOH, the second merge would be done in one step (the current
algorithm would do in it two), so the tree will be consistent on
For reference, te current algorithm would merge:
A/B (1-9)
A/B (1-20)
A (1-20), excluding A/B.

Returning to my proposed algorithm, if we wanted to, we could merge
A (1-9), excluding A/B
if we got a conflict during the first merge. I.e. we would merge
everything that was left to merge, but only up to the end revision of
the merge with conflicts. That would give us a consistent tree, *but*
it could introduce spurious conflicts that could be avoided if we
merged all along to revision 20.

Another example:
Let's say we're merging revisions 1-20. We have cherry-picked two
revisions in the whole tree and also a third revision in a subtree.
Before the merge, we have:
A (1-8, 10-17, 19-20)
A/B (1-4, 6-8, 10-17, 19-20)
(Again, the revisions are the ones that need to be merged, which is
the complement of the stored merge info.)

To make the discussion more confusing, let's start with what the
current algorithm would do:
It would merge:
A/B (1-4)
A/B (6-8)
A/B (10-17)
A/B (19-20)
(All below excluding the A/B subtree)
A (1-8)
A (10-17)
A (19-20)

Conflicts at any of the merges of A/B will always leave the rest of
the A tree without any merges (or all merges up to 20 if we choose not
to bail).

Let's look at the proposed algoritm:
A/B (1-4)
A (1-8), excluding B (1-5)
A (10-17)
A (19-20)

So, we have four merge steps instead of 7. Conflicts at the first step
will leave the tree in the same inconsistent state as the current
algorithm. The rest of the steps, though, keeps the whole tree in
sync. On conflicts in the first step, we could, as earlier, bring A
up to revision four, again risking to introduce spurious conflicts.

Another improvements in my proposed algorithm is to avoid merging
paths that are going to be deleted later on.

I hope this clarifies what I'm trying to get at;)

To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Fri Mar 9 23:38:17 2007

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

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.