/*

 * manifest.c - manifest type that does on-demand parsing.

 *

 * Copyright 2015, Google Inc.

 *

 * 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 <stdlib.h>

#include <string.h>

#include "charencode.h"

#include "util.h"

#define DEFAULT_LINES 100000

typedef struct {

	char *start;

	Py_ssize_t len; /* length of line including terminal newline */

	char hash_suffix;

	bool from_malloc;

	bool deleted;

} line;

typedef struct {

	PyObject_HEAD

	PyObject *pydata;

	Py_ssize_t nodelen;

	line *lines;

	int numlines; /* number of line entries */

	int livelines; /* number of non-deleted lines */

	int maxlines; /* allocated number of lines */

	bool dirty;

} lazymanifest;

#define MANIFEST_OOM -1

#define MANIFEST_NOT_SORTED -2

#define MANIFEST_MALFORMED -3

#define MANIFEST_BOGUS_FILENAME -4

#define MANIFEST_TOO_SHORT_LINE -5

/* get the length of the path for a line */

static Py_ssize_t pathlen(line *l)

{

	const char *end = memchr(l->start, '\0', l->len);

	return (end) ? (Py_ssize_t)(end - l->start) : l->len;

}

/* get the node value of a single line */

static PyObject *nodeof(Py_ssize_t nodelen, line *l, char *flag)

{

	char *s = l->start;

	Py_ssize_t llen = pathlen(l);

	Py_ssize_t hlen = l->len - llen - 2;

	PyObject *hash;

	if (llen + 1 + 40 + 1 > l->len) { /* path '\0' hash '\n' */

		PyErr_SetString(PyExc_ValueError, "manifest line too short");

		return NULL;

	}

	/* Detect flags after the hash first. */

	switch (s[llen + hlen]) {

	case 'l':

	case 't':

	case 'x':

		*flag = s[llen + hlen];

		--hlen;

		break;

	default:

		*flag = '\0';

		break;

	}

	if (hlen != 2 * nodelen) {

		PyErr_SetString(PyExc_ValueError, "invalid node length in manifest");

		return NULL;

	}

	hash = unhexlify(s + llen + 1, nodelen * 2);

	if (!hash) {

		return NULL;

	}

	if (l->hash_suffix != '\0') {

		char newhash[33];

		memcpy(newhash, PyBytes_AsString(hash), nodelen);

		Py_DECREF(hash);

		newhash[nodelen] = l->hash_suffix;

		hash = PyBytes_FromStringAndSize(newhash, nodelen + 1);

	}

	return hash;

}

/* get the node hash and flags of a line as a tuple */

static PyObject *hashflags(Py_ssize_t nodelen, line *l)

{

	char flag;

	PyObject *hash = nodeof(nodelen, l, &flag);

	PyObject *flags;

	PyObject *tup;

	if (!hash)

		return NULL;

	flags = PyBytes_FromStringAndSize(&flag, flag ? 1 : 0);

	if (!flags) {

		Py_DECREF(hash);

		return NULL;

	}

	tup = PyTuple_Pack(2, hash, flags);

	Py_DECREF(flags);

	Py_DECREF(hash);

	return tup;

}

/* if we're about to run out of space in the line index, add more */

static bool realloc_if_full(lazymanifest *self)

{

	if (self->numlines == self->maxlines) {

		self->maxlines *= 2;

		self->lines = realloc(self->lines, self->maxlines * sizeof(line));

	}

	return !!self->lines;

}

/*

 * Find the line boundaries in the manifest that 'data' points to and store

 * information about each line in 'self'.

 */

static int find_lines(lazymanifest *self, char *data, Py_ssize_t len)

{

	char *prev = NULL;

	while (len > 0) {

		line *l;

		char *next;

		if (*data == '\0') {

			/* It's implausible there's no filename, don't

			 * even bother looking for the newline. */

			return MANIFEST_BOGUS_FILENAME;

		}

		next = memchr(data, '\n', len);

		if (!next) {

			return MANIFEST_MALFORMED;

		}

		if ((next - data) < 42) {

			/* We should have at least 42 bytes in a line:

			   1 byte filename

			   1 NUL

			   40 bytes of hash

			   so we can give up here.

			*/

			return MANIFEST_TOO_SHORT_LINE;

		}

		next++; /* advance past newline */

		if (prev && strcmp(prev, data) > -1) {

			/* This data isn't sorted, so we have to abort. */

			return MANIFEST_NOT_SORTED;

		}

		if (!realloc_if_full(self)) {

			return MANIFEST_OOM; /* no memory */

		}

		l = self->lines + ((self->numlines)++);

		l->start = data;

		l->len = next - data;

		l->hash_suffix = '\0';

		l->from_malloc = false;

		l->deleted = false;

		len = len - l->len;

		prev = data;

		data = next;

	}

	self->livelines = self->numlines;

	return 0;

}

static void lazymanifest_init_early(lazymanifest *self)

{

	self->pydata = NULL;

	self->lines = NULL;

	self->numlines = 0;

	self->maxlines = 0;

}

static int lazymanifest_init(lazymanifest *self, PyObject *args)

