rank: add a "rank" value to the revlog-entry tuple

The rank of a revision is the size of sub-graph it defines as a head. In other
words, the rank of X is the size of `ancestors(X)` (X included).

This is a property that can help various algorithm and we intend to store it in
changelog-v2. We start with adding this new information to the "entry tuple",
with a default value. We will start to compute and persist the rank later.

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

mercurial/cext/revlog.c

@@ -1,3062 +1,3066 b''
 /*
  parsers.c - efficient content parsing
 
  Copyright 2008 Olivia Mackall <[e-mail]> and others
 
  This software may be used and distributed according to the terms of
  the GNU General Public License, incorporated herein by reference.
 */
 
 #define PY_SSIZE_T_CLEAN
 #include <Python.h>
 #include <assert.h>
 #include <ctype.h>
 #include <limits.h>
 #include <stddef.h>
 #include <stdlib.h>
 #include <string.h>
 #include <structmember.h>
 
 #include "bitmanipulation.h"
 #include "charencode.h"
 #include "compat.h"
 #include "revlog.h"
 #include "util.h"
 
 #ifdef IS_PY3K
 /* The mapping of Python types is meant to be temporary to get Python
  * 3 to compile. We should remove this once Python 3 support is fully
  * supported and proper types are used in the extensions themselves. */
 #define PyInt_Check PyLong_Check
 #define PyInt_FromLong PyLong_FromLong
 #define PyInt_FromSsize_t PyLong_FromSsize_t
 #define PyInt_AsLong PyLong_AsLong
 #endif
 
 typedef struct indexObjectStruct indexObject;
 
 typedef struct {
 	int children[16];
 } nodetreenode;
 
 typedef struct {
 	int abi_version;
 	Py_ssize_t (*index_length)(const indexObject *);
 	const char *(*index_node)(indexObject *, Py_ssize_t);
 	int (*index_parents)(PyObject *, int, int *);
 } Revlog_CAPI;
 
 /*
  * A base-16 trie for fast node->rev mapping.
  *
  * Positive value is index of the next node in the trie
  * Negative value is a leaf: -(rev + 2)
  * Zero is empty
  */
 typedef struct {
 	indexObject *index;
 	nodetreenode *nodes;
 	Py_ssize_t nodelen;
 	size_t length;   /* # nodes in use */
 	size_t capacity; /* # nodes allocated */
 	int depth;       /* maximum depth of tree */
 	int splits;      /* # splits performed */
 } nodetree;
 
 typedef struct {
 	PyObject_HEAD /* ; */
 	    nodetree nt;
 } nodetreeObject;
 
 /*
  * This class has two behaviors.
  *
  * When used in a list-like way (with integer keys), we decode an
  * entry in a RevlogNG index file on demand. We have limited support for
  * integer-keyed insert and delete, only at elements right before the
  * end.
  *
  * 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_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 */
 	char *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;
 	long entry_size; /* size of index headers. Differs in v1 v.s. v2 format
 	                  */
 	long rust_ext_compat; /* compatibility with being used in rust
 	                         extensions */
 	char format_version;  /* size of index headers. Differs in v1 v.s. v2
 	                         format */
 };
 
 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#KiBB", "Kiiiiiiy#KiBB");
+static const char *const tuple_format =
+    PY23("Kiiiiiis#KiBBi", "Kiiiiiiy#KiBBi");
 #else
-static const char *const tuple_format = PY23("kiiiiiis#kiBB", "kiiiiiiy#kiBB");
+static const char *const tuple_format =
+    PY23("kiiiiiis#kiBBi", "kiiiiiiy#kiBBi");
 #endif
 
 /* A RevlogNG v1 index entry is 64 bytes long. */
 static const long v1_entry_size = 64;
 
 /* A Revlogv2 index entry is 96 bytes long. */
 static const long v2_entry_size = 96;
 
 static const long format_v1 = 1; /* Internal only, could be any number */
 static const long format_v2 = 2; /* Internal only, could be any number */
 
 static const char comp_mode_inline = 2;
