/*

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

#include <string.h>

#include <stdlib.h>

#include <Python.h>

/* VC9 doesn't include bool and lacks stdbool.h based on my searching */

#ifdef _MSC_VER

#define true 1

#define false 0

typedef unsigned char bool;

#else

#include <stdbool.h>

#endif

#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;

	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

/* defined in parsers.c */

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

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

static size_t pathlen(line *l) {

	return strlen(l->start);

}

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

static PyObject *nodeof(line *l) {

	char *s = l->start;

	ssize_t llen = pathlen(l);

	PyObject *hash = unhexlify(s + llen + 1, 40);

	if (!hash) {

		return NULL;

	}

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

		char newhash[21];

		memcpy(newhash, PyString_AsString(hash), 20);

		Py_DECREF(hash);

		newhash[20] = l->hash_suffix;

		hash = PyString_FromStringAndSize(newhash, 21);

	}

	return hash;

}

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

static PyObject *hashflags(line *l)

{

	char *s = l->start;

	size_t plen = pathlen(l);

	PyObject *hash = nodeof(l);

	/* 40 for hash, 1 for null byte, 1 for newline */

	size_t hplen = plen + 42;

	Py_ssize_t flen = l->len - hplen;

	PyObject *flags;

	PyObject *tup;

	if (!hash)

		return NULL;

	flags = PyString_FromStringAndSize(s + hplen - 1, flen);

	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 = memchr(data, '\n', len);

		if (!next) {

			return MANIFEST_MALFORMED;

		}

		next++; /* advance past newline */

		if (!realloc_if_full(self)) {

			return MANIFEST_OOM; /* no memory */

		}

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

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

			return MANIFEST_NOT_SORTED;

		}

		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 int lazymanifest_init(lazymanifest *self, PyObject *args)

{

	char *data;

	Py_ssize_t len;

	int err, ret;

	PyObject *pydata;

	if (!PyArg_ParseTuple(args, "S", &pydata)) {

		return -1;

	}

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

	self->dirty = false;

	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;

	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; i < self->numlines; i++) {

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

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

		}

	}

	if (self->lines) {

		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 PyObject *lmiter_iternext(PyObject *o)

{

	size_t pl;

	line *l;

	Py_ssize_t consumed;

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

	lmIter *self = (lmIter *)o;

	do {

		self->pos++;

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

			goto bail;

		}

		/* skip over deleted manifest entries */

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

	l = self->m->lines + self->pos;

	pl = pathlen(l);

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

	hash = nodeof(l);

	consumed = pl + 41;

	flags = PyString_FromStringAndSize(l->start + consumed,

									   l->len - consumed - 1);

	if (!flags) {

		goto bail;

	}

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

 bail:

	Py_XDECREF(path);

	Py_XDECREF(hash);

	Py_XDECREF(flags);

	return ret;

}

static PyTypeObject lazymanifestIterator = {

	PyObject_HEAD_INIT(NULL)

	0,                               /*ob_size */

	"parsers.lazymanifest.iterator", /*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 */

	/* tp_flags: Py_TPFLAGS_HAVE_ITER tells python to

	   use tp_iter and tp_iternext fields. */

	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_ITER,

	"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_iternext,                 /* tp_iternext: next() method */

};

static lazymanifest *lazymanifest_copy(lazymanifest *self);

static PyObject *lazymanifest_getiter(lazymanifest *self)

{

	lmIter *i = NULL;

	lazymanifest *t = lazymanifest_copy(self);

	if (!t) {

		PyErr_NoMemory();

		return NULL;

	}

	i = PyObject_New(lmIter, &lazymanifestIterator);

	if (i) {

		i->m = t;

		i->pos = -1;

	} else {

		Py_DECREF(t);

		PyErr_NoMemory();

	}

	return (PyObject *)i;

}

/* __getitem__ and __setitem__ support */

static Py_ssize_t lazymanifest_size(lazymanifest *self)

{

	return self->livelines;

}

static int linecmp(const void *left, const void *right)

{

	return strcmp(((const line *)left)->start,

		      ((const line *)right)->start);

}

static PyObject *lazymanifest_getitem(lazymanifest *self, PyObject *key)

{

	line needle;

	line *hit;

	if (!PyString_Check(key)) {

		PyErr_Format(PyExc_TypeError,

			     "getitem: manifest keys must be a string.");

		return NULL;

	}

	needle.start = PyString_AsString(key);

	hit = bsearch(&needle, self->lines, self->numlines, sizeof(line),

		      &linecmp);

	if (!hit || hit->deleted) {

		PyErr_Format(PyExc_KeyError, "No such manifest entry.");

		return NULL;

	}

	return hashflags(hit);

}

static int lazymanifest_delitem(lazymanifest *self, PyObject *key)

{

	line needle;

	line *hit;

	if (!PyString_Check(key)) {

		PyErr_Format(PyExc_TypeError,

			     "delitem: manifest keys must be a string.");

		return -1;

	}

	needle.start = PyString_AsString(key);

	hit = bsearch(&needle, self->lines, self->numlines, sizeof(line),

		      &linecmp);

	if (!hit || hit->deleted) {

		PyErr_Format(PyExc_KeyError,

			     "Tried to delete nonexistent manifest entry.");

		return -1;

	}

	self->dirty = true;

	hit->deleted = true;

	self->livelines--;

	return 0;

}

/* Do a binary search for the insertion point for new, creating the

 * new entry if needed. */

static int internalsetitem(lazymanifest *self, line *new) {

	int start = 0, end = self->numlines;

	while (start < end) {

		int pos = start + (end - start) / 2;

		int c = linecmp(new, self->lines + pos);

		if (c < 0)

			end = pos;

		else if (c > 0)

			start = pos + 1;

		else {

			if (self->lines[pos].deleted)

				self->livelines++;

			start = pos;

			goto finish;

		}

	}

	/* being here means we need to do an insert */

	if (!realloc_if_full(self)) {

		PyErr_NoMemory();

		return -1;

	}

	memmove(self->lines + start + 1, self->lines + start,

		(self->numlines - start) * sizeof(line));

	self->numlines++;

	self->livelines++;

finish:

	self->lines[start] = *new;

	self->dirty = true;

	return 0;

}

static int lazymanifest_setitem(

	lazymanifest *self, PyObject *key, PyObject *value)

{

	char *path;

	Py_ssize_t plen;

	PyObject *pyhash;

	Py_ssize_t hlen;

	char *hash;

	PyObject *pyflags;

	char *flags;

	Py_ssize_t flen;