/*
bdiff.c - efficient binary diff extension for Mercurial
Copyright 2005, 2006 Matt Mackall <mpm@selenic.com>
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);
free(al);
free(bl);
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);
int r;
if (!m) {
return -1;
}
r = PyList_Append(rl, m);
Py_DECREF(m);
return r;
}
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