#include <stdlib.h>
#include <string.h>

#include "array.h"
#include "mode.h"
#include "place.h"
#include "macro.h"

struct macro {
	struct place defplace;
	struct place expansionplace;
	unsigned hash;
	char *name;
	bool hasparams;
	struct stringarray params;
	char *expansion;
};
DECLARRAY(macro);
DEFARRAY(macro, );
DECLARRAY(macroarray);
DEFARRAY(macroarray, );

static struct macroarrayarray macros;
static unsigned total_macros;
static unsigned hashmask;

////////////////////////////////////////////////////////////
// macro structure ops

static
struct macro *
macro_create(struct place *p1, const char *name, unsigned hash,
	     struct place *p2, const char *expansion)
{
	struct macro *m;

	m = domalloc(sizeof(*m));
	m->defplace = *p1;
	m->expansionplace = *p2;
	m->hash = hash;
	m->name = dostrdup(name);
	m->hasparams = false;
	stringarray_init(&m->params);
	m->expansion = dostrdup(expansion);
	return m;
}

static
void
macro_destroy(struct macro *m)
{
	free(m->name);
	free(m->expansion);
	free(m);
}

static
bool
macro_eq(const struct macro *m1, const struct macro *m2)
{
	unsigned num1, num2, i;
	const char *p1, *p2;

	if (strcmp(m1->name, m2->name) != 0) {
		return false;
	}

	if (m1->hasparams != m2->hasparams) {
		return false;
	}

	if (strcmp(m1->expansion, m2->expansion) != 0) {
		return false;
	}

	num1 = stringarray_num(&m1->params);
	num2 = stringarray_num(&m2->params);
	if (num1 != num2) {
		return false;
	}

	for (i=0; i<num1; i++) {
		p1 = stringarray_get(&m1->params, i);
		p2 = stringarray_get(&m2->params, i);
		if (strcmp(p1, p2) != 0) {
			return false;
		}
	}
	return true;
}

////////////////////////////////////////////////////////////
// macro table

/*
 * Unless I've screwed up, this is something called Fletcher's Checksum
 * that showed up in Dr. Dobbs in, according to my notes, May 1992. The
 * implementation is new.
 */
static
unsigned
hashfunc(const char *s)
{
	uint16_t x1, x2, a;
	size_t i, len;

	len = strlen(s);

	x1 = (uint16_t) (len >> 16);
	x2 = (uint16_t) (len);
	if (x1==0) {
		x1++;
	}
	if (x2==0) {
		x2++;
	}

	for (i=0; i<len; i+=2) {
		if (i==len-1) {
			a = (unsigned char)s[i];
			/* don't run off the end of the array */
		}
		else {
			a = (unsigned char)s[i] +
				((uint16_t)(unsigned char)s[i+1] << 8);
		}
		x1 += a;
		if (x1 < a) {
			x1++;
		}
		x2 += x1;
		if (x2 < x1) {
			x2++;
		}
	}

	x1 ^= 0xffff;
	x2 ^= 0xffff;
	return ((uint32_t)x2)*65535U + x1;
}

static
void
macrotable_init(void)
{
	unsigned i;

	macroarrayarray_init(&macros);
	macroarrayarray_setsize(&macros, 4);
	for (i=0; i<4; i++) {
		macroarrayarray_set(&macros, i, NULL);
	}
	total_macros = 0;
	hashmask = 0x3;
}

DESTROYALL_ARRAY(macro, );

static
void
macrotable_cleanup(void)
{
	struct macroarray *bucket;
	unsigned numbuckets, i;

	numbuckets = macroarrayarray_num(&macros);
	for (i=0; i<numbuckets; i++) {
		bucket = macroarrayarray_get(&macros, i);
		macroarray_destroyall(bucket);
		macroarray_destroy(bucket);
	}
	macroarrayarray_setsize(&macros, 0);
	macroarrayarray_cleanup(&macros);
}

static
struct macro *
macrotable_find(const char *name, bool remove)
{
	unsigned hash;
	struct macroarray *bucket;
	struct macro *m, *m2;
	unsigned i, num;

	hash = hashfunc(name);
	bucket = macroarrayarray_get(&macros, hash & hashmask);
	if (bucket == NULL) {
		return NULL;
	}
	num = macroarray_num(bucket);
	for (i=0; i<num; i++) {
		m = macroarray_get(bucket, i);
		if (hash != m->hash) {
			continue;
		}
		if (!strcmp(name, m->name)) {
			if (remove) {
				if (i < num-1) {
					m2 = macroarray_get(bucket, num-1);
					macroarray_set(bucket, i, m2);
				}
				macroarray_setsize(bucket, num-1);
				total_macros--;
			}
			return m;
		}
	}
	return NULL;
}

