/*
 *  Generate random C declarations for testing.
 *  Copyright © 2011 Nick Bowler
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <config.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <errno.h>
#include <assert.h>
#include <stdbool.h>
#include <gsl/gsl_rng.h>

#include "declgen.h"
#include "cdecl.h"
#include "test.h"

struct gen_rng {
	gsl_rng *rng;
};

/*
 * Generate a random identifier.  We arbitrarily pick 10 as the largest
 * possible.  Avoid generating keywords, including the English ones, by
 * excluding the letters t, o, a and n.  Reserved words are OK.
 */
char *gen_identifier(struct gen_rng *rng)
{
	static const char valid[59] = "_bcdefghijklmpqrsuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
	char *str;
	size_t n;

	n = gsl_rng_uniform_int(rng->rng, 10)+1;
	str = malloc_nofail(n+1);

	/* Exclude 10 digits from the first character. */
	str[0] = valid[gsl_rng_uniform_int(rng->rng, sizeof valid - 10)];
	for (size_t i = 1; i < n; i++)
		str[i] = valid[gsl_rng_uniform_int(rng->rng, sizeof valid)];
	str[n] = 0;

	return str;
}

/*
 * Generate random qualifiers.  Qualifiers can appear multiple times, so the
 * list is (potentially) unbounded.  We handle the potential unboundedness by
 * generating a list of n qualifiers with probability 1/2^(n+1).  Each
 * qualifier is chosen uniformly at random from the set of possibilities:
 * const, volatile and, if restrictqual is true, restrict.
 */
struct cdecl_declspec *gen_qualifiers(struct gen_rng *rng, bool restrictqual)
{
	struct cdecl_declspec *s = NULL, *p;

	while (gsl_rng_uniform(rng->rng) < 0.5) {
		p = s;
		s = malloc_nofail(sizeof *s);
		*s = (struct cdecl_declspec) {
			.next = p,
		};

		switch (gsl_rng_uniform_int(rng->rng, 2+restrictqual)) {
		case 0:
			s->type = CDECL_QUAL_CONST;
			break;
		case 1:
			s->type = CDECL_QUAL_VOLATILE;
			break;
		case 2: /* Only if restrictqual is true. */
			s->type = CDECL_QUAL_RESTRICT;
			break;
		default:
			assert(0);
		}
	}

	return s;
}

/*
 * Generate random function specifiers.  Like qualifiers, function specifiers
 * can appear multiple times.
 */
struct cdecl_declspec *gen_funcspecs(struct gen_rng *rng)
{
	struct cdecl_declspec *s = NULL, *p;

	while (gsl_rng_uniform(rng->rng) < 0.5) {
		p = s;
		s = malloc_nofail(sizeof *s);

		*s = (struct cdecl_declspec) {
			.type = CDECL_FUNC_INLINE,
			.next = p,
		};
	}

	return s;
}

/*
 * Generate zero or one random storage-class specifier.  If registeronly is
 * true, then the only possible storage-class specifier is "register".
 * Otherwise, a specifier type will be selected uniformly at random.
 */
struct cdecl_declspec *gen_storspecs(struct gen_rng *rng, bool registeronly)
{
	struct cdecl_declspec *s;

	if (gsl_rng_uniform(rng->rng) < 0.5)
		return NULL;

	s = malloc_nofail(sizeof *s);
	*s = (struct cdecl_declspec) {
		.type = CDECL_STOR_REGISTER,
	};

	if (registeronly)
		return s;

	switch (gsl_rng_uniform_int(rng->rng, 5)) {
	case 0: s->type = CDECL_STOR_TYPEDEF;  break;
	case 1: s->type = CDECL_STOR_REGISTER; break;
	case 2: s->type = CDECL_STOR_STATIC;   break;
	case 3: s->type = CDECL_STOR_AUTO;     break;
	case 4: s->type = CDECL_STOR_EXTERN;   break;
	default: assert(0);
	}

	return s;
}

/*
 * Generate random type specifiers.  There is a short list of valid
 * combinations, from which we can select one uniformly at random.
 */
static const unsigned long total_types;
static struct cdecl_declspec *gen_raw_typespecs(struct gen_rng *rng)
{
	switch (gsl_rng_uniform_int(rng->rng, total_types)) {
#	include "typegen.h"
	}
}
static const unsigned long total_types = TOTAL_TYPES;

struct cdecl_declspec *gen_typespecs(struct gen_rng *rng, bool voidtype)
{
	struct cdecl_declspec *specs;

retry:
	specs = gen_raw_typespecs(rng);

