You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Nathanael Nerode <ne...@twcny.rr.com> on 2002/12/11 06:16:31 UTC
Better repeated merge tracking...
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. 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.
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.
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.
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?
--Nathanael
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Better repeated merge tracking...
Posted by Branko Čibej <br...@xbc.nu>.
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 <br...@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
Re: Better repeated merge tracking...
Posted by Timothee Besset <tt...@idsoftware.com>.
Since I have to deal with Vendor branches a lot, I have written my own
scripts to synchronize SourceOffsite (i.e. Source Safe) with cvs and more
recently svn.
svn doesn't remember when you copy/merge files together currently. So it
doesn't have the ability to handle repeated merges. Not saying that it
will never happen, but it's not in at this time.
Basically what my script does is keep log files of the checkin operations
on the vendor branch (i.e. each time I get an update from the master
source), and I use that information to issue svn merge -rprevrev:newrev
commands. prerev is the last revision I used to merge into my main branch,
and newrev is the one I just commited. There are more svn-ish ways to do
this I believe, such as by setting properties on the directories when
checking in instead of logging to a file (or so I've been told by the svn
devs).
TTimo
On Wed, 11 Dec 2002 01:16:31 -0500
Nathanael Nerode <ne...@twcny.rr.com> 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. 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.
>
> 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.
>
> 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.
>
> 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?
>
> --Nathanael
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
> For additional commands, e-mail: dev-help@subversion.tigris.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Better repeated merge tracking...
Posted by Paul Smith <pa...@nortelnetworks.com>.
%% Nathanael Nerode <ne...@twcny.rr.com> writes:
nn> Of course, a good ancestor search algorithm might not be trivial,
Actually it's just a very simple shortest-path algorithm--you can find
excellent implementations in any first year computer algorithms course
book. I actually implemented one myself, in Perl, from the output of
ClearCase's version tree listing command (mine was based on a previous
implementation by Brad Appleton).
--
-------------------------------------------------------------------------------
Paul D. Smith <ps...@nortelnetworks.com> HASMAT--HA Software Mthds & Tools
"Please remain calm...I may be mad, but I am a professional." --Mad Scientist
-------------------------------------------------------------------------------
These are my opinions---Nortel Networks takes no responsibility for them.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org