parsers: incrementally parse the revlog index in C

We only parse entries in a revlog index file when they are actually
needed, and cache them when first requested.

This makes a huge difference to performance on large revlogs when
accessing the tip revision or performing a handful of numeric lookups
(very common cases).  For instance, "hg --time tip --template {node}"
on a tree with 300,000 revs takes 0.15 before, 0.02 after.

Even for revlog-intensive operations (e.g. running "hg log" to
completion), the lazy approach is about 1% faster than the eager
parse_index2.

mercurial/parsers.c

@@ -1,418 +1,720 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 <string.h>
 
 #include "util.h"
 
 static int hexdigit(char c)
 {
 	if (c >= '0' && c <= '9')
 		return c - '0';
 	if (c >= 'a' && c <= 'f')
 		return c - 'a' + 10;
 	if (c >= 'A' && c <= 'F')
 		return c - 'A' + 10;
 
 	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 *ret;
 	const char *c;
 	char *d;
 
 	ret = PyBytes_FromStringAndSize(NULL, len / 2);
 
 	if (!ret)
 		return NULL;
 
 	d = PyBytes_AsString(ret);
 
 	for (c = str; c < str + len;) {
 		int hi = hexdigit(*c++);
 		int lo = hexdigit(*c++);
 		*d++ = (hi << 4) | lo;
 	}
 
 	return ret;
 }
 
 /*
  * 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, *cur, *start, *zero;
 	int len;
 
 	if (!PyArg_ParseTuple(args, "O!O!s#:parse_manifest",
 			      &PyDict_Type, &mfdict,
 			      &PyDict_Type, &fdict,
 			      &str, &len))
 		goto quit;
 
 	for (start = cur = str, zero = NULL; cur < str + len; cur++) {
 		PyObject *file = NULL, *node = NULL;
 		PyObject *flags = NULL;
 		int nlen;
 
 		if (!*cur) {
 			zero = cur;
 			continue;
 		}
 		else if (*cur != '\n')
 			continue;
 
 		if (!zero) {
 			PyErr_SetString(PyExc_ValueError,
 					"manifest entry has no separator");
 			goto quit;
 		}
 
 		file = PyBytes_FromStringAndSize(start, zero - start);
 
 		if (!file)
 			goto bail;
 
 		nlen = cur - zero - 1;
 
 		node = unhexlify(zero + 1, nlen > 40 ? 40 : 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 = cur + 1;
 		zero = NULL;
 
 		Py_XDECREF(flags);
 		Py_XDECREF(node);
 		Py_XDECREF(file);
 		continue;
 	bail:
 		Py_XDECREF(flags);
 		Py_XDECREF(node);
 		Py_XDECREF(file);
 		goto quit;
 	}
 
 	if (len > 0 && *(cur - 1) != '\n') {
 		PyErr_SetString(PyExc_ValueError,
 				"manifest contains trailing garbage");
 		goto quit;
 	}
 
 	Py_INCREF(Py_None);
 	return Py_None;
 quit:
 	return NULL;
 }
 
 #ifdef _WIN32
 #ifdef _MSC_VER
 /* msvc 6.0 has problems */
 #define inline __inline
 typedef unsigned long uint32_t;
 typedef unsigned __int64 uint64_t;
 #else
 #include <stdint.h>
 #endif
 static uint32_t ntohl(uint32_t x)
 {
 	return ((x & 0x000000ffUL) << 24) |
 	       ((x & 0x0000ff00UL) <<  8) |
 	       ((x & 0x00ff0000UL) >>  8) |
 	       ((x & 0xff000000UL) >> 24);
 }
 #else
 /* not windows */
 #include <sys/types.h>
 #if defined __BEOS__ && !defined __HAIKU__
 #include <ByteOrder.h>
 #else
 #include <arpa/inet.h>
 #endif
 #include <inttypes.h>
 #endif
 
 static PyObject *parse_dirstate(PyObject *self, PyObject *args)
 {
 	PyObject *dmap, *cmap, *parents = NULL, *ret = NULL;
 	PyObject *fname = NULL, *cname = NULL, *entry = NULL;
 	char *str, *cur, *end, *cpos;
 	int state, mode, size, mtime;
 	unsigned int flen;
 	int len;
 	uint32_t decode[4]; /* for alignment */
 
 	if (!PyArg_ParseTuple(args, "O!O!s#:parse_dirstate",
 			      &PyDict_Type, &dmap,
 			      &PyDict_Type, &cmap,
 			      &str, &len))
 		goto quit;
 
 	/* read parents */
 	if (len < 40)
 		goto quit;
 
 	parents = Py_BuildValue("s#s#", str, 20, str + 20, 20);
 	if (!parents)
 		goto quit;
 
 	/* read filenames */
 	cur = str + 40;
 	end = str + len;
 
 	while (cur < end - 17) {
 		/* unpack header */
 		state = *cur;
 		memcpy(decode, cur + 1, 16);
 		mode = ntohl(decode[0]);
 		size = ntohl(decode[1]);
 		mtime = ntohl(decode[2]);
 		flen = ntohl(decode[3]);
 		cur += 17;
 		if (cur + flen > end || cur + flen < cur) {
 			PyErr_SetString(PyExc_ValueError, "overflow in dirstate");
 			goto quit;
 		}
 
 		entry = Py_BuildValue("ciii", state, mode, size, mtime);
 		if (!entry)
 			goto quit;
 		PyObject_GC_UnTrack(entry); /* don't waste time with this */
 
 		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;
 		}
 		cur += flen;
 		Py_DECREF(fname);
 		Py_DECREF(entry);
 		fname = cname = entry = NULL;
 	}
 
 	ret = parents;
 	Py_INCREF(ret);
 quit:
 	Py_XDECREF(fname);
 	Py_XDECREF(cname);
 	Py_XDECREF(entry);
 	Py_XDECREF(parents);
 	return ret;
 }
 
