[PATCH 2 of 2] [WIP] parsers: use base-16 trie for faster node->rev mapping

Matt Mackall mpm at selenic.com
Thu Mar 29 15:17:12 CDT 2012


On Thu, 2012-03-22 at 11:44 -0700, Bryan O'Sullivan wrote:
> This vastly speeds up node->rev lookups: "hg --time log" of rev
> 1000 on a linux-2.6 repo improves from 0.27 seconds to 0.08.

Use contrib/perf.py, please!

I added this test to measure the time of a single load + node lookup:

diff -r 06945239e9a4 contrib/perf.py
--- a/contrib/perf.py	Thu Mar 29 14:51:55 2012 -0500
+++ b/contrib/perf.py	Thu Mar 29 15:02:39 2012 -0500
@@ -111,6 +111,15 @@
 def perflookup(ui, repo, rev):
     timer(lambda: len(repo.lookup(rev)))
 
+def perfnodelookup(ui, repo, rev):
+    import mercurial.revlog
+    mercurial.revlog._prereadsize = 2**24 # disable lazy parser in old hg
+    n = repo[rev].node()
+    def d():
+        cl = mercurial.revlog.revlog(repo.sopener, "00changelog.i")
+        cl.rev(n)
+    timer(d)
+
 def perflog(ui, repo, **opts):
     ui.pushbuffer()
     timer(lambda: commands.log(ui, repo, rev=[], date='', user='',
@@ -153,6 +162,7 @@
 
 cmdtable = {
     'perflookup': (perflookup, []),
+    'perfnodelookup': (perfnodelookup, []),
     'perfparents': (perfparents, []),
     'perfstartup': (perfstartup, []),
     'perfstatus': (perfstatus, []),

My results:

Base:
! wall 0.371480 comb 0.370000 user 0.360000 sys 0.010000 (best of 26)
With new lazy parser:
! wall 0.201636 comb 0.210000 user 0.180000 sys 0.030000 (best of 46)
With radix tree:
! wall 0.053340 comb 0.040000 user 0.040000 sys 0.000000 (best of 100)

Notably, the old Python lazy index from 1.7 is actually faster here:

! wall 0.008514 comb 0.000000 user 0.000000 sys 0.000000 (best of 331)

http://www.selenic.com/hg/file/333421b9e0f9/mercurial/revlog.py#l200




> The only part that's not yet done is having parsers.index_getitem
> throw a LookupError instead of a KeyError on lookup failure.
> 
> (Speeding up prefix-based node->rev lookup will come in a patch
> that I haven't yet written, so don't expect that to be fast yet.)
> 
> diff --git a/mercurial/parsers.c b/mercurial/parsers.c
> --- a/mercurial/parsers.c
> +++ b/mercurial/parsers.c
> @@ -242,10 +242,27 @@
>  }
>  
>  /*
> - * 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.
> + * 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
> @@ -255,10 +272,16 @@
>  	Py_ssize_t raw_length;	/* original number of elements */
>  	Py_ssize_t length;	/* current number of elements */
>  	PyObject *added;	/* populated on demand */
> -	int inlined;
> +	nodetree *nt;
> +	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 inlined;		/* bool: index contains inline data */
>  } indexObject;
>  
> -static Py_ssize_t index_length(indexObject *self)
> +static Py_ssize_t index_length(const indexObject *self)
>  {
>  	if (self->added == NULL)
>  		return self->length;
> @@ -266,6 +289,7 @@
>  }
>  
>  static PyObject *nullentry;
> +static const char nullid[20];
>  
>  static long inline_scan(indexObject *self, const char **offsets);
>  
> @@ -275,7 +299,27 @@
>  static const char *tuple_format = "kiiiiiis#";
>  #endif
>  
> -/* RevlogNG format (all in big endian, data may be inlined):
> +/*
> + * 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 * 64;
> +}
> +
> +/*
> + * RevlogNG format (all in big endian, data may be inlined):
>   *    6 bytes: offset
>   *    2 bytes: flags
>   *    4 bytes: compressed length
> @@ -296,7 +340,10 @@
>  	Py_ssize_t length = index_length(self);
>  	PyObject *entry;
>  
> -	if (pos >= length) {
> +        if (pos < 0)
> +                pos += length;
> +
> +	if (pos < 0 || pos >= length) {
>  		PyErr_SetString(PyExc_IndexError, "revlog index out of range");
>  		return NULL;
>  	}
> @@ -313,17 +360,9 @@
>  		return obj;
>  	}
>  
> -	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;
> +	data = index_deref(self, pos);
> +	if (data == NULL)
> +		return NULL;
>  
>  	memcpy(decode, data, 8 * sizeof(uint32_t));
>  
> @@ -353,26 +392,60 @@
>  	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)
> +		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, *node;
> +	PyObject *obj;
> +	char *node;
>  	long offset;
> -	Py_ssize_t len;
> +	Py_ssize_t len, nodelen;
>  
>  	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");
> +		PyErr_SetString(PyExc_TypeError, "8-tuple required");
>  		return NULL;
>  	}
>  
> -	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");
> +	if (node_check(PyTuple_GET_ITEM(obj, 7), &node, &nodelen) == -1)
>  		return NULL;
> -	}
>  
>  	len = index_length(self);
>  
> @@ -385,6 +458,12 @@
>  		return NULL;
>  	}
>  
> +	if (offset > INT_MAX) {
> +		PyErr_SetString(PyExc_ValueError,
> +				"currently only 2**31 revs supported");
> +		return NULL;
> +	}
> +
>  	if (self->added == NULL) {
>  		self->added = PyList_New(0);
>  		if (self->added == NULL)
> @@ -394,21 +473,287 @@
>  	if (PyList_Append(self->added, obj) == -1)
>  		return NULL;
>  
> +	if (self->nt)
> +		nt_insert(self, node, (int) offset);
> +
>  	Py_RETURN_NONE;
>  }
>  
> +static PyObject *index_stats(indexObject *self)
> +{
> +	PyObject *obj = PyDict_New();
> +
> +	if (obj == NULL)
> +		return NULL;
> +
> +#define istat(__n, __d)							\
> +	if (PyDict_SetItemString(obj, __d, PyInt_FromLong(self->__n)) == -1) goto bail;
> +
> +	if (self->added) {
> +		Py_ssize_t len = PyList_GET_SIZE(self->added);
> +		if (PyDict_SetItemString(obj, "index entries added",
> +					 PyInt_FromLong(len)) == -1)
> +			goto bail;
> +	}
> +
> +	if (self->raw_length != self->length - 1)
> +		istat(raw_length, "revs on disk");
> +	istat(length, "revs in memory");
> +	istat(ntlength, "node trie count");
> +	istat(ntcapacity, "node trie capacity");
> +	istat(ntdepth, "node trie depth");
> +	istat(ntsplits, "node trie splits");
> +	istat(ntrev, "node trie last rev scanned");
> +
> +#undef istat
> +
> +	return obj;
> +
> +bail:
> +	Py_XDECREF(obj);
> +	return NULL;
> +}
> +
> +static inline int nt_level(const char *node, int level)
> +{
> +	int v = node[level>>1];
> +	if (!(level & 1))
> +		v >>= 4;
> +	return v & 0xf;
> +}
> +
> +static int nt_find(indexObject *self, const char *node, Py_ssize_t nodelen)
> +{
> +	int level, off;
> +
> +	if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0)
> +		return -1;
> +
> +	if (self->nt == NULL)
> +		return -2;
> +
> +	for (level = off = 0; level < nodelen; level++) {
> +		int k = nt_level(node, level);
> +		nodetree *n = &self->nt[off];
> +		int v = n->children[k];
> +
> +		if (v < 0) {
> +			const char *n;
> +			v = -v - 1;
> +			n = index_node(self, v);
> +			if (n == NULL)
> +				return -2;
> +			return memcmp(node, n, nodelen > 20 ? 20 : nodelen)
> +				? -2 : v;
> +		}
> +		if (v == 0)
> +			return -2;
> +		off = v;
> +	}
> +	return -2;
> +}
> +
> +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 < 20) {
> +		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 == NULL) {
> +				/* node has been deleted from array */
> +				n->children[k] = -rev - 1;
> +				return 0;
> +			}
> +			if (memcmp(oldnode, node, 20) == 0)
> +				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;
> +}
> +
> +/*
> + * 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;
> +
> +	rev = nt_find(self, node, nodelen);
> +	if (rev >= -1)
> +		return rev;
> +
> +	if (self->nt == NULL) {
> +		self->ntcapacity = 4096;
> +		self->nt = calloc(self->ntcapacity, sizeof(nodetree));
> +		if (self->nt == NULL) {
> +			PyErr_SetString(PyExc_MemoryError, "out of memory");
> +			return -3;
> +		}
> +		self->ntrev = (int) index_length(self) - 1;
> +		self->ntlength = 1;
> +	}
> +
> +	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;
> +		if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0)
> +			break;
> +	}
> +
> +	self->ntrev = rev;
> +
> +	if (rev >= 0)
> +		return rev;
> +	return -2;
> +}
> +
> +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 (PyString_AsStringAndSize(value, &node, &nodelen) == -1)
> +		return NULL;
> +	rev = index_find_node(self, node, nodelen);
> +	if (rev >= -1)
> +		return PyInt_FromLong(rev);
> +	if (rev == -2)
> +		/* XXX should be a LookupError? */
> +		PyErr_SetString(PyExc_KeyError, "node not found");
> +	return NULL;
> +}
> +
> +static PyObject *index_m_get(indexObject *self, PyObject *args)
> +{
> +	char *node;
> +	int nodelen, rev;
> +
> +	if (!PyArg_ParseTuple(args, "s#", &node, &nodelen))
> +		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 (!PyString_Check(value))
> +		return 0;
> +
> +	node = PyString_AS_STRING(value);
> +	nodelen = PyString_GET_SIZE(value);
> +
> +	switch (index_find_node(self, node, nodelen)) {
> +	case -3:
> +		return -1;
> +	case -2:
> +		return 0;
> +	default:
> +		return 1;
> +	}
> +}
> +
> +/*
> + * 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_DECREF(self->added);
> +		self->added = NULL;
> +	}
> +}
> +
> +/*
> + * Delete a numeric range of revs, which must be at the end of the
> + * range, but exclude the sentinel nullid entry.
> + */
>  static int
> -index_ass_subscript(indexObject* self, PyObject* item, PyObject* value)
> +index_slice_del(indexObject* self, PyObject* item)
>  {
>  	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;
> @@ -437,20 +782,67 @@
>  		return -1;
>  	}
>  
> -	if (start < self->length) {
> +	if (start < self->length - 1) {
>  		self->length = start + 1;
> -		if (self->added) {
> -			Py_DECREF(self->added);
> -			self->added = NULL;
> +
> +		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);
>  		}
>  		return 0;
>  	}
>  
> -	return PyList_SetSlice(self->added, start - self->length + 1,
> -			       PyList_GET_SIZE(self->added),
> -			       NULL);
> +	if (self->nt)
> +		nt_invalidate_added(self, start - self->length + 1);
> +	return self->added
> +		? PyList_SetSlice(self->added, start - self->length + 1,
> +				  PyList_GET_SIZE(self->added), NULL)
> +		: 0;
>  }
>  
> +/*
> + * Supported ops:
> + *
> + * slice deletion
> + * string assignment (extend node->rev mapping)
> + * string deletion (shrink node->rev mapping)
> + */
> +static int
> +index_ass_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;
> +	}
> +	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 long inline_scan(indexObject *self, const char **offsets)
>  {
>  	const char *data = PyString_AS_STRING(self->data);
> @@ -493,6 +885,10 @@
>  
>  	self->added = NULL;
>  	self->offsets = NULL;
> +	self->nt = NULL;
> +	self->ntlength = self->ntcapacity = 0;
> +	self->ntdepth = self->ntsplits = 0;
> +	self->ntrev = -1;
>  	Py_INCREF(self->data);
>  
>  	if (self->inlined) {
> @@ -535,6 +931,7 @@
>      Py_DECREF(self->data);
>      Py_XDECREF(self->added);
>      free(self->offsets);
> +    free(self->nt);
>      PyObject_Del(self);
>  }
>  
> @@ -543,24 +940,32 @@
>  	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 */
> -    NULL,			/* mp_subscript */
> +    (binaryfunc)index_getitem,	/* mp_subscript */
>      (objobjargproc)index_ass_subscript, /* mp_ass_subscript */
>  };
>  
>  static PyMethodDef index_methods[] = {
> +	{"get", (PyCFunction)index_m_get, METH_VARARGS,
> +	 "get an index entry"},
>  	{"insert", (PyCFunction)index_insert, METH_VARARGS,
>  	 "insert an index entry"},
> +	{"stats", (PyCFunction)index_stats, METH_NOARGS,
> +	 "stats for the index"},
>  	{NULL}	/* Sentinel */
>  };
>  
>  static PyTypeObject indexType = {
>  	PyObject_HEAD_INIT(NULL)
>  	0,			   /*ob_size*/
> -	"index.index",		   /*tp_name*/
> +	"parsers.index",	   /*tp_name*/
>  	sizeof(indexObject),	   /*tp_basicsize*/
>  	0,			   /*tp_itemsize*/
>  	(destructor)index_dealloc, /*tp_dealloc*/
> @@ -600,10 +1005,10 @@
>  };
>  
>  /*
> - * returns a tuple of the form (index, None, cache) with elements as
> + * returns a tuple of the form (index, index, cache) with elements as
>   * follows:
>   *
> - * index: an index object that lazily parses the RevlogNG records
> + * 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
> @@ -638,10 +1043,9 @@
>  		Py_INCREF(cache);
>  	}
>  
> -	none = Py_None;
> -	Py_INCREF(none);
> +	Py_INCREF(idx);
>  
> -	tuple = Py_BuildValue("NNN", idx, none, cache);
> +	tuple = Py_BuildValue("NNN", idx, idx, cache);
>  	if (!tuple)
>  		goto bail;
>  	return tuple;
> @@ -665,8 +1069,6 @@
>  
>  static void module_init(PyObject *mod)
>  {
> -	static const char nullid[20];
> -
>  	if (PyType_Ready(&indexType) < 0)
>  		return;
>  	Py_INCREF(&indexType);
> @@ -701,4 +1103,3 @@
>  	module_init(mod);
>  }
>  #endif
> -
> diff --git a/mercurial/revlog.py b/mercurial/revlog.py
> --- a/mercurial/revlog.py
> +++ b/mercurial/revlog.py
> @@ -219,7 +219,7 @@
>          self._chunkcache = (0, '')
>          self.index = []
>          self._pcache = {}
> -        self._nodecache = {nullid: nullrev}
> +        #self.__nodecache = {nullid: nullrev}
>          self._nodepos = None
>  
>          v = REVLOG_DEFAULT_VERSION
> @@ -287,9 +287,20 @@
>  
>      def rev(self, node):
>          try:
> -            return self._nodecache[node]
> +            r = self._nodecache[node]
>          except KeyError:
> -            n = self._nodecache
> +            raise LookupError(node, self.indexfile, _('no node?'))
> +        if False:
> +            r1 = self.rev_(node)
> +            if r != r1:
> +                raise Exception('node %s: %s != %s' % (node.encode('hex'), r, r1))
> +        return r
> +
> +    def rev_(self, node):
> +        try:
> +            return self.__nodecache[node]
> +        except KeyError:
> +            n = self.__nodecache
>              i = self.index
>              p = self._nodepos
>              if p is None:
> @@ -1057,6 +1068,7 @@
>               base, link, p1r, p2r, node)
>          self.index.insert(-1, e)
>          self.nodemap[node] = curr
> +        #self.__nodecache[node] = curr
>  
>          entry = self._io.packentry(e, self.node, self.version, curr)
>          if not self._inline:
> @@ -1230,6 +1242,7 @@
>          self._chunkclear()
>          for x in xrange(rev, len(self)):
>              del self.nodemap[self.node(x)]
> +            #del self.__nodecache[self.node(x)]
>  
>          del self.index[rev:-1]
>  
> diff --git a/tests/test-parseindex2.py b/tests/test-parseindex2.py
> --- a/tests/test-parseindex2.py
> +++ b/tests/test-parseindex2.py
> @@ -110,6 +110,17 @@
>      if py_res_2 != c_res_2:
>          print "Parse index result (no inlined data) differs!"
>  
> +    ix = parsers.parse_index2(data_inlined, True)[0]
> +    for i,r in enumerate(ix):
> +        try:
> +            if r[7] == nullid:
> +                i = -1
> +            if ix[r[7]] != i:
> +                print 'Reverse lookup inconsistent for %r' % r[7].encode('hex')
> +        except:
> +            print 'Reverse lookup failed for %r' % r[7].encode('hex')
> +            raise
> +
>      print "done"
>  
>  runtest()


-- 
Mathematics is the supreme nostalgia of our time.




More information about the Mercurial-devel mailing list