Re: libxdiff and patience diff

[Pierre Habouzit <madcoder@debian.org>]

[-- Attachment #1: Type: text/plain, Size: 2593 bytes --]

On Tue, Nov 04, 2008 at 03:17:37AM +0000, Davide Libenzi wrote:
> On Tue, 4 Nov 2008, Pierre Habouzit wrote:
> 
> > Hi Davide,
> > 
> > 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.
> > 
> > 
> > [ For the readers playing at home, the patience diff algorithm is
> >   explained after my sig. ]
> > 
> > 
> > What I did is to:
> > (1) add a flag to the xenv in xdl_split that says that I want a
> >     patience "split".
> > (2) Then in xdl_split, if that bit is set, I compute the longest common
> >     subsequence from the patience diff.
> > (3) for each split it computes I call xdl_recs_cmp on that interval.
> > 
> > 
> > What I thought it would achieve is that I force some boundaries at which
> > libxdiff _must_ resync. Though, it seems that for some reason it doesn't
> > work, probably because the "ha" stuff and the boundaries absolutely
> > don't work the way I thought it did.
> > 
> > So where is the place I should do that ? I suspect it should be
> > partly in xprepare.c but I'm a bit stuck right now.
> > 
> > 
> > Any pointer on how the stuff in xprepare.c and xdiffi.c work would help
> > greatly, it's really not self-evident to me :)
> 
> What makes you think it'd self-evident to me? :)
> Seriously, I forgot stuff I wrote the last month, this is way beyond my 
> memory limits.
> You definitely need to look at xprepare.c, especially at xdl_trim_ends() 
> and xdl_cleanup_records(). Lines are re-arranged in indexes, and this 
> might screw up your logic if you're not prepared for it.
> What xdl_split() does, is find the start of an LCS and return the 
> coordinate. Then xdl_recs_cmp() does the box reducing (first two "for" 
> loops) and different-lines marking (first and second "if").

Well it's what I thought it did indeed, that's why before recursing into
that bit, I tried to extract a full LCS from the patience diff algorithm
and recurse into that for each interval it gives, which _should_ work,
but doesn't at all :/

Okay maybe I should re-read my algorithm slowly and check that I've not
made something silly (like chaining the list in the reverse order or god
knows what), but my debug functions let me believe that I did that fine.

I'll look into it tonight.

-- 
·O·  Pierre Habouzit
··O                                                madcoder@debian.org
OOO                                                http://www.madism.org

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]