+static const char rank_unknown = -1;
 
 static void raise_revlog_error(void)
 {
 	PyObject *mod = NULL, *dict = NULL, *errclass = NULL;
 
 	mod = PyImport_ImportModule("mercurial.error");
 	if (mod == NULL) {
 		goto cleanup;
 	}
 
 	dict = PyModule_GetDict(mod);
 	if (dict == NULL) {
 		goto cleanup;
 	}
 	Py_INCREF(dict);
 
 	errclass = PyDict_GetItemString(dict, "RevlogError");
 	if (errclass == NULL) {
 		PyErr_SetString(PyExc_SystemError,
 		                "could not find RevlogError");
 		goto cleanup;
 	}
 
 	/* value of exception is ignored by callers */
 	PyErr_SetString(errclass, "RevlogError");
 
 cleanup:
 	Py_XDECREF(dict);
 	Py_XDECREF(mod);
 }
 
 /*
  * Return a pointer to the beginning of a RevlogNG record.
  */
 static const char *index_deref(indexObject *self, Py_ssize_t pos)
 {
 	if (pos >= self->length)
 		return self->added + (pos - self->length) * self->entry_size;
 
 	if (self->inlined && pos > 0) {
 		if (self->offsets == NULL) {
 			Py_ssize_t ret;
 			self->offsets =
 			    PyMem_Malloc(self->length * sizeof(*self->offsets));
 			if (self->offsets == NULL)
 				return (const char *)PyErr_NoMemory();
 			ret = inline_scan(self, self->offsets);
 			if (ret == -1) {
 				return NULL;
 			};
 		}
 		return self->offsets[pos];
 	}
 
 	return (const char *)(self->buf.buf) + pos * self->entry_size;
 }
 
 /*
  * Get parents of the given rev.
  *
  * The specified rev must be valid and must not be nullrev. A returned
  * parent revision may be nullrev, but is guaranteed to be in valid range.
  */
 static inline int index_get_parents(indexObject *self, Py_ssize_t rev, int *ps,
                                     int maxrev)
 {
 	const char *data = index_deref(self, rev);
 
 	ps[0] = getbe32(data + 24);
 	ps[1] = getbe32(data + 28);
 
 	/* If index file is corrupted, ps[] may point to invalid revisions. So
 	 * there is a risk of buffer overflow to trust them unconditionally. */
 	if (ps[0] < -1 || ps[0] > maxrev || ps[1] < -1 || ps[1] > maxrev) {
 		PyErr_SetString(PyExc_ValueError, "parent out of range");
 		return -1;
 	}
 	return 0;
 }
 
 /*
  * Get parents of the given rev.
  *
  * If the specified rev is out of range, IndexError will be raised. If the
  * revlog entry is corrupted, ValueError may be raised.
  *
  * Returns 0 on success or -1 on failure.
  */
 static int HgRevlogIndex_GetParents(PyObject *op, int rev, int *ps)
 {
 	int tiprev;
 	if (!op || !HgRevlogIndex_Check(op) || !ps) {
 		PyErr_BadInternalCall();
 		return -1;
 	}
 	tiprev = (int)index_length((indexObject *)op) - 1;
 	if (rev < -1 || rev > tiprev) {
 		PyErr_Format(PyExc_IndexError, "rev out of range: %d", rev);
 		return -1;
 	} else if (rev == -1) {
 		ps[0] = ps[1] = -1;
 		return 0;
 	} else {
 		return index_get_parents((indexObject *)op, rev, ps, tiprev);
 	}
 }
 
 static inline int64_t index_get_start(indexObject *self, Py_ssize_t rev)
 {
 	const char *data;
 	uint64_t offset;
 
 	if (rev == nullrev)
 		return 0;
 
 	data = index_deref(self, rev);
 	offset = getbe32(data + 4);
 	if (rev == 0) {
 		/* mask out version number for the first entry */
 		offset &= 0xFFFF;
 	} else {
 		uint32_t offset_high = getbe32(data);
 		offset |= ((uint64_t)offset_high) << 32;
 	}
 	return (int64_t)(offset >> 16);
 }
 
 static inline int index_get_length(indexObject *self, Py_ssize_t rev)
 {
 	const char *data;
 	int tmp;
 
 	if (rev == nullrev)
 		return 0;
 
 	data = index_deref(self, rev);
 
 	tmp = (int)getbe32(data + 8);
 	if (tmp < 0) {
 		PyErr_Format(PyExc_OverflowError,
 		             "revlog entry size out of bound (%d)", tmp);
 		return -1;
 	}
 	return tmp;
 }
 
 /*
  * RevlogNG format (all in big endian, data may be inlined):
  *    6 bytes: offset
  *    2 bytes: flags
  *    4 bytes: compressed length
  *    4 bytes: uncompressed length
  *    4 bytes: base revision
  *    4 bytes: link revision
  *    4 bytes: parent 1 revision
  *    4 bytes: parent 2 revision
  *   32 bytes: nodeid (only 20 bytes used with SHA-1)
  */
 static PyObject *index_get(indexObject *self, Py_ssize_t pos)
 {
 	uint64_t offset_flags, sidedata_offset;
 	int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2,
 	    sidedata_comp_len;
 	char data_comp_mode, sidedata_comp_mode;
 	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;
 	}
 
 	data = index_deref(self, pos);
 	if (data == NULL)
 		return NULL;
 
 	offset_flags = getbe32(data + 4);
 	/*
 	 * The first entry on-disk needs the version number masked out,
 	 * but this doesn't apply if entries are added to an empty index.
 	 */
 	if (self->length && pos == 0)
 		offset_flags &= 0xFFFF;
 	else {
 		uint32_t offset_high = getbe32(data);
 		offset_flags |= ((uint64_t)offset_high) << 32;
 	}
 
 	comp_len = getbe32(data + 8);
 	uncomp_len = getbe32(data + 12);
 	base_rev = getbe32(data + 16);
 	link_rev = getbe32(data + 20);
 	parent_1 = getbe32(data + 24);
 	parent_2 = getbe32(data + 28);
 	c_node_id = data + 32;
 
 	if (self->format_version == format_v1) {
 		sidedata_offset = 0;
 		sidedata_comp_len = 0;
 		data_comp_mode = comp_mode_inline;
 		sidedata_comp_mode = comp_mode_inline;
 	} else {
 		sidedata_offset = getbe64(data + 64);
 		sidedata_comp_len = getbe32(data + 72);
 		data_comp_mode = data[76] & 3;
 		sidedata_comp_mode = ((data[76] >> 2) & 3);
 	}
 
 	return Py_BuildValue(tuple_format, offset_flags, comp_len, uncomp_len,
 	                     base_rev, link_rev, parent_1, parent_2, c_node_id,
 	                     self->nodelen, sidedata_offset, sidedata_comp_len,
-	                     data_comp_mode, sidedata_comp_mode);
+	                     data_comp_mode, sidedata_comp_mode, rank_unknown);
 }
 /*
  * Pack header information in binary
  */
 static PyObject *index_pack_header(indexObject *self, PyObject *args)
 {
 	int header;
 	char out[4];
 	if (!PyArg_ParseTuple(args, "I", &header)) {
 		return NULL;
 	}
 	if (self->format_version != format_v1) {
 		PyErr_Format(PyExc_RuntimeError,
 		             "version header should go in the docket, not the "
 		             "index: %lu",
 		             header);
 		return NULL;
 	}
 	putbe32(header, out);
 	return PyBytes_FromStringAndSize(out, 4);
 }
 /*
  * Return the raw binary string representing a revision
  */
 static PyObject *index_entry_binary(indexObject *self, PyObject *value)
 {
 	long rev;
 	const char *data;
 	Py_ssize_t length = index_length(self);
 
 	if (!pylong_to_long(value, &rev)) {
 		return NULL;
 	}
 	if (rev < 0 || rev >= length) {
 		PyErr_Format(PyExc_ValueError, "revlog index out of range: %ld",
 		             rev);
 		return NULL;
 	};
 
 	data = index_deref(self, rev);
 	if (data == NULL)
 		return NULL;
 	if (rev == 0 && self->format_version == format_v1) {
 		/* the header is eating the start of the first entry */
 		return PyBytes_FromStringAndSize(data + 4,
 		                                 self->entry_size - 4);
 	}
 	return PyBytes_FromStringAndSize(data, self->entry_size);
 }
 
 /*
  * 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;
 
 	if (pos == nullrev)
 		return nullid;
 
 	if (pos >= length)
 		return NULL;
 
 	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);
 	if (node == NULL) {
 		PyErr_Format(PyExc_IndexError, "could not access rev %d",
 		             (int)pos);
 	}
 	return node;
 }
 
 static int nt_insert(nodetree *self, const char *node, int rev);
 
 static int node_check(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)
 {
 	uint64_t offset_flags, sidedata_offset;
 	int rev, comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2,
-	    sidedata_comp_len;
+	    sidedata_comp_len, rank;
 	char data_comp_mode, sidedata_comp_mode;
 	Py_ssize_t c_node_id_len;
 	const char *c_node_id;
 	char comp_field;
 	char *data;
 
 	if (!PyArg_ParseTuple(obj, tuple_format, &offset_flags, &comp_len,
 	                      &uncomp_len, &base_rev, &link_rev, &parent_1,
 	                      &parent_2, &c_node_id, &c_node_id_len,
 	                      &sidedata_offset, &sidedata_comp_len,
-	                      &data_comp_mode, &sidedata_comp_mode)) {
-		PyErr_SetString(PyExc_TypeError, "11-tuple required");
+	                      &data_comp_mode, &sidedata_comp_mode, &rank)) {
+		PyErr_SetString(PyExc_TypeError, "12-tuple required");
 		return NULL;
 	}
 
 	if (c_node_id_len != self->nodelen) {
 		PyErr_SetString(PyExc_TypeError, "invalid node");
 		return NULL;
 	}
 	if (self->format_version == format_v1) {
 
 		if (data_comp_mode != comp_mode_inline) {
 			PyErr_Format(PyExc_ValueError,
 			             "invalid data compression mode: %i",
 			             data_comp_mode);
 			return NULL;
 		}
 		if (sidedata_comp_mode != comp_mode_inline) {
 			PyErr_Format(PyExc_ValueError,
 			             "invalid sidedata compression mode: %i",
 			             sidedata_comp_mode);
 			return NULL;
 		}
 	}
 
 	if (self->new_length == self->added_length) {
 		size_t new_added_length =
 		    self->added_length ? self->added_length * 2 : 4096;
 		void *new_added = PyMem_Realloc(
 		    self->added, new_added_length * self->entry_size);
 		if (!new_added)
 			return PyErr_NoMemory();
 		self->added = new_added;
 		self->added_length = new_added_length;
 	}
 	rev = self->length + self->new_length;
 	data = self->added + self->entry_size * self->new_length++;
 	putbe32(offset_flags >> 32, data);
 	putbe32(offset_flags & 0xffffffffU, data + 4);
 	putbe32(comp_len, data + 8);
 	putbe32(uncomp_len, data + 12);
 	putbe32(base_rev, data + 16);
 	putbe32(link_rev, data + 20);
 	putbe32(parent_1, data + 24);
 	putbe32(parent_2, data + 28);
 	memcpy(data + 32, c_node_id, c_node_id_len);
 	/* Padding since SHA-1 is only 20 bytes for now */
 	memset(data + 32 + c_node_id_len, 0, 32 - c_node_id_len);
 	if (self->format_version == format_v2) {
 		putbe64(sidedata_offset, data + 64);
 		putbe32(sidedata_comp_len, data + 72);
 		comp_field = data_comp_mode & 3;
 		comp_field = comp_field | (sidedata_comp_mode & 3) << 2;
 		data[76] = comp_field;
 		/* Padding for 96 bytes alignment */
 		memset(data + 77, 0, self->entry_size - 77);
 	}
 
 	if (self->ntinitialized)
 		nt_insert(&self->nt, c_node_id, rev);
 
 	Py_CLEAR(self->headrevs);
 	Py_RETURN_NONE;
 }
 
 /* Replace an existing index entry's sidedata offset and length with new ones.
    This cannot be used outside of the context of sidedata rewriting,
    inside the transaction that creates the given revision. */
 static PyObject *index_replace_sidedata_info(indexObject *self, PyObject *args)
 {
 	uint64_t offset_flags, sidedata_offset;
 	Py_ssize_t rev;
 	int sidedata_comp_len;
 	char comp_mode;
 	char *data;
 #if LONG_MAX == 0x7fffffffL
 	const char *const sidedata_format = PY23("nKiKB", "nKiKB");
 #else
 	const char *const sidedata_format = PY23("nkikB", "nkikB");
 #endif
 
 	if (self->entry_size == v1_entry_size || self->inlined) {
 		/*
 		 There is a bug in the transaction handling when going from an
 	   inline revlog to a separate index and data file. Turn it off until
 	   it's fixed, since v2 revlogs sometimes get rewritten on exchange.
 	   See issue6485.
 	  */
 		raise_revlog_error();
 		return NULL;
 	}
 
 	if (!PyArg_ParseTuple(args, sidedata_format, &rev, &sidedata_offset,
 	                      &sidedata_comp_len, &offset_flags, &comp_mode))
 		return NULL;
 
 	if (rev < 0 || rev >= index_length(self)) {
 		PyErr_SetString(PyExc_IndexError, "revision outside index");
 		return NULL;
 	}
 	if (rev < self->length) {
 		PyErr_SetString(
 		    PyExc_IndexError,
 		    "cannot rewrite entries outside of this transaction");
 		return NULL;
 	}
 
 	/* Find the newly added node, offset from the "already on-disk" length
 	 */
 	data = self->added + self->entry_size * (rev - self->length);
 	putbe64(offset_flags, data);
 	putbe64(sidedata_offset, data + 64);
 	putbe32(sidedata_comp_len, data + 72);
 	data[76] = (data[76] & ~(3 << 2)) | ((comp_mode & 3) << 2);
 
 	Py_RETURN_NONE;
 }
 
 static PyObject *index_stats(indexObject *self)
 {
 	PyObject *obj = PyDict_New();
 	PyObject *s = NULL;
 	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_length)
 		istat(new_length, "index entries added");
 	istat(length, "revs in memory");
 	istat(ntlookups, "node trie lookups");
 	istat(ntmisses, "node trie misses");
 	istat(ntrev, "node trie last rev scanned");
 	if (self->ntinitialized) {
 		istat(nt.capacity, "node trie capacity");
 		istat(nt.depth, "node trie depth");
 		istat(nt.length, "node trie count");
 		istat(nt.splits, "node trie splits");
 	}
 
 #undef istat
 
 	return obj;
 
 bail:
 	Py_XDECREF(obj);
 	Py_XDECREF(s);
 	Py_XDECREF(t);
 	return NULL;
 }
 
 /*
  * When we cache a list, we want to be sure the caller can't mutate
  * the cached copy.
  */
 static PyObject *list_copy(PyObject *list)
 {
 	Py_ssize_t len = PyList_GET_SIZE(list);
 	PyObject *newlist = PyList_New(len);
 	Py_ssize_t i;
 
 	if (newlist == NULL)
 		return NULL;
 
 	for (i = 0; i < len; i++) {
 		PyObject *obj = PyList_GET_ITEM(list, i);
 		Py_INCREF(obj);
 		PyList_SET_ITEM(newlist, i, obj);
 	}
 
 	return newlist;
 }
 
 static int check_filter(PyObject *filter, Py_ssize_t arg)
 {
 	if (filter) {
 		PyObject *arglist, *result;
 		int isfiltered;
 
 		arglist = Py_BuildValue("(n)", arg);
 		if (!arglist) {
 			return -1;
 		}
 
 		result = PyObject_Call(filter, arglist, NULL);
 		Py_DECREF(arglist);
 		if (!result) {
 			return -1;
 		}
 
 		/* PyObject_IsTrue returns 1 if true, 0 if false, -1 if error,
 		 * same as this function, so we can just return it directly.*/
 		isfiltered = PyObject_IsTrue(result);
 		Py_DECREF(result);
 		return isfiltered;
 	} else {
 		return 0;
 	}
 }
 
 static inline void set_phase_from_parents(char *phases, int parent_1,
                                           int parent_2, Py_ssize_t i)
 {
 	if (parent_1 >= 0 && phases[parent_1] > phases[i])
 		phases[i] = phases[parent_1];
 	if (parent_2 >= 0 && phases[parent_2] > phases[i])
 		phases[i] = phases[parent_2];
 }
 
 static PyObject *reachableroots2(indexObject *self, PyObject *args)
 {
 
 	/* Input */
 	long minroot;
 	PyObject *includepatharg = NULL;
 	int includepath = 0;
 	/* heads and roots are lists */
 	PyObject *heads = NULL;
 	PyObject *roots = NULL;
 	PyObject *reachable = NULL;
 
 	PyObject *val;
 	Py_ssize_t len = index_length(self);
 	long revnum;
 	Py_ssize_t k;
 	Py_ssize_t i;
 	Py_ssize_t l;
 	int r;
 	int parents[2];
 
 	/* Internal data structure:
 	 * tovisit: array of length len+1 (all revs + nullrev), filled upto
 	 * lentovisit
 	 *
 	 * revstates: array of length len+1 (all revs + nullrev) */
 	int *tovisit = NULL;
 	long lentovisit = 0;
 	enum { RS_SEEN = 1, RS_ROOT = 2, RS_REACHABLE = 4 };
 	char *revstates = NULL;
 
 	/* Get arguments */
 	if (!PyArg_ParseTuple(args, "lO!O!O!", &minroot, &PyList_Type, &heads,
 	                      &PyList_Type, &roots, &PyBool_Type,
 	                      &includepatharg))
 		goto bail;
 
 	if (includepatharg == Py_True)
 		includepath = 1;
 
 	/* Initialize return set */
 	reachable = PyList_New(0);
 	if (reachable == NULL)
 		goto bail;
 
 	/* Initialize internal datastructures */
 	tovisit = (int *)malloc((len + 1) * sizeof(int));
 	if (tovisit == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	revstates = (char *)calloc(len + 1, 1);
 	if (revstates == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	l = PyList_GET_SIZE(roots);
 	for (i = 0; i < l; i++) {
 		revnum = PyInt_AsLong(PyList_GET_ITEM(roots, i));
 		if (revnum == -1 && PyErr_Occurred())
 			goto bail;
 		/* If root is out of range, e.g. wdir(), it must be unreachable
 		 * from heads. So we can just ignore it. */
 		if (revnum + 1 < 0 || revnum + 1 >= len + 1)
 			continue;
 		revstates[revnum + 1] |= RS_ROOT;
 	}
 
 	/* Populate tovisit with all the heads */
 	l = PyList_GET_SIZE(heads);
 	for (i = 0; i < l; i++) {
 		revnum = PyInt_AsLong(PyList_GET_ITEM(heads, i));
 		if (revnum == -1 && PyErr_Occurred())
 			goto bail;
 		if (revnum + 1 < 0 || revnum + 1 >= len + 1) {
 			PyErr_SetString(PyExc_IndexError, "head out of range");
 			goto bail;
 		}
 		if (!(revstates[revnum + 1] & RS_SEEN)) {
 			tovisit[lentovisit++] = (int)revnum;
 			revstates[revnum + 1] |= RS_SEEN;
 		}
 	}
 
 	/* Visit the tovisit list and find the reachable roots */
 	k = 0;
 	while (k < lentovisit) {
 		/* Add the node to reachable if it is a root*/
 		revnum = tovisit[k++];
 		if (revstates[revnum + 1] & RS_ROOT) {
 			revstates[revnum + 1] |= RS_REACHABLE;
 			val = PyInt_FromLong(revnum);
 			if (val == NULL)
 				goto bail;
 			r = PyList_Append(reachable, val);
 			Py_DECREF(val);
 			if (r < 0)
 				goto bail;
 			if (includepath == 0)
 				continue;
 		}
 
 		/* Add its parents to the list of nodes to visit */
 		if (revnum == nullrev)
 			continue;
 		r = index_get_parents(self, revnum, parents, (int)len - 1);
 		if (r < 0)
 			goto bail;
 		for (i = 0; i < 2; i++) {
 			if (!(revstates[parents[i] + 1] & RS_SEEN) &&
 			    parents[i] >= minroot) {
 				tovisit[lentovisit++] = parents[i];
 				revstates[parents[i] + 1] |= RS_SEEN;
 			}
 		}
 	}
 
 	/* Find all the nodes in between the roots we found and the heads
 	 * and add them to the reachable set */
 	if (includepath == 1) {
 		long minidx = minroot;
 		if (minidx < 0)
 			minidx = 0;
 		for (i = minidx; i < len; i++) {
 			if (!(revstates[i + 1] & RS_SEEN))
 				continue;
 			r = index_get_parents(self, i, parents, (int)len - 1);
 			/* Corrupted index file, error is set from
 			 * index_get_parents */
 			if (r < 0)
 				goto bail;
 			if (((revstates[parents[0] + 1] |
 			      revstates[parents[1] + 1]) &
 			     RS_REACHABLE) &&
 			    !(revstates[i + 1] & RS_REACHABLE)) {
 				revstates[i + 1] |= RS_REACHABLE;
 				val = PyInt_FromSsize_t(i);
 				if (val == NULL)
 					goto bail;
 				r = PyList_Append(reachable, val);
 				Py_DECREF(val);
 				if (r < 0)
 					goto bail;
 			}
 		}
 	}
 
 	free(revstates);
 	free(tovisit);
 	return reachable;
 bail:
 	Py_XDECREF(reachable);
 	free(revstates);
 	free(tovisit);
 	return NULL;
 }
 
 static int add_roots_get_min(indexObject *self, PyObject *roots, char *phases,
                              char phase)
 {
 	Py_ssize_t len = index_length(self);
 	PyObject *item;
 	PyObject *iterator;
 	int rev, minrev = -1;
 	char *node;
 
 	if (!PySet_Check(roots)) {
 		PyErr_SetString(PyExc_TypeError,
 		                "roots must be a set of nodes");
 		return -2;
 	}
 	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)
 			minrev = rev;
 		Py_DECREF(item);
 	}
 	Py_DECREF(iterator);
 	return minrev;
 failed:
 	Py_DECREF(iterator);
 	Py_DECREF(item);
 	return -2;
 }
 
 static PyObject *compute_phases_map_sets(indexObject *self, PyObject *args)
 {
 	/* 0: public (untracked), 1: draft, 2: secret, 32: archive,
 	   96: internal */
 	static const char trackedphases[] = {1, 2, 32, 96};
 	PyObject *roots = Py_None;
 	PyObject *phasesetsdict = NULL;
 	PyObject *phasesets[4] = {NULL, NULL, NULL, NULL};
 	Py_ssize_t len = index_length(self);
 	char *phases = NULL;
 	int minphaserev = -1, rev, i;
 	const int numphases = (int)(sizeof(phasesets) / sizeof(phasesets[0]));
 
 	if (!PyArg_ParseTuple(args, "O", &roots))
 		return NULL;
 	if (roots == NULL || !PyDict_Check(roots)) {
 		PyErr_SetString(PyExc_TypeError, "roots must be a dictionary");
 		return NULL;
 	}
 
 	phases = calloc(len, 1);
 	if (phases == NULL) {
 		PyErr_NoMemory();
 		return NULL;
 	}
 
 	for (i = 0; i < numphases; ++i) {
 		PyObject *pyphase = PyInt_FromLong(trackedphases[i]);
 		PyObject *phaseroots = NULL;
 		if (pyphase == NULL)
 			goto release;
 		phaseroots = PyDict_GetItem(roots, pyphase);
 		Py_DECREF(pyphase);
 		if (phaseroots == NULL)
 			continue;
 		rev = add_roots_get_min(self, phaseroots, phases,
 		                        trackedphases[i]);
 		if (rev == -2)
 			goto release;
 		if (rev != -1 && (minphaserev == -1 || rev < minphaserev))
 			minphaserev = rev;
 	}
 
 	for (i = 0; i < numphases; ++i) {
 		phasesets[i] = PySet_New(NULL);
 		if (phasesets[i] == NULL)
 			goto release;
 	}
 
 	if (minphaserev == -1)
 		minphaserev = len;
 	for (rev = minphaserev; rev < len; ++rev) {
 		PyObject *pyphase = NULL;
 		PyObject *pyrev = NULL;
 		int parents[2];
 		/*
 		 * The parent lookup could be skipped for phaseroots, but
 		 * phase --force would historically not recompute them
 		 * correctly, leaving descendents with a lower phase around.
 		 * As such, unconditionally recompute the phase.
 		 */
 		if (index_get_parents(self, rev, parents, (int)len - 1) < 0)
 			goto release;
 		set_phase_from_parents(phases, parents[0], parents[1], rev);
 		switch (phases[rev]) {
 		case 0:
 			continue;
 		case 1:
 			pyphase = phasesets[0];
 			break;
 		case 2:
 			pyphase = phasesets[1];
 			break;
 		case 32:
 			pyphase = phasesets[2];
 			break;
 		case 96:
 			pyphase = phasesets[3];
 			break;
 		default:
 			/* this should never happen since the phase number is
 			 * specified by this function. */
 			PyErr_SetString(PyExc_SystemError,
 			                "bad phase number in internal list");
 			goto release;
 		}
 		pyrev = PyInt_FromLong(rev);
 		if (pyrev == NULL)
 			goto release;
 		if (PySet_Add(pyphase, pyrev) == -1) {
 			Py_DECREF(pyrev);
 			goto release;
 		}
 		Py_DECREF(pyrev);
 	}
 
 	phasesetsdict = _dict_new_presized(numphases);
 	if (phasesetsdict == NULL)
 		goto release;
 	for (i = 0; i < numphases; ++i) {
 		PyObject *pyphase = PyInt_FromLong(trackedphases[i]);
 		if (pyphase == NULL)
 			goto release;
 		if (PyDict_SetItem(phasesetsdict, pyphase, phasesets[i]) ==
 		    -1) {
 			Py_DECREF(pyphase);
 			goto release;
 		}
 		Py_DECREF(phasesets[i]);
 		phasesets[i] = NULL;
 	}
 
 	free(phases);
 	return Py_BuildValue("nN", len, phasesetsdict);
 
 release:
 	for (i = 0; i < numphases; ++i)
 		Py_XDECREF(phasesets[i]);
 	Py_XDECREF(phasesetsdict);
 
 	free(phases);
 	return NULL;
 }
 
 static PyObject *index_headrevs(indexObject *self, PyObject *args)
 {
 	Py_ssize_t i, j, len;
 	char *nothead = NULL;
 	PyObject *heads = NULL;
 	PyObject *filter = NULL;
 	PyObject *filteredrevs = Py_None;
 
 	if (!PyArg_ParseTuple(args, "|O", &filteredrevs)) {
 		return NULL;
 	}
 
 	if (self->headrevs && filteredrevs == self->filteredrevs)
 		return list_copy(self->headrevs);
 
 	Py_DECREF(self->filteredrevs);
 	self->filteredrevs = filteredrevs;
 	Py_INCREF(filteredrevs);
 
 	if (filteredrevs != Py_None) {
 		filter = PyObject_GetAttrString(filteredrevs, "__contains__");
 		if (!filter) {
 			PyErr_SetString(
 			    PyExc_TypeError,
 			    "filteredrevs has no attribute __contains__");
 			goto bail;
 		}
 	}
 
 	len = index_length(self);
 	heads = PyList_New(0);
 	if (heads == NULL)
 		goto bail;
 	if (len == 0) {
 		PyObject *nullid = PyInt_FromLong(-1);
 		if (nullid == NULL || PyList_Append(heads, nullid) == -1) {
 			Py_XDECREF(nullid);
 			goto bail;
 		}
 		goto done;
 	}
 
 	nothead = calloc(len, 1);
 	if (nothead == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	for (i = len - 1; i >= 0; i--) {
 		int isfiltered;
 		int parents[2];
 
 		/* If nothead[i] == 1, it means we've seen an unfiltered child
 		 * of this node already, and therefore this node is not
 		 * filtered. So we can skip the expensive check_filter step.
 		 */
 		if (nothead[i] != 1) {
 			isfiltered = check_filter(filter, i);
 			if (isfiltered == -1) {
 				PyErr_SetString(PyExc_TypeError,
 				                "unable to check filter");
 				goto bail;
 			}
 
 			if (isfiltered) {
 				nothead[i] = 1;
 				continue;
 			}
 		}
 
 		if (index_get_parents(self, i, parents, (int)len - 1) < 0)
 			goto bail;
 		for (j = 0; j < 2; j++) {
 			if (parents[j] >= 0)
 				nothead[parents[j]] = 1;
 		}
 	}
 
 	for (i = 0; i < len; i++) {
 		PyObject *head;
 
 		if (nothead[i])
 			continue;
 		head = PyInt_FromSsize_t(i);
 		if (head == NULL || PyList_Append(heads, head) == -1) {
 			Py_XDECREF(head);
 			goto bail;
 		}
 	}
 
 done:
 	self->headrevs = heads;
 	Py_XDECREF(filter);
 	free(nothead);
 	return list_copy(self->headrevs);
 bail:
 	Py_XDECREF(filter);
 	Py_XDECREF(heads);
 	free(nothead);
 	return NULL;
 }
 
 /**
  * Obtain the base revision index entry.
  *
  * Callers must ensure that rev >= 0 or illegal memory access may occur.
  */
 static inline int index_baserev(indexObject *self, int rev)
 {
 	const char *data;
 	int result;
 
 	data = index_deref(self, rev);
 	if (data == NULL)
 		return -2;
 	result = getbe32(data + 16);
 
 	if (result > rev) {
 		PyErr_Format(
 		    PyExc_ValueError,
 		    "corrupted revlog, revision base above revision: %d, %d",
 		    rev, result);
 		return -2;
 	}
 	if (result < -1) {
 		PyErr_Format(
 		    PyExc_ValueError,
 		    "corrupted revlog, revision base out of range: %d, %d", rev,
 		    result);
 		return -2;
 	}
 	return result;
 }
 
 /**
  * Find if a revision is a snapshot or not
  *
  * Only relevant for sparse-revlog case.
  * Callers must ensure that rev is in a valid range.
  */
 static int index_issnapshotrev(indexObject *self, Py_ssize_t rev)
 {
 	int ps[2];
 	Py_ssize_t base;
 	while (rev >= 0) {
 		base = (Py_ssize_t)index_baserev(self, rev);
 		if (base == rev) {
 			base = -1;
 		}
 		if (base == -2) {
 			assert(PyErr_Occurred());
 			return -1;
 		}
 		if (base == -1) {
 			return 1;
 		}
 		if (index_get_parents(self, rev, ps, (int)rev) < 0) {
 			assert(PyErr_Occurred());
 			return -1;
 		};
 		if (base == ps[0] || base == ps[1]) {
 			return 0;
 		}
 		rev = base;
 	}
 	return rev == -1;
 }
 
 static PyObject *index_issnapshot(indexObject *self, PyObject *value)
 {
 	long rev;
 	int issnap;
 	Py_ssize_t length = index_length(self);
 
 	if (!pylong_to_long(value, &rev)) {
 		return NULL;
 	}
 	if (rev < -1 || rev >= length) {
 		PyErr_Format(PyExc_ValueError, "revlog index out of range: %ld",
 		             rev);
 		return NULL;
 	};
 	issnap = index_issnapshotrev(self, (Py_ssize_t)rev);
 	if (issnap < 0) {
 		return NULL;
 	};
 	return PyBool_FromLong((long)issnap);
 }
 
 static PyObject *index_findsnapshots(indexObject *self, PyObject *args)
 {
 	Py_ssize_t start_rev;
 	PyObject *cache;
 	Py_ssize_t base;
 	Py_ssize_t rev;
 	PyObject *key = NULL;
 	PyObject *value = NULL;
 	const Py_ssize_t length = index_length(self);
 	if (!PyArg_ParseTuple(args, "O!n", &PyDict_Type, &cache, &start_rev)) {
 		return NULL;
 	}
 	for (rev = start_rev; rev < length; rev++) {
 		int issnap;
 		PyObject *allvalues = NULL;
 		issnap = index_issnapshotrev(self, rev);
 		if (issnap < 0) {
 			goto bail;
 		}
 		if (issnap == 0) {
 			continue;
 		}
 		base = (Py_ssize_t)index_baserev(self, rev);
 		if (base == rev) {
 			base = -1;
 		}
 		if (base == -2) {
 			assert(PyErr_Occurred());
 			goto bail;
 		}
 		key = PyInt_FromSsize_t(base);
 		allvalues = PyDict_GetItem(cache, key);
 		if (allvalues == NULL && PyErr_Occurred()) {
 			goto bail;
 		}
 		if (allvalues == NULL) {
 			int r;
 			allvalues = PyList_New(0);
 			if (!allvalues) {
 				goto bail;
 			}
 			r = PyDict_SetItem(cache, key, allvalues);
 			Py_DECREF(allvalues);
 			if (r < 0) {
 				goto bail;
 			}
 		}
 		value = PyInt_FromSsize_t(rev);
 		if (PyList_Append(allvalues, value)) {
 			goto bail;
 		}
 		Py_CLEAR(key);
 		Py_CLEAR(value);
 	}
 	Py_RETURN_NONE;
 bail:
 	Py_XDECREF(key);
 	Py_XDECREF(value);
 	return NULL;
 }
 
 static PyObject *index_deltachain(indexObject *self, PyObject *args)
 {
 	int rev, generaldelta;
 	PyObject *stoparg;
 	int stoprev, iterrev, baserev = -1;
 	int stopped;
 	PyObject *chain = NULL, *result = NULL;
 	const Py_ssize_t length = index_length(self);
 
 	if (!PyArg_ParseTuple(args, "iOi", &rev, &stoparg, &generaldelta)) {
 		return NULL;
 	}
 
 	if (PyInt_Check(stoparg)) {
 		stoprev = (int)PyInt_AsLong(stoparg);
 		if (stoprev == -1 && PyErr_Occurred()) {
 			return NULL;
 		}
 	} else if (stoparg == Py_None) {
 		stoprev = -2;
 	} else {
 		PyErr_SetString(PyExc_ValueError,
 		                "stoprev must be integer or None");
 		return NULL;
 	}
 
 	if (rev < 0 || rev >= length) {
 		PyErr_SetString(PyExc_ValueError, "revlog index out of range");
 		return NULL;
 	}
 
 	chain = PyList_New(0);
 	if (chain == NULL) {
 		return NULL;
 	}
 
 	baserev = index_baserev(self, rev);
 
 	/* This should never happen. */
 	if (baserev <= -2) {
 		/* Error should be set by index_deref() */
 		assert(PyErr_Occurred());
 		goto bail;
 	}
 
 	iterrev = rev;
 
 	while (iterrev != baserev && iterrev != stoprev) {
 		PyObject *value = PyInt_FromLong(iterrev);
 		if (value == NULL) {
 			goto bail;
 		}
 		if (PyList_Append(chain, value)) {
 			Py_DECREF(value);
 			goto bail;
 		}
 		Py_DECREF(value);
 
 		if (generaldelta) {
 			iterrev = baserev;
 		} else {
 			iterrev--;
 		}
 
 		if (iterrev < 0) {
 			break;
 		}
 
 		if (iterrev >= length) {
 			PyErr_SetString(PyExc_IndexError,
 			                "revision outside index");
 			return NULL;
 		}
 
 		baserev = index_baserev(self, iterrev);
 
 		/* This should never happen. */
 		if (baserev <= -2) {
 			/* Error should be set by index_deref() */
 			assert(PyErr_Occurred());
 			goto bail;
 		}
 	}
 
 	if (iterrev == stoprev) {
 		stopped = 1;
 	} else {
 		PyObject *value = PyInt_FromLong(iterrev);
 		if (value == NULL) {
 			goto bail;
 		}
 		if (PyList_Append(chain, value)) {
 			Py_DECREF(value);
 			goto bail;
 		}
 		Py_DECREF(value);
 
 		stopped = 0;
 	}
 
 	if (PyList_Reverse(chain)) {
 		goto bail;
 	}
 
 	result = Py_BuildValue("OO", chain, stopped ? Py_True : Py_False);
 	Py_DECREF(chain);
 	return result;
 
 bail:
 	Py_DECREF(chain);
 	return NULL;
 }
 
 static inline int64_t
 index_segment_span(indexObject *self, Py_ssize_t start_rev, Py_ssize_t end_rev)
 {
 	int64_t start_offset;
 	int64_t end_offset;
 	int end_size;
 	start_offset = index_get_start(self, start_rev);
 	if (start_offset < 0) {
 		return -1;
 	}
 	end_offset = index_get_start(self, end_rev);
 	if (end_offset < 0) {
 		return -1;
 	}
 	end_size = index_get_length(self, end_rev);
 	if (end_size < 0) {
 		return -1;
 	}
 	if (end_offset < start_offset) {
 		PyErr_Format(PyExc_ValueError,
 		             "corrupted revlog index: inconsistent offset "
 		             "between revisions (%zd) and (%zd)",
 		             start_rev, end_rev);
 		return -1;
 	}
 	return (end_offset - start_offset) + (int64_t)end_size;
 }
 
 /* returns endidx so that revs[startidx:endidx] has no empty trailing revs */
 static Py_ssize_t trim_endidx(indexObject *self, const Py_ssize_t *revs,
                               Py_ssize_t startidx, Py_ssize_t endidx)
 {
 	int length;
 	while (endidx > 1 && endidx > startidx) {
 		length = index_get_length(self, revs[endidx - 1]);
 		if (length < 0) {
 			return -1;
 		}
 		if (length != 0) {
 			break;
 		}
 		endidx -= 1;
 	}
 	return endidx;
 }
 
 struct Gap {
 	int64_t size;
 	Py_ssize_t idx;
 };
 
 static int gap_compare(const void *left, const void *right)
 {
 	const struct Gap *l_left = ((const struct Gap *)left);
 	const struct Gap *l_right = ((const struct Gap *)right);
 	if (l_left->size < l_right->size) {
 		return -1;
 	} else if (l_left->size > l_right->size) {
 		return 1;
 	}
 	return 0;
 }
 static int Py_ssize_t_compare(const void *left, const void *right)
 {
 	const Py_ssize_t l_left = *(const Py_ssize_t *)left;
 	const Py_ssize_t l_right = *(const Py_ssize_t *)right;
 	if (l_left < l_right) {
 		return -1;
 	} else if (l_left > l_right) {
 		return 1;
 	}
 	return 0;
 }
 
 static PyObject *index_slicechunktodensity(indexObject *self, PyObject *args)
 {
 	/* method arguments */
 	PyObject *list_revs = NULL; /* revisions in the chain */
 	double targetdensity = 0;   /* min density to achieve */
 	Py_ssize_t mingapsize = 0;  /* threshold to ignore gaps */
 
 	/* other core variables */
 	Py_ssize_t idxlen = index_length(self);
 	Py_ssize_t i;            /* used for various iteration */
 	PyObject *result = NULL; /* the final return of the function */
 
 	/* generic information about the delta chain being slice */
 	Py_ssize_t num_revs = 0;    /* size of the full delta chain */
 	Py_ssize_t *revs = NULL;    /* native array of revision in the chain */
 	int64_t chainpayload = 0;   /* sum of all delta in the chain */
 	int64_t deltachainspan = 0; /* distance from first byte to last byte */
 
 	/* variable used for slicing the delta chain */
 	int64_t readdata = 0; /* amount of data currently planned to be read */
 	double density = 0;   /* ration of payload data compared to read ones */
 	int64_t previous_end;
 	struct Gap *gaps = NULL; /* array of notable gap in the chain */
 	Py_ssize_t num_gaps =
 	    0; /* total number of notable gap recorded so far */
 	Py_ssize_t *selected_indices = NULL; /* indices of gap skipped over */
 	Py_ssize_t num_selected = 0;         /* number of gaps skipped */
 	PyObject *chunk = NULL;              /* individual slice */
 	PyObject *allchunks = NULL;          /* all slices */
 	Py_ssize_t previdx;
 
 	/* parsing argument */
 	if (!PyArg_ParseTuple(args, "O!dn", &PyList_Type, &list_revs,
 	                      &targetdensity, &mingapsize)) {
 		goto bail;
 	}
 
 	/* If the delta chain contains a single element, we do not need slicing
 	 */
 	num_revs = PyList_GET_SIZE(list_revs);
 	if (num_revs <= 1) {
 		result = PyTuple_Pack(1, list_revs);
 		goto done;
 	}
 
 	/* Turn the python list into a native integer array (for efficiency) */
 	revs = (Py_ssize_t *)calloc(num_revs, sizeof(Py_ssize_t));
 	if (revs == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 	for (i = 0; i < num_revs; i++) {
 		Py_ssize_t revnum = PyInt_AsLong(PyList_GET_ITEM(list_revs, i));
 		if (revnum == -1 && PyErr_Occurred()) {
 			goto bail;
 		}
 		if (revnum < nullrev || revnum >= idxlen) {
 			PyErr_Format(PyExc_IndexError,
 			             "index out of range: %zd", revnum);
 			goto bail;
 		}
 		revs[i] = revnum;
 	}
 
 	/* Compute and check various property of the unsliced delta chain */
 	deltachainspan = index_segment_span(self, revs[0], revs[num_revs - 1]);
 	if (deltachainspan < 0) {
 		goto bail;
 	}
 
 	if (deltachainspan <= mingapsize) {
 		result = PyTuple_Pack(1, list_revs);
 		goto done;
 	}
 	chainpayload = 0;
 	for (i = 0; i < num_revs; i++) {
 		int tmp = index_get_length(self, revs[i]);
 		if (tmp < 0) {
 			goto bail;
 		}
 		chainpayload += tmp;
 	}
 
 	readdata = deltachainspan;
 	density = 1.0;
 
 	if (0 < deltachainspan) {
 		density = (double)chainpayload / (double)deltachainspan;
 	}
 
 	if (density >= targetdensity) {
 		result = PyTuple_Pack(1, list_revs);
 		goto done;
 	}
 
 	/* if chain is too sparse, look for relevant gaps */
 	gaps = (struct Gap *)calloc(num_revs, sizeof(struct Gap));
 	if (gaps == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	previous_end = -1;
 	for (i = 0; i < num_revs; i++) {
 		int64_t revstart;
 		int revsize;
 		revstart = index_get_start(self, revs[i]);
 		if (revstart < 0) {
 			goto bail;
 		};
 		revsize = index_get_length(self, revs[i]);
 		if (revsize < 0) {
 			goto bail;
 		};
 		if (revsize == 0) {
 			continue;
 		}
 		if (previous_end >= 0) {
 			int64_t gapsize = revstart - previous_end;
 			if (gapsize > mingapsize) {
 				gaps[num_gaps].size = gapsize;
 				gaps[num_gaps].idx = i;
 				num_gaps += 1;
 			}
 		}
 		previous_end = revstart + revsize;
 	}
 	if (num_gaps == 0) {
 		result = PyTuple_Pack(1, list_revs);
 		goto done;
 	}
 	qsort(gaps, num_gaps, sizeof(struct Gap), &gap_compare);
 
 	/* Slice the largest gap first, they improve the density the most */
 	selected_indices =
 	    (Py_ssize_t *)malloc((num_gaps + 1) * sizeof(Py_ssize_t));
 	if (selected_indices == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	for (i = num_gaps - 1; i >= 0; i--) {
 		selected_indices[num_selected] = gaps[i].idx;
 		readdata -= gaps[i].size;
 		num_selected += 1;
 		if (readdata <= 0) {
 			density = 1.0;
 		} else {
 			density = (double)chainpayload / (double)readdata;
 		}
 		if (density >= targetdensity) {
 			break;
 		}
 	}
 	qsort(selected_indices, num_selected, sizeof(Py_ssize_t),
 	      &Py_ssize_t_compare);
 
 	/* create the resulting slice */
 	allchunks = PyList_New(0);
 	if (allchunks == NULL) {
 		goto bail;
 	}
 	previdx = 0;
 	selected_indices[num_selected] = num_revs;
 	for (i = 0; i <= num_selected; i++) {
 		Py_ssize_t idx = selected_indices[i];
 		Py_ssize_t endidx = trim_endidx(self, revs, previdx, idx);
 		if (endidx < 0) {
 			goto bail;
 		}
 		if (previdx < endidx) {
 			chunk = PyList_GetSlice(list_revs, previdx, endidx);
 			if (chunk == NULL) {
 				goto bail;
 			}
 			if (PyList_Append(allchunks, chunk) == -1) {
 				goto bail;
 			}
 			Py_DECREF(chunk);
 			chunk = NULL;
 		}
 		previdx = idx;
 	}
 	result = allchunks;
 	goto done;
 
 bail:
 	Py_XDECREF(allchunks);
 	Py_XDECREF(chunk);
 done:
 	free(revs);
 	free(gaps);
 	free(selected_indices);
 	return result;
 }
 
 static inline int nt_level(const char *node, Py_ssize_t level)
 {
 	int v = node[level >> 1];
 	if (!(level & 1))
 		v >>= 4;
 	return v & 0xf;
 }
 
 /*
  * Return values:
  *
  *   -4: match is ambiguous (multiple candidates)
  *   -2: not found
  * rest: valid rev
  */
 static int nt_find(nodetree *self, const char *node, Py_ssize_t nodelen,
                    int hex)
 {
 	int (*getnybble)(const char *, Py_ssize_t) = hex ? hexdigit : nt_level;
 	int level, maxlevel, off;
 
 	/* If 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];
 
 		if (v < 0) {
 			const char *n;
 			Py_ssize_t i;
 
 			v = -(v + 2);
 			n = index_node(self->index, v);
 			if (n == NULL)
 				return -2;
 			for (i = level; i < maxlevel; i++)
 				if (getnybble(node, i) != nt_level(n, i))
 					return -2;
 			return v;
 		}
 		if (v == 0)
 			return -2;
 		off = v;
 	}
 	/* multiple matches against an ambiguous prefix */
 	return -4;
 }
 
 static int nt_new(nodetree *self)
 {
 	if (self->length == self->capacity) {
 		size_t newcapacity;
 		nodetreenode *newnodes;
 		newcapacity = self->capacity * 2;
 		if (newcapacity >= SIZE_MAX / sizeof(nodetreenode)) {
 			PyErr_SetString(PyExc_MemoryError,
 			                "overflow in nt_new");
 			return -1;
 		}
 		newnodes =
 		    realloc(self->nodes, newcapacity * sizeof(nodetreenode));
 		if (newnodes == NULL) {
 			PyErr_SetString(PyExc_MemoryError, "out of memory");
 			return -1;
 		}
 		self->capacity = newcapacity;
 		self->nodes = newnodes;
 		memset(&self->nodes[self->length], 0,
 		       sizeof(nodetreenode) * (self->capacity - self->length));
 	}
 	return self->length++;
 }
 
 static int nt_insert(nodetree *self, const char *node, int rev)
 {
 	int level = 0;
 	int off = 0;
 
 	while (level < 2 * self->nodelen) {
 		int k = nt_level(node, level);
 		nodetreenode *n;
 		int v;
 
 		n = &self->nodes[off];
 		v = n->children[k];
 
 		if (v == 0) {
 			n->children[k] = -rev - 2;
 			return 0;
 		}
 		if (v < 0) {
 			const char *oldnode =
 			    index_node_existing(self->index, -(v + 2));
 			int noff;
 
 			if (oldnode == NULL)
 				return -1;
 			if (!memcmp(oldnode, node, self->nodelen)) {
 				n->children[k] = -rev - 2;
 				return 0;
 			}
 			noff = nt_new(self);
 			if (noff == -1)
 				return -1;
 			/* self->nodes may have been changed by realloc */
 			self->nodes[off].children[k] = noff;
 			off = noff;
 			n = &self->nodes[off];
 			n->children[nt_level(oldnode, ++level)] = v;
 			if (level > self->depth)
 				self->depth = level;
 			self->splits += 1;
 		} else {
 			level += 1;
 			off = v;
 		}
 	}
 
 	return -1;
 }
 
 static PyObject *ntobj_insert(nodetreeObject *self, PyObject *args)
 {
 	Py_ssize_t rev;
 	const char *node;
 	Py_ssize_t length;
 	if (!PyArg_ParseTuple(args, "n", &rev))
 		return NULL;
 	length = index_length(self->nt.index);
 	if (rev < 0 || rev >= length) {
 		PyErr_SetString(PyExc_ValueError, "revlog index out of range");
 		return NULL;
 	}
 	node = index_node_existing(self->nt.index, rev);
 	if (nt_insert(&self->nt, node, (int)rev) == -1)
 		return NULL;
 	Py_RETURN_NONE;
 }
 
 static int nt_delete_node(nodetree *self, const char *node)
 {
 	/* rev==-2 happens to get encoded as 0, which is interpreted as not set
 	 */
 	return nt_insert(self, node, -2);
 }
 
 static int nt_init(nodetree *self, indexObject *index, unsigned capacity)
 {
 	/* Initialize before overflow-checking to avoid nt_dealloc() crash. */
 	self->nodes = NULL;
 
 	self->index = index;
 	/* The input capacity is in terms of revisions, while the field is in
 	 * terms of nodetree nodes. */
 	self->capacity = (capacity < 4 ? 4 : capacity / 2);
 	self->nodelen = index->nodelen;
 	self->depth = 0;
 	self->splits = 0;
 	if (self->capacity > SIZE_MAX / sizeof(nodetreenode)) {
 		PyErr_SetString(PyExc_ValueError, "overflow in init_nt");
 		return -1;
 	}
 	self->nodes = calloc(self->capacity, sizeof(nodetreenode));
 	if (self->nodes == NULL) {
 		PyErr_NoMemory();
 		return -1;
 	}
 	self->length = 1;
 	return 0;
 }
 
 static int ntobj_init(nodetreeObject *self, PyObject *args)
 {
 	PyObject *index;
 	unsigned capacity;
 	if (!PyArg_ParseTuple(args, "O!I", &HgRevlogIndex_Type, &index,
 	                      &capacity))
 		return -1;
 	Py_INCREF(index);
 	return nt_init(&self->nt, (indexObject *)index, capacity);
 }
 
 static int nt_partialmatch(nodetree *self, const char *node, Py_ssize_t nodelen)
 {
 	return nt_find(self, node, nodelen, 1);
 }
 
 /*
  * Find the length of the shortest unique prefix of node.
  *
  * Return values:
  *
  *   -3: error (exception set)
  *   -2: not found (no exception set)
  * rest: length of shortest prefix
  */
 static int nt_shortest(nodetree *self, const char *node)
 {
 	int level, off;
 
 	for (level = off = 0; level < 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).
 				 */
 				return -2;
 			return level + 1;
 		}
 		if (v == 0)
 			return -2;
 		off = v;
 	}
 	/*
 	 * The node was still not unique after 40 hex digits, so this won't
 	 * happen. Also, if we get here, then there's a programming error in
 	 * this file that made us insert a node longer than 40 hex digits.
 	 */
 	PyErr_SetString(PyExc_Exception, "broken node tree");
 	return -3;
 }
 
 static PyObject *ntobj_shortest(nodetreeObject *self, PyObject *args)
 {
 	PyObject *val;
 	char *node;
 	int length;
 
 	if (!PyArg_ParseTuple(args, "O", &val))
 		return NULL;
 	if (node_check(self->nt.nodelen, val, &node) == -1)
 		return NULL;
 
 	length = nt_shortest(&self->nt, node);
 	if (length == -3)
 		return NULL;
 	if (length == -2) {
 		raise_revlog_error();
 		return NULL;
 	}
 	return PyInt_FromLong(length);
 }
 
 static void nt_dealloc(nodetree *self)
 {
 	free(self->nodes);
 	self->nodes = NULL;
 }
 
 static void ntobj_dealloc(nodetreeObject *self)
 {
 	Py_XDECREF(self->nt.index);
 	nt_dealloc(&self->nt);
 	PyObject_Del(self);
 }
 
 static PyMethodDef ntobj_methods[] = {
     {"insert", (PyCFunction)ntobj_insert, METH_VARARGS,
      "insert an index entry"},
     {"shortest", (PyCFunction)ntobj_shortest, METH_VARARGS,
      "find length of shortest hex nodeid of a binary ID"},
     {NULL} /* Sentinel */
 };
 
 static PyTypeObject nodetreeType = {
     PyVarObject_HEAD_INIT(NULL, 0) /* header */
     "parsers.nodetree",            /* tp_name */
     sizeof(nodetreeObject),        /* tp_basicsize */
     0,                             /* tp_itemsize */
     (destructor)ntobj_dealloc,     /* tp_dealloc */
     0,                             /* tp_print */
     0,                             /* tp_getattr */
     0,                             /* tp_setattr */
     0,                             /* tp_compare */
     0,                             /* tp_repr */
     0,                             /* tp_as_number */
     0,                             /* tp_as_sequence */
     0,                             /* tp_as_mapping */
     0,                             /* tp_hash */
     0,                             /* tp_call */
     0,                             /* tp_str */
     0,                             /* tp_getattro */
     0,                             /* tp_setattro */
     0,                             /* tp_as_buffer */
     Py_TPFLAGS_DEFAULT,            /* tp_flags */
     "nodetree",                    /* tp_doc */
     0,                             /* tp_traverse */
     0,                             /* tp_clear */
     0,                             /* tp_richcompare */
     0,                             /* tp_weaklistoffset */
     0,                             /* tp_iter */
     0,                             /* tp_iternext */
     ntobj_methods,                 /* tp_methods */
     0,                             /* tp_members */
     0,                             /* tp_getset */
     0,                             /* tp_base */
     0,                             /* tp_dict */
     0,                             /* tp_descr_get */
     0,                             /* tp_descr_set */
     0,                             /* tp_dictoffset */
     (initproc)ntobj_init,          /* tp_init */
     0,                             /* tp_alloc */
 };
 
 static int index_init_nt(indexObject *self)
 {
 	if (!self->ntinitialized) {
 		if (nt_init(&self->nt, self, (int)self->length) == -1) {
 			nt_dealloc(&self->nt);
 			return -1;
 		}
 		if (nt_insert(&self->nt, nullid, -1) == -1) {
 			nt_dealloc(&self->nt);
 			return -1;
 		}
 		self->ntinitialized = 1;
 		self->ntrev = (int)index_length(self);
 		self->ntlookups = 1;
 		self->ntmisses = 0;
 	}
 	return 0;
 }
 
 /*
  * Return values:
  *
  *   -3: error (exception set)
  *   -2: not found (no exception set)
  * rest: valid rev
  */
 static int index_find_node(indexObject *self, const char *node)
 {
 	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,
 	 * and cache only the matching nodes. This optimizes for cases
 	 * like "hg tip", where only a few nodes are accessed.
 	 *
 	 * After that, we cache every node we visit, using a single
 	 * scan amortized over multiple lookups.  This gives the best
 	 * bulk performance, e.g. for "hg log".
 	 */
 	if (self->ntmisses++ < 4) {
 		for (rev = self->ntrev - 1; rev >= 0; rev--) {
 			const char *n = index_node_existing(self, rev);
 			if (n == NULL)
 				return -3;
 			if (memcmp(node, n, self->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, self->nodelen) == 0) {
 				break;
 			}
 		}
 		self->ntrev = rev;
 	}
 
 	if (rev >= 0)
 		return rev;
 	return -2;
 }
 
 static PyObject *index_getitem(indexObject *self, PyObject *value)
 {
 	char *node;
 	int rev;
 
 	if (PyInt_Check(value)) {
 		long idx;
 		if (!pylong_to_long(value, &idx)) {
 			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;
 }
 
 /*
  * Fully populate the radix tree.
  */
 static int index_populate_nt(indexObject *self)
 {
 	int rev;
 	if (self->ntrev > 0) {
 		for (rev = self->ntrev - 1; rev >= 0; rev--) {
 			const char *n = index_node_existing(self, rev);
 			if (n == NULL)
 				return -1;
 			if (nt_insert(&self->nt, n, rev) == -1)
 				return -1;
 		}
 		self->ntrev = -1;
 	}
 	return 0;
 }
 
 static PyObject *index_partialmatch(indexObject *self, PyObject *args)
 {
 	const char *fullnode;
 	Py_ssize_t nodelen;
 	char *node;
 	int rev, i;
 
 	if (!PyArg_ParseTuple(args, PY23("s#", "y#"), &node, &nodelen))
 		return NULL;
 
 	if (nodelen < 1) {
 		PyErr_SetString(PyExc_ValueError, "key too short");
 		return NULL;
 	}
 
 	if (nodelen > 2 * self->nodelen) {
 		PyErr_SetString(PyExc_ValueError, "key too long");
 		return NULL;
 	}
 
 	for (i = 0; i < nodelen; i++)
 		hexdigit(node, i);
 	if (PyErr_Occurred()) {
 		/* input contains non-hex characters */
 		PyErr_Clear();
 		Py_RETURN_NONE;
 	}
 
 	if (index_init_nt(self) == -1)
 		return NULL;
 	if (index_populate_nt(self) == -1)
 		return NULL;
 	rev = nt_partialmatch(&self->nt, node, nodelen);
 
 	switch (rev) {
 	case -4:
 		raise_revlog_error();
 		return NULL;
 	case -2:
 		Py_RETURN_NONE;
 	case -1:
 		return PyBytes_FromStringAndSize(nullid, 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;
 	if (index_populate_nt(self) == -1)
 		return NULL;
 	length = nt_shortest(&self->nt, node);
 	if (length == -3)
 		return NULL;
 	if (length == -2) {
 		raise_revlog_error();
 		return NULL;
 	}
 	return PyInt_FromLong(length);
 }
 
 static PyObject *index_m_get(indexObject *self, PyObject *args)
 {
 	PyObject *val;
 	char *node;
 	int rev;
 
 	if (!PyArg_ParseTuple(args, "O", &val))
 		return NULL;
 	if (node_check(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);
 }
 
 static int index_contains(indexObject *self, PyObject *value)
 {
 	char *node;
 
 	if (PyInt_Check(value)) {
 		long rev;
 		if (!pylong_to_long(value, &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:
 		return 1;
 	}
 }
 
 static PyObject *index_m_has_node(indexObject *self, PyObject *args)
 {
 	int ret = index_contains(self, args);
 	if (ret < 0)
 		return NULL;
 	return PyBool_FromLong((long)ret);
 }
 
 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;
 }
 
 typedef uint64_t bitmask;
 
 /*
  * Given a disjoint set of revs, return all candidates for the
  * greatest common ancestor. In revset notation, this is the set
  * "heads(::a and ::b and ...)"
  */
 static PyObject *find_gca_candidates(indexObject *self, const int *revs,
                                      int revcount)
 {
 	const bitmask allseen = (1ull << revcount) - 1;
 	const bitmask poison = 1ull << revcount;
 	PyObject *gca = PyList_New(0);
 	int i, v, interesting;
 	int maxrev = -1;
 	bitmask sp;
 	bitmask *seen;
 
 	if (gca == NULL)
 		return PyErr_NoMemory();
 
 	for (i = 0; i < revcount; i++) {
 		if (revs[i] > maxrev)
 			maxrev = revs[i];
 	}
 
 	seen = calloc(sizeof(*seen), maxrev + 1);
 	if (seen == NULL) {
 		Py_DECREF(gca);
 		return PyErr_NoMemory();
 	}
 
 	for (i = 0; i < revcount; i++)
 		seen[revs[i]] = 1ull << i;
 
 	interesting = revcount;
 
 	for (v = maxrev; v >= 0 && interesting; v--) {
 		bitmask sv = seen[v];
 		int parents[2];
 
 		if (!sv)
 			continue;
 
 		if (sv < poison) {
 			interesting -= 1;
 			if (sv == allseen) {
 				PyObject *obj = PyInt_FromLong(v);
 				if (obj == NULL)
 					goto bail;
 				if (PyList_Append(gca, obj) == -1) {
 					Py_DECREF(obj);
 					goto bail;
 				}
 				sv |= poison;
 				for (i = 0; i < revcount; i++) {
 					if (revs[i] == v)
 						goto done;
 				}
 			}
 		}
 		if (index_get_parents(self, v, parents, maxrev) < 0)
 			goto bail;
 
 		for (i = 0; i < 2; i++) {
 			int p = parents[i];
 			if (p == -1)
 				continue;
 			sp = seen[p];
 			if (sv < poison) {
 				if (sp == 0) {
 					seen[p] = sv;
 					interesting++;
 				} else if (sp != sv)
 					seen[p] |= sv;
 			} else {
 				if (sp && sp < poison)
 					interesting--;
 				seen[p] = sv;
 			}
 		}
 	}
 
 done:
 	free(seen);
 	return gca;
 bail:
 	free(seen);
 	Py_XDECREF(gca);
 	return NULL;
 }
 
 /*
  * Given a disjoint set of revs, return the subset with the longest
  * path to the root.
  */
 static PyObject *find_deepest(indexObject *self, PyObject *revs)
 {
 	const Py_ssize_t revcount = PyList_GET_SIZE(revs);
 	static const Py_ssize_t capacity = 24;
 	int *depth, *interesting = NULL;
 	int i, j, v, ninteresting;
 	PyObject *dict = NULL, *keys = NULL;
 	long *seen = NULL;
 	int maxrev = -1;
 	long final;
 
 	if (revcount > capacity) {
 		PyErr_Format(PyExc_OverflowError,
 		             "bitset size (%ld) > capacity (%ld)",
 		             (long)revcount, (long)capacity);
 		return NULL;
 	}
 
 	for (i = 0; i < revcount; i++) {
 		int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
 		if (n > maxrev)
 			maxrev = n;
 	}
 
 	depth = calloc(sizeof(*depth), maxrev + 1);
 	if (depth == NULL)
 		return PyErr_NoMemory();
 
 	seen = calloc(sizeof(*seen), maxrev + 1);
 	if (seen == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	interesting = calloc(sizeof(*interesting), ((size_t)1) << revcount);
 	if (interesting == NULL) {
 		PyErr_NoMemory();
 		goto bail;
 	}
 
 	if (PyList_Sort(revs) == -1)
 		goto bail;
 
 	for (i = 0; i < revcount; i++) {
 		int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
 		long b = 1l << i;
 		depth[n] = 1;
 		seen[n] = b;
 		interesting[b] = 1;
 	}
 
 	/* invariant: ninteresting is the number of non-zero entries in
 	 * interesting. */
 	ninteresting = (int)revcount;
 
 	for (v = maxrev; v >= 0 && ninteresting > 1; v--) {
 		int dv = depth[v];
 		int parents[2];
 		long sv;
 
 		if (dv == 0)
 			continue;
 
 		sv = seen[v];
 		if (index_get_parents(self, v, parents, maxrev) < 0)
 			goto bail;
 
 		for (i = 0; i < 2; i++) {
 			int p = parents[i];
 			long sp;
 			int dp;
 
 			if (p == -1)
 				continue;
 
 			dp = depth[p];
 			sp = seen[p];
 			if (dp <= dv) {
 				depth[p] = dv + 1;
 				if (sp != sv) {
 					interesting[sv] += 1;
 					seen[p] = sv;
 					if (sp) {
 						interesting[sp] -= 1;
 						if (interesting[sp] == 0)
 							ninteresting -= 1;
 					}
 				}
 			} else if (dv == dp - 1) {
 				long nsp = sp | sv;
 				if (nsp == sp)
 					continue;
 				seen[p] = nsp;
 				interesting[sp] -= 1;
 				if (interesting[sp] == 0)
 					ninteresting -= 1;
 				if (interesting[nsp] == 0)
 					ninteresting += 1;
 				interesting[nsp] += 1;
 			}
 		}
 		interesting[sv] -= 1;
 		if (interesting[sv] == 0)
 			ninteresting -= 1;
 	}
 
 	final = 0;
 	j = ninteresting;
 	for (i = 0; i < (int)(2 << revcount) && j > 0; i++) {
 		if (interesting[i] == 0)
 			continue;
 		final |= i;
 		j -= 1;
 	}
 	if (final == 0) {
 		keys = PyList_New(0);
 		goto bail;
 	}
 
 	dict = PyDict_New();
 	if (dict == NULL)
 		goto bail;
 
 	for (i = 0; i < revcount; i++) {
 		PyObject *key;
 
 		if ((final & (1 << i)) == 0)
 			continue;
 
 		key = PyList_GET_ITEM(revs, i);
 		Py_INCREF(key);
 		Py_INCREF(Py_None);
 		if (PyDict_SetItem(dict, key, Py_None) == -1) {
 			Py_DECREF(key);
 			Py_DECREF(Py_None);
 			goto bail;
 		}
 	}
 
 	keys = PyDict_Keys(dict);
 
 bail:
 	free(depth);
 	free(seen);
 	free(interesting);
 	Py_XDECREF(dict);
 
 	return keys;
 }
 
 /*
  * Given a (possibly overlapping) set of revs, return all the
  * common ancestors heads: heads(::args[0] and ::a[1] and ...)
  */
 static PyObject *index_commonancestorsheads(indexObject *self, PyObject *args)
 {
 	PyObject *ret = NULL;
 	Py_ssize_t argcount, i, len;
 	bitmask repeat = 0;
 	int revcount = 0;
 	int *revs;
 
 	argcount = PySequence_Length(args);
 	revs = PyMem_Malloc(argcount * sizeof(*revs));
 	if (argcount > 0 && revs == NULL)
 		return PyErr_NoMemory();
 	len = index_length(self);
 
 	for (i = 0; i < argcount; i++) {
 		static const int capacity = 24;
 		PyObject *obj = PySequence_GetItem(args, i);
 		bitmask x;
 		long val;
 
 		if (!PyInt_Check(obj)) {
 			PyErr_SetString(PyExc_TypeError,
 			                "arguments must all be ints");
 			Py_DECREF(obj);
 			goto bail;
 		}
 		val = PyInt_AsLong(obj);
 		Py_DECREF(obj);
 		if (val == -1) {
 			ret = PyList_New(0);
 			goto done;
 		}
 		if (val < 0 || val >= len) {
 			PyErr_SetString(PyExc_IndexError, "index out of range");
 			goto bail;
 		}
 		/* this cheesy bloom filter lets us avoid some more
 		 * expensive duplicate checks in the common set-is-disjoint
 		 * case */
 		x = 1ull << (val & 0x3f);
 		if (repeat & x) {
 			int k;
 			for (k = 0; k < revcount; k++) {
 				if (val == revs[k])
 					goto duplicate;
 			}
 		} else
 			repeat |= x;
 		if (revcount >= capacity) {
 			PyErr_Format(PyExc_OverflowError,
 			             "bitset size (%d) > capacity (%d)",
 			             revcount, capacity);
 			goto bail;
 		}
 		revs[revcount++] = (int)val;
 	duplicate:;
 	}
 
 	if (revcount == 0) {
 		ret = PyList_New(0);
 		goto done;
 	}
 	if (revcount == 1) {
 		PyObject *obj;
 		ret = PyList_New(1);
 		if (ret == NULL)
 			goto bail;
 		obj = PyInt_FromLong(revs[0]);
 		if (obj == NULL)
 			goto bail;
 		PyList_SET_ITEM(ret, 0, obj);
 		goto done;
 	}
 
 	ret = find_gca_candidates(self, revs, revcount);
 	if (ret == NULL)
 		goto bail;
 
 done:
 	PyMem_Free(revs);
 	return ret;
 
 bail:
 	PyMem_Free(revs);
 	Py_XDECREF(ret);
 	return NULL;
 }
 
 /*
  * Given a (possibly overlapping) set of revs, return the greatest
  * common ancestors: those with the longest path to the root.
  */
 static PyObject *index_ancestors(indexObject *self, PyObject *args)
 {
 	PyObject *ret;
 	PyObject *gca = index_commonancestorsheads(self, args);
 	if (gca == NULL)
 		return NULL;
 
 	if (PyList_GET_SIZE(gca) <= 1) {
 		return gca;
 	}
 
 	ret = find_deepest(self, gca);
 	Py_DECREF(gca);
 	return ret;
 }
 
 /*
  * Invalidate any trie entries introduced by added revs.
  */
 static void index_invalidate_added(indexObject *self, Py_ssize_t start)
 {
 	Py_ssize_t i, len;
 
 	len = self->length + self->new_length;
 	i = start - self->length;
 	if (i < 0)
 		return;
 
 	for (i = start; i < len; i++)
 		nt_delete_node(&self->nt, index_deref(self, i) + 32);
 
 	self->new_length = start - self->length;
 }
 
 /*
  * Delete a numeric range of revs, which must be at the end of the
  * range.
  */
 static int index_slice_del(indexObject *self, PyObject *item)
 {
 	Py_ssize_t start, stop, step, slicelength;
 	Py_ssize_t length = index_length(self) + 1;
 	int ret = 0;
 
 /* Argument changed from PySliceObject* to PyObject* in Python 3. */
 #ifdef IS_PY3K
 	if (PySlice_GetIndicesEx(item, length, &start, &stop, &step,
 	                         &slicelength) < 0)
 #else
 	if (PySlice_GetIndicesEx((PySliceObject *)item, length, &start, &stop,
 	                         &step, &slicelength) < 0)
 #endif
 		return -1;
 
 	if (slicelength <= 0)
 		return 0;
 
 	if ((step < 0 && start < stop) || (step > 0 && start > stop))
 		stop = start;
 
 	if (step < 0) {
 		stop = start + 1;
 		start = stop + step * (slicelength - 1) - 1;
 		step = -step;
 	}
 
 	if (step != 1) {
 		PyErr_SetString(PyExc_ValueError,
 		                "revlog index delete requires step size of 1");
 		return -1;
 	}
 
 	if (stop != length - 1) {
 		PyErr_SetString(PyExc_IndexError,
 		                "revlog index deletion indices are invalid");
 		return -1;
 	}
 
 	if (start < self->length) {
 		if (self->ntinitialized) {
 			Py_ssize_t i;
 
 			for (i = start; 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->new_length)
 				index_invalidate_added(self, self->length);
 			if (self->ntrev > start)
 				self->ntrev = (int)start;
 		} else if (self->new_length) {
 			self->new_length = 0;
 		}
 
 		self->length = start;
 		goto done;
 	}
 
 	if (self->ntinitialized) {
 		index_invalidate_added(self, start);
 		if (self->ntrev > start)
 			self->ntrev = (int)start;
 	} else {
 		self->new_length = start - self->length;
 	}
 done:
 	Py_CLEAR(self->headrevs);
 	return ret;
 }
 
 /*
  * Supported ops:
  *
  * slice deletion
  * string assignment (extend node->rev mapping)
  * string deletion (shrink node->rev mapping)
  */
 static int index_assign_subscript(indexObject *self, PyObject *item,
                                   PyObject *value)
 {
 	char *node;
 	long rev;
 
 	if (PySlice_Check(item) && value == NULL)
 		return index_slice_del(self, item);
 
 	if (node_check(self->nodelen, item, &node) == -1)
 		return -1;
 
 	if (value == NULL)
 		return self->ntinitialized ? nt_delete_node(&self->nt, node)
 		                           : 0;
 	rev = PyInt_AsLong(value);
 	if (rev > INT_MAX || rev < 0) {
 		if (!PyErr_Occurred())
 			PyErr_SetString(PyExc_ValueError, "rev out of range");
 		return -1;
 	}
 
 	if (index_init_nt(self) == -1)
 		return -1;
 	return nt_insert(&self->nt, node, (int)rev);
 }
 
 /*
  * Find all RevlogNG entries in an index that has inline data. Update
  * the optional "offsets" table with those entries.
  */
 static Py_ssize_t inline_scan(indexObject *self, const char **offsets)
 {
 	const char *data = (const char *)self->buf.buf;
 	Py_ssize_t pos = 0;
 	Py_ssize_t end = self->buf.len;
 	long incr = self->entry_size;
 	Py_ssize_t len = 0;
 
 	while (pos + self->entry_size <= end && pos >= 0) {
 		uint32_t comp_len, sidedata_comp_len = 0;
 		/* 3rd element of header is length of compressed inline data */
 		comp_len = getbe32(data + pos + 8);
 		if (self->entry_size == v2_entry_size) {
 			sidedata_comp_len = getbe32(data + pos + 72);
 		}
 		incr = self->entry_size + comp_len + sidedata_comp_len;
 		if (offsets)
 			offsets[len] = data + pos;
 		len++;
 		pos += incr;
 	}
 
 	if (pos != end) {
 		if (!PyErr_Occurred())
 			PyErr_SetString(PyExc_ValueError, "corrupt index file");
 		return -1;
 	}
 
 	return len;
 }
 
 static int index_init(indexObject *self, PyObject *args, PyObject *kwargs)
 {
 	PyObject *data_obj, *inlined_obj, *revlogv2;
 	Py_ssize_t size;
 
 	static char *kwlist[] = {"data", "inlined", "revlogv2", NULL};
 
 	/* Initialize before argument-checking to avoid index_dealloc() crash.
 	 */
 	self->added = NULL;
 	self->new_length = 0;
 	self->added_length = 0;
 	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;
 	self->nodelen = 20;
 	self->nullentry = NULL;
 	self->rust_ext_compat = 1;
 
 	revlogv2 = NULL;
 	if (!PyArg_ParseTupleAndKeywords(args, kwargs, "OO|O", kwlist,
 	                                 &data_obj, &inlined_obj, &revlogv2))
 		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 > (Py_ssize_t)sizeof(nullid)) {
 		PyErr_SetString(PyExc_RuntimeError, "unsupported node size");
 		return -1;
 	}
 
 	if (revlogv2 && PyObject_IsTrue(revlogv2)) {
 		self->format_version = format_v2;
 		self->entry_size = v2_entry_size;
 	} else {
 		self->format_version = format_v1;
 		self->entry_size = v1_entry_size;
 	}
 
-	self->nullentry = Py_BuildValue(
-	    PY23("iiiiiiis#iiBB", "iiiiiiiy#iiBB"), 0, 0, 0, -1, -1, -1, -1,
-	    nullid, self->nodelen, 0, 0, comp_mode_inline, comp_mode_inline);
+	self->nullentry =
+	    Py_BuildValue(PY23("iiiiiiis#iiBBi", "iiiiiiiy#iiBBi"), 0, 0, 0, -1,
+	                  -1, -1, -1, nullid, self->nodelen, 0, 0,
+	                  comp_mode_inline, comp_mode_inline, rank_unknown);
 
 	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;
 
 	self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
 	self->data = data_obj;
 
 	self->ntlookups = self->ntmisses = 0;
 	self->ntrev = -1;
 	Py_INCREF(self->data);
 
 	if (self->inlined) {
 		Py_ssize_t len = inline_scan(self, NULL);
 		if (len == -1)
 			goto bail;
 		self->length = len;
 	} else {
 		if (size % self->entry_size) {
 			PyErr_SetString(PyExc_ValueError, "corrupt index file");
 			goto bail;
 		}
 		self->length = size / self->entry_size;
 	}
 
 	return 0;
 bail:
 	return -1;
 }
 
 static PyObject *index_nodemap(indexObject *self)
 {
 	Py_INCREF(self);
 	return (PyObject *)self;
 }
 
 static void _index_clearcaches(indexObject *self)
 {
 	if (self->offsets) {
 		PyMem_Free((void *)self->offsets);
 		self->offsets = NULL;
 	}
 	if (self->ntinitialized) {
 		nt_dealloc(&self->nt);
 	}
 	self->ntinitialized = 0;
 	Py_CLEAR(self->headrevs);
 }
 
 static PyObject *index_clearcaches(indexObject *self)
 {
 	_index_clearcaches(self);
 	self->ntrev = -1;
 	self->ntlookups = self->ntmisses = 0;
 	Py_RETURN_NONE;
 }
 
 static void index_dealloc(indexObject *self)
 {
 	_index_clearcaches(self);
 	Py_XDECREF(self->filteredrevs);
 	if (self->buf.buf) {
 		PyBuffer_Release(&self->buf);
 		memset(&self->buf, 0, sizeof(self->buf));
 	}
 	Py_XDECREF(self->data);
 	PyMem_Free(self->added);
 	Py_XDECREF(self->nullentry);
 	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"},
     {"get_rev", (PyCFunction)index_m_get, METH_VARARGS,
      "return `rev` associated with a node or None"},
     {"has_node", (PyCFunction)index_m_has_node, METH_O,
      "return True if the node exist in the index"},
     {"rev", (PyCFunction)index_m_rev, METH_O,
      "return `rev` associated with a node or raise RevlogError"},
     {"computephasesmapsets", (PyCFunction)compute_phases_map_sets, METH_VARARGS,
      "compute phases"},
     {"reachableroots2", (PyCFunction)reachableroots2, METH_VARARGS,
      "reachableroots"},
     {"replace_sidedata_info", (PyCFunction)index_replace_sidedata_info,
      METH_VARARGS, "replace an existing index entry with a new value"},
     {"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 */
     {"issnapshot", (PyCFunction)index_issnapshot, METH_O,
      "True if the object is a snapshot"},
     {"findsnapshots", (PyCFunction)index_findsnapshots, METH_VARARGS,
      "Gather snapshot data in a cache dict"},
     {"deltachain", (PyCFunction)index_deltachain, METH_VARARGS,
      "determine revisions with deltas to reconstruct fulltext"},
     {"slicechunktodensity", (PyCFunction)index_slicechunktodensity,
      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"},
     {"entry_binary", (PyCFunction)index_entry_binary, METH_O,
      "return an entry in binary form"},
     {"pack_header", (PyCFunction)index_pack_header, METH_VARARGS,
      "pack the revlog header information into binary"},
     {NULL} /* Sentinel */
 };
 
 static PyGetSetDef index_getset[] = {
     {"nodemap", (getter)index_nodemap, NULL, "nodemap", NULL},
     {NULL} /* Sentinel */
 };
 
 static PyMemberDef index_members[] = {
     {"entry_size", T_LONG, offsetof(indexObject, entry_size), 0,
      "size of an index entry"},
     {"rust_ext_compat", T_LONG, offsetof(indexObject, rust_ext_compat), 0,
      "size of an index entry"},
     {NULL} /* Sentinel */
 };
 
 PyTypeObject HgRevlogIndex_Type = {
     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 */
     index_members,                 /* 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, cache) with elements as
  * follows:
  *
  * index: an index object that lazily parses Revlog (v1 or v2) records
  * cache: if data is inlined, a tuple (0, index_file_content), else None
  *        index_file_content could be a string, or a buffer
  *
  * added complications are for backwards compatibility
  */
 PyObject *parse_index2(PyObject *self, PyObject *args, PyObject *kwargs)
 {
 	PyObject *cache = NULL;
 	indexObject *idx;
 	int ret;
 
 	idx = PyObject_New(indexObject, &HgRevlogIndex_Type);
 	if (idx == NULL)
 		goto bail;
 
 	ret = index_init(idx, args, kwargs);
 	if (ret == -1)
 		goto bail;
 
 	if (idx->inlined) {
 		cache = Py_BuildValue("iO", 0, idx->data);
 		if (cache == NULL)
 			goto bail;
 	} else {
 		cache = Py_None;
 		Py_INCREF(cache);
 	}
 
 	return Py_BuildValue("NN", idx, cache);
 
 bail:
 	Py_XDECREF(idx);
 	Py_XDECREF(cache);
 	return NULL;
 }
 
 static Revlog_CAPI CAPI = {
     /* increment the abi_version field upon each change in the Revlog_CAPI
        struct or in the ABI of the listed functions */
     2,
     index_length,
     index_node,
     HgRevlogIndex_GetParents,
 };
 
 void revlog_module_init(PyObject *mod)
 {
 	PyObject *caps = NULL;
 	HgRevlogIndex_Type.tp_new = PyType_GenericNew;
 	if (PyType_Ready(&HgRevlogIndex_Type) < 0)
 		return;
 	Py_INCREF(&HgRevlogIndex_Type);
 	PyModule_AddObject(mod, "index", (PyObject *)&HgRevlogIndex_Type);
 
 	nodetreeType.tp_new = PyType_GenericNew;
 	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);
 }

mercurial/pure/parsers.py

@@ -1,966 +1,969 b''
 # parsers.py - Python implementation of parsers.c
 #
 # Copyright 2009 Olivia Mackall <[e-mail]> and others
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
 from __future__ import absolute_import
 
 import stat
 import struct
 import zlib
 
 from ..node import (
     nullrev,
     sha1nodeconstants,
 )
 from ..thirdparty import attr
 from .. import (
     error,
     pycompat,
     revlogutils,
     util,
 )
 
 from ..revlogutils import nodemap as nodemaputil
 from ..revlogutils import constants as revlog_constants
 
 stringio = pycompat.bytesio
 
 
 _pack = struct.pack
 _unpack = struct.unpack
 _compress = zlib.compress
 _decompress = zlib.decompress
 
 
 # a special value used internally for `size` if the file come from the other parent
 FROM_P2 = -2
 
 # a special value used internally for `size` if the file is modified/merged/added
 NONNORMAL = -1
 
 # a special value used internally for `time` if the time is ambigeous
 AMBIGUOUS_TIME = -1
 
 # Bits of the `flags` byte inside a node in the file format
 DIRSTATE_V2_WDIR_TRACKED = 1 << 0
 DIRSTATE_V2_P1_TRACKED = 1 << 1
 DIRSTATE_V2_P2_INFO = 1 << 2
 DIRSTATE_V2_MODE_EXEC_PERM = 1 << 3
 DIRSTATE_V2_MODE_IS_SYMLINK = 1 << 4
 DIRSTATE_V2_HAS_FALLBACK_EXEC = 1 << 5
 DIRSTATE_V2_FALLBACK_EXEC = 1 << 6
 DIRSTATE_V2_HAS_FALLBACK_SYMLINK = 1 << 7
 DIRSTATE_V2_FALLBACK_SYMLINK = 1 << 8
 DIRSTATE_V2_EXPECTED_STATE_IS_MODIFIED = 1 << 9
 DIRSTATE_V2_HAS_MODE_AND_SIZE = 1 << 10
 DIRSTATE_V2_HAS_MTIME = 1 << 11
 DIRSTATE_V2_MTIME_SECOND_AMBIGUOUS = 1 << 12
 DIRSTATE_V2_DIRECTORY = 1 << 13
 DIRSTATE_V2_ALL_UNKNOWN_RECORDED = 1 << 14
 DIRSTATE_V2_ALL_IGNORED_RECORDED = 1 << 15
 
 
 @attr.s(slots=True, init=False)
 class DirstateItem(object):
     """represent a dirstate entry
 
     It hold multiple attributes
 
     # about file tracking
     - wc_tracked: is the file tracked by the working copy
     - p1_tracked: is the file tracked in working copy first parent
     - p2_info: the file has been involved in some merge operation. Either
                because it was actually merged, or because the p2 version was
                ahead, or because some rename moved it there. In either case
                `hg status` will want it displayed as modified.
 
     # about the file state expected from p1 manifest:
     - mode: the file mode in p1
     - size: the file size in p1
 
     These value can be set to None, which mean we don't have a meaningful value
     to compare with. Either because we don't really care about them as there
     `status` is known without having to look at the disk or because we don't
     know these right now and a full comparison will be needed to find out if
     the file is clean.
 
     # about the file state on disk last time we saw it:
     - mtime: the last known clean mtime for the file.
 
     This value can be set to None if no cachable state exist. Either because we
     do not care (see previous section) or because we could not cache something
     yet.
     """
 
     _wc_tracked = attr.ib()
     _p1_tracked = attr.ib()
     _p2_info = attr.ib()
     _mode = attr.ib()
     _size = attr.ib()
     _mtime_s = attr.ib()
     _mtime_ns = attr.ib()
     _fallback_exec = attr.ib()
     _fallback_symlink = attr.ib()
     _mtime_second_ambiguous = attr.ib()
 
     def __init__(
         self,
         wc_tracked=False,
         p1_tracked=False,
         p2_info=False,
         has_meaningful_data=True,
         has_meaningful_mtime=True,
         parentfiledata=None,
         fallback_exec=None,
         fallback_symlink=None,
     ):
         self._wc_tracked = wc_tracked
         self._p1_tracked = p1_tracked
         self._p2_info = p2_info
 
         self._fallback_exec = fallback_exec
         self._fallback_symlink = fallback_symlink
 
         self._mode = None
         self._size = None
         self._mtime_s = None
         self._mtime_ns = None
         self._mtime_second_ambiguous = False
         if parentfiledata is None:
             has_meaningful_mtime = False
             has_meaningful_data = False
         elif parentfiledata[2] is None:
             has_meaningful_mtime = False
         if has_meaningful_data:
             self._mode = parentfiledata[0]
             self._size = parentfiledata[1]
         if has_meaningful_mtime:
             (
                 self._mtime_s,
                 self._mtime_ns,
                 self._mtime_second_ambiguous,
             ) = parentfiledata[2]
 
     @classmethod
     def from_v2_data(cls, flags, size, mtime_s, mtime_ns):
         """Build a new DirstateItem object from V2 data"""
         has_mode_size = bool(flags & DIRSTATE_V2_HAS_MODE_AND_SIZE)
         has_meaningful_mtime = bool(flags & DIRSTATE_V2_HAS_MTIME)
         mode = None
 
         if flags & +DIRSTATE_V2_EXPECTED_STATE_IS_MODIFIED:
             # we do not have support for this flag in the code yet,
             # force a lookup for this file.
             has_mode_size = False
             has_meaningful_mtime = False
 
         fallback_exec = None
         if flags & DIRSTATE_V2_HAS_FALLBACK_EXEC:
             fallback_exec = flags & DIRSTATE_V2_FALLBACK_EXEC
 
         fallback_symlink = None
         if flags & DIRSTATE_V2_HAS_FALLBACK_SYMLINK:
             fallback_symlink = flags & DIRSTATE_V2_FALLBACK_SYMLINK
 
         if has_mode_size:
             assert stat.S_IXUSR == 0o100
             if flags & DIRSTATE_V2_MODE_EXEC_PERM:
                 mode = 0o755
             else:
                 mode = 0o644
             if flags & DIRSTATE_V2_MODE_IS_SYMLINK:
                 mode |= stat.S_IFLNK
             else:
                 mode |= stat.S_IFREG
 
         second_ambiguous = flags & DIRSTATE_V2_MTIME_SECOND_AMBIGUOUS
         return cls(
             wc_tracked=bool(flags & DIRSTATE_V2_WDIR_TRACKED),
             p1_tracked=bool(flags & DIRSTATE_V2_P1_TRACKED),
             p2_info=bool(flags & DIRSTATE_V2_P2_INFO),
             has_meaningful_data=has_mode_size,
             has_meaningful_mtime=has_meaningful_mtime,
             parentfiledata=(mode, size, (mtime_s, mtime_ns, second_ambiguous)),
             fallback_exec=fallback_exec,
             fallback_symlink=fallback_symlink,
         )
 
     @classmethod
     def from_v1_data(cls, state, mode, size, mtime):
         """Build a new DirstateItem object from V1 data
 
         Since the dirstate-v1 format is frozen, the signature of this function
         is not expected to change, unlike the __init__ one.
         """
         if state == b'm':
             return cls(wc_tracked=True, p1_tracked=True, p2_info=True)
         elif state == b'a':
             return cls(wc_tracked=True)
         elif state == b'r':
             if size == NONNORMAL:
                 p1_tracked = True
                 p2_info = True
             elif size == FROM_P2:
                 p1_tracked = False
                 p2_info = True
             else:
                 p1_tracked = True
                 p2_info = False
             return cls(p1_tracked=p1_tracked, p2_info=p2_info)
         elif state == b'n':
             if size == FROM_P2:
                 return cls(wc_tracked=True, p2_info=True)
             elif size == NONNORMAL:
                 return cls(wc_tracked=True, p1_tracked=True)
             elif mtime == AMBIGUOUS_TIME:
                 return cls(
                     wc_tracked=True,
                     p1_tracked=True,
                     has_meaningful_mtime=False,
                     parentfiledata=(mode, size, (42, 0, False)),
                 )
             else:
                 return cls(
                     wc_tracked=True,
                     p1_tracked=True,
                     parentfiledata=(mode, size, (mtime, 0, False)),
                 )
         else:
             raise RuntimeError(b'unknown state: %s' % state)
 
     def set_possibly_dirty(self):
         """Mark a file as "possibly dirty"
 
         This means the next status call will have to actually check its content
         to make sure it is correct.
         """
         self._mtime_s = None
         self._mtime_ns = None
 
     def set_clean(self, mode, size, mtime):
         """mark a file as "clean" cancelling potential "possibly dirty call"
 
         Note: this function is a descendant of `dirstate.normal` and is
         currently expected to be call on "normal" entry only. There are not
         reason for this to not change in the future as long as the ccode is
         updated to preserve the proper state of the non-normal files.
         """
         self._wc_tracked = True
         self._p1_tracked = True
         self._mode = mode
         self._size = size
         self._mtime_s, self._mtime_ns, self._mtime_second_ambiguous = mtime
 
     def set_tracked(self):
         """mark a file as tracked in the working copy
 
         This will ultimately be called by command like `hg add`.
         """
         self._wc_tracked = True
         # `set_tracked` is replacing various `normallookup` call. So we mark
         # the files as needing lookup
         #
         # Consider dropping this in the future in favor of something less broad.
         self._mtime_s = None
         self._mtime_ns = None
 
     def set_untracked(self):
         """mark a file as untracked in the working copy
 
         This will ultimately be called by command like `hg remove`.
         """
         self._wc_tracked = False
         self._mode = None
         self._size = None
         self._mtime_s = None
         self._mtime_ns = None
 
     def drop_merge_data(self):
         """remove all "merge-only" from a DirstateItem
 
         This is to be call by the dirstatemap code when the second parent is dropped
         """
         if self._p2_info:
             self._p2_info = False
             self._mode = None
             self._size = None
             self._mtime_s = None
             self._mtime_ns = None
 
     @property
     def mode(self):
         return self.v1_mode()
 
     @property
     def size(self):
         return self.v1_size()
 
     @property
     def mtime(self):
         return self.v1_mtime()
 
     def mtime_likely_equal_to(self, other_mtime):
         self_sec = self._mtime_s
         if self_sec is None:
             return False
         self_ns = self._mtime_ns
         other_sec, other_ns, second_ambiguous = other_mtime
         if self_sec != other_sec:
             # seconds are different theses mtime are definitly not equal
             return False
         elif other_ns == 0 or self_ns == 0:
             # at least one side as no nano-seconds information
 
             if self._mtime_second_ambiguous:
                 # We cannot trust the mtime in this case
                 return False
             else:
                 # the "seconds" value was reliable on its own. We are good to go.
                 return True
         else:
             # We have nano second information, let us use them !
             return self_ns == other_ns
 
     @property
     def state(self):
         """
         States are:
           n  normal
           m  needs merging
           r  marked for removal
           a  marked for addition
 
         XXX This "state" is a bit obscure and mostly a direct expression of the
         dirstatev1 format. It would make sense to ultimately deprecate it in
         favor of the more "semantic" attributes.
         """
         if not self.any_tracked:
             return b'?'
         return self.v1_state()
 
     @property
     def has_fallback_exec(self):
         """True if "fallback" information are available for the "exec" bit
 
         Fallback information can be stored in the dirstate to keep track of
         filesystem attribute tracked by Mercurial when the underlying file
         system or operating system does not support that property, (e.g.
         Windows).
 
         Not all version of the dirstate on-disk storage support preserving this
         information.
         """
         return self._fallback_exec is not None
 
     @property
     def fallback_exec(self):
         """ "fallback" information for the executable bit
 
         True if the file should be considered executable when we cannot get
         this information from the files system. False if it should be
         considered non-executable.
 
         See has_fallback_exec for details."""
         return self._fallback_exec
 
     @fallback_exec.setter
     def set_fallback_exec(self, value):
         """control "fallback" executable bit
 
         Set to:
         - True if the file should be considered executable,
         - False if the file should be considered non-executable,
         - None if we do not have valid fallback data.
 
         See has_fallback_exec for details."""
         if value is None:
             self._fallback_exec = None
         else:
             self._fallback_exec = bool(value)
 
     @property
     def has_fallback_symlink(self):
         """True if "fallback" information are available for symlink status
 
         Fallback information can be stored in the dirstate to keep track of
         filesystem attribute tracked by Mercurial when the underlying file
         system or operating system does not support that property, (e.g.
         Windows).
 
         Not all version of the dirstate on-disk storage support preserving this
         information."""
         return self._fallback_symlink is not None
 
     @property
     def fallback_symlink(self):
         """ "fallback" information for symlink status
 
         True if the file should be considered executable when we cannot get
         this information from the files system. False if it should be
         considered non-executable.
 
         See has_fallback_exec for details."""
         return self._fallback_symlink
 
     @fallback_symlink.setter
     def set_fallback_symlink(self, value):
         """control "fallback" symlink status
 
         Set to:
         - True if the file should be considered a symlink,
         - False if the file should be considered not a symlink,
         - None if we do not have valid fallback data.
 
         See has_fallback_symlink for details."""
         if value is None:
             self._fallback_symlink = None
         else:
             self._fallback_symlink = bool(value)
 
     @property
     def tracked(self):
         """True is the file is tracked in the working copy"""
         return self._wc_tracked
 
     @property
     def any_tracked(self):
         """True is the file is tracked anywhere (wc or parents)"""
         return self._wc_tracked or self._p1_tracked or self._p2_info
 
     @property
     def added(self):
         """True if the file has been added"""
         return self._wc_tracked and not (self._p1_tracked or self._p2_info)
 
     @property
     def maybe_clean(self):
         """True if the file has a chance to be in the "clean" state"""
         if not self._wc_tracked:
             return False
         elif not self._p1_tracked:
             return False
         elif self._p2_info:
             return False
         return True
 
     @property
     def p1_tracked(self):
         """True if the file is tracked in the first parent manifest"""
         return self._p1_tracked
 
     @property
     def p2_info(self):
         """True if the file needed to merge or apply any input from p2
 
         See the class documentation for details.
         """
         return self._wc_tracked and self._p2_info
 
     @property
     def removed(self):
         """True if the file has been removed"""
         return not self._wc_tracked and (self._p1_tracked or self._p2_info)
 
     def v2_data(self):
         """Returns (flags, mode, size, mtime) for v2 serialization"""
         flags = 0
         if self._wc_tracked:
             flags |= DIRSTATE_V2_WDIR_TRACKED
         if self._p1_tracked:
             flags |= DIRSTATE_V2_P1_TRACKED
         if self._p2_info:
             flags |= DIRSTATE_V2_P2_INFO
         if self._mode is not None and self._size is not None:
             flags |= DIRSTATE_V2_HAS_MODE_AND_SIZE
             if self.mode & stat.S_IXUSR:
                 flags |= DIRSTATE_V2_MODE_EXEC_PERM
             if stat.S_ISLNK(self.mode):
                 flags |= DIRSTATE_V2_MODE_IS_SYMLINK
         if self._mtime_s is not None:
             flags |= DIRSTATE_V2_HAS_MTIME
         if self._mtime_second_ambiguous:
             flags |= DIRSTATE_V2_MTIME_SECOND_AMBIGUOUS
 
         if self._fallback_exec is not None:
             flags |= DIRSTATE_V2_HAS_FALLBACK_EXEC
             if self._fallback_exec:
                 flags |= DIRSTATE_V2_FALLBACK_EXEC
 
         if self._fallback_symlink is not None:
             flags |= DIRSTATE_V2_HAS_FALLBACK_SYMLINK
             if self._fallback_symlink:
                 flags |= DIRSTATE_V2_FALLBACK_SYMLINK
 
         # Note: we do not need to do anything regarding
         # DIRSTATE_V2_ALL_UNKNOWN_RECORDED and DIRSTATE_V2_ALL_IGNORED_RECORDED
         # since we never set _DIRSTATE_V2_HAS_DIRCTORY_MTIME
         return (flags, self._size or 0, self._mtime_s or 0, self._mtime_ns or 0)
 
     def v1_state(self):
         """return a "state" suitable for v1 serialization"""
         if not self.any_tracked:
             # the object has no state to record, this is -currently-
             # unsupported
             raise RuntimeError('untracked item')
         elif self.removed:
             return b'r'
         elif self._p1_tracked and self._p2_info:
             return b'm'
         elif self.added:
             return b'a'
         else:
             return b'n'
 
     def v1_mode(self):
         """return a "mode" suitable for v1 serialization"""
         return self._mode if self._mode is not None else 0
 
     def v1_size(self):
         """return a "size" suitable for v1 serialization"""
         if not self.any_tracked:
             # the object has no state to record, this is -currently-
             # unsupported
             raise RuntimeError('untracked item')
         elif self.removed and self._p1_tracked and self._p2_info:
             return NONNORMAL
         elif self._p2_info:
             return FROM_P2
         elif self.removed:
             return 0
         elif self.added:
             return NONNORMAL
         elif self._size is None:
             return NONNORMAL
         else:
             return self._size
 
     def v1_mtime(self):
         """return a "mtime" suitable for v1 serialization"""
         if not self.any_tracked:
             # the object has no state to record, this is -currently-
             # unsupported
             raise RuntimeError('untracked item')
         elif self.removed:
             return 0
         elif self._mtime_s is None:
             return AMBIGUOUS_TIME
         elif self._p2_info:
             return AMBIGUOUS_TIME
         elif not self._p1_tracked:
             return AMBIGUOUS_TIME
         elif self._mtime_second_ambiguous:
             return AMBIGUOUS_TIME
         else:
             return self._mtime_s
 
 
 def gettype(q):
     return int(q & 0xFFFF)
 
 
 class BaseIndexObject(object):
     # Can I be passed to an algorithme implemented in Rust ?
     rust_ext_compat = 0
     # Format of an index entry according to Python's `struct` language
     index_format = revlog_constants.INDEX_ENTRY_V1
     # Size of a C unsigned long long int, platform independent
     big_int_size = struct.calcsize(b'>Q')
     # Size of a C long int, platform independent
     int_size = struct.calcsize(b'>i')
     # An empty index entry, used as a default value to be overridden, or nullrev
     null_item = (
         0,
         0,
         0,
         -1,
         -1,
         -1,
         -1,
         sha1nodeconstants.nullid,
         0,
         0,
         revlog_constants.COMP_MODE_INLINE,
         revlog_constants.COMP_MODE_INLINE,
+        revlog_constants.RANK_UNKNOWN,
     )
 
     @util.propertycache
     def entry_size(self):
         return self.index_format.size
 
     @property
     def nodemap(self):
         msg = b"index.nodemap is deprecated, use index.[has_node|rev|get_rev]"
         util.nouideprecwarn(msg, b'5.3', stacklevel=2)
         return self._nodemap
 
     @util.propertycache
     def _nodemap(self):
         nodemap = nodemaputil.NodeMap({sha1nodeconstants.nullid: nullrev})
         for r in range(0, len(self)):
             n = self[r][7]
             nodemap[n] = r
         return nodemap
 
     def has_node(self, node):
         """return True if the node exist in the index"""
         return node in self._nodemap
 
     def rev(self, node):
         """return a revision for a node
 
         If the node is unknown, raise a RevlogError"""
         return self._nodemap[node]
 
     def get_rev(self, node):
         """return a revision for a node
 
         If the node is unknown, return None"""
         return self._nodemap.get(node)
 
     def _stripnodes(self, start):
         if '_nodemap' in vars(self):
             for r in range(start, len(self)):
                 n = self[r][7]
                 del self._nodemap[n]
 
     def clearcaches(self):
         self.__dict__.pop('_nodemap', None)
 
     def __len__(self):
         return self._lgt + len(self._extra)
 
     def append(self, tup):
         if '_nodemap' in vars(self):
             self._nodemap[tup[7]] = len(self)
         data = self._pack_entry(len(self), tup)
         self._extra.append(data)
 
     def _pack_entry(self, rev, entry):
         assert entry[8] == 0
         assert entry[9] == 0
         return self.index_format.pack(*entry[:8])
 
     def _check_index(self, i):
         if not isinstance(i, int):
             raise TypeError(b"expecting int indexes")
         if i < 0 or i >= len(self):
             raise IndexError(i)
 
     def __getitem__(self, i):
         if i == -1:
             return self.null_item
         self._check_index(i)
         if i >= self._lgt:
             data = self._extra[i - self._lgt]
         else:
             index = self._calculate_index(i)
             data = self._data[index : index + self.entry_size]
         r = self._unpack_entry(i, data)
         if self._lgt and i == 0:
             offset = revlogutils.offset_type(0, gettype(r[0]))
             r = (offset,) + r[1:]
         return r
 
     def _unpack_entry(self, rev, data):
         r = self.index_format.unpack(data)
         r = r + (
             0,
             0,
             revlog_constants.COMP_MODE_INLINE,
             revlog_constants.COMP_MODE_INLINE,
+            revlog_constants.RANK_UNKNOWN,
         )
         return r
 
     def pack_header(self, header):
         """pack header information as binary"""
         v_fmt = revlog_constants.INDEX_HEADER
         return v_fmt.pack(header)
 
     def entry_binary(self, rev):
         """return the raw binary string representing a revision"""
         entry = self[rev]
         p = revlog_constants.INDEX_ENTRY_V1.pack(*entry[:8])
         if rev == 0:
             p = p[revlog_constants.INDEX_HEADER.size :]
         return p
 
 
 class IndexObject(BaseIndexObject):
     def __init__(self, data):
         assert len(data) % self.entry_size == 0, (
             len(data),
             self.entry_size,
             len(data) % self.entry_size,
         )
         self._data = data
         self._lgt = len(data) // self.entry_size
         self._extra = []
 
     def _calculate_index(self, i):
         return i * self.entry_size
 
     def __delitem__(self, i):
         if not isinstance(i, slice) or not i.stop == -1 or i.step is not None:
             raise ValueError(b"deleting slices only supports a:-1 with step 1")
         i = i.start
         self._check_index(i)
         self._stripnodes(i)
         if i < self._lgt:
             self._data = self._data[: i * self.entry_size]
             self._lgt = i
             self._extra = []
         else:
             self._extra = self._extra[: i - self._lgt]
 
 
 class PersistentNodeMapIndexObject(IndexObject):
     """a Debug oriented class to test persistent nodemap
 
     We need a simple python object to test API and higher level behavior. See
     the Rust implementation for  more serious usage. This should be used only
     through the dedicated `devel.persistent-nodemap` config.
     """
 
     def nodemap_data_all(self):
         """Return bytes containing a full serialization of a nodemap
 
         The nodemap should be valid for the full set of revisions in the
         index."""
         return nodemaputil.persistent_data(self)
 
     def nodemap_data_incremental(self):
         """Return bytes containing a incremental update to persistent nodemap
 
         This containst the data for an append-only update of the data provided
         in the last call to `update_nodemap_data`.
         """
         if self._nm_root is None:
             return None
         docket = self._nm_docket
         changed, data = nodemaputil.update_persistent_data(
             self, self._nm_root, self._nm_max_idx, self._nm_docket.tip_rev
         )
 
         self._nm_root = self._nm_max_idx = self._nm_docket = None
         return docket, changed, data
 
     def update_nodemap_data(self, docket, nm_data):
         """provide full block of persisted binary data for a nodemap
 
         The data are expected to come from disk. See `nodemap_data_all` for a
         produceur of such data."""
         if nm_data is not None:
             self._nm_root, self._nm_max_idx = nodemaputil.parse_data(nm_data)
             if self._nm_root:
                 self._nm_docket = docket
             else:
                 self._nm_root = self._nm_max_idx = self._nm_docket = None
 
 
 class InlinedIndexObject(BaseIndexObject):
     def __init__(self, data, inline=0):
         self._data = data
         self._lgt = self._inline_scan(None)
         self._inline_scan(self._lgt)
         self._extra = []
 
     def _inline_scan(self, lgt):
         off = 0
         if lgt is not None:
             self._offsets = [0] * lgt
         count = 0
         while off <= len(self._data) - self.entry_size:
             start = off + self.big_int_size
             (s,) = struct.unpack(
                 b'>i',
                 self._data[start : start + self.int_size],
             )
             if lgt is not None:
                 self._offsets[count] = off
             count += 1
             off += self.entry_size + s
         if off != len(self._data):
             raise ValueError(b"corrupted data")
         return count
 
     def __delitem__(self, i):
         if not isinstance(i, slice) or not i.stop == -1 or i.step is not None:
             raise ValueError(b"deleting slices only supports a:-1 with step 1")
         i = i.start
         self._check_index(i)
         self._stripnodes(i)
         if i < self._lgt:
             self._offsets = self._offsets[:i]
             self._lgt = i
             self._extra = []
         else:
             self._extra = self._extra[: i - self._lgt]
 
     def _calculate_index(self, i):
         return self._offsets[i]
 
 
 def parse_index2(data, inline, revlogv2=False):
     if not inline:
         cls = IndexObject2 if revlogv2 else IndexObject
         return cls(data), None
     cls = InlinedIndexObject
     return cls(data, inline), (0, data)
 
 
 def parse_index_cl_v2(data):
     return IndexChangelogV2(data), None
 
 
 class IndexObject2(IndexObject):
     index_format = revlog_constants.INDEX_ENTRY_V2
 
     def replace_sidedata_info(
         self,
         rev,
         sidedata_offset,
         sidedata_length,
         offset_flags,
         compression_mode,
     ):
         """
         Replace an existing index entry's sidedata offset and length with new
         ones.
         This cannot be used outside of the context of sidedata rewriting,
         inside the transaction that creates the revision `rev`.
         """
         if rev < 0:
             raise KeyError
         self._check_index(rev)
         if rev < self._lgt:
             msg = b"cannot rewrite entries outside of this transaction"
             raise KeyError(msg)
         else:
             entry = list(self[rev])
             entry[0] = offset_flags
             entry[8] = sidedata_offset
             entry[9] = sidedata_length
             entry[11] = compression_mode
             entry = tuple(entry)
             new = self._pack_entry(rev, entry)
             self._extra[rev - self._lgt] = new
 
     def _unpack_entry(self, rev, data):
         data = self.index_format.unpack(data)
         entry = data[:10]
         data_comp = data[10] & 3
         sidedata_comp = (data[10] & (3 << 2)) >> 2
-        return entry + (data_comp, sidedata_comp)
+        return entry + (data_comp, sidedata_comp, revlog_constants.RANK_UNKNOWN)
 
     def _pack_entry(self, rev, entry):
         data = entry[:10]
         data_comp = entry[10] & 3
         sidedata_comp = (entry[11] & 3) << 2
         data += (data_comp | sidedata_comp,)
 
         return self.index_format.pack(*data)
 
     def entry_binary(self, rev):
         """return the raw binary string representing a revision"""
         entry = self[rev]
         return self._pack_entry(rev, entry)
 
     def pack_header(self, header):
         """pack header information as binary"""
         msg = 'version header should go in the docket, not the index: %d'
         msg %= header
         raise error.ProgrammingError(msg)
 
 
 class IndexChangelogV2(IndexObject2):
     index_format = revlog_constants.INDEX_ENTRY_CL_V2
 
     def _unpack_entry(self, rev, data, r=True):
         items = self.index_format.unpack(data)
         return (
             items[revlog_constants.INDEX_ENTRY_V2_IDX_OFFSET],
             items[revlog_constants.INDEX_ENTRY_V2_IDX_COMPRESSED_LENGTH],
             items[revlog_constants.INDEX_ENTRY_V2_IDX_UNCOMPRESSED_LENGTH],
             rev,
             rev,
             items[revlog_constants.INDEX_ENTRY_V2_IDX_PARENT_1],
             items[revlog_constants.INDEX_ENTRY_V2_IDX_PARENT_2],
             items[revlog_constants.INDEX_ENTRY_V2_IDX_NODEID],
             items[revlog_constants.INDEX_ENTRY_V2_IDX_SIDEDATA_OFFSET],
             items[
                 revlog_constants.INDEX_ENTRY_V2_IDX_SIDEDATA_COMPRESSED_LENGTH
             ],
             items[revlog_constants.INDEX_ENTRY_V2_IDX_COMPRESSION_MODE] & 3,
             (items[revlog_constants.INDEX_ENTRY_V2_IDX_COMPRESSION_MODE] >> 2)
             & 3,
+            revlog_constants.RANK_UNKNOWN,
         )
 
     def _pack_entry(self, rev, entry):
 
         base = entry[revlog_constants.ENTRY_DELTA_BASE]
         link_rev = entry[revlog_constants.ENTRY_LINK_REV]
         assert base == rev, (base, rev)
         assert link_rev == rev, (link_rev, rev)
         data = (
             entry[revlog_constants.ENTRY_DATA_OFFSET],
             entry[revlog_constants.ENTRY_DATA_COMPRESSED_LENGTH],
             entry[revlog_constants.ENTRY_DATA_UNCOMPRESSED_LENGTH],
             entry[revlog_constants.ENTRY_PARENT_1],
             entry[revlog_constants.ENTRY_PARENT_2],
             entry[revlog_constants.ENTRY_NODE_ID],
             entry[revlog_constants.ENTRY_SIDEDATA_OFFSET],
             entry[revlog_constants.ENTRY_SIDEDATA_COMPRESSED_LENGTH],
             entry[revlog_constants.ENTRY_DATA_COMPRESSION_MODE] & 3
             | (entry[revlog_constants.ENTRY_SIDEDATA_COMPRESSION_MODE] & 3)
             << 2,
         )
         return self.index_format.pack(*data)
 
 
 def parse_index_devel_nodemap(data, inline):
     """like parse_index2, but alway return a PersistentNodeMapIndexObject"""
     return PersistentNodeMapIndexObject(data), None
 
 
 def parse_dirstate(dmap, copymap, st):
     parents = [st[:20], st[20:40]]
     # dereference fields so they will be local in loop
     format = b">cllll"
     e_size = struct.calcsize(format)
     pos1 = 40
     l = len(st)
 
     # the inner loop
     while pos1 < l:
         pos2 = pos1 + e_size
         e = _unpack(b">cllll", st[pos1:pos2])  # a literal here is faster
         pos1 = pos2 + e[4]
         f = st[pos2:pos1]
         if b'\0' in f:
             f, c = f.split(b'\0')
             copymap[f] = c
         dmap[f] = DirstateItem.from_v1_data(*e[:4])
     return parents
 
 
 def pack_dirstate(dmap, copymap, pl):
     cs = stringio()
     write = cs.write
     write(b"".join(pl))
     for f, e in pycompat.iteritems(dmap):
         if f in copymap:
             f = b"%s\0%s" % (f, copymap[f])
         e = _pack(
             b">cllll",
             e.v1_state(),
             e.v1_mode(),
             e.v1_size(),
             e.v1_mtime(),
             len(f),
         )
         write(e)
         write(f)
     return cs.getvalue()

mercurial/revlogutils/__init__.py

@@ -1,80 +1,83 b''
 # mercurial.revlogutils -- basic utilities for revlog
 #
 # Copyright 2019 Pierre-Yves David <[e-mail]>
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
 from __future__ import absolute_import
 
 from ..thirdparty import attr
 from ..interfaces import repository
 
 # See mercurial.revlogutils.constants for doc
 COMP_MODE_INLINE = 2
+RANK_UNKNOWN = -1
 
 
 def offset_type(offset, type):
     if (type & ~repository.REVISION_FLAGS_KNOWN) != 0:
         raise ValueError(b'unknown revlog index flags: %d' % type)
     return int(int(offset) << 16 | type)
 
 
 def entry(
     data_offset,
     data_compressed_length,
     data_delta_base,
     link_rev,
     parent_rev_1,
     parent_rev_2,
     node_id,
     flags=0,
     data_uncompressed_length=-1,
     data_compression_mode=COMP_MODE_INLINE,
     sidedata_offset=0,
     sidedata_compressed_length=0,
     sidedata_compression_mode=COMP_MODE_INLINE,
+    rank=RANK_UNKNOWN,
 ):
     """Build one entry from symbolic name
 
     This is useful to abstract the actual detail of how we build the entry
     tuple for caller who don't care about it.
 
     This should always be called using keyword arguments. Some arguments have
     default value, this match the value used by index version that does not store such data.
     """
     return (
         offset_type(data_offset, flags),
         data_compressed_length,
         data_uncompressed_length,
         data_delta_base,
         link_rev,
         parent_rev_1,
         parent_rev_2,
         node_id,
         sidedata_offset,
         sidedata_compressed_length,
         data_compression_mode,
         sidedata_compression_mode,
+        rank,
     )
 
 
 @attr.s(slots=True, frozen=True)
 class revisioninfo(object):
     """Information about a revision that allows building its fulltext
     node:       expected hash of the revision
     p1, p2:     parent revs of the revision
     btext:      built text cache consisting of a one-element list
     cachedelta: (baserev, uncompressed_delta) or None
     flags:      flags associated to the revision storage
 
     One of btext[0] or cachedelta must be set.
     """
 
     node = attr.ib()
     p1 = attr.ib()
     p2 = attr.ib()
     btext = attr.ib()
     textlen = attr.ib()
     cachedelta = attr.ib()
     flags = attr.ib()

mercurial/revlogutils/constants.py

@@ -1,291 +1,302 b''
 # revlogdeltas.py - constant used for revlog logic.
 #
 # Copyright 2005-2007 Olivia Mackall <[e-mail]>
 # Copyright 2018 Octobus <[e-mail]>
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 """Helper class to compute deltas stored inside revlogs"""
 
 from __future__ import absolute_import
 
 import struct
 
 from ..interfaces import repository
 from .. import revlogutils
 
 ### Internal utily constants
 
 KIND_CHANGELOG = 1001  # over 256 to not be comparable with a bytes
 KIND_MANIFESTLOG = 1002
 KIND_FILELOG = 1003
 KIND_OTHER = 1004
 
 ALL_KINDS = {
     KIND_CHANGELOG,
     KIND_MANIFESTLOG,
     KIND_FILELOG,
     KIND_OTHER,
 }
 
 ### Index entry key
 #
 #
 #    Internal details
 #    ----------------
 #
 #    A large part of the revlog logic deals with revisions' "index entries", tuple
 #    objects that contains the same "items" whatever the revlog version.
 #    Different versions will have different ways of storing these items (sometimes
 #    not having them at all), but the tuple will always be the same. New fields
 #    are usually added at the end to avoid breaking existing code that relies
 #    on the existing order. The field are defined as follows:
 
 #    [0] offset:
 #            The byte index of the start of revision data chunk.
 #            That value is shifted up by 16 bits. use "offset = field >> 16" to
 #            retrieve it.
 #
 #        flags:
 #            A flag field that carries special information or changes the behavior
 #            of the revision. (see `REVIDX_*` constants for details)
 #            The flag field only occupies the first 16 bits of this field,
 #            use "flags = field & 0xFFFF" to retrieve the value.
 ENTRY_DATA_OFFSET = 0
 
 #    [1] compressed length:
 #            The size, in bytes, of the chunk on disk
 ENTRY_DATA_COMPRESSED_LENGTH = 1
 
 #    [2] uncompressed length:
 #            The size, in bytes, of the full revision once reconstructed.
 ENTRY_DATA_UNCOMPRESSED_LENGTH = 2
 
 #    [3] base rev:
 #            Either the base of the revision delta chain (without general
 #            delta), or the base of the delta (stored in the data chunk)
 #            with general delta.
 ENTRY_DELTA_BASE = 3
 
 #    [4] link rev:
 #            Changelog revision number of the changeset introducing this
 #            revision.
 ENTRY_LINK_REV = 4
 
 #    [5] parent 1 rev:
 #            Revision number of the first parent
 ENTRY_PARENT_1 = 5
 
 #    [6] parent 2 rev:
 #            Revision number of the second parent
 ENTRY_PARENT_2 = 6
 
 #    [7] node id:
 #            The node id of the current revision
 ENTRY_NODE_ID = 7
 
 #    [8] sidedata offset:
 #            The byte index of the start of the revision's side-data chunk.
 ENTRY_SIDEDATA_OFFSET = 8
 
 #    [9] sidedata chunk length:
 #            The size, in bytes, of the revision's side-data chunk.
 ENTRY_SIDEDATA_COMPRESSED_LENGTH = 9
 
 #    [10] data compression mode:
 #            two bits that detail the way the data chunk is compressed on disk.
 #            (see "COMP_MODE_*" constants for details). For revlog version 0 and
 #            1 this will always be COMP_MODE_INLINE.
 ENTRY_DATA_COMPRESSION_MODE = 10
 
 #    [11] side-data compression mode:
 #            two bits that detail the way the sidedata chunk is compressed on disk.
 #            (see "COMP_MODE_*" constants for details)
 ENTRY_SIDEDATA_COMPRESSION_MODE = 11
 
+#    [12] Revision rank:
+#            The number of revision under this one.
+#
+#            Formally this is defined as : rank(X) = len(ancestors(X) + X)
+#
+#            If rank == -1; then we do not have this information available.
+#            Only `null` has a rank of 0.
+ENTRY_RANK = 12
+
+RANK_UNKNOWN = -1
+
 ### main revlog header
 
 # We cannot rely on  Struct.format is inconsistent for python <=3.6 versus above
 INDEX_HEADER_FMT = b">I"
 INDEX_HEADER = struct.Struct(INDEX_HEADER_FMT)
 
 ## revlog version
 REVLOGV0 = 0
 REVLOGV1 = 1
 # Dummy value until file format is finalized.
 REVLOGV2 = 0xDEAD
 # Dummy value until file format is finalized.
 CHANGELOGV2 = 0xD34D
 
 ##  global revlog header flags
 # Shared across v1 and v2.
 FLAG_INLINE_DATA = 1 << 16
 # Only used by v1, implied by v2.
 FLAG_GENERALDELTA = 1 << 17
 REVLOG_DEFAULT_FLAGS = FLAG_INLINE_DATA
 REVLOG_DEFAULT_FORMAT = REVLOGV1
 REVLOG_DEFAULT_VERSION = REVLOG_DEFAULT_FORMAT | REVLOG_DEFAULT_FLAGS
 REVLOGV0_FLAGS = 0
 REVLOGV1_FLAGS = FLAG_INLINE_DATA | FLAG_GENERALDELTA
 REVLOGV2_FLAGS = FLAG_INLINE_DATA
 CHANGELOGV2_FLAGS = 0
 
 ### individual entry
 
 ## index v0:
 #  4 bytes: offset
 #  4 bytes: compressed length
 #  4 bytes: base rev
 #  4 bytes: link rev
 # 20 bytes: parent 1 nodeid
 # 20 bytes: parent 2 nodeid
 # 20 bytes: nodeid
 INDEX_ENTRY_V0 = struct.Struct(b">4l20s20s20s")
 
 ## index v1
 #  6 bytes: offset
 #  2 bytes: flags
 #  4 bytes: compressed length
 #  4 bytes: uncompressed length
 #  4 bytes: base rev
 #  4 bytes: link rev
 #  4 bytes: parent 1 rev
 #  4 bytes: parent 2 rev
 # 32 bytes: nodeid
 INDEX_ENTRY_V1 = struct.Struct(b">Qiiiiii20s12x")
 assert INDEX_ENTRY_V1.size == 32 * 2
 
 #  6 bytes: offset
 #  2 bytes: flags
 #  4 bytes: compressed length
 #  4 bytes: uncompressed length
 #  4 bytes: base rev
 #  4 bytes: link rev
 #  4 bytes: parent 1 rev
 #  4 bytes: parent 2 rev
 # 32 bytes: nodeid
 #  8 bytes: sidedata offset
 #  4 bytes: sidedata compressed length
 #  1 bytes: compression mode (2 lower bit are data_compression_mode)
 #  19 bytes: Padding to align to 96 bytes (see RevlogV2Plan wiki page)
 INDEX_ENTRY_V2 = struct.Struct(b">Qiiiiii20s12xQiB19x")
 assert INDEX_ENTRY_V2.size == 32 * 3, INDEX_ENTRY_V2.size
 
 #  6 bytes: offset
 #  2 bytes: flags
 #  4 bytes: compressed length
 #  4 bytes: uncompressed length
 #  4 bytes: parent 1 rev
 #  4 bytes: parent 2 rev
 # 32 bytes: nodeid
 #  8 bytes: sidedata offset
 #  4 bytes: sidedata compressed length
 #  1 bytes: compression mode (2 lower bit are data_compression_mode)
 #  27 bytes: Padding to align to 96 bytes (see RevlogV2Plan wiki page)
 INDEX_ENTRY_CL_V2 = struct.Struct(b">Qiiii20s12xQiB27x")
 assert INDEX_ENTRY_CL_V2.size == 32 * 3, INDEX_ENTRY_CL_V2.size
 INDEX_ENTRY_V2_IDX_OFFSET = 0
 INDEX_ENTRY_V2_IDX_COMPRESSED_LENGTH = 1
 INDEX_ENTRY_V2_IDX_UNCOMPRESSED_LENGTH = 2
 INDEX_ENTRY_V2_IDX_PARENT_1 = 3
 INDEX_ENTRY_V2_IDX_PARENT_2 = 4
 INDEX_ENTRY_V2_IDX_NODEID = 5
 INDEX_ENTRY_V2_IDX_SIDEDATA_OFFSET = 6
 INDEX_ENTRY_V2_IDX_SIDEDATA_COMPRESSED_LENGTH = 7
 INDEX_ENTRY_V2_IDX_COMPRESSION_MODE = 8
 
 # revlog index flags
 
 # For historical reasons, revlog's internal flags were exposed via the
 # wire protocol and are even exposed in parts of the storage APIs.
 
 # revision has censor metadata, must be verified
 REVIDX_ISCENSORED = repository.REVISION_FLAG_CENSORED
 # revision hash does not match data (narrowhg)
 REVIDX_ELLIPSIS = repository.REVISION_FLAG_ELLIPSIS
 # revision data is stored externally
 REVIDX_EXTSTORED = repository.REVISION_FLAG_EXTSTORED
 # revision changes files in a way that could affect copy tracing.
 REVIDX_HASCOPIESINFO = repository.REVISION_FLAG_HASCOPIESINFO
 REVIDX_DEFAULT_FLAGS = 0
 # stable order in which flags need to be processed and their processors applied
 REVIDX_FLAGS_ORDER = [
     REVIDX_ISCENSORED,
     REVIDX_ELLIPSIS,
     REVIDX_EXTSTORED,
     REVIDX_HASCOPIESINFO,
 ]
 
 # bitmark for flags that could cause rawdata content change
 REVIDX_RAWTEXT_CHANGING_FLAGS = REVIDX_ISCENSORED | REVIDX_EXTSTORED
 
 ## chunk compression mode constants:
 # These constants are used in revlog version >=2 to denote the compression used
 # for a chunk.
 
 # Chunk use no compression, the data stored on disk can be directly use as
 # chunk value. Without any header information prefixed.
 COMP_MODE_PLAIN = 0
 
 # Chunk use the "default compression" for the revlog (usually defined in the
 # revlog docket). A header is still used.
 #
 # XXX: keeping a header is probably not useful and we should probably drop it.
 #
 # XXX: The value of allow mixed type of compression in the revlog is unclear
 #      and we should consider making PLAIN/DEFAULT the only available mode for
 #      revlog v2, disallowing INLINE mode.
 COMP_MODE_DEFAULT = 1
 
 # Chunk use a compression mode stored "inline" at the start of the chunk
 # itself.  This is the mode always used for revlog version "0" and "1"
 COMP_MODE_INLINE = revlogutils.COMP_MODE_INLINE
 
 SUPPORTED_FLAGS = {
     REVLOGV0: REVLOGV0_FLAGS,
     REVLOGV1: REVLOGV1_FLAGS,
     REVLOGV2: REVLOGV2_FLAGS,
     CHANGELOGV2: CHANGELOGV2_FLAGS,
 }
 
 _no = lambda flags: False
 _yes = lambda flags: True
 
 
 def _from_flag(flag):
     return lambda flags: bool(flags & flag)
 
 
 FEATURES_BY_VERSION = {
     REVLOGV0: {
         b'inline': _no,
         b'generaldelta': _no,
         b'sidedata': False,
         b'docket': False,
     },
     REVLOGV1: {
         b'inline': _from_flag(FLAG_INLINE_DATA),
         b'generaldelta': _from_flag(FLAG_GENERALDELTA),
         b'sidedata': False,
         b'docket': False,
     },
     REVLOGV2: {
         # The point of inline-revlog is to reduce the number of files used in
         # the store. Using a docket defeat this purpose. So we needs other
         # means to reduce the number of files for revlogv2.
         b'inline': _no,
         b'generaldelta': _yes,
         b'sidedata': True,
         b'docket': True,
     },
     CHANGELOGV2: {
         b'inline': _no,
         # General delta is useless for changelog since we don't do any delta
         b'generaldelta': _no,
         b'sidedata': True,
         b'docket': True,
     },
 }
 
 
 SPARSE_REVLOG_MAX_CHAIN_LENGTH = 1000

mercurial/unionrepo.py

@@ -1,314 +1,316 b''
 # unionrepo.py - repository class for viewing union of repository changesets
 #
 # Derived from bundlerepo.py
 # Copyright 2006, 2007 Benoit Boissinot <[e-mail]>
 # Copyright 2013 Unity Technologies, Mads Kiilerich <[e-mail]>
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
 """Repository class for "in-memory pull" of one local repository to another,
 allowing operations like diff and log with revsets.
 """
 
 from __future__ import absolute_import
 
 from .i18n import _
 from .pycompat import getattr
 
 from . import (
     changelog,
     cmdutil,
     encoding,
     error,
     filelog,
     localrepo,
     manifest,
     mdiff,
     pathutil,
     revlog,
     util,
     vfs as vfsmod,
 )
 
 from .revlogutils import (
     constants as revlog_constants,
 )
 
 
 class unionrevlog(revlog.revlog):
     def __init__(self, opener, radix, revlog2, linkmapper):
         # How it works:
         # To retrieve a revision, we just need to know the node id so we can
         # look it up in revlog2.
         #
         # To differentiate a rev in the second revlog from a rev in the revlog,
         # we check revision against repotiprev.
         opener = vfsmod.readonlyvfs(opener)
         target = getattr(revlog2, 'target', None)
         if target is None:
             # a revlog wrapper, eg: the manifestlog that is not an actual revlog
             target = revlog2._revlog.target
         revlog.revlog.__init__(self, opener, target=target, radix=radix)
         self.revlog2 = revlog2
 
         n = len(self)
         self.repotiprev = n - 1
         self.bundlerevs = set()  # used by 'bundle()' revset expression
         for rev2 in self.revlog2:
             rev = self.revlog2.index[rev2]
             # rev numbers - in revlog2, very different from self.rev
             (
                 _start,
                 _csize,
                 rsize,
                 base,
                 linkrev,
                 p1rev,
                 p2rev,
                 node,
                 _sdo,
                 _sds,
                 _dcm,
                 _sdcm,
+                rank,
             ) = rev
             flags = _start & 0xFFFF
 
             if linkmapper is None:  # link is to same revlog
                 assert linkrev == rev2  # we never link back
                 link = n
             else:  # rev must be mapped from repo2 cl to unified cl by linkmapper
                 link = linkmapper(linkrev)
 
             if linkmapper is not None:  # link is to same revlog
                 base = linkmapper(base)
 
             this_rev = self.index.get_rev(node)
             if this_rev is not None:
                 # this happens for the common revlog revisions
                 self.bundlerevs.add(this_rev)
                 continue
 
             p1node = self.revlog2.node(p1rev)
             p2node = self.revlog2.node(p2rev)
 
             # TODO: it's probably wrong to set compressed length to -1, but
             # I have no idea if csize is valid in the base revlog context.
             e = (
                 flags,
                 -1,
                 rsize,
                 base,
                 link,
                 self.rev(p1node),
                 self.rev(p2node),
                 node,
                 0,  # sidedata offset
                 0,  # sidedata size
                 revlog_constants.COMP_MODE_INLINE,
                 revlog_constants.COMP_MODE_INLINE,
+                rank,
             )
             self.index.append(e)
             self.bundlerevs.add(n)
             n += 1
 
     def _chunk(self, rev):
         if rev <= self.repotiprev:
             return revlog.revlog._chunk(self, rev)
         return self.revlog2._chunk(self.node(rev))
 
     def revdiff(self, rev1, rev2):
         """return or calculate a delta between two revisions"""
         if rev1 > self.repotiprev and rev2 > self.repotiprev:
             return self.revlog2.revdiff(
                 self.revlog2.rev(self.node(rev1)),
                 self.revlog2.rev(self.node(rev2)),
             )
         elif rev1 <= self.repotiprev and rev2 <= self.repotiprev:
             return super(unionrevlog, self).revdiff(rev1, rev2)
 
         return mdiff.textdiff(self.rawdata(rev1), self.rawdata(rev2))
 
     def _revisiondata(self, nodeorrev, _df=None, raw=False):
         if isinstance(nodeorrev, int):
             rev = nodeorrev
             node = self.node(rev)
         else:
             node = nodeorrev
             rev = self.rev(node)
 
         if rev > self.repotiprev:
             # work around manifestrevlog NOT being a revlog
             revlog2 = getattr(self.revlog2, '_revlog', self.revlog2)
             func = revlog2._revisiondata
         else:
             func = super(unionrevlog, self)._revisiondata
         return func(node, _df=_df, raw=raw)
 
     def addrevision(self, text, transaction, link, p1=None, p2=None, d=None):
         raise NotImplementedError
 
     def addgroup(
         self,
         deltas,
         linkmapper,
         transaction,
         alwayscache=False,
         addrevisioncb=None,
         duplicaterevisioncb=None,
         maybemissingparents=False,
     ):
         raise NotImplementedError
 
     def strip(self, minlink, transaction):
         raise NotImplementedError
 
     def checksize(self):
         raise NotImplementedError
 
 
 class unionchangelog(unionrevlog, changelog.changelog):
     def __init__(self, opener, opener2):
         changelog.changelog.__init__(self, opener)
         linkmapper = None
         changelog2 = changelog.changelog(opener2)
         unionrevlog.__init__(self, opener, self.radix, changelog2, linkmapper)
 
 
 class unionmanifest(unionrevlog, manifest.manifestrevlog):
     def __init__(self, nodeconstants, opener, opener2, linkmapper):
         manifest.manifestrevlog.__init__(self, nodeconstants, opener)
         manifest2 = manifest.manifestrevlog(nodeconstants, opener2)
         unionrevlog.__init__(
             self, opener, self._revlog.radix, manifest2, linkmapper
         )
 
 
 class unionfilelog(filelog.filelog):
     def __init__(self, opener, path, opener2, linkmapper, repo):
         filelog.filelog.__init__(self, opener, path)
         filelog2 = filelog.filelog(opener2, path)
         self._revlog = unionrevlog(
             opener, self._revlog.radix, filelog2._revlog, linkmapper
         )
         self._repo = repo
         self.repotiprev = self._revlog.repotiprev
         self.revlog2 = self._revlog.revlog2
 
     def iscensored(self, rev):
         """Check if a revision is censored."""
         if rev <= self.repotiprev:
             return filelog.filelog.iscensored(self, rev)
         node = self.node(rev)
         return self.revlog2.iscensored(self.revlog2.rev(node))
 
 
 class unionpeer(localrepo.localpeer):
     def canpush(self):
         return False
 
 
 class unionrepository(object):
     """Represents the union of data in 2 repositories.
 
     Instances are not usable if constructed directly. Use ``instance()``
     or ``makeunionrepository()`` to create a usable instance.
     """
 
     def __init__(self, repo2, url):
         self.repo2 = repo2
         self._url = url
 
         self.ui.setconfig(b'phases', b'publish', False, b'unionrepo')
 
     @localrepo.unfilteredpropertycache
     def changelog(self):
         return unionchangelog(self.svfs, self.repo2.svfs)
 
     @localrepo.unfilteredpropertycache
     def manifestlog(self):
         rootstore = unionmanifest(
             self.nodeconstants,
             self.svfs,
             self.repo2.svfs,
             self.unfiltered()._clrev,
         )
         return manifest.manifestlog(
             self.svfs, self, rootstore, self.narrowmatch()
         )
 
     def _clrev(self, rev2):
         """map from repo2 changelog rev to temporary rev in self.changelog"""
         node = self.repo2.changelog.node(rev2)
         return self.changelog.rev(node)
 
     def url(self):
         return self._url
 
     def file(self, f):
         return unionfilelog(
             self.svfs, f, self.repo2.svfs, self.unfiltered()._clrev, self
         )
 
     def close(self):
         self.repo2.close()
 
     def cancopy(self):
         return False
 
     def peer(self):
         return unionpeer(self)
 
     def getcwd(self):
         return encoding.getcwd()  # always outside the repo
 
 
 def instance(ui, path, create, intents=None, createopts=None):
     if create:
         raise error.Abort(_(b'cannot create new union repository'))
     parentpath = ui.config(b"bundle", b"mainreporoot")
     if not parentpath:
         # try to find the correct path to the working directory repo
         parentpath = cmdutil.findrepo(encoding.getcwd())
         if parentpath is None:
             parentpath = b''
     if parentpath:
         # Try to make the full path relative so we get a nice, short URL.
         # In particular, we don't want temp dir names in test outputs.
         cwd = encoding.getcwd()
         if parentpath == cwd:
             parentpath = b''
         else:
             cwd = pathutil.normasprefix(cwd)
             if parentpath.startswith(cwd):
                 parentpath = parentpath[len(cwd) :]
     if path.startswith(b'union:'):
         s = path.split(b":", 1)[1].split(b"+", 1)
         if len(s) == 1:
             repopath, repopath2 = parentpath, s[0]
         else:
             repopath, repopath2 = s
     else:
         repopath, repopath2 = parentpath, path
 
     return makeunionrepository(ui, repopath, repopath2)
 
 
 def makeunionrepository(ui, repopath1, repopath2):
     """Make a union repository object from 2 local repo paths."""
     repo1 = localrepo.instance(ui, repopath1, create=False)
     repo2 = localrepo.instance(ui, repopath2, create=False)
 
     url = b'union:%s+%s' % (
         util.expandpath(repopath1),
         util.expandpath(repopath2),
     )
 
     class derivedunionrepository(unionrepository, repo1.__class__):
         pass
 
     repo = repo1
     repo.__class__ = derivedunionrepository
     unionrepository.__init__(repo1, repo2, url)
 
     return repo

tests/test-parseindex2.py

@@ -1,326 +1,330 b''
 """This unit test primarily tests parsers.parse_index2().
 
 It also checks certain aspects of the parsers module as a whole.
 """
 
 from __future__ import absolute_import, print_function
 
 import os
 import struct
 import subprocess
 import sys
 import unittest
 
 from mercurial.node import (
     bin,
     hex,
     nullrev,
     sha1nodeconstants,
 )
 from mercurial import (
     policy,
     pycompat,
 )
 from mercurial.revlogutils import (
     constants,
 )
 
 parsers = policy.importmod('parsers')
 
 # original python implementation
 def gettype(q):
     return int(q & 0xFFFF)
 
 
 def offset_type(offset, type):
     return int(int(offset) << 16 | type)
 
 
 indexformatng = ">Qiiiiii20s12x"
 
 
 def py_parseindex(data, inline):
     s = 64
     cache = None
     index = []
     nodemap = {sha1nodeconstants.nullid: nullrev}
     n = off = 0
 
     l = len(data) - s
     append = index.append
     if inline:
         cache = (0, data)
         while off <= l:
             e = struct.unpack(indexformatng, data[off : off + s])
             e = e + (
                 0,
                 0,
                 constants.COMP_MODE_INLINE,
                 constants.COMP_MODE_INLINE,
+                constants.RANK_UNKNOWN,
             )
             nodemap[e[7]] = n
             append(e)
             n += 1
             if e[1] < 0:
                 break
             off += e[1] + s
     else:
         while off <= l:
             e = struct.unpack(indexformatng, data[off : off + s])
             e = e + (
                 0,
                 0,
                 constants.COMP_MODE_INLINE,
                 constants.COMP_MODE_INLINE,
+                constants.RANK_UNKNOWN,
             )
             nodemap[e[7]] = n
             append(e)
             n += 1
             off += s
 
     e = list(index[0])
     type = gettype(e[0])
     e[0] = offset_type(0, type)
     index[0] = tuple(e)
 
     return index, cache
 
 
 data_inlined = (
     b'\x00\x01\x00\x01\x00\x00\x00\x00\x00\x00\x01\x8c'
     b'\x00\x00\x04\x07\x00\x00\x00\x00\x00\x00\x15\x15\xff\xff\xff'
     b'\xff\xff\xff\xff\xff\xebG\x97\xb7\x1fB\x04\xcf\x13V\x81\tw\x1b'
     b'w\xdduR\xda\xc6\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
     b'x\x9c\x9d\x93?O\xc30\x10\xc5\xf7|\x8a\xdb\x9a\xa8m\x06\xd8*\x95'
     b'\x81B\xa1\xa2\xa2R\xcb\x86Pd\x9a\x0b5$vd_\x04\xfd\xf6\x9c\xff@'
     b'\x11!\x0b\xd9\xec\xf7\xbbw\xe7gG6\xad6\x04\xdaN\xc0\x92\xa0$)'
     b'\xb1\x82\xa2\xd1%\x16\xa4\x8b7\xa9\xca\xd4-\xb2Y\x02\xfc\xc9'
     b'\xcaS\xf9\xaeX\xed\xb6\xd77Q\x02\x83\xd4\x19\xf5--Y\xea\xe1W'
     b'\xab\xed\x10\xceR\x0f_\xdf\xdf\r\xe1,\xf5\xf0\xcb\xf5 \xceR\x0f'
     b'_\xdc\x0e\x0e\xc3R\x0f_\xae\x96\x9b!\x9e\xa5\x1e\xbf\xdb,\x06'
     b'\xc7q\x9a/\x88\x82\xc3B\xea\xb5\xb4TJ\x93\xb6\x82\x0e\xe16\xe6'
     b'KQ\xdb\xaf\xecG\xa3\xd1 \x01\xd3\x0b_^\xe8\xaa\xa0\xae\xad\xd1'
     b'&\xbef\x1bz\x08\xb0|\xc9Xz\x06\xf6Z\x91\x90J\xaa\x17\x90\xaa'
     b'\xd2\xa6\x11$5C\xcf\xba#\xa0\x03\x02*2\x92-\xfc\xb1\x94\xdf\xe2'
     b'\xae\xb8\'m\x8ey0^\x85\xd3\x82\xb4\xf0`:\x9c\x00\x8a\xfd\x01'
     b'\xb0\xc6\x86\x8b\xdd\xae\x80\xf3\xa9\x9fd\x16\n\x00R%\x1a\x06'
     b'\xe9\xd8b\x98\x1d\xf4\xf3+\x9bf\x01\xd8p\x1b\xf3.\xed\x9f^g\xc3'
     b'^\xd9W81T\xdb\xd5\x04sx|\xf2\xeb\xd6`%?x\xed"\x831\xbf\xf3\xdc'
     b'b\xeb%gaY\xe1\xad\x9f\xb9f\'1w\xa9\xa5a\x83s\x82J\xb98\xbc4\x8b'
     b'\x83\x00\x9f$z\xb8#\xa5\xb1\xdf\x98\xd9\xec\x1b\x89O\xe3Ts\x9a4'
     b'\x17m\x8b\xfc\x8f\xa5\x95\x9a\xfc\xfa\xed,\xe5|\xa1\xfe\x15\xb9'
     b'\xbc\xb2\x93\x1f\xf2\x95\xff\xdf,\x1a\xc5\xe7\x17*\x93Oz:>\x0e'
 )
 
 data_non_inlined = (
     b'\x00\x00\x00\x01\x00\x00\x00\x00\x00\x01D\x19'
     b'\x00\x07e\x12\x00\x00\x00\x00\x00\x00\x00\x00\xff\xff\xff\xff'
     b'\xff\xff\xff\xff\xd1\xf4\xbb\xb0\xbe\xfc\x13\xbd\x8c\xd3\x9d'
     b'\x0f\xcd\xd9;\x8c\x07\x8cJ/\x00\x00\x00\x00\x00\x00\x00\x00\x00'
     b'\x00\x00\x00\x00\x00\x00\x01D\x19\x00\x00\x00\x00\x00\xdf\x00'
     b'\x00\x01q\x00\x00\x00\x01\x00\x00\x00\x01\x00\x00\x00\x00\xff'
     b'\xff\xff\xff\xc1\x12\xb9\x04\x96\xa4Z1t\x91\xdfsJ\x90\xf0\x9bh'
     b'\x07l&\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
     b'\x00\x01D\xf8\x00\x00\x00\x00\x01\x1b\x00\x00\x01\xb8\x00\x00'
     b'\x00\x01\x00\x00\x00\x02\x00\x00\x00\x01\xff\xff\xff\xff\x02\n'
     b'\x0e\xc6&\xa1\x92\xae6\x0b\x02i\xfe-\xe5\xbao\x05\xd1\xe7\x00'
     b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01F'
     b'\x13\x00\x00\x00\x00\x01\xec\x00\x00\x03\x06\x00\x00\x00\x01'
     b'\x00\x00\x00\x03\x00\x00\x00\x02\xff\xff\xff\xff\x12\xcb\xeby1'
     b'\xb6\r\x98B\xcb\x07\xbd`\x8f\x92\xd9\xc4\x84\xbdK\x00\x00\x00'
     b'\x00\x00\x00\x00\x00\x00\x00\x00\x00'
 )
 
 
 def parse_index2(data, inline, revlogv2=False):
     index, chunkcache = parsers.parse_index2(data, inline, revlogv2=revlogv2)
     return list(index), chunkcache
 
 
 def importparsers(hexversion):
     """Import mercurial.parsers with the given sys.hexversion."""
     # The file parsers.c inspects sys.hexversion to determine the version
     # of the currently-running Python interpreter, so we monkey-patch
     # sys.hexversion to simulate using different versions.
     code = (
         "import sys; sys.hexversion=%s; "
         "import mercurial.cext.parsers" % hexversion
     )
     cmd = "\"%s\" -c \"%s\"" % (os.environ['PYTHON'], code)
     # We need to do these tests inside a subprocess because parser.c's
     # version-checking code happens inside the module init function, and
     # when using reload() to reimport an extension module, "The init function
     # of extension modules is not called a second time"
     # (from http://docs.python.org/2/library/functions.html?#reload).
     p = subprocess.Popen(
         cmd, shell=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT
     )
     return p.communicate()  # returns stdout, stderr
 
 
 def hexfailmsg(testnumber, hexversion, stdout, expected):
     try:
         hexstring = hex(hexversion)
     except TypeError:
         hexstring = None
     return (
         "FAILED: version test #%s with Python %s and patched "
         "sys.hexversion %r (%r):\n Expected %s but got:\n-->'%s'\n"
         % (
             testnumber,
             sys.version_info,
             hexversion,
             hexstring,
             expected,
             stdout,
         )
     )
 
 
 def makehex(major, minor, micro):
     return int("%x%02x%02x00" % (major, minor, micro), 16)
 
 
 class parseindex2tests(unittest.TestCase):
     def assertversionokay(self, testnumber, hexversion):
         stdout, stderr = importparsers(hexversion)
         self.assertFalse(
             stdout, hexfailmsg(testnumber, hexversion, stdout, 'no stdout')
         )
 
     def assertversionfail(self, testnumber, hexversion):
         stdout, stderr = importparsers(hexversion)
         # We include versionerrortext to distinguish from other ImportErrors.
         errtext = b"ImportError: %s" % pycompat.sysbytes(
             parsers.versionerrortext
         )
         self.assertIn(
             errtext,
             stdout,
             hexfailmsg(
                 testnumber,
                 hexversion,
                 stdout,
                 expected="stdout to contain %r" % errtext,
             ),
         )
 
     def testversiondetection(self):
         """Check the version-detection logic when importing parsers."""
         # Only test the version-detection logic if it is present.
         try:
             parsers.versionerrortext
         except AttributeError:
             return
         info = sys.version_info
         major, minor, micro = info[0], info[1], info[2]
         # Test same major-minor versions.
         self.assertversionokay(1, makehex(major, minor, micro))
         self.assertversionokay(2, makehex(major, minor, micro + 1))
         # Test different major-minor versions.
         self.assertversionfail(3, makehex(major + 1, minor, micro))
         self.assertversionfail(4, makehex(major, minor + 1, micro))
         self.assertversionfail(5, "'foo'")
 
     def testbadargs(self):
         # Check that parse_index2() raises TypeError on bad arguments.
         with self.assertRaises(TypeError):
             parse_index2(0, True)
 
     def testparseindexfile(self):
         # Check parsers.parse_index2() on an index file against the
         # original Python implementation of parseindex, both with and
         # without inlined data.
 
         want = py_parseindex(data_inlined, True)
         got = parse_index2(data_inlined, True)
         self.assertEqual(want, got)  # inline data
 
         want = py_parseindex(data_non_inlined, False)
         got = parse_index2(data_non_inlined, False)
         self.assertEqual(want, got)  # no inline data
 
         ix = parsers.parse_index2(data_inlined, True)[0]
         for i, r in enumerate(ix):
             if r[7] == sha1nodeconstants.nullid:
                 i = -1
             try:
                 self.assertEqual(
                     ix[r[7]],
                     i,
                     'Reverse lookup inconsistent for %r' % hex(r[7]),
                 )
             except TypeError:
                 # pure version doesn't support this
                 break
 
     def testminusone(self):
         want = (
             0,
             0,
             0,
             -1,
             -1,
             -1,
             -1,
             sha1nodeconstants.nullid,
             0,
             0,
             constants.COMP_MODE_INLINE,
             constants.COMP_MODE_INLINE,
+            constants.RANK_UNKNOWN,
         )
         index, junk = parsers.parse_index2(data_inlined, True)
         got = index[-1]
         self.assertEqual(want, got)  # inline data
 
         index, junk = parsers.parse_index2(data_non_inlined, False)
         got = index[-1]
         self.assertEqual(want, got)  # no inline data
 
     def testdelitemwithoutnodetree(self):
         index, _junk = parsers.parse_index2(data_non_inlined, False)
 
         def hexrev(rev):
             if rev == nullrev:
                 return b'\xff\xff\xff\xff'
             else:
                 return bin('%08x' % rev)
 
         def appendrev(p1, p2=nullrev):
             # node won't matter for this test, let's just make sure
             # they don't collide. Other data don't matter either.
             node = hexrev(p1) + hexrev(p2) + b'.' * 12
             e = (
                 0,
                 0,
                 12,
                 1,
                 34,
                 p1,
                 p2,
                 node,
                 0,
                 0,
                 constants.COMP_MODE_INLINE,
                 constants.COMP_MODE_INLINE,
+                constants.RANK_UNKNOWN,
             )
             index.append(e)
 
         appendrev(4)
         appendrev(5)
         appendrev(6)
         self.assertEqual(len(index), 7)
 
         del index[1:-1]
 
         # assertions that failed before correction
         self.assertEqual(len(index), 1)  # was 4
         headrevs = getattr(index, 'headrevs', None)
         if headrevs is not None:  # not implemented in pure
             self.assertEqual(index.headrevs(), [0])  # gave ValueError
 
 
 if __name__ == '__main__':
     import silenttestrunner
 
     silenttestrunner.main(__name__)