mercurial/cext/revlog.c

40561:5c14bf0c5be3

 * 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.
 *

 * 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)
{

	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");

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);

		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

	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);
	}

	PyObject *t = NULL;

	if (obj == NULL)
		return NULL;

#define istat(__n, __d) \
	do { \
		s = PyBytes_FromString(__d); \
		t = PyInt_FromSsize_t(self->__n); \
		if (!s || !t) \
			goto bail; \
		if (PyDict_SetItem(obj, s, t) == -1) \
			goto bail; \
		Py_CLEAR(s); \
		Py_CLEAR(t); \
	} while (0)

	if (self->added) {
		Py_ssize_t len = PyList_GET_SIZE(self->added);
		s = PyBytes_FromString("index entries added");

	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;

			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;
			}
		}
	}

			/* 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);

	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;

	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);

	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;

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;
		}

	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");

		}
		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);

		}
	}

	if (iterrev == stoprev) {
		stopped = 1;
	}
	else {
		PyObject *value = PyInt_FromLong(iterrev);
		if (value == NULL) {
			goto bail;
		}
		if (PyList_Append(chain, value)) {

	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;
}

 *   -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)

	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;

		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)) {

	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)
{

	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);
}

/*

	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) {

 *
 *   -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;

}

/*
 * 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)

 * 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;

			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;

	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));

						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;

		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 */

			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:;
	}

	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) {

		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;
}

 * 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)

	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;

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));

	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;

	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:

 */
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 */
	Py_ssize_t initrevslen, long *initrevs,
	long stoprev,
	int inclusive);
void rustlazyancestors_drop(rustlazyancestorsObject *self);
int rustlazyancestors_next(rustlazyancestorsObject *self);
int rustlazyancestors_contains(rustlazyancestorsObject *self, long rev);

/* 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;
	}

		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 int rustla_contains(rustlazyancestorsObject *self, PyObject *rev) {
	if (!(PyInt_Check(rev))) {
		return 0;
	}
	return rustlazyancestors_contains(self->iter, PyInt_AS_LONG(rev));
}

static PySequenceMethods rustla_sequence_methods = {
	0,                       /* sq_length */
	0,                       /* sq_concat */
	0,                       /* sq_repeat */
	0,                       /* sq_item */
	0,                       /* sq_slice */
	0,                       /* sq_ass_item */
	0,                       /* sq_ass_slice */
	(objobjproc)rustla_contains, /* sq_contains */
};

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 */
	&rustla_sequence_methods,  /* 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)
{

		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

}

40562:e5ad3ef90aa1

 * 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.
 *

 * 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)
{

	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");

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);

		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

	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);
	}

	PyObject *t = NULL;

	if (obj == NULL)
		return NULL;

#define istat(__n, __d)                                                        \
	do {                                                                   \
		s = PyBytes_FromString(__d);                                   \
		t = PyInt_FromSsize_t(self->__n);                              \
		if (!s || !t)                                                  \
			goto bail;                                             \
		if (PyDict_SetItem(obj, s, t) == -1)                           \
			goto bail;                                             \
		Py_CLEAR(s);                                                   \
		Py_CLEAR(t);                                                   \
	} while (0)

	if (self->added) {
		Py_ssize_t len = PyList_GET_SIZE(self->added);
		s = PyBytes_FromString("index entries added");

	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;

			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;
			}
		}
	}

			/* 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);

	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;

	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);

	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;

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;
		}

	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");

		}
		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);

		}
	}

	if (iterrev == stoprev) {
		stopped = 1;
	} else {
		PyObject *value = PyInt_FromLong(iterrev);
		if (value == NULL) {
			goto bail;
		}
		if (PyList_Append(chain, value)) {

	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;
}

 *   -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)

	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;

		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)) {

	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)
{

	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);
}

/*

	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) {

 *
 *   -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;

}

/*
 * 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)

 * 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;

			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;

	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));

						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;

		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 */

			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:;
	}

	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) {

		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;
}

 * 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)

	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;

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));

	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;

	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:

 */
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 */
                       Py_ssize_t initrevslen, long *initrevs, long stoprev,
                       int inclusive);
void rustlazyancestors_drop(rustlazyancestorsObject *self);
int rustlazyancestors_next(rustlazyancestorsObject *self);
int rustlazyancestors_contains(rustlazyancestorsObject *self, long rev);

/* 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;
	}

		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 int rustla_contains(rustlazyancestorsObject *self, PyObject *rev)
{
	if (!(PyInt_Check(rev))) {
		return 0;
	}
	return rustlazyancestors_contains(self->iter, PyInt_AS_LONG(rev));
}

static PySequenceMethods rustla_sequence_methods = {
    0,                           /* sq_length */
    0,                           /* sq_concat */
    0,                           /* sq_repeat */
    0,                           /* sq_item */
    0,                           /* sq_slice */
    0,                           /* sq_ass_item */
    0,                           /* sq_ass_slice */
    (objobjproc)rustla_contains, /* sq_contains */
};

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 */
    &rustla_sequence_methods,                       /* 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)
{

		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
}