/*

 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 <ctype.h>

#include <stddef.h>

#include <string.h>

#include "util.h"

static inline int hexdigit(const char *p, Py_ssize_t off)

{

	char c = p[off];

	if (c >= '0' && c <= '9')

		return c - '0';

	if (c >= 'a' && c <= 'f')

		return c - 'a' + 10;

	if (c >= 'A' && c <= 'F')

		return c - 'A' + 10;

	PyErr_SetString(PyExc_ValueError, "input contains non-hex character");

	return 0;

}

/*

 * Turn a hex-encoded string into binary.

 */

static PyObject *unhexlify(const char *str, int len)

{

	PyObject *ret;

	char *d;

	int i;

	ret = PyBytes_FromStringAndSize(NULL, len / 2);

	if (!ret)

		return NULL;

	d = PyBytes_AsString(ret);

	for (i = 0; i < len;) {

		int hi = hexdigit(str, i++);

		int lo = hexdigit(str, i++);

		*d++ = (hi << 4) | lo;

	}

	return ret;

}

/*

 * This code assumes that a manifest is stitched together with newline

 * ('\n') characters.

 */

static PyObject *parse_manifest(PyObject *self, PyObject *args)

{

	PyObject *mfdict, *fdict;

	char *str, *cur, *start, *zero;

	int len;

	if (!PyArg_ParseTuple(args, "O!O!s#:parse_manifest",

			      &PyDict_Type, &mfdict,

			      &PyDict_Type, &fdict,

			      &str, &len))

		goto quit;

	for (start = cur = str, zero = NULL; cur < str + len; cur++) {

		PyObject *file = NULL, *node = NULL;

		PyObject *flags = NULL;

		ptrdiff_t nlen;

		if (!*cur) {

			zero = cur;

			continue;

		}

		else if (*cur != '\n')

			continue;

		if (!zero) {

			PyErr_SetString(PyExc_ValueError,

					"manifest entry has no separator");

			goto quit;

		}

		file = PyBytes_FromStringAndSize(start, zero - start);

		if (!file)

			goto bail;

		nlen = cur - zero - 1;

		node = unhexlify(zero + 1, nlen > 40 ? 40 : (int)nlen);

		if (!node)

			goto bail;

		if (nlen > 40) {

			flags = PyBytes_FromStringAndSize(zero + 41,

							   nlen - 40);

			if (!flags)

				goto bail;

			if (PyDict_SetItem(fdict, file, flags) == -1)

				goto bail;

		}

		if (PyDict_SetItem(mfdict, file, node) == -1)

			goto bail;

		start = cur + 1;

		zero = NULL;

		Py_XDECREF(flags);

		Py_XDECREF(node);

		Py_XDECREF(file);

		continue;

	bail:

		Py_XDECREF(flags);

		Py_XDECREF(node);

		Py_XDECREF(file);

		goto quit;

	}

	if (len > 0 && *(cur - 1) != '\n') {

		PyErr_SetString(PyExc_ValueError,

				"manifest contains trailing garbage");

		goto quit;

	}

	Py_INCREF(Py_None);

	return Py_None;

quit:

	return NULL;

}

static PyObject *parse_dirstate(PyObject *self, PyObject *args)

{

	PyObject *dmap, *cmap, *parents = NULL, *ret = NULL;

	PyObject *fname = NULL, *cname = NULL, *entry = NULL;

	char *str, *cur, *end, *cpos;

	int state, mode, size, mtime;

	unsigned int flen;

	int len;

	if (!PyArg_ParseTuple(args, "O!O!s#:parse_dirstate",

			      &PyDict_Type, &dmap,

			      &PyDict_Type, &cmap,

			      &str, &len))

		goto quit;

	/* read parents */

	if (len < 40)

		goto quit;

	parents = Py_BuildValue("s#s#", str, 20, str + 20, 20);

	if (!parents)

		goto quit;

	/* read filenames */

	cur = str + 40;

	end = str + len;

	while (cur < end - 17) {

		/* unpack header */

		state = *cur;

		mode = getbe32(cur + 1);

		size = getbe32(cur + 5);

		mtime = getbe32(cur + 9);

		flen = getbe32(cur + 13);

		cur += 17;

		if (cur + flen > end || cur + flen < cur) {

			PyErr_SetString(PyExc_ValueError, "overflow in dirstate");

			goto quit;

		}

		entry = Py_BuildValue("ciii", state, mode, size, mtime);

		if (!entry)

			goto quit;

		PyObject_GC_UnTrack(entry); /* don't waste time with this */

		cpos = memchr(cur, 0, flen);

		if (cpos) {

			fname = PyBytes_FromStringAndSize(cur, cpos - cur);

			cname = PyBytes_FromStringAndSize(cpos + 1,

							   flen - (cpos - cur) - 1);

			if (!fname || !cname ||

			    PyDict_SetItem(cmap, fname, cname) == -1 ||

			    PyDict_SetItem(dmap, fname, entry) == -1)

				goto quit;

			Py_DECREF(cname);

		} else {

			fname = PyBytes_FromStringAndSize(cur, flen);

			if (!fname ||

			    PyDict_SetItem(dmap, fname, entry) == -1)

				goto quit;

		}

		cur += flen;

		Py_DECREF(fname);

		Py_DECREF(entry);

		fname = cname = entry = NULL;

	}

	ret = parents;

	Py_INCREF(ret);

quit:

	Py_XDECREF(fname);

	Py_XDECREF(cname);

	Py_XDECREF(entry);

	Py_XDECREF(parents);

	return ret;

}

