/*

 parsers.c - efficient content parsing

 Copyright 2008 Matt Mackall <mpm@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.

*/

#include <Python.h>

#include <assert.h>

#include <ctype.h>

#include <stddef.h>

#include <string.h>

#include "bitmanipulation.h"

#include "charencode.h"

#include "util.h"

#ifdef IS_PY3K

/* The mapping of Python types is meant to be temporary to get Python

 * 3 to compile. We should remove this once Python 3 support is fully

 * supported and proper types are used in the extensions themselves. */

#define PyInt_Check PyLong_Check

#define PyInt_FromLong PyLong_FromLong

#define PyInt_FromSsize_t PyLong_FromSsize_t

#define PyInt_AS_LONG PyLong_AS_LONG

#define PyInt_AsLong PyLong_AsLong

#endif

typedef struct indexObjectStruct indexObject;

typedef struct {

	int children[16];

} nodetreenode;

/*

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

	PyObject_HEAD

	indexObject *index;

	nodetreenode *nodes;

	unsigned length;     /* # nodes in use */

	unsigned capacity;   /* # nodes allocated */

	int depth;           /* maximum depth of tree */

	int splits;          /* # splits performed */

} nodetree;

/*

 * 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. Our last entry is a

 * sentinel, always a nullid.  We have limited support for

 * integer-keyed insert and delete, only at elements right before the

 * sentinel.

 *

 * 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_buffer buf;         /* buffer of data */

	PyObject **cache;      /* cached tuples */

	const char **offsets;  /* populated on demand */

	Py_ssize_t raw_length; /* original number of elements */

	Py_ssize_t length;     /* current number of elements */

	PyObject *added;       /* populated on demand */

	PyObject *headrevs;    /* cache, invalidated on changes */

	PyObject *filteredrevs;/* filtered revs set */

	nodetree *nt;          /* base-16 trie */

	int ntrev;             /* last rev scanned */

	int ntlookups;         /* # lookups */

	int ntmisses;          /* # lookups that miss the cache */

	int inlined;

};

static Py_ssize_t index_length(const indexObject *self)

{

	if (self->added == NULL)

		return self->length;

	return self->length + PyList_GET_SIZE(self->added);

}

static PyObject *nullentry;

static const char nullid[20];

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

#if LONG_MAX == 0x7fffffffL

static const char *const tuple_format = PY23("Kiiiiiis#", "Kiiiiiiy#");

#else

static const char *const tuple_format = PY23("kiiiiiis#", "kiiiiiiy#");

#endif

/* A RevlogNG v1 index entry is 64 bytes long. */

static const long v1_hdrsize = 64;

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 (self->inlined && pos > 0) {

		if (self->offsets == NULL) {

			self->offsets = PyMem_Malloc(self->raw_length *

					             sizeof(*self->offsets));

			if (self->offsets == NULL)

				return (const char *)PyErr_NoMemory();

			inline_scan(self, self->offsets);

		}

		return self->offsets[pos];

	}

	return (const char *)(self->buf.buf) + pos * v1_hdrsize;

}

static inline int index_get_parents(indexObject *self, Py_ssize_t rev,

				    int *ps, int maxrev)

{

	if (rev >= self->length) {

		PyObject *tuple = PyList_GET_ITEM(self->added, rev - self->length);

		ps[0] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 5));

		ps[1] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 6));

	} else {

		const char *data = index_deref(self, rev);

		ps[0] = getbe32(data + 24);

		ps[1] = getbe32(data + 28);

	}

	/* If index file is corrupted, ps[] may point to invalid revisions. So

	 * there is a risk of buffer overflow to trust them unconditionally. */

	if (ps[0] > maxrev || ps[1] > maxrev) {

		PyErr_SetString(PyExc_ValueError, "parent out of range");

		return -1;

	}

	return 0;

}

/*

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

 */

static PyObject *index_get(indexObject *self, Py_ssize_t pos)

