cext: reorder #include

We mostly abide by this style.

In one case, a blank line was inserted to prevent a local
`#include "file"` from coming before a `#include <file>`.

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

mercurial/cext/bdiff.c

@@ -1,220 +1,220 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
 */
 
 #define PY_SSIZE_T_CLEAN
 #include <Python.h>
+#include <limits.h>
 #include <stdlib.h>
 #include <string.h>
-#include <limits.h>
 
 #include "bdiff.h"
 #include "bitmanipulation.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)
 {
 	char *sa, *sb, *rb, *ia, *ib;
 	PyObject *result = NULL;
 	struct bdiff_line *al, *bl;
 	struct bdiff_hunk l, *h;
 	int an, bn, count;
 	Py_ssize_t len = 0, la, lb, li = 0, lcommon = 0, lmax;
 	PyThreadState *_save;
 
 	l.next = NULL;
 
 	if (!PyArg_ParseTuple(args, "s#s#:bdiff", &sa, &la, &sb, &lb))
 		return NULL;
 
 	if (la > UINT_MAX || lb > UINT_MAX) {
 		PyErr_SetString(PyExc_ValueError, "bdiff inputs too large");
 		return NULL;
 	}
 
 	_save = PyEval_SaveThread();
 
 	lmax = la > lb ? lb : la;
 	for (ia = sa, ib = sb;
 	     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(sa + lcommon, la - lcommon, &al);
 	bn = bdiff_splitlines(sb + lcommon, lb - lcommon, &bl);
 	if (!al || !bl)
 		goto nomem;
 
 	count = bdiff_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;
 	}
 	PyEval_RestoreThread(_save);
 	_save = NULL;
 
 	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;
 			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;
 	}
 
 nomem:
 	if (_save)
 		PyEval_RestoreThread(_save);
 	free(al);
 	free(bl);
 	bdiff_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;
 	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 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}
 };
 
 static const int version = 1;
 
 #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

mercurial/cext/dirs.c

@@ -1,315 +1,316 b''
 /*
  dirs.c - dynamic directory diddling for dirstates
 
  Copyright 2013 Facebook
 
  This software may be used and distributed according to the terms of
  the GNU General Public License, incorporated herein by reference.
 */
 
 #define PY_SSIZE_T_CLEAN
 #include <Python.h>
+
 #include "util.h"
 
 #ifdef IS_PY3K
 #define PYLONG_VALUE(o) ((PyLongObject *)o)->ob_digit[1]
 #else
 #define PYLONG_VALUE(o) PyInt_AS_LONG(o)
 #endif
 
 /*
  * This is a multiset of directory names, built from the files that
  * appear in a dirstate or manifest.
  *
  * A few implementation notes:
  *
  * We modify Python integers for refcounting, but those integers are
  * never visible to Python code.
  *
  * We mutate strings in-place, but leave them immutable once they can
  * be seen by Python code.
  */
 typedef struct {
 	PyObject_HEAD
 	PyObject *dict;
 } dirsObject;
 
 static inline Py_ssize_t _finddir(const char *path, Py_ssize_t pos)
 {
 	while (pos != -1) {
 		if (path[pos] == '/')
 			break;
 		pos -= 1;
 	}
 
 	return pos;
 }
 
 static int _addpath(PyObject *dirs, PyObject *path)
 {
 	const char *cpath = PyBytes_AS_STRING(path);
 	Py_ssize_t pos = PyBytes_GET_SIZE(path);
 	PyObject *key = NULL;
 	int ret = -1;
 
 	/* This loop is super critical for performance. That's why we inline
 	* access to Python structs instead of going through a supported API.
 	* The implementation, therefore, is heavily dependent on CPython
 	* implementation details. We also commit violations of the Python
 	* "protocol" such as mutating immutable objects. But since we only
 	* mutate objects created in this function or in other well-defined
 	* locations, the references are known so these violations should go
 	* unnoticed. The code for adjusting the length of a PyBytesObject is
 	* essentially a minimal version of _PyBytes_Resize. */
 	while ((pos = _finddir(cpath, pos - 1)) != -1) {
 		PyObject *val;
 
 		/* It's likely that every prefix already has an entry
 		   in our dict. Try to avoid allocating and
 		   deallocating a string for each prefix we check. */
 		if (key != NULL)
 			((PyBytesObject *)key)->ob_shash = -1;
 		else {
 			/* Force Python to not reuse a small shared string. */
 			key = PyBytes_FromStringAndSize(cpath,
 							 pos < 2 ? 2 : pos);
 			if (key == NULL)
 				goto bail;
 		}
 		/* Py_SIZE(o) refers to the ob_size member of the struct. Yes,
 		* assigning to what looks like a function seems wrong. */
 		Py_SIZE(key) = pos;
 		((PyBytesObject *)key)->ob_sval[pos] = '\0';
 
 		val = PyDict_GetItem(dirs, key);
 		if (val != NULL) {
 			PYLONG_VALUE(val) += 1;
 			break;
 		}
 
 		/* Force Python to not reuse a small shared int. */
 #ifdef IS_PY3K
 		val = PyLong_FromLong(0x1eadbeef);
 #else
 		val = PyInt_FromLong(0x1eadbeef);
 #endif
 
 		if (val == NULL)
 			goto bail;
 
 		PYLONG_VALUE(val) = 1;
 		ret = PyDict_SetItem(dirs, key, val);
 		Py_DECREF(val);
 		if (ret == -1)
 			goto bail;
 		Py_CLEAR(key);
 	}
 	ret = 0;
 
 bail:
 	Py_XDECREF(key);
 
 	return ret;
 }
 
 static int _delpath(PyObject *dirs, PyObject *path)
 {
 	char *cpath = PyBytes_AS_STRING(path);
 	Py_ssize_t pos = PyBytes_GET_SIZE(path);
 	PyObject *key = NULL;
 	int ret = -1;
 
 	while ((pos = _finddir(cpath, pos - 1)) != -1) {
 		PyObject *val;
 
 		key = PyBytes_FromStringAndSize(cpath, pos);
 
 		if (key == NULL)
 			goto bail;
 
 		val = PyDict_GetItem(dirs, key);
 		if (val == NULL) {
 			PyErr_SetString(PyExc_ValueError,
 					"expected a value, found none");
 			goto bail;
 		}
 
 		if (--PYLONG_VALUE(val) <= 0) {
 			if (PyDict_DelItem(dirs, key) == -1)
 				goto bail;
 		} else
 			break;
 		Py_CLEAR(key);
 	}
 	ret = 0;
 
 bail:
 	Py_XDECREF(key);
 
 	return ret;
 }
 
 static int dirs_fromdict(PyObject *dirs, PyObject *source, char skipchar)
 {
 	PyObject *key, *value;
 	Py_ssize_t pos = 0;
 
 	while (PyDict_Next(source, &pos, &key, &value)) {
 		if (!PyBytes_Check(key)) {
 			PyErr_SetString(PyExc_TypeError, "expected string key");
 			return -1;
 		}
 		if (skipchar) {
 			if (!dirstate_tuple_check(value)) {
 				PyErr_SetString(PyExc_TypeError,
 						"expected a dirstate tuple");
 				return -1;
 			}
 			if (((dirstateTupleObject *)value)->state == skipchar)
 				continue;
 		}
 
 		if (_addpath(dirs, key) == -1)
 			return -1;
 	}
 
 	return 0;
 }
 
 static int dirs_fromiter(PyObject *dirs, PyObject *source)
 {
 	PyObject *iter, *item = NULL;
 	int ret;
 
 	iter = PyObject_GetIter(source);
 	if (iter == NULL)
 		return -1;
 
 	while ((item = PyIter_Next(iter)) != NULL) {
 		if (!PyBytes_Check(item)) {
 			PyErr_SetString(PyExc_TypeError, "expected string");
 			break;
 		}
 
 		if (_addpath(dirs, item) == -1)
 			break;
 		Py_CLEAR(item);
 	}
 
 	ret = PyErr_Occurred() ? -1 : 0;
 	Py_DECREF(iter);
 	Py_XDECREF(item);
 	return ret;
 }
 
 /*
  * Calculate a refcounted set of directory names for the files in a
  * dirstate.
  */
 static int dirs_init(dirsObject *self, PyObject *args)
 {
 	PyObject *dirs = NULL, *source = NULL;
 	char skipchar = 0;
 	int ret = -1;
 
 	self->dict = NULL;
 
 	if (!PyArg_ParseTuple(args, "|Oc:__init__", &source, &skipchar))
 		return -1;
 
 	dirs = PyDict_New();
 
 	if (dirs == NULL)
 		return -1;
 
 	if (source == NULL)
 		ret = 0;
 	else if (PyDict_Check(source))
 		ret = dirs_fromdict(dirs, source, skipchar);
 	else if (skipchar)
 		PyErr_SetString(PyExc_ValueError,
 				"skip character is only supported "
 				"with a dict source");
 	else
 		ret = dirs_fromiter(dirs, source);
 
 	if (ret == -1)
 		Py_XDECREF(dirs);
 	else
 		self->dict = dirs;
 
 	return ret;
 }
 
 PyObject *dirs_addpath(dirsObject *self, PyObject *args)
 {
 	PyObject *path;
 
 	if (!PyArg_ParseTuple(args, "O!:addpath", &PyBytes_Type, &path))
 		return NULL;
 
 	if (_addpath(self->dict, path) == -1)
 		return NULL;
 
 	Py_RETURN_NONE;
 }
 
 static PyObject *dirs_delpath(dirsObject *self, PyObject *args)
 {
 	PyObject *path;
 
 	if (!PyArg_ParseTuple(args, "O!:delpath", &PyBytes_Type, &path))
 		return NULL;
 
 	if (_delpath(self->dict, path) == -1)
 		return NULL;
 
 	Py_RETURN_NONE;
 }
 
 static int dirs_contains(dirsObject *self, PyObject *value)
 {
 	return PyBytes_Check(value) ? PyDict_Contains(self->dict, value) : 0;
 }
 
 static void dirs_dealloc(dirsObject *self)
 {
 	Py_XDECREF(self->dict);
 	PyObject_Del(self);
 }
 
 static PyObject *dirs_iter(dirsObject *self)
 {
 	return PyObject_GetIter(self->dict);
 }
 
 static PySequenceMethods dirs_sequence_methods;
 
 static PyMethodDef dirs_methods[] = {
 	{"addpath", (PyCFunction)dirs_addpath, METH_VARARGS, "add a path"},
 	{"delpath", (PyCFunction)dirs_delpath, METH_VARARGS, "remove a path"},
 	{NULL} /* Sentinel */
 };
 
 static PyTypeObject dirsType = { PyVarObject_HEAD_INIT(NULL, 0) };
 
 void dirs_module_init(PyObject *mod)
 {
 	dirs_sequence_methods.sq_contains = (objobjproc)dirs_contains;
 	dirsType.tp_name = "parsers.dirs";
 	dirsType.tp_new = PyType_GenericNew;
 	dirsType.tp_basicsize = sizeof(dirsObject);
 	dirsType.tp_dealloc = (destructor)dirs_dealloc;
 	dirsType.tp_as_sequence = &dirs_sequence_methods;
 	dirsType.tp_flags = Py_TPFLAGS_DEFAULT;
 	dirsType.tp_doc = "dirs";
 	dirsType.tp_iter = (getiterfunc)dirs_iter;
 	dirsType.tp_methods = dirs_methods;
 	dirsType.tp_init = (initproc)dirs_init;
 
 	if (PyType_Ready(&dirsType) < 0)
 		return;
 	Py_INCREF(&dirsType);
 
 	PyModule_AddObject(mod, "dirs", (PyObject *)&dirsType);
 }

mercurial/cext/manifest.c

@@ -1,937 +1,937 b''
 /*
  * manifest.c - manifest type that does on-demand parsing.
  *
  * Copyright 2015, Google Inc.
  *
  * This software may be used and distributed according to the terms of
  * the GNU General Public License, incorporated herein by reference.
  */
 #include <Python.h>
 
 #include <assert.h>
+#include <stdlib.h>
 #include <string.h>
