comparison mercurial/cext/revlog.c @ 39291:9f097214fbf3

index: embed nodetree in index object to avoid reference cycle

Since the index has a reference to a nodetree and the nodetree has a
reference back to the index, there is a reference cycle, so the index
(and its nodetree) can never be freed. This patch fixes that by making
"nodetree" a plan C struct that the index can embed, and also
introduces a new "nodetreeObject" that is a Python type wrapping the
nodetree struct.

Thanks to Yuya for noticing this and for suggesting the solution.

All tests passed on the first attempt once it compiled (I guess C is
like Haskell in this regard?).

Differential Revision: https://phab.mercurial-scm.org/D4372

39290:286a666365ec

 * Positive value is index of the next node in the trie
 * Negative value is a leaf: -(rev + 2)
 * Zero is empty
 */
typedef struct {
	PyObject_HEAD
	indexObject *index;
	nodetreenode *nodes;
	unsigned length;     /* # nodes in use */
	unsigned capacity;   /* # nodes allocated */
	int depth;           /* maximum depth of tree */
	int splits;          /* # splits performed */
} nodetree;

/*
 * This class has two behaviors.
 *
 * When used in a list-like way (with integer keys), we decode an

	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 ntrev;             /* last rev scanned */
	int ntlookups;         /* # lookups */
	int ntmisses;          /* # lookups that miss the cache */
	int inlined;
};

	}

	if (PyList_Append(self->added, obj) == -1)
		return NULL;

	if (self->nt)
		nt_insert(self->nt, node, (int)len);

	Py_CLEAR(self->headrevs);
	Py_RETURN_NONE;
}

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

	}

	return -1;
}

static PyObject *nt_insert_py(nodetree *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->index);
	if (rev < 0 || rev >= length) {
		PyErr_SetString(PyExc_ValueError, "revlog index out of range");
		return NULL;
	}
	node = index_node_existing(self->index, rev);
	if (nt_insert(self, node, (int)rev) == -1)
		return NULL;
	Py_RETURN_NONE;
}

static int nt_delete_node(nodetree *self, const char *node)

{
	/* Initialize before overflow-checking to avoid nt_dealloc() crash. */
	self->nodes = NULL;

	self->index = index;
	Py_INCREF(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;

	return 0;
}

static PyTypeObject indexType;

static int nt_init_py(nodetree *self, PyObject *args)
{
	PyObject *index;
	unsigned capacity;
	if (!PyArg_ParseTuple(args, "O!I", &indexType, &index, &capacity))
		return -1;
	return nt_init(self, (indexObject*)index, capacity);
}

static int nt_partialmatch(nodetree *self, const char *node,
			   Py_ssize_t nodelen)
{

	 */
	PyErr_SetString(PyExc_Exception, "broken node tree");
	return -3;
}

static PyObject *nt_shortest_py(nodetree *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, node);
	if (length == -3)
		return NULL;
	if (length == -2) {
		raise_revlog_error();
		return NULL;

	return PyInt_FromLong(length);
}

static void nt_dealloc(nodetree *self)
{
	Py_XDECREF(self->index);
	free(self->nodes);
	self->nodes = NULL;
	PyObject_Del(self);
}

static PyMethodDef nt_methods[] = {
	{"insert", (PyCFunction)nt_insert_py, METH_VARARGS,
	 "insert an index entry"},
	{"shortest", (PyCFunction)nt_shortest_py, 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(nodetree) ,         /* tp_basicsize */
	0,                         /* tp_itemsize */
	(destructor)nt_dealloc,    /* tp_dealloc */
	0,                         /* tp_print */
	0,                         /* tp_getattr */
	0,                         /* tp_setattr */
	0,                         /* tp_compare */
	0,                         /* tp_repr */

	0,                         /* tp_clear */
	0,                         /* tp_richcompare */
	0,                         /* tp_weaklistoffset */
	0,                         /* tp_iter */
	0,                         /* tp_iternext */
	nt_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)nt_init_py,      /* tp_init */
	0,                         /* tp_alloc */
};

static int index_init_nt(indexObject *self)
{
	if (self->nt == NULL) {
		self->nt = PyObject_New(nodetree, &nodetreeType);
		if (self->nt == NULL) {
			return -1;
		}
		if (nt_init(self->nt, self, (int)self->raw_length) == -1) {
			nt_dealloc(self->nt);
			self->nt = NULL;
			return -1;
		}
		if (nt_insert(self->nt, nullid, -1) == -1) {
			nt_dealloc(self->nt);
			self->nt = NULL;
			return -1;
		}
		self->ntrev = (int)index_length(self);
		self->ntlookups = 1;
		self->ntmisses = 0;
	}
	return 0;

	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,

		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;

	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;

	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;

	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;

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

				"revlog index deletion indices are invalid");
		return -1;
	}

	if (start < self->length) {
		if (self->nt) {
			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->raw_length = start;
		}
		goto done;
	}

	if (self->nt) {
		index_invalidate_added(self, start - self->length);
		if (self->ntrev > start)
			self->ntrev = (int)start;
	}
	if (self->added)

	if (node_check(item, &node) == -1)
		return -1;

	if (value == NULL)
		return self->nt ? 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.

	self->data = NULL;
	memset(&self->buf, 0, sizeof(self->buf));
	self->headrevs = NULL;
	self->filteredrevs = Py_None;
	Py_INCREF(Py_None);
	self->nt = NULL;
	self->offsets = NULL;

	if (!PyArg_ParseTuple(args, "OO", &data_obj, &inlined_obj))
		return -1;
	if (!PyObject_CheckBuffer(data_obj)) {

	}
	if (self->offsets) {
		PyMem_Free((void *)self->offsets);
		self->offsets = NULL;
	}
	if (self->nt != NULL) {
		nt_dealloc(self->nt);
	}
	self->nt = NULL;
	Py_CLEAR(self->headrevs);
}

static PyObject *index_clearcaches(indexObject *self)
{

		PyBuffer_Release(&self->buf);
		memset(&self->buf, 0, sizeof(self->buf));
	}
	Py_XDECREF(self->data);
	Py_XDECREF(self->added);
	Py_XDECREF(self->nt);
	PyObject_Del(self);
}

static PySequenceMethods index_sequence_methods = {
	(lenfunc)index_length,   /* sq_length */

39291:9f097214fbf3

 * 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

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

	}

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

		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;

	}

	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)

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

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

	 */
	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(nodetree) ,         /* 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_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;

	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,

		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;

	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;

	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;

	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;

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

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

	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.

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

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

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