mdiff: replace wscleanup() regexps with C loops

On my system it reduces:

  hg annotate -w mercurial/commands.py

from 36s to less than 8s, to be compared with 6.3s when run without whitespace
options.

mercurial/bdiff.c

@@ -1,455 +1,499 b''
 /*
  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 <Python.h>
 #include <stdlib.h>
 #include <string.h>
 #include <limits.h>
 
 #if defined __hpux || defined __SUNPRO_C || defined _AIX
 #define inline
 #endif
 
 #ifdef __linux
 #define inline __inline
 #endif
 
 #ifdef _WIN32
 #ifdef _MSC_VER
 #define inline __inline
 typedef unsigned long uint32_t;
 #else
 #include <stdint.h>
 #endif
 static uint32_t htonl(uint32_t x)
 {
 	return ((x & 0x000000ffUL) << 24) |
 		((x & 0x0000ff00UL) <<  8) |
 		((x & 0x00ff0000UL) >>  8) |
 		((x & 0xff000000UL) >> 24);
 }
 #else
 #include <sys/types.h>
 #if defined __BEOS__ && !defined __HAIKU__
 #include <ByteOrder.h>
 #else
 #include <arpa/inet.h>
 #endif
 #include <inttypes.h>
 #endif
 
 #include "util.h"
 
 struct line {
 	int hash, len, n, e;
 	const char *l;
 };
 
 struct pos {
 	int pos, len;
 };
 
 struct hunk;
 struct hunk {
 	int a1, a2, b1, b2;
 	struct hunk *next;
 };
 
 static int splitlines(const char *a, int len, struct line **lr)
 {
 	unsigned hash;
 	int i;
 	const char *p, *b = a;
 	const char * const plast = a + len - 1;
 	struct line *l;
 
 	/* count the lines */
 	i = 1; /* extra line for sentinel */
 	for (p = a; p < a + len; p++)
 		if (*p == '\n' || p == plast)
 			i++;
 
 	*lr = l = (struct line *)malloc(sizeof(struct line) * i);
 	if (!l)
 		return -1;
 
 	/* build the line array and calculate hashes */
 	hash = 0;
 	for (p = a; p < a + len; p++) {
 		/* Leonid Yuriev's hash */
 		hash = (hash * 1664525) + (unsigned char)*p + 1013904223;
 
 		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 line *a, struct line *b)
 {
 	return a->hash != b->hash || a->len != b->len || memcmp(a->l, b->l, a->len);
 }
 
 static int equatelines(struct line *a, int an, struct 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 = INT_MAX;
 		h[i].len = 0;
 	}
 
 	/* add lines to the hash table chains */
 	for (i = bn - 1; i >= 0; i--) {
 		/* find the equivalence class */
 		for (j = b[i].hash & buckets; h[j].pos != INT_MAX;
 		     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 != INT_MAX;
 		     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 = INT_MAX; /* too popular */
 	}
 
 	/* discard hash tables */
 	free(h);
 	return 1;
 }
 
 static int longest_match(struct line *a, struct line *b, struct pos *pos,
 			 int a1, int a2, int b1, int b2, int *omi, int *omj)
 {
 	int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k;
 
 	for (i = a1; i < a2; i++) {
 		/* skip things before the current block */
 		for (j = a[i].n; j < b1; j = b[j].n)
 			;
 
 		/* loop through all lines match a[i] in b */
 		for (; j < b2; j = b[j].n) {
 			/* does this extend an earlier match? */
 			if (i > a1 && j > b1 && pos[j - 1].pos == i - 1)
 				k = pos[j - 1].len + 1;
 			else
 				k = 1;
 			pos[j].pos = i;
 			pos[j].len = k;
 
 			/* best match so far? */
 			if (k > mk) {
 				mi = i;
 				mj = j;
 				mk = k;
 			}
 		}
 	}
 
 	if (mk) {
 		mi = mi - mk + 1;
 		mj = mj - mk + 1;
 	}
 
 	/* expand match to include neighboring popular lines */
 	while (mi - mb > a1 && mj - mb > b1 &&
 	       a[mi - mb - 1].e == b[mj - mb - 1].e)
 		mb++;
 	while (mi + mk < a2 && mj + mk < b2 &&
 	       a[mi + mk].e == b[mj + mk].e)
 		mk++;
 
 	*omi = mi - mb;
 	*omj = mj - mb;
 
 	return mk + mb;
 }
 
 static struct hunk *recurse(struct line *a, struct line *b, struct pos *pos,
 			    int a1, int a2, int b1, int b2, struct 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 hunk *)malloc(sizeof(struct 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;
 	}
 }
 
 static int diff(struct line *a, int an, struct line *b, int bn,
 		 struct hunk *base)
 {
 	struct 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 hunk *)malloc(sizeof(struct 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 hunk *next = curr->next;
 		int shift = 0;
 
 		if (!next)
 			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;
 	}
 
 	for (curr = base->next; curr; curr = curr->next)
 		count++;
 	return count;
 }
 
 static void freehunks(struct hunk *l)
 {
 	struct hunk *n;
 	for (; l; l = n) {
 		n = l->next;
 		free(l);
 	}
 }
 
 static PyObject *blocks(PyObject *self, PyObject *args)
 {
 	PyObject *sa, *sb, *rl = NULL, *m;
 	struct line *a, *b;
 	struct hunk l, *h;
 	int an, bn, count, pos = 0;
 
 	if (!PyArg_ParseTuple(args, "SS:bdiff", &sa, &sb))
 		return NULL;
 
 	an = splitlines(PyBytes_AsString(sa), PyBytes_Size(sa), &a);
 	bn = splitlines(PyBytes_AsString(sb), PyBytes_Size(sb), &b);
 
 	if (!a || !b)
 		goto nomem;
 
 	l.next = NULL;
 	count = diff(a, an, b, bn, &l);
 	if (count < 0)
 		goto nomem;
 
 	rl = PyList_New(count);
 	if (!rl)
 		goto nomem;
 
 	for (h = l.next; h; h = h->next) {
 		m = Py_BuildValue("iiii", h->a1, h->a2, h->b1, h->b2);
 		PyList_SetItem(rl, pos, m);
 		pos++;
 	}
 
 nomem:
 	free(a);
 	free(b);
 	freehunks(l.next);
 	return rl ? rl : PyErr_NoMemory();
 }
 
 static PyObject *bdiff(PyObject *self, PyObject *args)
 {
 	char *sa, *sb, *rb;
 	PyObject *result = NULL;
 	struct line *al, *bl;
 	struct hunk l, *h;
 	uint32_t encode[3];
 	int an, bn, len = 0, la, lb, count;
 
 	if (!PyArg_ParseTuple(args, "s#s#:bdiff", &sa, &la, &sb, &lb))
 		return NULL;
 
 	an = splitlines(sa, la, &al);
 	bn = splitlines(sb, lb, &bl);
 	if (!al || !bl)
 		goto nomem;
 
 	l.next = NULL;
 	count = diff(al, an, bl, bn, &l);
 	if (count < 0)
 		goto nomem;
 
 	/* calculate length of output */
 	la = lb = 0;
 	for (h = l.next; h; h = h->next) {
 		if (h->a1 != la || h->b1 != lb)
 			len += 12 + bl[h->b1].l - bl[lb].l;
 		la = h->a2;
 		lb = h->b2;
 	}
 
 	result = PyBytes_FromStringAndSize(NULL, len);
 
 	if (!result)
 		goto nomem;
 
 	/* build binary patch */
 	rb = PyBytes_AsString(result);
 	la = lb = 0;
 
 	for (h = l.next; h; h = h->next) {
 		if (h->a1 != la || h->b1 != lb) {
 			len = bl[h->b1].l - bl[lb].l;
 			encode[0] = htonl(al[la].l - al->l);
 			encode[1] = htonl(al[h->a1].l - al->l);
 			encode[2] = htonl(len);
 			memcpy(rb, encode, 12);
 			memcpy(rb + 12, bl[lb].l, len);
 			rb += 12 + len;
 		}
 		la = h->a2;
 		lb = h->b2;
 	}
 
 nomem:
 	free(al);
 	free(bl);
 	freehunks(l.next);
 	return result ? result : PyErr_NoMemory();
 }
 
