rust: exposing in parsers module

To build with the Rust code, set the HGWITHRUSTEXT
environment variable.

At this point, it's possible to instantiate and use
a rustlazyancestors object from a Python interpreter.

The changes in setup.py are obviously a quick hack,
just good enough to test/bench without much
refactoring. We'd be happy to improve on that with
help from the community.

Rust bindings crate gets compiled as a static library,
which in turn gets linked within 'parsers.so'

With respect to the plans at
https://www.mercurial-scm.org/wiki/OxidationPlan
this would probably qualify as "roll our own FFI".
Also, it doesn't quite meet the target of getting
rid of C code, since it brings actually more, yet:

- the new C code does nothing else than parsing
  arguments and calling Rust functions.
  In particular, there's no complex allocation involved.
- subsequent changes could rewrite more of revlog.c, this
  time resulting in an overall decrease of C code and
  unsafety.

mercurial/cext/revlog.c

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

setup.py

@@ -1,1103 +1,1160
 #
 # This is the mercurial setup script.
 #
 # 'python setup.py install', or
 # 'python setup.py --help' for more options
 
 import os
 
 supportedpy = '~= 2.7'
 if os.environ.get('HGALLOWPYTHON3', ''):
     # Mercurial will never work on Python 3 before 3.5 due to a lack
     # of % formatting on bytestrings, and can't work on 3.6.0 or 3.6.1
     # due to a bug in % formatting in bytestrings.
     # We cannot support Python 3.5.0, 3.5.1, 3.5.2 because of bug in
     # codecs.escape_encode() where it raises SystemError on empty bytestring
     # bug link: https://bugs.python.org/issue25270
     #
     # TODO: when we actually work on Python 3, use this string as the
     # actual supportedpy string.
     supportedpy = ','.join([
         '>=2.7',
         '!=3.0.*',
         '!=3.1.*',
         '!=3.2.*',
         '!=3.3.*',
         '!=3.4.*',
         '!=3.5.0',
         '!=3.5.1',
         '!=3.5.2',
         '!=3.6.0',
         '!=3.6.1',
     ])
 
 import sys, platform
 if sys.version_info[0] >= 3:
     printf = eval('print')
     libdir_escape = 'unicode_escape'
     def sysstr(s):
         return s.decode('latin-1')
 else:
     libdir_escape = 'string_escape'
     def printf(*args, **kwargs):
         f = kwargs.get('file', sys.stdout)
         end = kwargs.get('end', '\n')
         f.write(b' '.join(args) + end)
     def sysstr(s):
         return s
 
 # Attempt to guide users to a modern pip - this means that 2.6 users
 # should have a chance of getting a 4.2 release, and when we ratchet
 # the version requirement forward again hopefully everyone will get
 # something that works for them.
 if sys.version_info < (2, 7, 0, 'final'):
     pip_message = ('This may be due to an out of date pip. '
                    'Make sure you have pip >= 9.0.1.')
     try:
         import pip
         pip_version = tuple([int(x) for x in pip.__version__.split('.')[:3]])
         if pip_version < (9, 0, 1) :
             pip_message = (
                 'Your pip version is out of date, please install '
                 'pip >= 9.0.1. pip {} detected.'.format(pip.__version__))
         else:
             # pip is new enough - it must be something else
             pip_message = ''
     except Exception:
         pass
     error = """
 Mercurial does not support Python older than 2.7.
 Python {py} detected.
 {pip}
 """.format(py=sys.version_info, pip=pip_message)
     printf(error, file=sys.stderr)
     sys.exit(1)
 
 # We don't yet officially support Python 3. But we want to allow developers to
 # hack on. Detect and disallow running on Python 3 by default. But provide a
 # backdoor to enable working on Python 3.
 if sys.version_info[0] != 2:
     badpython = True
 
     # Allow Python 3 from source checkouts.
     if os.path.isdir('.hg') or 'HGPYTHON3' in os.environ:
         badpython = False
 
     if badpython:
         error = """
 Mercurial only supports Python 2.7.
 Python {py} detected.
 Please re-run with Python 2.7.
 """.format(py=sys.version_info)
 
         printf(error, file=sys.stderr)
         sys.exit(1)
 
 # 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
 
