You are viewing a plain text version of this content. The canonical link for it is here.

Posted to dev@subversion.apache.org by Torsten Rueger <to...@hiit.fi> on 2004/04/28 11:19:36 UTC

3 way merge algorithm

Moi,

at the university I work, we have found a more efficient algorithm for 
3 way merging. It's works better than diff3 especially in that it 
handles moves. So it can merge cases where one person moves a piece of 
text, while the other edits a subset of it. It also handles XML merges 
surprisingly well.

Unfortunately I can not release code (which is ruby anyway), but I can 
describe the algorithm, which is quite simple, and help anyone who 
wants to implement it.
I would suggest it could be used for cases where diff3 fails, so as not 
to rock the boat too much initially.

I'd really like to hear if anyone is interested in this, even quite 
separate from wanting to implement it.

Below is a minimal description of the algorithm using a small xml 
example,

Torsten


Original:  <html><body>Stuff</body><head>Merge Example</head></html>
              1     2     3     4      5    6     7      8       9

One:       <html><head>Merge Example</head><body>Stuff</body></html>
              1  <--5     6      7      8  <--2     3    4   <--9

Two:       <html><body>Algorithm</body><head>Example</head></html>
              1     2   <--10    <--4     5 <-- 7      8      9

Merge:     <html><head>Example</head><body>Algorithm</body></html>
              1     5     7       8      2     10       4     9

Matching phase: Find the string in One and Two to map to the original. 
Add added strings
          One:  1   5-8   2-4  9
          Two   1   5     7,8    2  add:10  4 9
Merging phase: go backwards through original following the change 
pattern:
       Start with 9 in either
       Go to 4, because of change in One
       Go to 10 because of change in Two
       Go to 2 because of change in Two
       Go to 8 because of change in One
       Go to 7 because no change in original order
       Go to 5 because of change in Two
       Go to 1 because of change in One

Output in reverse order and get Merge!

While going through the original matches of the matching phase, one has 
to recognise the "changes" inside the matches. It's either that or 
splitting all matches into the non overlapping pieces that are the 
numbers. This second option has proven to be more complicated.

Matching is done al la xdelta, by splitting files into chunks, 
calculating hashes for each chunk. Then looking for equal hashes and 
expanding the match as far as possible. At the end one can add the 
strings in the "gaps" that have not been matched.


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: 3 way merge algorithm

Posted by kf...@collab.net.

Branko Čibej <br...@xbc.nu> writes:
> >We use an internal diff/patch library now, in Subversion.
>
> To be pedantic, we don't actually use an internal patch
> implementation; that is, you can't apply a patch with "svn patch", or
> anything.

Sure.  What I meant was: since svn can update to receive repos changes
into a locally modified file, we clearly have some sort of internal
patch implementation.  Whether we call it "patch" or not, or make it
available as a subcommand, doesn't change that.

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: 3 way merge algorithm

Posted by Branko Čibej <br...@xbc.nu>.

kfogel@collab.net wrote:

>Torsten Rueger <to...@hiit.fi> writes:
>  
>
>>and patch process should result in less conflicts. Even if you do it
>>on a line basis. But as I understand you use external patch, so that's
>>out of the question.
>>    
>>
>
>We use an internal diff/patch library now, in Subversion.
>  
>
To be pedantic, we don't actually use an internal patch implementation; 
that is, you can't apply a patch with "svn patch", or anything.

-- Brane




---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org