mercurial/cext/revlog.c

46140:ec14c37958ec

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

 */
struct indexObjectStruct {
	PyObject_HEAD
	    /* Type-specific fields go here. */
	    PyObject *data;     /* raw bytes of index */
	Py_buffer buf;          /* buffer of data */
	const char **offsets;   /* populated on demand */
	Py_ssize_t length;      /* current on-disk number of elements */
	unsigned new_length;    /* number of added elements */
	unsigned added_length;  /* space reserved for added elements */

static Py_ssize_t index_length(const indexObject *self)
{
	return self->length + self->new_length;
}

static PyObject *nullentry = NULL;
static const char nullid[20] = {0};
static const Py_ssize_t nullrev = -1;

static Py_ssize_t inline_scan(indexObject *self, const char **offsets);

static int index_find_node(indexObject *self, const char *node,
                           Py_ssize_t nodelen);

#if LONG_MAX == 0x7fffffffL
static const char *const tuple_format = PY23("Kiiiiiis#", "Kiiiiiiy#");
#else
static const char *const tuple_format = PY23("kiiiiiis#", "kiiiiiiy#");

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

	if (pos == nullrev) {
		Py_INCREF(nullentry);
		return nullentry;
	}

	if (pos < 0 || pos >= length) {
		PyErr_SetString(PyExc_IndexError, "revlog index out of range");
		return NULL;

	parent_2 = getbe32(data + 28);
	c_node_id = data + 32;

	return Py_BuildValue(tuple_format, offset_flags, comp_len, uncomp_len,
	                     base_rev, link_rev, parent_1, parent_2, c_node_id,
	                     (Py_ssize_t)20);
}

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

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

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

	                      &uncomp_len, &base_rev, &link_rev, &parent_1,
	                      &parent_2, &c_node_id, &c_node_id_len)) {
		PyErr_SetString(PyExc_TypeError, "8-tuple required");
		return NULL;
	}
	if (c_node_id_len != 20 && c_node_id_len != 32) {
		PyErr_SetString(PyExc_TypeError, "invalid node");
		return NULL;
	}

	if (self->new_length == self->added_length) {

	}
	iterator = PyObject_GetIter(roots);
	if (iterator == NULL)
		return -2;
	while ((item = PyIter_Next(iterator))) {
		if (node_check(item, &node) == -1)
			goto failed;
		rev = index_find_node(self, node, 20);
		/* null is implicitly public, so negative is invalid */
		if (rev < 0 || rev >= len)
			goto failed;
		phases[rev] = phase;
		if (minrev == -1 || minrev > rev)

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

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

			    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)

	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;

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

	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;

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

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

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

			return NULL;
		}
		return index_get(self, idx);
	}

	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;

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

		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;

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

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

static PyObject *index_m_rev(indexObject *self, PyObject *val)
{
	char *node;
	int rev;

	if (node_check(val, &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;

	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;

	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;

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

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

	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, (Py_ssize_t)20);
	}
	if (nullentry)
		PyObject_GC_UnTrack(nullentry);

	caps = PyCapsule_New(&CAPI, "mercurial.cext.parsers.revlog_CAPI", NULL);
	if (caps != NULL)
		PyModule_AddObject(mod, "revlog_CAPI", caps);
}

46141:41733a1c3532

 * Zero is empty
 */
typedef struct {
	indexObject *index;
	nodetreenode *nodes;
	Py_ssize_t nodelen;
	unsigned length;   /* # nodes in use */
	unsigned capacity; /* # nodes allocated */
	int depth;         /* maximum depth of tree */
	int splits;        /* # splits performed */
} nodetree;

 */
struct indexObjectStruct {
	PyObject_HEAD
	    /* Type-specific fields go here. */
	    PyObject *data;     /* raw bytes of index */
	Py_ssize_t nodelen;     /* digest size of the hash, 20 for SHA-1 */
	PyObject *nullentry;    /* fast path for references to null */
	Py_buffer buf;          /* buffer of data */
	const char **offsets;   /* populated on demand */
	Py_ssize_t length;      /* current on-disk number of elements */
	unsigned new_length;    /* number of added elements */
	unsigned added_length;  /* space reserved for added elements */

static Py_ssize_t index_length(const indexObject *self)
{
	return self->length + self->new_length;
}

static const char nullid[32] = {0};
static const Py_ssize_t nullrev = -1;

static Py_ssize_t inline_scan(indexObject *self, const char **offsets);

static int index_find_node(indexObject *self, const char *node);

#if LONG_MAX == 0x7fffffffL
static const char *const tuple_format = PY23("Kiiiiiis#", "Kiiiiiiy#");
#else
static const char *const tuple_format = PY23("kiiiiiis#", "kiiiiiiy#");

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