+iswithrustextensions = 'HGWITHRUSTEXT' in os.environ
+
 import ctypes
 import stat, subprocess, time
 import re
 import shutil
 import tempfile
 from distutils import log
 # We have issues with setuptools on some platforms and builders. Until
 # those are resolved, setuptools is opt-in except for platforms where
 # we don't have issues.
 issetuptools = (os.name == 'nt' or 'FORCE_SETUPTOOLS' in os.environ)
 if issetuptools:
     from setuptools import setup
 else:
     from distutils.core import setup
 from distutils.ccompiler import new_compiler
 from distutils.core import 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.build_scripts import build_scripts
 from distutils.command.install import install
 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,
     DistutilsError,
     DistutilsExecError,
 )
 from distutils.sysconfig import get_python_inc, get_config_var
 from distutils.version import StrictVersion
 
 def write_if_changed(path, content):
     """Write content to a file iff the content hasn't changed."""
     if os.path.exists(path):
         with open(path, 'rb') as fh:
             current = fh.read()
     else:
         current = b''
 
     if current != content:
         with open(path, 'wb') as fh:
             fh.write(content)
 
 scripts = ['hg']
 if os.name == 'nt':
     # We remove hg.bat if we are able to build hg.exe.
     scripts.append('contrib/win32/hg.bat')
 
 def cancompile(cc, code):
     tmpdir = tempfile.mkdtemp(prefix='hg-install-')
     devnull = oldstderr = None
     try:
         fname = os.path.join(tmpdir, 'testcomp.c')
         f = open(fname, 'w')
         f.write(code)
         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"))
         return True
     except Exception:
         return False
     finally:
         if oldstderr is not None:
             os.dup2(oldstderr, sys.stderr.fileno())
         if devnull is not None:
             devnull.close()
         shutil.rmtree(tmpdir)
 
 # simplified version of distutils.ccompiler.CCompiler.has_function
 # that actually removes its temporary files.
 def hasfunction(cc, funcname):
     code = 'int main(void) { %s(); }\n' % funcname
     return cancompile(cc, code)
 
 def hasheader(cc, headername):
     code = '#include <%s>\nint main(void) { return 0; }\n' % headername
     return cancompile(cc, code)
 
 # 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):
     p = subprocess.Popen(cmd, stdout=subprocess.PIPE,
                          stderr=subprocess.PIPE, env=env)
     out, err = p.communicate()
     return p.returncode, out, err
 
 class hgcommand(object):
     def __init__(self, cmd, env):
         self.cmd = cmd
         self.env = env
 
     def run(self, args):
         cmd = self.cmd + args
         returncode, out, err = runcmd(cmd, self.env)
         err = filterhgerr(err)
         if err or returncode != 0:
             printf("stderr from '%s':" % (' '.join(cmd)), file=sys.stderr)
             printf(err, file=sys.stderr)
             return ''
         return out
 
 def filterhgerr(err):
     # 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')
                and not e.startswith(b'*** failed to import extension')
                and not e.startswith(b'devel-warn:')
                and not (e.startswith(b'(third party extension')
                         and e.endswith(b'or newer of Mercurial; disabling)')))]
     return b'\n'.join(b'  ' + e for e in err)
 
 def findhg():
     """Try to figure out how we should invoke hg for examining the local
     repository contents.
 
     Returns an hgcommand object."""
     # By default, prefer the "hg" command in the user's path.  This was
     # presumably the hg command that the user used to create this repository.
     #
     # This repository may require extensions or other settings that would not
     # be enabled by running the hg script directly from this local repository.
     hgenv = os.environ.copy()
     # Use HGPLAIN to disable hgrc settings that would change output formatting,
     # and disable localization for the same reasons.
     hgenv['HGPLAIN'] = '1'
     hgenv['LANGUAGE'] = 'C'
     hgcmd = ['hg']
     # Run a simple "hg log" command just to see if using hg from the user's
     # path works and can successfully interact with this repository.
     check_cmd = ['log', '-r.', '-Ttest']
     try:
         retcode, out, err = runcmd(hgcmd + check_cmd, hgenv)
     except EnvironmentError:
         retcode = -1
     if retcode == 0 and not filterhgerr(err):
         return hgcommand(hgcmd, hgenv)
 
     # Fall back to trying the local hg installation.
     hgenv = localhgenv()
     hgcmd = [sys.executable, 'hg']
     try:
         retcode, out, err = runcmd(hgcmd + check_cmd, hgenv)
     except EnvironmentError:
         retcode = -1
     if retcode == 0 and not filterhgerr(err):
         return hgcommand(hgcmd, hgenv)
 
     raise SystemExit('Unable to find a working hg binary to extract the '
                      'version from the repository tags')
 
 def localhgenv():
     """Get an environment dictionary to use for invoking or importing
     mercurial from the local repository."""
     # Execute hg out of this directory with a custom environment which takes
     # care to not use any hgrc files and do no localization.
     env = {'HGMODULEPOLICY': 'py',
            'HGRCPATH': '',
            'LANGUAGE': 'C',
            'PATH': ''} # make pypi modules that use os.environ['PATH'] happy
     if 'LD_LIBRARY_PATH' in os.environ:
         env['LD_LIBRARY_PATH'] = os.environ['LD_LIBRARY_PATH']
     if 'SystemRoot' in os.environ:
         # SystemRoot is required by Windows to load various DLLs.  See:
         # https://bugs.python.org/issue13524#msg148850
         env['SystemRoot'] = os.environ['SystemRoot']
     return env
 
 version = ''
 
 if os.path.isdir('.hg'):
     hg = findhg()
     cmd = ['log', '-r', '.', '--template', '{tags}\n']
     numerictags = [t for t in sysstr(hg.run(cmd)).split() if t[0:1].isdigit()]
     hgid = sysstr(hg.run(['id', '-i'])).strip()
     if not hgid:
         # Bail out if hg is having problems interacting with this repository,
         # rather than falling through and producing a bogus version number.
         # Continuing with an invalid version number will break extensions
         # that define minimumhgversion.
         raise SystemExit('Unable to determine hg version from local repository')
     if numerictags: # tag(s) found
         version = numerictags[-1]
         if hgid.endswith('+'): # propagate the dirty status to the tag
             version += '+'
     else: # no tag found
         ltagcmd = ['parents', '--template', '{latesttag}']
         ltag = sysstr(hg.run(ltagcmd))
         changessincecmd = ['log', '-T', 'x\n', '-r', "only(.,'%s')" % ltag]
         changessince = len(hg.run(changessincecmd).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:
     versionb = version
     if not isinstance(versionb, bytes):
         versionb = versionb.encode('ascii')
 
     write_if_changed('mercurial/__version__.py', b''.join([
         b'# this file is autogenerated by setup.py\n'
         b'version = b"%s"\n' % versionb,
     ]))
 
 try:
     oldpolicy = os.environ.get('HGMODULEPOLICY', None)
     os.environ['HGMODULEPOLICY'] = 'py'
     from mercurial import __version__
     version = __version__.version
 except ImportError:
     version = b'unknown'
 finally:
     if oldpolicy is None:
         del os.environ['HGMODULEPOLICY']
     else:
         os.environ['HGMODULEPOLICY'] = oldpolicy
 
 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)] + 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 = False
     cffi = ispypy
 
     global_options = Distribution.global_options + \
                      [('pure', None, "use pure (slow) Python "
                         "code instead of C extensions"),
                      ]
 
     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)
 
 # This is ugly as a one-liner. So use a variable.
 buildextnegops = dict(getattr(build_ext, 'negative_options', {}))
 buildextnegops['no-zstd'] = 'zstd'
 
 class hgbuildext(build_ext):
     user_options = build_ext.user_options + [
         ('zstd', None, 'compile zstd bindings [default]'),
         ('no-zstd', None, 'do not compile zstd bindings'),
     ]
 
     boolean_options = build_ext.boolean_options + ['zstd']
     negative_opt = buildextnegops
 
     def initialize_options(self):
         self.zstd = True
         return build_ext.initialize_options(self)
 
     def build_extensions(self):
         # Filter out zstd if disabled via argument.
         if not self.zstd:
             self.extensions = [e for e in self.extensions
                                if e.name != 'mercurial.zstd']
 
         return build_ext.build_extensions(self)
 
     def build_extension(self, ext):
