obsolete: use C code for headrevs calculation

Previously, if there were filtered revs the repository could not use the C fast
path for computing the head revs in the changelog. This slowed down many
operations in large repositories.

This adds the ability to filter revs to the C fast path. This speeds up histedit
on repositories with filtered revs by 30% (13s to 9s). This could be improved
further by sorting the filtered revs and walking the sorted list while we walk
the changelog, but even this initial version that just calls __contains__ is
still massively faster.

The new C api is compatible for both new and old python clients, and the new
python client can call both new and old C apis.

mercurial/changelog.py

@@ -171,8 +171,13 b' class changelog(revlog.revlog):'
 
     def headrevs(self):
         if self.filteredrevs:
-            # XXX we should fix and use the C version
-            return self._headrevs()
+            try:
+                return self.index.headrevs(self.filteredrevs)
+            # AttributeError covers non-c-extension environments.
+            # TypeError allows us work with old c extensions.
+            except (AttributeError, TypeError):
+                return self._headrevs()
+
         return super(changelog, self).headrevs()
 
     def strip(self, *args, **kwargs):

mercurial/parsers.c

@@ -508,6 +508,7 b' typedef struct {'
 	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 */
@@ -823,15 +824,60 b' static PyObject *list_copy(PyObject *lis'
 	return newlist;
 }
 
-static PyObject *index_headrevs(indexObject *self)
+static int check_filter(PyObject *filter, Py_ssize_t arg) {
+	if (filter) {
+		PyObject *arglist, *result;
+		int isfiltered;
+
+		arglist = Py_BuildValue("(n)", arg);
+		if (!arglist) {
+			return -1;
+		}
+
+		result = PyEval_CallObject(filter, arglist);
+		Py_DECREF(arglist);
+		if (!result) {
+			return -1;
+		}
+
+		/* PyObject_IsTrue returns 1 if true, 0 if false, -1 if error,
+		 * same as this function, so we can just return it directly.*/
+		isfiltered = PyObject_IsTrue(result);
+		Py_DECREF(result);
+		return isfiltered;
+	} else {
+		return 0;
+	}
+}
+
+static PyObject *index_headrevs(indexObject *self, PyObject *args)
 {
 	Py_ssize_t i, len, addlen;
 	char *nothead = NULL;
 	PyObject *heads;
+	PyObject *filter = NULL;
+	PyObject *filteredrevs = Py_None;
 
-	if (self->headrevs)
+	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)
@@ -850,9 +896,25 b' static PyObject *index_headrevs(indexObj'
 		goto bail;
 
 	for (i = 0; i < self->raw_length; i++) {
-		const char *data = index_deref(self, i);
-		int parent_1 = getbe32(data + 24);
-		int parent_2 = getbe32(data + 28);
+		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)
@@ -866,12 +928,26 b' static PyObject *index_headrevs(indexObj'
 		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)
@@ -894,9 +970,11 b' static PyObject *index_headrevs(indexObj'
 
 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;
@@ -1896,6 +1974,8 b' static int index_init(indexObject *self,'
 	self->cache = NULL;
 	self->data = NULL;
 	self->headrevs = NULL;
+	self->filteredrevs = Py_None;
+	Py_INCREF(Py_None);
 	self->nt = NULL;
 	self->offsets = NULL;
 
@@ -1945,6 +2025,7 b' static PyObject *index_nodemap(indexObje'
 static void index_dealloc(indexObject *self)
 {
 	_index_clearcaches(self);
+	Py_XDECREF(self->filteredrevs);
 	Py_XDECREF(self->data);
 	Py_XDECREF(self->added);
 	PyObject_Del(self);
@@ -1977,7 +2058,7 b' static PyMethodDef index_methods[] = {'
 	 "clear the index caches"},
 	{"get", (PyCFunction)index_m_get, METH_VARARGS,
 	 "get an index entry"},
-	{"headrevs", (PyCFunction)index_headrevs, METH_NOARGS,
+	{"headrevs", (PyCFunction)index_headrevs, METH_VARARGS,
 	 "get head revisions"},
 	{"insert", (PyCFunction)index_insert, METH_VARARGS,
 	 "insert an index entry"},