Re: [PATCH] xdiff: add xdl_merge() (was: (unknown))

From: Jakub Narebski <jnareb@gmail.com>
Date: Nov 21, 2006, 23:15 UTC
Message-ID: <ek0170$h53$1@sea.gmane.org>
In-Reply-To: <Pine.LNX.4.63.0611212316080.26827@wbgn013.biozentrum.uni-wuerzburg.de>

Johannes Schindelin wrote:

> [PATCH] xdiff: add xdl_merge()

Shouldn't this be in the subject of message?

> This new function implements the functionality of RCS merge, but
> in-memory. It returns < 0 on error, otherwise the number of conflicts.

Only RCS merge, or can you implement whole diff3 (from GNU diffutils) functionality with that?

Show 15 quoted lines

> Finding the conflicting lines can be a very expensive task. You can
> control the eagerness of this algorithm:
> 
> - a level value of 0 means that all overlapping changes are treated
>   as conflicts,
> - a value of 1 means that if the overlapping changes are identical,
>   it is not treated as a conflict.
> - If you set level to 2, overlapping changes will be analyzed, so that
>   almost identical changes will not result in huge conflicts. Rather,
>   only the conflicting lines will be shown inside conflict markers.
> 
> With each increasing level, the algorithm gets slower, but more accurate.
> Note that the code for level 2 depends on the simple definition of
> mmfile_t specific to git, and therefore it will be harder to port that
> to LibXDiff.

How it compares performance with RCS merge/GNU diff3?

It is really nice to have that. Bram Cohen (of Codeville, SCM built around sophisticated merge algorithm) wrote about recursive three-way merge in http://revctrl.org/CrissCrossMerge

   Recursive three-way merge _usually_ provides the right answer, however
   there are some edge cases. For example, conflict markers can be matched
   incorrectly, because they aren't given any special semantic meaning for
   the merge algorithm, and are simply treated as lines. In particular,
   there are (somewhat complicated) cases where the conflict markers of two
   unrelated conflicts get matched against each other, even though the
   content sections of them are totally unrelated.

I'm not sure if he has specific examples, or is it just theoretical talk, but having built-in merge would certainly help revursive merge strategy (and perhaps also git-rerere).

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git