view mercurial/cext/bdiff.c @ 37711:65a23cc8e75b

cborutil: implement support for streaming encoding, bytestring decoding

The vendored cbor2 package is... a bit disappointing.

On the encoding side, it insists that you pass it something with
a write() to send data to. That means if you want to emit data to
a generator, you have to construct an e.g. io.BytesIO(), write()
to it, then get the data back out. There can be non-trivial overhead
involved.

The encoder also doesn't support indefinite types - bytestrings, arrays,
and maps that don't have a known length. Again, this is really
unfortunate because it requires you to buffer the entire source and
destination in memory to encode large things.

On the decoding side, it supports reading indefinite length types.
But it buffers them completely before returning. More sadness.

This commit implements "streaming" encoders for various CBOR types.
Encoding emits a generator of hunks. So you can efficiently stream
encoded data elsewhere.

It also implements support for emitting indefinite length bytestrings,
arrays, and maps.

On the decoding side, we only implement support for decoding an
indefinite length bytestring from a file object. It will emit a
generator of raw chunks from the source.

I didn't want to reinvent so many wheels. But profiling the wire
protocol revealed that the overhead of constructing io.BytesIO()
instances to temporarily hold results has a non-trivial overhead.
We're talking >15% of execution time for operations like
"transfer the fulltexts of all files in a revision." So I can
justify this effort.

Fortunately, CBOR is a relatively straightforward format. And we have
a reference implementation in the repo we can test against.

Differential Revision: https://phab.mercurial-scm.org/D3303

/*
 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
*/

#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

#include "bdiff.h"
#include "bitmanipulation.h"
#include "thirdparty/xdiff/xdiff.h"
#include "util.h"

static PyObject *blocks(PyObject *self, PyObject *args)
{
	PyObject *sa, *sb, *rl = NULL, *m;
	struct bdiff_line *a, *b;
	struct bdiff_hunk l, *h;
	int an, bn, count, pos = 0;

	l.next = NULL;

	if (!PyArg_ParseTuple(args, "SS:bdiff", &sa, &sb))
		return NULL;

	an = bdiff_splitlines(PyBytes_AsString(sa), PyBytes_Size(sa), &a);
	bn = bdiff_splitlines(PyBytes_AsString(sb), PyBytes_Size(sb), &b);

	if (!a || !b)
		goto nomem;

	count = bdiff_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);
	bdiff_freehunks(l.next);
	return rl ? rl : PyErr_NoMemory();
}

