delta-find: use a smarter object for snapshot caching

This open the way for a longer lived cache.

contrib/fuzz/revlog.cc

@@ -1,61 +1,61 b''
 #include <Python.h>
 #include <assert.h>
 #include <stdlib.h>
 #include <unistd.h>
 
 #include <string>
 
 #include "pyutil.h"
 
 extern "C" {
 
 static PYCODETYPE *code;
 
 extern "C" int LLVMFuzzerInitialize(int *argc, char ***argv)
 {
 	contrib::initpy(*argv[0]);
 	code = (PYCODETYPE *)Py_CompileString(R"py(
 for inline in (True, False):
     try:
         index, cache = parsers.parse_index2(data, inline)
         index.slicechunktodensity(list(range(len(index))), 0.5, 262144)
         index.stats()
-        index.findsnapshots({}, 0)
+        index.findsnapshots({}, 0, len(index) - 1)
         10 in index
         for rev in range(len(index)):
             index.reachableroots(0, [len(index)-1], [rev])
             node = index[rev][7]
             partial = index.shortest(node)
             index.partialmatch(node[:partial])
             index.deltachain(rev, None, True)
     except Exception as e:
         pass
         # uncomment this print if you're editing this Python code
         # to debug failures.
         # print e
 )py",
 	                                      "fuzzer", Py_file_input);
 	return 0;
 }
 
 int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size)
 {
 	// Don't allow fuzzer inputs larger than 60k, since we'll just bog
 	// down and not accomplish much.
 	if (Size > 60000) {
 		return 0;
 	}
 	PyObject *text =
 	    PyBytes_FromStringAndSize((const char *)Data, (Py_ssize_t)Size);
 	PyObject *locals = PyDict_New();
 	PyDict_SetItemString(locals, "data", text);
 	PyObject *res = PyEval_EvalCode(code, contrib::pyglobals(), locals);
 	if (!res) {
 		PyErr_Print();
 	}
 	Py_XDECREF(res);
 	Py_DECREF(locals);
 	Py_DECREF(text);
 	return 0; // Non-zero return values are reserved for future use.
 }
 }

mercurial/cext/revlog.c

