Re: The criss-cross merge case

From: Daniel Barkalow <barkalow@iabervon.org>
Date: Apr 28, 2005, 02:19 UTC
Message-ID: <Pine.LNX.4.21.0504272209390.30848-100000@iabervon.org>
In-Reply-To: <87d5sf7il2.fsf@rzstud4.rz.uni-karlsruhe.de>

On Thu, 28 Apr 2005, Benedikt Schmidt wrote:

> AFAIK the paper mentioned in the GNU diff sources [1] is an improvement
> to an earlier paper by the same author titled
> "A File Comparison Program" - Miller, Myers - 1985.

GNU diff is based on a better algorithm than traditional diff, reportly, but there are better algorithms still, developed since, at least according to a brief literature search on Google Scholar. (bdiff and vdelta, for example, which can identify block moves as well.)

> Can you be more specific why the algorithm is a bad choice (performance,
> quality of diff output)?

I suspect that the speed is suboptimal (for the cases under which it is actually used). The quality of the output is about ideal, lacking a representation for block moves, but I'm hoping to have a diff/merge set that handles block moves effectively, even if it can't report them in diff format. I'm also hoping for an annotate function that could use block moves.

> Ok, darcs doesn't handle block moves, so there is no need for an algorithm that
> supports them (yet). Is there any free SCM that has support for block moves at
> the moment? It seems like clearcase detects them, but I don't know where it
> takes advantage of it.

I would think that darcs would be able to do neat things in its merger if it knew about block moves. Obviously, it only makes sense to add support for identifying them and using them at the same time.

	-Daniel
*This .sig left intentionally blank*