manifest.c: new extension code to lazily parse manifests

This lets us iterate manifests in order, but do a _lot_ less work in
the common case when we only care about a few manifest entries.

Many thanks to Mike Edgar for reviewing this in advance of it going
out to the list, which caught many things I missed.

This version of the patch includes C89 fixes from Sean Farley and
many correctness/efficiency cleanups from Martin von
Zweigbergk. Thanks to both!

mercurial/manifest.c

@@ -0,0 +1,841 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 <assert.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include <Python.h>
+
+/* VC9 doesn't include bool and lacks stdbool.h based on my searching */
+#ifdef _MSC_VER
+#define true 1
+#define false 0
+typedef unsigned char bool;
+#else
+#include <stdbool.h>
+#endif
+
+#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
+
+/* defined in parsers.c */
+PyObject *unhexlify(const char *str, int len);
+
+/* 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, PyString_AsString(hash), 20);
+		Py_DECREF(hash);
+		newhash[20] = l->hash_suffix;
+		hash = PyString_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 = PyString_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 = PyString_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 PyObject *lmiter_iternext(PyObject *o)
+{
+	size_t pl;
+	line *l;
+	Py_ssize_t consumed;
+	PyObject *ret = NULL, *path = NULL, *hash = NULL, *flags = NULL;
+	lmIter *self = (lmIter *)o;
+	do {
+		self->pos++;
+		if (self->pos >= self->m->numlines) {
+			goto bail;
+		}
+		/* skip over deleted manifest entries */
+	} while (self->m->lines[self->pos].deleted);
+	l = self->m->lines + self->pos;
+	pl = pathlen(l);
+	path = PyString_FromStringAndSize(l->start, pl);
+	hash = nodeof(l);
+	consumed = pl + 41;
+	flags = PyString_FromStringAndSize(l->start + consumed,
+									   l->len - consumed - 1);
+	if (!flags) {
+		goto bail;
+	}
+	ret = PyTuple_Pack(3, path, hash, flags);
+ bail:
+	Py_XDECREF(path);
+	Py_XDECREF(hash);
+	Py_XDECREF(flags);
+	return ret;
+}
+
+static PyTypeObject lazymanifestIterator = {
+	PyObject_HEAD_INIT(NULL)
+	0,                               /*ob_size */
+	"parsers.lazymanifest.iterator", /*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 */
+	/* tp_flags: Py_TPFLAGS_HAVE_ITER tells python to
+	   use tp_iter and tp_iternext fields. */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_ITER,
+	"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_iternext,                 /* tp_iternext: next() method */
+};
+
+static lazymanifest *lazymanifest_copy(lazymanifest *self);
+
+static PyObject *lazymanifest_getiter(lazymanifest *self)
+{
+	lmIter *i = NULL;
+	lazymanifest *t = lazymanifest_copy(self);
+	if (!t) {
+		PyErr_NoMemory();
+		return NULL;
+	}
+	i = PyObject_New(lmIter, &lazymanifestIterator);
+	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 (!PyString_Check(key)) {
+		PyErr_Format(PyExc_TypeError,
+			     "getitem: manifest keys must be a string.");
+		return NULL;
+	}
+	needle.start = PyString_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 (!PyString_Check(key)) {
+		PyErr_Format(PyExc_TypeError,
+			     "delitem: manifest keys must be a string.");
+		return -1;
+	}
+	needle.start = PyString_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;
+}
+
+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;
+	line *hit;
+	if (!PyString_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 (PyString_AsStringAndSize(key, &path, &plen) == -1) {
+		return -1;
+	}
+
+	pyhash = PyTuple_GetItem(value, 0);
+	if (!PyString_Check(pyhash)) {
+		PyErr_Format(PyExc_TypeError,
+			     "node must be a 20-byte string");
+		return -1;
+	}
+	hlen = PyString_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 = PyString_AsString(pyhash);
+
+	pyflags = PyTuple_GetItem(value, 1);
+	if (!PyString_Check(pyflags) || PyString_Size(pyflags) > 1) {
+		PyErr_Format(PyExc_TypeError,
+			     "flags must a 0 or 1 byte string");
+		return -1;
+	}
+	if (PyString_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++) {
+		sprintf(dest + plen + 1 + (i * 2), "%02hhx", 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? */
+	hit = bsearch(&new, self->lines, self->numlines,
+		      sizeof(line), &linecmp);
+	self->dirty = true;
+	if (hit) {
+		/* updating a line we already had */
+		if (hit->from_malloc) {
+			free(hit->start);
+		}
+		if (hit->deleted) {
+			self->livelines++;
+		}
+		*hit = new;
+	} else {
+		/* new line */
+		if (!realloc_if_full(self)) {
+			PyErr_NoMemory();
+			return -1;
+		}
+		self->lines[self->numlines++] = new;
+		self->livelines++;
+		/* TODO: do a binary search and insert rather than
+		 * append and qsort. Also offer a batch-insert
+		 * interface, which should be a nice little
+		 * performance win.
+		 */
+		qsort(self->lines, self->numlines, sizeof(line), &linecmp);
+	}
+	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 (!PyString_Check(key)) {
+		/* Our keys are always strings, so if the contains
+		 * check is for a non-string, just return false. */
+		return 0;
+	}
+	needle.start = PyString_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 = PyString_FromStringAndSize(NULL, need);
+	if (!pydata)
+		return -1;
+	data = PyString_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);
+	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 *arg = PyString_FromString(self->lines[i].start);
+		PyObject *arglist = PyTuple_Pack(1, arg);
+		PyObject *result = PyObject_CallObject(matchfn, arglist);
+		Py_DECREF(arglist);
+		Py_DECREF(arg);
+		/* 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 = PyString_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 ?
+			PyString_FromString(left->start) :
+			PyString_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[] = {
+	{"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},
+};
+
+static PyTypeObject lazymanifestType = {
+	PyObject_HEAD_INIT(NULL)
+	0,                                                /* ob_size */
+	"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 */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_SEQUENCE_IN, /* tp_flags */
+	"TODO(augie)",                                    /* tp_doc */
+	0,                                                /* tp_traverse */
+	0,                                                /* tp_clear */
+	0,                                                /* tp_richcompare */
+	0,                                             /* tp_weaklistoffset */
+	(getiterfunc)lazymanifest_getiter,                /* 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);
+}

tests/test-manifest.py

@@ -0,0 +1,221 b''
+import binascii
+import unittest
+import itertools
+
+import silenttestrunner
+
+from mercurial import parsers
+
+HASH_1 = '1' * 40
+HASH_2 = 'f' * 40
+HASH_3 = '1234567890abcdef0987654321deadbeef0fcafe'
+A_SHORT_MANIFEST = (
+    'bar/baz/qux.py\0%(hash2)s%(flag2)s\n'
+    'foo\0%(hash1)s%(flag1)s\n'
+    ) % {'hash1': HASH_1,
+         'flag1': '',
+         'hash2': HASH_2,
+         'flag2': 'l',
+         }
+
+HUGE_MANIFEST_ENTRIES = 200001
+
+A_HUGE_MANIFEST = ''.join(sorted(
+    'file%d\0%s%s\n' % (i, h, f) for i, h, f in
+    itertools.izip(xrange(200001),
+                   itertools.cycle((HASH_1, HASH_2)),
+                   itertools.cycle(('', 'x', 'l')))))
+
+class testmanifest(unittest.TestCase):
+
+    def assertIn(self, thing, container, msg=None):
+        # assertIn new in 2.7, use it if available, otherwise polyfill
+        sup = getattr(unittest.TestCase, 'assertIn', False)
+        if sup:
+            return sup(self, thing, container, msg=msg)
+        if not msg:
+            msg = 'Expected %r in %r' % (thing, container)
+        self.assert_(thing in container, msg)
+
+    def testEmptyManifest(self):
+        m = parsers.lazymanifest('')
+        self.assertEqual(0, len(m))
+        self.assertEqual([], list(m))
+
+    def testManifest(self):
+        m = parsers.lazymanifest(A_SHORT_MANIFEST)
+        want = [
+            ('bar/baz/qux.py', binascii.unhexlify(HASH_2), 'l'),
+            ('foo', binascii.unhexlify(HASH_1), ''),
+            ]
+        self.assertEqual(len(want), len(m))
+        self.assertEqual(want, list(m))
+        self.assertEqual((binascii.unhexlify(HASH_1), ''), m['foo'])
+        self.assertRaises(KeyError, lambda : m['wat'])
+        self.assertEqual((binascii.unhexlify(HASH_2), 'l'),
+                         m['bar/baz/qux.py'])
+
+    def testSetItem(self):
+        want = binascii.unhexlify(HASH_1), ''
+
+        m = parsers.lazymanifest('')
+        m['a'] = want
+        self.assertIn('a', m)
+        self.assertEqual(want, m['a'])
+        self.assertEqual('a\0' + HASH_1 + '\n', m.text())
+
+        m = parsers.lazymanifest(A_SHORT_MANIFEST)
+        m['a'] = want
+        self.assertEqual(want, m['a'])
+        self.assertEqual('a\0' + HASH_1 + '\n' + A_SHORT_MANIFEST,
+                         m.text())
+        m2 = m.copy()
+        del m
+        del m2 # make sure we don't double free() anything
+
+    def testCompaction(self):
+        unhex = binascii.unhexlify
+        h1, h2 = unhex(HASH_1), unhex(HASH_2)
+        m = parsers.lazymanifest(A_SHORT_MANIFEST)
+        m['alpha'] = h1, ''
+        m['beta'] = h2, ''
+        del m['foo']
+        want = 'alpha\0%s\nbar/baz/qux.py\0%sl\nbeta\0%s\n' % (
+            HASH_1, HASH_2, HASH_2)
+        self.assertEqual(want, m.text())
+        self.assertEqual(3, len(m))
+        self.assertEqual((h1, ''), m['alpha'])
+        self.assertEqual((h2, ''), m['beta'])
+        self.assertRaises(KeyError, lambda : m['foo'])
+        w = [('alpha', h1, ''), ('bar/baz/qux.py', h2, 'l'), ('beta', h2, '')]
+        self.assertEqual(w, list(m))
+
+    def testSetGetNodeSuffix(self):
+        clean = parsers.lazymanifest(A_SHORT_MANIFEST)
+        m = parsers.lazymanifest(A_SHORT_MANIFEST)
+        h, f = m['foo']
+        want = h + 'a', f
+        # Merge code wants to set 21-byte fake hashes at times
+        m['foo'] = want
+        self.assertEqual(want, m['foo'])
+        self.assertEqual([('bar/baz/qux.py', binascii.unhexlify(HASH_2), 'l'),
+                          ('foo', binascii.unhexlify(HASH_1) + 'a', '')],
+                         list(m))
+        # Sometimes it even tries a 22-byte fake hash, but we can
+        # return 21 and it'll work out
+        m['foo'] = want[0] + '+', f
+        self.assertEqual(want, m['foo'])
+        # make sure the suffix survives a copy
+        m2 = m.filtercopy(lambda x: x == 'foo')
+        self.assertEqual(want, m2['foo'])
+        self.assertEqual(1, len(m2))
+        self.assertEqual(('foo\0%s\n' % HASH_1), m2.text())
+        m2 = m.copy()
+        self.assertEqual(want, m2['foo'])
+        # suffix with iteration
+        self.assertEqual([('bar/baz/qux.py', binascii.unhexlify(HASH_2), 'l'),
+                          ('foo', want[0], '')], list(m))
+        # shows up in diff
+        self.assertEqual({'foo': (want, (h, ''))}, m.diff(clean))
+        self.assertEqual({'foo': ((h, ''), want)}, clean.diff(m))
+
+    def testFilterCopyException(self):
+        m = parsers.lazymanifest(A_SHORT_MANIFEST)
+        def filt(path):
+            if path == 'foo':
+                assert False
+            return True
+        self.assertRaises(AssertionError, m.filtercopy, filt)
+
+    def testRemoveItem(self):
+        m = parsers.lazymanifest(A_SHORT_MANIFEST)
+        del m['foo']
+        self.assertRaises(KeyError, lambda : m['foo'])
+        self.assertEqual(1, len(m))
+        self.assertEqual(1, len(list(m)))
+
+    def testManifestDiff(self):
+        MISSING = (None, '')
+        addl = 'z-only-in-left\0' + HASH_1 + '\n'
+        addr = 'z-only-in-right\0' + HASH_2 + 'x\n'
+        left = parsers.lazymanifest(
+            A_SHORT_MANIFEST.replace(HASH_1, HASH_3 + 'x') + addl)
+        right = parsers.lazymanifest(A_SHORT_MANIFEST + addr)
+        want = {
+            'foo': ((binascii.unhexlify(HASH_3), 'x'),
+                    (binascii.unhexlify(HASH_1), '')),
+            'z-only-in-left': ((binascii.unhexlify(HASH_1), ''), MISSING),
+            'z-only-in-right': (MISSING, (binascii.unhexlify(HASH_2), 'x')),
+            }
+        self.assertEqual(want, left.diff(right))
+
+        want = {
+            'bar/baz/qux.py': (MISSING, (binascii.unhexlify(HASH_2), 'l')),
+            'foo': (MISSING, (binascii.unhexlify(HASH_3), 'x')),
+            'z-only-in-left': (MISSING, (binascii.unhexlify(HASH_1), '')),
+            }
+        self.assertEqual(want, parsers.lazymanifest('').diff(left))
+
+        want = {
+            'bar/baz/qux.py': ((binascii.unhexlify(HASH_2), 'l'), MISSING),
+            'foo': ((binascii.unhexlify(HASH_3), 'x'), MISSING),
+            'z-only-in-left': ((binascii.unhexlify(HASH_1), ''), MISSING),
+            }
+        self.assertEqual(want, left.diff(parsers.lazymanifest('')))
+        copy = right.copy()
+        del copy['z-only-in-right']
+        del right['foo']
+        want = {
+            'foo': (MISSING, (binascii.unhexlify(HASH_1), '')),
+            'z-only-in-right': ((binascii.unhexlify(HASH_2), 'x'), MISSING),
+            }
+        self.assertEqual(want, right.diff(copy))
+
+        short = parsers.lazymanifest(A_SHORT_MANIFEST)
+        pruned = short.copy()
+        del pruned['foo']
+        want = {
+            'foo': ((binascii.unhexlify(HASH_1), ''), MISSING),
+            }
+        self.assertEqual(want, short.diff(pruned))
+        want = {
+            'foo': (MISSING, (binascii.unhexlify(HASH_1), '')),
+            }
+        self.assertEqual(want, pruned.diff(short))
+        want = {
+            'bar/baz/qux.py': None,
+            'foo': (MISSING, (binascii.unhexlify(HASH_1), '')),
+            }
+        self.assertEqual(want, pruned.diff(short, True))
+
+    def testReversedLines(self):
+        backwards = ''.join(
+            l + '\n' for l in reversed(A_SHORT_MANIFEST.split('\n')) if l)
+        try:
+            parsers.lazymanifest(backwards)
+            self.fail('Should have raised ValueError')
+        except ValueError, v:
+            self.assertIn('Manifest lines not in sorted order.', str(v))
+
+    def testNoTerminalNewline(self):
+        try:
+            parsers.lazymanifest(A_SHORT_MANIFEST + 'wat')
+            self.fail('Should have raised ValueError')
+        except ValueError, v:
+            self.assertIn('Manifest did not end in a newline.', str(v))
+
+    def testNoNewLineAtAll(self):
+        try:
+            parsers.lazymanifest('wat')
+            self.fail('Should have raised ValueError')
+        except ValueError, v:
+            self.assertIn('Manifest did not end in a newline.', str(v))
+
+    def testHugeManifest(self):
+        m = parsers.lazymanifest(A_HUGE_MANIFEST)
+        self.assertEqual(HUGE_MANIFEST_ENTRIES, len(m))
+        self.assertEqual(len(m), len(list(m)))
+
+
+if __name__ == '__main__':
+    silenttestrunner.main(__name__)

mercurial/parsers.c

@@ -1,2407 +1,2409 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 "util.h"
 
 static char *versionerrortext = "Python minor version mismatch";
 
 static int8_t hextable[256] = {
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1, /* 0-9 */
 	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* A-F */
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* a-f */
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
 	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
 };
 
 static char lowertable[128] = {
 	'\x00', '\x01', '\x02', '\x03', '\x04', '\x05', '\x06', '\x07',
 	'\x08', '\x09', '\x0a', '\x0b', '\x0c', '\x0d', '\x0e', '\x0f',
 	'\x10', '\x11', '\x12', '\x13', '\x14', '\x15', '\x16', '\x17',
 	'\x18', '\x19', '\x1a', '\x1b', '\x1c', '\x1d', '\x1e', '\x1f',
 	'\x20', '\x21', '\x22', '\x23', '\x24', '\x25', '\x26', '\x27',
 	'\x28', '\x29', '\x2a', '\x2b', '\x2c', '\x2d', '\x2e', '\x2f',
 	'\x30', '\x31', '\x32', '\x33', '\x34', '\x35', '\x36', '\x37',
 	'\x38', '\x39', '\x3a', '\x3b', '\x3c', '\x3d', '\x3e', '\x3f',
 	'\x40',
 	        '\x61', '\x62', '\x63', '\x64', '\x65', '\x66', '\x67', /* A-G */
 	'\x68', '\x69', '\x6a', '\x6b', '\x6c', '\x6d', '\x6e', '\x6f', /* H-O */
 	'\x70', '\x71', '\x72', '\x73', '\x74', '\x75', '\x76', '\x77', /* P-W */
 	'\x78', '\x79', '\x7a',                                         /* X-Z */
 	                        '\x5b', '\x5c', '\x5d', '\x5e', '\x5f',
 	'\x60', '\x61', '\x62', '\x63', '\x64', '\x65', '\x66', '\x67',
 	'\x68', '\x69', '\x6a', '\x6b', '\x6c', '\x6d', '\x6e', '\x6f',
 	'\x70', '\x71', '\x72', '\x73', '\x74', '\x75', '\x76', '\x77',
 	'\x78', '\x79', '\x7a', '\x7b', '\x7c', '\x7d', '\x7e', '\x7f'
 };
 
 static inline int hexdigit(const char *p, Py_ssize_t off)
 {
 	int8_t val = hextable[(unsigned char)p[off]];
 
 	if (val >= 0) {
 		return val;
 	}
 
 	PyErr_SetString(PyExc_ValueError, "input contains non-hex character");
 	return 0;
 }
 
 /*
  * Turn a hex-encoded string into binary.
  */
-static PyObject *unhexlify(const char *str, int len)
+PyObject *unhexlify(const char *str, int len)
 {
 	PyObject *ret;
 	char *d;
 	int i;
 
 	ret = PyBytes_FromStringAndSize(NULL, len / 2);
 
 	if (!ret)
 		return NULL;
 
 	d = PyBytes_AsString(ret);
 
 	for (i = 0; i < len;) {
 		int hi = hexdigit(str, i++);
 		int lo = hexdigit(str, i++);
 		*d++ = (hi << 4) | lo;
 	}
 
 	return ret;
 }
 
 static PyObject *asciilower(PyObject *self, PyObject *args)
 {
 	char *str, *newstr;
 	int i, len;
 	PyObject *newobj = NULL;
 
 	if (!PyArg_ParseTuple(args, "s#", &str, &len))
 		goto quit;
 
 	newobj = PyBytes_FromStringAndSize(NULL, len);
 	if (!newobj)
 		goto quit;
 
 	newstr = PyBytes_AS_STRING(newobj);
 
 	for (i = 0; i < len; i++) {
 		char c = str[i];
 		if (c & 0x80) {
 			PyObject *err = PyUnicodeDecodeError_Create(
 				"ascii", str, len, i, (i + 1),
 				"unexpected code byte");
 			PyErr_SetObject(PyExc_UnicodeDecodeError, err);
 			Py_XDECREF(err);
 			goto quit;
 		}
 		newstr[i] = lowertable[(unsigned char)c];
 	}
 
 	return newobj;
 quit:
 	Py_XDECREF(newobj);
 	return NULL;
 }
 
 /*
  * 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 : (int)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;
 
 	if (readlen < 0)
 		goto quit;
 
 	len = readlen;
 
 	/* read parents */
 	if (len < 40)
 		goto quit;
 
 	parents = Py_BuildValue("s#s#", str, 20, str + 20, 20);
 	if (!parents)
 		goto quit;
 
 	/* read filenames */
 	while (pos >= 40 && pos < len) {
 		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;
 }
 
 /*
  * 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;
 	double now;
 
 	if (!PyArg_ParseTuple(args, "O!O!Od: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 (!PyString_Check(k)) {
 			PyErr_SetString(PyExc_TypeError, "expected string key");
 			goto bail;
 		}
 		nbytes += PyString_GET_SIZE(k) + 17;
 		c = PyDict_GetItem(copymap, k);
 		if (c) {
 			if (!PyString_Check(c)) {
 				PyErr_SetString(PyExc_TypeError,
 						"expected string key");
 				goto bail;
 			}
 			nbytes += PyString_GET_SIZE(c) + 1;
 		}
 	}
 
 	packobj = PyString_FromStringAndSize(NULL, nbytes);
 	if (packobj == NULL)
 		goto bail;
 
 	p = PyString_AS_STRING(packobj);
 
 	pn = PySequence_ITEM(pl, 0);
 	if (PyString_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 (PyString_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;
 		uint32_t 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 == (uint32_t)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(mode, p);
 		putbe32(size, p + 4);
 		putbe32(mtime, p + 8);
 		t = p + 12;
 		p += 16;
 		len = PyString_GET_SIZE(k);
 		memcpy(p, PyString_AS_STRING(k), len);
 		p += len;
 		o = PyDict_GetItem(copymap, k);
 		if (o) {
 			*p++ = '\0';
 			l = PyString_GET_SIZE(o);
 			memcpy(p, PyString_AS_STRING(o), l);
 			p += l;
 			len += l + 1;
 		}
 		putbe32((uint32_t)len, t);
 	}
 
 	pos = p - PyString_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;
 }
 
 /*
  * 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 behaviours.
  *
  * 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 */
 	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 */
 	int ntlength;          /* # nodes in use */
 	int 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 = 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 PyString_AS_STRING(self->data) + pos * v1_hdrsize;
 }
 
 /*
  * 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 ? PyString_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 (PyString_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) {
 		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) \
 	t = PyInt_FromSsize_t(self->__n); \
 	if (!t) \
 		goto bail; \
 	if (PyDict_SetItemString(obj, __d, t) == -1) \
 		goto bail; \
 	Py_DECREF(t);
 
 	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;
 }
 
 /* arg should be Py_ssize_t but Python 2.4 do not support the n format */
 static int check_filter(PyObject *filter, unsigned long arg) {
 	if (filter) {
 		PyObject *arglist, *result;
 		int isfiltered;
 
 		arglist = Py_BuildValue("(k)", 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 PyObject *index_headrevs(indexObject *self, PyObject *args)
 {
 	Py_ssize_t i, len, addlen;
 	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)
 		goto bail;
 
 	for (i = 0; i < self->raw_length; i++) {
 		const char *data;
 		int parent_1, parent_2, isfiltered;
 
 		isfiltered = check_filter(filter, i);
 		if (isfiltered == -1) {
 			PyErr_SetString(PyExc_TypeError,
 				"unable to check filter");
 			goto bail;
 		}
 
 		if (isfiltered) {
 			nothead[i] = 1;
 			continue;
 		}
 
 		data = index_deref(self, i);
 		parent_1 = getbe32(data + 24);
 		parent_2 = getbe32(data + 28);
 
 		if (parent_1 >= 0)
 			nothead[parent_1] = 1;
 		if (parent_2 >= 0)
 			nothead[parent_2] = 1;
 	}
 
 	addlen = self->added ? PyList_GET_SIZE(self->added) : 0;
 
 	for (i = 0; i < addlen; i++) {
 		PyObject *rev = PyList_GET_ITEM(self->added, i);
 		PyObject *p1 = PyTuple_GET_ITEM(rev, 5);
 		PyObject *p2 = PyTuple_GET_ITEM(rev, 6);
 		long parent_1, parent_2;
 		int isfiltered;
 
 		if (!PyInt_Check(p1) || !PyInt_Check(p2)) {
 			PyErr_SetString(PyExc_TypeError,
 					"revlog parents are invalid");
 			goto bail;
 		}
 
 		isfiltered = check_filter(filter, i);
 		if (isfiltered == -1) {
 			PyErr_SetString(PyExc_TypeError,
 				"unable to check filter");
 			goto bail;
 		}
 
 		if (isfiltered) {
 			nothead[i] = 1;
 			continue;
 		}
 
 		parent_1 = PyInt_AS_LONG(p1);
 		parent_2 = PyInt_AS_LONG(p2);
 		if (parent_1 >= 0)
 			nothead[parent_1] = 1;
 		if (parent_2 >= 0)
 			nothead[parent_2] = 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;
 }
 
 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) {
 		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 (self->raw_length > INT_MAX) {
 			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 PyObject *raise_revlog_error(void)
 {
 	static PyObject *errclass;
 	PyObject *mod = NULL, *errobj;
 
 	if (errclass == NULL) {
 		PyObject *dict;
 
 		mod = PyImport_ImportModule("mercurial.error");
 		if (mod == NULL)
 			goto classfail;
 
 		dict = PyModule_GetDict(mod);
 		if (dict == NULL)
 			goto classfail;
 
 		errclass = PyDict_GetItemString(dict, "RevlogError");
 		if (errclass == NULL) {
 			PyErr_SetString(PyExc_SystemError,
 					"could not find RevlogError");
 			goto classfail;
 		}
 		Py_INCREF(errclass);
 		Py_DECREF(mod);
 	}
 
 	errobj = PyObject_CallFunction(errclass, NULL);
 	if (errobj == NULL)
 		return NULL;
 	PyErr_SetObject(errclass, errobj);
 	return errobj;
 
 classfail:
 	Py_XDECREF(mod);
 	return NULL;
 }
 
 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 PyString_FromStringAndSize(nullid, 20);
 	}
 
 	fullnode = index_node(self, rev);
 	if (fullnode == NULL) {
 		PyErr_Format(PyExc_IndexError,
 			     "could not access rev %d", rev);
 		return NULL;
 	}
 	return PyString_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;
 	}
 }
 
 static inline void index_get_parents(indexObject *self, int rev, int *ps)
 {
 	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);
 	}
 }
 
 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;
 				}
 			}
 		}
 		index_get_parents(self, v, parents);
 
 		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), 2 << 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;
 	}
 
 	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];
 		index_get_parents(self, v, parents);
 
 		for (i = 0; i < 2; i++) {
 			int p = parents[i];
 			long nsp, sp;
 			int dp;
 
 			if (p == -1)
 				continue;
 
 			dp = depth[p];
 			nsp = sp = seen[p];
 			if (dp <= dv) {
 				depth[p] = dv + 1;
 				if (sp != sv) {
 					interesting[sv] += 1;
 					nsp = seen[p] = sv;
 					if (sp) {
 						interesting[sp] -= 1;
 						if (interesting[sp] == 0)
 							ninteresting -= 1;
 					}
 				}
 			}
 			else if (dv == dp - 1) {
 				nsp = sp | sv;
 				if (nsp == sp)
 					continue;
 				seen[p] = nsp;
 				interesting[sp] -= 1;
 				if (interesting[sp] == 0 && 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 = 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:
 	free(revs);
 	return ret;
 
 bail:
 	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 *gca = index_commonancestorsheads(self, args);
 	if (gca == NULL)
 		return NULL;
 
 	if (PyList_GET_SIZE(gca) <= 1) {
 		Py_INCREF(gca);
 		return gca;
 	}
 
 	return find_deepest(self, gca);
 }
 
 /*
  * 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, PyString_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;
 
 	if (PySlice_GetIndicesEx((PySliceObject*)item, length,
 				 &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 = PyString_AS_STRING(self->data);
 	Py_ssize_t pos = 0;
 	Py_ssize_t end = PyString_GET_SIZE(self->data);
 	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;
 	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 (!PyString_Check(data_obj)) {
 		PyErr_SetString(PyExc_TypeError, "data is not a string");
 		return -1;
 	}
 	size = PyString_GET_SIZE(data_obj);
 
 	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);
 	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"},
 	{"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 */
 	{"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 = {
 	PyObject_HEAD_INIT(NULL)
 	0,                         /* ob_size */
 	"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 (index_file_content, 0), else None
  *
  * added complications are for backwards compatibility
  */
 static 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;
 }
 
 #define BUMPED_FIX 1
 #define USING_SHA_256 2
 
 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 = PyString_FromStringAndSize(source, hashwidth);
 		if (hash == NULL) {
 			Py_DECREF(list);
 			return NULL;
 		}
 		PyTuple_SetItem(list, i, hash);
 		source += hashwidth;
 	}
 	return list;
 }
 
 static PyObject *fm1readmarker(const char *data, uint32_t *msize)
 {
 	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;
 
 	*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++);
 
 	prec = PyString_FromStringAndSize(data, hashwidth);
 	data += hashwidth;
 	if (prec == NULL) {
 		goto bail;
 	}
 
 	succs = readshas(data, nsuccs, hashwidth);
 	if (succs == NULL) {
 		goto bail;
 	}
 	data += nsuccs * hashwidth;
 
 	if (nparents == 1 || nparents == 2) {
 		parents = readshas(data, nparents, hashwidth);
 		if (parents == NULL) {
 			goto bail;
 		}
 		data += nparents * hashwidth;
 	} else {
 		parents = Py_None;
 	}
 
 	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 metasize = (unsigned char)(*data++);
 		left = PyString_FromStringAndSize(meta, metasize);
 		meta += metasize;
 		metasize = (unsigned char)(*data++);
 		right = PyString_FromStringAndSize(meta, metasize);
 		meta += metasize;
 		if (!left || !right) {
 			Py_XDECREF(left);
 			Py_XDECREF(right);
 			goto bail;
 		}
 		tmp = PyTuple_Pack(2, left, right);
 		Py_DECREF(left);
 		Py_DECREF(right);
 		if (!tmp) {
 			goto bail;
 		}
 		PyTuple_SetItem(metadata, i, tmp);
 	}
 	ret = Py_BuildValue("(OOHO(di)O)", prec, succs, flags,
 			    metadata, mtime, (int)tz * 60, parents);
 bail:
 	Py_XDECREF(prec);
 	Py_XDECREF(succs);
 	Py_XDECREF(metadata);
 	if (parents != Py_None)
 		Py_XDECREF(parents);
 	return ret;
 }
 
 
 static PyObject *fm1readmarkers(PyObject *self, PyObject *args) {
 	const char *data;
 	Py_ssize_t datalen;
 	/* only unsigned long because python 2.4, should be Py_ssize_t */
 	unsigned long offset, stop;
 	PyObject *markers = NULL;
 
 	/* replace kk with nn when we drop Python 2.4 */
 	if (!PyArg_ParseTuple(args, "s#kk", &data, &datalen, &offset, &stop)) {
 		return NULL;
 	}
 	data += offset;
 	markers = PyList_New(0);
 	if (!markers) {
 		return NULL;
 	}
 	while (offset < stop) {
 		uint32_t msize;
 		int error;
 		PyObject *record = fm1readmarker(data, &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);
 
 static PyMethodDef methods[] = {
 	{"pack_dirstate", pack_dirstate, METH_VARARGS, "pack a 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"},
 	{"asciilower", asciilower, METH_VARARGS, "lowercase an ASCII string\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);
 
 static void module_init(PyObject *mod)
 {
 	/* 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);
 
 	indexType.tp_new = PyType_GenericNew;
 	if (PyType_Ready(&indexType) < 0 ||
 	    PyType_Ready(&dirstateTupleType) < 0)
 		return;
 	Py_INCREF(&indexType);
 	PyModule_AddObject(mod, "index", (PyObject *)&indexType);
 	Py_INCREF(&dirstateTupleType);
 	PyModule_AddObject(mod, "dirstatetuple",
 			   (PyObject *)&dirstateTupleType);
 
 	nullentry = Py_BuildValue("iiiiiiis#", 0, 0, 0,
 				  -1, -1, -1, -1, nullid, 20);
 	if (nullentry)
 		PyObject_GC_UnTrack(nullentry);
 }
 
 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;
 	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

setup.py

@@ -1,648 +1,649 b''
 #
 # This is the mercurial setup script.
 #
 # 'python setup.py install', or
 # 'python setup.py --help' for more options
 
 import sys, platform
 if getattr(sys, 'version_info', (0, 0, 0)) < (2, 4, 0, 'final'):
     raise SystemExit("Mercurial requires Python 2.4 or later.")
 
 if sys.version_info[0] >= 3:
     def b(s):
         '''A helper function to emulate 2.6+ bytes literals using string
         literals.'''
         return s.encode('latin1')
     printf = eval('print')
     libdir_escape = 'unicode_escape'
 else:
     libdir_escape = 'string_escape'
     def b(s):
         '''A helper function to emulate 2.6+ bytes literals using string
         literals.'''
         return s
     def printf(*args, **kwargs):
         f = kwargs.get('file', sys.stdout)
         end = kwargs.get('end', '\n')
         f.write(b(' ').join(args) + end)
 
 # Solaris Python packaging brain damage
 try:
     import hashlib
     sha = hashlib.sha1()
 except ImportError:
     try:
         import sha
         sha.sha # silence unused import warning
     except ImportError:
         raise SystemExit(
             "Couldn't import standard hashlib (incomplete Python install).")
 
 try:
     import zlib
     zlib.compressobj # silence unused import warning
 except ImportError:
     raise SystemExit(
         "Couldn't import standard zlib (incomplete Python install).")
 
 # The base IronPython distribution (as of 2.7.1) doesn't support bz2
 isironpython = False
 try:
     isironpython = (platform.python_implementation()
                     .lower().find("ironpython") != -1)
 except AttributeError:
     pass
 
 if isironpython:
     sys.stderr.write("warning: IronPython detected (no bz2 support)\n")
 else:
     try:
         import bz2
         bz2.BZ2Compressor # silence unused import warning
     except ImportError:
         raise SystemExit(
             "Couldn't import standard bz2 (incomplete Python install).")
 
 ispypy = "PyPy" in sys.version
 
 import os, stat, subprocess, time
 import re
 import shutil
 import tempfile
 from distutils import log
 from distutils.core import setup, Command, Extension
 from distutils.dist import Distribution
 from distutils.command.build import build
 from distutils.command.build_ext import build_ext
 from distutils.command.build_py import build_py
 from distutils.command.install_lib import install_lib
 from distutils.command.install_scripts import install_scripts
 from distutils.spawn import spawn, find_executable
 from distutils import file_util
 from distutils.errors import CCompilerError, DistutilsExecError
 from distutils.sysconfig import get_python_inc, get_config_var
 from distutils.version import StrictVersion
 
 convert2to3 = '--c2to3' in sys.argv
 if convert2to3:
     try:
         from distutils.command.build_py import build_py_2to3 as build_py
         from lib2to3.refactor import get_fixers_from_package as getfixers
     except ImportError:
         if sys.version_info[0] < 3:
             raise SystemExit("--c2to3 is only compatible with python3.")
         raise
     sys.path.append('contrib')
 elif sys.version_info[0] >= 3:
     raise SystemExit("setup.py with python3 needs --c2to3 (experimental)")
 
 scripts = ['hg']
 if os.name == 'nt':
     scripts.append('contrib/win32/hg.bat')
 
 # simplified version of distutils.ccompiler.CCompiler.has_function
 # that actually removes its temporary files.
 def hasfunction(cc, funcname):
     tmpdir = tempfile.mkdtemp(prefix='hg-install-')
     devnull = oldstderr = None
     try:
         try:
             fname = os.path.join(tmpdir, 'funcname.c')
             f = open(fname, 'w')
             f.write('int main(void) {\n')
             f.write('    %s();\n' % funcname)
             f.write('}\n')
             f.close()
             # Redirect stderr to /dev/null to hide any error messages
             # from the compiler.
             # This will have to be changed if we ever have to check
             # for a function on Windows.
             devnull = open('/dev/null', 'w')
             oldstderr = os.dup(sys.stderr.fileno())
             os.dup2(devnull.fileno(), sys.stderr.fileno())
             objects = cc.compile([fname], output_dir=tmpdir)
             cc.link_executable(objects, os.path.join(tmpdir, "a.out"))
         except Exception:
             return False
         return True
     finally:
         if oldstderr is not None:
             os.dup2(oldstderr, sys.stderr.fileno())
         if devnull is not None:
             devnull.close()
         shutil.rmtree(tmpdir)
 
 # py2exe needs to be installed to work
 try:
     import py2exe
     py2exe.Distribution # silence unused import warning
     py2exeloaded = True
     # import py2exe's patched Distribution class
     from distutils.core import Distribution
 except ImportError:
     py2exeloaded = False
 
 def runcmd(cmd, env):
     if (sys.platform == 'plan9'
        and (sys.version_info[0] == 2 and sys.version_info[1] < 7)):
         # subprocess kludge to work around issues in half-baked Python
         # ports, notably bichued/python:
         _, out, err = os.popen3(cmd)
         return str(out), str(err)
     else:
         p = subprocess.Popen(cmd, stdout=subprocess.PIPE,
                              stderr=subprocess.PIPE, env=env)
         out, err = p.communicate()
         return out, err
 
 def runhg(cmd, env):
     out, err = runcmd(cmd, env)
     # If root is executing setup.py, but the repository is owned by
     # another user (as in "sudo python setup.py install") we will get
     # trust warnings since the .hg/hgrc file is untrusted. That is
     # fine, we don't want to load it anyway.  Python may warn about
     # a missing __init__.py in mercurial/locale, we also ignore that.
     err = [e for e in err.splitlines()
            if not e.startswith(b('not trusting file')) \
               and not e.startswith(b('warning: Not importing')) \
               and not e.startswith(b('obsolete feature not enabled'))]
     if err:
         printf("stderr from '%s':" % (' '.join(cmd)), file=sys.stderr)
         printf(b('\n').join([b('  ') + e for e in err]), file=sys.stderr)
         return ''
     return out
 
 version = ''
 
 # Execute hg out of this directory with a custom environment which
 # includes the pure Python modules in mercurial/pure. We also take
 # care to not use any hgrc files and do no localization.
 pypath = ['mercurial', os.path.join('mercurial', 'pure')]
 env = {'PYTHONPATH': os.pathsep.join(pypath),
        'HGRCPATH': '',
        'LANGUAGE': 'C'}
 if 'LD_LIBRARY_PATH' in os.environ:
     env['LD_LIBRARY_PATH'] = os.environ['LD_LIBRARY_PATH']
 if 'SystemRoot' in os.environ:
     # Copy SystemRoot into the custom environment for Python 2.6
     # under Windows. Otherwise, the subprocess will fail with
     # error 0xc0150004. See: http://bugs.python.org/issue3440
     env['SystemRoot'] = os.environ['SystemRoot']
 
 if os.path.isdir('.hg'):
     cmd = [sys.executable, 'hg', 'log', '-r', '.', '--template', '{tags}\n']
     numerictags = [t for t in runhg(cmd, env).split() if t[0].isdigit()]
     hgid = runhg([sys.executable, 'hg', 'id', '-i'], env).strip()
     if numerictags: # tag(s) found
         version = numerictags[-1]
         if hgid.endswith('+'): # propagate the dirty status to the tag
             version += '+'
     else: # no tag found
         ltagcmd = [sys.executable, 'hg', 'parents', '--template',
                    '{latesttag}']
         ltag = runhg(ltagcmd, env)
         changessincecmd = [sys.executable, 'hg', 'log', '-T', 'x\n', '-r',
                            "only(.,'%s')" % ltag]
         changessince = len(runhg(changessincecmd, env).splitlines())
         version = '%s+%s-%s' % (ltag, changessince, hgid)
     if version.endswith('+'):
         version += time.strftime('%Y%m%d')
 elif os.path.exists('.hg_archival.txt'):
     kw = dict([[t.strip() for t in l.split(':', 1)]
                for l in open('.hg_archival.txt')])
     if 'tag' in kw:
         version =  kw['tag']
     elif 'latesttag' in kw:
         if 'changessincelatesttag' in kw:
             version = '%(latesttag)s+%(changessincelatesttag)s-%(node).12s' % kw
         else:
             version = '%(latesttag)s+%(latesttagdistance)s-%(node).12s' % kw
     else:
         version = kw.get('node', '')[:12]
 
 if version:
     f = open("mercurial/__version__.py", "w")
     f.write('# this file is autogenerated by setup.py\n')
     f.write('version = "%s"\n' % version)
     f.close()
 
 
 try:
     from mercurial import __version__
     version = __version__.version
 except ImportError:
     version = 'unknown'
 
 class hgbuild(build):
     # Insert hgbuildmo first so that files in mercurial/locale/ are found
     # when build_py is run next.
     sub_commands = [('build_mo', None),
 
     # We also need build_ext before build_py. Otherwise, when 2to3 is
     # called (in build_py), it will not find osutil & friends,
     # thinking that those modules are global and, consequently, making
     # a mess, now that all module imports are global.
 
                     ('build_ext', build.has_ext_modules),
                    ] + build.sub_commands
 
 class hgbuildmo(build):
 
     description = "build translations (.mo files)"
 
     def run(self):
         if not find_executable('msgfmt'):
             self.warn("could not find msgfmt executable, no translations "
                      "will be built")
             return
 
         podir = 'i18n'
         if not os.path.isdir(podir):
             self.warn("could not find %s/ directory" % podir)
             return
 
         join = os.path.join
         for po in os.listdir(podir):
             if not po.endswith('.po'):
                 continue
             pofile = join(podir, po)
             modir = join('locale', po[:-3], 'LC_MESSAGES')
             mofile = join(modir, 'hg.mo')
             mobuildfile = join('mercurial', mofile)
             cmd = ['msgfmt', '-v', '-o', mobuildfile, pofile]
             if sys.platform != 'sunos5':
                 # msgfmt on Solaris does not know about -c
                 cmd.append('-c')
             self.mkpath(join('mercurial', modir))
             self.make_file([pofile], mobuildfile, spawn, (cmd,))
 
 
 class hgdist(Distribution):
     pure = ispypy
 
     global_options = Distribution.global_options + \
                      [('pure', None, "use pure (slow) Python "
                         "code instead of C extensions"),
                       ('c2to3', None, "(experimental!) convert "
                         "code with 2to3"),
                      ]
 
     def has_ext_modules(self):
         # self.ext_modules is emptied in hgbuildpy.finalize_options which is
         # too late for some cases
         return not self.pure and Distribution.has_ext_modules(self)
 
 class hgbuildext(build_ext):
 
     def build_extension(self, ext):
         try:
             build_ext.build_extension(self, ext)
         except CCompilerError:
             if not getattr(ext, 'optional', False):
                 raise
             log.warn("Failed to build optional extension '%s' (skipping)",
                      ext.name)
 
 class hgbuildpy(build_py):
     if convert2to3:
         fixer_names = sorted(set(getfixers("lib2to3.fixes") +
                                  getfixers("hgfixes")))
 
     def finalize_options(self):
         build_py.finalize_options(self)
 
         if self.distribution.pure:
             if self.py_modules is None:
                 self.py_modules = []
             for ext in self.distribution.ext_modules:
                 if ext.name.startswith("mercurial."):
                     self.py_modules.append("mercurial.pure.%s" % ext.name[10:])
             self.distribution.ext_modules = []
         else:
             h = os.path.join(get_python_inc(), 'Python.h')
             if not os.path.exists(h):
                 raise SystemExit('Python headers are required to build '
                                  'Mercurial but weren\'t found in %s' % h)
 
     def find_modules(self):
         modules = build_py.find_modules(self)
         for module in modules:
             if module[0] == "mercurial.pure":
                 if module[1] != "__init__":
                     yield ("mercurial", module[1], module[2])
             else:
                 yield module
 
 class buildhgextindex(Command):
     description = 'generate prebuilt index of hgext (for frozen package)'
     user_options = []
     _indexfilename = 'hgext/__index__.py'
 
     def initialize_options(self):
         pass
 
     def finalize_options(self):
         pass
 
     def run(self):
         if os.path.exists(self._indexfilename):
             f = open(self._indexfilename, 'w')
             f.write('# empty\n')
             f.close()
 
         # here no extension enabled, disabled() lists up everything
         code = ('import pprint; from mercurial import extensions; '
                 'pprint.pprint(extensions.disabled())')
         out, err = runcmd([sys.executable, '-c', code], env)
         if err:
             raise DistutilsExecError(err)
 
         f = open(self._indexfilename, 'w')
         f.write('# this file is autogenerated by setup.py\n')
         f.write('docs = ')
         f.write(out)
         f.close()
 
 class buildhgexe(build_ext):
     description = 'compile hg.exe from mercurial/exewrapper.c'
 
     def build_extensions(self):
         if os.name != 'nt':
             return
         if isinstance(self.compiler, HackedMingw32CCompiler):
             self.compiler.compiler_so = self.compiler.compiler # no -mdll
             self.compiler.dll_libraries = [] # no -lmsrvc90
         hv = sys.hexversion
         pythonlib = 'python%d%d' % (hv >> 24, (hv >> 16) & 0xff)
         f = open('mercurial/hgpythonlib.h', 'wb')
         f.write('/* this file is autogenerated by setup.py */\n')
         f.write('#define HGPYTHONLIB "%s"\n' % pythonlib)
         f.close()
         objects = self.compiler.compile(['mercurial/exewrapper.c'],
                                          output_dir=self.build_temp)
         dir = os.path.dirname(self.get_ext_fullpath('dummy'))
         target = os.path.join(dir, 'hg')
         self.compiler.link_executable(objects, target,
                                       libraries=[],
                                       output_dir=self.build_temp)
 
 class hginstalllib(install_lib):
     '''
     This is a specialization of install_lib that replaces the copy_file used
     there so that it supports setting the mode of files after copying them,
     instead of just preserving the mode that the files originally had.  If your
     system has a umask of something like 027, preserving the permissions when
     copying will lead to a broken install.
 
     Note that just passing keep_permissions=False to copy_file would be
     insufficient, as it might still be applying a umask.
     '''
 
     def run(self):
         realcopyfile = file_util.copy_file
         def copyfileandsetmode(*args, **kwargs):
             src, dst = args[0], args[1]
             dst, copied = realcopyfile(*args, **kwargs)
             if copied:
                 st = os.stat(src)
                 # Persist executable bit (apply it to group and other if user
                 # has it)
                 if st[stat.ST_MODE] & stat.S_IXUSR:
                     setmode = 0755
                 else:
                     setmode = 0644
                 os.chmod(dst, (stat.S_IMODE(st[stat.ST_MODE]) & ~0777) |
                          setmode)
         file_util.copy_file = copyfileandsetmode
         try:
             install_lib.run(self)
         finally:
             file_util.copy_file = realcopyfile
 
 class hginstallscripts(install_scripts):
     '''
     This is a specialization of install_scripts that replaces the @LIBDIR@ with
     the configured directory for modules. If possible, the path is made relative
     to the directory for scripts.
     '''
 
     def initialize_options(self):
         install_scripts.initialize_options(self)
 
         self.install_lib = None
 
     def finalize_options(self):
         install_scripts.finalize_options(self)
         self.set_undefined_options('install',
                                    ('install_lib', 'install_lib'))
 
     def run(self):
         install_scripts.run(self)
 
         if (os.path.splitdrive(self.install_dir)[0] !=
             os.path.splitdrive(self.install_lib)[0]):
             # can't make relative paths from one drive to another, so use an
             # absolute path instead
             libdir = self.install_lib
         else:
             common = os.path.commonprefix((self.install_dir, self.install_lib))
             rest = self.install_dir[len(common):]
             uplevel = len([n for n in os.path.split(rest) if n])
 
             libdir =  uplevel * ('..' + os.sep) + self.install_lib[len(common):]
 
         for outfile in self.outfiles:
             fp = open(outfile, 'rb')
             data = fp.read()
             fp.close()
 
             # skip binary files
             if b('\0') in data:
                 continue
 
             data = data.replace(b('@LIBDIR@'), libdir.encode(libdir_escape))
             fp = open(outfile, 'wb')
             fp.write(data)
             fp.close()
 
 cmdclass = {'build': hgbuild,
             'build_mo': hgbuildmo,
             'build_ext': hgbuildext,
             'build_py': hgbuildpy,
             'build_hgextindex': buildhgextindex,
             'install_lib': hginstalllib,
             'install_scripts': hginstallscripts,
             'build_hgexe': buildhgexe,
             }
 
 packages = ['mercurial', 'mercurial.hgweb', 'mercurial.httpclient',
             'hgext', 'hgext.convert', 'hgext.highlight', 'hgext.zeroconf',
             'hgext.largefiles']
 
 pymodules = []
 
 common_depends = ['mercurial/util.h']
 
 extmodules = [
     Extension('mercurial.base85', ['mercurial/base85.c'],
               depends=common_depends),
     Extension('mercurial.bdiff', ['mercurial/bdiff.c'],
               depends=common_depends),
     Extension('mercurial.diffhelpers', ['mercurial/diffhelpers.c'],
               depends=common_depends),
     Extension('mercurial.mpatch', ['mercurial/mpatch.c'],
               depends=common_depends),
     Extension('mercurial.parsers', ['mercurial/dirs.c',
+                                    'mercurial/manifest.c',
                                     'mercurial/parsers.c',
                                     'mercurial/pathencode.c'],
               depends=common_depends),
     ]
 
 osutil_ldflags = []
 
 if sys.platform == 'darwin':
     osutil_ldflags += ['-framework', 'ApplicationServices']
 
 # disable osutil.c under windows + python 2.4 (issue1364)
 if sys.platform == 'win32' and sys.version_info < (2, 5, 0, 'final'):
     pymodules.append('mercurial.pure.osutil')
 else:
     extmodules.append(Extension('mercurial.osutil', ['mercurial/osutil.c'],
                                 extra_link_args=osutil_ldflags,
                                 depends=common_depends))
 
 try:
     from distutils import cygwinccompiler
 
     # the -mno-cygwin option has been deprecated for years
     compiler = cygwinccompiler.Mingw32CCompiler
 
     class HackedMingw32CCompiler(cygwinccompiler.Mingw32CCompiler):
         def __init__(self, *args, **kwargs):
             compiler.__init__(self, *args, **kwargs)
             for i in 'compiler compiler_so linker_exe linker_so'.split():
                 try:
                     getattr(self, i).remove('-mno-cygwin')
                 except ValueError:
                     pass
 
     cygwinccompiler.Mingw32CCompiler = HackedMingw32CCompiler
 except ImportError:
     # the cygwinccompiler package is not available on some Python
     # distributions like the ones from the optware project for Synology
     # DiskStation boxes
     class HackedMingw32CCompiler(object):
         pass
 
 packagedata = {'mercurial': ['locale/*/LC_MESSAGES/hg.mo',
                              'help/*.txt',
                              'default.d/*.rc',
                              'dummycert.pem']}
 
 def ordinarypath(p):
     return p and p[0] != '.' and p[-1] != '~'
 
 for root in ('templates',):
     for curdir, dirs, files in os.walk(os.path.join('mercurial', root)):
         curdir = curdir.split(os.sep, 1)[1]
         dirs[:] = filter(ordinarypath, dirs)
         for f in filter(ordinarypath, files):
             f = os.path.join(curdir, f)
             packagedata['mercurial'].append(f)
 
 datafiles = []
 setupversion = version
 extra = {}
 
 if py2exeloaded:
     extra['console'] = [
         {'script':'hg',
          'copyright':'Copyright (C) 2005-2015 Matt Mackall and others',
          'product_version':version}]
     # sub command of 'build' because 'py2exe' does not handle sub_commands
     build.sub_commands.insert(0, ('build_hgextindex', None))
 
 if os.name == 'nt':
     # Windows binary file versions for exe/dll files must have the
     # form W.X.Y.Z, where W,X,Y,Z are numbers in the range 0..65535
     setupversion = version.split('+', 1)[0]
 
 if sys.platform == 'darwin' and os.path.exists('/usr/bin/xcodebuild'):
     version = runcmd(['/usr/bin/xcodebuild', '-version'], {})[0].splitlines()
     if version:
         version = version[0]
         xcode4 = (version.startswith('Xcode') and
                   StrictVersion(version.split()[1]) >= StrictVersion('4.0'))
         xcode51 = re.match(r'^Xcode\s+5\.1', version) is not None
     else:
         # xcodebuild returns empty on OS X Lion with XCode 4.3 not
         # installed, but instead with only command-line tools. Assume
         # that only happens on >= Lion, thus no PPC support.
         xcode4 = True
         xcode51 = False
 
     # XCode 4.0 dropped support for ppc architecture, which is hardcoded in
     # distutils.sysconfig
     if xcode4:
         os.environ['ARCHFLAGS'] = ''
 
     # XCode 5.1 changes clang such that it now fails to compile if the
     # -mno-fused-madd flag is passed, but the version of Python shipped with
     # OS X 10.9 Mavericks includes this flag. This causes problems in all
     # C extension modules, and a bug has been filed upstream at
     # http://bugs.python.org/issue21244. We also need to patch this here
     # so Mercurial can continue to compile in the meantime.
     if xcode51:
         cflags = get_config_var('CFLAGS')
         if cflags and re.search(r'-mno-fused-madd\b', cflags) is not None:
             os.environ['CFLAGS'] = (
                 os.environ.get('CFLAGS', '') + ' -Qunused-arguments')
 
 setup(name='mercurial',
       version=setupversion,
       author='Matt Mackall and many others',
       author_email='[e-mail]',
       url='http://mercurial.selenic.com/',
       download_url='http://mercurial.selenic.com/release/',
       description=('Fast scalable distributed SCM (revision control, version '
                    'control) system'),
       long_description=('Mercurial is a distributed SCM tool written in Python.'
                         ' It is used by a number of large projects that require'
                         ' fast, reliable distributed revision control, such as '
                         'Mozilla.'),
       license='GNU GPLv2 or any later version',
       classifiers=[
           'Development Status :: 6 - Mature',
           'Environment :: Console',
           'Intended Audience :: Developers',
           'Intended Audience :: System Administrators',
           'License :: OSI Approved :: GNU General Public License (GPL)',
           'Natural Language :: Danish',
           'Natural Language :: English',
           'Natural Language :: German',
           'Natural Language :: Italian',
           'Natural Language :: Japanese',
           'Natural Language :: Portuguese (Brazilian)',
           'Operating System :: Microsoft :: Windows',
           'Operating System :: OS Independent',
           'Operating System :: POSIX',
           'Programming Language :: C',
           'Programming Language :: Python',
           'Topic :: Software Development :: Version Control',
       ],
       scripts=scripts,
       packages=packages,
       py_modules=pymodules,
       ext_modules=extmodules,
       data_files=datafiles,
       package_data=packagedata,
       cmdclass=cmdclass,
       distclass=hgdist,
       options={'py2exe': {'packages': ['hgext', 'email']},
                'bdist_mpkg': {'zipdist': False,
                               'license': 'COPYING',
                               'readme': 'contrib/macosx/Readme.html',
                               'welcome': 'contrib/macosx/Welcome.html',
                               },
                },
       **extra)