[ANN] Diff::LCS 1.1.0, Diff::LCS 1.0.4

[Austin Ziegler]

It is with pleasure that I announce the latest versions of Diff::LCS,
a pure-Ruby differencing algorithm.

Version 1.0.4 is an incremental bugfix that improves the installer (it
is not entirely fixed for ri document generation; I believe that I
have done most of what I can do with this), fixes a problem of missing
left-side changes when comparing against an empty sequence, and fixes
a problem with ldiff output, especially for unified diff output.

Version 1.1.0 is a feature release that includes all bugfixes up to
and including 1.0.4. In addition, it adds a new standard callback
(ContextDiffCallback) that works similarly to SDiffCallback but
produces a smaller diff set.

More importantly, it is now possible to patch a sequence with a diff
set to produce the second sequence. If the patch is performed without
specifying direction, then it will be examined to see which direction
in which the patch will be performed. If the patch is performed by
specifying the direction, then the patch will be performed without
verification that the patch set applies to the source sequence.

Using version 1.0.4, I have produced a couple of patches today for
both rdoc and for Ruby's dir.c that look *exactly* like they do from
unix diff (at least the version included with cygwin).

Both versions can be found in the Ruwiki project filelist:
http://rubyforge.org/frs/?group_id=84

-austin

Diff::LCS README
================
Diff::LCS is a port of Algorithm:iff[1] that uses the McIlroy-Hunt
longest common subsequence (LCS) algorithm to compute intelligent
differences between two sequenced enumerable containers[2]. The
implementation is based on Mario I. Wolczko's[3] Smalltalk version
(1.2, 1993)[4] and Ned Konz's[5] Perl version (Algorithm:iff)[6].

This release is version 1.1.0 with the addition of new features,
including the ability to #patch and #unpatch changes as well as a new
contextual diff callback, Diff::LCS::ContextDiffCallbacks, that should
improve the context sensitivity of patching.

Using this module is quite simple. By default, Diff::LCS does not
extend objects with the Diff::LCS interface, but will be called as if
it were a function:

require 'diff/lcs'

seq1 = %w(a b c e h j l m n p)
seq2 = %w(b c d e f j k l m r s t)

lcs = Diff::LCS.LCS(seq1, seq2)
diffs = Diff::LCS.diff(seq1, seq2)
sdiff = Diff::LCS.sdiff(seq1, seq2)
seq = Diff::LCS.traverse_sequences(seq1, seq2, callback_obj)
bal = Diff::LCS.traverse_balanced(seq1, seq2, callback_obj)
seq2 == Diff::LCS.patch!(seq1, diffs)
seq1 == Diff::LCS.unpatch!(seq2, diffs)
seq2 == Diff::LCS.patch!(seq1, sdiff)
seq1 == Diff::LCS.unpatch!(seq2, sdiff)

Objects can be extended with Diff::LCS:

seq1.extend(Diff::LCS)
lcs = seq1.lcs(seq2)
diffs = seq1.diff(seq2)
sdiff = seq1.sdiff(seq2)
seq = seq1.traverse_sequences(seq2, callback_obj)
bal = seq1.traverse_balanced(seq2, callback_obj)
seq2 == seq1.patch!(diffs)
seq1 == seq2.unpatch!(diffs)
seq2 == seq1.patch!(sdiff)
seq1 == seq2.unpatch!(sdiff)

By requiring 'diff/lcs/array' or 'diff/lcs/string', Array or String
will be extended for use this way.

Copyright
=========
# Copyright 2004 Austin Ziegler <[email protected]>
# adapted from:
# Algorithm:iff (Perl) by Ned Konz <[email protected]>
# Smalltalk by Mario I. Wolczko <[email protected]>
# implements McIlroy-Hunt diff algorithm
#
# This program is free software. It may be redistributed and/or modified
# under the terms of the GPL version 2 (or later), the Perl Artistic
# licence, or the Ruby licence.
#
# $Id: README,v 1.5 2004/08/08 20:33:09 austin Exp $

Footnotes
=========
[1] This library is called Diff::LCS because there are multiple
Ruby libraries called Algorithm:iff maintained by other authors.
[2] By sequenced enumerable, I mean that the order of enumeration is
predictable and consistent for the same set of data. While it is
theoretically possible to generate a diff for unordereded hash, it
will only be meaningful if the enumeration of the hashes is
consistent. In general, this will mean that containers that behave
like String or Array will perform best.
[3] (e-mail address removed)
[4] ftp://st.cs.uiuc.edu/pub/Smalltalk/MANCHESTER/manchester/4.0/diff.st
[5] (e-mail address removed)
[6] http://search.cpan.org/~nedkonz/Algorithm-Diff-1.15/

 

[Mauricio Fernández]

