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).

mercurial/bdiff.c

@@ -240,6 +240,7 b' static void recurse(struct line *a, stru'
 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 b' static struct hunklist diff(struct line '
 	}
 
 	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;
 }
 

tests/test-bdiff

@@ -1,6 +1,6 b''
 #!/usr/bin/env python
 
-import sys
+import sys, struct
 from mercurial import bdiff, mpatch
 
 def test1(a, b):
@@ -39,4 +39,16 b' test("abc", "abc")'
 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"

tests/test-bdiff.out

@@ -17,4 +17,7 b''
 *** '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