This is an archive of the discontinued Mercurial Phabricator instance.

Differential D2602

bdiff: add a xdiffblocks method
ClosedPublic

Authored by quark on Mar 3 2018, 3:07 PM.

Details

Reviewers
indygreg
durin42
Group Reviewers
hg-reviewers
Commits
rHG430fdb717549: bdiff: add a xdiffblocks method
rHGd74589c85f5e: bdiff: add a xdiffblocks method
Summary

This is similar to bdiff.blocks, but uses xdiff as the backend.

The indent heuristic is turned on by default since it has little overhead
and improves diff quality significantly.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

quark created this revision.Mar 3 2018, 3:07 PM
quark updated this revision to Diff 6476.Mar 3 2018, 3:30 PM
indygreg accepted this revision.Mar 3 2018, 4:19 PM
indygreg added a subscriber: indygreg.
indygreg added inline comments.
mercurial/cext/bdiff.c
266

Calling PyList_Append() in tight loops can be a bit slow. It is faster to allocate an array of PyObject and then allocate a PyList of final size and call PyList_SET_ITEM to populate it. But we can optimize this later: this is definitely the easiest first implementation.

290

Does our C standard level allow to declare variables after non-declarations in blocks?

310

This exception type is nonsensical. But it is what blocks() uses. So not worth worrying about.

This revision is now accepted and ready to land.Mar 3 2018, 4:19 PM
quark added inline comments.Mar 3 2018, 4:25 PM
mercurial/cext/bdiff.c
290

Not sure. But the rest is C89. So I'll move this up.

310

It actually makes some sense - if the xdiff library is solid, then hunk_consumer returning -1 is the only reason things go wrong. And that's caused by NoMemory.

quark added inline comments.Mar 3 2018, 4:26 PM
mercurial/cext/bdiff.c
266

Ideally, xdiff could return how many lines the input string has. So we can preallocate. But it's not in the current xdiff API.

quark updated this revision to Diff 6480.Mar 3 2018, 4:31 PM
durin42 accepted this revision.Mar 3 2018, 6:12 PM
Closed by commit rHGd74589c85f5e: bdiff: add a xdiffblocks method (authored by quark). · Explain WhyMar 3 2018, 6:40 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/cext/bdiff.c (63 lines)
Mmercurial/policy.py (2 lines)
Msetup.py (23 lines)

Diff 6516

mercurial/cext/bdiff.c