+/*
+ * If allws != 0, remove all whitespace (' ', \t and \r). Otherwise,
+ * reduce whitespace sequences to a single space and trim remaining whitespace
+ * from end of lines.
+ */
+static PyObject *fixws(PyObject *self, PyObject *args)
+{
+	PyObject *s, *result = NULL;
+	char allws, c;
+	const char *r;
+	int i, rlen, wlen = 0;
+	char *w;
+
+	if (!PyArg_ParseTuple(args, "Sb:fixws", &s, &allws))
+		return NULL;
+	r = PyBytes_AsString(s);
+	rlen = PyBytes_Size(s);
+
+	w = (char *)malloc(rlen);
+	if (!w)
+		goto nomem;
+
+	for (i = 0; i != rlen; i++) {
+		c = r[i];
+		if (c == ' ' || c == '\t' || c == '\r') {
+			if (!allws && (wlen == 0 || w[wlen - 1] != ' '))
+				w[wlen++] = ' ';
+		} else if (c == '\n' && !allws
+			  && wlen > 0 && w[wlen - 1] == ' ') {
+			w[wlen - 1] = '\n';
+		} else {
+			w[wlen++] = c;
+		}
+	}
+
+	result = PyBytes_FromStringAndSize(w, wlen);
+
+nomem:
+	free(w);
+	return result ? result : PyErr_NoMemory();
+}
+
+
 static char mdiff_doc[] = "Efficient binary diff.";
 
 static PyMethodDef methods[] = {
 	{"bdiff", bdiff, METH_VARARGS, "calculate a binary diff\n"},
 	{"blocks", blocks, METH_VARARGS, "find a list of matching lines\n"},
+	{"fixws", fixws, METH_VARARGS, "normalize diff whitespaces\n"},
 	{NULL, NULL}
 };
 
 #ifdef IS_PY3K
 static struct PyModuleDef bdiff_module = {
 	PyModuleDef_HEAD_INIT,
 	"bdiff",
 	mdiff_doc,
 	-1,
 	methods
 };
 
 PyMODINIT_FUNC PyInit_bdiff(void)
 {
 	return PyModule_Create(&bdiff_module);
 }
 #else
 PyMODINIT_FUNC initbdiff(void)
 {
 	Py_InitModule3("bdiff", methods, mdiff_doc);
 }
 #endif
 