static PyObject *bdiff(PyObject *self, PyObject *args)
{
	Py_buffer ba, bb;
	char *rb, *ia, *ib;
	PyObject *result = NULL;
	struct bdiff_line *al = NULL, *bl = NULL;
	struct bdiff_hunk l, *h;
	int an, bn, count;
	Py_ssize_t len = 0, la, lb, li = 0, lcommon = 0, lmax;
	PyThreadState *_save = NULL;

	l.next = NULL;

	if (!PyArg_ParseTuple(args, PY23("s*s*:bdiff", "y*y*:bdiff"), &ba, &bb))
		return NULL;

	if (!PyBuffer_IsContiguous(&ba, 'C') || ba.ndim > 1) {
		PyErr_SetString(PyExc_ValueError, "bdiff input not contiguous");
		goto cleanup;
	}

	if (!PyBuffer_IsContiguous(&bb, 'C') || bb.ndim > 1) {
		PyErr_SetString(PyExc_ValueError, "bdiff input not contiguous");
		goto cleanup;
	}

	la = ba.len;
	lb = bb.len;

	if (la > UINT_MAX || lb > UINT_MAX) {
		PyErr_SetString(PyExc_ValueError, "bdiff inputs too large");
		goto cleanup;
	}

	_save = PyEval_SaveThread();

	lmax = la > lb ? lb : la;
	for (ia = ba.buf, ib = bb.buf; li < lmax && *ia == *ib;
	     ++li, ++ia, ++ib) {
		if (*ia == '\n')
			lcommon = li + 1;
	}
	/* we can almost add: if (li == lmax) lcommon = li; */

	an = bdiff_splitlines((char *)ba.buf + lcommon, la - lcommon, &al);
	bn = bdiff_splitlines((char *)bb.buf + lcommon, lb - lcommon, &bl);
	if (!al || !bl) {
		PyErr_NoMemory();
		goto cleanup;
	}

	count = bdiff_diff(al, an, bl, bn, &l);
	if (count < 0) {
		PyErr_NoMemory();
		goto cleanup;
	}

	/* 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;
	}
	PyEval_RestoreThread(_save);
	_save = NULL;

	result = PyBytes_FromStringAndSize(NULL, len);

	if (!result)
		goto cleanup;

	/* 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;
			putbe32((uint32_t)(al[la].l + lcommon - al->l), rb);
			putbe32((uint32_t)(al[h->a1].l + lcommon - al->l),
			        rb + 4);
			putbe32((uint32_t)len, rb + 8);
			memcpy(rb + 12, bl[lb].l, len);
			rb += 12 + len;
		}
		la = h->a2;
		lb = h->b2;
	}

cleanup:
	if (_save)
		PyEval_RestoreThread(_save);
	PyBuffer_Release(&ba);
	PyBuffer_Release(&bb);
	if (al) {
		free(al);
	}
	if (bl) {
		free(bl);
	}
	if (l.next) {
		bdiff_freehunks(l.next);
	}
	return result;
}

/*
 * 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;
	Py_ssize_t 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 *)PyMem_Malloc(rlen ? rlen : 1);
	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:
	PyMem_Free(w);
	return result ? result : PyErr_NoMemory();
}

static bool sliceintolist(PyObject *list, Py_ssize_t destidx,
                          const char *source, Py_ssize_t len)
{
	PyObject *sliced = PyBytes_FromStringAndSize(source, len);
	if (sliced == NULL)
		return false;
	PyList_SET_ITEM(list, destidx, sliced);
	return true;
}

static PyObject *splitnewlines(PyObject *self, PyObject *args)
{
	const char *text;
	Py_ssize_t nelts = 0, size, i, start = 0;
	PyObject *result = NULL;

	if (!PyArg_ParseTuple(args, PY23("s#", "y#"), &text, &size)) {
		goto abort;
	}
	if (!size) {
		return PyList_New(0);
	}
	/* This loops to size-1 because if the last byte is a newline,
	 * we don't want to perform a split there. */
	for (i = 0; i < size - 1; ++i) {
		if (text[i] == '\n') {
			++nelts;
		}
	}
	if ((result = PyList_New(nelts + 1)) == NULL)
		goto abort;
	nelts = 0;
	for (i = 0; i < size - 1; ++i) {
		if (text[i] == '\n') {
			if (!sliceintolist(result, nelts++, text + start,
			                   i - start + 1))
				goto abort;
			start = i + 1;
		}
	}
	if (!sliceintolist(result, nelts++, text + start, size - start))
		goto abort;
	return result;
abort:
	Py_XDECREF(result);
	return NULL;
}

static int hunk_consumer(int64_t a1, int64_t a2, int64_t b1, int64_t b2,
                         void *priv)
{
	PyObject *rl = (PyObject *)priv;
	PyObject *m = Py_BuildValue("llll", a1, a2, b1, b2);
	if (!m)
		return -1;
	if (PyList_Append(rl, m) != 0) {
		Py_DECREF(m);
		return -1;
	}
	return 0;
}

static PyObject *xdiffblocks(PyObject *self, PyObject *args)
{
	Py_ssize_t la, lb;
	mmfile_t a, b;
	PyObject *rl;

	xpparam_t xpp = {
	    XDF_INDENT_HEURISTIC, /* flags */
	};
	xdemitconf_t xecfg = {
	    XDL_EMIT_BDIFFHUNK, /* flags */
	    hunk_consumer,      /* hunk_consume_func */
	};
	xdemitcb_t ecb = {
	    NULL, /* priv */
	};

	if (!PyArg_ParseTuple(args, PY23("s#s#", "y#y#"), &a.ptr, &la, &b.ptr,
	                      &lb))
		return NULL;

	a.size = la;
	b.size = lb;

	rl = PyList_New(0);
	if (!rl)
		return PyErr_NoMemory();

	ecb.priv = rl;

	if (xdl_diff(&a, &b, &xpp, &xecfg, &ecb) != 0) {
		Py_DECREF(rl);
		return PyErr_NoMemory();
	}

	return rl;
}

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"},
    {"splitnewlines", splitnewlines, METH_VARARGS,
     "like str.splitlines, but only split on newlines\n"},
    {"xdiffblocks", xdiffblocks, METH_VARARGS,
     "find a list of matching lines using xdiff algorithm\n"},
    {NULL, NULL},
};

static const int version = 3;

#ifdef IS_PY3K
static struct PyModuleDef bdiff_module = {
    PyModuleDef_HEAD_INIT, "bdiff", mdiff_doc, -1, methods,
};

PyMODINIT_FUNC PyInit_bdiff(void)
{
	PyObject *m;
	m = PyModule_Create(&bdiff_module);
	PyModule_AddIntConstant(m, "version", version);
	return m;
}
#else
PyMODINIT_FUNC initbdiff(void)
{
	PyObject *m;
	m = Py_InitModule3("bdiff", methods, mdiff_doc);
	PyModule_AddIntConstant(m, "version", version);
}
#endif