	if (pos == nullrev) {
		Py_INCREF(self->nullentry);
		return self->nullentry;
	}

	if (pos < 0 || pos >= length) {
		PyErr_SetString(PyExc_IndexError, "revlog index out of range");
		return NULL;

	parent_2 = getbe32(data + 28);
	c_node_id = data + 32;

	return Py_BuildValue(tuple_format, offset_flags, comp_len, uncomp_len,
	                     base_rev, link_rev, parent_1, parent_2, c_node_id,
	                     self->nodelen);
}

/*
 * Return the hash of 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;

	data = index_deref(self, pos);
	return data ? data + 32 : NULL;
}

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

	return node;
}

static int nt_insert(nodetree *self, const char *node, int rev);

static int node_check(Py_ssize_t nodelen, PyObject *obj, char **node)
{
	Py_ssize_t thisnodelen;
	if (PyBytes_AsStringAndSize(obj, node, &thisnodelen) == -1)
		return -1;
	if (nodelen == thisnodelen)
		return 0;
	PyErr_Format(PyExc_ValueError, "node len %zd != expected node len %zd",
	             thisnodelen, nodelen);
	return -1;
}

static PyObject *index_append(indexObject *self, PyObject *obj)
{

	                      &uncomp_len, &base_rev, &link_rev, &parent_1,
	                      &parent_2, &c_node_id, &c_node_id_len)) {
		PyErr_SetString(PyExc_TypeError, "8-tuple required");
		return NULL;
	}
	if (c_node_id_len != self->nodelen) {
		PyErr_SetString(PyExc_TypeError, "invalid node");
		return NULL;
	}

	if (self->new_length == self->added_length) {

	}
	iterator = PyObject_GetIter(roots);
	if (iterator == NULL)
		return -2;
	while ((item = PyIter_Next(iterator))) {
		if (node_check(self->nodelen, item, &node) == -1)
			goto failed;
		rev = index_find_node(self, node);
		/* null is implicitly public, so negative is invalid */
		if (rev < 0 || rev >= len)
			goto failed;
		phases[rev] = phase;
		if (minrev == -1 || minrev > rev)

