Re: libxdiff and patience diff

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Nov 4, 2008, 05:39 UTC
Message-ID: <alpine.DEB.1.00.0811040627020.24407@pacific.mpi-cbg.de>
In-Reply-To: <20081104004001.GB29458@artemis.corp>

Hi,

On Tue, 4 Nov 2008, Pierre Habouzit wrote:

> I've been working tonight, trying to make libxdiff support the patience 
> diff algorithm, but I've totally failed, because I _thought_ I 
> understood what xdl_split was doing, but it appears I don't.

I thought about it, too, at the GitTogether, although I want to finish my jGit diff first.

The main idea I had about patience diff is that you can reuse a lot of functions in libxdiff.

But the requirement of taking just unique lines/hashes into account, and _after_ splitting up, _again_ determine uniqueness _just_ in the between-hunk part made me think that it may be wiser to have a separate function for the patience diff stuff.

Basically, you would start to have libxdiff split the lines and hash them as normal, but then determine the unique hashes (I'd start with the smaller text, just to have a better chance to end up with unique hashes).

Once they are determined, you can search for those exact lines (hash first) in the post-document.

Once that is done, you'd have to find the longest common subsequence, which you could do using the existing infrastructure, but that would require more work (as we already know the lines are unique).

After that, you would have to recurse to the same algorithm _between_ known chunks. Eventually, that would have to resort to classical libxdiff (if there are no, or not enough, unique lines).

Ciao, Dscho