You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Sander Striker <st...@apache.org> on 2003/01/08 23:59:32 UTC

RE: Diff lib

Hi,

More progress on this front.

Currently we have an implementation of two algorithms mixed
together:

"An O(NP) Sequence Comparison Algorithm"
by Wu, Manber and Meyers

"An O(ND) Difference Algorithm and Its Variations"
by Meyers.

Specifically variation 4b from the second paper is used and partially
implemented.  It doesn't implement the linear space LCS recovery algorithm,
but does take advantage of scanning from both the start aswell as the end
of sequences being compared.

This kind of brings the longest common subsequence part of the code
up to speed.  It can always be improved upon later on.  I've been told
GNU diff uses some heuristic to speed things up, but I refuse to look
at their code because of the license issues.  If someone could explain it
to me though, I would probably be all ears ;).

Furthermore there are some things on the TODO list which I
will echo here.  I guess I could put it in the issue, but hey,
I'm already halfway through this post...  Half of these are implementation
details:

 - The tree to hold the nodes should be replaced by something smarter.
   At a minimum it should be balanced, at best it should be fronted by
   a hash table.

 - We should be taking advantage of the knowledge that some tokens (lines)
   don't occur at all in another sequence.  We should just skip these.
   If we don't we might aswell do away with the node tree and do comparison
   on the tokens (and/or their hashes) directly.

 - The public API should grow a hash * argument to return hashes in
   get_token().

 - Several cleanups need to be applied:
    - svn_diff__tree_insert_token() should return a svn_diff__node_t instead
      of a svn_diff__position_t.
    - svn_diff__position_t allocation should be isolated in svn_diff__get_tokens.
      Currently it is in svn_diff__tree_insert_token which is Wrong(tm).

 - The diff3 code is missing usefull output functions (see: diff_file.c).

 - We are in dire need for some tests of this library.  The only real
   testing I've done are through gdb and 'diff', which didn't change since
   I last posted it:
     http://subversion.tigris.org/servlets/ReadMsg?list=dev&msgNo=13857.
   The way I use it is as follows:
     ./diff original modified >original.patch
     cp original modified2
     cat orignal.patch | patch modified2
     diff modified modified2 (should report no differences).

   The diff3 code is completely untested...

 - Some timed tests need to be done.


Just a heads up,  

Sander



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Diff lib

Posted by cm...@collab.net.
Ben Collins-Sussman <su...@collab.net> writes:

> "Sander Striker" <st...@apache.org> writes:
> 
> > In all, I'm glad I did a clean room implementation.  Although it is nice
> > to see good ideas and solutions by others, sometimes reinventing the
> > wheel brings in new good ideas ;)  And more importantly, lets you truly
> > understand the algorithm.
> 
> Sander, I hope your diff library could somehow be packaged up as a
> standalone library someday... it would be a great boon to the BSD
> world, who have no choice but to use GNU diffutils at the moment.
> 
> If somebody really wanted to help Subversion indirectly, they'd start
> writing a hard-core test suite for this new difflib.  Not a glamorous
> job, but critical.  The sooner we have rigorous tests, the sooner we
> can start integrating it into Subversion, and the sooner we can drop
> our dependence on external 'diff' and 'diff3' binaries.  What a joy
> that will be!

+1 (x2)!

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Diff lib

Posted by rb...@rkbloom.net.
I have actually been enjoying writing test suites recently.  So, I
volunteer, oh pick me, pick me, pick me.   :-)  I would prefer to use my
hacked version of CuTest for the test suite, because that is my latest
project.  Would that be a problem?

Ryan

On 9 Jan 2003, Ben Collins-Sussman wrote:

> "Sander Striker" <st...@apache.org> writes:
>
> > In all, I'm glad I did a clean room implementation.  Although it is nice
> > to see good ideas and solutions by others, sometimes reinventing the
> > wheel brings in new good ideas ;)  And more importantly, lets you truly
> > understand the algorithm.
>
> Sander, I hope your diff library could somehow be packaged up as a
> standalone library someday... it would be a great boon to the BSD
> world, who have no choice but to use GNU diffutils at the moment.
>
> If somebody really wanted to help Subversion indirectly, they'd start
> writing a hard-core test suite for this new difflib.  Not a glamorous
> job, but critical.  The sooner we have rigorous tests, the sooner we
> can start integrating it into Subversion, and the sooner we can drop
> our dependence on external 'diff' and 'diff3' binaries.  What a joy
> that will be!
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
> For additional commands, e-mail: dev-help@subversion.tigris.org
>
>



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Diff lib

Posted by Ben Collins-Sussman <su...@collab.net>.
"Sander Striker" <st...@apache.org> writes:

> In all, I'm glad I did a clean room implementation.  Although it is nice
> to see good ideas and solutions by others, sometimes reinventing the
> wheel brings in new good ideas ;)  And more importantly, lets you truly
> understand the algorithm.

Sander, I hope your diff library could somehow be packaged up as a
standalone library someday... it would be a great boon to the BSD
world, who have no choice but to use GNU diffutils at the moment.

If somebody really wanted to help Subversion indirectly, they'd start
writing a hard-core test suite for this new difflib.  Not a glamorous
job, but critical.  The sooner we have rigorous tests, the sooner we
can start integrating it into Subversion, and the sooner we can drop
our dependence on external 'diff' and 'diff3' binaries.  What a joy
that will be!


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

RE: Diff lib

Posted by Sander Striker <st...@apache.org>.
> From: Karl Fogel [mailto:kfogel@newton.ch.collab.net]
> Sent: Thursday, January 09, 2003 5:34 AM

> "Sander Striker" <st...@apache.org> writes:
> > up to speed.  It can always be improved upon later on.  I've been told
> > GNU diff uses some heuristic to speed things up, but I refuse to look
> > at their code because of the license issues.  If someone could explain it
> > to me though, I would probably be all ears ;).
> 
> The GPL does not demand that you do a clean room implementation,
> merely that you don't copy their code.  (I am not a lawyer, of course;
> but I personally wouldn't hesitate to look at GPL'd code when
> reimplementing it.  Might have some good ideas.)

IANAL either, which is why I didn't want to take the chance.  It would be
a shame to have to ditch the final code when I did and it turned out to
be a problem.

In all, I'm glad I did a clean room implementation.  Although it is nice
to see good ideas and solutions by others, sometimes reinventing the
wheel brings in new good ideas ;)  And more importantly, lets you truly
understand the algorithm.

I'm still interested in more speedup (which will also be achieved by
clearing up some points on the TODO list), and knowing about a trick
in the GNU diff implementation wouldn't hurt...
 
>> [...]
>> 
>> Just a heads up,  
> 
> Sounds great!

Yeah, but does it look and work great too? ;) :)

Sander

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Diff lib

Posted by Karl Fogel <kf...@newton.ch.collab.net>.
"Sander Striker" <st...@apache.org> writes:
> up to speed.  It can always be improved upon later on.  I've been told
> GNU diff uses some heuristic to speed things up, but I refuse to look
> at their code because of the license issues.  If someone could explain it
> to me though, I would probably be all ears ;).

The GPL does not demand that you do a clean room implementation,
merely that you don't copy their code.  (I am not a lawyer, of course;
but I personally wouldn't hesitate to look at GPL'd code when
reimplementing it.  Might have some good ideas.)

> [...]
> 
> Just a heads up,  

Sounds great!

-K

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org