                   int hex)
{
	int (*getnybble)(const char *, Py_ssize_t) = hex ? hexdigit : nt_level;
	int level, maxlevel, off;

	/* If the input is binary, do a fast check for the nullid first. */
	if (!hex && nodelen == self->nodelen && node[0] == '\0' &&
	    node[1] == '\0' && memcmp(node, nullid, self->nodelen) == 0)
		return -1;

	if (hex)
		maxlevel = nodelen;
	else
		maxlevel = 2 * nodelen;
	if (maxlevel > 2 * self->nodelen)
		maxlevel = 2 * self->nodelen;

	for (level = off = 0; level < maxlevel; level++) {
		int k = getnybble(node, level);
		nodetreenode *n = &self->nodes[off];
		int v = n->children[k];

static int nt_insert(nodetree *self, const char *node, int rev)
{
	int level = 0;
	int off = 0;

	while (level < 2 * self->nodelen) {
		int k = nt_level(node, level);
		nodetreenode *n;
		int v;

		n = &self->nodes[off];

			    index_node_existing(self->index, -(v + 2));
			int noff;

			if (oldnode == NULL)
				return -1;
			if (!memcmp(oldnode, node, self->nodelen)) {
				n->children[k] = -rev - 2;
				return 0;
			}
			noff = nt_new(self);
			if (noff == -1)

	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->nodelen = index->nodelen;
	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;

 */
static int nt_shortest(nodetree *self, const char *node)
{
	int level, off;

	for (level = off = 0; level < 2 * self->nodelen; 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, self->nodelen) != 0)
				/*
				 * Found a unique prefix, but it wasn't for the
				 * requested node (i.e the requested node does
				 * not exist).
				 */

	char *node;
	int length;

	if (!PyArg_ParseTuple(args, "O", &val))
		return NULL;
	if (node_check(self->nt.nodelen, val, &node) == -1)
		return NULL;

	length = nt_shortest(&self->nt, node);
	if (length == -3)
		return NULL;

 *
 *   -3: error (exception set)
 *   -2: not found (no exception set)
 * rest: valid rev
 */
static int index_find_node(indexObject *self, const char *node)
{
	int rev;

	if (index_init_nt(self) == -1)
		return -3;

	self->ntlookups++;
	rev = nt_find(&self->nt, node, self->nodelen, 0);
	if (rev >= -1)
		return rev;

	/*
	 * For the first handful of lookups, we scan the entire index,

	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, self->nodelen) == 0) {
				if (nt_insert(&self->nt, n, rev) == -1)
					return -3;
				break;
			}
		}

				return -3;
			if (nt_insert(&self->nt, n, rev) == -1) {
				self->ntrev = rev + 1;
				return -3;
			}
			if (memcmp(node, n, self->nodelen) == 0) {
				break;
			}
		}
		self->ntrev = rev;
	}

			return NULL;
		}
		return index_get(self, idx);
	}

	if (node_check(self->nodelen, value, &node) == -1)
		return NULL;
	rev = index_find_node(self, node);
	if (rev >= -1)
		return PyInt_FromLong(rev);
	if (rev == -2)
		raise_revlog_error();
	return NULL;

	if (nodelen < 1) {
		PyErr_SetString(PyExc_ValueError, "key too short");
		return NULL;
	}

	if (nodelen > 2 * self->nodelen) {
		PyErr_SetString(PyExc_ValueError, "key too long");
		return NULL;
	}

	for (i = 0; i < nodelen; i++)

		raise_revlog_error();
		return NULL;
	case -2:
		Py_RETURN_NONE;
	case -1:
		return PyBytes_FromStringAndSize(nullid, self->nodelen);
	}

	fullnode = index_node_existing(self, rev);
	if (fullnode == NULL) {
		return NULL;
	}
	return PyBytes_FromStringAndSize(fullnode, self->nodelen);
}

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(self->nodelen, val, &node) == -1)
		return NULL;

	self->ntlookups++;
	if (index_init_nt(self) == -1)
		return NULL;

	char *node;
	int rev;

	if (!PyArg_ParseTuple(args, "O", &val))
		return NULL;
	if (node_check(self->nodelen, val, &node) == -1)
		return NULL;
	rev = index_find_node(self, node);
	if (rev == -3)
		return NULL;
	if (rev == -2)
		Py_RETURN_NONE;
	return PyInt_FromLong(rev);

			return -1;
		}
		return rev >= -1 && rev < index_length(self);
	}

	if (node_check(self->nodelen, value, &node) == -1)
		return -1;

	switch (index_find_node(self, node)) {
	case -3:
		return -1;
	case -2:
		return 0;
	default:

static PyObject *index_m_rev(indexObject *self, PyObject *val)
{
	char *node;
	int rev;

	if (node_check(self->nodelen, val, &node) == -1)
		return NULL;
	rev = index_find_node(self, node);
	if (rev >= -1)
		return PyInt_FromLong(rev);
	if (rev == -2)
		raise_revlog_error();
	return NULL;

	long rev;

	if (PySlice_Check(item) && value == NULL)
		return index_slice_del(self, item);

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

	if (value == NULL)
		return self->ntinitialized ? nt_delete_node(&self->nt, node)
		                           : 0;

	self->headrevs = NULL;
	self->filteredrevs = Py_None;
	Py_INCREF(Py_None);
	self->ntinitialized = 0;
	self->offsets = NULL;
	self->nodelen = 20;
	self->nullentry = 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 (self->nodelen < 20 || self->nodelen > sizeof(nullid)) {
		PyErr_SetString(PyExc_RuntimeError, "unsupported node size");
		return -1;
	}

	self->nullentry = Py_BuildValue(PY23("iiiiiiis#", "iiiiiiiy#"), 0, 0, 0,
	                                -1, -1, -1, -1, nullid, self->nodelen);
	if (!self->nullentry)
		return -1;
	PyObject_GC_UnTrack(self->nullentry);

	if (PyObject_GetBuffer(data_obj, &self->buf, PyBUF_SIMPLE) == -1)
		return -1;
	size = self->buf.len;

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

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

	if (PyType_Ready(&nodetreeType) < 0)
		return;
	Py_INCREF(&nodetreeType);
	PyModule_AddObject(mod, "nodetree", (PyObject *)&nodetreeType);

	caps = PyCapsule_New(&CAPI, "mercurial.cext.parsers.revlog_CAPI", NULL);
	if (caps != NULL)
		PyModule_AddObject(mod, "revlog_CAPI", caps);
}