/*

 parsers.c - efficient content parsing

 Copyright 2008 Olivia Mackall <olivia@selenic.com> 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);