{

	char *data;

	Py_ssize_t nodelen, len;

	int err, ret;

	PyObject *pydata;

	lazymanifest_init_early(self);

	if (!PyArg_ParseTuple(args, "nS", &nodelen, &pydata)) {

		return -1;

	}

	if (nodelen != 20 && nodelen != 32) {

		/* See fixed buffer in nodeof */

		PyErr_Format(PyExc_ValueError, "Unsupported node length");

		return -1;

	}

	self->nodelen = nodelen;

	self->dirty = false;

	err = PyBytes_AsStringAndSize(pydata, &data, &len);

	if (err == -1)

		return -1;

	self->pydata = pydata;

	Py_INCREF(self->pydata);

	Py_BEGIN_ALLOW_THREADS

	self->lines = malloc(DEFAULT_LINES * sizeof(line));

	self->maxlines = DEFAULT_LINES;

	self->numlines = 0;

	if (!self->lines)

		ret = MANIFEST_OOM;

	else

		ret = find_lines(self, data, len);

	Py_END_ALLOW_THREADS

	switch (ret) {

	case 0:

		break;

	case MANIFEST_OOM:

		PyErr_NoMemory();

		break;

	case MANIFEST_NOT_SORTED:

		PyErr_Format(PyExc_ValueError,

			     "Manifest lines not in sorted order.");

		break;

	case MANIFEST_MALFORMED:

		PyErr_Format(PyExc_ValueError,

			     "Manifest did not end in a newline.");

		break;

	case MANIFEST_BOGUS_FILENAME:

		PyErr_Format(

			PyExc_ValueError,

			"Manifest had an entry with a zero-length filename.");

		break;

	case MANIFEST_TOO_SHORT_LINE:

		PyErr_Format(

			PyExc_ValueError,

			"Manifest had implausibly-short line.");

		break;

	default:

		PyErr_Format(PyExc_ValueError,

			     "Unknown problem parsing manifest.");

	}

	return ret == 0 ? 0 : -1;

}

static void lazymanifest_dealloc(lazymanifest *self)

{

	/* free any extra lines we had to allocate */

	int i;

	for (i = 0; self->lines && (i < self->numlines); i++) {

		if (self->lines[i].from_malloc) {

			free(self->lines[i].start);

		}

	}

	free(self->lines);

	self->lines = NULL;

	if (self->pydata) {

		Py_DECREF(self->pydata);

		self->pydata = NULL;

	}

	PyObject_Del(self);

}

/* iteration support */

typedef struct {

	PyObject_HEAD lazymanifest *m;

	Py_ssize_t pos;

} lmIter;

static void lmiter_dealloc(PyObject *o)

{

	lmIter *self = (lmIter *)o;

	Py_DECREF(self->m);

	PyObject_Del(self);

}

static line *lmiter_nextline(lmIter *self)

{

	do {

		self->pos++;

		if (self->pos >= self->m->numlines) {

			return NULL;

		}

		/* skip over deleted manifest entries */

	} while (self->m->lines[self->pos].deleted);

	return self->m->lines + self->pos;

}

static PyObject *lmiter_iterentriesnext(PyObject *o)

{

	lmIter *self = (lmIter *)o;

	Py_ssize_t pl;

	line *l;

	char flag;

	PyObject *ret = NULL, *path = NULL, *hash = NULL, *flags = NULL;

	l = lmiter_nextline(self);

	if (!l) {

		goto done;

	}

	pl = pathlen(l);

	path = PyBytes_FromStringAndSize(l->start, pl);

	hash = nodeof(self->m->nodelen, l, &flag);

	if (!path || !hash) {

		goto done;

	}

	flags = PyBytes_FromStringAndSize(&flag, flag ? 1 : 0);

	if (!flags) {

		goto done;

	}

	ret = PyTuple_Pack(3, path, hash, flags);

done:

	Py_XDECREF(path);

	Py_XDECREF(hash);

	Py_XDECREF(flags);

	return ret;

}

#define LAZYMANIFESTENTRIESITERATOR_TPFLAGS Py_TPFLAGS_DEFAULT

static PyTypeObject lazymanifestEntriesIterator = {

	PyVarObject_HEAD_INIT(NULL, 0) /* header */

	"parsers.lazymanifest.entriesiterator", /*tp_name */

	sizeof(lmIter),                  /*tp_basicsize */

	0,                               /*tp_itemsize */

	lmiter_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 */

	LAZYMANIFESTENTRIESITERATOR_TPFLAGS, /* tp_flags */

	"Iterator for 3-tuples in a lazymanifest.",  /* tp_doc */

	0,                               /* tp_traverse */

	0,                               /* tp_clear */

	0,                               /* tp_richcompare */

	0,                               /* tp_weaklistoffset */

	PyObject_SelfIter,               /* tp_iter: __iter__() method */

	lmiter_iterentriesnext,          /* tp_iternext: next() method */

};

static PyObject *lmiter_iterkeysnext(PyObject *o)

{

	Py_ssize_t pl;

	line *l = lmiter_nextline((lmIter *)o);

	if (!l) {

		return NULL;

	}

	pl = pathlen(l);

	return PyBytes_FromStringAndSize(l->start, pl);

}

#define LAZYMANIFESTKEYSITERATOR_TPFLAGS Py_TPFLAGS_DEFAULT

static PyTypeObject lazymanifestKeysIterator = {

	PyVarObject_HEAD_INIT(NULL, 0) /* header */

	"parsers.lazymanifest.keysiterator", /*tp_name */

	sizeof(lmIter),                  /*tp_basicsize */

	0,                               /*tp_itemsize */

	lmiter_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 */

	LAZYMANIFESTKEYSITERATOR_TPFLAGS, /* tp_flags */

	"Keys iterator for a lazymanifest.",  /* tp_doc */

	0,                               /* tp_traverse */

	0,                               /* tp_clear */

	0,                               /* tp_richcompare */

	0,                               /* tp_weaklistoffset */

	PyObject_SelfIter,               /* tp_iter: __iter__() method */

	lmiter_iterkeysnext,             /* tp_iternext: next() method */

};

static lazymanifest *lazymanifest_copy(lazymanifest *self);

static PyObject *lazymanifest_getentriesiter(lazymanifest *self)

{

	lmIter *i = NULL;

	lazymanifest *t = lazymanifest_copy(self);

	if (!t) {