-const char nullid[20];
-const int nullrev = -1;
+/*
+ * A list-like object that decodes the contents of a RevlogNG index
+ * file on demand. It has limited support for insert and delete at the
+ * last element before the end.  The last entry is always a sentinel
+ * nullid.
+ */
+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 */
+	int inlined;
+} indexObject;
+
+static Py_ssize_t index_length(indexObject *self)
+{
+	if (self->added == NULL)
+		return self->length;
+	return self->length + PyList_GET_SIZE(self->added);
+}
+
+static PyObject *nullentry;
+
+static long inline_scan(indexObject *self, const char **offsets);
+
+#if LONG_MAX == 0x7fffffffL
+static const char *tuple_format = "Kiiiiiis#";
+#else
+static const char *tuple_format = "kiiiiiis#";
+#endif
 
 /* 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 int _parse_index_ng(const char *data, int size, int inlined,
-			   PyObject *index)
+static PyObject *index_get(indexObject *self, Py_ssize_t pos)
 {
-	PyObject *entry;
-	int n = 0, err;
+	uint32_t decode[8]; /* to enforce alignment with inline data */
 	uint64_t offset_flags;
 	int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;
 	const char *c_node_id;
-	const char *end = data + size;
-	uint32_t decode[8]; /* to enforce alignment with inline data */
+	const char *data;
+	Py_ssize_t length = index_length(self);
+	PyObject *entry;
+
+	if (pos >= length) {
+		PyErr_SetString(PyExc_IndexError, "revlog index out of range");
+		return NULL;
+	}
+
+	if (pos == length - 1) {
+		Py_INCREF(nullentry);
+		return nullentry;
+	}
 
-	while (data < end) {
-		unsigned int step;
+	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();
+	}
 