	switch (specs->type) {
	/* void is not always valid, so we might need to pick again. */
	case CDECL_TYPE_VOID:
		if (!voidtype)
			goto retry;
		break;
	/* A few kinds of type specifiers need identifiers to go with them. */
	case CDECL_TYPE_STRUCT:
	case CDECL_TYPE_UNION:
	case CDECL_TYPE_ENUM:
	case CDECL_TYPE_IDENT:
		assert(!specs->next);
		specs->ident = gen_identifier(rng);
		break;
	default:
		/* Nothing to be done. */
		;
	}

	return specs;
}

struct cdecl_declspec *
gen_randomize_specs(struct gen_rng *rng, struct cdecl_declspec *specs)
{
	struct cdecl_declspec **p;
	size_t n = 0;

	if (!specs)
		return specs;

	for (struct cdecl_declspec *s = specs; s; s = s->next)
		n++;

	p = malloc_nofail((n+1) * sizeof *p);

	/* Build a temporary array for easy element swapping. */
	p[0] = specs;
	p[n] = NULL;
	for (size_t i = 1; i < n; i++)
		p[i] = p[i-1]->next;

	/* Knuth shuffle. */
	for (size_t i = 0; i < n; i++) {
		struct cdecl_declspec *tmp;
		size_t r;
		
		r = gsl_rng_uniform_int(rng->rng, n-i);
		tmp = p[i];
		p[i] = p[r+i];
		p[r+i] = tmp;
	}

	/* Fix up the pointers. */
	for (size_t i = 1; i <= n; i++)
		p[i-1]->next = p[i];
	specs = p[0];

	free(p);
	return specs;
}

/*
 * Generate random declaration specifiers.  This consists of random qualifiers
 * and type specifiers, as described in the functions above, plus up to one
 * storage-class specifier and zero or more function specifiers.
 *
 * The flags parameter controls what sort of specifiers can be generated in
 * order to handle various special cases in the C language.  It is the
 * bitwise-or of zero or more values, which have the following meanings:
 * 
 *   GEN_NO_FUNCTION: Do not generate any function specifiers at all.
 *   GEN_NO_STORAGE: Do not generate any storage-class specifiers at all.
 *   GEN_NO_VOID: Do not generate the "void" type specifier.
 *   GEN_ONLY_REGISTER: Never generate any storage-class specifiers other than
 *                      "register".
 *
 * Notwithstanding any of the above, the "restrict" type qualifier will never
 * be generated by this function: use gen_qualifiers directly.
 */
struct cdecl_declspec *
gen_declspecs(struct gen_rng *rng, unsigned flags)
{
	struct cdecl_declspec *s, *p;

	s = gen_typespecs(rng, ~flags & GEN_NO_VOID);
	for (p = s; p->next;)
		p = p->next;

	if (~flags & GEN_NO_FUNCTION)
		p->next = gen_funcspecs(rng);
	for (p = s; p->next;)
		p = p->next;

	if (~flags & GEN_NO_STORAGE)
		p->next = gen_storspecs(rng, flags & GEN_ONLY_REGISTER);
	for (p = s; p->next;)
		p = p->next;

	p->next = gen_qualifiers(rng, false);
	return gen_randomize_specs(rng, s);
}

static uintmax_t gen_uintmax(struct gen_rng *rng)
{
	unsigned char tmp;
	uintmax_t ret = 0;

	for (size_t i = 0; i < sizeof ret; i++) {
		tmp = gsl_rng_uniform_int(rng->rng, UCHAR_MAX+1);
		ret <<= CHAR_BIT;
		ret |= tmp;
	}

	return ret;
}

/*
 * Generate a random array declarator, selecting one of four possibilities
 * uniformly at random.
 */
static void gen_array(struct gen_rng *rng, struct cdecl_declarator *d)
{
	d->type = CDECL_DECL_ARRAY;
	d->u.array = (struct cdecl_array){0};

	switch (gsl_rng_uniform_int(rng->rng, 4)) {
	case 0:
		d->u.array.vla = malloc_nofail(1);
		d->u.array.vla[0] = 0;
		break;
	case 1:
		d->u.array.vla = gen_identifier(rng);
		break;
	case 2:
		d->u.array.length = 0;
		break;
	case 3:
		d->u.array.length = gen_uintmax(rng);
		break;
	default:
		assert(0);
	}
}

