[PATCH 5 of 6] pure Python implementation of bdiff.c

[Martin Geisler]

# HG changeset patch
# User Martin Geisler <mg at daimi.au.dk>
# Date 1231781066 -3600
# Node ID 211568685b2a7f6a9916f57d9a53b8c53a0b06f0
# Parent  e5ef97c26d1b1cba1c090c2ba95fef426d425884
pure Python implementation of bdiff.c
The bdiff.blocks functions is not quite correct here, it gives one
error in the test suite:

  ERROR: test-bdiff output changed
  --- Expected output
  +++ Test output
  @@ -17,7 +17,7 @@
   *** 'abc' 'abc'
   *** 'a\n' 'a\n'
   *** 'a\nb' 'a\nb'
  +5 5 '\ny\n'
   6 6 'y\n\n'
  -6 6 'y\n\n'
  -9 9 'y\n\n'
  +8 8 '\ny\n'
   done
  !.
  Failed test-bdiff: output changed

diff -r e5ef97c26d1b -r 211568685b2a mercurial/bdiff.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mercurial/bdiff.py	Mon Jan 12 18:24:26 2009 +0100
@@ -0,0 +1,42 @@
+# bdiff.py - Python implementation of bdiff.c
+#
+# Copyright 2009 Matt Mackall <mpm at selenic.com> and others
+#
+# This software may be used and distributed according to the terms
+# of the GNU General Public License, incorporated herein by reference.
+
+import struct, difflib
+# mdiff import moved to bottom due to import cycle
+
+def bdiff(a, b):
+    a = str(a).splitlines(1)
+    b = str(b).splitlines(1)
+
+    if not a:
+        s = "".join(b)
+        return s and (struct.pack(">lll", 0, 0, len(s)) + s)
+
+    bin = []
+    p = [0]
+    for i in a: p.append(p[-1] + len(i))
+
+    d = difflib.SequenceMatcher(None, a, b).get_matching_blocks()
+    la = 0
+    lb = 0
+    for am, bm, size in d:
+        s = "".join(b[lb:bm])
+        if am > la or s:
+            bin.append(struct.pack(">lll", p[la], p[am], len(s)) + s)
+        la = am + size
+        lb = bm + size
+
+    return "".join(bin)
+
+def blocks(a, b):
+    an = mdiff.splitnewlines(a)
+    bn = mdiff.splitnewlines(b)
+    d = difflib.SequenceMatcher(None, an, bn)
+    return [(i, i + n, j, j + n) for (i, j, n) in d.get_matching_blocks()]
+
+# this breaks an import cycle
+import mdiff