-		memcpy(decode, data, 32);
-		offset_flags = ntohl(decode[1]);
-		if (n == 0) /* mask out version number for the first entry */
-			offset_flags &= 0xFFFF;
-		else {
-			uint32_t offset_high =  ntohl(decode[0]);
-			offset_flags |= ((uint64_t)offset_high) << 32;
+	if (self->inlined && pos > 0) {
+		if (self->offsets == NULL) {
+			self->offsets = malloc(self->raw_length *
+					       sizeof(*self->offsets));
+			if (self->offsets == NULL)
+				return PyErr_NoMemory();
+			inline_scan(self, self->offsets);
 		}
+		data = self->offsets[pos];
+	} else
+		data = PyString_AS_STRING(self->data) + pos * 64;
+
+	memcpy(decode, data, 8 * sizeof(uint32_t));
 
-		comp_len = ntohl(decode[2]);
-		uncomp_len = ntohl(decode[3]);
-		base_rev = ntohl(decode[4]);
-		link_rev = ntohl(decode[5]);
-		parent_1 = ntohl(decode[6]);
-		parent_2 = ntohl(decode[7]);
-		c_node_id = data + 32;
+	offset_flags = ntohl(decode[1]);
+	if (pos == 0) /* mask out version number for the first entry */
+		offset_flags &= 0xFFFF;
+	else {
+		uint32_t offset_high = ntohl(decode[0]);
+		offset_flags |= ((uint64_t)offset_high) << 32;
+	}
 
-		entry = Py_BuildValue("Liiiiiis#", offset_flags, comp_len,
+	comp_len = ntohl(decode[2]);
+	uncomp_len = ntohl(decode[3]);
+	base_rev = ntohl(decode[4]);
+	link_rev = ntohl(decode[5]);
+	parent_1 = ntohl(decode[6]);
+	parent_2 = ntohl(decode[7]);
+	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)
-			return 0;
+	if (entry)
+		PyObject_GC_UnTrack(entry);
+
+	self->cache[pos] = entry;
+	Py_INCREF(entry);
+
+	return entry;
+}
+
+static PyObject *index_insert(indexObject *self, PyObject *args)
+{
+	PyObject *obj, *node;
+	long offset;
+	Py_ssize_t len;
+
+	if (!PyArg_ParseTuple(args, "lO", &offset, &obj))
+		return NULL;
+
+	if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) {
+		PyErr_SetString(PyExc_ValueError, "8-tuple required");
+		return NULL;
+	}
 