/* Generate a function declarator. */
static void gen_function(struct gen_rng *rng, struct cdecl_declarator *d)
{
	d->type = CDECL_DECL_FUNCTION;
	d->u.function.parameters = NULL;

	while (gsl_rng_uniform(rng->rng) < 0.5) {
		unsigned flags = GEN_ONLY_REGISTER | GEN_NO_FUNCTION;
		struct cdecl *param;

		param = malloc_nofail(sizeof *param);
		*param = (struct cdecl) {
			.next = d->u.function.parameters,
			.declarators = gen_declarators(rng),
		};

		if (param->declarators->type != CDECL_DECL_POINTER
		    && param->declarators->type != CDECL_DECL_FUNCTION)
			flags |= GEN_NO_VOID;

		param->specifiers = gen_declspecs(rng, flags);
		d->u.function.parameters = param;
	}

	if (d->u.function.parameters) {
		d->u.function.variadic = gsl_rng_uniform(rng->rng) < 0.5;
	} else if (gsl_rng_uniform(rng->rng) < 0.5) {
		struct cdecl *param;

		/* We will never generate (void) above; do it here. */
		param = malloc_nofail(sizeof *param);
		*param = (struct cdecl) { 0 };

		param->declarators = malloc_nofail(sizeof *param->declarators);
		*param->declarators = (struct cdecl_declarator) {
			.type = CDECL_DECL_NULL,
		};

		param->specifiers = malloc_nofail(sizeof *param->specifiers);
		*param->specifiers = (struct cdecl_declspec) {
			.type = CDECL_TYPE_VOID,
		};

		d->u.function.parameters = param;
	}
}

/*
 * Generate a random chain of declarators.  Like qualifiers above, a chain of
 * length N has probability 1/2^(N+1) of occurring.  All declarator chains
 * are ultimately terminated by either a null declarator or an identifier,
 * selected uniformly at random.
 */
struct cdecl_declarator *gen_declarators(struct gen_rng *rng)
{
	struct cdecl_declarator *d, *p;
	unsigned limit = 3;

	d = malloc_nofail(sizeof *d);
	if (gsl_rng_uniform(rng->rng) < 0.5) {
		*d = (struct cdecl_declarator) {
			.type = CDECL_DECL_NULL,
		};
	} else {
		*d = (struct cdecl_declarator) {
			.type = CDECL_DECL_IDENT,
			.u.ident = gen_identifier(rng),
		};
	}

	while (gsl_rng_uniform(rng->rng) < 0.5) {
		p = d;
		d = malloc_nofail(sizeof *d);
		*d = (struct cdecl_declarator) {
			.child = p,
		};

		switch (gsl_rng_uniform_int(rng->rng, limit)) {
		case 0:
			d->type = CDECL_DECL_POINTER;
			d->u.pointer = (struct cdecl_pointer) {
				.qualifiers = gen_qualifiers(rng, true),
			};
			limit = 3;
			break;
		case 1:
			gen_array(rng, d);
			limit = 2;
			break;
		case 2:
			gen_function(rng, d);
			if (p && p->type == CDECL_DECL_POINTER) {
				struct cdecl_pointer *ptr = &p->u.pointer;

				gen_free_declspecs(ptr->qualifiers);
				ptr->qualifiers = gen_qualifiers(rng, false);
			}
			limit = 1;
			break;
		default:
			assert(0);
		}
	}

	return d;
}

struct gen_rng *gen_alloc_rng(const char *seed_str)
{
	unsigned long seed;
	struct gen_rng *rng;
	char *end;

	errno = 0;
	seed = strtoul(seed_str, &end, 0);
	if (*end != 0) {
		fprintf(stderr, "%s: invalid seed\n", seed_str);
		return NULL;
	} else if (errno != 0) {
		fprintf(stderr, "%s: invalid seed: %s\n",
		                seed_str, strerror(errno));
		return NULL;
	}

	rng = malloc_nofail(sizeof *rng);
	rng->rng = gsl_rng_alloc(gsl_rng_mt19937);
	gsl_rng_set(rng->rng, seed);

	return rng;
}

void gen_free_rng(struct gen_rng *rng)
{
	if (rng)
		gsl_rng_free(rng->rng);
	free(rng);
}

static void gen_free_parameters(struct cdecl *x)
{
	struct cdecl *p;

	while (x) {
		p = x->next;

		gen_free_declspecs(x->specifiers);
		gen_free_declarators(x->declarators);
		free(x);

		x = p;
	}
}

void gen_free_declspecs(struct cdecl_declspec *x)
{
	struct cdecl_declspec *p;

	while (x) {
		p = x->next;
		free(x->ident);
		free(x);
		x = p;
	}
}

void gen_free_declarators(struct cdecl_declarator *x)
{
	struct cdecl_declarator *p;

	while (x) {
		p = x->child;

		switch (x->type) {
		case CDECL_DECL_NULL:
			break;
		case CDECL_DECL_IDENT:
			free(x->u.ident);
			break;
		case CDECL_DECL_POINTER:
			gen_free_declspecs(x->u.pointer.qualifiers);
			break;
		case CDECL_DECL_ARRAY:
			free(x->u.array.vla);
			break;
		case CDECL_DECL_FUNCTION:
			gen_free_parameters(x->u.function.parameters);
			break;
		default:
			assert(0);
		}

		free(x);
		x = p;
	}
}