mercurial/mdiff.py

@@ -1,334 +1,333 b''
 # mdiff.py - diff and patch routines 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 version 2 or any later version.
 
 from i18n import _
 import bdiff, mpatch, util
 import re, struct
 
 def splitnewlines(text):
     '''like str.splitlines, but only split on newlines.'''
     lines = [l + '\n' for l in text.split('\n')]
     if lines:
         if lines[-1] == '\n':
             lines.pop()
         else:
             lines[-1] = lines[-1][:-1]
     return lines
 
 class diffopts(object):
     '''context is the number of context lines
     text treats all files as text
     showfunc enables diff -p output
     git enables the git extended patch format
     nodates removes dates from diff headers
     ignorews ignores all whitespace changes in the diff
     ignorewsamount ignores changes in the amount of whitespace
     ignoreblanklines ignores changes whose lines are all blank
     upgrade generates git diffs to avoid data loss
     '''
 
     defaults = {
         'context': 3,
         'text': False,
         'showfunc': False,
         'git': False,
         'nodates': False,
         'ignorews': False,
         'ignorewsamount': False,
         'ignoreblanklines': False,
         'upgrade': False,
         }
 
     __slots__ = defaults.keys()
 
     def __init__(self, **opts):
         for k in self.__slots__:
             v = opts.get(k)
             if v is None:
                 v = self.defaults[k]
             setattr(self, k, v)
 
         try:
             self.context = int(self.context)
         except ValueError:
             raise util.Abort(_('diff context lines count must be '
                                'an integer, not %r') % self.context)
 
     def copy(self, **kwargs):
         opts = dict((k, getattr(self, k)) for k in self.defaults)
         opts.update(kwargs)
         return diffopts(**opts)
 
 defaultopts = diffopts()
 
 def wsclean(opts, text, blank=True):
     if opts.ignorews:
-        text = re.sub('[ \t\r]+', '', text)
+        text = bdiff.fixws(text, 1)
     elif opts.ignorewsamount:
-        text = re.sub('[ \t\r]+', ' ', text)
-        text = text.replace(' \n', '\n')
+        text = bdiff.fixws(text, 0)
     if blank and opts.ignoreblanklines:
         text = re.sub('\n+', '\n', text).strip('\n')
     return text
 
 def splitblock(base1, lines1, base2, lines2, opts):
     # The input lines matches except for interwoven blank lines. We
     # transform it into a sequence of matching blocks and blank blocks.
     lines1 = [(wsclean(opts, l) and 1 or 0) for l in lines1]
     lines2 = [(wsclean(opts, l) and 1 or 0) for l in lines2]
     s1, e1 = 0, len(lines1)
     s2, e2 = 0, len(lines2)
     while s1 < e1 or s2 < e2:
         i1, i2, btype = s1, s2, '='
         if (i1 >= e1 or lines1[i1] == 0
             or i2 >= e2 or lines2[i2] == 0):
             # Consume the block of blank lines
             btype = '~'
             while i1 < e1 and lines1[i1] == 0:
                 i1 += 1
             while i2 < e2 and lines2[i2] == 0:
                 i2 += 1
         else:
             # Consume the matching lines
             while i1 < e1 and lines1[i1] == 1 and lines2[i2] == 1:
                 i1 += 1
                 i2 += 1
         yield [base1 + s1, base1 + i1, base2 + s2, base2 + i2], btype
         s1 = i1
         s2 = i2
 
 def allblocks(text1, text2, opts=None, lines1=None, lines2=None, refine=False):
     """Return (block, type) tuples, where block is an mdiff.blocks
     line entry. type is '=' for blocks matching exactly one another
     (bdiff blocks), '!' for non-matching blocks and '~' for blocks
     matching only after having filtered blank lines. If refine is True,
     then '~' blocks are refined and are only made of blank lines.
     line1 and line2 are text1 and text2 split with splitnewlines() if
     they are already available.
     """
     if opts is None:
         opts = defaultopts
     if opts.ignorews or opts.ignorewsamount:
         text1 = wsclean(opts, text1, False)
         text2 = wsclean(opts, text2, False)
     diff = bdiff.blocks(text1, text2)
     for i, s1 in enumerate(diff):
         # The first match is special.
         # we've either found a match starting at line 0 or a match later
         # in the file.  If it starts later, old and new below will both be
         # empty and we'll continue to the next match.
         if i > 0:
             s = diff[i - 1]
         else:
             s = [0, 0, 0, 0]
         s = [s[1], s1[0], s[3], s1[2]]
 
         # bdiff sometimes gives huge matches past eof, this check eats them,
         # and deals with the special first match case described above
         if s[0] != s[1] or s[2] != s[3]:
             type = '!'
             if opts.ignoreblanklines:
                 if lines1 is None:
                     lines1 = splitnewlines(text1)
                 if lines2 is None:
                     lines2 = splitnewlines(text2)
                 old = wsclean(opts, "".join(lines1[s[0]:s[1]]))
                 new = wsclean(opts, "".join(lines2[s[2]:s[3]]))
                 if old == new:
                     type = '~'
             yield s, type
         yield s1, '='
 
 def diffline(revs, a, b, opts):
     parts = ['diff']
     if opts.git:
         parts.append('--git')
     if revs and not opts.git:
         parts.append(' '.join(["-r %s" % rev for rev in revs]))
     if opts.git:
         parts.append('a/%s' % a)
         parts.append('b/%s' % b)
     else:
         parts.append(a)
     return ' '.join(parts) + '\n'
 
 def unidiff(a, ad, b, bd, fn1, fn2, r=None, opts=defaultopts):
     def datetag(date, addtab=True):
         if not opts.git and not opts.nodates:
             return '\t%s\n' % date
         if addtab and ' ' in fn1:
             return '\t\n'
         return '\n'
 
     if not a and not b:
         return ""
     epoch = util.datestr((0, 0))
 
     fn1 = util.pconvert(fn1)
     fn2 = util.pconvert(fn2)
 
     if not opts.text and (util.binary(a) or util.binary(b)):
         if a and b and len(a) == len(b) and a == b:
             return ""
         l = ['Binary file %s has changed\n' % fn1]
     elif not a:
         b = splitnewlines(b)
         if a is None:
             l1 = '--- /dev/null%s' % datetag(epoch, False)
         else:
             l1 = "--- %s%s" % ("a/" + fn1, datetag(ad))
         l2 = "+++ %s%s" % ("b/" + fn2, datetag(bd))
         l3 = "@@ -0,0 +1,%d @@\n" % len(b)
         l = [l1, l2, l3] + ["+" + e for e in b]
     elif not b:
         a = splitnewlines(a)
         l1 = "--- %s%s" % ("a/" + fn1, datetag(ad))
         if b is None:
             l2 = '+++ /dev/null%s' % datetag(epoch, False)
         else:
             l2 = "+++ %s%s" % ("b/" + fn2, datetag(bd))
         l3 = "@@ -1,%d +0,0 @@\n" % len(a)
         l = [l1, l2, l3] + ["-" + e for e in a]
     else:
         al = splitnewlines(a)
         bl = splitnewlines(b)
         l = list(_unidiff(a, b, al, bl, opts=opts))
         if not l:
             return ""
 
         l.insert(0, "--- a/%s%s" % (fn1, datetag(ad)))
         l.insert(1, "+++ b/%s%s" % (fn2, datetag(bd)))
 
     for ln in xrange(len(l)):
         if l[ln][-1] != '\n':
             l[ln] += "\n\ No newline at end of file\n"
 
     if r:
         l.insert(0, diffline(r, fn1, fn2, opts))
 
     return "".join(l)
 
 # creates a headerless unified diff
 # t1 and t2 are the text to be diffed
 # l1 and l2 are the text broken up into lines
 def _unidiff(t1, t2, l1, l2, opts=defaultopts):
     def contextend(l, len):
         ret = l + opts.context
         if ret > len:
             ret = len
         return ret
 
     def contextstart(l):
         ret = l - opts.context
         if ret < 0:
             return 0
         return ret
 
     lastfunc = [0, '']
     def yieldhunk(hunk):
         (astart, a2, bstart, b2, delta) = hunk
         aend = contextend(a2, len(l1))
         alen = aend - astart
         blen = b2 - bstart + aend - a2
 
         func = ""
         if opts.showfunc:
             lastpos, func = lastfunc
             # walk backwards from the start of the context up to the start of
             # the previous hunk context until we find a line starting with an
             # alphanumeric char.
             for i in xrange(astart - 1, lastpos - 1, -1):
                 if l1[i][0].isalnum():
                     func = ' ' + l1[i].rstrip()[:40]
                     lastfunc[1] = func
                     break
             # by recording this hunk's starting point as the next place to
             # start looking for function lines, we avoid reading any line in
             # the file more than once.
             lastfunc[0] = astart
 
         # zero-length hunk ranges report their start line as one less
         if alen:
             astart += 1
         if blen:
             bstart += 1
 
         yield "@@ -%d,%d +%d,%d @@%s\n" % (astart, alen,
                                            bstart, blen, func)
         for x in delta:
             yield x
         for x in xrange(a2, aend):
             yield ' ' + l1[x]
 
     # bdiff.blocks gives us the matching sequences in the files.  The loop
     # below finds the spaces between those matching sequences and translates
     # them into diff output.
     #
     hunk = None
     for s, stype in allblocks(t1, t2, opts, l1, l2):
         if stype != '!':
             continue
         delta = []
         a1, a2, b1, b2 = s
         old = l1[a1:a2]
         new = l2[b1:b2]
 
         astart = contextstart(a1)
         bstart = contextstart(b1)
         prev = None
         if hunk:
             # join with the previous hunk if it falls inside the context
             if astart < hunk[1] + opts.context + 1:
                 prev = hunk
                 astart = hunk[1]
                 bstart = hunk[3]
             else:
                 for x in yieldhunk(hunk):
                     yield x
         if prev:
             # we've joined the previous hunk, record the new ending points.
             hunk[1] = a2
             hunk[3] = b2
             delta = hunk[4]
         else:
             # create a new hunk
             hunk = [astart, a2, bstart, b2, delta]
 
         delta[len(delta):] = [' ' + x for x in l1[astart:a1]]
         delta[len(delta):] = ['-' + x for x in old]
         delta[len(delta):] = ['+' + x for x in new]
 
     if hunk:
         for x in yieldhunk(hunk):
             yield x
 
 def patchtext(bin):
     pos = 0
     t = []
     while pos < len(bin):
         p1, p2, l = struct.unpack(">lll", bin[pos:pos + 12])
         pos += 12
         t.append(bin[pos:pos + l])
         pos += l
     return "".join(t)
 
 def patch(a, bin):
     if len(a) == 0:
         # skip over trivial delta header
         return buffer(bin, 12)
     return mpatch.patches(a, [bin])
 
 # similar to difflib.SequenceMatcher.get_matching_blocks
 def get_matching_blocks(a, b):
     return [(d[0], d[2], d[1] - d[0]) for d in bdiff.blocks(a, b)]
 
 def trivialdiffheader(length):
     return struct.pack(">lll", 0, 0, length)
 
 patches = mpatch.patches
 patchedsize = mpatch.patchedsize
 textdiff = bdiff.bdiff