+        if isinstance(ext, RustExtension):
+            ext.rustbuild()
         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 hgbuildscripts(build_scripts):
     def run(self):
         if os.name != 'nt' or self.distribution.pure:
             return build_scripts.run(self)
 
         exebuilt = False
         try:
             self.run_command('build_hgexe')
             exebuilt = True
         except (DistutilsError, CCompilerError):
             log.warn('failed to build optional hg.exe')
 
         if exebuilt:
             # Copying hg.exe to the scripts build directory ensures it is
             # installed by the install_scripts command.
             hgexecommand = self.get_finalized_command('build_hgexe')
             dest = os.path.join(self.build_dir, 'hg.exe')
             self.mkpath(self.build_dir)
             self.copy_file(hgexecommand.hgexepath, dest)
 
             # Remove hg.bat because it is redundant with hg.exe.
             self.scripts.remove('contrib/win32/hg.bat')
 
         return build_scripts.run(self)
 
 class hgbuildpy(build_py):
     def finalize_options(self):
         build_py.finalize_options(self)
 
         if self.distribution.pure:
             self.distribution.ext_modules = []
         elif self.distribution.cffi:
             from mercurial.cffi import (
                 bdiffbuild,
                 mpatchbuild,
             )
             exts = [mpatchbuild.ffi.distutils_extension(),
                     bdiffbuild.ffi.distutils_extension()]
             # cffi modules go here
             if sys.platform == 'darwin':
                 from mercurial.cffi import osutilbuild
                 exts.append(osutilbuild.ffi.distutils_extension())
             self.distribution.ext_modules = exts
         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 run(self):
         basepath = os.path.join(self.build_lib, 'mercurial')
         self.mkpath(basepath)
 
         if self.distribution.pure:
             modulepolicy = 'py'
         elif self.build_lib == '.':
             # in-place build should run without rebuilding C extensions
             modulepolicy = 'allow'
         else:
             modulepolicy = 'c'
 
         content = b''.join([
             b'# this file is autogenerated by setup.py\n',
             b'modulepolicy = b"%s"\n' % modulepolicy.encode('ascii'),
         ])
         write_if_changed(os.path.join(basepath, '__modulepolicy__.py'),
                          content)
 
         build_py.run(self)
 
 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):
             with open(self._indexfilename, 'w') as f:
                 f.write('# empty\n')
 
         # here no extension enabled, disabled() lists up everything
         code = ('import pprint; from mercurial import extensions; '
                 'pprint.pprint(extensions.disabled())')
         returncode, out, err = runcmd([sys.executable, '-c', code],
                                       localhgenv())
         if err or returncode != 0:
             raise DistutilsExecError(err)
 
         with open(self._indexfilename, 'w') as f:
             f.write('# this file is autogenerated by setup.py\n')
             f.write('docs = ')
             f.write(out)
 
 class buildhgexe(build_ext):
     description = 'compile hg.exe from mercurial/exewrapper.c'
     user_options = build_ext.user_options + [
         ('long-paths-support', None, 'enable support for long paths on '
                                      'Windows (off by default and '
                                      'experimental)'),
     ]
 
     LONG_PATHS_MANIFEST = """
     <?xml version="1.0" encoding="UTF-8" standalone="yes"?>
     <assembly xmlns="urn:schemas-microsoft-com:asm.v1" manifestVersion="1.0">
         <application>
             <windowsSettings
             xmlns:ws2="http://schemas.microsoft.com/SMI/2016/WindowsSettings">
                 <ws2:longPathAware>true</ws2:longPathAware>
             </windowsSettings>
         </application>
     </assembly>"""
 
     def initialize_options(self):
         build_ext.initialize_options(self)
         self.long_paths_support = False
 
     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
 
         # Different Python installs can have different Python library
         # names. e.g. the official CPython distribution uses pythonXY.dll
         # and MinGW uses libpythonX.Y.dll.
         _kernel32 = ctypes.windll.kernel32
         _kernel32.GetModuleFileNameA.argtypes = [ctypes.c_void_p,
                                                  ctypes.c_void_p,
                                                  ctypes.c_ulong]
         _kernel32.GetModuleFileNameA.restype = ctypes.c_ulong
         size = 1000
         buf = ctypes.create_string_buffer(size + 1)
         filelen = _kernel32.GetModuleFileNameA(sys.dllhandle, ctypes.byref(buf),
                                                size)
 
         if filelen > 0 and filelen != size:
             dllbasename = os.path.basename(buf.value)
             if not dllbasename.lower().endswith(b'.dll'):
                 raise SystemExit('Python DLL does not end with .dll: %s' %
                                  dllbasename)
             pythonlib = dllbasename[:-4]
         else:
             log.warn('could not determine Python DLL filename; '
                      'assuming pythonXY')
 
             hv = sys.hexversion
             pythonlib = 'python%d%d' % (hv >> 24, (hv >> 16) & 0xff)
 
         log.info('using %s as Python library name' % pythonlib)
         with open('mercurial/hgpythonlib.h', 'wb') as f:
             f.write(b'/* this file is autogenerated by setup.py */\n')
             f.write(b'#define HGPYTHONLIB "%s"\n' % pythonlib)
         objects = self.compiler.compile(['mercurial/exewrapper.c'],
                                          output_dir=self.build_temp)
         dir = os.path.dirname(self.get_ext_fullpath('dummy'))
         self.hgtarget = os.path.join(dir, 'hg')
         self.compiler.link_executable(objects, self.hgtarget,
                                       libraries=[],
                                       output_dir=self.build_temp)
         if self.long_paths_support:
             self.addlongpathsmanifest()
 
     def addlongpathsmanifest(self):
         """Add manifest pieces so that hg.exe understands long paths
 
         This is an EXPERIMENTAL feature, use with care.
         To enable long paths support, one needs to do two things:
         - build Mercurial with --long-paths-support option
         - change HKLM\SYSTEM\CurrentControlSet\Control\FileSystem\
                  LongPathsEnabled to have value 1.
 
         Please ignore 'warning 81010002: Unrecognized Element "longPathAware"';
         it happens because Mercurial uses mt.exe circa 2008, which is not
         yet aware of long paths support in the manifest (I think so at least).
         This does not stop mt.exe from embedding/merging the XML properly.
 
         Why resource #1 should be used for .exe manifests? I don't know and
         wasn't able to find an explanation for mortals. But it seems to work.
         """
         exefname = self.compiler.executable_filename(self.hgtarget)
         fdauto, manfname = tempfile.mkstemp(suffix='.hg.exe.manifest')
         os.close(fdauto)
         with open(manfname, 'w') as f:
             f.write(self.LONG_PATHS_MANIFEST)
         log.info("long paths manifest is written to '%s'" % manfname)
         inputresource = '-inputresource:%s;#1' % exefname
         outputresource = '-outputresource:%s;#1' % exefname
         log.info("running mt.exe to update hg.exe's manifest in-place")
         # supplying both -manifest and -inputresource to mt.exe makes
         # it merge the embedded and supplied manifests in the -outputresource
         self.spawn(['mt.exe', '-nologo', '-manifest', manfname,
                     inputresource, outputresource])
         log.info("done updating hg.exe's manifest")
         os.remove(manfname)
 
     @property
     def hgexepath(self):
         dir = os.path.dirname(self.get_ext_fullpath('dummy'))
         return os.path.join(self.build_temp, dir, 'hg.exe')
 
 class hginstall(install):
 
     user_options = install.user_options + [
         ('old-and-unmanageable', None,
          'noop, present for eggless setuptools compat'),
         ('single-version-externally-managed', None,
          'noop, present for eggless setuptools compat'),
     ]
 
     # Also helps setuptools not be sad while we refuse to create eggs.
     single_version_externally_managed = True
 
     def get_sub_commands(self):
         # Screen out egg related commands to prevent egg generation.  But allow
         # mercurial.egg-info generation, since that is part of modern
         # packaging.
         excl = set(['bdist_egg'])
         return filter(lambda x: x not in excl, install.get_sub_commands(self))
 
 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 = int('0755', 8)
                 else:
                     setmode = int('0644', 8)
                 m = stat.S_IMODE(st[stat.ST_MODE])
                 m = (m & ~int('0777', 8)) | setmode
                 os.chmod(dst, m)
         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)
 
         # It only makes sense to replace @LIBDIR@ with the install path if
         # the install path is known. For wheels, the logic below calculates
         # the libdir to be "../..". This is because the internal layout of a
         # wheel archive looks like:
         #
         #   mercurial-3.6.1.data/scripts/hg
         #   mercurial/__init__.py
         #
         # When installing wheels, the subdirectories of the "<pkg>.data"
         # directory are translated to system local paths and files therein
         # are copied in place. The mercurial/* files are installed into the
         # site-packages directory. However, the site-packages directory
         # isn't known until wheel install time. This means we have no clue
         # at wheel generation time what the installed site-packages directory
         # will be. And, wheels don't appear to provide the ability to register
         # custom code to run during wheel installation. This all means that
         # we can't reliably set the libdir in wheels: the default behavior
         # of looking in sys.path must do.
 
         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:
             with open(outfile, 'rb') as fp:
                 data = fp.read()
 
             # skip binary files
             if b'\0' in data:
                 continue
 
             # During local installs, the shebang will be rewritten to the final
             # install path. During wheel packaging, the shebang has a special
             # value.
             if data.startswith(b'#!python'):
                 log.info('not rewriting @LIBDIR@ in %s because install path '
                          'not known' % outfile)
                 continue
 
             data = data.replace(b'@LIBDIR@', libdir.encode(libdir_escape))
             with open(outfile, 'wb') as fp:
                 fp.write(data)
 
 cmdclass = {'build': hgbuild,
             'build_mo': hgbuildmo,
             'build_ext': hgbuildext,
             'build_py': hgbuildpy,
             'build_scripts': hgbuildscripts,
             'build_hgextindex': buildhgextindex,
             'install': hginstall,
             'install_lib': hginstalllib,
             'install_scripts': hginstallscripts,
             'build_hgexe': buildhgexe,
             }
 
 packages = ['mercurial',
             'mercurial.cext',
             'mercurial.cffi',
             'mercurial.hgweb',
             'mercurial.pure',
             'mercurial.thirdparty',
             'mercurial.thirdparty.attr',
             'mercurial.thirdparty.cbor',
             'mercurial.thirdparty.cbor.cbor2',
             'mercurial.thirdparty.zope',
             'mercurial.thirdparty.zope.interface',
             'mercurial.utils',
             'mercurial.revlogutils',
             'mercurial.testing',
             'hgext', 'hgext.convert', 'hgext.fsmonitor',
             'hgext.fastannotate',
             'hgext.fsmonitor.pywatchman',
             'hgext.infinitepush',
             'hgext.highlight',
             'hgext.largefiles', 'hgext.lfs', 'hgext.narrow',
             'hgext.zeroconf', 'hgext3rd',
             'hgdemandimport']
 if sys.version_info[0] == 2:
     packages.extend(['mercurial.thirdparty.concurrent',
                      'mercurial.thirdparty.concurrent.futures'])
 
 common_depends = ['mercurial/bitmanipulation.h',
                   'mercurial/compat.h',
                   'mercurial/cext/util.h']
 common_include_dirs = ['mercurial']
 
 osutil_cflags = []
 osutil_ldflags = []
 
 # platform specific macros
 for plat, func in [('bsd', 'setproctitle')]:
     if re.search(plat, sys.platform) and hasfunction(new_compiler(), func):
         osutil_cflags.append('-DHAVE_%s' % func.upper())
 
 for plat, macro, code in [
     ('bsd|darwin', 'BSD_STATFS', '''
      #include <sys/param.h>
      #include <sys/mount.h>
      int main() { struct statfs s; return sizeof(s.f_fstypename); }
      '''),
     ('linux', 'LINUX_STATFS', '''
      #include <linux/magic.h>
      #include <sys/vfs.h>
      int main() { struct statfs s; return sizeof(s.f_type); }
      '''),
 ]:
     if re.search(plat, sys.platform) and cancompile(new_compiler(), code):
         osutil_cflags.append('-DHAVE_%s' % macro)
 
 if sys.platform == 'darwin':
     osutil_ldflags += ['-framework', 'ApplicationServices']
 
 xdiff_srcs = [
     'mercurial/thirdparty/xdiff/xdiffi.c',
     'mercurial/thirdparty/xdiff/xprepare.c',
     'mercurial/thirdparty/xdiff/xutils.c',
 ]
 
 xdiff_headers = [
     'mercurial/thirdparty/xdiff/xdiff.h',
     'mercurial/thirdparty/xdiff/xdiffi.h',
     'mercurial/thirdparty/xdiff/xinclude.h',
     'mercurial/thirdparty/xdiff/xmacros.h',
     'mercurial/thirdparty/xdiff/xprepare.h',
     'mercurial/thirdparty/xdiff/xtypes.h',
     'mercurial/thirdparty/xdiff/xutils.h',
 ]
 