-		PyObject_GC_UnTrack(entry); /* don't waste time with this */
+	node = PyTuple_GET_ITEM(obj, 7);
+	if (!PyString_Check(node) || PyString_GET_SIZE(node) != 20) {
+		PyErr_SetString(PyExc_ValueError,
+				"20-byte hash required as last element");
+		return NULL;
+	}
+
+	len = index_length(self);
+
+	if (offset < 0)
+		offset += len;
+
+	if (offset != 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 (inlined) {
-			err = PyList_Append(index, entry);
-			Py_DECREF(entry);
-			if (err)
-				return 0;
-		} else
-			PyList_SET_ITEM(index, n, entry); /* steals reference */
+	Py_RETURN_NONE;
+}
+
+static int index_assign_subscript(indexObject *self, PyObject *item,
+				  PyObject *value)
+{
+	Py_ssize_t start, stop, step, slicelength;
+	Py_ssize_t length = index_length(self);
+
+	if (!PySlice_Check(item) || value != NULL) {
+		PyErr_SetString(PyExc_TypeError,
+				"revlog index only supports slice deletion");
+		return -1;
+	}
+
+	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;
 
-		n++;
-		step = 64 + (inlined ? comp_len : 0);
-		if (data + step > end || data + step < data)
-			break;
-		data += step;
+	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 (data != end) {
-		if (!PyErr_Occurred())
-			PyErr_SetString(PyExc_ValueError, "corrupt index file");
+
+	if (stop != length - 1) {
+		PyErr_SetString(PyExc_IndexError,
+				"revlog index deletion indices are invalid");
+		return -1;
+	}
+
+	if (start < self->length) {
+		self->length = start + 1;
+		if (self->added) {
+			Py_DECREF(self->added);
+			self->added = NULL;
+		}
 		return 0;
 	}
 
-	/* create the magic nullid entry in the index at [-1] */
-	entry = Py_BuildValue("Liiiiiis#", (uint64_t)0, 0, 0, -1, -1, -1, -1, nullid, 20);
+	return PyList_SetSlice(self->added, start - self->length + 1,
+			       PyList_GET_SIZE(self->added),
+			       NULL);
+}
+
+static long inline_scan(indexObject *self, const char **offsets)
+{
+	const char *data = PyString_AS_STRING(self->data);
+	const char *end = data + PyString_GET_SIZE(self->data);
+	const long hdrsize = 64;
+	long incr = hdrsize;
+	Py_ssize_t len = 0;
 
-	if (!entry)
-		return 0;
+	while (data + hdrsize <= end) {
+		uint32_t comp_len;
+		const char *old_data;
+		/* 3rd element of header is length of compressed inline data */
+		memcpy(&comp_len, data + 8, sizeof(uint32_t));
+		incr = hdrsize + ntohl(comp_len);
+		if (incr < hdrsize)
+			break;
+		if (offsets)
+			offsets[len] = data;
+		len++;
+		old_data = data;
+		data += incr;
+		if (data <= old_data)
+			break;
+	}
 
-	PyObject_GC_UnTrack(entry); /* don't waste time with this */
+	if (data != end && data + hdrsize != end) {
+		if (!PyErr_Occurred())
+			PyErr_SetString(PyExc_ValueError, "corrupt index file");
+		return -1;
+	}
+
+	return len;
+}
 
-	if (inlined) {
-		err = PyList_Append(index, entry);
-		Py_DECREF(entry);
-		if (err)
-			return 0;
-	} else
-		PyList_SET_ITEM(index, n, entry); /* steals reference */
+static int index_real_init(indexObject *self, const char *data, int size,
+			   PyObject *inlined_obj, PyObject *data_obj)
+{
+	self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
+	self->data = data_obj;
+	self->cache = NULL;
+
+	self->added = NULL;
+	self->offsets = NULL;
+	Py_INCREF(self->data);
 
-	return 1;
+	if (self->inlined) {
+		long len = inline_scan(self, NULL);
+		if (len == -1)
+			goto bail;
+		self->raw_length = len;
+		self->length = len + 1;
+	} else {
+		if (size % 64) {
+			PyErr_SetString(PyExc_ValueError, "corrupt index file");
+			goto bail;
+		}
+		self->raw_length = size / 64;
+		self->length = self->raw_length + 1;
+	}
+
+	return 0;
+bail:
+	return -1;
+}
+
+static int index_init(indexObject *self, PyObject *args, PyObject *kwds)
+{
+	const char *data;
+	int size;
+	PyObject *inlined_obj;
+
+	if (!PyArg_ParseTuple(args, "s#O", &data, &size, &inlined_obj))
+		return -1;
+
+	return index_real_init(self, data, size, inlined_obj,
+			       PyTuple_GET_ITEM(args, 0));
 }
 
-/* This function parses a index file and returns a Python tuple of the
- * following format: (index, cache)
+static void index_dealloc(indexObject *self)
+{
+	Py_DECREF(self->data);
+	if (self->cache) {
+		Py_ssize_t i;
+
+		for (i = 0; i < self->raw_length; i++)
+			Py_XDECREF(self->cache[i]);
+	}
+	Py_XDECREF(self->added);
+	free(self->offsets);
+	PyObject_Del(self);
+}
+
+static PySequenceMethods index_sequence_methods = {
+	(lenfunc)index_length,   /* sq_length */
+	0,                       /* sq_concat */
+	0,                       /* sq_repeat */
+	(ssizeargfunc)index_get, /* sq_item */
+};
+
+static PyMappingMethods index_mapping_methods = {
+	(lenfunc)index_length,                 /* mp_length */
+	NULL,                                  /* mp_subscript */
+	(objobjargproc)index_assign_subscript, /* mp_ass_subscript */
+};
+
+static PyMethodDef index_methods[] = {
+	{"insert", (PyCFunction)index_insert, METH_VARARGS,
+	 "insert an index entry"},
+	{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 */
+	0,                         /* 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 */
+	PyType_GenericNew,         /* tp_new */
+};
+
+/*
+ * returns a tuple of the form (index, None, cache) with elements as
+ * follows:
  *
- * index: a list of tuples containing the RevlogNG records
- * cache: if data is inlined, a tuple (index_file_content, 0) else None
+ * index: an index object that lazily parses the 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)
 {
 	const char *data;
-	int size, inlined;
-	PyObject *rval = NULL, *index = NULL, *cache = NULL;
-	PyObject *data_obj = NULL, *inlined_obj;
+	int size, ret;
+	PyObject *inlined_obj, *tuple = NULL, *cache = NULL;
+	indexObject *idx;
 
 	if (!PyArg_ParseTuple(args, "s#O", &data, &size, &inlined_obj))
 		return NULL;
-	inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
+
+	idx = PyObject_New(indexObject, &indexType);
+
+	if (idx == NULL)
+		goto bail;
 
-	/* If no data is inlined, we know the size of the index list in
-	 * advance: size divided by the size of one revlog record (64 bytes)
-	 * plus one for nullid */
-	index = inlined ? PyList_New(0) : PyList_New(size / 64 + 1);
-	if (!index)
-		goto quit;
+	ret = index_real_init(idx, data, size, inlined_obj,
+			      PyTuple_GET_ITEM(args, 0));
+	if (ret)
+		goto bail;
 
-	/* set up the cache return value */
-	if (inlined) {
-		/* Note that the reference to data_obj is only borrowed */
-		data_obj = PyTuple_GET_ITEM(args, 0);
-		cache = Py_BuildValue("iO", 0, data_obj);
-		if (!cache)
-			goto quit;
+	if (idx->inlined) {
+		Py_INCREF(idx->data);
+		cache = Py_BuildValue("iO", 0, idx->data);
+		if (cache == NULL)
+			goto bail;
 	} else {
 		cache = Py_None;
-		Py_INCREF(Py_None);
+		Py_INCREF(cache);
 	}
 
-	/* actually populate the index with data */
-	if (!_parse_index_ng(data, size, inlined, index))
-		goto quit;
+	tuple = Py_BuildValue("NN", idx, cache);
+	if (!tuple)
+		goto bail;
+	return tuple;
 
-	rval = Py_BuildValue("NN", index, cache);
-	if (!rval)
-		goto quit;
-	return rval;
-
-quit:
-	Py_XDECREF(index);
+bail:
+	Py_XDECREF(idx);
 	Py_XDECREF(cache);
-	Py_XDECREF(rval);
+	Py_XDECREF(tuple);
 	return NULL;
 }
 
-
 static char parsers_doc[] = "Efficient content parsing.";
 
 static PyMethodDef methods[] = {
 	{"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"},
 	{NULL, NULL}
 };
 
+static void module_init(PyObject *mod)
+{
+	static const char nullid[20];
+
+	if (PyType_Ready(&indexType) < 0)
+		return;
+	Py_INCREF(&indexType);
+
+	PyModule_AddObject(mod, "index", (PyObject *)&indexType);
+
+	nullentry = Py_BuildValue("iiiiiiis#", 0, 0, 0,
+				  -1, -1, -1, -1, nullid, 20);
+	if (nullentry)
+		PyObject_GC_UnTrack(nullentry);
+}
+
 #ifdef IS_PY3K
 static struct PyModuleDef parsers_module = {
 	PyModuleDef_HEAD_INIT,
 	"parsers",
 	parsers_doc,
 	-1,
 	methods
 };
 
 PyMODINIT_FUNC PyInit_parsers(void)
 {
-	return PyModule_Create(&parsers_module);
+	PyObject *mod = PyModule_Create(&parsers_module);
+	module_init(mod);
+	return mod;
 }
 #else
 PyMODINIT_FUNC initparsers(void)
 {
-	Py_InitModule3("parsers", methods, parsers_doc);
+	PyObject *mod = Py_InitModule3("parsers", methods, parsers_doc);
+	module_init(mod);
 }
 #endif
 

tests/test-parseindex2.py

@@ -1,113 +1,115 b''
 from mercurial import parsers
 from mercurial.node import nullid, nullrev
 import struct
 
 # This unit test compares the return value of the original Python
 # implementation of parseindex and the new C implementation for
 # an index file with and without inlined data
 
 # original python implementation
 def gettype(q):
     return int(q & 0xFFFF)
 
 def offset_type(offset, type):
     return long(long(offset) << 16 | type)
 
 indexformatng = ">Qiiiiii20s12x"
 
 def py_parseindex(data, inline) :
     s = 64
     cache = None
     index = []
     nodemap =  {nullid: nullrev}
     n = off = 0
 
     l = len(data) - s
     append = index.append
     if inline:
         cache = (0, data)
         while off <= l:
             e = struct.unpack(indexformatng, data[off:off + s])
             nodemap[e[7]] = n
             append(e)
             n += 1
             if e[1] < 0:
                 break
             off += e[1] + s
     else:
         while off <= l:
             e = struct.unpack(indexformatng, data[off:off + s])
             nodemap[e[7]] = n
             append(e)
             n += 1
             off += s
 
     e = list(index[0])
     type = gettype(e[0])
     e[0] = offset_type(0, type)
     index[0] = tuple(e)
 
     # add the magic null revision at -1
     index.append((0, 0, 0, -1, -1, -1, -1, nullid))
 
     return index, cache
 
-
 data_inlined = '\x00\x01\x00\x01\x00\x00\x00\x00\x00\x00\x01\x8c' \
     '\x00\x00\x04\x07\x00\x00\x00\x00\x00\x00\x15\x15\xff\xff\xff' \
     '\xff\xff\xff\xff\xff\xebG\x97\xb7\x1fB\x04\xcf\x13V\x81\tw\x1b' \
     'w\xdduR\xda\xc6\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00' \
     'x\x9c\x9d\x93?O\xc30\x10\xc5\xf7|\x8a\xdb\x9a\xa8m\x06\xd8*\x95' \
     '\x81B\xa1\xa2\xa2R\xcb\x86Pd\x9a\x0b5$vd_\x04\xfd\xf6\x9c\xff@' \
     '\x11!\x0b\xd9\xec\xf7\xbbw\xe7gG6\xad6\x04\xdaN\xc0\x92\xa0$)' \
     '\xb1\x82\xa2\xd1%\x16\xa4\x8b7\xa9\xca\xd4-\xb2Y\x02\xfc\xc9' \
     '\xcaS\xf9\xaeX\xed\xb6\xd77Q\x02\x83\xd4\x19\xf5--Y\xea\xe1W' \
     '\xab\xed\x10\xceR\x0f_\xdf\xdf\r\xe1,\xf5\xf0\xcb\xf5 \xceR\x0f' \
     '_\xdc\x0e\x0e\xc3R\x0f_\xae\x96\x9b!\x9e\xa5\x1e\xbf\xdb,\x06' \
     '\xc7q\x9a/\x88\x82\xc3B\xea\xb5\xb4TJ\x93\xb6\x82\x0e\xe16\xe6' \
     'KQ\xdb\xaf\xecG\xa3\xd1 \x01\xd3\x0b_^\xe8\xaa\xa0\xae\xad\xd1' \
     '&\xbef\x1bz\x08\xb0|\xc9Xz\x06\xf6Z\x91\x90J\xaa\x17\x90\xaa' \
     '\xd2\xa6\x11$5C\xcf\xba#\xa0\x03\x02*2\x92-\xfc\xb1\x94\xdf\xe2' \
     '\xae\xb8\'m\x8ey0^\x85\xd3\x82\xb4\xf0`:\x9c\x00\x8a\xfd\x01' \
     '\xb0\xc6\x86\x8b\xdd\xae\x80\xf3\xa9\x9fd\x16\n\x00R%\x1a\x06' \
     '\xe9\xd8b\x98\x1d\xf4\xf3+\x9bf\x01\xd8p\x1b\xf3.\xed\x9f^g\xc3' \
     '^\xd9W81T\xdb\xd5\x04sx|\xf2\xeb\xd6`%?x\xed"\x831\xbf\xf3\xdc' \
     'b\xeb%gaY\xe1\xad\x9f\xb9f\'1w\xa9\xa5a\x83s\x82J\xb98\xbc4\x8b' \
     '\x83\x00\x9f$z\xb8#\xa5\xb1\xdf\x98\xd9\xec\x1b\x89O\xe3Ts\x9a4' \
     '\x17m\x8b\xfc\x8f\xa5\x95\x9a\xfc\xfa\xed,\xe5|\xa1\xfe\x15\xb9' \
     '\xbc\xb2\x93\x1f\xf2\x95\xff\xdf,\x1a\xc5\xe7\x17*\x93Oz:>\x0e'
 
 data_non_inlined = '\x00\x00\x00\x01\x00\x00\x00\x00\x00\x01D\x19' \
     '\x00\x07e\x12\x00\x00\x00\x00\x00\x00\x00\x00\xff\xff\xff\xff' \
     '\xff\xff\xff\xff\xd1\xf4\xbb\xb0\xbe\xfc\x13\xbd\x8c\xd3\x9d' \
     '\x0f\xcd\xd9;\x8c\x07\x8cJ/\x00\x00\x00\x00\x00\x00\x00\x00\x00' \
     '\x00\x00\x00\x00\x00\x00\x01D\x19\x00\x00\x00\x00\x00\xdf\x00' \
     '\x00\x01q\x00\x00\x00\x01\x00\x00\x00\x01\x00\x00\x00\x00\xff' \
     '\xff\xff\xff\xc1\x12\xb9\x04\x96\xa4Z1t\x91\xdfsJ\x90\xf0\x9bh' \
     '\x07l&\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00' \
     '\x00\x01D\xf8\x00\x00\x00\x00\x01\x1b\x00\x00\x01\xb8\x00\x00' \
     '\x00\x01\x00\x00\x00\x02\x00\x00\x00\x01\xff\xff\xff\xff\x02\n' \
     '\x0e\xc6&\xa1\x92\xae6\x0b\x02i\xfe-\xe5\xbao\x05\xd1\xe7\x00' \
     '\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01F' \
     '\x13\x00\x00\x00\x00\x01\xec\x00\x00\x03\x06\x00\x00\x00\x01' \
     '\x00\x00\x00\x03\x00\x00\x00\x02\xff\xff\xff\xff\x12\xcb\xeby1' \
     '\xb6\r\x98B\xcb\x07\xbd`\x8f\x92\xd9\xc4\x84\xbdK\x00\x00\x00' \
     '\x00\x00\x00\x00\x00\x00\x00\x00\x00'
 
-def runtest() :
+def parse_index2(data, inline):
+    index, chunkcache = parsers.parse_index2(data, inline)
+    return list(index), chunkcache
 
+def runtest() :
     py_res_1 = py_parseindex(data_inlined, True)
-    c_res_1 = parsers.parse_index2(data_inlined, True)
+    c_res_1 = parse_index2(data_inlined, True)
 
     py_res_2 = py_parseindex(data_non_inlined, False)
-    c_res_2 = parsers.parse_index2(data_non_inlined, False)
+    c_res_2 = parse_index2(data_non_inlined, False)
 
     if py_res_1 != c_res_1:
         print "Parse index result (with inlined data) differs!"
 
     if py_res_2 != c_res_2:
         print "Parse index result (no inlined data) differs!"
 
     print "done"
 
 runtest()