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

Re: Better repeated merge tracking...

From: Branko Čibej <brane_at_xbc.nu>
Date: 2002-12-11 15:36:04 CET

Nathanael Nerode wrote:

>I was thinking about graceful handling of repeated merges. Clearly the key
>to this is tracking the history at the time of the early merges.
>

Well, if you want to be really pedantic, file history isn't nearly
enough -- you'd have to track which hunks of a diff actually contributed
to a file's contents. But we can forget that (changesets) for the time
being.

> For
>instance, if we have a setup like
>root->A->C
> |->B-----^
>
>We need a note on the "C" copy that it has two ancestors, A and B, not just
>one. If we view it as having A as the primary ancestor, then the "patch"
>from A to C consists of the differences from the common ancestor (root) to B.
> If we view it as having B as the primary ancestor, then the "patch" from B
>to C consists of the differences from root to A.
>

It actually doesn't matter which is the "primary" ancestor. The logical
ancestry set of C is (root, A); the physical ancestry set is (root, A,
B). When lookig for a common predecessor for merges, you have to look at
the physical ancestry set.

>Then suppose just for confusion that new development sprouted all over:
>root->D
>A->E->H
>B->F---^
>C->G
>
>To merge F and G, we find the common ancestor (B) and do three-way merge.
>Similarly to merge E and G.
>
>Now look at a really perverse case. When we come to merge H with G, there
>are two common ancestor choices: A and B. If we pick A, then we have one
>three-way merge (paths A->C->G and A->E->H), and if we pick B, then we have
>a different three-way merge (B->C->G and B->F->H). This leads to a little
>repetition, but not much, really.
>
If your branches are organized in a tree, there's ever only one common
ancestor. In the worst case, that's root. However, in the common case,
looking for a common ancestor is only the first step. You also have to
skip, on each branch, all the revisions that were already merged.

>Look at a typical case, where you repeatedly merge from HEAD, and finally
>merge the whole branch in.
>root->A->B->C->D->E
>|->1---\>2-----\>3---/
>
>At the creation of 3 (the second merge from HEAD), it finds the common
>ancestor A and merges from there. At the final merger, for E, it finds the
>common ancestor C and merges from there.
>
Eh? the common ancestor of D and 3 is D, since 3 was merged from D. E
becomes D + diff (3, D).

But you're looking at the simple cases. Imagine a more complex situation:

0--->1--->2--->3--->4--->5
. \A--------\----\B---\C

In this case, the merge to B involves changes from 3 to 4, but _not_
from 2. When you merge 5->C, 1 is still your common ancestor, but you
have to discount the 2->3 and 3->4 changes.

>So I don't see what the problem is in handling repeated merges; we just have
>to record multiple ancestors for the purposes of "merge" searching for a
>common ancestor. (Not necessarily for other purposes.) Of course, a good
>ancestor search algorithm might not be trivial, but you get the idea.
>
>Am I missing some vital point?
>
>Is svn already recording merge history in this manner?
>
>

The vital point is that SVN doesn't record merge history yet. That's
exactly the point. :-)
Recording this history is the first step towards making repeated merges
work.

-- 
Brane Čibej   <brane_at_xbc.nu>   http://www.xbc.nu/brane/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Wed Dec 11 15:36:46 2002

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