static inline int getintat(PyObject *tuple, int off, uint32_t *v)

{

	PyObject *o = PyTuple_GET_ITEM(tuple, off);

	long val;

	if (PyInt_Check(o))

		val = PyInt_AS_LONG(o);

	else if (PyLong_Check(o)) {

		val = PyLong_AsLong(o);

		if (val == -1 && PyErr_Occurred())

			return -1;

	} else {

		PyErr_SetString(PyExc_TypeError, "expected an int or long");

		return -1;

	}

	if (LONG_MAX > INT_MAX && (val > INT_MAX || val < INT_MIN)) {

		PyErr_SetString(PyExc_OverflowError,

				"Python value to large to convert to uint32_t");

		return -1;

	}

	*v = (uint32_t)val;

	return 0;

}

static PyObject *dirstate_unset;

/*

 * Efficiently pack a dirstate object into its on-disk format.

 */

static PyObject *pack_dirstate(PyObject *self, PyObject *args)

{

	PyObject *packobj = NULL;

	PyObject *map, *copymap, *pl;

	Py_ssize_t nbytes, pos, l;

	PyObject *k, *v, *pn;

	char *p, *s;

	double now;

	if (!PyArg_ParseTuple(args, "O!O!Od:pack_dirstate",

			      &PyDict_Type, &map, &PyDict_Type, &copymap,

			      &pl, &now))

		return NULL;

	if (!PySequence_Check(pl) || PySequence_Size(pl) != 2) {

		PyErr_SetString(PyExc_TypeError, "expected 2-element sequence");

		return NULL;

	}

	/* Figure out how much we need to allocate. */

	for (nbytes = 40, pos = 0; PyDict_Next(map, &pos, &k, &v);) {

		PyObject *c;

		if (!PyString_Check(k)) {

			PyErr_SetString(PyExc_TypeError, "expected string key");

			goto bail;

		}

		nbytes += PyString_GET_SIZE(k) + 17;

		c = PyDict_GetItem(copymap, k);

		if (c) {

			if (!PyString_Check(c)) {

				PyErr_SetString(PyExc_TypeError,

						"expected string key");

				goto bail;

			}

			nbytes += PyString_GET_SIZE(c) + 1;

		}

	}

	packobj = PyString_FromStringAndSize(NULL, nbytes);

	if (packobj == NULL)

		goto bail;

	p = PyString_AS_STRING(packobj);

	pn = PySequence_ITEM(pl, 0);

	if (PyString_AsStringAndSize(pn, &s, &l) == -1 || l != 20) {

		PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash");

		goto bail;

	}

	memcpy(p, s, l);

	p += 20;

	pn = PySequence_ITEM(pl, 1);

	if (PyString_AsStringAndSize(pn, &s, &l) == -1 || l != 20) {

		PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash");

		goto bail;

	}

	memcpy(p, s, l);

	p += 20;

	for (pos = 0; PyDict_Next(map, &pos, &k, &v); ) {

		uint32_t mode, size, mtime;

		Py_ssize_t len, l;

		PyObject *o;

		char *s, *t;

		if (!PyTuple_Check(v) || PyTuple_GET_SIZE(v) != 4) {

			PyErr_SetString(PyExc_TypeError, "expected a 4-tuple");

			goto bail;

		}

		o = PyTuple_GET_ITEM(v, 0);

		if (PyString_AsStringAndSize(o, &s, &l) == -1 || l != 1) {

			PyErr_SetString(PyExc_TypeError, "expected one byte");

			goto bail;

		}

		*p++ = *s;

		if (getintat(v, 1, &mode) == -1)

			goto bail;

		if (getintat(v, 2, &size) == -1)

			goto bail;

		if (getintat(v, 3, &mtime) == -1)

			goto bail;

		if (*s == 'n' && mtime == (uint32_t)now) {

			/* See dirstate.py:write for why we do this. */

			if (PyDict_SetItem(map, k, dirstate_unset) == -1)

				goto bail;

			mode = 0, size = -1, mtime = -1;

		}

		putbe32(mode, p);

		putbe32(size, p + 4);

		putbe32(mtime, p + 8);

		t = p + 12;

		p += 16;

		len = PyString_GET_SIZE(k);

		memcpy(p, PyString_AS_STRING(k), len);

		p += len;

		o = PyDict_GetItem(copymap, k);

		if (o) {

			*p++ = '\0';

			l = PyString_GET_SIZE(o);

			memcpy(p, PyString_AS_STRING(o), l);

			p += l;

			len += l + 1;

		}

		putbe32((uint32_t)len, t);

	}

	pos = p - PyString_AS_STRING(packobj);

	if (pos != nbytes) {

		PyErr_Format(PyExc_SystemError, "bad dirstate size: %ld != %ld",

                             (long)pos, (long)nbytes);

		goto bail;

	}

	return packobj;

bail:

	Py_XDECREF(packobj);

	return NULL;

}

/*

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

 * Zero is empty

 */

typedef struct {

	int children[16];

} nodetree;

/*

 * This class has two behaviours.

 *

 * 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