-#include <stdlib.h>
 
 #include "charencode.h"
 #include "util.h"
 
 #define DEFAULT_LINES 100000
 
 typedef struct {
 	char *start;
 	Py_ssize_t len; /* length of line including terminal newline */
 	char hash_suffix;
 	bool from_malloc;
 	bool deleted;
 } line;
 
 typedef struct {
 	PyObject_HEAD
 	PyObject *pydata;
 	line *lines;
 	int numlines; /* number of line entries */
 	int livelines; /* number of non-deleted lines */
 	int maxlines; /* allocated number of lines */
 	bool dirty;
 } lazymanifest;
 
 #define MANIFEST_OOM -1
 #define MANIFEST_NOT_SORTED -2
 #define MANIFEST_MALFORMED -3
 
 /* get the length of the path for a line */
 static size_t pathlen(line *l) {
 	return strlen(l->start);
 }
 
 /* get the node value of a single line */
 static PyObject *nodeof(line *l) {
 	char *s = l->start;
 	ssize_t llen = pathlen(l);
 	PyObject *hash = unhexlify(s + llen + 1, 40);
 	if (!hash) {
 		return NULL;
 	}
 	if (l->hash_suffix != '\0') {
 		char newhash[21];
 		memcpy(newhash, PyBytes_AsString(hash), 20);
 		Py_DECREF(hash);
 		newhash[20] = l->hash_suffix;
 		hash = PyBytes_FromStringAndSize(newhash, 21);
 	}
 	return hash;
 }
 
 /* get the node hash and flags of a line as a tuple */
 static PyObject *hashflags(line *l)
 {
 	char *s = l->start;
 	size_t plen = pathlen(l);
 	PyObject *hash = nodeof(l);
 
 	/* 40 for hash, 1 for null byte, 1 for newline */
 	size_t hplen = plen + 42;
 	Py_ssize_t flen = l->len - hplen;
 	PyObject *flags;
 	PyObject *tup;
 
 	if (!hash)
 		return NULL;
 	flags = PyBytes_FromStringAndSize(s + hplen - 1, flen);
 	if (!flags) {
 		Py_DECREF(hash);
 		return NULL;
 	}
 	tup = PyTuple_Pack(2, hash, flags);
 	Py_DECREF(flags);
 	Py_DECREF(hash);
 	return tup;
 }
 
 /* if we're about to run out of space in the line index, add more */
 static bool realloc_if_full(lazymanifest *self)
 {
 	if (self->numlines == self->maxlines) {
 		self->maxlines *= 2;
 		self->lines = realloc(self->lines, self->maxlines * sizeof(line));
 	}
 	return !!self->lines;
 }
 
 /*
  * Find the line boundaries in the manifest that 'data' points to and store
  * information about each line in 'self'.
  */
 static int find_lines(lazymanifest *self, char *data, Py_ssize_t len)
 {
 	char *prev = NULL;
 	while (len > 0) {
 		line *l;
 		char *next = memchr(data, '\n', len);
 		if (!next) {
 			return MANIFEST_MALFORMED;
 		}
 		next++; /* advance past newline */
 		if (!realloc_if_full(self)) {
 			return MANIFEST_OOM; /* no memory */
 		}
 		if (prev && strcmp(prev, data) > -1) {
 			/* This data isn't sorted, so we have to abort. */
 			return MANIFEST_NOT_SORTED;
 		}
 		l = self->lines + ((self->numlines)++);
 		l->start = data;
 		l->len = next - data;
 		l->hash_suffix = '\0';
 		l->from_malloc = false;
 		l->deleted = false;
 		len = len - l->len;
 		prev = data;
 		data = next;
 	}
 	self->livelines = self->numlines;
 	return 0;
 }
 
 static int lazymanifest_init(lazymanifest *self, PyObject *args)
 {
 	char *data;
 	Py_ssize_t len;
 	int err, ret;
 	PyObject *pydata;
 	if (!PyArg_ParseTuple(args, "S", &pydata)) {
 		return -1;
 	}
 	err = PyBytes_AsStringAndSize(pydata, &data, &len);
 
 	self->dirty = false;
 	if (err == -1)
 		return -1;
 	self->pydata = pydata;
 	Py_INCREF(self->pydata);
 	Py_BEGIN_ALLOW_THREADS
 	self->lines = malloc(DEFAULT_LINES * sizeof(line));
 	self->maxlines = DEFAULT_LINES;
 	self->numlines = 0;
 	if (!self->lines)
 		ret = MANIFEST_OOM;
 	else
 		ret = find_lines(self, data, len);
 	Py_END_ALLOW_THREADS
 	switch (ret) {
 	case 0:
 		break;
 	case MANIFEST_OOM:
 		PyErr_NoMemory();
 		break;
 	case MANIFEST_NOT_SORTED:
 		PyErr_Format(PyExc_ValueError,
 			     "Manifest lines not in sorted order.");
 		break;
 	case MANIFEST_MALFORMED:
 		PyErr_Format(PyExc_ValueError,
 			     "Manifest did not end in a newline.");
 		break;
 	default:
 		PyErr_Format(PyExc_ValueError,
 			     "Unknown problem parsing manifest.");
 	}
 	return ret == 0 ? 0 : -1;
 }
 
 static void lazymanifest_dealloc(lazymanifest *self)
 {
 	/* free any extra lines we had to allocate */
 	int i;
 	for (i = 0; i < self->numlines; i++) {
 		if (self->lines[i].from_malloc) {
 			free(self->lines[i].start);
 		}
 	}
 	if (self->lines) {
 		free(self->lines);
 		self->lines = NULL;
 	}
 	if (self->pydata) {
 		Py_DECREF(self->pydata);
 		self->pydata = NULL;
 	}
 	PyObject_Del(self);
 }
 
 /* iteration support */
 
 typedef struct {
 	PyObject_HEAD lazymanifest *m;
 	Py_ssize_t pos;
 } lmIter;
 
 static void lmiter_dealloc(PyObject *o)
 {
 	lmIter *self = (lmIter *)o;
 	Py_DECREF(self->m);
 	PyObject_Del(self);
 }
 
 static line *lmiter_nextline(lmIter *self)
 {
 	do {
 		self->pos++;
 		if (self->pos >= self->m->numlines) {
 			return NULL;
 		}
 		/* skip over deleted manifest entries */
 	} while (self->m->lines[self->pos].deleted);
 	return self->m->lines + self->pos;
 }
 
 static PyObject *lmiter_iterentriesnext(PyObject *o)
 {
 	size_t pl;
 	line *l;
 	Py_ssize_t consumed;
 	PyObject *ret = NULL, *path = NULL, *hash = NULL, *flags = NULL;
 	l = lmiter_nextline((lmIter *)o);
 	if (!l) {
 		goto done;
 	}
 	pl = pathlen(l);
 	path = PyBytes_FromStringAndSize(l->start, pl);
 	hash = nodeof(l);
 	consumed = pl + 41;
 	flags = PyBytes_FromStringAndSize(l->start + consumed,
 					   l->len - consumed - 1);
 	if (!path || !hash || !flags) {
 		goto done;
 	}
 	ret = PyTuple_Pack(3, path, hash, flags);
 done:
 	Py_XDECREF(path);
 	Py_XDECREF(hash);
 	Py_XDECREF(flags);
 	return ret;
 }
 
 #ifdef IS_PY3K
 #define LAZYMANIFESTENTRIESITERATOR_TPFLAGS Py_TPFLAGS_DEFAULT
 #else
 #define LAZYMANIFESTENTRIESITERATOR_TPFLAGS Py_TPFLAGS_DEFAULT \
 	| Py_TPFLAGS_HAVE_ITER
 #endif
 
 static PyTypeObject lazymanifestEntriesIterator = {
 	PyVarObject_HEAD_INIT(NULL, 0)
 	"parsers.lazymanifest.entriesiterator", /*tp_name */
 	sizeof(lmIter),                  /*tp_basicsize */
 	0,                               /*tp_itemsize */
 	lmiter_dealloc,                  /*tp_dealloc */
 	0,                               /*tp_print */
 	0,                               /*tp_getattr */
 	0,                               /*tp_setattr */
 	0,                               /*tp_compare */
 	0,                               /*tp_repr */
 	0,                               /*tp_as_number */
 	0,                               /*tp_as_sequence */
 	0,                               /*tp_as_mapping */
 	0,                               /*tp_hash */
 	0,                               /*tp_call */
 	0,                               /*tp_str */
 	0,                               /*tp_getattro */
 	0,                               /*tp_setattro */
 	0,                               /*tp_as_buffer */
 	LAZYMANIFESTENTRIESITERATOR_TPFLAGS, /* tp_flags */
 	"Iterator for 3-tuples in a lazymanifest.",  /* tp_doc */
 	0,                               /* tp_traverse */
 	0,                               /* tp_clear */
 	0,                               /* tp_richcompare */
 	0,                               /* tp_weaklistoffset */
 	PyObject_SelfIter,               /* tp_iter: __iter__() method */
 	lmiter_iterentriesnext,          /* tp_iternext: next() method */
 };
 
 static PyObject *lmiter_iterkeysnext(PyObject *o)
 {
 	size_t pl;
 	line *l = lmiter_nextline((lmIter *)o);
 	if (!l) {
 		return NULL;
 	}
 	pl = pathlen(l);
 	return PyBytes_FromStringAndSize(l->start, pl);
 }
 
 #ifdef IS_PY3K
 #define LAZYMANIFESTKEYSITERATOR_TPFLAGS Py_TPFLAGS_DEFAULT
 #else
 #define LAZYMANIFESTKEYSITERATOR_TPFLAGS Py_TPFLAGS_DEFAULT \
 	| Py_TPFLAGS_HAVE_ITER
 #endif
 
 static PyTypeObject lazymanifestKeysIterator = {
 	PyVarObject_HEAD_INIT(NULL, 0)
 	"parsers.lazymanifest.keysiterator", /*tp_name */
 	sizeof(lmIter),                  /*tp_basicsize */
 	0,                               /*tp_itemsize */
 	lmiter_dealloc,                  /*tp_dealloc */
 	0,                               /*tp_print */
 	0,                               /*tp_getattr */
 	0,                               /*tp_setattr */
 	0,                               /*tp_compare */
 	0,                               /*tp_repr */
 	0,                               /*tp_as_number */
 	0,                               /*tp_as_sequence */
 	0,                               /*tp_as_mapping */
 	0,                               /*tp_hash */
 	0,                               /*tp_call */
 	0,                               /*tp_str */
 	0,                               /*tp_getattro */
 	0,                               /*tp_setattro */
 	0,                               /*tp_as_buffer */
 	LAZYMANIFESTKEYSITERATOR_TPFLAGS, /* tp_flags */
 	"Keys iterator for a lazymanifest.",  /* tp_doc */
 	0,                               /* tp_traverse */
 	0,                               /* tp_clear */
 	0,                               /* tp_richcompare */
 	0,                               /* tp_weaklistoffset */
 	PyObject_SelfIter,               /* tp_iter: __iter__() method */
 	lmiter_iterkeysnext,             /* tp_iternext: next() method */
 };
 
 static lazymanifest *lazymanifest_copy(lazymanifest *self);
 
 static PyObject *lazymanifest_getentriesiter(lazymanifest *self)
 {
 	lmIter *i = NULL;
 	lazymanifest *t = lazymanifest_copy(self);
 	if (!t) {
 		PyErr_NoMemory();
 		return NULL;
 	}
 	i = PyObject_New(lmIter, &lazymanifestEntriesIterator);
 	if (i) {
 		i->m = t;
 		i->pos = -1;
 	} else {
 		Py_DECREF(t);
 		PyErr_NoMemory();
 	}
 	return (PyObject *)i;
 }
 
 static PyObject *lazymanifest_getkeysiter(lazymanifest *self)
 {
 	lmIter *i = NULL;
 	lazymanifest *t = lazymanifest_copy(self);
 	if (!t) {
 		PyErr_NoMemory();
 		return NULL;
 	}
 	i = PyObject_New(lmIter, &lazymanifestKeysIterator);
 	if (i) {
 		i->m = t;
 		i->pos = -1;
 	} else {
 		Py_DECREF(t);
 		PyErr_NoMemory();
 	}
 	return (PyObject *)i;
 }
 
 /* __getitem__ and __setitem__ support */
 
 static Py_ssize_t lazymanifest_size(lazymanifest *self)
 {
 	return self->livelines;
 }
 
 static int linecmp(const void *left, const void *right)
 {
 	return strcmp(((const line *)left)->start,
 		      ((const line *)right)->start);
 }
 
 static PyObject *lazymanifest_getitem(lazymanifest *self, PyObject *key)
 {
 	line needle;
 	line *hit;
 	if (!PyBytes_Check(key)) {
 		PyErr_Format(PyExc_TypeError,
 			     "getitem: manifest keys must be a string.");
 		return NULL;
 	}
 	needle.start = PyBytes_AsString(key);
 	hit = bsearch(&needle, self->lines, self->numlines, sizeof(line),
 		      &linecmp);
 	if (!hit || hit->deleted) {
 		PyErr_Format(PyExc_KeyError, "No such manifest entry.");
 		return NULL;
 	}
 	return hashflags(hit);
 }
 
 static int lazymanifest_delitem(lazymanifest *self, PyObject *key)
 {
 	line needle;
 	line *hit;
 	if (!PyBytes_Check(key)) {
 		PyErr_Format(PyExc_TypeError,
 			     "delitem: manifest keys must be a string.");
 		return -1;
 	}
 	needle.start = PyBytes_AsString(key);
 	hit = bsearch(&needle, self->lines, self->numlines, sizeof(line),
 		      &linecmp);
 	if (!hit || hit->deleted) {
 		PyErr_Format(PyExc_KeyError,
 			     "Tried to delete nonexistent manifest entry.");
 		return -1;
 	}
 	self->dirty = true;
 	hit->deleted = true;
 	self->livelines--;
 	return 0;
 }
 
 /* Do a binary search for the insertion point for new, creating the
  * new entry if needed. */
 static int internalsetitem(lazymanifest *self, line *new) {
 	int start = 0, end = self->numlines;
 	while (start < end) {
 		int pos = start + (end - start) / 2;
 		int c = linecmp(new, self->lines + pos);
 		if (c < 0)
 			end = pos;
 		else if (c > 0)
 			start = pos + 1;
 		else {
 			if (self->lines[pos].deleted)
 				self->livelines++;
 			if (self->lines[pos].from_malloc)
 				free(self->lines[pos].start);
 			start = pos;
 			goto finish;
 		}
 	}
 	/* being here means we need to do an insert */
 	if (!realloc_if_full(self)) {
 		PyErr_NoMemory();
 		return -1;
 	}
 	memmove(self->lines + start + 1, self->lines + start,
 		(self->numlines - start) * sizeof(line));
 	self->numlines++;
 	self->livelines++;
 finish:
 	self->lines[start] = *new;
 	self->dirty = true;
 	return 0;
 }
 
 static int lazymanifest_setitem(
 	lazymanifest *self, PyObject *key, PyObject *value)
 {
 	char *path;
 	Py_ssize_t plen;
 	PyObject *pyhash;
 	Py_ssize_t hlen;
 	char *hash;
 	PyObject *pyflags;
 	char *flags;
 	Py_ssize_t flen;
 	size_t dlen;
 	char *dest;
 	int i;
 	line new;
 	if (!PyBytes_Check(key)) {
 		PyErr_Format(PyExc_TypeError,
 			     "setitem: manifest keys must be a string.");
 		return -1;
 	}
 	if (!value) {
 		return lazymanifest_delitem(self, key);
 	}
 	if (!PyTuple_Check(value) || PyTuple_Size(value) != 2) {
 		PyErr_Format(PyExc_TypeError,
 			     "Manifest values must be a tuple of (node, flags).");
 		return -1;
 	}
 	if (PyBytes_AsStringAndSize(key, &path, &plen) == -1) {
 		return -1;
 	}
 
 	pyhash = PyTuple_GetItem(value, 0);
 	if (!PyBytes_Check(pyhash)) {
 		PyErr_Format(PyExc_TypeError,
 			     "node must be a 20-byte string");
 		return -1;
 	}
 	hlen = PyBytes_Size(pyhash);
 	/* Some parts of the codebase try and set 21 or 22
 	 * byte "hash" values in order to perturb things for
 	 * status. We have to preserve at least the 21st
 	 * byte. Sigh. If there's a 22nd byte, we drop it on
 	 * the floor, which works fine.
 	 */
 	if (hlen != 20 && hlen != 21 && hlen != 22) {
 		PyErr_Format(PyExc_TypeError,
 			     "node must be a 20-byte string");
 		return -1;
 	}
 	hash = PyBytes_AsString(pyhash);
 
 	pyflags = PyTuple_GetItem(value, 1);
 	if (!PyBytes_Check(pyflags) || PyBytes_Size(pyflags) > 1) {
 		PyErr_Format(PyExc_TypeError,
 			     "flags must a 0 or 1 byte string");
 		return -1;
 	}
 	if (PyBytes_AsStringAndSize(pyflags, &flags, &flen) == -1) {
 		return -1;
 	}
 	/* one null byte and one newline */
 	dlen = plen + 41 + flen + 1;
 	dest = malloc(dlen);
 	if (!dest) {
 		PyErr_NoMemory();
 		return -1;
 	}
 	memcpy(dest, path, plen + 1);
 	for (i = 0; i < 20; i++) {
 		/* Cast to unsigned, so it will not get sign-extended when promoted
 		 * to int (as is done when passing to a variadic function)
 		 */
 		sprintf(dest + plen + 1 + (i * 2), "%02x", (unsigned char)hash[i]);
 	}
 	memcpy(dest + plen + 41, flags, flen);
 	dest[plen + 41 + flen] = '\n';
 	new.start = dest;
 	new.len = dlen;
 	new.hash_suffix = '\0';
 	if (hlen > 20) {
 		new.hash_suffix = hash[20];
 	}
 	new.from_malloc = true;     /* is `start` a pointer we allocated? */
 	new.deleted = false;        /* is this entry deleted? */
 	if (internalsetitem(self, &new)) {
 		return -1;
 	}
 	return 0;
 }
 
 static PyMappingMethods lazymanifest_mapping_methods = {
 	(lenfunc)lazymanifest_size,             /* mp_length */
 	(binaryfunc)lazymanifest_getitem,       /* mp_subscript */
 	(objobjargproc)lazymanifest_setitem,    /* mp_ass_subscript */
 };
 
 /* sequence methods (important or __contains__ builds an iterator) */
 
 static int lazymanifest_contains(lazymanifest *self, PyObject *key)
 {
 	line needle;
 	line *hit;
 	if (!PyBytes_Check(key)) {
 		/* Our keys are always strings, so if the contains
 		 * check is for a non-string, just return false. */
 		return 0;
 	}
 	needle.start = PyBytes_AsString(key);
 	hit = bsearch(&needle, self->lines, self->numlines, sizeof(line),
 		      &linecmp);
 	if (!hit || hit->deleted) {
 		return 0;
 	}
 	return 1;
 }
 
 static PySequenceMethods lazymanifest_seq_meths = {
 	(lenfunc)lazymanifest_size, /* sq_length */
 	0, /* sq_concat */
 	0, /* sq_repeat */
 	0, /* sq_item */
 	0, /* sq_slice */
 	0, /* sq_ass_item */
 	0, /* sq_ass_slice */
 	(objobjproc)lazymanifest_contains, /* sq_contains */
 	0, /* sq_inplace_concat */
 	0, /* sq_inplace_repeat */
 };
 
 
 /* Other methods (copy, diff, etc) */
 static PyTypeObject lazymanifestType;
 
 /* If the manifest has changes, build the new manifest text and reindex it. */
 static int compact(lazymanifest *self) {
 	int i;
 	ssize_t need = 0;
 	char *data;
 	line *src, *dst;
 	PyObject *pydata;
 	if (!self->dirty)
 		return 0;
 	for (i = 0; i < self->numlines; i++) {
 		if (!self->lines[i].deleted) {
 			need += self->lines[i].len;
 		}
 	}
 	pydata = PyBytes_FromStringAndSize(NULL, need);
 	if (!pydata)
 		return -1;
 	data = PyBytes_AsString(pydata);
 	if (!data) {
 		return -1;
 	}
 	src = self->lines;
 	dst = self->lines;
 	for (i = 0; i < self->numlines; i++, src++) {
 		char *tofree = NULL;
 		if (src->from_malloc) {
 			tofree = src->start;
 		}
 		if (!src->deleted) {
 			memcpy(data, src->start, src->len);
 			*dst = *src;
 			dst->start = data;
 			dst->from_malloc = false;
 			data += dst->len;
 			dst++;
 		}
 		free(tofree);
 	}
 	Py_DECREF(self->pydata);
 	self->pydata = pydata;
 	self->numlines = self->livelines;
 	self->dirty = false;
 	return 0;
 }
 
 static PyObject *lazymanifest_text(lazymanifest *self)
 {
 	if (compact(self) != 0) {
 		PyErr_NoMemory();
 		return NULL;
 	}
 	Py_INCREF(self->pydata);
 	return self->pydata;
 }
 
 static lazymanifest *lazymanifest_copy(lazymanifest *self)
 {
 	lazymanifest *copy = NULL;
 	if (compact(self) != 0) {
 		goto nomem;
 	}
 	copy = PyObject_New(lazymanifest, &lazymanifestType);
 	if (!copy) {
 		goto nomem;
 	}
 	copy->numlines = self->numlines;
 	copy->livelines = self->livelines;
 	copy->dirty = false;
 	copy->lines = malloc(self->maxlines *sizeof(line));
 	if (!copy->lines) {
 		goto nomem;
 	}
 	memcpy(copy->lines, self->lines, self->numlines * sizeof(line));
 	copy->maxlines = self->maxlines;
 	copy->pydata = self->pydata;
 	Py_INCREF(copy->pydata);
 	return copy;
 nomem:
 	PyErr_NoMemory();
 	Py_XDECREF(copy);
 	return NULL;
 }
 
 static lazymanifest *lazymanifest_filtercopy(
 	lazymanifest *self, PyObject *matchfn)
 {
 	lazymanifest *copy = NULL;
 	int i;
 	if (!PyCallable_Check(matchfn)) {
 		PyErr_SetString(PyExc_TypeError, "matchfn must be callable");
 		return NULL;
 	}
 	/* compact ourselves first to avoid double-frees later when we
 	 * compact tmp so that it doesn't have random pointers to our
 	 * underlying from_malloc-data (self->pydata is safe) */
 	if (compact(self) != 0) {
 		goto nomem;
 	}
 	copy = PyObject_New(lazymanifest, &lazymanifestType);
 	if (!copy) {
 		goto nomem;
 	}
 	copy->dirty = true;
 	copy->lines = malloc(self->maxlines * sizeof(line));
 	if (!copy->lines) {
 		goto nomem;
 	}
 	copy->maxlines = self->maxlines;
 	copy->numlines = 0;
 	copy->pydata = self->pydata;
 	Py_INCREF(self->pydata);
 	for (i = 0; i < self->numlines; i++) {
 		PyObject *arglist = NULL, *result = NULL;
 		arglist = Py_BuildValue("(s)", self->lines[i].start);
 		if (!arglist) {
 			return NULL;
 		}
 		result = PyObject_CallObject(matchfn, arglist);
 		Py_DECREF(arglist);
 		/* if the callback raised an exception, just let it
 		 * through and give up */
 		if (!result) {
 			free(copy->lines);
 			Py_DECREF(self->pydata);
 			return NULL;
 		}
 		if (PyObject_IsTrue(result)) {
 			assert(!(self->lines[i].from_malloc));
 			copy->lines[copy->numlines++] = self->lines[i];
 		}
 		Py_DECREF(result);
 	}
 	copy->livelines = copy->numlines;
 	return copy;
 nomem:
 	PyErr_NoMemory();
 	Py_XDECREF(copy);
 	return NULL;
 }
 
 static PyObject *lazymanifest_diff(lazymanifest *self, PyObject *args)
 {
 	lazymanifest *other;
 	PyObject *pyclean = NULL;
 	bool listclean;
 	PyObject *emptyTup = NULL, *ret = NULL;
 	PyObject *es;
 	int sneedle = 0, oneedle = 0;
 	if (!PyArg_ParseTuple(args, "O!|O", &lazymanifestType, &other, &pyclean)) {
 		return NULL;
 	}
 	listclean = (!pyclean) ? false : PyObject_IsTrue(pyclean);
 	es = PyBytes_FromString("");
 	if (!es) {
 		goto nomem;
 	}
 	emptyTup = PyTuple_Pack(2, Py_None, es);
 	Py_DECREF(es);
 	if (!emptyTup) {
 		goto nomem;
 	}
 	ret = PyDict_New();
 	if (!ret) {
 		goto nomem;
 	}
 	while (sneedle != self->numlines || oneedle != other->numlines) {
 		line *left = self->lines + sneedle;
 		line *right = other->lines + oneedle;
 		int result;
 		PyObject *key;
 		PyObject *outer;
 		/* If we're looking at a deleted entry and it's not
 		 * the end of the manifest, just skip it. */
 		if (left->deleted && sneedle < self->numlines) {
 			sneedle++;
 			continue;
 		}
 		if (right->deleted && oneedle < other->numlines) {
 			oneedle++;
 			continue;
 		}
 		/* if we're at the end of either manifest, then we
 		 * know the remaining items are adds so we can skip
 		 * the strcmp. */
 		if (sneedle == self->numlines) {
 			result = 1;
 		} else if (oneedle == other->numlines) {
 			result = -1;
 		} else {
 			result = linecmp(left, right);
 		}
 		key = result <= 0 ?
 			PyBytes_FromString(left->start) :
 			PyBytes_FromString(right->start);
 		if (!key)
 			goto nomem;
 		if (result < 0) {
 			PyObject *l = hashflags(left);
 			if (!l) {
 				goto nomem;
 			}
 			outer = PyTuple_Pack(2, l, emptyTup);
 			Py_DECREF(l);
 			if (!outer) {
 				goto nomem;
 			}
 			PyDict_SetItem(ret, key, outer);
 			Py_DECREF(outer);
 			sneedle++;
 		} else if (result > 0) {
 			PyObject *r = hashflags(right);
 			if (!r) {
 				goto nomem;
 			}
 			outer = PyTuple_Pack(2, emptyTup, r);
 			Py_DECREF(r);
 			if (!outer) {
 				goto nomem;
 			}
 			PyDict_SetItem(ret, key, outer);
 			Py_DECREF(outer);
 			oneedle++;
 		} else {
 			/* file exists in both manifests */
 			if (left->len != right->len
 			    || memcmp(left->start, right->start, left->len)
 			    || left->hash_suffix != right->hash_suffix) {
 				PyObject *l = hashflags(left);
 				PyObject *r;
 				if (!l) {
 					goto nomem;
 				}
 				r = hashflags(right);
 				if (!r) {
 					Py_DECREF(l);
 					goto nomem;
 				}
 				outer = PyTuple_Pack(2, l, r);
 				Py_DECREF(l);
 				Py_DECREF(r);
 				if (!outer) {
 					goto nomem;
 				}
 				PyDict_SetItem(ret, key, outer);
 				Py_DECREF(outer);
 			} else if (listclean) {
 				PyDict_SetItem(ret, key, Py_None);
 			}
 			sneedle++;
 			oneedle++;
 		}
 		Py_DECREF(key);
 	}
 	Py_DECREF(emptyTup);
 	return ret;
 nomem:
 	PyErr_NoMemory();
 	Py_XDECREF(ret);
 	Py_XDECREF(emptyTup);
 	return NULL;
 }
 
 static PyMethodDef lazymanifest_methods[] = {
 	{"iterkeys", (PyCFunction)lazymanifest_getkeysiter, METH_NOARGS,
 	 "Iterate over file names in this lazymanifest."},
 	{"iterentries", (PyCFunction)lazymanifest_getentriesiter, METH_NOARGS,
 	 "Iterate over (path, nodeid, flags) tuples in this lazymanifest."},
 	{"copy", (PyCFunction)lazymanifest_copy, METH_NOARGS,
 	 "Make a copy of this lazymanifest."},
 	{"filtercopy", (PyCFunction)lazymanifest_filtercopy, METH_O,
 	 "Make a copy of this manifest filtered by matchfn."},
 	{"diff", (PyCFunction)lazymanifest_diff, METH_VARARGS,
 	 "Compare this lazymanifest to another one."},
 	{"text", (PyCFunction)lazymanifest_text, METH_NOARGS,
 	 "Encode this manifest to text."},
 	{NULL},
 };
 
 #ifdef IS_PY3K
 #define LAZYMANIFEST_TPFLAGS Py_TPFLAGS_DEFAULT
 #else
 #define LAZYMANIFEST_TPFLAGS Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_SEQUENCE_IN
 #endif
 
 static PyTypeObject lazymanifestType = {
 	PyVarObject_HEAD_INIT(NULL, 0)
 	"parsers.lazymanifest",                           /* tp_name */
 	sizeof(lazymanifest),                             /* tp_basicsize */
 	0,                                                /* tp_itemsize */
 	(destructor)lazymanifest_dealloc,                 /* tp_dealloc */
 	0,                                                /* tp_print */
 	0,                                                /* tp_getattr */
 	0,                                                /* tp_setattr */
 	0,                                                /* tp_compare */
 	0,                                                /* tp_repr */
 	0,                                                /* tp_as_number */
 	&lazymanifest_seq_meths,                          /* tp_as_sequence */
 	&lazymanifest_mapping_methods,                    /* tp_as_mapping */
 	0,                                                /* tp_hash */
 	0,                                                /* tp_call */
 	0,                                                /* tp_str */
 	0,                                                /* tp_getattro */
 	0,                                                /* tp_setattro */
 	0,                                                /* tp_as_buffer */
 	LAZYMANIFEST_TPFLAGS,                             /* tp_flags */
 	"TODO(augie)",                                    /* tp_doc */
 	0,                                                /* tp_traverse */
 	0,                                                /* tp_clear */
 	0,                                                /* tp_richcompare */
 	0,                                             /* tp_weaklistoffset */
 	(getiterfunc)lazymanifest_getkeysiter,                /* tp_iter */
 	0,                                                /* tp_iternext */
 	lazymanifest_methods,                             /* tp_methods */
 	0,                                                /* tp_members */
 	0,                                                /* tp_getset */
 	0,                                                /* tp_base */
 	0,                                                /* tp_dict */
 	0,                                                /* tp_descr_get */
 	0,                                                /* tp_descr_set */
 	0,                                                /* tp_dictoffset */
 	(initproc)lazymanifest_init,                      /* tp_init */
 	0,                                                /* tp_alloc */
 };
 
 void manifest_module_init(PyObject * mod)
 {
 	lazymanifestType.tp_new = PyType_GenericNew;
 	if (PyType_Ready(&lazymanifestType) < 0)
 		return;
 	Py_INCREF(&lazymanifestType);
 
 	PyModule_AddObject(mod, "lazymanifest",
 			   (PyObject *)&lazymanifestType);
 }

mercurial/cext/mpatch.c

@@ -1,200 +1,200 b''
 /*
  mpatch.c - efficient binary patching for Mercurial
 
  This implements a patch algorithm that's O(m + nlog n) where m is the
  size of the output and n is the number of patches.
 
  Given a list of binary patches, it unpacks each into a hunk list,
  then combines the hunk lists with a treewise recursion to form a
  single hunk list. This hunk list is then applied to the original
  text.
 
  The text (or binary) fragments are copied directly from their source
  Python objects into a preallocated output string to avoid the
  allocation of intermediate Python objects. Working memory is about 2x
  the total number of hunks.
 
  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.
 */
 
 #define PY_SSIZE_T_CLEAN
 #include <Python.h>
 #include <stdlib.h>
 #include <string.h>
 
-#include "util.h"
 #include "bitmanipulation.h"
 #include "compat.h"
 #include "mpatch.h"
