bdiff: normalize the diff (issue1295)

bdiff: normalize the diff (issue1295)

When the common part of a diff can be moved forward, move it forward.
Otherwise we don't get deterministic results (it would depends on the way we
split for the recursion).
That way we get identical hunks when doing the same change, it helps to solve
issue1295 (inconsistent diffs on different side during a merge).

--- a/mercurial/bdiff.c	Wed Oct 15 23:27:35 2008 +0200
+++ b/mercurial/bdiff.c	Tue Oct 14 20:13:53 2008 +0200
@@ -240,6 +240,7 @@
 static struct hunklist diff(struct line *a, int an, struct line *b, int bn)
 {
 	struct hunklist l;
+	struct hunk *curr;
 	struct pos *pos;
 	int t;
 
@@ -259,6 +260,30 @@
 	}
 
 	free(pos);
+
+	for (curr = l.base; curr != l.head; curr++) {
+		struct hunk *next = curr+1;
+		int shift = 0;
+
+		if (next == l.head)
+			break;
+
+		if (curr->a2 == next->a1)
+			while (curr->a2+shift < an && curr->b2+shift < bn
+			       && !cmp(a+curr->a2+shift, b+curr->b2+shift))
+				shift++;
+		else if (curr->b2 == next->b1)
+			while (curr->b2+shift < bn && curr->a2+shift < an
+			       && !cmp(b+curr->b2+shift, a+curr->a2+shift))
+				shift++;
+		if (!shift)
+			continue;
+		curr->b2 += shift;
+		next->b1 += shift;
+		curr->a2 += shift;
+		next->a1 += shift;
+	}
+
 	return l;
 }
 

--- a/tests/test-bdiff	Wed Oct 15 23:27:35 2008 +0200
+++ b/tests/test-bdiff	Tue Oct 14 20:13:53 2008 +0200
@@ -1,6 +1,6 @@
 #!/usr/bin/env python
 
-import sys
+import sys, struct
 from mercurial import bdiff, mpatch
 
 def test1(a, b):
@@ -39,4 +39,16 @@
 test("a\n", "a\n")
 test("a\nb", "a\nb")
 
+#issue1295
+def showdiff(a, b):
+    bin = bdiff.bdiff(a, b)
+    pos = 0
+    while pos < len(bin):
+        p1, p2, l = struct.unpack(">lll", bin[pos:pos + 12])
+        pos += 12
+        print p1, p2, repr(bin[pos:pos + l])
+        pos += l
+showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\nx\n\nz\n")
+showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\ny\n\nx\n\nz\n")
+
 print "done"

--- a/tests/test-bdiff.out	Wed Oct 15 23:27:35 2008 +0200
+++ b/tests/test-bdiff.out	Tue Oct 14 20:13:53 2008 +0200
@@ -17,4 +17,7 @@
 *** 'abc' 'abc'
 *** 'a\n' 'a\n'
 *** 'a\nb' 'a\nb'
+6 6 'y\n\n'
+6 6 'y\n\n'
+9 9 'y\n\n'
 done