{

	uint64_t offset_flags;

	int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;

	const char *c_node_id;

	const char *data;

	Py_ssize_t length = index_length(self);

	PyObject *entry;

	if (pos == -1) {

		Py_INCREF(nullentry);

		return nullentry;

	}

	if (pos < 0 || pos >= length) {

		PyErr_SetString(PyExc_IndexError, "revlog index out of range");

		return NULL;

	}

	if (pos >= self->length) {

		PyObject *obj;

		obj = PyList_GET_ITEM(self->added, pos - self->length);

		Py_INCREF(obj);

		return obj;

	}

	if (self->cache) {

		if (self->cache[pos]) {

			Py_INCREF(self->cache[pos]);

			return self->cache[pos];

		}

	} else {

		self->cache = calloc(self->raw_length, sizeof(PyObject *));

		if (self->cache == NULL)

			return PyErr_NoMemory();

	}

	data = index_deref(self, pos);

	if (data == NULL)

		return NULL;

	offset_flags = getbe32(data + 4);

	if (pos == 0) /* mask out version number for the first entry */

		offset_flags &= 0xFFFF;

	else {

		uint32_t offset_high = getbe32(data);

		offset_flags |= ((uint64_t)offset_high) << 32;

	}

	comp_len = getbe32(data + 8);

	uncomp_len = getbe32(data + 12);

	base_rev = getbe32(data + 16);

	link_rev = getbe32(data + 20);

	parent_1 = getbe32(data + 24);

	parent_2 = getbe32(data + 28);

	c_node_id = data + 32;

	entry = Py_BuildValue(tuple_format, offset_flags, comp_len,

			      uncomp_len, base_rev, link_rev,

			      parent_1, parent_2, c_node_id, 20);

	if (entry) {

		PyObject_GC_UnTrack(entry);

		Py_INCREF(entry);

	}

	self->cache[pos] = entry;

	return entry;

}

/*

 * Return the 20-byte SHA of the node corresponding to the given rev.

 */

static const char *index_node(indexObject *self, Py_ssize_t pos)

{

	Py_ssize_t length = index_length(self);

	const char *data;

	if (pos == -1)

		return nullid;

	if (pos >= length)

		return NULL;

	if (pos >= self->length) {

		PyObject *tuple, *str;

		tuple = PyList_GET_ITEM(self->added, pos - self->length);

		str = PyTuple_GetItem(tuple, 7);

		return str ? PyBytes_AS_STRING(str) : NULL;

	}

	data = index_deref(self, pos);

	return data ? data + 32 : NULL;

}

/*

 * Return the 20-byte SHA of the node corresponding to the given rev. The

 * rev is assumed to be existing. If not, an exception is set.

 */

static const char *index_node_existing(indexObject *self, Py_ssize_t pos)

{

	const char *node = index_node(self, pos);

	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(PyObject *obj, char **node)

{

	Py_ssize_t nodelen;

	if (PyBytes_AsStringAndSize(obj, node, &nodelen) == -1)

		return -1;

	if (nodelen == 20)

		return 0;

	PyErr_SetString(PyExc_ValueError, "20-byte hash required");

	return -1;

}

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

{

	char *node;

	Py_ssize_t len;

	if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) {

		PyErr_SetString(PyExc_TypeError, "8-tuple required");

		return NULL;

	}

	if (node_check(PyTuple_GET_ITEM(obj, 7), &node) == -1)

		return NULL;

	len = index_length(self);

	if (self->added == NULL) {

		self->added = PyList_New(0);

		if (self->added == NULL)

			return NULL;

	}

	if (PyList_Append(self->added, obj) == -1)

		return NULL;

	if (self->nt)

		nt_insert(self->nt, node, (int)len);

	Py_CLEAR(self->headrevs);

	Py_RETURN_NONE;

}

static PyObject *index_stats(indexObject *self)

{

	PyObject *obj = PyDict_New();

	PyObject *t = NULL;

	if (obj == NULL)

		return NULL;

#define istat(__n, __d) \

	do { \

		t = PyInt_FromSsize_t(self->__n); \

		if (!t) \

			goto bail; \

		if (PyDict_SetItemString(obj, __d, t) == -1) \

			goto bail; \

		Py_DECREF(t); \

	} while (0)

	if (self->added) {

		Py_ssize_t len = PyList_GET_SIZE(self->added);

		t = PyInt_FromSsize_t(len);

		if (!t)

			goto bail;

		if (PyDict_SetItemString(obj, "index entries added", t) == -1)

			goto bail;

		Py_DECREF(t);

	}

	if (self->raw_length != self->length)

		istat(raw_length, "revs on disk");

	istat(length, "revs in memory");

	istat(ntlookups, "node trie lookups");

	istat(ntmisses, "node trie misses");

	istat(ntrev, "node trie last rev scanned");

	if (self->nt) {

		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(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 = PyEval_CallObject(filter, arglist);

		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 Py_ssize_t add_roots_get_min(indexObject *self, PyObject *list,

                                    Py_ssize_t marker, char *phases)

{

	PyObject *iter = NULL;

	PyObject *iter_item = NULL;

	Py_ssize_t min_idx = index_length(self) + 2;

	long iter_item_long;

	if (PyList_GET_SIZE(list) != 0) {

		iter = PyObject_GetIter(list);

		if (iter == NULL)

			return -2;

		while ((iter_item = PyIter_Next(iter))) {

			iter_item_long = PyInt_AS_LONG(iter_item);

			Py_DECREF(iter_item);

			if (iter_item_long < min_idx)

				min_idx = iter_item_long;

			phases[iter_item_long] = marker;

		}

		Py_DECREF(iter);

	}

	return min_idx;

}

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;