+#include "util.h"
 
 static char mpatch_doc[] = "Efficient binary patching.";
 static PyObject *mpatch_Error;
 
 static void setpyerr(int r)
 {
 	switch (r) {
 	case MPATCH_ERR_NO_MEM:
 		PyErr_NoMemory();
 		break;
 	case MPATCH_ERR_CANNOT_BE_DECODED:
 		PyErr_SetString(mpatch_Error, "patch cannot be decoded");
 		break;
 	case MPATCH_ERR_INVALID_PATCH:
 		PyErr_SetString(mpatch_Error, "invalid patch");
 		break;
 	}
 }
 
 struct mpatch_flist *cpygetitem(void *bins, ssize_t pos)
 {
 	const char *buffer;
 	struct mpatch_flist *res;
 	ssize_t blen;
 	int r;
 
 	PyObject *tmp = PyList_GetItem((PyObject*)bins, pos);
 	if (!tmp)
 		return NULL;
 	if (PyObject_AsCharBuffer(tmp, &buffer, (Py_ssize_t*)&blen))
 		return NULL;
 	if ((r = mpatch_decode(buffer, blen, &res)) < 0) {
 		if (!PyErr_Occurred())
 			setpyerr(r);
 		return NULL;
 	}
 	return res;
 }
 
 static PyObject *
 patches(PyObject *self, PyObject *args)
 {
 	PyObject *text, *bins, *result;
 	struct mpatch_flist *patch;
 	const char *in;
 	int r = 0;
 	char *out;
 	Py_ssize_t len, outlen, inlen;
 
 	if (!PyArg_ParseTuple(args, "OO:mpatch", &text, &bins))
 		return NULL;
 
 	len = PyList_Size(bins);
 	if (!len) {
 		/* nothing to do */
 		Py_INCREF(text);
 		return text;
 	}
 
 	if (PyObject_AsCharBuffer(text, &in, &inlen))
 		return NULL;
 
 	patch = mpatch_fold(bins, cpygetitem, 0, len);
 	if (!patch) { /* error already set or memory error */
 		if (!PyErr_Occurred())
 			PyErr_NoMemory();
 		return NULL;
 	}
 
 	outlen = mpatch_calcsize(inlen, patch);
 	if (outlen < 0) {
 		r = (int)outlen;
 		result = NULL;
 		goto cleanup;
 	}
 	result = PyBytes_FromStringAndSize(NULL, outlen);
 	if (!result) {
 		result = NULL;
 		goto cleanup;
 	}
 	out = PyBytes_AsString(result);
 	if ((r = mpatch_apply(out, in, inlen, patch)) < 0) {
 		Py_DECREF(result);
 		result = NULL;
 	}
 cleanup:
 	mpatch_lfree(patch);
 	if (!result && !PyErr_Occurred())
 		setpyerr(r);
 	return result;
 }
 
 /* calculate size of a patched file directly */
 static PyObject *
 patchedsize(PyObject *self, PyObject *args)
 {
 	long orig, start, end, len, outlen = 0, last = 0, pos = 0;
 	Py_ssize_t patchlen;
 	char *bin;
 
 	if (!PyArg_ParseTuple(args, "ls#", &orig, &bin, &patchlen))
 		return NULL;
 
 	while (pos >= 0 && pos < patchlen) {
 		start = getbe32(bin + pos);
 		end = getbe32(bin + pos + 4);
 		len = getbe32(bin + pos + 8);
 		if (start > end)
 			break; /* sanity check */
 		pos += 12 + len;
 		outlen += start - last;
 		last = end;
 		outlen += len;
 	}
 
 	if (pos != patchlen) {
 		if (!PyErr_Occurred())
 			PyErr_SetString(mpatch_Error, "patch cannot be decoded");
 		return NULL;
 	}
 
 	outlen += orig - last;
 	return Py_BuildValue("l", outlen);
 }
 
 static PyMethodDef methods[] = {
 	{"patches", patches, METH_VARARGS, "apply a series of patches\n"},
 	{"patchedsize", patchedsize, METH_VARARGS, "calculed patched size\n"},
 	{NULL, NULL}
 };
 
 static const int version = 1;
 
 #ifdef IS_PY3K
 static struct PyModuleDef mpatch_module = {
 	PyModuleDef_HEAD_INIT,
 	"mpatch",
 	mpatch_doc,
 	-1,
 	methods
 };
 
 PyMODINIT_FUNC PyInit_mpatch(void)
 {
 	PyObject *m;
 
 	m = PyModule_Create(&mpatch_module);
 	if (m == NULL)
 		return NULL;
 
 	mpatch_Error = PyErr_NewException("mercurial.cext.mpatch.mpatchError",
 					  NULL, NULL);
 	Py_INCREF(mpatch_Error);
 	PyModule_AddObject(m, "mpatchError", mpatch_Error);
 	PyModule_AddIntConstant(m, "version", version);
 
 	return m;
 }
 #else
 PyMODINIT_FUNC
 initmpatch(void)
 {
 	PyObject *m;
 	m = Py_InitModule3("mpatch", methods, mpatch_doc);
 	mpatch_Error = PyErr_NewException("mercurial.cext.mpatch.mpatchError",
 					  NULL, NULL);
 	PyModule_AddIntConstant(m, "version", version);
 }
 #endif

mercurial/cext/osutil.c

@@ -1,1335 +1,1335 b''
 /*
  osutil.c - native operating system services
 
  Copyright 2007 Matt Mackall and others
 
  This software may be used and distributed according to the terms of
  the GNU General Public License, incorporated herein by reference.
 */
 
 #define _ATFILE_SOURCE
 #include <Python.h>
+#include <errno.h>
 #include <fcntl.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
-#include <errno.h>
 
 #ifdef _WIN32
+#include <io.h>
 #include <windows.h>
