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

conflicts.

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;)

//Peter

---------------------------------------------------------------------

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