mercurial/pure/bdiff.py

@@ -1,80 +1,87 b''
 # bdiff.py - Python implementation of bdiff.c
 #
 # Copyright 2009 Matt Mackall <[e-mail]> and others
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
-import struct, difflib
+import struct, difflib, re
 
 def splitnewlines(text):
     '''like str.splitlines, but only split on newlines.'''
     lines = [l + '\n' for l in text.split('\n')]
     if lines:
         if lines[-1] == '\n':
             lines.pop()
         else:
             lines[-1] = lines[-1][:-1]
     return lines
 
 def _normalizeblocks(a, b, blocks):
     prev = None
     r = []
     for curr in blocks:
         if prev is None:
             prev = curr
             continue
         shift = 0
 
         a1, b1, l1 = prev
         a1end = a1 + l1
         b1end = b1 + l1
 
         a2, b2, l2 = curr
         a2end = a2 + l2
         b2end = b2 + l2
         if a1end == a2:
             while (a1end + shift < a2end and
                    a[a1end + shift] == b[b1end + shift]):
                 shift += 1
         elif b1end == b2:
             while (b1end + shift < b2end and
                    a[a1end + shift] == b[b1end + shift]):
                 shift += 1
         r.append((a1, b1, l1 + shift))
         prev = a2 + shift, b2 + shift, l2 - shift
     r.append(prev)
     return r
 
 def bdiff(a, b):
     a = str(a).splitlines(True)
     b = str(b).splitlines(True)
 
     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()
     d = _normalizeblocks(a, b, d)
     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 = splitnewlines(a)
     bn = splitnewlines(b)
     d = difflib.SequenceMatcher(None, an, bn).get_matching_blocks()
     d = _normalizeblocks(an, bn, d)
     return [(i, i + n, j, j + n) for (i, j, n) in d]
 