#define PY_SSIZE_T_CLEAN #define PY_SSIZE_T_CLEAN
#include <Python.h> #include <Python.h>
#include <limits.h> #include <limits.h>
#include <stdlib.h> #include <stdlib.h>
#include <string.h> #include <string.h>
#include "bdiff.h" #include "bdiff.h"
#include "bitmanipulation.h" #include "bitmanipulation.h"
#include "thirdparty/xdiff/xdiff.h"
#include "util.h" #include "util.h"
static PyObject *blocks(PyObject *self, PyObject *args) static PyObject *blocks(PyObject *self, PyObject *args)
{ {
PyObject *sa, *sb, *rl = NULL, *m; PyObject *sa, *sb, *rl = NULL, *m;
struct bdiff_line *a, *b; struct bdiff_line *a, *b;
struct bdiff_hunk l, *h; struct bdiff_hunk l, *h;
int an, bn, count, pos = 0; int an, bn, count, pos = 0;
if (!sliceintolist(result, nelts++, text + start, size - start)) if (!sliceintolist(result, nelts++, text + start, size - start))
goto abort; goto abort;
return result; return result;
abort: abort:
Py_XDECREF(result); Py_XDECREF(result);
return NULL; 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) {
indygregUnsubmitted
Not Done

Calling PyList_Append() in tight loops can be a bit slow. It is faster to allocate an array of PyObject and then allocate a PyList of final size and call PyList_SET_ITEM to populate it. But we can optimize this later: this is definitely the easiest first implementation.

indygreg: Calling `PyList_Append()` in tight loops can be a bit slow. It is faster to allocate an array…
quarkAuthorUnsubmitted
Not Done

Ideally, xdiff could return how many lines the input string has. So we can preallocate. But it's not in the current xdiff API.

quark: Ideally, xdiff could return how many lines the input string has. So we can preallocate. But…
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 */
NULL, /* anchors */
0, /* anchors_nr */
};
xdemitconf_t xecfg = {
0, /* ctxlen */
0, /* interhunkctxlen */
XDL_EMIT_BDIFFHUNK, /* flags */
NULL, /* find_func */
NULL, /* find_func_priv */
hunk_consumer, /* hunk_consume_func */
indygregUnsubmitted
Not Done

Does our C standard level allow to declare variables after non-declarations in blocks?

indygreg: Does our C standard level allow to declare variables after non-declarations in blocks?
quarkAuthorUnsubmitted
Not Done

Not sure. But the rest is C89. So I'll move this up.

quark: Not sure. But the rest is C89. So I'll move this up.
};
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) {
indygregUnsubmitted
Not Done

This exception type is nonsensical. But it is what blocks() uses. So not worth worrying about.

indygreg: This exception type is nonsensical. But it is what `blocks()` uses. So not worth worrying about.
quarkAuthorUnsubmitted
Not Done

It actually makes some sense - if the xdiff library is solid, then hunk_consumer returning -1 is the only reason things go wrong. And that's caused by NoMemory.

quark: It actually makes some sense - if the xdiff library is solid, then `hunk_consumer` returning -1…
Py_DECREF(rl);
return PyErr_NoMemory();
}
return rl;
}
static char mdiff_doc[] = "Efficient binary diff."; static char mdiff_doc[] = "Efficient binary diff.";
static PyMethodDef methods[] = { static PyMethodDef methods[] = {
{"bdiff", bdiff, METH_VARARGS, "calculate a binary diff\n"}, {"bdiff", bdiff, METH_VARARGS, "calculate a binary diff\n"},
{"blocks", blocks, METH_VARARGS, "find a list of matching lines\n"}, {"blocks", blocks, METH_VARARGS, "find a list of matching lines\n"},
{"fixws", fixws, METH_VARARGS, "normalize diff whitespaces\n"}, {"fixws", fixws, METH_VARARGS, "normalize diff whitespaces\n"},
{"splitnewlines", splitnewlines, METH_VARARGS, {"splitnewlines", splitnewlines, METH_VARARGS,
"like str.splitlines, but only split on newlines\n"}, "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}, {NULL, NULL},
}; };
static const int version = 2; static const int version = 3;
#ifdef IS_PY3K #ifdef IS_PY3K
static struct PyModuleDef bdiff_module = { static struct PyModuleDef bdiff_module = {
PyModuleDef_HEAD_INIT, "bdiff", mdiff_doc, -1, methods, PyModuleDef_HEAD_INIT, "bdiff", mdiff_doc, -1, methods,
}; };
PyMODINIT_FUNC PyInit_bdiff(void) PyMODINIT_FUNC PyInit_bdiff(void)
{ {

mercurial/policy.py

raise ImportError(r'cannot import name %s' % modname) raise ImportError(r'cannot import name %s' % modname)
# force import; fakelocals[modname] may be replaced with the real module # force import; fakelocals[modname] may be replaced with the real module
getattr(mod, r'__doc__', None) getattr(mod, r'__doc__', None)
return fakelocals[modname] return fakelocals[modname]
# keep in sync with "version" in C modules # keep in sync with "version" in C modules
_cextversions = { _cextversions = {
(r'cext', r'base85'): 1, (r'cext', r'base85'): 1,
(r'cext', r'bdiff'): 2, (r'cext', r'bdiff'): 3,
(r'cext', r'diffhelpers'): 1, (r'cext', r'diffhelpers'): 1,
(r'cext', r'mpatch'): 1, (r'cext', r'mpatch'): 1,
(r'cext', r'osutil'): 3, (r'cext', r'osutil'): 3,
(r'cext', r'parsers'): 4, (r'cext', r'parsers'): 4,
} }
# map import request to other package or module # map import request to other package or module
_modredirects = { _modredirects = {

setup.py

'''), '''),
]: ]:
if re.search(plat, sys.platform) and cancompile(new_compiler(), code): if re.search(plat, sys.platform) and cancompile(new_compiler(), code):
osutil_cflags.append('-DHAVE_%s' % macro) osutil_cflags.append('-DHAVE_%s' % macro)
if sys.platform == 'darwin': if sys.platform == 'darwin':
osutil_ldflags += ['-framework', 'ApplicationServices'] osutil_ldflags += ['-framework', 'ApplicationServices']
xdiff_srcs = [
'mercurial/thirdparty/xdiff/xdiffi.c',
'mercurial/thirdparty/xdiff/xemit.c',
'mercurial/thirdparty/xdiff/xmerge.c',
'mercurial/thirdparty/xdiff/xprepare.c',
'mercurial/thirdparty/xdiff/xutils.c',
]
xdiff_headers = [
'mercurial/thirdparty/xdiff/xdiff.h',
'mercurial/thirdparty/xdiff/xdiffi.h',
'mercurial/thirdparty/xdiff/xemit.h',
'mercurial/thirdparty/xdiff/xinclude.h',
'mercurial/thirdparty/xdiff/xmacros.h',
'mercurial/thirdparty/xdiff/xprepare.h',
'mercurial/thirdparty/xdiff/xtypes.h',
'mercurial/thirdparty/xdiff/xutils.h',
]
extmodules = [ extmodules = [
Extension('mercurial.cext.base85', ['mercurial/cext/base85.c'], Extension('mercurial.cext.base85', ['mercurial/cext/base85.c'],
include_dirs=common_include_dirs, include_dirs=common_include_dirs,
depends=common_depends), depends=common_depends),
Extension('mercurial.cext.bdiff', ['mercurial/bdiff.c', Extension('mercurial.cext.bdiff', ['mercurial/bdiff.c',
'mercurial/cext/bdiff.c'], 'mercurial/cext/bdiff.c'] + xdiff_srcs,
include_dirs=common_include_dirs, include_dirs=common_include_dirs,
depends=common_depends + ['mercurial/bdiff.h']), depends=common_depends + ['mercurial/bdiff.h'] + xdiff_headers),
Extension('mercurial.cext.diffhelpers', ['mercurial/cext/diffhelpers.c'], Extension('mercurial.cext.diffhelpers', ['mercurial/cext/diffhelpers.c'],
include_dirs=common_include_dirs, include_dirs=common_include_dirs,
depends=common_depends), depends=common_depends),
Extension('mercurial.cext.mpatch', ['mercurial/mpatch.c', Extension('mercurial.cext.mpatch', ['mercurial/mpatch.c',
'mercurial/cext/mpatch.c'], 'mercurial/cext/mpatch.c'],
include_dirs=common_include_dirs, include_dirs=common_include_dirs,
depends=common_depends), depends=common_depends),
Extension('mercurial.cext.parsers', ['mercurial/cext/charencode.c', Extension('mercurial.cext.parsers', ['mercurial/cext/charencode.c',