Re: [PATCH v3 1/3] Implement the patience diff algorithm

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Jan 7, 2009, 20:19 UTC
Message-ID: <alpine.DEB.1.00.0901072110340.7496@intel-tinevez-2-302>
In-Reply-To: <alpine.DEB.1.10.0901071159060.17115@alien.or.mcafeemobile.com>

Hi,

On Wed, 7 Jan 2009, Davide Libenzi wrote:

Show 17 quoted lines

> On Wed, 7 Jan 2009, Johannes Schindelin wrote:
> 
> > Could it be that you misread my patch, and assumed that I faked an 
> > xdfenv?
> > 
> > I did not, but instead faked two mmfiles, which is only as simple as I did 
> > it because in git.git, we only have contiguous mmfiles.  (I recall that 
> > libxdiff allows for ropes instead of arrays.)
> > 
> > The way I did it has one big shortcoming: I need to prepare an xdfenv for 
> > the subfiles even if I already prepared one for the complete files.  IOW 
> > the lines are rehashed all over again.
> 
> I told you I just glanced at the code :)
> In that way, if you guys decide to merge this new algo, you'll need to 
> split the prepare from the optimize, and feed it with an already prepared 
> env.

Right.

> Before going that way, have you ever tried to tweak xdl_cleanup_records 
> and xdl_clean_mmatch to reduce the level of optimization, and see the 
> results you get? It is possible that you won't need two different algos 
> inside git.

No, I hadn't thought that libxdiff already determines uniqueness before actually running xdl_do_diff().

I also have to admit that I am not as clever as other people, and had quite a hard time figuring out as much as I did (for example, that rchg[i] == 1 means that this line is to be added/deleted, and that i is in the range 0, ..., N - 1 rather than 1, ..., N).

So it is quite possible that something patience-like can be done earlier.

However, I do not see a way to implement the recursion necessary for the patience diff. Remember:

	patience(line range):
		find unique lines
		if no unique lines found:
			resort to classical diff
			return
		extract the longest common sequence of unique common lines
		between those, recurse

When recursing, previously non-unique lines can turn unique, of course. And I do not see how that recursion could be done before xdl_clean_mmatch(), short of redoing the hashing and cleaning records up.

Of course, it might well be possible, but I am already out of my depth reading something like "rdis0" and "rpdis1", and being close to despair.

:')

Ciao, Dscho