+def fixws(text, allws):
+    if allws:
+        text = re.sub('[ \t\r]+', '', text)
+    else:
+        text = re.sub('[ \t\r]+', ' ', text)
+        text = text.replace(' \n', '\n')
+    return text

tests/test-bdiff.py

@@ -1,52 +1,66 b''
 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 "***", repr(a), repr(b)
         print "bad:"
         print repr(c)[:200]
         print repr(d)
 
 def test(a, b):
     print "***", 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):
     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"
+
+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"

tests/test-bdiff.py.out

@@ -1,23 +1,24 b''
 *** 'a\nc\n\n\n\n' 'a\nb\n\n\n'
 *** 'a\nb\nc\n' 'a\nc\n'
 *** '' ''
 *** 'a\nb\nc' 'a\nb\nc'
 *** 'a\nb\nc\nd\n' 'a\nd\n'
 *** 'a\nb\nc\nd\n' 'a\nc\ne\n'
 *** 'a\nb\nc\n' 'a\nc\n'
 *** 'a\n' 'c\na\nb\n'
 *** 'a\n' ''
 *** 'a\n' 'b\nc\n'
 *** 'a\n' 'c\na\n'
 *** '' 'adjfkjdjksdhfksj'
 *** '' 'ab'
 *** '' 'abc'
 *** 'a' 'a'
 *** 'ab' 'ab'
 *** '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
+done