It is with pleasure that I announce the latest versions of Diff::LCS,
a pure-Ruby differencing algorithm. [...]
Version 1.1.0 is a feature release that includes all bugfixes up to
and including 1.0.4. In addition, it adds a new standard callback
(ContextDiffCallback) that works similarly to SDiffCallback but
produces a smaller diff set.

I have just updated the package in the preliminary Ruby Production Archive
(RPA) repository (http://rubyforge.org/frs/?group_id=265)

$ rpa query diff-lcs
Matching available ports:
diff-lcs 1.1.0-1 LCS algorithm to compute differences between two
enumerable containers

As usual, it can be installed/upgraded with
rpa install diff-lcs

When reviewing the library while packaging, I have found some small
quirks, which I fixed in the RPA package (note that the following is
not the exact patch I applied):

batsman@tux-chan:/tmp/diff-lcs-1.1.0/bin$ RUBYOPT= ldiff -u htmldiff.orig htmldiff
--- htmldiff.orig 2004-08-08 23:47:38 +0200
+++ htmldiff 2004-08-08 23:48:11 +0200

@@ -1,4 +1,4 @@
-#! /usr/bin/env ruby
+#!/usr/bin/env ruby
#--
# Copyright 2004 Austin Ziegler <[email protected]>
# adapted from:
@@ -17,7 +17,7 @@
require 'rubygems'
require_gem 'diff-lcs', "1.1.0"
require 'diff/lcs/string'
-rescue
+rescue LoadError
require 'diff/lcs/string'
end


batsman@tux-chan:/tmp/diff-lcs-1.1.0/bin$ RUBYOPT= ldiff -u ldiff.orig ldiff
--- ldiff.orig 2004-08-08 23:47:41 +0200
+++ ldiff 2004-08-08 23:48:34 +0200

@@ -1,4 +1,4 @@
-#!/user/bin/env ruby
+#!/usr/bin/env ruby
# = Diff::LCS 1.1.0
# == ldiff Usage
# ldiff [options] oldfile newfile
@@ -33,7 +33,7 @@
begin
require 'rubygems'
require_gem 'diff-lcs', "1.1.0"
-rescue
+rescue LoadError
require 'diff/lcs'
end

 

[jm]

As sad as it is I think you just made my day.


J.

 

[Austin Ziegler]

The changes the Mauricio found have been checked in. I will be
re-releasing these files in the morning sometime. Because the changes
are so small, I am *not* renumbering the version (e.g., it will not be
1.1.1), but the packages will be clearly marked (e.g.,
diff-lcs-1.1.0-1.tar.gz), excepting the Gems release, which will be
either 1.1.0.1 or 1.1.0 depending on whether my tests indicate that
Gems can handle 4-level versioning. Agh. I *hate* making this sort of
error.

If this maintaining the versioning scheme will cause problems for
anyone, please let me know ASAP.

-austin

It is with pleasure that I announce the latest versions of Diff::LCS,
a pure-Ruby differencing algorithm. [...]
Version 1.1.0 is a feature release that includes all bugfixes up to
and including 1.0.4. In addition, it adds a new standard callback
(ContextDiffCallback) that works similarly to SDiffCallback but
produces a smaller diff set.

I have just updated the package in the preliminary Ruby Production Archive
(RPA) repository (http://rubyforge.org/frs/?group_id=265)

$ rpa query diff-lcs
Matching available ports:
diff-lcs 1.1.0-1 LCS algorithm to compute differences between two
enumerable containers

As usual, it can be installed/upgraded with
rpa install diff-lcs

When reviewing the library while packaging, I have found some small
quirks, which I fixed in the RPA package (note that the following is
not the exact patch I applied):

batsman@tux-chan:/tmp/diff-lcs-1.1.0/bin$ RUBYOPT= ldiff -u htmldiff.orig htmldiff
--- htmldiff.orig 2004-08-08 23:47:38 +0200
+++ htmldiff 2004-08-08 23:48:11 +0200

@@ -1,4 +1,4 @@
-#! /usr/bin/env ruby
+#!/usr/bin/env ruby
#--
# Copyright 2004 Austin Ziegler <[email protected]>
# adapted from:
@@ -17,7 +17,7 @@
require 'rubygems'
require_gem 'diff-lcs', "1.1.0"
require 'diff/lcs/string'
-rescue
+rescue LoadError
require 'diff/lcs/string'
end

batsman@tux-chan:/tmp/diff-lcs-1.1.0/bin$ RUBYOPT= ldiff -u ldiff.orig ldiff
--- ldiff.orig 2004-08-08 23:47:41 +0200
+++ ldiff 2004-08-08 23:48:34 +0200

@@ -1,4 +1,4 @@
-#!/user/bin/env ruby
+#!/usr/bin/env ruby
# = Diff::LCS 1.1.0
# == ldiff Usage
# ldiff [options] oldfile newfile
@@ -33,7 +33,7 @@
begin
require 'rubygems'
require_gem 'diff-lcs', "1.1.0"
-rescue
+rescue LoadError
require 'diff/lcs'
end