|
|
/*
|
|
|
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);
|
|
|
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(long a1, long a2, long b1, long 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 = {
|
|
|
0, /* ctxlen */
|
|
|
0, /* interhunkctxlen */
|
|
|
XDL_EMIT_BDIFFHUNK, /* flags */
|
|
|
NULL, /* find_func */
|
|
|
NULL, /* find_func_priv */
|
|
|
hunk_consumer, /* hunk_consume_func */
|
|
|
};
|
|
|
xdemitcb_t ecb = {
|
|
|
NULL, /* priv */
|
|
|
NULL, /* outf */
|
|
|
};
|
|
|
|
|
|
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
|
|
|
|