@@ -1,3315 +1,3324 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"
 
 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 (*fast_rank)(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 */
 	long format_version;  /* format version selector (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 = "Kiiiiiiy#KiBBi";
 #else
 static const char *const tuple_format = "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;
 
 /* A Changelogv2 index entry is 96 bytes long. */
 static const long cl2_entry_size = 96;
 
 /* Internal format version.
  * Must match their counterparts in revlogutils/constants.py */
 static const long format_v1 = 1;       /* constants.py: REVLOGV1 */
 static const long format_v2 = 0xDEAD;  /* constants.py: REVLOGV2 */
 static const long format_cl2 = 0xD34D; /* constants.py: CHANGELOGV2 */
 
 static const long entry_v1_offset_high = 0;
 static const long entry_v1_offset_offset_flags = 4;
 static const long entry_v1_offset_comp_len = 8;
 static const long entry_v1_offset_uncomp_len = 12;
 static const long entry_v1_offset_base_rev = 16;
 static const long entry_v1_offset_link_rev = 20;
 static const long entry_v1_offset_parent_1 = 24;
 static const long entry_v1_offset_parent_2 = 28;
 static const long entry_v1_offset_node_id = 32;
 
 static const long entry_v2_offset_high = 0;
 static const long entry_v2_offset_offset_flags = 4;
 static const long entry_v2_offset_comp_len = 8;
 static const long entry_v2_offset_uncomp_len = 12;
 static const long entry_v2_offset_base_rev = 16;
 static const long entry_v2_offset_link_rev = 20;
 static const long entry_v2_offset_parent_1 = 24;
 static const long entry_v2_offset_parent_2 = 28;
 static const long entry_v2_offset_node_id = 32;
 static const long entry_v2_offset_sidedata_offset = 64;
 static const long entry_v2_offset_sidedata_comp_len = 72;
 static const long entry_v2_offset_all_comp_mode = 76;
 /* next free offset: 77 */
 
 static const long entry_cl2_offset_high = 0;
 static const long entry_cl2_offset_offset_flags = 4;
 static const long entry_cl2_offset_comp_len = 8;
 static const long entry_cl2_offset_uncomp_len = 12;
 static const long entry_cl2_offset_parent_1 = 16;
 static const long entry_cl2_offset_parent_2 = 20;
 static const long entry_cl2_offset_node_id = 24;
 static const long entry_cl2_offset_sidedata_offset = 56;
 static const long entry_cl2_offset_sidedata_comp_len = 64;
 static const long entry_cl2_offset_all_comp_mode = 68;
 static const long entry_cl2_offset_rank = 69;
 /* next free offset: 73 */
 
 static const char comp_mode_inline = 2;
 static const int 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);
 
 	if (self->format_version == format_v1) {
 		ps[0] = getbe32(data + entry_v1_offset_parent_1);
 		ps[1] = getbe32(data + entry_v1_offset_parent_2);
 	} else if (self->format_version == format_v2) {
 		ps[0] = getbe32(data + entry_v2_offset_parent_1);
 		ps[1] = getbe32(data + entry_v2_offset_parent_2);
 	} else if (self->format_version == format_cl2) {
 		ps[0] = getbe32(data + entry_cl2_offset_parent_1);
 		ps[1] = getbe32(data + entry_cl2_offset_parent_2);
 	} else {
 		raise_revlog_error();
 		return -1;
 	}
 
 	/* 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);
 
 	if (self->format_version == format_v1) {
 		offset = getbe32(data + entry_v1_offset_offset_flags);
 		if (rev == 0) {
 			/* mask out version number for the first entry */
 			offset &= 0xFFFF;
 		} else {
 			uint32_t offset_high =
 			    getbe32(data + entry_v1_offset_high);
 			offset |= ((uint64_t)offset_high) << 32;
 		}
 	} else if (self->format_version == format_v2) {
 		offset = getbe32(data + entry_v2_offset_offset_flags);
 		if (rev == 0) {
 			/* mask out version number for the first entry */
 			offset &= 0xFFFF;
 		} else {
 			uint32_t offset_high =
 			    getbe32(data + entry_v2_offset_high);
 			offset |= ((uint64_t)offset_high) << 32;
 		}
 	} else if (self->format_version == format_cl2) {
 		uint32_t offset_high = getbe32(data + entry_cl2_offset_high);
 		offset = getbe32(data + entry_cl2_offset_offset_flags);
 		offset |= ((uint64_t)offset_high) << 32;
 	} else {
 		raise_revlog_error();
 		return -1;
 	}
 
 	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);
 
 	if (self->format_version == format_v1) {
 		tmp = (int)getbe32(data + entry_v1_offset_comp_len);
 	} else if (self->format_version == format_v2) {
 		tmp = (int)getbe32(data + entry_v2_offset_comp_len);
 	} else if (self->format_version == format_cl2) {
 		tmp = (int)getbe32(data + entry_cl2_offset_comp_len);
 	} else {
 		raise_revlog_error();
 		return -1;
 	}
 	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, rank = rank_unknown;
 	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;
 
 	if (self->format_version == format_v1) {
 		offset_flags = getbe32(data + entry_v1_offset_offset_flags);
 		/*
 		 * 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 + entry_v1_offset_high);
 			offset_flags |= ((uint64_t)offset_high) << 32;
 		}
 
 		comp_len = getbe32(data + entry_v1_offset_comp_len);
 		uncomp_len = getbe32(data + entry_v1_offset_uncomp_len);
 		base_rev = getbe32(data + entry_v1_offset_base_rev);
 		link_rev = getbe32(data + entry_v1_offset_link_rev);
 		parent_1 = getbe32(data + entry_v1_offset_parent_1);
 		parent_2 = getbe32(data + entry_v1_offset_parent_2);
 		c_node_id = data + entry_v1_offset_node_id;
 
 		sidedata_offset = 0;
 		sidedata_comp_len = 0;
 		data_comp_mode = comp_mode_inline;
 		sidedata_comp_mode = comp_mode_inline;
 	} else if (self->format_version == format_v2) {
 		offset_flags = getbe32(data + entry_v2_offset_offset_flags);
 		/*
 		 * 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 + entry_v2_offset_high);
 			offset_flags |= ((uint64_t)offset_high) << 32;
 		}
 
 		comp_len = getbe32(data + entry_v2_offset_comp_len);
 		uncomp_len = getbe32(data + entry_v2_offset_uncomp_len);
 		base_rev = getbe32(data + entry_v2_offset_base_rev);
 		link_rev = getbe32(data + entry_v2_offset_link_rev);
 		parent_1 = getbe32(data + entry_v2_offset_parent_1);
 		parent_2 = getbe32(data + entry_v2_offset_parent_2);
 		c_node_id = data + entry_v2_offset_node_id;
 
 		sidedata_offset =
 		    getbe64(data + entry_v2_offset_sidedata_offset);
 		sidedata_comp_len =
 		    getbe32(data + entry_v2_offset_sidedata_comp_len);
 		data_comp_mode = data[entry_v2_offset_all_comp_mode] & 3;
 		sidedata_comp_mode =
 		    ((data[entry_v2_offset_all_comp_mode] >> 2) & 3);
 	} else if (self->format_version == format_cl2) {
 		uint32_t offset_high = getbe32(data + entry_cl2_offset_high);
 		offset_flags = getbe32(data + entry_cl2_offset_offset_flags);
 		offset_flags |= ((uint64_t)offset_high) << 32;
 		comp_len = getbe32(data + entry_cl2_offset_comp_len);
 		uncomp_len = getbe32(data + entry_cl2_offset_uncomp_len);
 		/* base_rev and link_rev are not stored in changelogv2, but are
 		 still used by some functions shared with the other revlogs.
 		 They are supposed to contain links to other revisions,
 		 but they always point to themselves in the case of a changelog.
 		*/
 		base_rev = pos;
 		link_rev = pos;
 		parent_1 = getbe32(data + entry_cl2_offset_parent_1);
 		parent_2 = getbe32(data + entry_cl2_offset_parent_2);
 		c_node_id = data + entry_cl2_offset_node_id;
 		sidedata_offset =
 		    getbe64(data + entry_cl2_offset_sidedata_offset);
 		sidedata_comp_len =
 		    getbe32(data + entry_cl2_offset_sidedata_comp_len);
 		data_comp_mode = data[entry_cl2_offset_all_comp_mode] & 3;
 		sidedata_comp_mode =
 		    ((data[entry_cl2_offset_all_comp_mode] >> 2) & 3);
 		rank = getbe32(data + entry_cl2_offset_rank);
 	} else {
 		raise_revlog_error();
 		return NULL;
 	}
 
 	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, rank);
 }
 /*
  * 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: %d",
 		             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;
 	const char *node_id;
 
 	if (pos == nullrev)
 		return nullid;
 
 	if (pos >= length)
 		return NULL;
 
 	data = index_deref(self, pos);
 
 	if (self->format_version == format_v1) {
 		node_id = data + entry_v1_offset_node_id;
 	} else if (self->format_version == format_v2) {
 		node_id = data + entry_v2_offset_node_id;
 	} else if (self->format_version == format_cl2) {
 		node_id = data + entry_cl2_offset_node_id;
 	} else {
 		raise_revlog_error();
 		return NULL;
 	}
 
 	return data ? node_id : NULL;
 }
 
 /*
  * Return the stored rank of a given revision if known, or rank_unknown
  * otherwise.
  *
  * The rank of a revision is the size of the sub-graph it defines as a head.
  * Equivalently, the rank of a revision `r` is the size of the set
  * `ancestors(r)`, `r` included.
  *
  * This method returns the rank retrieved from the revlog in constant time. It
  * makes no attempt at computing unknown values for versions of the revlog
  * which do not persist the rank.
  */
 static int index_fast_rank(indexObject *self, Py_ssize_t pos)
 {
 	Py_ssize_t length = index_length(self);
 
 	if (self->format_version != format_cl2 || pos >= length) {
 		return rank_unknown;
 	}
 
 	if (pos == nullrev) {
 		return 0; /* convention */
 	}
 
 	return getbe32(index_deref(self, pos) + entry_cl2_offset_rank);
 }
 
 /*
  * 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, 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, &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++;
 
 	memset(data, 0, self->entry_size);
 
 	if (self->format_version == format_v1) {
 		putbe32(offset_flags >> 32, data + entry_v1_offset_high);
 		putbe32(offset_flags & 0xffffffffU,
 		        data + entry_v1_offset_offset_flags);
 		putbe32(comp_len, data + entry_v1_offset_comp_len);
 		putbe32(uncomp_len, data + entry_v1_offset_uncomp_len);
 		putbe32(base_rev, data + entry_v1_offset_base_rev);
 		putbe32(link_rev, data + entry_v1_offset_link_rev);
 		putbe32(parent_1, data + entry_v1_offset_parent_1);
 		putbe32(parent_2, data + entry_v1_offset_parent_2);
 		memcpy(data + entry_v1_offset_node_id, c_node_id,
 		       c_node_id_len);
 	} else if (self->format_version == format_v2) {
 		putbe32(offset_flags >> 32, data + entry_v2_offset_high);
 		putbe32(offset_flags & 0xffffffffU,
 		        data + entry_v2_offset_offset_flags);
 		putbe32(comp_len, data + entry_v2_offset_comp_len);
 		putbe32(uncomp_len, data + entry_v2_offset_uncomp_len);
 		putbe32(base_rev, data + entry_v2_offset_base_rev);
 		putbe32(link_rev, data + entry_v2_offset_link_rev);
 		putbe32(parent_1, data + entry_v2_offset_parent_1);
 		putbe32(parent_2, data + entry_v2_offset_parent_2);
 		memcpy(data + entry_v2_offset_node_id, c_node_id,
 		       c_node_id_len);
 		putbe64(sidedata_offset,
 		        data + entry_v2_offset_sidedata_offset);
 		putbe32(sidedata_comp_len,
 		        data + entry_v2_offset_sidedata_comp_len);
 		comp_field = data_comp_mode & 3;
 		comp_field = comp_field | (sidedata_comp_mode & 3) << 2;
 		data[entry_v2_offset_all_comp_mode] = comp_field;
 	} else if (self->format_version == format_cl2) {
 		putbe32(offset_flags >> 32, data + entry_cl2_offset_high);
 		putbe32(offset_flags & 0xffffffffU,
 		        data + entry_cl2_offset_offset_flags);
 		putbe32(comp_len, data + entry_cl2_offset_comp_len);
 		putbe32(uncomp_len, data + entry_cl2_offset_uncomp_len);
 		putbe32(parent_1, data + entry_cl2_offset_parent_1);
 		putbe32(parent_2, data + entry_cl2_offset_parent_2);
 		memcpy(data + entry_cl2_offset_node_id, c_node_id,
 		       c_node_id_len);
 		putbe64(sidedata_offset,
 		        data + entry_cl2_offset_sidedata_offset);
 		putbe32(sidedata_comp_len,
 		        data + entry_cl2_offset_sidedata_comp_len);
 		comp_field = data_comp_mode & 3;
 		comp_field = comp_field | (sidedata_comp_mode & 3) << 2;
 		data[entry_cl2_offset_all_comp_mode] = comp_field;
 		putbe32(rank, data + entry_cl2_offset_rank);
 	} else {
 		raise_revlog_error();
 		return NULL;
 	}
 
 	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 = "nKiKB";
 #else
 	const char *const sidedata_format = "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);
 	if (self->format_version == format_v2) {
 		putbe64(offset_flags, data + entry_v2_offset_high);
 		putbe64(sidedata_offset,
 		        data + entry_v2_offset_sidedata_offset);
 		putbe32(sidedata_comp_len,
 		        data + entry_v2_offset_sidedata_comp_len);
 		data[entry_v2_offset_all_comp_mode] =
 		    (data[entry_v2_offset_all_comp_mode] & ~(3 << 2)) |
 		    ((comp_mode & 3) << 2);
 	} else if (self->format_version == format_cl2) {
 		putbe64(offset_flags, data + entry_cl2_offset_high);
 		putbe64(sidedata_offset,
 		        data + entry_cl2_offset_sidedata_offset);
 		putbe32(sidedata_comp_len,
 		        data + entry_cl2_offset_sidedata_comp_len);
 		data[entry_cl2_offset_all_comp_mode] =
 		    (data[entry_cl2_offset_all_comp_mode] & ~(3 << 2)) |
 		    ((comp_mode & 3) << 2);
 	} else {
 		raise_revlog_error();
 		return NULL;
 	}
 
 	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 = PyLong_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 = PyLong_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 = PyLong_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 = PyLong_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 = PyLong_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 = PyLong_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 = PyLong_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 = PyLong_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 = PyLong_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 = PyLong_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;
 
 	if (self->format_version == format_v1) {
 		result = getbe32(data + entry_v1_offset_base_rev);
 	} else if (self->format_version == format_v2) {
 		result = getbe32(data + entry_v2_offset_base_rev);
 	} else if (self->format_version == format_cl2) {
 		return rev;
 	} else {
 		raise_revlog_error();
 		return -1;
 	}
 
 	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];
 	int b;
 	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;
 		};
 		while ((index_get_length(self, ps[0]) == 0) && ps[0] >= 0) {
 			b = index_baserev(self, ps[0]);
 			if (b == ps[0]) {
 				break;
 			}
 			ps[0] = b;
 		}
 		while ((index_get_length(self, ps[1]) == 0) && ps[1] >= 0) {
 			b = index_baserev(self, ps[1]);
 			if (b == ps[1]) {
 				break;
 			}
 			ps[1] = b;
 		}
 		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;
+	Py_ssize_t end_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)) {
+	if (!PyArg_ParseTuple(args, "O!nn", &PyDict_Type, &cache, &start_rev,
+	                      &end_rev)) {
 		return NULL;
 	}
-	for (rev = start_rev; rev < length; rev++) {
+	end_rev += 1;
+	if (end_rev > length) {
+		end_rev = length;
+	}
+	if (start_rev < 0) {
+		start_rev = 0;
+	}
+	for (rev = start_rev; rev < end_rev; 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 = PyLong_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 = PyLong_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 (PyLong_Check(stoparg)) {
 		stoprev = (int)PyLong_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 = PyLong_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 = PyLong_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 =
 		    PyLong_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 PyLong_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 (PyLong_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 PyLong_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, "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 PyLong_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 PyLong_FromLong(rev);
 }
 
 static int index_contains(indexObject *self, PyObject *value)
 {
 	char *node;
 
 	if (PyLong_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 PyLong_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 = PyLong_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)PyLong_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)PyLong_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 (!PyLong_Check(obj)) {
 			PyErr_SetString(PyExc_TypeError,
 			                "arguments must all be ints");
 			Py_DECREF(obj);
 			goto bail;
 		}
 		val = PyLong_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 = PyLong_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++) {
 		const char *node = index_node(self, i);
 		nt_delete_node(&self->nt, node);
 	}
 
 	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;
 
 	if (PySlice_GetIndicesEx(item, length, &start, &stop, &step,
 	                         &slicelength) < 0)
 		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 = PyLong_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 */
 		if (self->format_version == format_v1) {
 			comp_len =
 			    getbe32(data + pos + entry_v1_offset_comp_len);
 			sidedata_comp_len = 0;
 		} else if (self->format_version == format_v2) {
 			comp_len =
 			    getbe32(data + pos + entry_v2_offset_comp_len);
 			sidedata_comp_len = getbe32(
 			    data + pos + entry_v2_offset_sidedata_comp_len);
 		} else {
 			raise_revlog_error();
 			return -1;
 		}
 		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;
 	Py_ssize_t size;
 
 	static char *kwlist[] = {"data", "inlined", "format", 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;
 	self->format_version = format_v1;
 
 	if (!PyArg_ParseTupleAndKeywords(args, kwargs, "OO|l", kwlist,
 	                                 &data_obj, &inlined_obj,
 	                                 &(self->format_version)))
 		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 (self->format_version == format_v1) {
 		self->entry_size = v1_entry_size;
 	} else if (self->format_version == format_v2) {
 		self->entry_size = v2_entry_size;
 	} else if (self->format_version == format_cl2) {
 		self->entry_size = cl2_entry_size;
 	}
 
 	self->nullentry = Py_BuildValue(
 	    "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 */
     3, index_length, index_node, index_fast_rank, 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/revlogutils/deltas.py

@@ -1,1428 +1,1472 b''
 # revlogdeltas.py - Logic around delta computation for revlog
 #
 # 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"""
 
 
 import collections
 import struct
 
 # import stuff from node for others to import from revlog
 from ..node import nullrev
 from ..i18n import _
 from ..pycompat import getattr
 
 from .constants import (
     COMP_MODE_DEFAULT,
     COMP_MODE_INLINE,
     COMP_MODE_PLAIN,
     DELTA_BASE_REUSE_NO,
     KIND_CHANGELOG,
     KIND_FILELOG,
     KIND_MANIFESTLOG,
     REVIDX_ISCENSORED,
     REVIDX_RAWTEXT_CHANGING_FLAGS,
 )
 
 from ..thirdparty import attr
 
 from .. import (
     error,
     mdiff,
     util,
 )
 
 from . import flagutil
 
 # maximum <delta-chain-data>/<revision-text-length> ratio
 LIMIT_DELTA2TEXT = 2
 
 
 class _testrevlog:
     """minimalist fake revlog to use in doctests"""
 
     def __init__(self, data, density=0.5, mingap=0, snapshot=()):
         """data is an list of revision payload boundaries"""
         self._data = data
         self._srdensitythreshold = density
         self._srmingapsize = mingap
         self._snapshot = set(snapshot)
         self.index = None
 
     def start(self, rev):
         if rev == nullrev:
             return 0
         if rev == 0:
             return 0
         return self._data[rev - 1]
 
     def end(self, rev):
         if rev == nullrev:
             return 0
         return self._data[rev]
 
     def length(self, rev):
         return self.end(rev) - self.start(rev)
 
     def __len__(self):
         return len(self._data)
 
     def issnapshot(self, rev):
         if rev == nullrev:
             return True
         return rev in self._snapshot
 
 
 def slicechunk(revlog, revs, targetsize=None):
     """slice revs to reduce the amount of unrelated data to be read from disk.
 
     ``revs`` is sliced into groups that should be read in one time.
     Assume that revs are sorted.
 
     The initial chunk is sliced until the overall density (payload/chunks-span
     ratio) is above `revlog._srdensitythreshold`. No gap smaller than
     `revlog._srmingapsize` is skipped.
 
     If `targetsize` is set, no chunk larger than `targetsize` will be yield.
     For consistency with other slicing choice, this limit won't go lower than
     `revlog._srmingapsize`.
 
     If individual revisions chunk are larger than this limit, they will still
     be raised individually.
 
     >>> data = [
     ...  5,  #00 (5)
     ...  10, #01 (5)
     ...  12, #02 (2)
     ...  12, #03 (empty)
     ...  27, #04 (15)
     ...  31, #05 (4)
     ...  31, #06 (empty)
     ...  42, #07 (11)
     ...  47, #08 (5)
     ...  47, #09 (empty)
     ...  48, #10 (1)
     ...  51, #11 (3)
     ...  74, #12 (23)
     ...  85, #13 (11)
     ...  86, #14 (1)
     ...  91, #15 (5)
     ... ]
     >>> revlog = _testrevlog(data, snapshot=range(16))
 
     >>> list(slicechunk(revlog, list(range(16))))
     [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]]
     >>> list(slicechunk(revlog, [0, 15]))
     [[0], [15]]
     >>> list(slicechunk(revlog, [0, 11, 15]))
     [[0], [11], [15]]
     >>> list(slicechunk(revlog, [0, 11, 13, 15]))
     [[0], [11, 13, 15]]
     >>> list(slicechunk(revlog, [1, 2, 3, 5, 8, 10, 11, 14]))
     [[1, 2], [5, 8, 10, 11], [14]]
 
     Slicing with a maximum chunk size
     >>> list(slicechunk(revlog, [0, 11, 13, 15], targetsize=15))
     [[0], [11], [13], [15]]
     >>> list(slicechunk(revlog, [0, 11, 13, 15], targetsize=20))
     [[0], [11], [13, 15]]
 
     Slicing involving nullrev
     >>> list(slicechunk(revlog, [-1, 0, 11, 13, 15], targetsize=20))
     [[-1, 0], [11], [13, 15]]
     >>> list(slicechunk(revlog, [-1, 13, 15], targetsize=5))
     [[-1], [13], [15]]
     """
     if targetsize is not None:
         targetsize = max(targetsize, revlog._srmingapsize)
     # targetsize should not be specified when evaluating delta candidates:
     # * targetsize is used to ensure we stay within specification when reading,
     densityslicing = getattr(revlog.index, 'slicechunktodensity', None)
     if densityslicing is None:
         densityslicing = lambda x, y, z: _slicechunktodensity(revlog, x, y, z)
     for chunk in densityslicing(
         revs, revlog._srdensitythreshold, revlog._srmingapsize
     ):
         for subchunk in _slicechunktosize(revlog, chunk, targetsize):
             yield subchunk
 
 
 def _slicechunktosize(revlog, revs, targetsize=None):
     """slice revs to match the target size
 
     This is intended to be used on chunk that density slicing selected by that
     are still too large compared to the read garantee of revlog. This might
     happens when "minimal gap size" interrupted the slicing or when chain are
     built in a way that create large blocks next to each other.
 
     >>> data = [
     ...  3,  #0 (3)
     ...  5,  #1 (2)
     ...  6,  #2 (1)
     ...  8,  #3 (2)
     ...  8,  #4 (empty)
     ...  11, #5 (3)
     ...  12, #6 (1)
     ...  13, #7 (1)
     ...  14, #8 (1)
     ... ]
 
     == All snapshots cases ==
     >>> revlog = _testrevlog(data, snapshot=range(9))
 
     Cases where chunk is already small enough
     >>> list(_slicechunktosize(revlog, [0], 3))
     [[0]]
     >>> list(_slicechunktosize(revlog, [6, 7], 3))
     [[6, 7]]
     >>> list(_slicechunktosize(revlog, [0], None))
     [[0]]
     >>> list(_slicechunktosize(revlog, [6, 7], None))
     [[6, 7]]
 
     cases where we need actual slicing
     >>> list(_slicechunktosize(revlog, [0, 1], 3))
     [[0], [1]]
     >>> list(_slicechunktosize(revlog, [1, 3], 3))
     [[1], [3]]
     >>> list(_slicechunktosize(revlog, [1, 2, 3], 3))
     [[1, 2], [3]]
     >>> list(_slicechunktosize(revlog, [3, 5], 3))
     [[3], [5]]
     >>> list(_slicechunktosize(revlog, [3, 4, 5], 3))
     [[3], [5]]
     >>> list(_slicechunktosize(revlog, [5, 6, 7, 8], 3))
     [[5], [6, 7, 8]]
     >>> list(_slicechunktosize(revlog, [0, 1, 2, 3, 4, 5, 6, 7, 8], 3))
     [[0], [1, 2], [3], [5], [6, 7, 8]]
 
     Case with too large individual chunk (must return valid chunk)
     >>> list(_slicechunktosize(revlog, [0, 1], 2))
     [[0], [1]]
     >>> list(_slicechunktosize(revlog, [1, 3], 1))
     [[1], [3]]
     >>> list(_slicechunktosize(revlog, [3, 4, 5], 2))
     [[3], [5]]
 
     == No Snapshot cases ==
     >>> revlog = _testrevlog(data)
 
     Cases where chunk is already small enough
     >>> list(_slicechunktosize(revlog, [0], 3))
     [[0]]
     >>> list(_slicechunktosize(revlog, [6, 7], 3))
     [[6, 7]]
     >>> list(_slicechunktosize(revlog, [0], None))
     [[0]]
     >>> list(_slicechunktosize(revlog, [6, 7], None))
     [[6, 7]]
 
     cases where we need actual slicing
     >>> list(_slicechunktosize(revlog, [0, 1], 3))
     [[0], [1]]
     >>> list(_slicechunktosize(revlog, [1, 3], 3))
     [[1], [3]]
     >>> list(_slicechunktosize(revlog, [1, 2, 3], 3))
     [[1], [2, 3]]
     >>> list(_slicechunktosize(revlog, [3, 5], 3))
     [[3], [5]]
     >>> list(_slicechunktosize(revlog, [3, 4, 5], 3))
     [[3], [4, 5]]
     >>> list(_slicechunktosize(revlog, [5, 6, 7, 8], 3))
     [[5], [6, 7, 8]]
     >>> list(_slicechunktosize(revlog, [0, 1, 2, 3, 4, 5, 6, 7, 8], 3))
     [[0], [1, 2], [3], [5], [6, 7, 8]]
 
     Case with too large individual chunk (must return valid chunk)
     >>> list(_slicechunktosize(revlog, [0, 1], 2))
     [[0], [1]]
     >>> list(_slicechunktosize(revlog, [1, 3], 1))
     [[1], [3]]
     >>> list(_slicechunktosize(revlog, [3, 4, 5], 2))
     [[3], [5]]
 
     == mixed case ==
     >>> revlog = _testrevlog(data, snapshot=[0, 1, 2])
     >>> list(_slicechunktosize(revlog, list(range(9)), 5))
     [[0, 1], [2], [3, 4, 5], [6, 7, 8]]
     """
     assert targetsize is None or 0 <= targetsize
     startdata = revlog.start(revs[0])
     enddata = revlog.end(revs[-1])
     fullspan = enddata - startdata
     if targetsize is None or fullspan <= targetsize:
         yield revs
         return
 
     startrevidx = 0
     endrevidx = 1
     iterrevs = enumerate(revs)
     next(iterrevs)  # skip first rev.
     # first step: get snapshots out of the way
     for idx, r in iterrevs:
         span = revlog.end(r) - startdata
         snapshot = revlog.issnapshot(r)
         if span <= targetsize and snapshot:
             endrevidx = idx + 1
         else:
             chunk = _trimchunk(revlog, revs, startrevidx, endrevidx)
             if chunk:
                 yield chunk
             startrevidx = idx
             startdata = revlog.start(r)
             endrevidx = idx + 1
         if not snapshot:
             break
 
     # for the others, we use binary slicing to quickly converge toward valid
     # chunks (otherwise, we might end up looking for start/end of many
     # revisions). This logic is not looking for the perfect slicing point, it
     # focuses on quickly converging toward valid chunks.
     nbitem = len(revs)
     while (enddata - startdata) > targetsize:
         endrevidx = nbitem
         if nbitem - startrevidx <= 1:
             break  # protect against individual chunk larger than limit
         localenddata = revlog.end(revs[endrevidx - 1])
         span = localenddata - startdata
         while span > targetsize:
             if endrevidx - startrevidx <= 1:
                 break  # protect against individual chunk larger than limit
             endrevidx -= (endrevidx - startrevidx) // 2
             localenddata = revlog.end(revs[endrevidx - 1])
             span = localenddata - startdata
         chunk = _trimchunk(revlog, revs, startrevidx, endrevidx)
         if chunk:
             yield chunk
         startrevidx = endrevidx
         startdata = revlog.start(revs[startrevidx])
 
     chunk = _trimchunk(revlog, revs, startrevidx)
     if chunk:
         yield chunk
 
 
 def _slicechunktodensity(revlog, revs, targetdensity=0.5, mingapsize=0):
     """slice revs to reduce the amount of unrelated data to be read from disk.
 
     ``revs`` is sliced into groups that should be read in one time.
     Assume that revs are sorted.
 
     The initial chunk is sliced until the overall density (payload/chunks-span
     ratio) is above `targetdensity`. No gap smaller than `mingapsize` is
     skipped.
 
     >>> revlog = _testrevlog([
     ...  5,  #00 (5)
     ...  10, #01 (5)
     ...  12, #02 (2)
     ...  12, #03 (empty)
     ...  27, #04 (15)
     ...  31, #05 (4)
     ...  31, #06 (empty)
     ...  42, #07 (11)
     ...  47, #08 (5)
     ...  47, #09 (empty)
     ...  48, #10 (1)
     ...  51, #11 (3)
     ...  74, #12 (23)
     ...  85, #13 (11)
     ...  86, #14 (1)
     ...  91, #15 (5)
     ... ])
 
     >>> list(_slicechunktodensity(revlog, list(range(16))))
     [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]]
     >>> list(_slicechunktodensity(revlog, [0, 15]))
     [[0], [15]]
     >>> list(_slicechunktodensity(revlog, [0, 11, 15]))
     [[0], [11], [15]]
     >>> list(_slicechunktodensity(revlog, [0, 11, 13, 15]))
     [[0], [11, 13, 15]]
     >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14]))
     [[1, 2], [5, 8, 10, 11], [14]]
     >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14],
     ...                           mingapsize=20))
     [[1, 2, 3, 5, 8, 10, 11], [14]]
     >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14],
     ...                           targetdensity=0.95))
     [[1, 2], [5], [8, 10, 11], [14]]
     >>> list(_slicechunktodensity(revlog, [1, 2, 3, 5, 8, 10, 11, 14],
     ...                           targetdensity=0.95, mingapsize=12))
     [[1, 2], [5, 8, 10, 11], [14]]
     """
     start = revlog.start
     length = revlog.length
 
     if len(revs) <= 1:
         yield revs
         return
 
     deltachainspan = segmentspan(revlog, revs)
 
     if deltachainspan < mingapsize:
         yield revs
         return
 
     readdata = deltachainspan
     chainpayload = sum(length(r) for r in revs)
 
     if deltachainspan:
         density = chainpayload / float(deltachainspan)
     else:
         density = 1.0
 
     if density >= targetdensity:
         yield revs
         return
 
     # Store the gaps in a heap to have them sorted by decreasing size
     gaps = []
     prevend = None
     for i, rev in enumerate(revs):
         revstart = start(rev)
         revlen = length(rev)
 
         # Skip empty revisions to form larger holes
         if revlen == 0:
             continue
 
         if prevend is not None:
             gapsize = revstart - prevend
             # only consider holes that are large enough
             if gapsize > mingapsize:
                 gaps.append((gapsize, i))
 
         prevend = revstart + revlen
     # sort the gaps to pop them from largest to small
     gaps.sort()
 
     # Collect the indices of the largest holes until the density is acceptable
     selected = []
     while gaps and density < targetdensity:
         gapsize, gapidx = gaps.pop()
 
         selected.append(gapidx)
 
         # the gap sizes are stored as negatives to be sorted decreasingly
         # by the heap
         readdata -= gapsize
         if readdata > 0:
             density = chainpayload / float(readdata)
         else:
             density = 1.0
     selected.sort()
 
     # Cut the revs at collected indices
     previdx = 0
     for idx in selected:
 
         chunk = _trimchunk(revlog, revs, previdx, idx)
         if chunk:
             yield chunk
 
         previdx = idx
 
     chunk = _trimchunk(revlog, revs, previdx)
     if chunk:
         yield chunk
 
 
 def _trimchunk(revlog, revs, startidx, endidx=None):
     """returns revs[startidx:endidx] without empty trailing revs
 
     Doctest Setup
     >>> revlog = _testrevlog([
     ...  5,  #0
     ...  10, #1
     ...  12, #2
     ...  12, #3 (empty)
     ...  17, #4
     ...  21, #5
     ...  21, #6 (empty)
     ... ])
 
     Contiguous cases:
     >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0)
     [0, 1, 2, 3, 4, 5]
     >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0, 5)
     [0, 1, 2, 3, 4]
     >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 0, 4)
     [0, 1, 2]
     >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 2, 4)
     [2]
     >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 3)
     [3, 4, 5]
     >>> _trimchunk(revlog, [0, 1, 2, 3, 4, 5, 6], 3, 5)
     [3, 4]
 
     Discontiguous cases:
     >>> _trimchunk(revlog, [1, 3, 5, 6], 0)
     [1, 3, 5]
     >>> _trimchunk(revlog, [1, 3, 5, 6], 0, 2)
     [1]
     >>> _trimchunk(revlog, [1, 3, 5, 6], 1, 3)
     [3, 5]
     >>> _trimchunk(revlog, [1, 3, 5, 6], 1)
     [3, 5]
     """
     length = revlog.length
 
     if endidx is None:
         endidx = len(revs)
 
     # If we have a non-emtpy delta candidate, there are nothing to trim
     if revs[endidx - 1] < len(revlog):
         # Trim empty revs at the end, except the very first revision of a chain
         while (
             endidx > 1 and endidx > startidx and length(revs[endidx - 1]) == 0
         ):
             endidx -= 1
 
     return revs[startidx:endidx]
 
 
 def segmentspan(revlog, revs):
     """Get the byte span of a segment of revisions
 
     revs is a sorted array of revision numbers
 
     >>> revlog = _testrevlog([
     ...  5,  #0
     ...  10, #1
     ...  12, #2
     ...  12, #3 (empty)
     ...  17, #4
     ... ])
 
     >>> segmentspan(revlog, [0, 1, 2, 3, 4])
     17
     >>> segmentspan(revlog, [0, 4])
     17
     >>> segmentspan(revlog, [3, 4])
     5
     >>> segmentspan(revlog, [1, 2, 3,])
     7
     >>> segmentspan(revlog, [1, 3])
     7
     """
     if not revs:
         return 0
     end = revlog.end(revs[-1])
     return end - revlog.start(revs[0])
 
 
 def _textfromdelta(fh, revlog, baserev, delta, p1, p2, flags, expectednode):
     """build full text from a (base, delta) pair and other metadata"""
     # special case deltas which replace entire base; no need to decode
     # base revision. this neatly avoids censored bases, which throw when
     # they're decoded.
     hlen = struct.calcsize(b">lll")
     if delta[:hlen] == mdiff.replacediffheader(
         revlog.rawsize(baserev), len(delta) - hlen
     ):
         fulltext = delta[hlen:]
     else:
         # deltabase is rawtext before changed by flag processors, which is
         # equivalent to non-raw text
         basetext = revlog.revision(baserev, _df=fh)
         fulltext = mdiff.patch(basetext, delta)
 
     try:
         validatehash = flagutil.processflagsraw(revlog, fulltext, flags)
         if validatehash:
             revlog.checkhash(fulltext, expectednode, p1=p1, p2=p2)
         if flags & REVIDX_ISCENSORED:
             raise error.StorageError(
                 _(b'node %s is not censored') % expectednode
             )
     except error.CensoredNodeError:
         # must pass the censored index flag to add censored revisions
         if not flags & REVIDX_ISCENSORED:
             raise
     return fulltext
 
 
 @attr.s(slots=True, frozen=True)
 class _deltainfo:
     distance = attr.ib()
     deltalen = attr.ib()
     data = attr.ib()
     base = attr.ib()
     chainbase = attr.ib()
     chainlen = attr.ib()
     compresseddeltalen = attr.ib()
     snapshotdepth = attr.ib()
 
 
 def drop_u_compression(delta):
     """turn into a "u" (no-compression) into no-compression without header
 
     This is useful for revlog format that has better compression method.
     """
     assert delta.data[0] == b'u', delta.data[0]
     return _deltainfo(
         delta.distance,
         delta.deltalen - 1,
         (b'', delta.data[1]),
         delta.base,
         delta.chainbase,
         delta.chainlen,
         delta.compresseddeltalen,
         delta.snapshotdepth,
     )
 
 
 def is_good_delta_info(revlog, deltainfo, revinfo):
     """Returns True if the given delta is good. Good means that it is within
     the disk span, disk size, and chain length bounds that we know to be
     performant."""
     if deltainfo is None:
         return False
 
     # - 'deltainfo.distance' is the distance from the base revision --
     #   bounding it limits the amount of I/O we need to do.
     # - 'deltainfo.compresseddeltalen' is the sum of the total size of
     #   deltas we need to apply -- bounding it limits the amount of CPU
     #   we consume.
 
     textlen = revinfo.textlen
     defaultmax = textlen * 4
     maxdist = revlog._maxdeltachainspan
     if not maxdist:
         maxdist = deltainfo.distance  # ensure the conditional pass
     maxdist = max(maxdist, defaultmax)
 
     # Bad delta from read span:
     #
     #   If the span of data read is larger than the maximum allowed.
     #
     #   In the sparse-revlog case, we rely on the associated "sparse reading"
     #   to avoid issue related to the span of data. In theory, it would be
     #   possible to build pathological revlog where delta pattern would lead
     #   to too many reads. However, they do not happen in practice at all. So
     #   we skip the span check entirely.
     if not revlog._sparserevlog and maxdist < deltainfo.distance:
         return False
 
     # Bad delta from new delta size:
     #
     #   If the delta size is larger than the target text, storing the
     #   delta will be inefficient.
     if textlen < deltainfo.deltalen:
         return False
 
     # Bad delta from cumulated payload size:
     #
     #   If the sum of delta get larger than K * target text length.
     if textlen * LIMIT_DELTA2TEXT < deltainfo.compresseddeltalen:
         return False
 
     # Bad delta from chain length:
     #
     #   If the number of delta in the chain gets too high.
     if revlog._maxchainlen and revlog._maxchainlen < deltainfo.chainlen:
         return False
 
     # bad delta from intermediate snapshot size limit
     #
     #   If an intermediate snapshot size is higher than the limit.  The
     #   limit exist to prevent endless chain of intermediate delta to be
     #   created.
     if (
         deltainfo.snapshotdepth is not None
         and (textlen >> deltainfo.snapshotdepth) < deltainfo.deltalen
     ):
         return False
 
     # bad delta if new intermediate snapshot is larger than the previous
     # snapshot
     if (
         deltainfo.snapshotdepth
         and revlog.length(deltainfo.base) < deltainfo.deltalen
     ):
         return False
 
     return True
 
 
 # If a revision's full text is that much bigger than a base candidate full
 # text's, it is very unlikely that it will produce a valid delta. We no longer
 # consider these candidates.
 LIMIT_BASE2TEXT = 500
 
 
 def _candidategroups(
     revlog,
     textlen,
     p1,
     p2,
     cachedelta,
     excluded_bases=None,
     target_rev=None,
 ):
     """Provides group of revision to be tested as delta base
 
     This top level function focus on emitting groups with unique and worthwhile
     content. See _raw_candidate_groups for details about the group order.
     """
     # should we try to build a delta?
     if not (len(revlog) and revlog._storedeltachains):
         yield None
         return
 
     deltalength = revlog.length
     deltaparent = revlog.deltaparent
     sparse = revlog._sparserevlog
     good = None
 
     deltas_limit = textlen * LIMIT_DELTA2TEXT
     group_chunk_size = revlog._candidate_group_chunk_size
 
     tested = {nullrev}
     candidates = _refinedgroups(
         revlog,
         p1,
         p2,
         cachedelta,
     )
     while True:
         temptative = candidates.send(good)
         if temptative is None:
             break
         group = []
         for rev in temptative:
             # skip over empty delta (no need to include them in a chain)
             while revlog._generaldelta and not (
                 rev == nullrev or rev in tested or deltalength(rev)
             ):
                 tested.add(rev)
                 rev = deltaparent(rev)
             # no need to try a delta against nullrev, this will be done as a
             # last resort.
             if rev == nullrev:
                 continue
             # filter out revision we tested already
             if rev in tested:
                 continue
             # an higher authority deamed the base unworthy (e.g. censored)
             if excluded_bases is not None and rev in excluded_bases:
                 tested.add(rev)
                 continue
             # We are in some recomputation cases and that rev is too high in
             # the revlog
             if target_rev is not None and rev >= target_rev:
                 tested.add(rev)
                 continue
             # filter out delta base that will never produce good delta
             if deltas_limit < revlog.length(rev):
                 tested.add(rev)
                 continue
             if sparse and revlog.rawsize(rev) < (textlen // LIMIT_BASE2TEXT):
                 tested.add(rev)
                 continue
             # no delta for rawtext-changing revs (see "candelta" for why)
             if revlog.flags(rev) & REVIDX_RAWTEXT_CHANGING_FLAGS:
                 tested.add(rev)
                 continue
 
             # If we reach here, we are about to build and test a delta.
             # The delta building process will compute the chaininfo in all
             # case, since that computation is cached, it is fine to access it
             # here too.
             chainlen, chainsize = revlog._chaininfo(rev)
             # if chain will be too long, skip base
             if revlog._maxchainlen and chainlen >= revlog._maxchainlen:
                 tested.add(rev)
                 continue
             # if chain already have too much data, skip base
             if deltas_limit < chainsize:
                 tested.add(rev)
                 continue
             if sparse and revlog.upperboundcomp is not None:
                 maxcomp = revlog.upperboundcomp
                 basenotsnap = (p1, p2, nullrev)
                 if rev not in basenotsnap and revlog.issnapshot(rev):
                     snapshotdepth = revlog.snapshotdepth(rev)
                     # If text is significantly larger than the base, we can
                     # expect the resulting delta to be proportional to the size
                     # difference
                     revsize = revlog.rawsize(rev)
                     rawsizedistance = max(textlen - revsize, 0)
                     # use an estimate of the compression upper bound.
                     lowestrealisticdeltalen = rawsizedistance // maxcomp
 
                     # check the absolute constraint on the delta size
                     snapshotlimit = textlen >> snapshotdepth
                     if snapshotlimit < lowestrealisticdeltalen:
                         # delta lower bound is larger than accepted upper bound
                         tested.add(rev)
                         continue
 
                     # check the relative constraint on the delta size
                     revlength = revlog.length(rev)
                     if revlength < lowestrealisticdeltalen:
                         # delta probable lower bound is larger than target base
                         tested.add(rev)
                         continue
 
             group.append(rev)
         if group:
             # When the size of the candidate group is big, it can result in a
             # quite significant performance impact. To reduce this, we can send
             # them in smaller batches until the new batch does not provide any
             # improvements.
             #
             # This might reduce the overall efficiency of the compression in
             # some corner cases, but that should also prevent very pathological
             # cases from being an issue. (eg. 20 000 candidates).
             #
             # XXX note that the ordering of the group becomes important as it
             # now impacts the final result. The current order is unprocessed
             # and can be improved.
             if group_chunk_size == 0:
                 tested.update(group)
                 good = yield tuple(group)
             else:
                 prev_good = good
                 for start in range(0, len(group), group_chunk_size):
                     sub_group = group[start : start + group_chunk_size]
                     tested.update(sub_group)
                     good = yield tuple(sub_group)
                     if prev_good == good:
                         break
 
     yield None
 
 
-def _findsnapshots(revlog, cache, start_rev):
-    """find snapshot from start_rev to tip"""
-    if util.safehasattr(revlog.index, b'findsnapshots'):
-        revlog.index.findsnapshots(cache, start_rev)
-    else:
-        deltaparent = revlog.deltaparent
-        issnapshot = revlog.issnapshot
-        for rev in revlog.revs(start_rev):
-            if issnapshot(rev):
-                cache[deltaparent(rev)].append(rev)
-
-
 def _refinedgroups(revlog, p1, p2, cachedelta):
     good = None
     # First we try to reuse a the delta contained in the bundle.
     # (or from the source revlog)
     #
     # This logic only applies to general delta repositories and can be disabled
     # through configuration. Disabling reuse source delta is useful when
     # we want to make sure we recomputed "optimal" deltas.
     debug_info = None
     if cachedelta is not None and cachedelta[2] > DELTA_BASE_REUSE_NO:
         # Assume what we received from the server is a good choice
         # build delta will reuse the cache
         if debug_info is not None:
             debug_info['cached-delta.tested'] += 1
         good = yield (cachedelta[0],)
         if good is not None:
             if debug_info is not None:
                 debug_info['cached-delta.accepted'] += 1
             yield None
             return
     # XXX cache me higher
-    snapshots = collections.defaultdict(list)
+    snapshot_cache = SnapshotCache()
     groups = _rawgroups(
         revlog,
         p1,
         p2,
         cachedelta,
-        snapshots,
+        snapshot_cache,
     )
     for candidates in groups:
         good = yield candidates
         if good is not None:
             break
 
     # If sparse revlog is enabled, we can try to refine the available deltas
     if not revlog._sparserevlog:
         yield None
         return
 
     # if we have a refinable value, try to refine it
     if good is not None and good not in (p1, p2) and revlog.issnapshot(good):
         # refine snapshot down
         previous = None
         while previous != good:
             previous = good
             base = revlog.deltaparent(good)
             if base == nullrev:
                 break
             good = yield (base,)
         # refine snapshot up
-        if not snapshots:
-            _findsnapshots(revlog, snapshots, good + 1)
+        if not snapshot_cache.snapshots:
+            snapshot_cache.update(revlog, good + 1)
         previous = None
         while good != previous:
             previous = good
-            children = tuple(sorted(c for c in snapshots[good]))
+            children = tuple(sorted(c for c in snapshot_cache.snapshots[good]))
             good = yield children
 
     if debug_info is not None:
         if good is None:
             debug_info['no-solution'] += 1
 
     yield None
 
 
-def _rawgroups(revlog, p1, p2, cachedelta, snapshots=None):
+def _rawgroups(revlog, p1, p2, cachedelta, snapshot_cache=None):
     """Provides group of revision to be tested as delta base
 
     This lower level function focus on emitting delta theorically interresting
     without looking it any practical details.
 
     The group order aims at providing fast or small candidates first.
     """
     gdelta = revlog._generaldelta
     # gate sparse behind general-delta because of issue6056
     sparse = gdelta and revlog._sparserevlog
     curr = len(revlog)
     prev = curr - 1
     deltachain = lambda rev: revlog._deltachain(rev)[0]
 
     if gdelta:
         # exclude already lazy tested base if any
         parents = [p for p in (p1, p2) if p != nullrev]
 
         if not revlog._deltabothparents and len(parents) == 2:
             parents.sort()
             # To minimize the chance of having to build a fulltext,
             # pick first whichever parent is closest to us (max rev)
             yield (parents[1],)
             # then the other one (min rev) if the first did not fit
             yield (parents[0],)
         elif len(parents) > 0:
             # Test all parents (1 or 2), and keep the best candidate
             yield parents
 
     if sparse and parents:
-        if snapshots is None:
+        if snapshot_cache is None:
             # map: base-rev: [snapshot-revs]
-            snapshots = collections.defaultdict(list)
+            snapshot_cache = SnapshotCache()
         # See if we can use an existing snapshot in the parent chains to use as
         # a base for a new intermediate-snapshot
         #
         # search for snapshot in parents delta chain
         # map: snapshot-level: snapshot-rev
         parents_snaps = collections.defaultdict(set)
         candidate_chains = [deltachain(p) for p in parents]
         for chain in candidate_chains:
             for idx, s in enumerate(chain):
                 if not revlog.issnapshot(s):
                     break
                 parents_snaps[idx].add(s)
         snapfloor = min(parents_snaps[0]) + 1
-        _findsnapshots(revlog, snapshots, snapfloor)
+        snapshot_cache.update(revlog, snapfloor)
         # search for the highest "unrelated" revision
         #
         # Adding snapshots used by "unrelated" revision increase the odd we
         # reuse an independant, yet better snapshot chain.
         #
         # XXX instead of building a set of revisions, we could lazily enumerate
         # over the chains. That would be more efficient, however we stick to
         # simple code for now.
         all_revs = set()
         for chain in candidate_chains:
             all_revs.update(chain)
         other = None
         for r in revlog.revs(prev, snapfloor):
             if r not in all_revs:
                 other = r
                 break
         if other is not None:
             # To avoid unfair competition, we won't use unrelated intermediate
             # snapshot that are deeper than the ones from the parent delta
             # chain.
             max_depth = max(parents_snaps.keys())
             chain = deltachain(other)
             for depth, s in enumerate(chain):
                 if s < snapfloor:
                     continue
                 if max_depth < depth:
                     break
                 if not revlog.issnapshot(s):
                     break
                 parents_snaps[depth].add(s)
         # Test them as possible intermediate snapshot base
         # We test them from highest to lowest level. High level one are more
         # likely to result in small delta
         floor = None
         for idx, snaps in sorted(parents_snaps.items(), reverse=True):
             siblings = set()
             for s in snaps:
-                siblings.update(snapshots[s])
+                siblings.update(snapshot_cache.snapshots[s])
             # Before considering making a new intermediate snapshot, we check
             # if an existing snapshot, children of base we consider, would be
             # suitable.
             #
             # It give a change to reuse a delta chain "unrelated" to the
             # current revision instead of starting our own. Without such
             # re-use, topological branches would keep reopening new chains.
             # Creating more and more snapshot as the repository grow.
 
             if floor is not None:
                 # We only do this for siblings created after the one in our
                 # parent's delta chain. Those created before has less chances
                 # to be valid base since our ancestors had to create a new
                 # snapshot.
                 siblings = [r for r in siblings if floor < r]
             yield tuple(sorted(siblings))
             # then test the base from our parent's delta chain.
             yield tuple(sorted(snaps))
             floor = min(snaps)
         # No suitable base found in the parent chain, search if any full
         # snapshots emitted since parent's base would be a suitable base for an
         # intermediate snapshot.
         #
         # It give a chance to reuse a delta chain unrelated to the current
         # revisions instead of starting our own. Without such re-use,
         # topological branches would keep reopening new full chains. Creating
         # more and more snapshot as the repository grow.
-        yield tuple(snapshots[nullrev])
+        yield tuple(snapshot_cache.snapshots[nullrev])
 
     if not sparse:
         # other approach failed try against prev to hopefully save us a
         # fulltext.
         yield (prev,)
 
 
+class SnapshotCache:
+    __slots__ = ('snapshots', '_start_rev', '_end_rev')
+
+    def __init__(self):
+        # XXX should probably be a set ?
+        self.snapshots = collections.defaultdict(list)
+        self._start_rev = None
+        self._end_rev = None
+
+    def update(self, revlog, start_rev=0):
+        """find snapshots from start_rev to tip"""
+        nb_revs = len(revlog)
+        end_rev = nb_revs - 1
+        if start_rev > end_rev:
+            return  # range is empty
+
+        if self._start_rev is None:
+            assert self._end_rev is None
+            self._update(revlog, start_rev, end_rev)
+        elif not (self._start_rev <= start_rev and end_rev <= self._end_rev):
+            if start_rev < self._start_rev:
+                self._update(revlog, start_rev, self._start_rev - 1)
+            if self._end_rev < end_rev:
+                self._update(revlog, self._end_rev + 1, end_rev)
+
+        if self._start_rev is None:
+            assert self._end_rev is None
+            self._end_rev = end_rev
+            self._start_rev = start_rev
+        else:
+            self._start_rev = min(self._start_rev, start_rev)
+            self._end_rev = max(self._end_rev, end_rev)
+        assert self._start_rev <= self._end_rev, (
+            self._start_rev,
+            self._end_rev,
+        )
+
+    def _update(self, revlog, start_rev, end_rev):
+        """internal method that actually do update content"""
+        assert self._start_rev is None or (
+            start_rev < self._start_rev or start_rev > self._end_rev
+        ), (self._start_rev, self._end_rev, start_rev, end_rev)
+        assert self._start_rev is None or (
+            end_rev < self._start_rev or end_rev > self._end_rev
+        ), (self._start_rev, self._end_rev, start_rev, end_rev)
+        cache = self.snapshots
+        if util.safehasattr(revlog.index, b'findsnapshots'):
+            revlog.index.findsnapshots(cache, start_rev, end_rev)
+        else:
+            deltaparent = revlog.deltaparent
+            issnapshot = revlog.issnapshot
+            for rev in revlog.revs(start_rev, end_rev):
+                if issnapshot(rev):
+                    cache[deltaparent(rev)].append(rev)
+
+
 class deltacomputer:
     def __init__(
         self,
         revlog,
         write_debug=None,
         debug_search=False,
         debug_info=None,
     ):
         self.revlog = revlog
         self._write_debug = write_debug
         self._debug_search = debug_search
         self._debug_info = debug_info
 
     def buildtext(self, revinfo, fh):
         """Builds a fulltext version of a revision
 
         revinfo: revisioninfo instance that contains all needed info
         fh:      file handle to either the .i or the .d revlog file,
                  depending on whether it is inlined or not
         """
         btext = revinfo.btext
         if btext[0] is not None:
             return btext[0]
 
         revlog = self.revlog
         cachedelta = revinfo.cachedelta
         baserev = cachedelta[0]
         delta = cachedelta[1]
 
         fulltext = btext[0] = _textfromdelta(
             fh,
             revlog,
             baserev,
             delta,
             revinfo.p1,
             revinfo.p2,
             revinfo.flags,
             revinfo.node,
         )
         return fulltext
 
     def _builddeltadiff(self, base, revinfo, fh):
         revlog = self.revlog
         t = self.buildtext(revinfo, fh)
         if revlog.iscensored(base):
             # deltas based on a censored revision must replace the
             # full content in one patch, so delta works everywhere
             header = mdiff.replacediffheader(revlog.rawsize(base), len(t))
             delta = header + t
         else:
             ptext = revlog.rawdata(base, _df=fh)
             delta = mdiff.textdiff(ptext, t)
 
         return delta
 
     def _builddeltainfo(self, revinfo, base, fh):
         # can we use the cached delta?
         revlog = self.revlog
         debug_search = self._write_debug is not None and self._debug_search
         chainbase = revlog.chainbase(base)
         if revlog._generaldelta:
             deltabase = base
         else:
             deltabase = chainbase
         snapshotdepth = None
         if revlog._sparserevlog and deltabase == nullrev:
             snapshotdepth = 0
         elif revlog._sparserevlog and revlog.issnapshot(deltabase):
             # A delta chain should always be one full snapshot,
             # zero or more semi-snapshots, and zero or more deltas
             p1, p2 = revlog.rev(revinfo.p1), revlog.rev(revinfo.p2)
             if deltabase not in (p1, p2) and revlog.issnapshot(deltabase):
                 snapshotdepth = len(revlog._deltachain(deltabase)[0])
         delta = None
         if revinfo.cachedelta:
             cachebase = revinfo.cachedelta[0]
             # check if the diff still apply
             currentbase = cachebase
             while (
                 currentbase != nullrev
                 and currentbase != base
                 and self.revlog.length(currentbase) == 0
             ):
                 currentbase = self.revlog.deltaparent(currentbase)
             if self.revlog._lazydelta and currentbase == base:
                 delta = revinfo.cachedelta[1]
         if delta is None:
             delta = self._builddeltadiff(base, revinfo, fh)
         if debug_search:
             msg = b"DBG-DELTAS-SEARCH:     uncompressed-delta-size=%d\n"
             msg %= len(delta)
             self._write_debug(msg)
         # snapshotdept need to be neither None nor 0 level snapshot
         if revlog.upperboundcomp is not None and snapshotdepth:
             lowestrealisticdeltalen = len(delta) // revlog.upperboundcomp
             snapshotlimit = revinfo.textlen >> snapshotdepth
             if debug_search:
                 msg = b"DBG-DELTAS-SEARCH:     projected-lower-size=%d\n"
                 msg %= lowestrealisticdeltalen
                 self._write_debug(msg)
             if snapshotlimit < lowestrealisticdeltalen:
                 if debug_search:
                     msg = b"DBG-DELTAS-SEARCH:     DISCARDED (snapshot limit)\n"
                     self._write_debug(msg)
                 return None
             if revlog.length(base) < lowestrealisticdeltalen:
                 if debug_search:
                     msg = b"DBG-DELTAS-SEARCH:     DISCARDED (prev size)\n"
                     self._write_debug(msg)
                 return None
         header, data = revlog.compress(delta)
         deltalen = len(header) + len(data)
         offset = revlog.end(len(revlog) - 1)
         dist = deltalen + offset - revlog.start(chainbase)
         chainlen, compresseddeltalen = revlog._chaininfo(base)
         chainlen += 1
         compresseddeltalen += deltalen
 
         return _deltainfo(
             dist,
             deltalen,
             (header, data),
             deltabase,
             chainbase,
             chainlen,
             compresseddeltalen,
             snapshotdepth,
         )
 
     def _fullsnapshotinfo(self, fh, revinfo, curr):
         rawtext = self.buildtext(revinfo, fh)
         data = self.revlog.compress(rawtext)
         compresseddeltalen = deltalen = dist = len(data[1]) + len(data[0])
         deltabase = chainbase = curr
         snapshotdepth = 0
         chainlen = 1
 
         return _deltainfo(
             dist,
             deltalen,
             data,
             deltabase,
             chainbase,
             chainlen,
             compresseddeltalen,
             snapshotdepth,
         )
 
     def finddeltainfo(self, revinfo, fh, excluded_bases=None, target_rev=None):
         """Find an acceptable delta against a candidate revision
 
         revinfo: information about the revision (instance of _revisioninfo)
         fh:      file handle to either the .i or the .d revlog file,
                  depending on whether it is inlined or not
 
         Returns the first acceptable candidate revision, as ordered by
         _candidategroups
 
         If no suitable deltabase is found, we return delta info for a full
         snapshot.
 
         `excluded_bases` is an optional set of revision that cannot be used as
         a delta base. Use this to recompute delta suitable in censor or strip
         context.
         """
         if target_rev is None:
             target_rev = len(self.revlog)
 
         if not revinfo.textlen:
             return self._fullsnapshotinfo(fh, revinfo, target_rev)
 
         if excluded_bases is None:
             excluded_bases = set()
 
         # no delta for flag processor revision (see "candelta" for why)
         # not calling candelta since only one revision needs test, also to
         # avoid overhead fetching flags again.
         if revinfo.flags & REVIDX_RAWTEXT_CHANGING_FLAGS:
             return self._fullsnapshotinfo(fh, revinfo, target_rev)
 
         gather_debug = (
             self._write_debug is not None or self._debug_info is not None
         )
         debug_search = self._write_debug is not None and self._debug_search
 
         if gather_debug:
             start = util.timer()
 
         # count the number of different delta we tried (for debug purpose)
         dbg_try_count = 0
         # count the number of "search round" we did. (for debug purpose)
         dbg_try_rounds = 0
         dbg_type = b'unknown'
 
         cachedelta = revinfo.cachedelta
         p1 = revinfo.p1
         p2 = revinfo.p2
         revlog = self.revlog
 
         deltainfo = None
         p1r, p2r = revlog.rev(p1), revlog.rev(p2)
 
         if gather_debug:
             if p1r != nullrev:
                 p1_chain_len = revlog._chaininfo(p1r)[0]
             else:
                 p1_chain_len = -1
             if p2r != nullrev:
                 p2_chain_len = revlog._chaininfo(p2r)[0]
             else:
                 p2_chain_len = -1
         if debug_search:
             msg = b"DBG-DELTAS-SEARCH: SEARCH rev=%d\n"
             msg %= target_rev
             self._write_debug(msg)
 
         groups = _candidategroups(
             self.revlog,
             revinfo.textlen,
             p1r,
             p2r,
             cachedelta,
             excluded_bases,
             target_rev,
         )
         candidaterevs = next(groups)
         while candidaterevs is not None:
             dbg_try_rounds += 1
             if debug_search:
                 prev = None
                 if deltainfo is not None:
                     prev = deltainfo.base
 
                 if (
                     cachedelta is not None
                     and len(candidaterevs) == 1
                     and cachedelta[0] in candidaterevs
                 ):
                     round_type = b"cached-delta"
                 elif p1 in candidaterevs or p2 in candidaterevs:
                     round_type = b"parents"
                 elif prev is not None and all(c < prev for c in candidaterevs):
                     round_type = b"refine-down"
                 elif prev is not None and all(c > prev for c in candidaterevs):
                     round_type = b"refine-up"
                 else:
                     round_type = b"search-down"
                 msg = b"DBG-DELTAS-SEARCH: ROUND #%d - %d candidates - %s\n"
                 msg %= (dbg_try_rounds, len(candidaterevs), round_type)
                 self._write_debug(msg)
             nominateddeltas = []
             if deltainfo is not None:
                 if debug_search:
                     msg = (
                         b"DBG-DELTAS-SEARCH:   CONTENDER: rev=%d - length=%d\n"
                     )
                     msg %= (deltainfo.base, deltainfo.deltalen)
                     self._write_debug(msg)
                 # if we already found a good delta,
                 # challenge it against refined candidates
                 nominateddeltas.append(deltainfo)
             for candidaterev in candidaterevs:
                 if debug_search:
                     msg = b"DBG-DELTAS-SEARCH:   CANDIDATE: rev=%d\n"
                     msg %= candidaterev
                     self._write_debug(msg)
                     candidate_type = None
                     if candidaterev == p1:
                         candidate_type = b"p1"
                     elif candidaterev == p2:
                         candidate_type = b"p2"
                     elif self.revlog.issnapshot(candidaterev):
                         candidate_type = b"snapshot-%d"
                         candidate_type %= self.revlog.snapshotdepth(
                             candidaterev
                         )
 
                     if candidate_type is not None:
                         msg = b"DBG-DELTAS-SEARCH:     type=%s\n"
                         msg %= candidate_type
                         self._write_debug(msg)
                     msg = b"DBG-DELTAS-SEARCH:     size=%d\n"
                     msg %= self.revlog.length(candidaterev)
                     self._write_debug(msg)
                     msg = b"DBG-DELTAS-SEARCH:     base=%d\n"
                     msg %= self.revlog.deltaparent(candidaterev)
                     self._write_debug(msg)
 
                 dbg_try_count += 1
 
                 if debug_search:
                     delta_start = util.timer()
                 candidatedelta = self._builddeltainfo(revinfo, candidaterev, fh)
                 if debug_search:
                     delta_end = util.timer()
                     msg = b"DBG-DELTAS-SEARCH:     delta-search-time=%f\n"
                     msg %= delta_end - delta_start
                     self._write_debug(msg)
                 if candidatedelta is not None:
                     if is_good_delta_info(self.revlog, candidatedelta, revinfo):
                         if debug_search:
                             msg = b"DBG-DELTAS-SEARCH:     DELTA: length=%d (GOOD)\n"
                             msg %= candidatedelta.deltalen
                             self._write_debug(msg)
                         nominateddeltas.append(candidatedelta)
                     elif debug_search:
                         msg = b"DBG-DELTAS-SEARCH:     DELTA: length=%d (BAD)\n"
                         msg %= candidatedelta.deltalen
                         self._write_debug(msg)
                 elif debug_search:
                     msg = b"DBG-DELTAS-SEARCH:     NO-DELTA\n"
                     self._write_debug(msg)
             if nominateddeltas:
                 deltainfo = min(nominateddeltas, key=lambda x: x.deltalen)
             if deltainfo is not None:
                 candidaterevs = groups.send(deltainfo.base)
             else:
                 candidaterevs = next(groups)
 
         if deltainfo is None:
             dbg_type = b"full"
             deltainfo = self._fullsnapshotinfo(fh, revinfo, target_rev)
         elif deltainfo.snapshotdepth:  # pytype: disable=attribute-error
             dbg_type = b"snapshot"
         else:
             dbg_type = b"delta"
 
         if gather_debug:
             end = util.timer()
             used_cached = (
                 cachedelta is not None
                 and dbg_try_rounds == 1
                 and dbg_try_count == 1
                 and deltainfo.base == cachedelta[0]
             )
             dbg = {
                 'duration': end - start,
                 'revision': target_rev,
                 'delta-base': deltainfo.base,  # pytype: disable=attribute-error
                 'search_round_count': dbg_try_rounds,
                 'using-cached-base': used_cached,
                 'delta_try_count': dbg_try_count,
                 'type': dbg_type,
                 'p1-chain-len': p1_chain_len,
                 'p2-chain-len': p2_chain_len,
             }
             if (
                 deltainfo.snapshotdepth  # pytype: disable=attribute-error
                 is not None
             ):
                 dbg[
                     'snapshot-depth'
                 ] = deltainfo.snapshotdepth  # pytype: disable=attribute-error
             else:
                 dbg['snapshot-depth'] = 0
             target_revlog = b"UNKNOWN"
             target_type = self.revlog.target[0]
             target_key = self.revlog.target[1]
             if target_type == KIND_CHANGELOG:
                 target_revlog = b'CHANGELOG:'
             elif target_type == KIND_MANIFESTLOG:
                 target_revlog = b'MANIFESTLOG:'
                 if target_key:
                     target_revlog += b'%s:' % target_key
             elif target_type == KIND_FILELOG:
                 target_revlog = b'FILELOG:'
                 if target_key:
                     target_revlog += b'%s:' % target_key
             dbg['target-revlog'] = target_revlog
 
             if self._debug_info is not None:
                 self._debug_info.append(dbg)
 
             if self._write_debug is not None:
                 msg = (
                     b"DBG-DELTAS:"
                     b" %-12s"
                     b" rev=%d:"
                     b" delta-base=%d"
                     b" is-cached=%d"
                     b" - search-rounds=%d"
                     b" try-count=%d"
                     b" - delta-type=%-6s"
                     b" snap-depth=%d"
                     b" - p1-chain-length=%d"
                     b" p2-chain-length=%d"
                     b" - duration=%f"
                     b"\n"
                 )
                 msg %= (
                     dbg["target-revlog"],
                     dbg["revision"],
                     dbg["delta-base"],
                     dbg["using-cached-base"],
                     dbg["search_round_count"],
                     dbg["delta_try_count"],
                     dbg["type"],
                     dbg["snapshot-depth"],
                     dbg["p1-chain-len"],
                     dbg["p2-chain-len"],
                     dbg["duration"],
                 )
                 self._write_debug(msg)
         return deltainfo
 
 
 def delta_compression(default_compression_header, deltainfo):
     """return (COMPRESSION_MODE, deltainfo)
 
     used by revlog v2+ format to dispatch between PLAIN and DEFAULT
     compression.
     """
     h, d = deltainfo.data
     compression_mode = COMP_MODE_INLINE
     if not h and not d:
         # not data to store at all... declare them uncompressed
         compression_mode = COMP_MODE_PLAIN
     elif not h:
         t = d[0:1]
         if t == b'\0':
             compression_mode = COMP_MODE_PLAIN
         elif t == default_compression_header:
             compression_mode = COMP_MODE_DEFAULT
     elif h == b'u':
         # we have a more efficient way to declare uncompressed
         h = b''
         compression_mode = COMP_MODE_PLAIN
         deltainfo = drop_u_compression(deltainfo)
     return compression_mode, deltainfo

tests/test-revlog-raw.py

@@ -1,524 +1,523 b''
 # test revlog interaction about raw data (flagprocessor)
 
 
-import collections
 import hashlib
 import sys
 
 from mercurial import (
     encoding,
     revlog,
     transaction,
     vfs,
 )
 
 from mercurial.revlogutils import (
     constants,
     deltas,
     flagutil,
 )
 
 
 class _NoTransaction:
     """transaction like object to update the nodemap outside a transaction"""
 
     def __init__(self):
         self._postclose = {}
 
     def addpostclose(self, callback_id, callback_func):
         self._postclose[callback_id] = callback_func
 
     def registertmp(self, *args, **kwargs):
         pass
 
     def addbackup(self, *args, **kwargs):
         pass
 
     def add(self, *args, **kwargs):
         pass
 
     def addabort(self, *args, **kwargs):
         pass
 
     def _report(self, *args):
         pass
 
 
 # TESTTMP is optional. This makes it convenient to run without run-tests.py
 tvfs = vfs.vfs(encoding.environ.get(b'TESTTMP', b'/tmp'))
 
 # Enable generaldelta otherwise revlog won't use delta as expected by the test
 tvfs.options = {
     b'generaldelta': True,
     b'revlogv1': True,
     b'sparse-revlog': True,
 }
 
 
 def abort(msg):
     print('abort: %s' % msg)
     # Return 0 so run-tests.py could compare the output.
     sys.exit()
 
 
 # Register a revlog processor for flag EXTSTORED.
 #
 # It simply prepends a fixed header, and replaces '1' to 'i'. So it has
 # insertion and replacement, and may be interesting to test revlog's line-based
 # deltas.
 _extheader = b'E\n'
 
 
 def readprocessor(self, rawtext):
     # True: the returned text could be used to verify hash
     text = rawtext[len(_extheader) :].replace(b'i', b'1')
     return text, True
 
 
 def writeprocessor(self, text):
     # False: the returned rawtext shouldn't be used to verify hash
     rawtext = _extheader + text.replace(b'1', b'i')
     return rawtext, False
 
 
 def rawprocessor(self, rawtext):
     # False: do not verify hash. Only the content returned by "readprocessor"
     # can be used to verify hash.
     return False
 
 
 flagutil.addflagprocessor(
     revlog.REVIDX_EXTSTORED, (readprocessor, writeprocessor, rawprocessor)
 )
 
 # Utilities about reading and appending revlog
 
 
 def newtransaction():
     # A transaction is required to write revlogs
     report = lambda msg: None
     return transaction.transaction(report, tvfs, {'plain': tvfs}, b'journal')
 
 
 def newrevlog(name=b'_testrevlog', recreate=False):
     if recreate:
         tvfs.tryunlink(name + b'.i')
     target = (constants.KIND_OTHER, b'test')
     rlog = revlog.revlog(tvfs, target=target, radix=name)
     return rlog
 
 
 def appendrev(rlog, text, tr, isext=False, isdelta=True):
     """Append a revision. If isext is True, set the EXTSTORED flag so flag
     processor will be used (and rawtext is different from text). If isdelta is
     True, force the revision to be a delta, otherwise it's full text.
     """
     nextrev = len(rlog)
     p1 = rlog.node(nextrev - 1)
     p2 = rlog.nullid
     if isext:
         flags = revlog.REVIDX_EXTSTORED
     else:
         flags = revlog.REVIDX_DEFAULT_FLAGS
     # Change storedeltachains temporarily, to override revlog's delta decision
     rlog._storedeltachains = isdelta
     try:
         rlog.addrevision(text, tr, nextrev, p1, p2, flags=flags)
         return nextrev
     except Exception as ex:
         abort('rev %d: failed to append: %s' % (nextrev, ex))
     finally:
         # Restore storedeltachains. It is always True, see revlog.__init__
         rlog._storedeltachains = True
 
 
 def addgroupcopy(rlog, tr, destname=b'_destrevlog', optimaldelta=True):
     """Copy revlog to destname using revlog.addgroup. Return the copied revlog.
 
     This emulates push or pull. They use changegroup. Changegroup requires
     repo to work. We don't have a repo, so a dummy changegroup is used.
 
     If optimaldelta is True, use optimized delta parent, so the destination
     revlog could probably reuse it. Otherwise it builds sub-optimal delta, and
     the destination revlog needs more work to use it.
 
     This exercises some revlog.addgroup (and revlog._addrevision(text=None))
     code path, which is not covered by "appendrev" alone.
     """
 
     class dummychangegroup:
         @staticmethod
         def deltachunk(pnode):
             pnode = pnode or rlog.nullid
             parentrev = rlog.rev(pnode)
             r = parentrev + 1
             if r >= len(rlog):
                 return {}
             if optimaldelta:
                 deltaparent = parentrev
             else:
                 # suboptimal deltaparent
                 deltaparent = min(0, parentrev)
             if not rlog.candelta(deltaparent, r):
                 deltaparent = -1
             return {
                 b'node': rlog.node(r),
                 b'p1': pnode,
                 b'p2': rlog.nullid,
                 b'cs': rlog.node(rlog.linkrev(r)),
                 b'flags': rlog.flags(r),
                 b'deltabase': rlog.node(deltaparent),
                 b'delta': rlog.revdiff(deltaparent, r),
                 b'sidedata': rlog.sidedata(r),
             }
 
         def deltaiter(self):
             chain = None
             for chunkdata in iter(lambda: self.deltachunk(chain), {}):
                 node = chunkdata[b'node']
                 p1 = chunkdata[b'p1']
                 p2 = chunkdata[b'p2']
                 cs = chunkdata[b'cs']
                 deltabase = chunkdata[b'deltabase']
                 delta = chunkdata[b'delta']
                 flags = chunkdata[b'flags']
                 sidedata = chunkdata[b'sidedata']
 
                 chain = node
 
                 yield (node, p1, p2, cs, deltabase, delta, flags, sidedata)
 
     def linkmap(lnode):
         return rlog.rev(lnode)
 
     dlog = newrevlog(destname, recreate=True)
     dummydeltas = dummychangegroup().deltaiter()
     dlog.addgroup(dummydeltas, linkmap, tr)
     return dlog
 
 
 def lowlevelcopy(rlog, tr, destname=b'_destrevlog'):
     """Like addgroupcopy, but use the low level revlog._addrevision directly.
 
     It exercises some code paths that are hard to reach easily otherwise.
     """
     dlog = newrevlog(destname, recreate=True)
     for r in rlog:
         p1 = rlog.node(r - 1)
         p2 = rlog.nullid
         if r == 0 or (rlog.flags(r) & revlog.REVIDX_EXTSTORED):
             text = rlog.rawdata(r)
             cachedelta = None
         else:
             # deltaparent cannot have EXTSTORED flag.
             deltaparent = max(
                 [-1]
                 + [
                     p
                     for p in range(r)
                     if rlog.flags(p) & revlog.REVIDX_EXTSTORED == 0
                 ]
             )
             text = None
             cachedelta = (deltaparent, rlog.revdiff(deltaparent, r))
         flags = rlog.flags(r)
         with dlog._writing(_NoTransaction()):
             dlog._addrevision(
                 rlog.node(r),
                 text,
                 tr,
                 r,
                 p1,
                 p2,
                 flags,
                 cachedelta,
             )
     return dlog
 
 
 # Utilities to generate revisions for testing
 
 
 def genbits(n):
     """Given a number n, generate (2 ** (n * 2) + 1) numbers in range(2 ** n).
     i.e. the generated numbers have a width of n bits.
 
     The combination of two adjacent numbers will cover all possible cases.
     That is to say, given any x, y where both x, and y are in range(2 ** n),
     there is an x followed immediately by y in the generated sequence.
     """
     m = 2 ** n
 
     # Gray Code. See https://en.wikipedia.org/wiki/Gray_code
     gray = lambda x: x ^ (x >> 1)
     reversegray = {gray(i): i for i in range(m)}
 
     # Generate (n * 2) bit gray code, yield lower n bits as X, and look for
     # the next unused gray code where higher n bits equal to X.
 
     # For gray codes whose higher bits are X, a[X] of them have been used.
     a = [0] * m
 
     # Iterate from 0.
     x = 0
     yield x
     for i in range(m * m):
         x = reversegray[x]
         y = gray(a[x] + x * m) & (m - 1)
         assert a[x] < m
         a[x] += 1
         x = y
         yield x
 
 
 def gentext(rev):
     '''Given a revision number, generate dummy text'''
     return b''.join(b'%d\n' % j for j in range(-1, rev % 5))
 
 
 def writecases(rlog, tr):
     """Write some revisions interested to the test.
 
     The test is interested in 3 properties of a revision:
 
         - Is it a delta or a full text? (isdelta)
           This is to catch some delta application issues.
         - Does it have a flag of EXTSTORED? (isext)
           This is to catch some flag processor issues. Especially when
           interacted with revlog deltas.
         - Is its text empty? (isempty)
           This is less important. It is intended to try to catch some careless
           checks like "if text" instead of "if text is None". Note: if flag
           processor is involved, raw text may be not empty.
 
     Write 65 revisions. So that all combinations of the above flags for
     adjacent revisions are covered. That is to say,
 
         len(set(
             (r.delta, r.ext, r.empty, (r+1).delta, (r+1).ext, (r+1).empty)
             for r in range(len(rlog) - 1)
            )) is 64.
 
     Where "r.delta", "r.ext", and "r.empty" are booleans matching properties
     mentioned above.
 
     Return expected [(text, rawtext)].
     """
     result = []
     for i, x in enumerate(genbits(3)):
         isdelta, isext, isempty = bool(x & 1), bool(x & 2), bool(x & 4)
         if isempty:
             text = b''
         else:
             text = gentext(i)
         rev = appendrev(rlog, text, tr, isext=isext, isdelta=isdelta)
 
         # Verify text, rawtext, and rawsize
         if isext:
             rawtext = writeprocessor(None, text)[0]
         else:
             rawtext = text
         if rlog.rawsize(rev) != len(rawtext):
             abort('rev %d: wrong rawsize' % rev)
         if rlog.revision(rev) != text:
             abort('rev %d: wrong text' % rev)
         if rlog.rawdata(rev) != rawtext:
             abort('rev %d: wrong rawtext' % rev)
         result.append((text, rawtext))
 
         # Verify flags like isdelta, isext work as expected
         # isdelta can be overridden to False if this or p1 has isext set
         if bool(rlog.deltaparent(rev) > -1) and not isdelta:
             abort('rev %d: isdelta is unexpected' % rev)
         if bool(rlog.flags(rev)) != isext:
             abort('rev %d: isext is ineffective' % rev)
     return result
 
 
 # Main test and checking
 
 
 def checkrevlog(rlog, expected):
     '''Check if revlog has expected contents. expected is [(text, rawtext)]'''
     # Test using different access orders. This could expose some issues
     # depending on revlog caching (see revlog._cache).
     for r0 in range(len(rlog) - 1):
         r1 = r0 + 1
         for revorder in [[r0, r1], [r1, r0]]:
             for raworder in [[True], [False], [True, False], [False, True]]:
                 nlog = newrevlog()
                 for rev in revorder:
                     for raw in raworder:
                         if raw:
                             t = nlog.rawdata(rev)
                         else:
                             t = nlog.revision(rev)
                         if t != expected[rev][int(raw)]:
                             abort(
                                 'rev %d: corrupted %stext'
                                 % (rev, raw and 'raw' or '')
                             )
 
 
 slicingdata = [
     ([0, 1, 2, 3, 55, 56, 58, 59, 60], [[0, 1], [2], [58], [59, 60]], 10),
     ([0, 1, 2, 3, 55, 56, 58, 59, 60], [[0, 1], [2], [58], [59, 60]], 10),
     (
         [-1, 0, 1, 2, 3, 55, 56, 58, 59, 60],
         [[-1, 0, 1], [2], [58], [59, 60]],
         10,
     ),
 ]
 
 
 def slicingtest(rlog):
     oldmin = rlog._srmingapsize
     try:
         # the test revlog is small, we remove the floor under which we
         # slicing is diregarded.
         rlog._srmingapsize = 0
         for item in slicingdata:
             chain, expected, target = item
             result = deltas.slicechunk(rlog, chain, targetsize=target)
             result = list(result)
             if result != expected:
                 print('slicing differ:')
                 print('  chain: %s' % chain)
                 print('  target: %s' % target)
                 print('  expected: %s' % expected)
                 print('  result:   %s' % result)
     finally:
         rlog._srmingapsize = oldmin
 
 
 def md5sum(s):
     return hashlib.md5(s).digest()
 
 
 def _maketext(*coord):
     """create piece of text according to range of integers
 
     The test returned use a md5sum of the integer to make it less
     compressible"""
     pieces = []
     for start, size in coord:
         num = range(start, start + size)
         p = [md5sum(b'%d' % r) for r in num]
         pieces.append(b'\n'.join(p))
     return b'\n'.join(pieces) + b'\n'
 
 
 data = [
     _maketext((0, 120), (456, 60)),
     _maketext((0, 120), (345, 60)),
     _maketext((0, 120), (734, 60)),
     _maketext((0, 120), (734, 60), (923, 45)),
     _maketext((0, 120), (734, 60), (234, 45)),
     _maketext((0, 120), (734, 60), (564, 45)),
     _maketext((0, 120), (734, 60), (361, 45)),
     _maketext((0, 120), (734, 60), (489, 45)),
     _maketext((0, 120), (123, 60)),
     _maketext((0, 120), (145, 60)),
     _maketext((0, 120), (104, 60)),
     _maketext((0, 120), (430, 60)),
     _maketext((0, 120), (430, 60), (923, 45)),
     _maketext((0, 120), (430, 60), (234, 45)),
     _maketext((0, 120), (430, 60), (564, 45)),
     _maketext((0, 120), (430, 60), (361, 45)),
     _maketext((0, 120), (430, 60), (489, 45)),
     _maketext((0, 120), (249, 60)),
     _maketext((0, 120), (832, 60)),
     _maketext((0, 120), (891, 60)),
     _maketext((0, 120), (543, 60)),
     _maketext((0, 120), (120, 60)),
     _maketext((0, 120), (60, 60), (768, 30)),
     _maketext((0, 120), (60, 60), (260, 30)),
     _maketext((0, 120), (60, 60), (450, 30)),
     _maketext((0, 120), (60, 60), (361, 30)),
     _maketext((0, 120), (60, 60), (886, 30)),
     _maketext((0, 120), (60, 60), (116, 30)),
     _maketext((0, 120), (60, 60), (567, 30), (629, 40)),
     _maketext((0, 120), (60, 60), (569, 30), (745, 40)),
     _maketext((0, 120), (60, 60), (777, 30), (700, 40)),
     _maketext((0, 120), (60, 60), (618, 30), (398, 40), (158, 10)),
 ]
 
 
 def makesnapshot(tr):
     rl = newrevlog(name=b'_snaprevlog3', recreate=True)
     for i in data:
         appendrev(rl, i, tr)
     return rl
 
 
 snapshots = [-1, 0, 6, 8, 11, 17, 19, 21, 25, 30]
 
 
 def issnapshottest(rlog):
     result = []
     if rlog.issnapshot(-1):
         result.append(-1)
     for rev in rlog:
         if rlog.issnapshot(rev):
             result.append(rev)
     if snapshots != result:
         print('snapshot differ:')
         print('  expected: %s' % snapshots)
         print('  got:      %s' % result)
 
 
 snapshotmapall = {0: [6, 8, 11, 17, 19, 25], 8: [21], -1: [0, 30]}
 snapshotmap15 = {0: [17, 19, 25], 8: [21], -1: [30]}
 
 
 def findsnapshottest(rlog):
-    resultall = collections.defaultdict(list)
-    deltas._findsnapshots(rlog, resultall, 0)
-    resultall = dict(resultall.items())
+    cache = deltas.SnapshotCache()
+    cache.update(rlog)
+    resultall = dict(cache.snapshots)
     if resultall != snapshotmapall:
         print('snapshot map  differ:')
         print('  expected: %s' % snapshotmapall)
         print('  got:      %s' % resultall)
-    result15 = collections.defaultdict(list)
-    deltas._findsnapshots(rlog, result15, 15)
-    result15 = dict(result15.items())
+    cache15 = deltas.SnapshotCache()
+    cache15.update(rlog, 15)
+    result15 = dict(cache15.snapshots)
     if result15 != snapshotmap15:
         print('snapshot map  differ:')
         print('  expected: %s' % snapshotmap15)
         print('  got:      %s' % result15)
 
 
 def maintest():
     with newtransaction() as tr:
         rl = newrevlog(recreate=True)
         expected = writecases(rl, tr)
         checkrevlog(rl, expected)
         print('local test passed')
         # Copy via revlog.addgroup
         rl1 = addgroupcopy(rl, tr)
         checkrevlog(rl1, expected)
         rl2 = addgroupcopy(rl, tr, optimaldelta=False)
         checkrevlog(rl2, expected)
         print('addgroupcopy test passed')
         # Copy via revlog.clone
         rl3 = newrevlog(name=b'_destrevlog3', recreate=True)
         rl.clone(tr, rl3)
         checkrevlog(rl3, expected)
         print('clone test passed')
         # Copy via low-level revlog._addrevision
         rl4 = lowlevelcopy(rl, tr)
         checkrevlog(rl4, expected)
         print('lowlevelcopy test passed')
         slicingtest(rl)
         print('slicing test passed')
         rl5 = makesnapshot(tr)
         issnapshottest(rl5)
         print('issnapshot test passed')
         findsnapshottest(rl5)
         print('findsnapshot test passed')
 
 
 try:
     maintest()
 except Exception as ex:
     abort('crashed: %s' % ex)