Newsgroups: comp.sources.bugs
Path: utzoo!utgpu!jarvis.csri.toronto.edu!dgp.toronto.edu!hugh
From: hugh@dgp.toronto.edu ("D. Hugh Redelmeier")
Subject: bug in public domain diff?
Message-ID: <8901191545.AA18697@explorer.dgp.toronto.edu>
Organization: University of Toronto, CSRI
Date: Thu, 19 Jan 89 10:45:51 EST


Various versions of a public domain diff have been broadcast across
the net over the years (including comp.sources.misc 2.1, 2.8, and
2.59).  The original version was on the DECUS C tape, author unknown
(Conroy?).  This program is based on the same algorithm as UNIX diff.

Anyway, all the versions I have checked seem to produce suboptimal
output when diffing the following two files.  UNIX diff does not
have this problem.  Am I right, is this a bug?  Does anyone know a
fix?  The code is currently beyond my comprehension.

file a:
	9
	1
	2
	3
	4
	5
	6
	9

file b:
	8
	1
	2
	x
	x
	4
	3
	4
	5
	6
	8

pd-diff says:
	1c1
	< 9
	---
	> 8
	4c4,5
	< 3
	---
	> x
	> x
	5a7,8
	> 3
	> 4
	8c11
	< 9
	---
	> 8

SunOS3.5 diff says:
	1c1
	< 9
	---
	> 8
	3a4,6
	> x
	> x
	> 4
	8c11
	< 9
	---
	> 8

Notice that pd-diff uselessly deletes and re-inserts 3.  This is not
wrong, just suboptimal.  Perhaps there is a simple off-by-one error
in the code.

Hugh Redelmeier
{utcsri, yunexus, uunet!attcan!utzoo, hcr}!redvax!hugh
When all else fails: hugh@csri.toronto.edu
+1 416 482-8253