static
void
macrotable_rehash(void)
{
	struct macroarray *newbucket, *oldbucket;
	struct macro *m;
	unsigned newmask, tossbit;
	unsigned numbuckets, i;
	unsigned oldnum, j, k;

	numbuckets = macroarrayarray_num(&macros);
	macroarrayarray_setsize(&macros, numbuckets*2);

	assert(hashmask == numbuckets - 1);
	newmask = (hashmask << 1) | 1U;
	tossbit = newmask && ~hashmask;
	hashmask = newmask;

	for (i=0; i<numbuckets; i++) {
		newbucket = NULL;
		oldbucket = macroarrayarray_get(&macros, i);
		oldnum = macroarray_num(oldbucket);
		for (j=0; j<oldnum; j++) {
			m = macroarray_get(oldbucket, j);
			if (m->hash & tossbit) {
				if (newbucket == NULL) {
					newbucket = macroarray_create();
				}
				macroarray_set(oldbucket, j, NULL);
				macroarray_add(newbucket, m, NULL);
			}
		}
		for (j=k=0; j<oldnum; j++) {
			m = macroarray_get(oldbucket, j);
			if (m != NULL && k < j) {
				macroarray_set(oldbucket, k++, m);
			}
		}
		macroarray_setsize(oldbucket, k);
		macroarrayarray_set(&macros, numbuckets + i, newbucket);
	}
}

static
void
macrotable_add(struct macro *m)
{
	unsigned hash;
	struct macroarray *bucket;
	unsigned numbuckets;

	numbuckets = macroarrayarray_num(&macros);
	if (total_macros > 0 && total_macros / numbuckets > 9) {
		macrotable_rehash();
	}

	hash = hashfunc(m->name);
	bucket = macroarrayarray_get(&macros, hash & hashmask);
	if (bucket == NULL) {
		bucket = macroarray_create();
		macroarrayarray_set(&macros, hash & hashmask, bucket);
	}
	macroarray_add(bucket, m, NULL);
	total_macros++;
}

////////////////////////////////////////////////////////////
// external macro definition interface

static
struct macro *
macro_define_common_start(struct place *p1, const char *macro,
			  struct place *p2, const char *expansion)
{
	struct macro *m;

	if (!is_identifier(macro)) {
		complain(p1, "Invalid macro name %s", macro);
		complain_fail();
	}

	m = macro_create(p1, macro, hashfunc(macro), p2, expansion);
	return m;
}

static
void
macro_define_common_end(struct macro *m)
{
	struct macro *oldm;
	bool ok;

	oldm = macrotable_find(m->name, false);
	if (oldm != NULL) {
		ok = macro_eq(m, oldm);
		if (ok) {
			complain(&m->defplace,
				 "Warning: redefinition of %s", m->name);
			if (mode.werror) {
				complain_fail();
			}
		} else {
			complain(&m->defplace,
				 "Redefinition of %s is not identical",
				 m->name);
			complain_fail();
		}
		complain(&oldm->defplace, "Previous definition was here");
		macro_destroy(m);
		return;
	}
	macrotable_add(m);
}

static
void
macro_parse_parameters(struct macro *m, struct place *p, const char *params)
{
	size_t len;
	const char *s;
	char *param;

	while (params != NULL) {
		len = strspn(params, ws);
		params += len;
		p->column += len;
		s = strchr(params, ',');
		if (s) {
			len = s-params;
			param = dostrndup(params, len);
			s++;
		} else {
			len = strlen(params);
			param = dostrndup(params, len);
		}
		notrailingws(param, strlen(param));
		if (!is_identifier(param)) {
			complain(p, "Invalid macro parameter name %s", param);
			complain_fail();
		} else {
			stringarray_add(&m->params, param, NULL);
		}
		params = s;
		p->column += len;
	}
}

void
macro_define_plain(struct place *p1, const char *macro,
		   struct place *p2, const char *expansion)
{
	struct macro *m;

	m = macro_define_common_start(p1, macro, p2, expansion);
	macro_define_common_end(m);
}

void
macro_define_params(struct place *p1, const char *macro,
		    struct place *p2, const char *params,
		    struct place *p3, const char *expansion)
{
	struct macro *m;

	m = macro_define_common_start(p1, macro, p3, expansion);
	macro_parse_parameters(m, p2, params);
	macro_define_common_end(m);
}

void
macro_undef(const char *macro)
{
	struct macro *m;

	m = macrotable_find(macro, true);
	if (m) {
		macro_destroy(m);
	}
}

bool
macro_isdefined(const char *macro)
{
	struct macro *m;

	m = macrotable_find(macro, false);
	return m != NULL;
}

////////////////////////////////////////////////////////////
// macro expansion

char *macroexpand(struct place *, char *buf, size_t len, bool honordefined);

void macro_sendline(struct place *, char *buf, size_t len);
void macro_sendeof(struct place *);

////////////////////////////////////////////////////////////
// module initialization

void
macros_init(void)
{
	macrotable_init();
}

void
macros_cleanup(void)
{
	macrotable_cleanup();
}