+class RustExtension(Extension):
+    """A C Extension, conditionnally enhanced with Rust code.
+
+    if iswithrustextensions is False, does nothing else than plain Extension
+    """
+
+    rusttargetdir = os.path.join('rust', 'target', 'release')
+
+    def __init__(self, mpath, sources, rustlibname, subcrate, **kw):
+        Extension.__init__(self, mpath, sources, **kw)
+        if not iswithrustextensions:
+            return
+        srcdir = self.rustsrcdir = os.path.join('rust', subcrate)
+        self.libraries.append(rustlibname)
+        self.extra_compile_args.append('-DWITH_RUST')
+
+        # adding Rust source and control files to depends so that the extension
+        # gets rebuilt if they've changed
+        self.depends.append(os.path.join(srcdir, 'Cargo.toml'))
+        cargo_lock = os.path.join(srcdir, 'Cargo.lock')
+        if os.path.exists(cargo_lock):
+            self.depends.append(cargo_lock)
+        for dirpath, subdir, fnames in os.walk(os.path.join(srcdir, 'src')):
+            self.depends.extend(os.path.join(dirpath, fname)
+                                for fname in fnames
+                                if os.path.splitext(fname)[1] == '.rs')
+
+    def rustbuild(self):
+        if not iswithrustextensions:
+            return
+        env = os.environ.copy()
+        if 'HGTEST_RESTOREENV' in env:
+            # Mercurial tests change HOME to a temporary directory,
+            # but, if installed with rustup, the Rust toolchain needs
+            # HOME to be correct (otherwise the 'no default toolchain'
+            # error message is issued and the build fails).
+            # This happens currently with test-hghave.t, which does
+            # invoke this build.
+
+            # Unix only fix (os.path.expanduser not really reliable if
+            # HOME is shadowed like this)
+            import pwd
+            env['HOME'] = pwd.getpwuid(os.getuid()).pw_dir
+
+        subprocess.check_call(['cargo', 'build', '-vv', '--release'],
+                              env=env, cwd=self.rustsrcdir)
+        self.library_dirs.append(self.rusttargetdir)
+
 extmodules = [
     Extension('mercurial.cext.base85', ['mercurial/cext/base85.c'],
               include_dirs=common_include_dirs,
               depends=common_depends),
     Extension('mercurial.cext.bdiff', ['mercurial/bdiff.c',
                                        'mercurial/cext/bdiff.c'] + xdiff_srcs,
               include_dirs=common_include_dirs,
               depends=common_depends + ['mercurial/bdiff.h'] + xdiff_headers),
     Extension('mercurial.cext.mpatch', ['mercurial/mpatch.c',
                                         'mercurial/cext/mpatch.c'],
               include_dirs=common_include_dirs,
               depends=common_depends),
-    Extension('mercurial.cext.parsers', ['mercurial/cext/charencode.c',
-                                         'mercurial/cext/dirs.c',
-                                         'mercurial/cext/manifest.c',
-                                         'mercurial/cext/parsers.c',
-                                         'mercurial/cext/pathencode.c',
-                                         'mercurial/cext/revlog.c'],
-              include_dirs=common_include_dirs,
-              depends=common_depends + ['mercurial/cext/charencode.h']),
+    RustExtension('mercurial.cext.parsers', ['mercurial/cext/charencode.c',
+                                             'mercurial/cext/dirs.c',
+                                             'mercurial/cext/manifest.c',
+                                             'mercurial/cext/parsers.c',
+                                             'mercurial/cext/pathencode.c',
+                                             'mercurial/cext/revlog.c'],
+                  'hgdirectffi',
+                  'hg-direct-ffi',
+                  include_dirs=common_include_dirs,
+                  depends=common_depends + ['mercurial/cext/charencode.h',
+                                            'mercurial/rust/src/lib.rs',
+                                            'mercurial/rust/src/ancestors.rs',
+                                            'mercurial/rust/src/cpython.rs']),
     Extension('mercurial.cext.osutil', ['mercurial/cext/osutil.c'],
               include_dirs=common_include_dirs,
               extra_compile_args=osutil_cflags,
               extra_link_args=osutil_ldflags,
               depends=common_depends),
     Extension(
         'mercurial.thirdparty.zope.interface._zope_interface_coptimizations', [
         'mercurial/thirdparty/zope/interface/_zope_interface_coptimizations.c',
         ]),
     Extension('hgext.fsmonitor.pywatchman.bser',
               ['hgext/fsmonitor/pywatchman/bser.c']),
     ]
 
 sys.path.insert(0, 'contrib/python-zstandard')
 import setup_zstd
 extmodules.append(setup_zstd.get_c_extension(
     name='mercurial.zstd',
     root=os.path.abspath(os.path.dirname(__file__))))
 
 try:
     from distutils import cygwinccompiler
 
     # the -mno-cygwin option has been deprecated for years
     mingw32compilerclass = cygwinccompiler.Mingw32CCompiler
 
     class HackedMingw32CCompiler(cygwinccompiler.Mingw32CCompiler):
         def __init__(self, *args, **kwargs):
             mingw32compilerclass.__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
 
 if os.name == 'nt':
     # Allow compiler/linker flags to be added to Visual Studio builds.  Passing
     # extra_link_args to distutils.extensions.Extension() doesn't have any
     # effect.
     from distutils import msvccompiler
 
     msvccompilerclass = msvccompiler.MSVCCompiler
 
     class HackedMSVCCompiler(msvccompiler.MSVCCompiler):
         def initialize(self):
             msvccompilerclass.initialize(self)
             # "warning LNK4197: export 'func' specified multiple times"
             self.ldflags_shared.append('/ignore:4197')
             self.ldflags_shared_debug.append('/ignore:4197')
 
     msvccompiler.MSVCCompiler = HackedMSVCCompiler
 
 packagedata = {'mercurial': ['locale/*/LC_MESSAGES/hg.mo',
                              'help/*.txt',
                              'help/internals/*.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 = []
 
 # distutils expects version to be str/unicode. Converting it to
 # unicode on Python 2 still works because it won't contain any
 # non-ascii bytes and will be implicitly converted back to bytes
 # when operated on.
 assert isinstance(version, bytes)
 setupversion = version.decode('ascii')
 
 extra = {}
 
 if issetuptools:
     extra['python_requires'] = supportedpy
 if py2exeloaded:
     extra['console'] = [
         {'script':'hg',
          'copyright':'Copyright (C) 2005-2018 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))
     # put dlls in sub directory so that they won't pollute PATH
     extra['zipfile'] = 'lib/library.zip'
 
 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(b'+', 1)[0]
 
 if sys.platform == 'darwin' and os.path.exists('/usr/bin/xcodebuild'):
     version = runcmd(['/usr/bin/xcodebuild', '-version'], {})[1].splitlines()
     if version:
         version = version[0]
         if sys.version_info[0] == 3:
             version = version.decode('utf-8')
         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='https://mercurial-scm.org/',
       download_url='https://mercurial-scm.org/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,
       ext_modules=extmodules,
       data_files=datafiles,
       package_data=packagedata,
       cmdclass=cmdclass,
       distclass=hgdist,
       options={
           'py2exe': {
               'packages': [
                   'hgdemandimport',
                   'hgext',
                   'email',
                   # implicitly imported per module policy
                   # (cffi wouldn't be used as a frozen exe)
                   'mercurial.cext',
                   #'mercurial.cffi',
                   'mercurial.pure',
               ],
           },
           'bdist_mpkg': {
               'zipdist': False,
               'license': 'COPYING',
               'readme': 'contrib/packaging/macosx/Readme.html',
               'welcome': 'contrib/packaging/macosx/Welcome.html',
           },
       },
       **extra)