/*

 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;