-#include <io.h>
 #else
 #include <dirent.h>
 #include <sys/socket.h>
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <unistd.h>
 #ifdef HAVE_LINUX_STATFS
 #include <linux/magic.h>
 #include <sys/vfs.h>
 #endif
 #ifdef HAVE_BSD_STATFS
 #include <sys/mount.h>
 #include <sys/param.h>
 #endif
 #endif
 
 #ifdef __APPLE__
 #include <sys/attr.h>
 #include <sys/vnode.h>
 #endif
 
 #include "util.h"
 
 /* some platforms lack the PATH_MAX definition (eg. GNU/Hurd) */
 #ifndef PATH_MAX
 #define PATH_MAX 4096
 #endif
 
 #ifdef _WIN32
 /*
 stat struct compatible with hg expectations
 Mercurial only uses st_mode, st_size and st_mtime
 the rest is kept to minimize changes between implementations
 */
 struct hg_stat {
 	int st_dev;
 	int st_mode;
 	int st_nlink;
 	__int64 st_size;
 	int st_mtime;
 	int st_ctime;
 };
 struct listdir_stat {
 	PyObject_HEAD
 	struct hg_stat st;
 };
 #else
 struct listdir_stat {
 	PyObject_HEAD
 	struct stat st;
 };
 #endif
 
 #ifdef IS_PY3K
 #define listdir_slot(name) \
 	static PyObject *listdir_stat_##name(PyObject *self, void *x) \
 	{ \
 		return PyLong_FromLong(((struct listdir_stat *)self)->st.name); \
 	}
 #else
 #define listdir_slot(name) \
 	static PyObject *listdir_stat_##name(PyObject *self, void *x) \
 	{ \
 		return PyInt_FromLong(((struct listdir_stat *)self)->st.name); \
 	}
 #endif
 
 listdir_slot(st_dev)
 listdir_slot(st_mode)
 listdir_slot(st_nlink)
 #ifdef _WIN32
 static PyObject *listdir_stat_st_size(PyObject *self, void *x)
 {
 	return PyLong_FromLongLong(
 		(PY_LONG_LONG)((struct listdir_stat *)self)->st.st_size);
 }
 #else
 listdir_slot(st_size)
 #endif
 listdir_slot(st_mtime)
 listdir_slot(st_ctime)
 
 static struct PyGetSetDef listdir_stat_getsets[] = {
 	{"st_dev", listdir_stat_st_dev, 0, 0, 0},
 	{"st_mode", listdir_stat_st_mode, 0, 0, 0},
 	{"st_nlink", listdir_stat_st_nlink, 0, 0, 0},
 	{"st_size", listdir_stat_st_size, 0, 0, 0},
 	{"st_mtime", listdir_stat_st_mtime, 0, 0, 0},
 	{"st_ctime", listdir_stat_st_ctime, 0, 0, 0},
 	{0, 0, 0, 0, 0}
 };
 
 static PyObject *listdir_stat_new(PyTypeObject *t, PyObject *a, PyObject *k)
 {
 	return t->tp_alloc(t, 0);
 }
 
 static void listdir_stat_dealloc(PyObject *o)
 {
 	o->ob_type->tp_free(o);
 }
 
 static PyTypeObject listdir_stat_type = {
 	PyVarObject_HEAD_INIT(NULL, 0)
 	"osutil.stat",             /*tp_name*/
 	sizeof(struct listdir_stat), /*tp_basicsize*/
 	0,                         /*tp_itemsize*/
 	(destructor)listdir_stat_dealloc, /*tp_dealloc*/
 	0,                         /*tp_print*/
 	0,                         /*tp_getattr*/
 	0,                         /*tp_setattr*/
 	0,                         /*tp_compare*/
 	0,                         /*tp_repr*/
 	0,                         /*tp_as_number*/
 	0,                         /*tp_as_sequence*/
 	0,                         /*tp_as_mapping*/
 	0,                         /*tp_hash */
 	0,                         /*tp_call*/
 	0,                         /*tp_str*/
 	0,                         /*tp_getattro*/
 	0,                         /*tp_setattro*/
 	0,                         /*tp_as_buffer*/
 	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
 	"stat objects",            /* tp_doc */
 	0,                         /* tp_traverse */
 	0,                         /* tp_clear */
 	0,                         /* tp_richcompare */
 	0,                         /* tp_weaklistoffset */
 	0,                         /* tp_iter */
 	0,                         /* tp_iternext */
 	0,                         /* tp_methods */
 	0,                         /* tp_members */
 	listdir_stat_getsets,      /* tp_getset */
 	0,                         /* tp_base */
 	0,                         /* tp_dict */
 	0,                         /* tp_descr_get */
 	0,                         /* tp_descr_set */
 	0,                         /* tp_dictoffset */
 	0,                         /* tp_init */
 	0,                         /* tp_alloc */
 	listdir_stat_new,          /* tp_new */
 };
 
 #ifdef _WIN32
 
 static int to_python_time(const FILETIME *tm)
 {
 	/* number of seconds between epoch and January 1 1601 */
 	const __int64 a0 = (__int64)134774L * (__int64)24L * (__int64)3600L;
 	/* conversion factor from 100ns to 1s */
 	const __int64 a1 = 10000000;
 	/* explicit (int) cast to suspend compiler warnings */
 	return (int)((((__int64)tm->dwHighDateTime << 32)
 			+ tm->dwLowDateTime) / a1 - a0);
 }
 
 static PyObject *make_item(const WIN32_FIND_DATAA *fd, int wantstat)
 {
 	PyObject *py_st;
 	struct hg_stat *stp;
 
 	int kind = (fd->dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
 		? _S_IFDIR : _S_IFREG;
 
 	if (!wantstat)
 		return Py_BuildValue("si", fd->cFileName, kind);
 
 	py_st = PyObject_CallObject((PyObject *)&listdir_stat_type, NULL);
 	if (!py_st)
 		return NULL;
 
 	stp = &((struct listdir_stat *)py_st)->st;
 	/*
 	use kind as st_mode
 	rwx bits on Win32 are meaningless
 	and Hg does not use them anyway
 	*/
 	stp->st_mode  = kind;
 	stp->st_mtime = to_python_time(&fd->ftLastWriteTime);
 	stp->st_ctime = to_python_time(&fd->ftCreationTime);
 	if (kind == _S_IFREG)
 		stp->st_size = ((__int64)fd->nFileSizeHigh << 32)
 				+ fd->nFileSizeLow;
 	return Py_BuildValue("siN", fd->cFileName,
 		kind, py_st);
 }
 
 static PyObject *_listdir(char *path, int plen, int wantstat, char *skip)
 {
 	PyObject *rval = NULL; /* initialize - return value */
 	PyObject *list;
 	HANDLE fh;
 	WIN32_FIND_DATAA fd;
 	char *pattern;
 
 	/* build the path + \* pattern string */
 	pattern = PyMem_Malloc(plen + 3); /* path + \* + \0 */
 	if (!pattern) {
 		PyErr_NoMemory();
 		goto error_nomem;
 	}
 	memcpy(pattern, path, plen);
 
 	if (plen > 0) {
 		char c = path[plen-1];
 		if (c != ':' && c != '/' && c != '\\')
 			pattern[plen++] = '\\';
 	}
 	pattern[plen++] = '*';
 	pattern[plen] = '\0';
 
 	fh = FindFirstFileA(pattern, &fd);
 	if (fh == INVALID_HANDLE_VALUE) {
 		PyErr_SetFromWindowsErrWithFilename(GetLastError(), path);
 		goto error_file;
 	}
 
 	list = PyList_New(0);
 	if (!list)
 		goto error_list;
 
 	do {
 		PyObject *item;
 
 		if (fd.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) {
 			if (!strcmp(fd.cFileName, ".")
 			|| !strcmp(fd.cFileName, ".."))
 				continue;
 
 			if (skip && !strcmp(fd.cFileName, skip)) {
 				rval = PyList_New(0);
 				goto error;
 			}
 		}
 
 		item = make_item(&fd, wantstat);
 		if (!item)
 			goto error;
 
 		if (PyList_Append(list, item)) {
 			Py_XDECREF(item);
 			goto error;
 		}
 
 		Py_XDECREF(item);
 	} while (FindNextFileA(fh, &fd));
 
 	if (GetLastError() != ERROR_NO_MORE_FILES) {
 		PyErr_SetFromWindowsErrWithFilename(GetLastError(), path);
 		goto error;
 	}
 
 	rval = list;
 	Py_XINCREF(rval);
 error:
 	Py_XDECREF(list);
 error_list:
 	FindClose(fh);
 error_file:
 	PyMem_Free(pattern);
 error_nomem:
 	return rval;
 }
 
 #else
 
 int entkind(struct dirent *ent)
 {
 #ifdef DT_REG
 	switch (ent->d_type) {
 	case DT_REG: return S_IFREG;
 	case DT_DIR: return S_IFDIR;
 	case DT_LNK: return S_IFLNK;
 	case DT_BLK: return S_IFBLK;
 	case DT_CHR: return S_IFCHR;
 	case DT_FIFO: return S_IFIFO;
 	case DT_SOCK: return S_IFSOCK;
 	}
 #endif
 	return -1;
 }
 
 static PyObject *makestat(const struct stat *st)
 {
 	PyObject *stat;
 
 	stat = PyObject_CallObject((PyObject *)&listdir_stat_type, NULL);
 	if (stat)
 		memcpy(&((struct listdir_stat *)stat)->st, st, sizeof(*st));
 	return stat;
 }
 
 static PyObject *_listdir_stat(char *path, int pathlen, int keepstat,
 			       char *skip)
 {
 	PyObject *list, *elem, *stat = NULL, *ret = NULL;
 	char fullpath[PATH_MAX + 10];
 	int kind, err;
 	struct stat st;
 	struct dirent *ent;
 	DIR *dir;
 #ifdef AT_SYMLINK_NOFOLLOW
 	int dfd = -1;
 #endif
 
 	if (pathlen >= PATH_MAX) {
 		errno = ENAMETOOLONG;
 		PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
 		goto error_value;
 	}
 	strncpy(fullpath, path, PATH_MAX);
 	fullpath[pathlen] = '/';
 
 #ifdef AT_SYMLINK_NOFOLLOW
 	dfd = open(path, O_RDONLY);
 	if (dfd == -1) {
 		PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
 		goto error_value;
 	}
 	dir = fdopendir(dfd);
 #else
 	dir = opendir(path);
 #endif
 	if (!dir) {
 		PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
 		goto error_dir;
 	}
 
 	list = PyList_New(0);
 	if (!list)
 		goto error_list;
 
 	while ((ent = readdir(dir))) {
 		if (!strcmp(ent->d_name, ".") || !strcmp(ent->d_name, ".."))
 			continue;
 
 		kind = entkind(ent);
 		if (kind == -1 || keepstat) {
 #ifdef AT_SYMLINK_NOFOLLOW
 			err = fstatat(dfd, ent->d_name, &st,
 				      AT_SYMLINK_NOFOLLOW);
 #else
 			strncpy(fullpath + pathlen + 1, ent->d_name,
 				PATH_MAX - pathlen);
 			fullpath[PATH_MAX] = '\0';
 			err = lstat(fullpath, &st);
 #endif
 			if (err == -1) {
 				/* race with file deletion? */
 				if (errno == ENOENT)
 					continue;
 				strncpy(fullpath + pathlen + 1, ent->d_name,
 					PATH_MAX - pathlen);
 				fullpath[PATH_MAX] = 0;
 				PyErr_SetFromErrnoWithFilename(PyExc_OSError,
 							       fullpath);
 				goto error;
 			}
 			kind = st.st_mode & S_IFMT;
 		}
 
 		/* quit early? */
 		if (skip && kind == S_IFDIR && !strcmp(ent->d_name, skip)) {
 			ret = PyList_New(0);
 			goto error;
 		}
 
 		if (keepstat) {
 			stat = makestat(&st);
 			if (!stat)
 				goto error;
 			elem = Py_BuildValue("siN", ent->d_name, kind, stat);
 		} else
 			elem = Py_BuildValue("si", ent->d_name, kind);
 		if (!elem)
 			goto error;
 		stat = NULL;
 
 		PyList_Append(list, elem);
 		Py_DECREF(elem);
 	}
 
 	ret = list;
 	Py_INCREF(ret);
 
 error:
 	Py_DECREF(list);
 	Py_XDECREF(stat);
 error_list:
 	closedir(dir);
 	/* closedir also closes its dirfd */
 	goto error_value;
 error_dir:
 #ifdef AT_SYMLINK_NOFOLLOW
 	close(dfd);
 #endif
 error_value:
 	return ret;
 }
 
 #ifdef __APPLE__
 
 typedef struct {
 	u_int32_t length;
 	attrreference_t name;
 	fsobj_type_t obj_type;
 	struct timespec mtime;
 #if __LITTLE_ENDIAN__
 	mode_t access_mask;
 	uint16_t padding;
 #else
 	uint16_t padding;
 	mode_t access_mask;
 #endif
 	off_t size;
 } __attribute__((packed)) attrbuf_entry;
 
 int attrkind(attrbuf_entry *entry)
 {
 	switch (entry->obj_type) {
 	case VREG: return S_IFREG;
 	case VDIR: return S_IFDIR;
 	case VLNK: return S_IFLNK;
 	case VBLK: return S_IFBLK;
 	case VCHR: return S_IFCHR;
 	case VFIFO: return S_IFIFO;
 	case VSOCK: return S_IFSOCK;
 	}
 	return -1;
 }
 
 /* get these many entries at a time */
 #define LISTDIR_BATCH_SIZE 50
 
 static PyObject *_listdir_batch(char *path, int pathlen, int keepstat,
 				char *skip, bool *fallback)
 {
 	PyObject *list, *elem, *stat = NULL, *ret = NULL;
 	int kind, err;
 	unsigned long index;
 	unsigned int count, old_state, new_state;
 	bool state_seen = false;
 	attrbuf_entry *entry;
 	/* from the getattrlist(2) man page: a path can be no longer than
 	   (NAME_MAX * 3 + 1) bytes. Also, "The getattrlist() function will
 	   silently truncate attribute data if attrBufSize is too small." So
 	   pass in a buffer big enough for the worst case. */
 	char attrbuf[LISTDIR_BATCH_SIZE * (sizeof(attrbuf_entry) + NAME_MAX * 3 + 1)];
 	unsigned int basep_unused;
 
 	struct stat st;
 	int dfd = -1;
 
 	/* these must match the attrbuf_entry struct, otherwise you'll end up
 	   with garbage */
 	struct attrlist requested_attr = {0};
 	requested_attr.bitmapcount = ATTR_BIT_MAP_COUNT;
 	requested_attr.commonattr = (ATTR_CMN_NAME | ATTR_CMN_OBJTYPE |
 				     ATTR_CMN_MODTIME | ATTR_CMN_ACCESSMASK);
 	requested_attr.fileattr = ATTR_FILE_DATALENGTH;
 
 	*fallback = false;
 
 	if (pathlen >= PATH_MAX) {
 		errno = ENAMETOOLONG;
 		PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
 		goto error_value;
 	}
 
 	dfd = open(path, O_RDONLY);
 	if (dfd == -1) {
 		PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
 		goto error_value;
 	}
 
 	list = PyList_New(0);
 	if (!list)
 		goto error_dir;
 
 	do {
 		count = LISTDIR_BATCH_SIZE;
 		err = getdirentriesattr(dfd, &requested_attr, &attrbuf,
 					sizeof(attrbuf), &count, &basep_unused,
 					&new_state, 0);
 		if (err < 0) {
 			if (errno == ENOTSUP) {
 				/* We're on a filesystem that doesn't support
 				   getdirentriesattr. Fall back to the
 				   stat-based implementation. */
 				*fallback = true;
 			} else
 				PyErr_SetFromErrnoWithFilename(PyExc_OSError, path);
 			goto error;
 		}
 
 		if (!state_seen) {
 			old_state = new_state;
 			state_seen = true;
 		} else if (old_state != new_state) {
 			/* There's an edge case with getdirentriesattr. Consider
 			   the following initial list of files:
 
 			   a
 			   b
 			   <--
 			   c
 			   d
 
 			   If the iteration is paused at the arrow, and b is
 			   deleted before it is resumed, getdirentriesattr will
 			   not return d at all!  Ordinarily we're expected to
 			   restart the iteration from the beginning. To avoid
 			   getting stuck in a retry loop here, fall back to
 			   stat. */
 			*fallback = true;
 			goto error;
 		}
 
 		entry = (attrbuf_entry *)attrbuf;
 
 		for (index = 0; index < count; index++) {
 			char *filename = ((char *)&entry->name) +
 				entry->name.attr_dataoffset;
 
 			if (!strcmp(filename, ".") || !strcmp(filename, ".."))
 				continue;
 
 			kind = attrkind(entry);
 			if (kind == -1) {
 				PyErr_Format(PyExc_OSError,
 					     "unknown object type %u for file "
 					     "%s%s!",
 					     entry->obj_type, path, filename);
 				goto error;
 			}
 
 			/* quit early? */
 			if (skip && kind == S_IFDIR && !strcmp(filename, skip)) {
 				ret = PyList_New(0);
 				goto error;
 			}
 
 			if (keepstat) {
 				/* from the getattrlist(2) man page: "Only the
 				   permission bits ... are valid". */
 				st.st_mode = (entry->access_mask & ~S_IFMT) | kind;
 				st.st_mtime = entry->mtime.tv_sec;
 				st.st_size = entry->size;
 				stat = makestat(&st);
 				if (!stat)
 					goto error;
 				elem = Py_BuildValue("siN", filename, kind, stat);
 			} else
 				elem = Py_BuildValue("si", filename, kind);
 			if (!elem)
 				goto error;
 			stat = NULL;
 
 			PyList_Append(list, elem);
 			Py_DECREF(elem);
 
 			entry = (attrbuf_entry *)((char *)entry + entry->length);
 		}
 	} while (err == 0);
 
 	ret = list;
 	Py_INCREF(ret);
 
 error:
 	Py_DECREF(list);
 	Py_XDECREF(stat);
 error_dir:
 	close(dfd);
 error_value:
 	return ret;
 }
 
 #endif /* __APPLE__ */
 
 static PyObject *_listdir(char *path, int pathlen, int keepstat, char *skip)
 {
 #ifdef __APPLE__
 	PyObject *ret;
 	bool fallback = false;
 
 	ret = _listdir_batch(path, pathlen, keepstat, skip, &fallback);
 	if (ret != NULL || !fallback)
 		return ret;
 #endif
 	return _listdir_stat(path, pathlen, keepstat, skip);
 }
 
 static PyObject *statfiles(PyObject *self, PyObject *args)
 {
 	PyObject *names, *stats;
 	Py_ssize_t i, count;
 
 	if (!PyArg_ParseTuple(args, "O:statfiles", &names))
 		return NULL;
 
 	count = PySequence_Length(names);
 	if (count == -1) {
 		PyErr_SetString(PyExc_TypeError, "not a sequence");
 		return NULL;
 	}
 
 	stats = PyList_New(count);
 	if (stats == NULL)
 		return NULL;
 
 	for (i = 0; i < count; i++) {
 		PyObject *stat, *pypath;
 		struct stat st;
 		int ret, kind;
 		char *path;
 
 		/* With a large file count or on a slow filesystem,
 		   don't block signals for long (issue4878). */
 		if ((i % 1000) == 999 && PyErr_CheckSignals() == -1)
 			goto bail;
 
 		pypath = PySequence_GetItem(names, i);
 		if (!pypath)
 			goto bail;
 		path = PyBytes_AsString(pypath);
 		if (path == NULL) {
 			Py_DECREF(pypath);
 			PyErr_SetString(PyExc_TypeError, "not a string");
 			goto bail;
 		}
 		ret = lstat(path, &st);
 		Py_DECREF(pypath);
 		kind = st.st_mode & S_IFMT;
 		if (ret != -1 && (kind == S_IFREG || kind == S_IFLNK)) {
 			stat = makestat(&st);
 			if (stat == NULL)
 				goto bail;
 			PyList_SET_ITEM(stats, i, stat);
 		} else {
 			Py_INCREF(Py_None);
 			PyList_SET_ITEM(stats, i, Py_None);
 		}
 	}
 
 	return stats;
 
 bail:
 	Py_DECREF(stats);
 	return NULL;
 }
 
 /*
  * recvfds() simply does not release GIL during blocking io operation because
  * command server is known to be single-threaded.
  *
  * Old systems such as Solaris don't provide CMSG_LEN, msg_control, etc.
  * Currently, recvfds() is not supported on these platforms.
  */
 #ifdef CMSG_LEN
 
 static ssize_t recvfdstobuf(int sockfd, int **rfds, void *cbuf, size_t cbufsize)
 {
 	char dummy[1];
 	struct iovec iov = {dummy, sizeof(dummy)};
 	struct msghdr msgh = {0};
 	struct cmsghdr *cmsg;
 
 	msgh.msg_iov = &iov;
 	msgh.msg_iovlen = 1;
 	msgh.msg_control = cbuf;
 	msgh.msg_controllen = (socklen_t)cbufsize;
 	if (recvmsg(sockfd, &msgh, 0) < 0)
 		return -1;
 
 	for (cmsg = CMSG_FIRSTHDR(&msgh); cmsg;
 	     cmsg = CMSG_NXTHDR(&msgh, cmsg)) {
 		if (cmsg->cmsg_level != SOL_SOCKET ||
 		    cmsg->cmsg_type != SCM_RIGHTS)
 			continue;
 		*rfds = (int *)CMSG_DATA(cmsg);
 		return (cmsg->cmsg_len - CMSG_LEN(0)) / sizeof(int);
 	}
 
 	*rfds = cbuf;
 	return 0;
 }
 
 static PyObject *recvfds(PyObject *self, PyObject *args)
 {
 	int sockfd;
 	int *rfds = NULL;
 	ssize_t rfdscount, i;
 	char cbuf[256];
 	PyObject *rfdslist = NULL;
 
 	if (!PyArg_ParseTuple(args, "i", &sockfd))
 		return NULL;
 
 	rfdscount = recvfdstobuf(sockfd, &rfds, cbuf, sizeof(cbuf));
 	if (rfdscount < 0)
 		return PyErr_SetFromErrno(PyExc_OSError);
 
 	rfdslist = PyList_New(rfdscount);
 	if (!rfdslist)
 		goto bail;
 	for (i = 0; i < rfdscount; i++) {
 		PyObject *obj = PyLong_FromLong(rfds[i]);
 		if (!obj)
 			goto bail;
 		PyList_SET_ITEM(rfdslist, i, obj);
 	}
 	return rfdslist;
 
 bail:
 	Py_XDECREF(rfdslist);
 	return NULL;
 }
 
 #endif /* CMSG_LEN */
 
 #if defined(HAVE_SETPROCTITLE)
 /* setproctitle is the first choice - available in FreeBSD */
 #define SETPROCNAME_USE_SETPROCTITLE
 #elif (defined(__linux__) || defined(__APPLE__)) && PY_MAJOR_VERSION == 2
 /* rewrite the argv buffer in place - works in Linux and OS X. Py_GetArgcArgv
  * in Python 3 returns the copied wchar_t **argv, thus unsupported. */
 #define SETPROCNAME_USE_ARGVREWRITE
 #else
 #define SETPROCNAME_USE_NONE
 #endif
 
 #ifndef SETPROCNAME_USE_NONE
 static PyObject *setprocname(PyObject *self, PyObject *args)
 {
 	const char *name = NULL;
 	if (!PyArg_ParseTuple(args, "s", &name))
 		return NULL;
 
 #if defined(SETPROCNAME_USE_SETPROCTITLE)
 	setproctitle("%s", name);
 #elif defined(SETPROCNAME_USE_ARGVREWRITE)
 	{
 		static char *argvstart = NULL;
 		static size_t argvsize = 0;
 		if (argvstart == NULL) {
 			int argc = 0, i;
 			char **argv = NULL;
 			char *argvend;
 			extern void Py_GetArgcArgv(int *argc, char ***argv);
 			Py_GetArgcArgv(&argc, &argv);
 
 			/* Check the memory we can use. Typically, argv[i] and
 			 * argv[i + 1] are continuous. */
 			argvend = argvstart = argv[0];
 			for (i = 0; i < argc; ++i) {
 				if (argv[i] > argvend || argv[i] < argvstart)
 					break; /* not continuous */
 				size_t len = strlen(argv[i]);
 				argvend = argv[i] + len + 1 /* '\0' */;
 			}
 			if (argvend > argvstart) /* sanity check */
 				argvsize = argvend - argvstart;
 		}
 
 		if (argvstart && argvsize > 1) {
 			int n = snprintf(argvstart, argvsize, "%s", name);
 			if (n >= 0 && (size_t)n < argvsize)
 				memset(argvstart + n, 0, argvsize - n);
 		}
 	}
 #endif
 
 	Py_RETURN_NONE;
 }
 #endif /* ndef SETPROCNAME_USE_NONE */
 
 #if defined(HAVE_BSD_STATFS)
 static const char *describefstype(const struct statfs *pbuf)
 {
 	/* BSD or OSX provides a f_fstypename field */
 	return pbuf->f_fstypename;
 }
 #elif defined(HAVE_LINUX_STATFS)
 static const char *describefstype(const struct statfs *pbuf)
 {
 	/* Begin of Linux filesystems */
 #ifdef ADFS_SUPER_MAGIC
 	if (pbuf->f_type == ADFS_SUPER_MAGIC)
 		return "adfs";
 #endif
 #ifdef AFFS_SUPER_MAGIC
 	if (pbuf->f_type == AFFS_SUPER_MAGIC)
 		return "affs";
 #endif
 #ifdef AUTOFS_SUPER_MAGIC
 	if (pbuf->f_type == AUTOFS_SUPER_MAGIC)
 		return "autofs";
 #endif
 #ifdef BDEVFS_MAGIC
 	if (pbuf->f_type == BDEVFS_MAGIC)
 		return "bdevfs";
 #endif
 #ifdef BEFS_SUPER_MAGIC
 	if (pbuf->f_type == BEFS_SUPER_MAGIC)
 		return "befs";
 #endif
 #ifdef BFS_MAGIC
 	if (pbuf->f_type == BFS_MAGIC)
 		return "bfs";
 #endif
 #ifdef BINFMTFS_MAGIC
 	if (pbuf->f_type == BINFMTFS_MAGIC)
 		return "binfmtfs";
 #endif
 #ifdef BTRFS_SUPER_MAGIC
 	if (pbuf->f_type == BTRFS_SUPER_MAGIC)
 		return "btrfs";
 #endif
 #ifdef CGROUP_SUPER_MAGIC
 	if (pbuf->f_type == CGROUP_SUPER_MAGIC)
 		return "cgroup";
 #endif
 #ifdef CIFS_MAGIC_NUMBER
 	if (pbuf->f_type == CIFS_MAGIC_NUMBER)
 		return "cifs";
 #endif
 #ifdef CODA_SUPER_MAGIC
 	if (pbuf->f_type == CODA_SUPER_MAGIC)
 		return "coda";
 #endif
 #ifdef COH_SUPER_MAGIC
 	if (pbuf->f_type == COH_SUPER_MAGIC)
 		return "coh";
 #endif
 #ifdef CRAMFS_MAGIC
 	if (pbuf->f_type == CRAMFS_MAGIC)
 		return "cramfs";
 #endif
 #ifdef DEBUGFS_MAGIC
 	if (pbuf->f_type == DEBUGFS_MAGIC)
 		return "debugfs";
 #endif
 #ifdef DEVFS_SUPER_MAGIC
 	if (pbuf->f_type == DEVFS_SUPER_MAGIC)
 		return "devfs";
 #endif
 #ifdef DEVPTS_SUPER_MAGIC
 	if (pbuf->f_type == DEVPTS_SUPER_MAGIC)
 		return "devpts";
 #endif
 #ifdef EFIVARFS_MAGIC
 	if (pbuf->f_type == EFIVARFS_MAGIC)
 		return "efivarfs";
 #endif
 #ifdef EFS_SUPER_MAGIC
 	if (pbuf->f_type == EFS_SUPER_MAGIC)
 		return "efs";
 #endif
 #ifdef EXT_SUPER_MAGIC
 	if (pbuf->f_type == EXT_SUPER_MAGIC)
 		return "ext";
 #endif
 #ifdef EXT2_OLD_SUPER_MAGIC
 	if (pbuf->f_type == EXT2_OLD_SUPER_MAGIC)
 		return "ext2";
 #endif
 #ifdef EXT2_SUPER_MAGIC
 	if (pbuf->f_type == EXT2_SUPER_MAGIC)
 		return "ext2";
 #endif
 #ifdef EXT3_SUPER_MAGIC
 	if (pbuf->f_type == EXT3_SUPER_MAGIC)
 		return "ext3";
 #endif
 #ifdef EXT4_SUPER_MAGIC
 	if (pbuf->f_type == EXT4_SUPER_MAGIC)
 		return "ext4";
 #endif
 #ifdef F2FS_SUPER_MAGIC
 	if (pbuf->f_type == F2FS_SUPER_MAGIC)
 		return "f2fs";
 #endif
 #ifdef FUSE_SUPER_MAGIC
 	if (pbuf->f_type == FUSE_SUPER_MAGIC)
 		return "fuse";
 #endif
 #ifdef FUTEXFS_SUPER_MAGIC
 	if (pbuf->f_type == FUTEXFS_SUPER_MAGIC)
 		return "futexfs";
 #endif
 #ifdef HFS_SUPER_MAGIC
 	if (pbuf->f_type == HFS_SUPER_MAGIC)
 		return "hfs";
 #endif
 #ifdef HOSTFS_SUPER_MAGIC
 	if (pbuf->f_type == HOSTFS_SUPER_MAGIC)
 		return "hostfs";
 #endif
 #ifdef HPFS_SUPER_MAGIC
 	if (pbuf->f_type == HPFS_SUPER_MAGIC)
 		return "hpfs";
 #endif
 #ifdef HUGETLBFS_MAGIC
 	if (pbuf->f_type == HUGETLBFS_MAGIC)
 		return "hugetlbfs";
 #endif
 #ifdef ISOFS_SUPER_MAGIC
 	if (pbuf->f_type == ISOFS_SUPER_MAGIC)
 		return "isofs";
 #endif
 #ifdef JFFS2_SUPER_MAGIC
 	if (pbuf->f_type == JFFS2_SUPER_MAGIC)
 		return "jffs2";
 #endif
 #ifdef JFS_SUPER_MAGIC
 	if (pbuf->f_type == JFS_SUPER_MAGIC)
 		return "jfs";
 #endif
 #ifdef MINIX_SUPER_MAGIC
 	if (pbuf->f_type == MINIX_SUPER_MAGIC)
 		return "minix";
 #endif
 #ifdef MINIX2_SUPER_MAGIC
 	if (pbuf->f_type == MINIX2_SUPER_MAGIC)
 		return "minix2";
 #endif
 #ifdef MINIX3_SUPER_MAGIC
 	if (pbuf->f_type == MINIX3_SUPER_MAGIC)
 		return "minix3";
 #endif
 #ifdef MQUEUE_MAGIC
 	if (pbuf->f_type == MQUEUE_MAGIC)
 		return "mqueue";
 #endif
 #ifdef MSDOS_SUPER_MAGIC
 	if (pbuf->f_type == MSDOS_SUPER_MAGIC)
 		return "msdos";
 #endif
 #ifdef NCP_SUPER_MAGIC
 	if (pbuf->f_type == NCP_SUPER_MAGIC)
 		return "ncp";
 #endif
 #ifdef NFS_SUPER_MAGIC
 	if (pbuf->f_type == NFS_SUPER_MAGIC)
 		return "nfs";
 #endif
 #ifdef NILFS_SUPER_MAGIC
 	if (pbuf->f_type == NILFS_SUPER_MAGIC)
 		return "nilfs";
 #endif
 #ifdef NTFS_SB_MAGIC
 	if (pbuf->f_type == NTFS_SB_MAGIC)
 		return "ntfs-sb";
 #endif
 #ifdef OCFS2_SUPER_MAGIC
 	if (pbuf->f_type == OCFS2_SUPER_MAGIC)
 		return "ocfs2";
 #endif
 #ifdef OPENPROM_SUPER_MAGIC
 	if (pbuf->f_type == OPENPROM_SUPER_MAGIC)
 		return "openprom";
 #endif
 #ifdef OVERLAYFS_SUPER_MAGIC
 	if (pbuf->f_type == OVERLAYFS_SUPER_MAGIC)
 		return "overlay";
 #endif
 #ifdef PIPEFS_MAGIC
 	if (pbuf->f_type == PIPEFS_MAGIC)
 		return "pipefs";
 #endif
 #ifdef PROC_SUPER_MAGIC
 	if (pbuf->f_type == PROC_SUPER_MAGIC)
 		return "proc";
 #endif
 #ifdef PSTOREFS_MAGIC
 	if (pbuf->f_type == PSTOREFS_MAGIC)
 		return "pstorefs";
 #endif
 #ifdef QNX4_SUPER_MAGIC
 	if (pbuf->f_type == QNX4_SUPER_MAGIC)
 		return "qnx4";
 #endif
 #ifdef QNX6_SUPER_MAGIC
 	if (pbuf->f_type == QNX6_SUPER_MAGIC)
 		return "qnx6";
 #endif
 #ifdef RAMFS_MAGIC
 	if (pbuf->f_type == RAMFS_MAGIC)
 		return "ramfs";
 #endif
 #ifdef REISERFS_SUPER_MAGIC
 	if (pbuf->f_type == REISERFS_SUPER_MAGIC)
 		return "reiserfs";
 #endif
 #ifdef ROMFS_MAGIC
 	if (pbuf->f_type == ROMFS_MAGIC)
 		return "romfs";
 #endif
 #ifdef SECURITYFS_MAGIC
 	if (pbuf->f_type == SECURITYFS_MAGIC)
 		return "securityfs";
 #endif
 #ifdef SELINUX_MAGIC
 	if (pbuf->f_type == SELINUX_MAGIC)
 		return "selinux";
 #endif
 #ifdef SMACK_MAGIC
 	if (pbuf->f_type == SMACK_MAGIC)
 		return "smack";
 #endif
 #ifdef SMB_SUPER_MAGIC
 	if (pbuf->f_type == SMB_SUPER_MAGIC)
 		return "smb";
 #endif
 #ifdef SOCKFS_MAGIC
 	if (pbuf->f_type == SOCKFS_MAGIC)
 		return "sockfs";
 #endif
 #ifdef SQUASHFS_MAGIC
 	if (pbuf->f_type == SQUASHFS_MAGIC)
 		return "squashfs";
 #endif
 #ifdef SYSFS_MAGIC
 	if (pbuf->f_type == SYSFS_MAGIC)
 		return "sysfs";
 #endif
 #ifdef SYSV2_SUPER_MAGIC
 	if (pbuf->f_type == SYSV2_SUPER_MAGIC)
 		return "sysv2";
 #endif
 #ifdef SYSV4_SUPER_MAGIC
 	if (pbuf->f_type == SYSV4_SUPER_MAGIC)
 		return "sysv4";
 #endif
 #ifdef TMPFS_MAGIC
 	if (pbuf->f_type == TMPFS_MAGIC)
 		return "tmpfs";
 #endif
 #ifdef UDF_SUPER_MAGIC
 	if (pbuf->f_type == UDF_SUPER_MAGIC)
 		return "udf";
 #endif
 #ifdef UFS_MAGIC
 	if (pbuf->f_type == UFS_MAGIC)
 		return "ufs";
 #endif
 #ifdef USBDEVICE_SUPER_MAGIC
 	if (pbuf->f_type == USBDEVICE_SUPER_MAGIC)
 		return "usbdevice";
 #endif
 #ifdef V9FS_MAGIC
 	if (pbuf->f_type == V9FS_MAGIC)
 		return "v9fs";
 #endif
 #ifdef VXFS_SUPER_MAGIC
 	if (pbuf->f_type == VXFS_SUPER_MAGIC)
 		return "vxfs";
 #endif
 #ifdef XENFS_SUPER_MAGIC
 	if (pbuf->f_type == XENFS_SUPER_MAGIC)
 		return "xenfs";
 #endif
 #ifdef XENIX_SUPER_MAGIC
 	if (pbuf->f_type == XENIX_SUPER_MAGIC)
 		return "xenix";
 #endif
 #ifdef XFS_SUPER_MAGIC
 	if (pbuf->f_type == XFS_SUPER_MAGIC)
 		return "xfs";
 #endif
 	/* End of Linux filesystems */
 	return NULL;
 }
 #endif /* def HAVE_LINUX_STATFS */
 
 #if defined(HAVE_BSD_STATFS) || defined(HAVE_LINUX_STATFS)
 /* given a directory path, return filesystem type name (best-effort) */
 static PyObject *getfstype(PyObject *self, PyObject *args)
 {
 	const char *path = NULL;
 	struct statfs buf;
 	int r;
 	if (!PyArg_ParseTuple(args, "s", &path))
 		return NULL;
 
 	memset(&buf, 0, sizeof(buf));
 	r = statfs(path, &buf);
 	if (r != 0)
 		return PyErr_SetFromErrno(PyExc_OSError);
 	return Py_BuildValue("s", describefstype(&buf));
 }
 #endif /* defined(HAVE_LINUX_STATFS) || defined(HAVE_BSD_STATFS) */
 
 #endif /* ndef _WIN32 */
 
 static PyObject *listdir(PyObject *self, PyObject *args, PyObject *kwargs)
 {
 	PyObject *statobj = NULL; /* initialize - optional arg */
 	PyObject *skipobj = NULL; /* initialize - optional arg */
 	char *path, *skip = NULL;
 	int wantstat, plen;
 
 	static char *kwlist[] = {"path", "stat", "skip", NULL};
 
 	if (!PyArg_ParseTupleAndKeywords(args, kwargs, "s#|OO:listdir",
 			kwlist, &path, &plen, &statobj, &skipobj))
 		return NULL;
 
 	wantstat = statobj && PyObject_IsTrue(statobj);
 
 	if (skipobj && skipobj != Py_None) {
 		skip = PyBytes_AsString(skipobj);
 		if (!skip)
 			return NULL;
 	}
 
 	return _listdir(path, plen, wantstat, skip);
 }
 
 #ifdef _WIN32
 static PyObject *posixfile(PyObject *self, PyObject *args, PyObject *kwds)
 {
 	static char *kwlist[] = {"name", "mode", "buffering", NULL};
 	PyObject *file_obj = NULL;
 	char *name = NULL;
 	char *mode = "rb";
 	DWORD access = 0;
 	DWORD creation;
 	HANDLE handle;
 	int fd, flags = 0;
 	int bufsize = -1;
 	char m0, m1, m2;
 	char fpmode[4];
 	int fppos = 0;
 	int plus;
 	FILE *fp;
 
 	if (!PyArg_ParseTupleAndKeywords(args, kwds, "et|si:posixfile", kwlist,
 					 Py_FileSystemDefaultEncoding,
 					 &name, &mode, &bufsize))
 		return NULL;
 
 	m0 = mode[0];
 	m1 = m0 ? mode[1] : '\0';
 	m2 = m1 ? mode[2] : '\0';
 	plus = m1 == '+' || m2 == '+';
 
 	fpmode[fppos++] = m0;
 	if (m1 == 'b' || m2 == 'b') {
 		flags = _O_BINARY;
 		fpmode[fppos++] = 'b';
 	}
 	else
 		flags = _O_TEXT;
 	if (m0 == 'r' && !plus) {
 		flags |= _O_RDONLY;
 		access = GENERIC_READ;
 	} else {
 		/*
 		work around http://support.microsoft.com/kb/899149 and
 		set _O_RDWR for 'w' and 'a', even if mode has no '+'
 		*/
 		flags |= _O_RDWR;
 		access = GENERIC_READ | GENERIC_WRITE;
 		fpmode[fppos++] = '+';
 	}
 	fpmode[fppos++] = '\0';
 
 	switch (m0) {
 	case 'r':
 		creation = OPEN_EXISTING;
 		break;
 	case 'w':
 		creation = CREATE_ALWAYS;
 		break;
 	case 'a':
 		creation = OPEN_ALWAYS;
 		flags |= _O_APPEND;
 		break;
 	default:
 		PyErr_Format(PyExc_ValueError,
 			     "mode string must begin with one of 'r', 'w', "
 			     "or 'a', not '%c'", m0);
 		goto bail;
 	}
 
 	handle = CreateFile(name, access,
 			    FILE_SHARE_READ | FILE_SHARE_WRITE |
 			    FILE_SHARE_DELETE,
 			    NULL,
 			    creation,
 			    FILE_ATTRIBUTE_NORMAL,
 			    0);
 
 	if (handle == INVALID_HANDLE_VALUE) {
 		PyErr_SetFromWindowsErrWithFilename(GetLastError(), name);
 		goto bail;
 	}
 
 	fd = _open_osfhandle((intptr_t)handle, flags);
 
 	if (fd == -1) {
 		CloseHandle(handle);
 		PyErr_SetFromErrnoWithFilename(PyExc_IOError, name);
 		goto bail;
 	}
 #ifndef IS_PY3K
 	fp = _fdopen(fd, fpmode);
 	if (fp == NULL) {
 		_close(fd);
 		PyErr_SetFromErrnoWithFilename(PyExc_IOError, name);
 		goto bail;
 	}
 
 	file_obj = PyFile_FromFile(fp, name, mode, fclose);
 	if (file_obj == NULL) {
 		fclose(fp);
 		goto bail;
 	}
 
 	PyFile_SetBufSize(file_obj, bufsize);
 #else
 	file_obj = PyFile_FromFd(fd, name, mode, bufsize, NULL, NULL, NULL, 1);
 	if (file_obj == NULL)
 		goto bail;
 #endif
 bail:
 	PyMem_Free(name);
 	return file_obj;
 }
 #endif
 
 #ifdef __APPLE__
 #include <ApplicationServices/ApplicationServices.h>
 
 static PyObject *isgui(PyObject *self)
 {
 	CFDictionaryRef dict = CGSessionCopyCurrentDictionary();
 
 	if (dict != NULL) {
 		CFRelease(dict);
 		Py_RETURN_TRUE;
 	} else {
 		Py_RETURN_FALSE;
 	}
 }
 #endif
 
 static char osutil_doc[] = "Native operating system services.";
 
 static PyMethodDef methods[] = {
 	{"listdir", (PyCFunction)listdir, METH_VARARGS | METH_KEYWORDS,
 	 "list a directory\n"},
 #ifdef _WIN32
 	{"posixfile", (PyCFunction)posixfile, METH_VARARGS | METH_KEYWORDS,
 	 "Open a file with POSIX-like semantics.\n"
 "On error, this function may raise either a WindowsError or an IOError."},
 #else
 	{"statfiles", (PyCFunction)statfiles, METH_VARARGS | METH_KEYWORDS,
 	 "stat a series of files or symlinks\n"
 "Returns None for non-existent entries and entries of other types.\n"},
 #ifdef CMSG_LEN
 	{"recvfds", (PyCFunction)recvfds, METH_VARARGS,
 	 "receive list of file descriptors via socket\n"},
 #endif
 #ifndef SETPROCNAME_USE_NONE
 	{"setprocname", (PyCFunction)setprocname, METH_VARARGS,
 	 "set process title (best-effort)\n"},
 #endif
 #if defined(HAVE_BSD_STATFS) || defined(HAVE_LINUX_STATFS)
 	{"getfstype", (PyCFunction)getfstype, METH_VARARGS,
 	 "get filesystem type (best-effort)\n"},
 #endif
 #endif /* ndef _WIN32 */
 #ifdef __APPLE__
 	{
 		"isgui", (PyCFunction)isgui, METH_NOARGS,
 		"Is a CoreGraphics session available?"
 	},
 #endif
 	{NULL, NULL}
 };
 
 static const int version = 1;
 
 #ifdef IS_PY3K
 static struct PyModuleDef osutil_module = {
 	PyModuleDef_HEAD_INIT,
 	"osutil",
 	osutil_doc,
 	-1,
 	methods
 };
 
 PyMODINIT_FUNC PyInit_osutil(void)
 {
 	PyObject *m;
 	if (PyType_Ready(&listdir_stat_type) < 0)
 		return NULL;
 
 	m = PyModule_Create(&osutil_module);
 	PyModule_AddIntConstant(m, "version", version);
 	return m;
 }
 #else
 PyMODINIT_FUNC initosutil(void)
 {
 	PyObject *m;
 	if (PyType_Ready(&listdir_stat_type) == -1)
 		return;
 
 	m = Py_InitModule3("osutil", methods, osutil_doc);
 	PyModule_AddIntConstant(m, "version", version);
 }
 #endif

mercurial/cext/parsers.c

@@ -1,802 +1,802 b''
 /*
  parsers.c - efficient content parsing
 
  Copyright 2008 Matt Mackall <[e-mail]> and others
 
  This software may be used and distributed according to the terms of
  the GNU General Public License, incorporated herein by reference.
 */
 
 #include <Python.h>
 #include <ctype.h>
 #include <stddef.h>
 #include <string.h>
 
+#include "bitmanipulation.h"
 #include "charencode.h"
 #include "util.h"
-#include "bitmanipulation.h"
 
 #ifdef IS_PY3K
 /* The mapping of Python types is meant to be temporary to get Python
  * 3 to compile. We should remove this once Python 3 support is fully
  * supported and proper types are used in the extensions themselves. */
 #define PyInt_Check PyLong_Check
 #define PyInt_FromLong PyLong_FromLong
 #define PyInt_FromSsize_t PyLong_FromSsize_t
 #define PyInt_AsLong PyLong_AsLong
 #endif
 
 static const char *const versionerrortext = "Python minor version mismatch";
 
 static PyObject *dict_new_presized(PyObject *self, PyObject *args)
 {
 	Py_ssize_t expected_size;
 
 	if (!PyArg_ParseTuple(args, "n:make_presized_dict", &expected_size))
 		return NULL;
 
 	return _dict_new_presized(expected_size);
 }
 
 /*
  * This code assumes that a manifest is stitched together with newline
  * ('\n') characters.
  */
 static PyObject *parse_manifest(PyObject *self, PyObject *args)
 {
 	PyObject *mfdict, *fdict;
 	char *str, *start, *end;
 	int len;
 
 	if (!PyArg_ParseTuple(args, "O!O!s#:parse_manifest",
 			      &PyDict_Type, &mfdict,
 			      &PyDict_Type, &fdict,
 			      &str, &len))
 		goto quit;
 
 	start = str;
 	end = str + len;
 	while (start < end) {
 		PyObject *file = NULL, *node = NULL;
 		PyObject *flags = NULL;
 		char *zero = NULL, *newline = NULL;
 		ptrdiff_t nlen;
 
 		zero = memchr(start, '\0', end - start);
 		if (!zero) {
 			PyErr_SetString(PyExc_ValueError,
 					"manifest entry has no separator");
 			goto quit;
 		}
 
 		newline = memchr(zero + 1, '\n', end - (zero + 1));
 		if (!newline) {
 			PyErr_SetString(PyExc_ValueError,
 					"manifest contains trailing garbage");
 			goto quit;
 		}
 
 		file = PyBytes_FromStringAndSize(start, zero - start);
 
 		if (!file)
 			goto bail;
 
 		nlen = newline - zero - 1;
 
 		node = unhexlify(zero + 1, nlen > 40 ? 40 : (Py_ssize_t)nlen);
 		if (!node)
 			goto bail;
 
 		if (nlen > 40) {
 			flags = PyBytes_FromStringAndSize(zero + 41,
 							   nlen - 40);
 			if (!flags)
 				goto bail;
 
 			if (PyDict_SetItem(fdict, file, flags) == -1)
 				goto bail;
 		}
 
 		if (PyDict_SetItem(mfdict, file, node) == -1)
 			goto bail;
 
 		start = newline + 1;
 
 		Py_XDECREF(flags);
 		Py_XDECREF(node);
 		Py_XDECREF(file);
 		continue;
 	bail:
 		Py_XDECREF(flags);
 		Py_XDECREF(node);
 		Py_XDECREF(file);
 		goto quit;
 	}
 
 	Py_INCREF(Py_None);
 	return Py_None;
 quit:
 	return NULL;
 }
 
 static inline dirstateTupleObject *make_dirstate_tuple(char state, int mode,
 						       int size, int mtime)
 {
 	dirstateTupleObject *t = PyObject_New(dirstateTupleObject,
 					      &dirstateTupleType);
 	if (!t)
 		return NULL;
 	t->state = state;
 	t->mode = mode;
 	t->size = size;
 	t->mtime = mtime;
 	return t;
 }
 
 static PyObject *dirstate_tuple_new(PyTypeObject *subtype, PyObject *args,
 				    PyObject *kwds)
 {
 	/* We do all the initialization here and not a tp_init function because
 	 * dirstate_tuple is immutable. */
 	dirstateTupleObject *t;
 	char state;
 	int size, mode, mtime;
 	if (!PyArg_ParseTuple(args, "ciii", &state, &mode, &size, &mtime))
 		return NULL;
 
 	t = (dirstateTupleObject *)subtype->tp_alloc(subtype, 1);
 	if (!t)
 		return NULL;
 	t->state = state;
 	t->mode = mode;
 	t->size = size;
 	t->mtime = mtime;
 
 	return (PyObject *)t;
 }
 
 static void dirstate_tuple_dealloc(PyObject *o)
 {
 	PyObject_Del(o);
 }
 
 static Py_ssize_t dirstate_tuple_length(PyObject *o)
 {
 	return 4;
 }
 
 static PyObject *dirstate_tuple_item(PyObject *o, Py_ssize_t i)
 {
 	dirstateTupleObject *t = (dirstateTupleObject *)o;
 	switch (i) {
 	case 0:
 		return PyBytes_FromStringAndSize(&t->state, 1);
 	case 1:
 		return PyInt_FromLong(t->mode);
 	case 2:
 		return PyInt_FromLong(t->size);
 	case 3:
 		return PyInt_FromLong(t->mtime);
 	default:
 		PyErr_SetString(PyExc_IndexError, "index out of range");
 		return NULL;
 	}
 }
 
 static PySequenceMethods dirstate_tuple_sq = {
 	dirstate_tuple_length,     /* sq_length */
 	0,                         /* sq_concat */
 	0,                         /* sq_repeat */
 	dirstate_tuple_item,       /* sq_item */
 	0,                         /* sq_ass_item */
 	0,                         /* sq_contains */
 	0,                         /* sq_inplace_concat */
 	0                          /* sq_inplace_repeat */
 };
 
 PyTypeObject dirstateTupleType = {
 	PyVarObject_HEAD_INIT(NULL, 0)
 	"dirstate_tuple",          /* tp_name */
 	sizeof(dirstateTupleObject),/* tp_basicsize */
 	0,                         /* tp_itemsize */
 	(destructor)dirstate_tuple_dealloc, /* tp_dealloc */
 	0,                         /* tp_print */
 	0,                         /* tp_getattr */
 	0,                         /* tp_setattr */
 	0,                         /* tp_compare */
 	0,                         /* tp_repr */
 	0,                         /* tp_as_number */
 	&dirstate_tuple_sq,        /* tp_as_sequence */
 	0,                         /* tp_as_mapping */
 	0,                         /* tp_hash  */
 	0,                         /* tp_call */
 	0,                         /* tp_str */
 	0,                         /* tp_getattro */
 	0,                         /* tp_setattro */
 	0,                         /* tp_as_buffer */
 	Py_TPFLAGS_DEFAULT,        /* tp_flags */
 	"dirstate tuple",          /* tp_doc */
 	0,                         /* tp_traverse */
 	0,                         /* tp_clear */
 	0,                         /* tp_richcompare */
 	0,                         /* tp_weaklistoffset */
 	0,                         /* tp_iter */
 	0,                         /* tp_iternext */
 	0,                         /* tp_methods */
 	0,                         /* tp_members */
 	0,                         /* tp_getset */
 	0,                         /* tp_base */
 	0,                         /* tp_dict */
 	0,                         /* tp_descr_get */
 	0,                         /* tp_descr_set */
 	0,                         /* tp_dictoffset */
 	0,                         /* tp_init */
 	0,                         /* tp_alloc */
 	dirstate_tuple_new,        /* tp_new */
 };
 
 static PyObject *parse_dirstate(PyObject *self, PyObject *args)
 {
 	PyObject *dmap, *cmap, *parents = NULL, *ret = NULL;
 	PyObject *fname = NULL, *cname = NULL, *entry = NULL;
 	char state, *cur, *str, *cpos;
 	int mode, size, mtime;
 	unsigned int flen, len, pos = 40;
 	int readlen;
 
 	if (!PyArg_ParseTuple(args, "O!O!s#:parse_dirstate",
 			      &PyDict_Type, &dmap,
 			      &PyDict_Type, &cmap,
 			      &str, &readlen))
 		goto quit;
 
 	len = readlen;
 
 	/* read parents */
 	if (len < 40) {
 		PyErr_SetString(
 			PyExc_ValueError, "too little data for parents");
 		goto quit;
 	}
 
 	parents = Py_BuildValue("s#s#", str, 20, str + 20, 20);
 	if (!parents)
 		goto quit;
 
 	/* read filenames */
 	while (pos >= 40 && pos < len) {
 		if (pos + 17 > len) {
 			PyErr_SetString(PyExc_ValueError,
 					"overflow in dirstate");
 			goto quit;
 		}
 		cur = str + pos;
 		/* unpack header */
 		state = *cur;
 		mode = getbe32(cur + 1);
 		size = getbe32(cur + 5);
 		mtime = getbe32(cur + 9);
 		flen = getbe32(cur + 13);
 		pos += 17;
 		cur += 17;
 		if (flen > len - pos) {
 			PyErr_SetString(PyExc_ValueError, "overflow in dirstate");
 			goto quit;
 		}
 
 		entry = (PyObject *)make_dirstate_tuple(state, mode, size,
 							mtime);
 		cpos = memchr(cur, 0, flen);
 		if (cpos) {
 			fname = PyBytes_FromStringAndSize(cur, cpos - cur);
 			cname = PyBytes_FromStringAndSize(cpos + 1,
 							   flen - (cpos - cur) - 1);
 			if (!fname || !cname ||
 			    PyDict_SetItem(cmap, fname, cname) == -1 ||
 			    PyDict_SetItem(dmap, fname, entry) == -1)
 				goto quit;
 			Py_DECREF(cname);
 		} else {
 			fname = PyBytes_FromStringAndSize(cur, flen);
 			if (!fname ||
 			    PyDict_SetItem(dmap, fname, entry) == -1)
 				goto quit;
 		}
 		Py_DECREF(fname);
 		Py_DECREF(entry);
 		fname = cname = entry = NULL;
 		pos += flen;
 	}
 
 	ret = parents;
 	Py_INCREF(ret);
 quit:
 	Py_XDECREF(fname);
 	Py_XDECREF(cname);
 	Py_XDECREF(entry);
 	Py_XDECREF(parents);
 	return ret;
 }
 
 /*
  * Build a set of non-normal and other parent entries from the dirstate dmap
 */
 static PyObject *nonnormalotherparententries(PyObject *self, PyObject *args) {
 	PyObject *dmap, *fname, *v;
 	PyObject *nonnset = NULL, *otherpset = NULL, *result = NULL;
 	Py_ssize_t pos;
 
 	if (!PyArg_ParseTuple(args, "O!:nonnormalentries",
 			      &PyDict_Type, &dmap))
 		goto bail;
 
 	nonnset = PySet_New(NULL);
 	if (nonnset == NULL)
 		goto bail;
 
 	otherpset = PySet_New(NULL);
 	if (otherpset == NULL)
 		goto bail;
 
 	pos = 0;
 	while (PyDict_Next(dmap, &pos, &fname, &v)) {
 		dirstateTupleObject *t;
 		if (!dirstate_tuple_check(v)) {
 			PyErr_SetString(PyExc_TypeError,
 					"expected a dirstate tuple");
 			goto bail;
 		}
 		t = (dirstateTupleObject *)v;
 
 		if (t->state == 'n' && t->size == -2) {
 			if (PySet_Add(otherpset, fname) == -1) {
 				goto bail;
 			}
 		}
 
 		if (t->state == 'n' && t->mtime != -1)
 			continue;
 		if (PySet_Add(nonnset, fname) == -1)
 			goto bail;
 	}
 
 	result = Py_BuildValue("(OO)", nonnset, otherpset);
 	if (result == NULL)
 		goto bail;
 	Py_DECREF(nonnset);
 	Py_DECREF(otherpset);
 	return result;
 bail:
 	Py_XDECREF(nonnset);
 	Py_XDECREF(otherpset);
 	Py_XDECREF(result);
 	return NULL;
 }
 
 /*
  * Efficiently pack a dirstate object into its on-disk format.
  */
 static PyObject *pack_dirstate(PyObject *self, PyObject *args)
 {
 	PyObject *packobj = NULL;
 	PyObject *map, *copymap, *pl, *mtime_unset = NULL;
 	Py_ssize_t nbytes, pos, l;
 	PyObject *k, *v = NULL, *pn;
 	char *p, *s;
 	int now;
 
 	if (!PyArg_ParseTuple(args, "O!O!Oi:pack_dirstate",
 			      &PyDict_Type, &map, &PyDict_Type, &copymap,
 			      &pl, &now))
 		return NULL;
 
 	if (!PySequence_Check(pl) || PySequence_Size(pl) != 2) {
 		PyErr_SetString(PyExc_TypeError, "expected 2-element sequence");
 		return NULL;
 	}
 
 	/* Figure out how much we need to allocate. */
 	for (nbytes = 40, pos = 0; PyDict_Next(map, &pos, &k, &v);) {
 		PyObject *c;
 		if (!PyBytes_Check(k)) {
 			PyErr_SetString(PyExc_TypeError, "expected string key");
 			goto bail;
 		}
 		nbytes += PyBytes_GET_SIZE(k) + 17;
 		c = PyDict_GetItem(copymap, k);
 		if (c) {
 			if (!PyBytes_Check(c)) {
 				PyErr_SetString(PyExc_TypeError,
 						"expected string key");
 				goto bail;
 			}
 			nbytes += PyBytes_GET_SIZE(c) + 1;
 		}
 	}
 
 	packobj = PyBytes_FromStringAndSize(NULL, nbytes);
 	if (packobj == NULL)
 		goto bail;
 
 	p = PyBytes_AS_STRING(packobj);
 
 	pn = PySequence_ITEM(pl, 0);
 	if (PyBytes_AsStringAndSize(pn, &s, &l) == -1 || l != 20) {
 		PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash");
 		goto bail;
 	}
 	memcpy(p, s, l);
 	p += 20;
 	pn = PySequence_ITEM(pl, 1);
 	if (PyBytes_AsStringAndSize(pn, &s, &l) == -1 || l != 20) {
 		PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash");
 		goto bail;
 	}
 	memcpy(p, s, l);
 	p += 20;
 
 	for (pos = 0; PyDict_Next(map, &pos, &k, &v); ) {
 		dirstateTupleObject *tuple;
 		char state;
 		int mode, size, mtime;
 		Py_ssize_t len, l;
 		PyObject *o;
 		char *t;
 
 		if (!dirstate_tuple_check(v)) {
 			PyErr_SetString(PyExc_TypeError,
 					"expected a dirstate tuple");
 			goto bail;
 		}
 		tuple = (dirstateTupleObject *)v;
 
 		state = tuple->state;
 		mode = tuple->mode;
 		size = tuple->size;
 		mtime = tuple->mtime;
 		if (state == 'n' && mtime == now) {
 			/* See pure/parsers.py:pack_dirstate for why we do
 			 * this. */
 			mtime = -1;
 			mtime_unset = (PyObject *)make_dirstate_tuple(
 				state, mode, size, mtime);
 			if (!mtime_unset)
 				goto bail;
 			if (PyDict_SetItem(map, k, mtime_unset) == -1)
 				goto bail;
 			Py_DECREF(mtime_unset);
 			mtime_unset = NULL;
 		}
 		*p++ = state;
 		putbe32((uint32_t)mode, p);
 		putbe32((uint32_t)size, p + 4);
 		putbe32((uint32_t)mtime, p + 8);
 		t = p + 12;
 		p += 16;
 		len = PyBytes_GET_SIZE(k);
 		memcpy(p, PyBytes_AS_STRING(k), len);
 		p += len;
 		o = PyDict_GetItem(copymap, k);
 		if (o) {
 			*p++ = '\0';
 			l = PyBytes_GET_SIZE(o);
 			memcpy(p, PyBytes_AS_STRING(o), l);
 			p += l;
 			len += l + 1;
 		}
 		putbe32((uint32_t)len, t);
 	}
 
 	pos = p - PyBytes_AS_STRING(packobj);
 	if (pos != nbytes) {
 		PyErr_Format(PyExc_SystemError, "bad dirstate size: %ld != %ld",
                              (long)pos, (long)nbytes);
 		goto bail;
 	}
 
 	return packobj;
 bail:
 	Py_XDECREF(mtime_unset);
 	Py_XDECREF(packobj);
 	Py_XDECREF(v);
 	return NULL;
 }
 
 #define BUMPED_FIX 1
 #define USING_SHA_256 2
 #define FM1_HEADER_SIZE (4 + 8 + 2 + 2 + 1 + 1 + 1)
 
 static PyObject *readshas(
 	const char *source, unsigned char num, Py_ssize_t hashwidth)
 {
 	int i;
 	PyObject *list = PyTuple_New(num);
 	if (list == NULL) {
 		return NULL;
 	}
 	for (i = 0; i < num; i++) {
 		PyObject *hash = PyBytes_FromStringAndSize(source, hashwidth);
 		if (hash == NULL) {
 			Py_DECREF(list);
 			return NULL;
 		}
 		PyTuple_SET_ITEM(list, i, hash);
 		source += hashwidth;
 	}
 	return list;
 }
 
 static PyObject *fm1readmarker(const char *databegin, const char *dataend,
 			       uint32_t *msize)
 {
 	const char *data = databegin;
 	const char *meta;
 
 	double mtime;
 	int16_t tz;
 	uint16_t flags;
 	unsigned char nsuccs, nparents, nmetadata;
 	Py_ssize_t hashwidth = 20;
 
 	PyObject *prec = NULL, *parents = NULL, *succs = NULL;
 	PyObject *metadata = NULL, *ret = NULL;
 	int i;
 
 	if (data + FM1_HEADER_SIZE > dataend) {
 		goto overflow;
 	}
 
 	*msize = getbe32(data);
 	data += 4;
 	mtime = getbefloat64(data);
 	data += 8;
 	tz = getbeint16(data);
 	data += 2;
 	flags = getbeuint16(data);
 	data += 2;
 
 	if (flags & USING_SHA_256) {
 		hashwidth = 32;
 	}
 
 	nsuccs = (unsigned char)(*data++);
 	nparents = (unsigned char)(*data++);
 	nmetadata = (unsigned char)(*data++);
 
 	if (databegin + *msize > dataend) {
 		goto overflow;
 	}
 	dataend = databegin + *msize;  /* narrow down to marker size */
 
 	if (data + hashwidth > dataend) {
 		goto overflow;
 	}
 	prec = PyBytes_FromStringAndSize(data, hashwidth);
 	data += hashwidth;
 	if (prec == NULL) {
 		goto bail;
 	}
 
 	if (data + nsuccs * hashwidth > dataend) {
 		goto overflow;
 	}
 	succs = readshas(data, nsuccs, hashwidth);
 	if (succs == NULL) {
 		goto bail;
 	}
 	data += nsuccs * hashwidth;
 
 	if (nparents == 1 || nparents == 2) {
 		if (data + nparents * hashwidth > dataend) {
 			goto overflow;
 		}
 		parents = readshas(data, nparents, hashwidth);
 		if (parents == NULL) {
 			goto bail;
 		}
 		data += nparents * hashwidth;
 	} else {
 		parents = Py_None;
 		Py_INCREF(parents);
 	}
 
 	if (data + 2 * nmetadata > dataend) {
 		goto overflow;
 	}
 	meta = data + (2 * nmetadata);
 	metadata = PyTuple_New(nmetadata);
 	if (metadata == NULL) {
 		goto bail;
 	}
 	for (i = 0; i < nmetadata; i++) {
 		PyObject *tmp, *left = NULL, *right = NULL;
 		Py_ssize_t leftsize = (unsigned char)(*data++);
 		Py_ssize_t rightsize = (unsigned char)(*data++);
 		if (meta + leftsize + rightsize > dataend) {
 			goto overflow;
 		}
 		left = PyBytes_FromStringAndSize(meta, leftsize);
 		meta += leftsize;
 		right = PyBytes_FromStringAndSize(meta, rightsize);
 		meta += rightsize;
 		tmp = PyTuple_New(2);
 		if (!left || !right || !tmp) {
 			Py_XDECREF(left);
 			Py_XDECREF(right);
 			Py_XDECREF(tmp);
 			goto bail;
 		}
 		PyTuple_SET_ITEM(tmp, 0, left);
 		PyTuple_SET_ITEM(tmp, 1, right);
 		PyTuple_SET_ITEM(metadata, i, tmp);
 	}
 	ret = Py_BuildValue("(OOHO(di)O)", prec, succs, flags,
 			    metadata, mtime, (int)tz * 60, parents);
 	goto bail;  /* return successfully */
 
 overflow:
 	PyErr_SetString(PyExc_ValueError, "overflow in obsstore");
 bail:
 	Py_XDECREF(prec);
 	Py_XDECREF(succs);
 	Py_XDECREF(metadata);
 	Py_XDECREF(parents);
 	return ret;
 }
 
 
 static PyObject *fm1readmarkers(PyObject *self, PyObject *args) {
 	const char *data, *dataend;
 	int datalen;
 	Py_ssize_t offset, stop;
 	PyObject *markers = NULL;
 
 	if (!PyArg_ParseTuple(args, "s#nn", &data, &datalen, &offset, &stop)) {
 		return NULL;
 	}
 	dataend = data + datalen;
 	data += offset;
 	markers = PyList_New(0);
 	if (!markers) {
 		return NULL;
 	}
 	while (offset < stop) {
 		uint32_t msize;
 		int error;
 		PyObject *record = fm1readmarker(data, dataend, &msize);
 		if (!record) {
 			goto bail;
 		}
 		error = PyList_Append(markers, record);
 		Py_DECREF(record);
 		if (error) {
 			goto bail;
 		}
 		data += msize;
 		offset += msize;
 	}
 	return markers;
 bail:
 	Py_DECREF(markers);
 	return NULL;
 }
 
 static char parsers_doc[] = "Efficient content parsing.";
 
 PyObject *encodedir(PyObject *self, PyObject *args);
 PyObject *pathencode(PyObject *self, PyObject *args);
 PyObject *lowerencode(PyObject *self, PyObject *args);
 PyObject *parse_index2(PyObject *self, PyObject *args);
 
 static PyMethodDef methods[] = {
 	{"pack_dirstate", pack_dirstate, METH_VARARGS, "pack a dirstate\n"},
 	{"nonnormalotherparententries", nonnormalotherparententries, METH_VARARGS,
 	"create a set containing non-normal and other parent entries of given "
 	"dirstate\n"},
 	{"parse_manifest", parse_manifest, METH_VARARGS, "parse a manifest\n"},
 	{"parse_dirstate", parse_dirstate, METH_VARARGS, "parse a dirstate\n"},
 	{"parse_index2", parse_index2, METH_VARARGS, "parse a revlog index\n"},
 	{"isasciistr", isasciistr, METH_VARARGS, "check if an ASCII string\n"},
 	{"asciilower", asciilower, METH_VARARGS, "lowercase an ASCII string\n"},
 	{"asciiupper", asciiupper, METH_VARARGS, "uppercase an ASCII string\n"},
 	{"dict_new_presized", dict_new_presized, METH_VARARGS,
 	 "construct a dict with an expected size\n"},
 	{"make_file_foldmap", make_file_foldmap, METH_VARARGS,
 	 "make file foldmap\n"},
 	{"jsonescapeu8fast", jsonescapeu8fast, METH_VARARGS,
 	 "escape a UTF-8 byte string to JSON (fast path)\n"},
 	{"encodedir", encodedir, METH_VARARGS, "encodedir a path\n"},
 	{"pathencode", pathencode, METH_VARARGS, "fncache-encode a path\n"},
 	{"lowerencode", lowerencode, METH_VARARGS, "lower-encode a path\n"},
 	{"fm1readmarkers", fm1readmarkers, METH_VARARGS,
 			"parse v1 obsolete markers\n"},
 	{NULL, NULL}
 };
 
 void dirs_module_init(PyObject *mod);
 void manifest_module_init(PyObject *mod);
 void revlog_module_init(PyObject *mod);
 
 static const int version = 3;
 
 static void module_init(PyObject *mod)
 {
 	PyModule_AddIntConstant(mod, "version", version);
 
 	/* This module constant has two purposes.  First, it lets us unit test
 	 * the ImportError raised without hard-coding any error text.  This
 	 * means we can change the text in the future without breaking tests,
 	 * even across changesets without a recompile.  Second, its presence
 	 * can be used to determine whether the version-checking logic is
 	 * present, which also helps in testing across changesets without a
 	 * recompile.  Note that this means the pure-Python version of parsers
 	 * should not have this module constant. */
 	PyModule_AddStringConstant(mod, "versionerrortext", versionerrortext);
 
 	dirs_module_init(mod);
 	manifest_module_init(mod);
 	revlog_module_init(mod);
 
 	if (PyType_Ready(&dirstateTupleType) < 0)
 		return;
 	Py_INCREF(&dirstateTupleType);
 	PyModule_AddObject(mod, "dirstatetuple",
 			   (PyObject *)&dirstateTupleType);
 }
 
 static int check_python_version(void)
 {
 	PyObject *sys = PyImport_ImportModule("sys"), *ver;
 	long hexversion;
 	if (!sys)
 		return -1;
 	ver = PyObject_GetAttrString(sys, "hexversion");
 	Py_DECREF(sys);
 	if (!ver)
 		return -1;
 	hexversion = PyInt_AsLong(ver);
 	Py_DECREF(ver);
 	/* sys.hexversion is a 32-bit number by default, so the -1 case
 	 * should only occur in unusual circumstances (e.g. if sys.hexversion
 	 * is manually set to an invalid value). */
 	if ((hexversion == -1) || (hexversion >> 16 != PY_VERSION_HEX >> 16)) {
 		PyErr_Format(PyExc_ImportError, "%s: The Mercurial extension "
 			"modules were compiled with Python " PY_VERSION ", but "
 			"Mercurial is currently using Python with sys.hexversion=%ld: "
 			"Python %s\n at: %s", versionerrortext, hexversion,
 			Py_GetVersion(), Py_GetProgramFullPath());
 		return -1;
 	}
 	return 0;
 }
 
 #ifdef IS_PY3K
 static struct PyModuleDef parsers_module = {
 	PyModuleDef_HEAD_INIT,
 	"parsers",
 	parsers_doc,
 	-1,
 	methods
 };
 
 PyMODINIT_FUNC PyInit_parsers(void)
 {
 	PyObject *mod;
 
 	if (check_python_version() == -1)
 		return NULL;
 	mod = PyModule_Create(&parsers_module);
 	module_init(mod);
 	return mod;
 }
 #else
 PyMODINIT_FUNC initparsers(void)
 {
 	PyObject *mod;
 
 	if (check_python_version() == -1)
 		return;
 	mod = Py_InitModule3("parsers", methods, parsers_doc);
 	module_init(mod);
 }
 #endif

mercurial/cext/revlog.c

@@ -1,2089 +1,2089 b''
 /*
  parsers.c - efficient content parsing
 
  Copyright 2008 Matt Mackall <[e-mail]> and others
 
  This software may be used and distributed according to the terms of
  the GNU General Public License, incorporated herein by reference.
 */
 
 #include <Python.h>
 #include <assert.h>
 #include <ctype.h>
 #include <stddef.h>
 #include <string.h>
 
+#include "bitmanipulation.h"
 #include "charencode.h"
 #include "util.h"
-#include "bitmanipulation.h"
 
 #ifdef IS_PY3K
 /* The mapping of Python types is meant to be temporary to get Python
  * 3 to compile. We should remove this once Python 3 support is fully
  * supported and proper types are used in the extensions themselves. */
 #define PyInt_Check PyLong_Check
 #define PyInt_FromLong PyLong_FromLong
 #define PyInt_FromSsize_t PyLong_FromSsize_t
 #define PyInt_AS_LONG PyLong_AS_LONG
 #define PyInt_AsLong PyLong_AsLong
 #endif
 
 /*
  * A base-16 trie for fast node->rev mapping.
  *
  * Positive value is index of the next node in the trie
  * Negative value is a leaf: -(rev + 1)
  * Zero is empty
  */
 typedef struct {
 	int children[16];
 } nodetree;
 
 /*
  * This class has two behaviors.
  *
  * When used in a list-like way (with integer keys), we decode an
  * entry in a RevlogNG index file on demand. Our last entry is a
  * sentinel, always a nullid.  We have limited support for
  * integer-keyed insert and delete, only at elements right before the
  * sentinel.
  *
  * With string keys, we lazily perform a reverse mapping from node to
  * rev, using a base-16 trie.
  */
 typedef struct {
 	PyObject_HEAD
 	/* Type-specific fields go here. */
 	PyObject *data;        /* raw bytes of index */
 	Py_buffer buf;         /* buffer of data */
 	PyObject **cache;      /* cached tuples */
 	const char **offsets;  /* populated on demand */
 	Py_ssize_t raw_length; /* original number of elements */
 	Py_ssize_t length;     /* current number of elements */
 	PyObject *added;       /* populated on demand */
 	PyObject *headrevs;    /* cache, invalidated on changes */
 	PyObject *filteredrevs;/* filtered revs set */
 	nodetree *nt;          /* base-16 trie */
 	unsigned ntlength;          /* # nodes in use */
 	unsigned ntcapacity;        /* # nodes allocated */
 	int ntdepth;           /* maximum depth of tree */
 	int ntsplits;          /* # splits performed */
 	int ntrev;             /* last rev scanned */
 	int ntlookups;         /* # lookups */
 	int ntmisses;          /* # lookups that miss the cache */
 	int inlined;
 } indexObject;
 
 static Py_ssize_t index_length(const indexObject *self)
 {
 	if (self->added == NULL)
 		return self->length;
 	return self->length + PyList_GET_SIZE(self->added);
 }
 
 static PyObject *nullentry;
 static const char nullid[20];
 
 static Py_ssize_t inline_scan(indexObject *self, const char **offsets);
 
 #if LONG_MAX == 0x7fffffffL
 static char *tuple_format = "Kiiiiiis#";
 #else
 static char *tuple_format = "kiiiiiis#";
 #endif
 
 /* A RevlogNG v1 index entry is 64 bytes long. */
 static const long v1_hdrsize = 64;
 
 /*
  * Return a pointer to the beginning of a RevlogNG record.
  */
 static const char *index_deref(indexObject *self, Py_ssize_t pos)
 {
 	if (self->inlined && pos > 0) {
 		if (self->offsets == NULL) {
 			self->offsets = PyMem_Malloc(self->raw_length *
 					             sizeof(*self->offsets));
 			if (self->offsets == NULL)
 				return (const char *)PyErr_NoMemory();
 			inline_scan(self, self->offsets);
 		}
 		return self->offsets[pos];
 	}
 
 	return (const char *)(self->buf.buf) + pos * v1_hdrsize;
 }
 
 static inline int index_get_parents(indexObject *self, Py_ssize_t rev,
 				    int *ps, int maxrev)
 {
 	if (rev >= self->length - 1) {
 		PyObject *tuple = PyList_GET_ITEM(self->added,
 						  rev - self->length + 1);
 		ps[0] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 5));
 		ps[1] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 6));
 	} else {
 		const char *data = index_deref(self, rev);
 		ps[0] = getbe32(data + 24);
 		ps[1] = getbe32(data + 28);
 	}
 	/* If index file is corrupted, ps[] may point to invalid revisions. So
 	 * there is a risk of buffer overflow to trust them unconditionally. */
 	if (ps[0] > maxrev || ps[1] > maxrev) {
 		PyErr_SetString(PyExc_ValueError, "parent out of range");
 		return -1;
 	}
 	return 0;
 }
 
 
 /*
  * RevlogNG format (all in big endian, data may be inlined):
  *    6 bytes: offset
  *    2 bytes: flags
  *    4 bytes: compressed length
  *    4 bytes: uncompressed length
  *    4 bytes: base revision
  *    4 bytes: link revision
  *    4 bytes: parent 1 revision
  *    4 bytes: parent 2 revision
  *   32 bytes: nodeid (only 20 bytes used)
  */
 static PyObject *index_get(indexObject *self, Py_ssize_t pos)
 {
 	uint64_t offset_flags;
 	int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;
 	const char *c_node_id;
 	const char *data;
 	Py_ssize_t length = index_length(self);
 	PyObject *entry;
 
 	if (pos < 0)
 		pos += length;
 
 	if (pos < 0 || pos >= length) {
 		PyErr_SetString(PyExc_IndexError, "revlog index out of range");
 		return NULL;
 	}
 
 	if (pos == length - 1) {
 		Py_INCREF(nullentry);
 		return nullentry;
 	}
 
 	if (pos >= self->length - 1) {
 		PyObject *obj;
 		obj = PyList_GET_ITEM(self->added, pos - self->length + 1);
 		Py_INCREF(obj);
 		return obj;
 	}
 
 	if (self->cache) {
 		if (self->cache[pos]) {
 			Py_INCREF(self->cache[pos]);
 			return self->cache[pos];
 		}
 	} else {
 		self->cache = calloc(self->raw_length, sizeof(PyObject *));
 		if (self->cache == NULL)
 			return PyErr_NoMemory();
 	}
 
 	data = index_deref(self, pos);
 	if (data == NULL)
 		return NULL;
 
 	offset_flags = getbe32(data + 4);
 	if (pos == 0) /* mask out version number for the first entry */
 		offset_flags &= 0xFFFF;
 	else {
 		uint32_t offset_high = getbe32(data);
 		offset_flags |= ((uint64_t)offset_high) << 32;
 	}
 
 	comp_len = getbe32(data + 8);
 	uncomp_len = getbe32(data + 12);
 	base_rev = getbe32(data + 16);
 	link_rev = getbe32(data + 20);
 	parent_1 = getbe32(data + 24);
 	parent_2 = getbe32(data + 28);
 	c_node_id = data + 32;
 
 	entry = Py_BuildValue(tuple_format, offset_flags, comp_len,
 			      uncomp_len, base_rev, link_rev,
 			      parent_1, parent_2, c_node_id, 20);
 
 	if (entry) {
 		PyObject_GC_UnTrack(entry);
 		Py_INCREF(entry);
 	}
 
 	self->cache[pos] = entry;
 
 	return entry;
 }
 
 /*
  * Return the 20-byte SHA of the node corresponding to the given rev.
  */
 static const char *index_node(indexObject *self, Py_ssize_t pos)
 {
 	Py_ssize_t length = index_length(self);
 	const char *data;
 
 	if (pos == length - 1 || pos == INT_MAX)
 		return nullid;
 
 	if (pos >= length)
 		return NULL;
 
 	if (pos >= self->length - 1) {
 		PyObject *tuple, *str;
 		tuple = PyList_GET_ITEM(self->added, pos - self->length + 1);
 		str = PyTuple_GetItem(tuple, 7);
 		return str ? PyBytes_AS_STRING(str) : NULL;
 	}
 
 	data = index_deref(self, pos);
 	return data ? data + 32 : NULL;
 }
 
 static int nt_insert(indexObject *self, const char *node, int rev);
 
 static int node_check(PyObject *obj, char **node, Py_ssize_t *nodelen)
 {
 	if (PyBytes_AsStringAndSize(obj, node, nodelen) == -1)
 		return -1;
 	if (*nodelen == 20)
 		return 0;
 	PyErr_SetString(PyExc_ValueError, "20-byte hash required");
 	return -1;
 }
 
 static PyObject *index_insert(indexObject *self, PyObject *args)
 {
 	PyObject *obj;
 	char *node;
 	int index;
 	Py_ssize_t len, nodelen;
 
 	if (!PyArg_ParseTuple(args, "iO", &index, &obj))
 		return NULL;
 
 	if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) {
 		PyErr_SetString(PyExc_TypeError, "8-tuple required");
 		return NULL;
 	}
 
 	if (node_check(PyTuple_GET_ITEM(obj, 7), &node, &nodelen) == -1)
 		return NULL;
 
 	len = index_length(self);
 
 	if (index < 0)
 		index += len;
 
 	if (index != len - 1) {
 		PyErr_SetString(PyExc_IndexError,
 				"insert only supported at index -1");
 		return NULL;
 	}
 
 	if (self->added == NULL) {
 		self->added = PyList_New(0);
 		if (self->added == NULL)
 			return NULL;
 	}
 
 	if (PyList_Append(self->added, obj) == -1)
 		return NULL;
 
 	if (self->nt)
 		nt_insert(self, node, index);
 
 	Py_CLEAR(self->headrevs);
 	Py_RETURN_NONE;
 }
 
 static void _index_clearcaches(indexObject *self)
 {
 	if (self->cache) {
 		Py_ssize_t i;
 
 		for (i = 0; i < self->raw_length; i++)
 			Py_CLEAR(self->cache[i]);
 		free(self->cache);
 		self->cache = NULL;
 	}
 	if (self->offsets) {
 		PyMem_Free(self->offsets);
 		self->offsets = NULL;
 	}
 	if (self->nt) {
 		free(self->nt);
 		self->nt = NULL;
 	}
 	Py_CLEAR(self->headrevs);
 }
 
 static PyObject *index_clearcaches(indexObject *self)
 {
 	_index_clearcaches(self);
 	self->ntlength = self->ntcapacity = 0;
 	self->ntdepth = self->ntsplits = 0;
 	self->ntrev = -1;
 	self->ntlookups = self->ntmisses = 0;
 	Py_RETURN_NONE;
 }
 
 static PyObject *index_stats(indexObject *self)
 {
 	PyObject *obj = PyDict_New();
 	PyObject *t = NULL;
 
 	if (obj == NULL)
 		return NULL;
 
 #define istat(__n, __d) \
 	do { \
 		t = PyInt_FromSsize_t(self->__n); \
 		if (!t) \
 			goto bail; \
 		if (PyDict_SetItemString(obj, __d, t) == -1) \
 			goto bail; \
 		Py_DECREF(t); \
 	} while (0)
 
 	if (self->added) {
 		Py_ssize_t len = PyList_GET_SIZE(self->added);
 		t = PyInt_FromSsize_t(len);
 		if (!t)
 			goto bail;
 		if (PyDict_SetItemString(obj, "index entries added", t) == -1)
 			goto bail;
 		Py_DECREF(t);
 	}
 
 	if (self->raw_length != self->length - 1)
 		istat(raw_length, "revs on disk");
 	istat(length, "revs in memory");
 	istat(ntcapacity, "node trie capacity");
 	istat(ntdepth, "node trie depth");
 	istat(ntlength, "node trie count");
 	istat(ntlookups, "node trie lookups");
 	istat(ntmisses, "node trie misses");
 	istat(ntrev, "node trie last rev scanned");
 	istat(ntsplits, "node trie splits");
 
 #undef istat
 
 	return obj;
 
 bail:
 	Py_XDECREF(obj);
 	Py_XDECREF(t);
 	return NULL;
 }
 
 /*
  * When we cache a list, we want to be sure the caller can't mutate
  * the cached copy.
  */
 static PyObject *list_copy(PyObject *list)
 {
 	Py_ssize_t len = PyList_GET_SIZE(list);
 	PyObject *newlist = PyList_New(len);
 	Py_ssize_t i;
 
 	if (newlist == NULL)
 		return NULL;
 
 	for (i = 0; i < len; i++) {
 		PyObject *obj = PyList_GET_ITEM(list, i);
 		Py_INCREF(obj);
 		PyList_SET_ITEM(newlist, i, obj);
 	}
 
 	return newlist;
 }
 
 static int check_filter(PyObject *filter, Py_ssize_t arg) {
 	if (filter) {
 		PyObject *arglist, *result;
 		int isfiltered;
 
 		arglist = Py_BuildValue("(n)", arg);
 		if (!arglist) {
 			return -1;
 		}
 
 		result = PyEval_CallObject(filter, arglist);
 		Py_DECREF(arglist);
 		if (!result) {
 			return -1;
 		}
 
 		/* PyObject_IsTrue returns 1 if true, 0 if false, -1 if error,
 		 * same as this function, so we can just return it directly.*/
 		isfiltered = PyObject_IsTrue(result);
 		Py_DECREF(result);
 		return isfiltered;
 	} else {
 		return 0;
 	}
 }
 
 static Py_ssize_t add_roots_get_min(indexObject *self, PyObject *list,
                                     Py_ssize_t marker, char *phases)
 {
 	PyObject *iter = NULL;
 	PyObject *iter_item = NULL;
 	Py_ssize_t min_idx = index_length(self) + 1;
 	long iter_item_long;
 
 	if (PyList_GET_SIZE(list) != 0) {
 		iter = PyObject_GetIter(list);
 		if (iter == NULL)
 			return -2;
 		while ((iter_item = PyIter_Next(iter))) {
 			iter_item_long = PyInt_AS_LONG(iter_item);
 			Py_DECREF(iter_item);
 			if (iter_item_long < min_idx)
 				min_idx = iter_item_long;
 			phases[iter_item_long] = marker;
 		}
 		Py_DECREF(iter);
 	}
 
 	return min_idx;
 }
 
 static inline void set_phase_from_parents(char *phases, int parent_1,
                                           int parent_2, Py_ssize_t i)
 {
 	if (parent_1 >= 0 && phases[parent_1] > phases[i])
 		phases[i] = phases[parent_1];
 	if (parent_2 >= 0 && phases[parent_2] > phases[i])
 		phases[i] = phases[parent_2];
 }
 
 static PyObject *reachableroots2(indexObject *self, PyObject *args)
 {
 
 	/* Input */
 	long minroot;
 	PyObject *includepatharg = NULL;
 	int includepath = 0;
 	/* heads and roots are lists */
 	PyObject *heads = NULL;
 	PyObject *roots = NULL;
 	PyObject *reachable = NULL;
 
 	PyObject *val;
 	Py_ssize_t len = index_length(self) - 1;
 	long revnum;
 	Py_ssize_t k;
 	Py_ssize_t i;
 	Py_ssize_t l;
 	int r;
 	int parents[2];
 
 	/* Internal data structure:
 	 * tovisit: array of length len+1 (all revs + nullrev), filled upto lentovisit
 	 * revstates: array of length len+1 (all revs + nullrev) */
 	int *tovisit = NULL;
 	long lentovisit = 0;
 	enum { RS_SEEN = 1, RS_ROOT = 2, RS_REACHABLE = 4 };
 	char *revstates = NULL;
 
 	/* Get arguments */
 	if (!PyArg_ParseTuple(args, "lO!O!O!", &minroot, &PyList_Type, &heads,
 			      &PyList_Type, &roots,
 			      &PyBool_Type, &includepatharg))
 		goto bail;
 
 	if (includepatharg == Py_True)
 		includepath = 1;
 
 	/* Initialize return set */
 	reachable = PyList_New(0);
 	if (reachable == NULL)
 		goto bail;
 
 	/* Initialize internal datastructures */
 	tovisit = (int *)malloc((len + 1) * sizeof(int));
 	if (tovisit == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	revstates = (char *)calloc(len + 1, 1);
 	if (revstates == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	l = PyList_GET_SIZE(roots);
 	for (i = 0; i < l; i++) {
 		revnum = PyInt_AsLong(PyList_GET_ITEM(roots, i));
 		if (revnum == -1 && PyErr_Occurred())
 			goto bail;
 		/* If root is out of range, e.g. wdir(), it must be unreachable
 		 * from heads. So we can just ignore it. */
 		if (revnum + 1 < 0 || revnum + 1 >= len + 1)
 			continue;
 		revstates[revnum + 1] |= RS_ROOT;
 	}
 
 	/* Populate tovisit with all the heads */
 	l = PyList_GET_SIZE(heads);
 	for (i = 0; i < l; i++) {
 		revnum = PyInt_AsLong(PyList_GET_ITEM(heads, i));
 		if (revnum == -1 && PyErr_Occurred())
 			goto bail;
 		if (revnum + 1 < 0 || revnum + 1 >= len + 1) {
 			PyErr_SetString(PyExc_IndexError, "head out of range");
 			goto bail;
 		}
 		if (!(revstates[revnum + 1] & RS_SEEN)) {
 			tovisit[lentovisit++] = (int)revnum;
 			revstates[revnum + 1] |= RS_SEEN;
 		}
 	}
 
 	/* Visit the tovisit list and find the reachable roots */
 	k = 0;
 	while (k < lentovisit) {
 		/* Add the node to reachable if it is a root*/
 		revnum = tovisit[k++];
 		if (revstates[revnum + 1] & RS_ROOT) {
 			revstates[revnum + 1] |= RS_REACHABLE;
 			val = PyInt_FromLong(revnum);
 			if (val == NULL)
 				goto bail;
 			r = PyList_Append(reachable, val);
 			Py_DECREF(val);
 			if (r < 0)
 				goto bail;
 			if (includepath == 0)
 				continue;
 		}
 
 		/* Add its parents to the list of nodes to visit */
 		if (revnum == -1)
 			continue;
 		r = index_get_parents(self, revnum, parents, (int)len - 1);
 		if (r < 0)
 			goto bail;
 		for (i = 0; i < 2; i++) {
 			if (!(revstates[parents[i] + 1] & RS_SEEN)
 			    && parents[i] >= minroot) {
 				tovisit[lentovisit++] = parents[i];
 				revstates[parents[i] + 1] |= RS_SEEN;
 			}
 		}
 	}
 
 	/* Find all the nodes in between the roots we found and the heads
 	 * and add them to the reachable set */
 	if (includepath == 1) {
 		long minidx = minroot;
 		if (minidx < 0)
 			minidx = 0;
 		for (i = minidx; i < len; i++) {
 			if (!(revstates[i + 1] & RS_SEEN))
 				continue;
 			r = index_get_parents(self, i, parents, (int)len - 1);
 			/* Corrupted index file, error is set from
 			 * index_get_parents */
 			if (r < 0)
 				goto bail;
 			if (((revstates[parents[0] + 1] |
 			      revstates[parents[1] + 1]) & RS_REACHABLE)
 			    && !(revstates[i + 1] & RS_REACHABLE)) {
 				revstates[i + 1] |= RS_REACHABLE;
 				val = PyInt_FromLong(i);
 				if (val == NULL)
 					goto bail;
 				r = PyList_Append(reachable, val);
 				Py_DECREF(val);
 				if (r < 0)
 					goto bail;
 			}
 		}
 	}
 
 	free(revstates);
 	free(tovisit);
 	return reachable;
 bail:
 	Py_XDECREF(reachable);
 	free(revstates);
 	free(tovisit);
 	return NULL;
 }
 
 static PyObject *compute_phases_map_sets(indexObject *self, PyObject *args)
 {
 	PyObject *roots = Py_None;
 	PyObject *ret = NULL;
 	PyObject *phaseslist = NULL;
 	PyObject *phaseroots = NULL;
 	PyObject *phaseset = NULL;
 	PyObject *phasessetlist = NULL;
 	PyObject *rev = NULL;
 	Py_ssize_t len = index_length(self) - 1;
 	Py_ssize_t numphase = 0;
 	Py_ssize_t minrevallphases = 0;
 	Py_ssize_t minrevphase = 0;
 	Py_ssize_t i = 0;
 	char *phases = NULL;
 	long phase;
 
 	if (!PyArg_ParseTuple(args, "O", &roots))
 		goto done;
 	if (roots == NULL || !PyList_Check(roots))
 		goto done;
 
 	phases = calloc(len, 1); /* phase per rev: {0: public, 1: draft, 2: secret} */
 	if (phases == NULL) {
 		PyErr_NoMemory();
 		goto done;
 	}
 	/* Put the phase information of all the roots in phases */
 	numphase = PyList_GET_SIZE(roots)+1;
 	minrevallphases = len + 1;
 	phasessetlist = PyList_New(numphase);
 	if (phasessetlist == NULL)
 		goto done;
 
 	PyList_SET_ITEM(phasessetlist, 0, Py_None);
 	Py_INCREF(Py_None);
 
 	for (i = 0; i < numphase-1; i++) {
 		phaseroots = PyList_GET_ITEM(roots, i);
 		phaseset = PySet_New(NULL);
 		if (phaseset == NULL)
 			goto release;
 		PyList_SET_ITEM(phasessetlist, i+1, phaseset);
 		if (!PyList_Check(phaseroots))
 			goto release;
 		minrevphase = add_roots_get_min(self, phaseroots, i+1, phases);
 		if (minrevphase == -2) /* Error from add_roots_get_min */
 			goto release;
 		minrevallphases = MIN(minrevallphases, minrevphase);
 	}
 	/* Propagate the phase information from the roots to the revs */
 	if (minrevallphases != -1) {
 		int parents[2];
 		for (i = minrevallphases; i < len; i++) {
 			if (index_get_parents(self, i, parents,
 					      (int)len - 1) < 0)
 				goto release;
 			set_phase_from_parents(phases, parents[0], parents[1], i);
 		}
 	}
 	/* Transform phase list to a python list */
 	phaseslist = PyList_New(len);
 	if (phaseslist == NULL)
 		goto release;
 	for (i = 0; i < len; i++) {
 		PyObject *phaseval;
 
 		phase = phases[i];
 		/* We only store the sets of phase for non public phase, the public phase
 		 * is computed as a difference */
 		if (phase != 0) {
 			phaseset = PyList_GET_ITEM(phasessetlist, phase);
 			rev = PyInt_FromLong(i);
 			if (rev == NULL)
 				goto release;
 			PySet_Add(phaseset, rev);
 			Py_XDECREF(rev);
 		}
 		phaseval = PyInt_FromLong(phase);
 		if (phaseval == NULL)
 			goto release;
 		PyList_SET_ITEM(phaseslist, i, phaseval);
 	}
 	ret = PyTuple_Pack(2, phaseslist, phasessetlist);
 
 release:
 	Py_XDECREF(phaseslist);
 	Py_XDECREF(phasessetlist);
 done:
 	free(phases);
 	return ret;
 }
 
 static PyObject *index_headrevs(indexObject *self, PyObject *args)
 {
 	Py_ssize_t i, j, len;
 	char *nothead = NULL;
 	PyObject *heads = NULL;
 	PyObject *filter = NULL;
 	PyObject *filteredrevs = Py_None;
 
 	if (!PyArg_ParseTuple(args, "|O", &filteredrevs)) {
 		return NULL;
 	}
 
 	if (self->headrevs && filteredrevs == self->filteredrevs)
 		return list_copy(self->headrevs);
 
 	Py_DECREF(self->filteredrevs);
 	self->filteredrevs = filteredrevs;
 	Py_INCREF(filteredrevs);
 
 	if (filteredrevs != Py_None) {
 		filter = PyObject_GetAttrString(filteredrevs, "__contains__");
 		if (!filter) {
 			PyErr_SetString(PyExc_TypeError,
 				"filteredrevs has no attribute __contains__");
 			goto bail;
 		}
 	}
 
 	len = index_length(self) - 1;
 	heads = PyList_New(0);
 	if (heads == NULL)
 		goto bail;
 	if (len == 0) {
 		PyObject *nullid = PyInt_FromLong(-1);
 		if (nullid == NULL || PyList_Append(heads, nullid) == -1) {
 			Py_XDECREF(nullid);
 			goto bail;
 		}
 		goto done;
 	}
 
 	nothead = calloc(len, 1);
 	if (nothead == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	for (i = len - 1; i >= 0; i--) {
 		int isfiltered;
 		int parents[2];
 
 		/* If nothead[i] == 1, it means we've seen an unfiltered child of this
 		 * node already, and therefore this node is not filtered. So we can skip
 		 * the expensive check_filter step.
 		 */
 		if (nothead[i] != 1) {
 			isfiltered = check_filter(filter, i);
 			if (isfiltered == -1) {
 				PyErr_SetString(PyExc_TypeError,
 					"unable to check filter");
 				goto bail;
 			}
 
 			if (isfiltered) {
 				nothead[i] = 1;
 				continue;
 			}
 		}
 
 		if (index_get_parents(self, i, parents, (int)len - 1) < 0)
 			goto bail;
 		for (j = 0; j < 2; j++) {
 			if (parents[j] >= 0)
 				nothead[parents[j]] = 1;
 		}
 	}
 
 	for (i = 0; i < len; i++) {
 		PyObject *head;
 
 		if (nothead[i])
 			continue;
 		head = PyInt_FromSsize_t(i);
 		if (head == NULL || PyList_Append(heads, head) == -1) {
 			Py_XDECREF(head);
 			goto bail;
 		}
 	}
 
 done:
 	self->headrevs = heads;
 	Py_XDECREF(filter);
 	free(nothead);
 	return list_copy(self->headrevs);
 bail:
 	Py_XDECREF(filter);
 	Py_XDECREF(heads);
 	free(nothead);
 	return NULL;
 }
 
 /**
  * Obtain the base revision index entry.
  *
  * Callers must ensure that rev >= 0 or illegal memory access may occur.
  */
 static inline int index_baserev(indexObject *self, int rev)
 {
 	const char *data;
 
 	if (rev >= self->length - 1) {
 		PyObject *tuple = PyList_GET_ITEM(self->added,
 			rev - self->length + 1);
 		return (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 3));
 	}
 	else {
 		data = index_deref(self, rev);
 		if (data == NULL) {
 			return -2;
 		}
 
 		return getbe32(data + 16);
 	}
 }
 
 static PyObject *index_deltachain(indexObject *self, PyObject *args)
 {
 	int rev, generaldelta;
 	PyObject *stoparg;
 	int stoprev, iterrev, baserev = -1;
 	int stopped;
 	PyObject *chain = NULL, *result = NULL;
 	const Py_ssize_t length = index_length(self);
 
 	if (!PyArg_ParseTuple(args, "iOi", &rev, &stoparg, &generaldelta)) {
 		return NULL;
 	}
 
 	if (PyInt_Check(stoparg)) {
 		stoprev = (int)PyInt_AsLong(stoparg);
 		if (stoprev == -1 && PyErr_Occurred()) {
 			return NULL;
 		}
 	}
 	else if (stoparg == Py_None) {
 		stoprev = -2;
 	}
 	else {
 		PyErr_SetString(PyExc_ValueError,
 			"stoprev must be integer or None");
 		return NULL;
 	}
 
 	if (rev < 0 || rev >= length - 1) {
 		PyErr_SetString(PyExc_ValueError, "revlog index out of range");
 		return NULL;
 	}
 
 	chain = PyList_New(0);
 	if (chain == NULL) {
 		return NULL;
 	}
 
 	baserev = index_baserev(self, rev);
 
 	/* This should never happen. */
 	if (baserev <= -2) {
 		/* Error should be set by index_deref() */
 		assert(PyErr_Occurred());
 		goto bail;
 	}
 
 	iterrev = rev;
 
 	while (iterrev != baserev && iterrev != stoprev) {
 		PyObject *value = PyInt_FromLong(iterrev);
 		if (value == NULL) {
 			goto bail;
 		}
 		if (PyList_Append(chain, value)) {
 			Py_DECREF(value);
 			goto bail;
 		}
 		Py_DECREF(value);
 
 		if (generaldelta) {
 			iterrev = baserev;
 		}
 		else {
 			iterrev--;
 		}
 
 		if (iterrev < 0) {
 			break;
 		}
 
 		if (iterrev >= length - 1) {
 			PyErr_SetString(PyExc_IndexError, "revision outside index");
 			return NULL;
 		}
 
 		baserev = index_baserev(self, iterrev);
 
 		/* This should never happen. */
 		if (baserev <= -2) {
 			/* Error should be set by index_deref() */
 			assert(PyErr_Occurred());
 			goto bail;
 		}
 	}
 
 	if (iterrev == stoprev) {
 		stopped = 1;
 	}
 	else {
 		PyObject *value = PyInt_FromLong(iterrev);
 		if (value == NULL) {
 			goto bail;
 		}
 		if (PyList_Append(chain, value)) {
 			Py_DECREF(value);
 			goto bail;
 		}
 		Py_DECREF(value);
 
 		stopped = 0;
 	}
 
 	if (PyList_Reverse(chain)) {
 		goto bail;
 	}
 
 	result = Py_BuildValue("OO", chain, stopped ? Py_True : Py_False);
 	Py_DECREF(chain);
 	return result;
 
 bail:
 	Py_DECREF(chain);
 	return NULL;
 }
 
 static inline int nt_level(const char *node, Py_ssize_t level)
 {
 	int v = node[level>>1];
 	if (!(level & 1))
 		v >>= 4;
 	return v & 0xf;
 }
 
 /*
  * Return values:
  *
  *   -4: match is ambiguous (multiple candidates)
  *   -2: not found
  * rest: valid rev
  */
 static int nt_find(indexObject *self, const char *node, Py_ssize_t nodelen,
 		   int hex)
 {
 	int (*getnybble)(const char *, Py_ssize_t) = hex ? hexdigit : nt_level;
 	int level, maxlevel, off;
 
 	if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0)
 		return -1;
 
 	if (self->nt == NULL)
 		return -2;
 
 	if (hex)
 		maxlevel = nodelen > 40 ? 40 : (int)nodelen;
 	else
 		maxlevel = nodelen > 20 ? 40 : ((int)nodelen * 2);
 
 	for (level = off = 0; level < maxlevel; level++) {
 		int k = getnybble(node, level);
 		nodetree *n = &self->nt[off];
 		int v = n->children[k];
 
 		if (v < 0) {
 			const char *n;
 			Py_ssize_t i;
 
 			v = -(v + 1);
 			n = index_node(self, v);
 			if (n == NULL)
 				return -2;
 			for (i = level; i < maxlevel; i++)
 				if (getnybble(node, i) != nt_level(n, i))
 					return -2;
 			return v;
 		}
 		if (v == 0)
 			return -2;
 		off = v;
 	}
 	/* multiple matches against an ambiguous prefix */
 	return -4;
 }
 
 static int nt_new(indexObject *self)
 {
 	if (self->ntlength == self->ntcapacity) {
 		if (self->ntcapacity >= INT_MAX / (sizeof(nodetree) * 2)) {
 			PyErr_SetString(PyExc_MemoryError,
 					"overflow in nt_new");
 			return -1;
 		}
 		self->ntcapacity *= 2;
 		self->nt = realloc(self->nt,
 				   self->ntcapacity * sizeof(nodetree));
 		if (self->nt == NULL) {
 			PyErr_SetString(PyExc_MemoryError, "out of memory");
 			return -1;
 		}
 		memset(&self->nt[self->ntlength], 0,
 		       sizeof(nodetree) * (self->ntcapacity - self->ntlength));
 	}
 	return self->ntlength++;
 }
 
 static int nt_insert(indexObject *self, const char *node, int rev)
 {
 	int level = 0;
 	int off = 0;
 
 	while (level < 40) {
 		int k = nt_level(node, level);
 		nodetree *n;
 		int v;
 
 		n = &self->nt[off];
 		v = n->children[k];
 
 		if (v == 0) {
 			n->children[k] = -rev - 1;
 			return 0;
 		}
 		if (v < 0) {
 			const char *oldnode = index_node(self, -(v + 1));
 			int noff;
 
 			if (!oldnode || !memcmp(oldnode, node, 20)) {
 				n->children[k] = -rev - 1;
 				return 0;
 			}
 			noff = nt_new(self);
 			if (noff == -1)
 				return -1;
 			/* self->nt may have been changed by realloc */
 			self->nt[off].children[k] = noff;
 			off = noff;
 			n = &self->nt[off];
 			n->children[nt_level(oldnode, ++level)] = v;
 			if (level > self->ntdepth)
 				self->ntdepth = level;
 			self->ntsplits += 1;
 		} else {
 			level += 1;
 			off = v;
 		}
 	}
 
 	return -1;
 }
 
 static int nt_init(indexObject *self)
 {
 	if (self->nt == NULL) {
 		if ((size_t)self->raw_length > INT_MAX / sizeof(nodetree)) {
 			PyErr_SetString(PyExc_ValueError, "overflow in nt_init");
 			return -1;
 		}
 		self->ntcapacity = self->raw_length < 4
 			? 4 : (int)self->raw_length / 2;
 
 		self->nt = calloc(self->ntcapacity, sizeof(nodetree));
 		if (self->nt == NULL) {
 			PyErr_NoMemory();
 			return -1;
 		}
 		self->ntlength = 1;
 		self->ntrev = (int)index_length(self) - 1;
 		self->ntlookups = 1;
 		self->ntmisses = 0;
 		if (nt_insert(self, nullid, INT_MAX) == -1)
 			return -1;
 	}
 	return 0;
 }
 
 /*
  * Return values:
  *
  *   -3: error (exception set)
  *   -2: not found (no exception set)
  * rest: valid rev
  */
 static int index_find_node(indexObject *self,
 			   const char *node, Py_ssize_t nodelen)
 {
 	int rev;
 
 	self->ntlookups++;
 	rev = nt_find(self, node, nodelen, 0);
 	if (rev >= -1)
 		return rev;
 
 	if (nt_init(self) == -1)
 		return -3;
 
 	/*
 	 * For the first handful of lookups, we scan the entire index,
 	 * and cache only the matching nodes. This optimizes for cases
 	 * like "hg tip", where only a few nodes are accessed.
 	 *
 	 * After that, we cache every node we visit, using a single
 	 * scan amortized over multiple lookups.  This gives the best
 	 * bulk performance, e.g. for "hg log".
 	 */
 	if (self->ntmisses++ < 4) {
 		for (rev = self->ntrev - 1; rev >= 0; rev--) {
 			const char *n = index_node(self, rev);
 			if (n == NULL)
 				return -2;
 			if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
 				if (nt_insert(self, n, rev) == -1)
 					return -3;
 				break;
 			}
 		}
 	} else {
 		for (rev = self->ntrev - 1; rev >= 0; rev--) {
 			const char *n = index_node(self, rev);
 			if (n == NULL) {
 				self->ntrev = rev + 1;
 				return -2;
 			}
 			if (nt_insert(self, n, rev) == -1) {
 				self->ntrev = rev + 1;
 				return -3;
 			}
 			if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
 				break;
 			}
 		}
 		self->ntrev = rev;
 	}
 
 	if (rev >= 0)
 		return rev;
 	return -2;
 }
 
 static void raise_revlog_error(void)
 {
 	PyObject *mod = NULL, *dict = NULL, *errclass = NULL;
 
 	mod = PyImport_ImportModule("mercurial.error");
 	if (mod == NULL) {
 		goto cleanup;
 	}
 
 	dict = PyModule_GetDict(mod);
 	if (dict == NULL) {
 		goto cleanup;
 	}
 	Py_INCREF(dict);
 
 	errclass = PyDict_GetItemString(dict, "RevlogError");
 	if (errclass == NULL) {
 		PyErr_SetString(PyExc_SystemError,
 				"could not find RevlogError");
 		goto cleanup;
 	}
 
 	/* value of exception is ignored by callers */
 	PyErr_SetString(errclass, "RevlogError");
 
 cleanup:
 	Py_XDECREF(dict);
 	Py_XDECREF(mod);
 }
 
 static PyObject *index_getitem(indexObject *self, PyObject *value)
 {
 	char *node;
 	Py_ssize_t nodelen;
 	int rev;
 
 	if (PyInt_Check(value))
 		return index_get(self, PyInt_AS_LONG(value));
 
 	if (node_check(value, &node, &nodelen) == -1)
 		return NULL;
 	rev = index_find_node(self, node, nodelen);
 	if (rev >= -1)
 		return PyInt_FromLong(rev);
 	if (rev == -2)
 		raise_revlog_error();
 	return NULL;
 }
 
 static int nt_partialmatch(indexObject *self, const char *node,
 			   Py_ssize_t nodelen)
 {
 	int rev;
 
 	if (nt_init(self) == -1)
 		return -3;
 
 	if (self->ntrev > 0) {
 		/* ensure that the radix tree is fully populated */
 		for (rev = self->ntrev - 1; rev >= 0; rev--) {
 			const char *n = index_node(self, rev);
 			if (n == NULL)
 				return -2;
 			if (nt_insert(self, n, rev) == -1)
 				return -3;
 		}
 		self->ntrev = rev;
 	}
 
 	return nt_find(self, node, nodelen, 1);
 }
 
 static PyObject *index_partialmatch(indexObject *self, PyObject *args)
 {
 	const char *fullnode;
 	int nodelen;
 	char *node;
 	int rev, i;
 
 	if (!PyArg_ParseTuple(args, "s#", &node, &nodelen))
 		return NULL;
 
 	if (nodelen < 4) {
 		PyErr_SetString(PyExc_ValueError, "key too short");
 		return NULL;
 	}
 
 	if (nodelen > 40) {
 		PyErr_SetString(PyExc_ValueError, "key too long");
 		return NULL;
 	}
 
 	for (i = 0; i < nodelen; i++)
 		hexdigit(node, i);
 	if (PyErr_Occurred()) {
 		/* input contains non-hex characters */
 		PyErr_Clear();
 		Py_RETURN_NONE;
 	}
 
 	rev = nt_partialmatch(self, node, nodelen);
 
 	switch (rev) {
 	case -4:
 		raise_revlog_error();
 	case -3:
 		return NULL;
 	case -2:
 		Py_RETURN_NONE;
 	case -1:
 		return PyBytes_FromStringAndSize(nullid, 20);
 	}
 
 	fullnode = index_node(self, rev);
 	if (fullnode == NULL) {
 		PyErr_Format(PyExc_IndexError,
 			     "could not access rev %d", rev);
 		return NULL;
 	}
 	return PyBytes_FromStringAndSize(fullnode, 20);
 }
 
 static PyObject *index_m_get(indexObject *self, PyObject *args)
 {
 	Py_ssize_t nodelen;
 	PyObject *val;
 	char *node;
 	int rev;
 
 	if (!PyArg_ParseTuple(args, "O", &val))
 		return NULL;
 	if (node_check(val, &node, &nodelen) == -1)
 		return NULL;
 	rev = index_find_node(self, node, nodelen);
 	if (rev == -3)
 		return NULL;
 	if (rev == -2)
 		Py_RETURN_NONE;
 	return PyInt_FromLong(rev);
 }
 
 static int index_contains(indexObject *self, PyObject *value)
 {
 	char *node;
 	Py_ssize_t nodelen;
 
 	if (PyInt_Check(value)) {
 		long rev = PyInt_AS_LONG(value);
 		return rev >= -1 && rev < index_length(self);
 	}
 
 	if (node_check(value, &node, &nodelen) == -1)
 		return -1;
 
 	switch (index_find_node(self, node, nodelen)) {
 	case -3:
 		return -1;
 	case -2:
 		return 0;
 	default:
 		return 1;
 	}
 }
 
 typedef uint64_t bitmask;
 
 /*
  * Given a disjoint set of revs, return all candidates for the
  * greatest common ancestor. In revset notation, this is the set
  * "heads(::a and ::b and ...)"
  */
 static PyObject *find_gca_candidates(indexObject *self, const int *revs,
 				     int revcount)
 {
 	const bitmask allseen = (1ull << revcount) - 1;
 	const bitmask poison = 1ull << revcount;
 	PyObject *gca = PyList_New(0);
 	int i, v, interesting;
 	int maxrev = -1;
 	bitmask sp;
 	bitmask *seen;
 
 	if (gca == NULL)
 		return PyErr_NoMemory();
 
 	for (i = 0; i < revcount; i++) {
 		if (revs[i] > maxrev)
 			maxrev = revs[i];
 	}
 
 	seen = calloc(sizeof(*seen), maxrev + 1);
 	if (seen == NULL) {
 		Py_DECREF(gca);
 		return PyErr_NoMemory();
 	}
 
 	for (i = 0; i < revcount; i++)
 		seen[revs[i]] = 1ull << i;
 
 	interesting = revcount;
 
 	for (v = maxrev; v >= 0 && interesting; v--) {
 		bitmask sv = seen[v];
 		int parents[2];
 
 		if (!sv)
 			continue;
 
 		if (sv < poison) {
 			interesting -= 1;
 			if (sv == allseen) {
 				PyObject *obj = PyInt_FromLong(v);
 				if (obj == NULL)
 					goto bail;
 				if (PyList_Append(gca, obj) == -1) {
 					Py_DECREF(obj);
 					goto bail;
 				}
 				sv |= poison;
 				for (i = 0; i < revcount; i++) {
 					if (revs[i] == v)
 						goto done;
 				}
 			}
 		}
 		if (index_get_parents(self, v, parents, maxrev) < 0)
 			goto bail;
 
 		for (i = 0; i < 2; i++) {
 			int p = parents[i];
 			if (p == -1)
 				continue;
 			sp = seen[p];
 			if (sv < poison) {
 				if (sp == 0) {
 					seen[p] = sv;
 					interesting++;
 				}
 				else if (sp != sv)
 					seen[p] |= sv;
 			} else {
 				if (sp && sp < poison)
 					interesting--;
 				seen[p] = sv;
 			}
 		}
 	}
 
 done:
 	free(seen);
 	return gca;
 bail:
 	free(seen);
 	Py_XDECREF(gca);
 	return NULL;
 }
 
 /*
  * Given a disjoint set of revs, return the subset with the longest
  * path to the root.
  */
 static PyObject *find_deepest(indexObject *self, PyObject *revs)
 {
 	const Py_ssize_t revcount = PyList_GET_SIZE(revs);
 	static const Py_ssize_t capacity = 24;
 	int *depth, *interesting = NULL;
 	int i, j, v, ninteresting;
 	PyObject *dict = NULL, *keys = NULL;
 	long *seen = NULL;
 	int maxrev = -1;
 	long final;
 
 	if (revcount > capacity) {
 		PyErr_Format(PyExc_OverflowError,
 			     "bitset size (%ld) > capacity (%ld)",
 			     (long)revcount, (long)capacity);
 		return NULL;
 	}
 
 	for (i = 0; i < revcount; i++) {
 		int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
 		if (n > maxrev)
 			maxrev = n;
 	}
 
 	depth = calloc(sizeof(*depth), maxrev + 1);
 	if (depth == NULL)
 		return PyErr_NoMemory();
 
 	seen = calloc(sizeof(*seen), maxrev + 1);
 	if (seen == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	interesting = calloc(sizeof(*interesting), 1 << revcount);
 	if (interesting == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	if (PyList_Sort(revs) == -1)
 		goto bail;
 
 	for (i = 0; i < revcount; i++) {
 		int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
 		long b = 1l << i;
 		depth[n] = 1;
 		seen[n] = b;
 		interesting[b] = 1;
 	}
 
 	/* invariant: ninteresting is the number of non-zero entries in
 	 * interesting. */
 	ninteresting = (int)revcount;
 
 	for (v = maxrev; v >= 0 && ninteresting > 1; v--) {
 		int dv = depth[v];
 		int parents[2];
 		long sv;
 
 		if (dv == 0)
 			continue;
 
 		sv = seen[v];
 		if (index_get_parents(self, v, parents, maxrev) < 0)
 			goto bail;
 
 		for (i = 0; i < 2; i++) {
 			int p = parents[i];
 			long sp;
 			int dp;
 
 			if (p == -1)
 				continue;
 
 			dp = depth[p];
 			sp = seen[p];
 			if (dp <= dv) {
 				depth[p] = dv + 1;
 				if (sp != sv) {
 					interesting[sv] += 1;
 					seen[p] = sv;
 					if (sp) {
 						interesting[sp] -= 1;
 						if (interesting[sp] == 0)
 							ninteresting -= 1;
 					}
 				}
 			}
 			else if (dv == dp - 1) {
 				long nsp = sp | sv;
 				if (nsp == sp)
 					continue;
 				seen[p] = nsp;
 				interesting[sp] -= 1;
 				if (interesting[sp] == 0)
 					ninteresting -= 1;
 				if (interesting[nsp] == 0)
 					ninteresting += 1;
 				interesting[nsp] += 1;
 			}
 		}
 		interesting[sv] -= 1;
 		if (interesting[sv] == 0)
 			ninteresting -= 1;
 	}
 
 	final = 0;
 	j = ninteresting;
 	for (i = 0; i < (int)(2 << revcount) && j > 0; i++) {
 		if (interesting[i] == 0)
 			continue;
 		final |= i;
 		j -= 1;
 	}
 	if (final == 0) {
 		keys = PyList_New(0);
 		goto bail;
 	}
 
 	dict = PyDict_New();
 	if (dict == NULL)
 		goto bail;
 
 	for (i = 0; i < revcount; i++) {
 		PyObject *key;
 
 		if ((final & (1 << i)) == 0)
 			continue;
 
 		key = PyList_GET_ITEM(revs, i);
 		Py_INCREF(key);
 		Py_INCREF(Py_None);
 		if (PyDict_SetItem(dict, key, Py_None) == -1) {
 			Py_DECREF(key);
 			Py_DECREF(Py_None);
 			goto bail;
 		}
 	}
 
 	keys = PyDict_Keys(dict);
 
 bail:
 	free(depth);
 	free(seen);
 	free(interesting);
 	Py_XDECREF(dict);
 
 	return keys;
 }
 
 /*
  * Given a (possibly overlapping) set of revs, return all the
  * common ancestors heads: heads(::args[0] and ::a[1] and ...)
  */
 static PyObject *index_commonancestorsheads(indexObject *self, PyObject *args)
 {
 	PyObject *ret = NULL;
 	Py_ssize_t argcount, i, len;
 	bitmask repeat = 0;
 	int revcount = 0;
 	int *revs;
 
 	argcount = PySequence_Length(args);
 	revs = PyMem_Malloc(argcount * sizeof(*revs));
 	if (argcount > 0 && revs == NULL)
 		return PyErr_NoMemory();
 	len = index_length(self) - 1;
 
 	for (i = 0; i < argcount; i++) {
 		static const int capacity = 24;
 		PyObject *obj = PySequence_GetItem(args, i);
 		bitmask x;
 		long val;
 
 		if (!PyInt_Check(obj)) {
 			PyErr_SetString(PyExc_TypeError,
 					"arguments must all be ints");
 			Py_DECREF(obj);
 			goto bail;
 		}
 		val = PyInt_AsLong(obj);
 		Py_DECREF(obj);
 		if (val == -1) {
 			ret = PyList_New(0);
 			goto done;
 		}
 		if (val < 0 || val >= len) {
 			PyErr_SetString(PyExc_IndexError,
 					"index out of range");
 			goto bail;
 		}
 		/* this cheesy bloom filter lets us avoid some more
 		 * expensive duplicate checks in the common set-is-disjoint
 		 * case */
 		x = 1ull << (val & 0x3f);
 		if (repeat & x) {
 			int k;
 			for (k = 0; k < revcount; k++) {
 				if (val == revs[k])
 					goto duplicate;
 			}
 		}
 		else repeat |= x;
 		if (revcount >= capacity) {
 			PyErr_Format(PyExc_OverflowError,
 				     "bitset size (%d) > capacity (%d)",
 				     revcount, capacity);
 			goto bail;
 		}
 		revs[revcount++] = (int)val;
 	duplicate:;
 	}
 
 	if (revcount == 0) {
 		ret = PyList_New(0);
 		goto done;
 	}
 	if (revcount == 1) {
 		PyObject *obj;
 		ret = PyList_New(1);
 		if (ret == NULL)
 			goto bail;
 		obj = PyInt_FromLong(revs[0]);
 		if (obj == NULL)
 			goto bail;
 		PyList_SET_ITEM(ret, 0, obj);
 		goto done;
 	}
 
 	ret = find_gca_candidates(self, revs, revcount);
 	if (ret == NULL)
 		goto bail;
 
 done:
 	PyMem_Free(revs);
 	return ret;
 
 bail:
 	PyMem_Free(revs);
 	Py_XDECREF(ret);
 	return NULL;
 }
 
 /*
  * Given a (possibly overlapping) set of revs, return the greatest
  * common ancestors: those with the longest path to the root.
  */
 static PyObject *index_ancestors(indexObject *self, PyObject *args)
 {
 	PyObject *ret;
 	PyObject *gca = index_commonancestorsheads(self, args);
 	if (gca == NULL)
 		return NULL;
 
 	if (PyList_GET_SIZE(gca) <= 1) {
 		return gca;
 	}
 
 	ret = find_deepest(self, gca);
 	Py_DECREF(gca);
 	return ret;
 }
 
 /*
  * Invalidate any trie entries introduced by added revs.
  */
 static void nt_invalidate_added(indexObject *self, Py_ssize_t start)
 {
 	Py_ssize_t i, len = PyList_GET_SIZE(self->added);
 
 	for (i = start; i < len; i++) {
 		PyObject *tuple = PyList_GET_ITEM(self->added, i);
 		PyObject *node = PyTuple_GET_ITEM(tuple, 7);
 
 		nt_insert(self, PyBytes_AS_STRING(node), -1);
 	}
 
 	if (start == 0)
 		Py_CLEAR(self->added);
 }
 
 /*
  * Delete a numeric range of revs, which must be at the end of the
  * range, but exclude the sentinel nullid entry.
  */
 static int index_slice_del(indexObject *self, PyObject *item)
 {
 	Py_ssize_t start, stop, step, slicelength;
 	Py_ssize_t length = index_length(self);
 	int ret = 0;
 
 /* Argument changed from PySliceObject* to PyObject* in Python 3. */
 #ifdef IS_PY3K
 	if (PySlice_GetIndicesEx(item, length,
 #else
 	if (PySlice_GetIndicesEx((PySliceObject*)item, length,
 #endif
 				 &start, &stop, &step, &slicelength) < 0)
 		return -1;
 
 	if (slicelength <= 0)
 		return 0;
 
 	if ((step < 0 && start < stop) || (step > 0 && start > stop))
 		stop = start;
 
 	if (step < 0) {
 		stop = start + 1;
 		start = stop + step*(slicelength - 1) - 1;
 		step = -step;
 	}
 
 	if (step != 1) {
 		PyErr_SetString(PyExc_ValueError,
 				"revlog index delete requires step size of 1");
 		return -1;
 	}
 
 	if (stop != length - 1) {
 		PyErr_SetString(PyExc_IndexError,
 				"revlog index deletion indices are invalid");
 		return -1;
 	}
 
 	if (start < self->length - 1) {
 		if (self->nt) {
 			Py_ssize_t i;
 
 			for (i = start + 1; i < self->length - 1; i++) {
 				const char *node = index_node(self, i);
 
 				if (node)
 					nt_insert(self, node, -1);
 			}
 			if (self->added)
 				nt_invalidate_added(self, 0);
 			if (self->ntrev > start)
 				self->ntrev = (int)start;
 		}
 		self->length = start + 1;
 		if (start < self->raw_length) {
 			if (self->cache) {
 				Py_ssize_t i;
 				for (i = start; i < self->raw_length; i++)
 					Py_CLEAR(self->cache[i]);
 			}
 			self->raw_length = start;
 		}
 		goto done;
 	}
 
 	if (self->nt) {
 		nt_invalidate_added(self, start - self->length + 1);
 		if (self->ntrev > start)
 			self->ntrev = (int)start;
 	}
 	if (self->added)
 		ret = PyList_SetSlice(self->added, start - self->length + 1,
 				      PyList_GET_SIZE(self->added), NULL);
 done:
 	Py_CLEAR(self->headrevs);
 	return ret;
 }
 
 /*
  * Supported ops:
  *
  * slice deletion
  * string assignment (extend node->rev mapping)
  * string deletion (shrink node->rev mapping)
  */
 static int index_assign_subscript(indexObject *self, PyObject *item,
 				  PyObject *value)
 {
 	char *node;
 	Py_ssize_t nodelen;
 	long rev;
 
 	if (PySlice_Check(item) && value == NULL)
 		return index_slice_del(self, item);
 
 	if (node_check(item, &node, &nodelen) == -1)
 		return -1;
 
 	if (value == NULL)
 		return self->nt ? nt_insert(self, node, -1) : 0;
 	rev = PyInt_AsLong(value);
 	if (rev > INT_MAX || rev < 0) {
 		if (!PyErr_Occurred())
 			PyErr_SetString(PyExc_ValueError, "rev out of range");
 		return -1;
 	}
 
 	if (nt_init(self) == -1)
 		return -1;
 	return nt_insert(self, node, (int)rev);
 }
 
 /*
  * Find all RevlogNG entries in an index that has inline data. Update
  * the optional "offsets" table with those entries.
  */
 static Py_ssize_t inline_scan(indexObject *self, const char **offsets)
 {
 	const char *data = (const char *)self->buf.buf;
 	Py_ssize_t pos = 0;
 	Py_ssize_t end = self->buf.len;
 	long incr = v1_hdrsize;
 	Py_ssize_t len = 0;
 
 	while (pos + v1_hdrsize <= end && pos >= 0) {
 		uint32_t comp_len;
 		/* 3rd element of header is length of compressed inline data */
 		comp_len = getbe32(data + pos + 8);
 		incr = v1_hdrsize + comp_len;
 		if (offsets)
 			offsets[len] = data + pos;
 		len++;
 		pos += incr;
 	}
 
 	if (pos != end) {
 		if (!PyErr_Occurred())
 			PyErr_SetString(PyExc_ValueError, "corrupt index file");
 		return -1;
 	}
 
 	return len;
 }
 
 static int index_init(indexObject *self, PyObject *args)
 {
 	PyObject *data_obj, *inlined_obj;
 	Py_ssize_t size;
 
 	/* Initialize before argument-checking to avoid index_dealloc() crash. */
 	self->raw_length = 0;
 	self->added = NULL;
 	self->cache = NULL;
 	self->data = NULL;
 	memset(&self->buf, 0, sizeof(self->buf));
 	self->headrevs = NULL;
 	self->filteredrevs = Py_None;
 	Py_INCREF(Py_None);
 	self->nt = NULL;
 	self->offsets = NULL;
 
 	if (!PyArg_ParseTuple(args, "OO", &data_obj, &inlined_obj))
 		return -1;
 	if (!PyObject_CheckBuffer(data_obj)) {
 		PyErr_SetString(PyExc_TypeError,
 				"data does not support buffer interface");
 		return -1;
 	}
 
 	if (PyObject_GetBuffer(data_obj, &self->buf, PyBUF_SIMPLE) == -1)
 		return -1;
 	size = self->buf.len;
 
 	self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
 	self->data = data_obj;
 
 	self->ntlength = self->ntcapacity = 0;
 	self->ntdepth = self->ntsplits = 0;
 	self->ntlookups = self->ntmisses = 0;
 	self->ntrev = -1;
 	Py_INCREF(self->data);
 
 	if (self->inlined) {
 		Py_ssize_t len = inline_scan(self, NULL);
 		if (len == -1)
 			goto bail;
 		self->raw_length = len;
 		self->length = len + 1;
 	} else {
 		if (size % v1_hdrsize) {
 			PyErr_SetString(PyExc_ValueError, "corrupt index file");
 			goto bail;
 		}
 		self->raw_length = size / v1_hdrsize;
 		self->length = self->raw_length + 1;
 	}
 
 	return 0;
 bail:
 	return -1;
 }
 
 static PyObject *index_nodemap(indexObject *self)
 {
 	Py_INCREF(self);
 	return (PyObject *)self;
 }
 
 static void index_dealloc(indexObject *self)
 {
 	_index_clearcaches(self);
 	Py_XDECREF(self->filteredrevs);
 	if (self->buf.buf) {
 		PyBuffer_Release(&self->buf);
 		memset(&self->buf, 0, sizeof(self->buf));
 	}
 	Py_XDECREF(self->data);
 	Py_XDECREF(self->added);
 	PyObject_Del(self);
 }
 
 static PySequenceMethods index_sequence_methods = {
 	(lenfunc)index_length,   /* sq_length */
 	0,                       /* sq_concat */
 	0,                       /* sq_repeat */
 	(ssizeargfunc)index_get, /* sq_item */
 	0,                       /* sq_slice */
 	0,                       /* sq_ass_item */
 	0,                       /* sq_ass_slice */
 	(objobjproc)index_contains, /* sq_contains */
 };
 
 static PyMappingMethods index_mapping_methods = {
 	(lenfunc)index_length,                 /* mp_length */
 	(binaryfunc)index_getitem,             /* mp_subscript */
 	(objobjargproc)index_assign_subscript, /* mp_ass_subscript */
 };
 
 static PyMethodDef index_methods[] = {
 	{"ancestors", (PyCFunction)index_ancestors, METH_VARARGS,
 	 "return the gca set of the given revs"},
 	{"commonancestorsheads", (PyCFunction)index_commonancestorsheads,
 	  METH_VARARGS,
 	  "return the heads of the common ancestors of the given revs"},
 	{"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS,
 	 "clear the index caches"},
 	{"get", (PyCFunction)index_m_get, METH_VARARGS,
 	 "get an index entry"},
 	{"computephasesmapsets", (PyCFunction)compute_phases_map_sets,
 			METH_VARARGS, "compute phases"},
 	{"reachableroots2", (PyCFunction)reachableroots2, METH_VARARGS,
 		"reachableroots"},
 	{"headrevs", (PyCFunction)index_headrevs, METH_VARARGS,
 	 "get head revisions"}, /* Can do filtering since 3.2 */
 	{"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS,
 	 "get filtered head revisions"}, /* Can always do filtering */
 	{"deltachain", (PyCFunction)index_deltachain, METH_VARARGS,
 	 "determine revisions with deltas to reconstruct fulltext"},
 	{"insert", (PyCFunction)index_insert, METH_VARARGS,
 	 "insert an index entry"},
 	{"partialmatch", (PyCFunction)index_partialmatch, METH_VARARGS,
 	 "match a potentially ambiguous node ID"},
 	{"stats", (PyCFunction)index_stats, METH_NOARGS,
 	 "stats for the index"},
 	{NULL} /* Sentinel */
 };
 
 static PyGetSetDef index_getset[] = {
 	{"nodemap", (getter)index_nodemap, NULL, "nodemap", NULL},
 	{NULL} /* Sentinel */
 };
 
 static PyTypeObject indexType = {
 	PyVarObject_HEAD_INIT(NULL, 0)
 	"parsers.index",           /* tp_name */
 	sizeof(indexObject),       /* tp_basicsize */
 	0,                         /* tp_itemsize */
 	(destructor)index_dealloc, /* tp_dealloc */
 	0,                         /* tp_print */
 	0,                         /* tp_getattr */
 	0,                         /* tp_setattr */
 	0,                         /* tp_compare */
 	0,                         /* tp_repr */
 	0,                         /* tp_as_number */
 	&index_sequence_methods,   /* tp_as_sequence */
 	&index_mapping_methods,    /* tp_as_mapping */
 	0,                         /* tp_hash */
 	0,                         /* tp_call */
 	0,                         /* tp_str */
 	0,                         /* tp_getattro */
 	0,                         /* tp_setattro */
 	0,                         /* tp_as_buffer */
 	Py_TPFLAGS_DEFAULT,        /* tp_flags */
 	"revlog index",            /* tp_doc */
 	0,                         /* tp_traverse */
 	0,                         /* tp_clear */
 	0,                         /* tp_richcompare */
 	0,                         /* tp_weaklistoffset */
 	0,                         /* tp_iter */
 	0,                         /* tp_iternext */
 	index_methods,             /* tp_methods */
 	0,                         /* tp_members */
 	index_getset,              /* tp_getset */
 	0,                         /* tp_base */
 	0,                         /* tp_dict */
 	0,                         /* tp_descr_get */
 	0,                         /* tp_descr_set */
 	0,                         /* tp_dictoffset */
 	(initproc)index_init,      /* tp_init */
 	0,                         /* tp_alloc */
 };
 
 /*
  * returns a tuple of the form (index, index, cache) with elements as
  * follows:
  *
  * index: an index object that lazily parses RevlogNG records
  * cache: if data is inlined, a tuple (0, index_file_content), else None
  *        index_file_content could be a string, or a buffer
  *
  * added complications are for backwards compatibility
  */
 PyObject *parse_index2(PyObject *self, PyObject *args)
 {
 	PyObject *tuple = NULL, *cache = NULL;
 	indexObject *idx;
 	int ret;
 
 	idx = PyObject_New(indexObject, &indexType);
 	if (idx == NULL)
 		goto bail;
 
 	ret = index_init(idx, args);
 	if (ret == -1)
 		goto bail;
 
 	if (idx->inlined) {
 		cache = Py_BuildValue("iO", 0, idx->data);
 		if (cache == NULL)
 			goto bail;
 	} else {
 		cache = Py_None;
 		Py_INCREF(cache);
 	}
 
 	tuple = Py_BuildValue("NN", idx, cache);
 	if (!tuple)
 		goto bail;
 	return tuple;
 
 bail:
 	Py_XDECREF(idx);
 	Py_XDECREF(cache);
 	Py_XDECREF(tuple);
 	return NULL;
 }
 
 void revlog_module_init(PyObject *mod)
 {
 	indexType.tp_new = PyType_GenericNew;
 	if (PyType_Ready(&indexType) < 0)
 		return;
 	Py_INCREF(&indexType);
 	PyModule_AddObject(mod, "index", (PyObject *)&indexType);
 
 	nullentry = Py_BuildValue("iiiiiiis#", 0, 0, 0,
 				  -1, -1, -1, -1, nullid, 20);
 	if (nullentry)
 		PyObject_GC_UnTrack(nullentry);
 }