bdiff: give slight preference to removing trailing lines

[This change could be folded into the previous changeset to minimize the repo
churn ...]

Similar to the previous change, introduce an exception to the general
preference for matches in the middle of bdiff ranges: If the best match on the
B side starts at the beginning of the bdiff range, don't aim for the
middle-most A side match but for the earliest.

New (later) matches on the A side will only be considered better if the
corresponding match on the B side *not* is at the beginning of the range.
Thus, if the best (middle-most) match on the B side turns out to be at the
beginning of the range, the earliest match on the A side will be used.

The bundle size for 4.0 (hg bundle --base null -r 4.0 x.hg) happens to go from
22807275 to 22808120 bytes - a 0.004% increase.

mercurial/bdiff.c

@@ -1,312 +1,312
 /*
  bdiff.c - efficient binary diff extension for Mercurial
 
  Copyright 2005, 2006 Matt Mackall <[e-mail]>
 
  This software may be used and distributed according to the terms of
  the GNU General Public License, incorporated herein by reference.
 
  Based roughly on Python difflib
 */
 
 #include <stdlib.h>
 #include <string.h>
 #include <limits.h>
 
 #include "compat.h"
 #include "bitmanipulation.h"
 #include "bdiff.h"
 
 /* Hash implementation from diffutils */
 #define ROL(v, n) ((v) << (n) | (v) >> (sizeof(v) * CHAR_BIT - (n)))
 #define HASH(h, c) ((c) + ROL(h ,7))
 
 struct pos {
 	int pos, len;
 };
 
 int bdiff_splitlines(const char *a, ssize_t len, struct bdiff_line **lr)
 {
 	unsigned hash;
 	int i;
 	const char *p, *b = a;
 	const char * const plast = a + len - 1;
 	struct bdiff_line *l;
 
 	/* count the lines */
 	i = 1; /* extra line for sentinel */
 	for (p = a; p < plast; p++)
 		if (*p == '\n')
 			i++;
 	if (p == plast)
 		i++;
 
 	*lr = l = (struct bdiff_line *)malloc(sizeof(struct bdiff_line) * i);
 	if (!l)
 		return -1;
 
 	/* build the line array and calculate hashes */
 	hash = 0;
 	for (p = a; p < a + len; p++) {
 		hash = HASH(hash, *p);
 
 		if (*p == '\n' || p == plast) {
 			l->hash = hash;
 			hash = 0;
 			l->len = p - b + 1;
 			l->l = b;
 			l->n = INT_MAX;
 			l++;
 			b = p + 1;
 		}
 	}
 
 	/* set up a sentinel */
 	l->hash = 0;
 	l->len = 0;
 	l->l = a + len;
 	return i - 1;
 }
 
 static inline int cmp(struct bdiff_line *a, struct bdiff_line *b)
 {
 	return a->hash != b->hash || a->len != b->len || memcmp(a->l, b->l, a->len);
 }
 
 static int equatelines(struct bdiff_line *a, int an, struct bdiff_line *b,
 	int bn)
 {
 	int i, j, buckets = 1, t, scale;
 	struct pos *h = NULL;
 
 	/* build a hash table of the next highest power of 2 */
 	while (buckets < bn + 1)
 		buckets *= 2;
 
 	/* try to allocate a large hash table to avoid collisions */
 	for (scale = 4; scale; scale /= 2) {
 		h = (struct pos *)malloc(scale * buckets * sizeof(struct pos));
 		if (h)
 			break;
 	}
 
 	if (!h)
 		return 0;
 
 	buckets = buckets * scale - 1;
 
 	/* clear the hash table */
 	for (i = 0; i <= buckets; i++) {
 		h[i].pos = -1;
 		h[i].len = 0;
 	}
 
 	/* add lines to the hash table chains */
 	for (i = 0; i < bn; i++) {
 		/* find the equivalence class */
 		for (j = b[i].hash & buckets; h[j].pos != -1;
 		     j = (j + 1) & buckets)
 			if (!cmp(b + i, b + h[j].pos))
 				break;
 
 		/* add to the head of the equivalence class */
 		b[i].n = h[j].pos;
 		b[i].e = j;
 		h[j].pos = i;
 		h[j].len++; /* keep track of popularity */
 	}
 
 	/* compute popularity threshold */
 	t = (bn >= 31000) ? bn / 1000 : 1000000 / (bn + 1);
 
 	/* match items in a to their equivalence class in b */
 	for (i = 0; i < an; i++) {
 		/* find the equivalence class */
 		for (j = a[i].hash & buckets; h[j].pos != -1;
 		     j = (j + 1) & buckets)
 			if (!cmp(a + i, b + h[j].pos))
 				break;
 
 		a[i].e = j; /* use equivalence class for quick compare */
 		if (h[j].len <= t)
 			a[i].n = h[j].pos; /* point to head of match list */
 		else
 			a[i].n = -1; /* too popular */
 	}
 
 	/* discard hash tables */
 	free(h);
 	return 1;
 }
 
 static int longest_match(struct bdiff_line *a, struct bdiff_line *b,
 			struct pos *pos,
 			 int a1, int a2, int b1, int b2, int *omi, int *omj)
 {
 	int mi = a1, mj = b1, mk = 0, i, j, k, half, bhalf;
 
 	/* window our search on large regions to better bound
 	   worst-case performance. by choosing a window at the end, we
 	   reduce skipping overhead on the b chains. */
 	if (a2 - a1 > 30000)
 		a1 = a2 - 30000;
 
 	half = (a1 + a2 - 1) / 2;
 	bhalf = (b1 + b2 - 1) / 2;
 
 	for (i = a1; i < a2; i++) {
 		/* skip all lines in b after the current block */
 		for (j = a[i].n; j >= b2; j = b[j].n)
 			;
 
 		/* loop through all lines match a[i] in b */
 		for (; j >= b1; j = b[j].n) {
 			/* does this extend an earlier match? */
 			for (k = 1; j - k >= b1 && i - k >= a1; k++) {
 				/* reached an earlier match? */
 				if (pos[j - k].pos == i - k) {
 					k += pos[j - k].len;
 					break;
 				}
 				/* previous line mismatch? */
 				if (a[i - k].e != b[j - k].e)
 					break;
 			}
 
 			pos[j].pos = i;
 			pos[j].len = k;
 
 			/* best match so far? we prefer matches closer
 			   to the middle to balance recursion */
 			if (k > mk) {
 				/* a longer match */
 				mi = i;
 				mj = j;
 				mk = k;
 			} else if (k == mk) {
-				if (i > mi && i <= half) {
+				if (i > mi && i <= half && j > b1) {
 					/* same match but closer to half */
 					mi = i;
 					mj = j;
 				} else if (i == mi && (mj > bhalf || i == a1)) {
 					/* same i but best earlier j */
 					mj = j;
 				}
 			}
 		}
 	}
 
 	if (mk) {
 		mi = mi - mk + 1;
 		mj = mj - mk + 1;
 	}
 
 	/* expand match to include subsequent popular lines */
 	while (mi + mk < a2 && mj + mk < b2 &&
 	       a[mi + mk].e == b[mj + mk].e)
 		mk++;
 
 	*omi = mi;
 	*omj = mj;
 
 	return mk;
 }
 
 static struct bdiff_hunk *recurse(struct bdiff_line *a, struct bdiff_line *b,
 				struct pos *pos,
 			    int a1, int a2, int b1, int b2, struct bdiff_hunk *l)
 {
 	int i, j, k;
 
 	while (1) {
 		/* find the longest match in this chunk */
 		k = longest_match(a, b, pos, a1, a2, b1, b2, &i, &j);
 		if (!k)
 			return l;
 
 		/* and recurse on the remaining chunks on either side */
 		l = recurse(a, b, pos, a1, i, b1, j, l);
 		if (!l)
 			return NULL;
 
 		l->next = (struct bdiff_hunk *)malloc(sizeof(struct bdiff_hunk));
 		if (!l->next)
 			return NULL;
 
 		l = l->next;
 		l->a1 = i;
 		l->a2 = i + k;
 		l->b1 = j;
 		l->b2 = j + k;
 		l->next = NULL;
 
 		/* tail-recursion didn't happen, so do equivalent iteration */
 		a1 = i + k;
 		b1 = j + k;
 	}
 }
 
 int bdiff_diff(struct bdiff_line *a, int an, struct bdiff_line *b,
 		int bn, struct bdiff_hunk *base)
 {
 	struct bdiff_hunk *curr;
 	struct pos *pos;
 	int t, count = 0;
 
 	/* allocate and fill arrays */
 	t = equatelines(a, an, b, bn);
 	pos = (struct pos *)calloc(bn ? bn : 1, sizeof(struct pos));
 
 	if (pos && t) {
 		/* generate the matching block list */
 
 		curr = recurse(a, b, pos, 0, an, 0, bn, base);
 		if (!curr)
 			return -1;
 
 		/* sentinel end hunk */
 		curr->next = (struct bdiff_hunk *)malloc(sizeof(struct bdiff_hunk));
 		if (!curr->next)
 			return -1;
 		curr = curr->next;
 		curr->a1 = curr->a2 = an;
 		curr->b1 = curr->b2 = bn;
 		curr->next = NULL;
 	}
 
 	free(pos);
 
 	/* normalize the hunk list, try to push each hunk towards the end */
 	for (curr = base->next; curr; curr = curr->next) {
 		struct bdiff_hunk *next = curr->next;
 
 		if (!next)
 			break;
 
 		if (curr->a2 == next->a1 || curr->b2 == next->b1)
 			while (curr->a2 < an && curr->b2 < bn
 			       && next->a1 < next->a2
 			       && next->b1 < next->b2
 			       && !cmp(a + curr->a2, b + curr->b2)) {
 				curr->a2++;
 				next->a1++;
 				curr->b2++;
 				next->b1++;
 			}
 	}
 
 	for (curr = base->next; curr; curr = curr->next)
 		count++;
 	return count;
 }
 
 void bdiff_freehunks(struct bdiff_hunk *l)
 {
 	struct bdiff_hunk *n;
 	for (; l; l = n) {
 		n = l->next;
 		free(l);
 	}
 }
 
 

tests/test-bdiff.py

@@ -1,94 +1,94
 from __future__ import absolute_import, print_function
 import struct
 from mercurial import (
     bdiff,
     mpatch,
 )
 
 def test1(a, b):
     d = bdiff.bdiff(a, b)
     c = a
     if d:
         c = mpatch.patches(a, [d])
     if c != b:
         print("bad diff+patch result from\n  %r to\n  %r:" % (a, b))
         print("bdiff: %r" % d)
         print("patched: %r" % c[:200])
 
 def test(a, b):
     print("test", repr(a), repr(b))
     test1(a, b)
     test1(b, a)
 
 test("a\nc\n\n\n\n", "a\nb\n\n\n")
 test("a\nb\nc\n", "a\nc\n")
 test("", "")
 test("a\nb\nc", "a\nb\nc")
 test("a\nb\nc\nd\n", "a\nd\n")
 test("a\nb\nc\nd\n", "a\nc\ne\n")
 test("a\nb\nc\n", "a\nc\n")
 test("a\n", "c\na\nb\n")
 test("a\n", "")
 test("a\n", "b\nc\n")
 test("a\n", "c\na\n")
 test("", "adjfkjdjksdhfksj")
 test("", "ab")
 test("", "abc")
 test("a", "a")
 test("ab", "ab")
 test("abc", "abc")
 test("a\n", "a\n")
 test("a\nb", "a\nb")
 
 #issue1295
 def showdiff(a, b):
     print('showdiff(\n  %r,\n  %r):' % (a, b))
     bin = bdiff.bdiff(a, b)
     pos = 0
     q = 0
     while pos < len(bin):
         p1, p2, l = struct.unpack(">lll", bin[pos:pos + 12])
         pos += 12
         if p1:
             print('', repr(a[q:p1]))
         print('', p1, p2, repr(a[p1:p2]), '->', repr(bin[pos:pos + l]))
         pos += l
         q = p2
     if q < len(a):
         print('', repr(a[q:]))
 
 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")
 # we should pick up abbbc. rather than bc.de as the longest match
 showdiff("a\nb\nb\nb\nc\n.\nd\ne\n.\nf\n",
          "a\nb\nb\na\nb\nb\nb\nc\n.\nb\nc\n.\nd\ne\nf\n")
 
 print("done")
 
 def testfixws(a, b, allws):
     c = bdiff.fixws(a, allws)
     if c != b:
         print("*** fixws", repr(a), repr(b), allws)
         print("got:")
         print(repr(c))
 
 testfixws(" \ta\r b\t\n", "ab\n", 1)
 testfixws(" \ta\r b\t\n", " a b\n", 0)
 testfixws("", "", 1)
 testfixws("", "", 0)
 
 print("done")
 
 print("Nice diff for a trivial change:")
 showdiff(
     ''.join('<%s\n-\n' % i for i in range(5)),
     ''.join('>%s\n-\n' % i for i in range(5)))
 
 print("Diff 1 to 3 lines - preference for appending:")
 showdiff('a\n', 'a\n' * 3)
 print("Diff 1 to 5 lines - preference for appending:")
 showdiff('a\n', 'a\n' * 5)
-print("Diff 3 to 1 lines - preference for balanced recursion:")
+print("Diff 3 to 1 lines - preference for removing trailing lines:")
 showdiff('a\n' * 3, 'a\n')
-print("Diff 5 to 1 lines - preference for balanced recursion:")
+print("Diff 5 to 1 lines - preference for removing trailing lines:")
 showdiff('a\n' * 5, 'a\n')

tests/test-bdiff.py.out

@@ -1,84 +1,82
 test 'a\nc\n\n\n\n' 'a\nb\n\n\n'
 test 'a\nb\nc\n' 'a\nc\n'
 test '' ''
 test 'a\nb\nc' 'a\nb\nc'
 test 'a\nb\nc\nd\n' 'a\nd\n'
 test 'a\nb\nc\nd\n' 'a\nc\ne\n'
 test 'a\nb\nc\n' 'a\nc\n'
 test 'a\n' 'c\na\nb\n'
 test 'a\n' ''
 test 'a\n' 'b\nc\n'
 test 'a\n' 'c\na\n'
 test '' 'adjfkjdjksdhfksj'
 test '' 'ab'
 test '' 'abc'
 test 'a' 'a'
 test 'ab' 'ab'
 test 'abc' 'abc'
 test 'a\n' 'a\n'
 test 'a\nb' 'a\nb'
 showdiff(
   'x\n\nx\n\nx\n\nx\n\nz\n',
   'x\n\nx\n\ny\n\nx\n\nx\n\nz\n'):
  'x\n\nx\n\n'
  6 6 '' -> 'y\n\n'
  'x\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'):
  'x\n\nx\n\n'
  6 6 '' -> 'y\n\n'
  'x\n\n'
  9 9 '' -> 'y\n\n'
  'x\n\nz\n'
 showdiff(
   'a\nb\nb\nb\nc\n.\nd\ne\n.\nf\n',
   'a\nb\nb\na\nb\nb\nb\nc\n.\nb\nc\n.\nd\ne\nf\n'):
  0 0 '' -> 'a\nb\nb\n'
  'a\nb\nb\nb\nc\n.\n'
  12 12 '' -> 'b\nc\n.\n'
  'd\ne\n'
  16 18 '.\n' -> ''
  'f\n'
 done
 done
 Nice diff for a trivial change:
 showdiff(
   '<0\n-\n<1\n-\n<2\n-\n<3\n-\n<4\n-\n',
   '>0\n-\n>1\n-\n>2\n-\n>3\n-\n>4\n-\n'):
  0 3 '<0\n' -> '>0\n'
  '-\n'
  5 8 '<1\n' -> '>1\n'
  '-\n'
  10 13 '<2\n' -> '>2\n'
  '-\n'
  15 18 '<3\n' -> '>3\n'
  '-\n'
  20 23 '<4\n' -> '>4\n'
  '-\n'
 Diff 1 to 3 lines - preference for appending:
 showdiff(
   'a\n',
   'a\na\na\n'):
  'a\n'
  2 2 '' -> 'a\na\n'
 Diff 1 to 5 lines - preference for appending:
 showdiff(
   'a\n',
   'a\na\na\na\na\n'):
  'a\n'
  2 2 '' -> 'a\na\na\na\n'
-Diff 3 to 1 lines - preference for balanced recursion:
+Diff 3 to 1 lines - preference for removing trailing lines:
 showdiff(
   'a\na\na\n',
   'a\n'):
- 0 2 'a\n' -> ''
  'a\n'
- 4 6 'a\n' -> ''
-Diff 5 to 1 lines - preference for balanced recursion:
+ 2 6 'a\na\n' -> ''
+Diff 5 to 1 lines - preference for removing trailing lines:
 showdiff(
   'a\na\na\na\na\n',
   'a\n'):
- 0 4 'a\na\n' -> ''
  'a\n'
- 6 10 'a\na\n' -> ''
+ 2 10 'a\na\na\na\n' -> ''