/* Parser generator */

/* For a description, see the comments at end of this file */

#include "Python.h"

#include "pgenheaders.h"

#include "token.h"

#include "node.h"

#include "grammar.h"

#include "metagrammar.h"

#include "pgen.h"

extern int Py_DebugFlag;

extern int Py_IgnoreEnvironmentFlag; /* needed by Py_GETENV */

/* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */

typedef struct _nfaarc {

	int	ar_label;

	int	ar_arrow;

} nfaarc;

typedef struct _nfastate {

	int	st_narcs;

	nfaarc	*st_arc;

} nfastate;

typedef struct _nfa {

	int		nf_type;

	char		*nf_name;

	int		nf_nstates;

	nfastate	*nf_state;

	int		nf_start, nf_finish;

} nfa;

/* Forward */

static void compile_rhs(labellist *ll,

			nfa *nf, node *n, int *pa, int *pb);

static void compile_alt(labellist *ll,

			nfa *nf, node *n, int *pa, int *pb);

static void compile_item(labellist *ll,

			 nfa *nf, node *n, int *pa, int *pb);

static void compile_atom(labellist *ll,

			 nfa *nf, node *n, int *pa, int *pb);

static int

addnfastate(nfa *nf)

{

	nfastate *st;

	nf->nf_state = (nfastate *)PyObject_REALLOC(nf->nf_state, 

                                    sizeof(nfastate) * (nf->nf_nstates + 1));

	if (nf->nf_state == NULL)

		Py_FatalError("out of mem");

	st = &nf->nf_state[nf->nf_nstates++];

	st->st_narcs = 0;

	st->st_arc = NULL;

	return st - nf->nf_state;

}

static void

addnfaarc(nfa *nf, int from, int to, int lbl)

{

	nfastate *st;

	nfaarc *ar;

	st = &nf->nf_state[from];

	st->st_arc = (nfaarc *)PyObject_REALLOC(st->st_arc,

				      sizeof(nfaarc) * (st->st_narcs + 1));

	if (st->st_arc == NULL)

		Py_FatalError("out of mem");

	ar = &st->st_arc[st->st_narcs++];

	ar->ar_label = lbl;

	ar->ar_arrow = to;

}

static nfa *

newnfa(char *name)

{

	nfa *nf;

	static int type = NT_OFFSET; /* All types will be disjunct */

	nf = (nfa *)PyObject_MALLOC(sizeof(nfa));

	if (nf == NULL)

		Py_FatalError("no mem for new nfa");

	nf->nf_type = type++;

	nf->nf_name = name; /* XXX strdup(name) ??? */

	nf->nf_nstates = 0;

	nf->nf_state = NULL;

	nf->nf_start = nf->nf_finish = -1;

	return nf;

}

typedef struct _nfagrammar {

	int		gr_nnfas;

	nfa		**gr_nfa;

	labellist	gr_ll;

} nfagrammar;

/* Forward */

static void compile_rule(nfagrammar *gr, node *n);

static nfagrammar *

newnfagrammar(void)

{

	nfagrammar *gr;

	gr = (nfagrammar *)PyObject_MALLOC(sizeof(nfagrammar));

	if (gr == NULL)

		Py_FatalError("no mem for new nfa grammar");

	gr->gr_nnfas = 0;

	gr->gr_nfa = NULL;

	gr->gr_ll.ll_nlabels = 0;

	gr->gr_ll.ll_label = NULL;

	addlabel(&gr->gr_ll, ENDMARKER, "EMPTY");

	return gr;

}

static nfa *

addnfa(nfagrammar *gr, char *name)

{

	nfa *nf;

	nf = newnfa(name);

	gr->gr_nfa = (nfa **)PyObject_REALLOC(gr->gr_nfa,

				      sizeof(nfa*) * (gr->gr_nnfas + 1));

	if (gr->gr_nfa == NULL)

		Py_FatalError("out of mem");

	gr->gr_nfa[gr->gr_nnfas++] = nf;

	addlabel(&gr->gr_ll, NAME, nf->nf_name);

	return nf;

}

#ifdef Py_DEBUG

static char REQNFMT[] = "metacompile: less than %d children\n";

#define REQN(i, count) \

 	if (i < count) { \

		fprintf(stderr, REQNFMT, count); \

		Py_FatalError("REQN"); \

	} else

#else

#define REQN(i, count)	/* empty */

#endif

static nfagrammar *

metacompile(node *n)

{

	nfagrammar *gr;

	int i;

	if (Py_DebugFlag)

		printf("Compiling (meta-) parse tree into NFA grammar\n");

	gr = newnfagrammar();

	REQ(n, MSTART);

	i = n->n_nchildren - 1; /* Last child is ENDMARKER */

	n = n->n_child;

	for (; --i >= 0; n++) {

		if (n->n_type != NEWLINE)

			compile_rule(gr, n);

	}

	return gr;

}

static void

compile_rule(nfagrammar *gr, node *n)

{

	nfa *nf;

	REQ(n, RULE);

	REQN(n->n_nchildren, 4);

	n = n->n_child;

	REQ(n, NAME);

	nf = addnfa(gr, n->n_str);

	n++;

	REQ(n, COLON);

	n++;

	REQ(n, RHS);

	compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);

	n++;

	REQ(n, NEWLINE);

}

static void

compile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb)

{

	int i;

	int a, b;

	REQ(n, RHS);

	i = n->n_nchildren;

	REQN(i, 1);

	n = n->n_child;

	REQ(n, ALT);

	compile_alt(ll, nf, n, pa, pb);

	if (--i <= 0)

		return;

	n++;

	a = *pa;

	b = *pb;

	*pa = addnfastate(nf);

	*pb = addnfastate(nf);

	addnfaarc(nf, *pa, a, EMPTY);

	addnfaarc(nf, b, *pb, EMPTY);

	for (; --i >= 0; n++) {

		REQ(n, VBAR);

		REQN(i, 1);

		--i;

		n++;

		REQ(n, ALT);

		compile_alt(ll, nf, n, &a, &b);

		addnfaarc(nf, *pa, a, EMPTY);

		addnfaarc(nf, b, *pb, EMPTY);

	}

}

static void

compile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb)

{

	int i;

	int a, b;

	REQ(n, ALT);

	i = n->n_nchildren;

	REQN(i, 1);

	n = n->n_child;

	REQ(n, ITEM);

	compile_item(ll, nf, n, pa, pb);

	--i;

	n++;

	for (; --i >= 0; n++) {

		REQ(n, ITEM);

		compile_item(ll, nf, n, &a, &b);

		addnfaarc(nf, *pb, a, EMPTY);

		*pb = b;

	}

}

static void

compile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb)

{

	int i;

	int a, b;

	REQ(n, ITEM);

	i = n->n_nchildren;

	REQN(i, 1);

	n = n->n_child;

	if (n->n_type == LSQB) {

		REQN(i, 3);

		n++;

		REQ(n, RHS);

		*pa = addnfastate(nf);

		*pb = addnfastate(nf);

		addnfaarc(nf, *pa, *pb, EMPTY);

		compile_rhs(ll, nf, n, &a, &b);

		addnfaarc(nf, *pa, a, EMPTY);

		addnfaarc(nf, b, *pb, EMPTY);

		REQN(i, 1);

		n++;

		REQ(n, RSQB);

	}

	else {

		compile_atom(ll, nf, n, pa, pb);

		if (--i <= 0)

			return;

		n++;

		addnfaarc(nf, *pb, *pa, EMPTY);

		if (n->n_type == STAR)

			*pb = *pa;

		else

			REQ(n, PLUS);

	}

}

static void

compile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb)

{

	int i;

	REQ(n, ATOM);

	i = n->n_nchildren;

	REQN(i, 1);

	n = n->n_child;

	if (n->n_type == LPAR) {

		REQN(i, 3);

		n++;

		REQ(n, RHS);

		compile_rhs(ll, nf, n, pa, pb);

		n++;

		REQ(n, RPAR);

	}

	else if (n->n_type == NAME || n->n_type == STRING) {

		*pa = addnfastate(nf);

		*pb = addnfastate(nf);

		addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));

	}

	else

		REQ(n, NAME);

}

static void

dumpstate(labellist *ll, nfa *nf, int istate)

{

	nfastate *st;

	int i;

	nfaarc *ar;

	printf("%c%2d%c",

		istate == nf->nf_start ? '*' : ' ',

		istate,

		istate == nf->nf_finish ? '.' : ' ');

	st = &nf->nf_state[istate];

	ar = st->st_arc;

	for (i = 0; i < st->st_narcs; i++) {

		if (i > 0)

			printf("\n    ");

		printf("-> %2d  %s", ar->ar_arrow,

			PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));

		ar++;

	}

	printf("\n");

}

static void

dumpnfa(labellist *ll, nfa *nf)

{

	int i;

	printf("NFA '%s' has %d states; start %d, finish %d\n",

		nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);

	for (i = 0; i < nf->nf_nstates; i++)

		dumpstate(ll, nf, i);

}

/* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */

static void

addclosure(bitset ss, nfa *nf, int istate)

{

	if (addbit(ss, istate)) {

		nfastate *st = &nf->nf_state[istate];

		nfaarc *ar = st->st_arc;

		int i;

		for (i = st->st_narcs; --i >= 0; ) {

			if (ar->ar_label == EMPTY)

				addclosure(ss, nf, ar->ar_arrow);

			ar++;

		}

	}

}

typedef struct _ss_arc {

	bitset	sa_bitset;

	int	sa_arrow;

	int	sa_label;

} ss_arc;

typedef struct _ss_state {

	bitset	ss_ss;

	int	ss_narcs;

	struct _ss_arc	*ss_arc;

	int	ss_deleted;

	int	ss_finish;

	int	ss_rename;

} ss_state;

typedef struct _ss_dfa {

	int	sd_nstates;

	ss_state *sd_state;

} ss_dfa;

/* Forward */

static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits,

		       labellist *ll, char *msg);

static void simplify(int xx_nstates, ss_state *xx_state);

static void convert(dfa *d, int xx_nstates, ss_state *xx_state);

static void

makedfa(nfagrammar *gr, nfa *nf, dfa *d)

{

	int nbits = nf->nf_nstates;

	bitset ss;

	int xx_nstates;

	ss_state *xx_state, *yy;

	ss_arc *zz;

	int istate, jstate, iarc, jarc, ibit;

	nfastate *st;

	nfaarc *ar;

	ss = newbitset(nbits);

	addclosure(ss, nf, nf->nf_start);

	xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state));

	if (xx_state == NULL)

		Py_FatalError("no mem for xx_state in makedfa");

	xx_nstates = 1;

	yy = &xx_state[0];

	yy->ss_ss = ss;

	yy->ss_narcs = 0;

	yy->ss_arc = NULL;

	yy->ss_deleted = 0;

	yy->ss_finish = testbit(ss, nf->nf_finish);

	if (yy->ss_finish)

		printf("Error: nonterminal '%s' may produce empty.\n",

			nf->nf_name);

	/* This algorithm is from a book written before

	   the invention of structured programming... */

	/* For each unmarked state... */

	for (istate = 0; istate < xx_nstates; ++istate) {

		size_t size;

		yy = &xx_state[istate];

		ss = yy->ss_ss;

		/* For all its states... */

		for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {

			if (!testbit(ss, ibit))

				continue;

			st = &nf->nf_state[ibit];

			/* For all non-empty arcs from this state... */

			for (iarc = 0; iarc < st->st_narcs; iarc++) {

				ar = &st->st_arc[iarc];

				if (ar->ar_label == EMPTY)

					continue;

				/* Look up in list of arcs from this state */

				for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {

					zz = &yy->ss_arc[jarc];

					if (ar->ar_label == zz->sa_label)

						goto found;

				}

				/* Add new arc for this state */

				size = sizeof(ss_arc) * (yy->ss_narcs + 1);

				yy->ss_arc = (ss_arc *)PyObject_REALLOC(

                                                            yy->ss_arc, size);

				if (yy->ss_arc == NULL)

					Py_FatalError("out of mem");

				zz = &yy->ss_arc[yy->ss_narcs++];

				zz->sa_label = ar->ar_label;

				zz->sa_bitset = newbitset(nbits);

				zz->sa_arrow = -1;

			 found:	;

				/* Add destination */

				addclosure(zz->sa_bitset, nf, ar->ar_arrow);

			}

		}

		/* Now look up all the arrow states */

		for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {

			zz = &xx_state[istate].ss_arc[jarc];

			for (jstate = 0; jstate < xx_nstates; jstate++) {

				if (samebitset(zz->sa_bitset,

					xx_state[jstate].ss_ss, nbits)) {

					zz->sa_arrow = jstate;

					goto done;

				}

			}

			size = sizeof(ss_state) * (xx_nstates + 1);

			xx_state = (ss_state *)PyObject_REALLOC(xx_state, 

                                                                    size);

			if (xx_state == NULL)

				Py_FatalError("out of mem");

			zz->sa_arrow = xx_nstates;

			yy = &xx_state[xx_nstates++];

			yy->ss_ss = zz->sa_bitset;

			yy->ss_narcs = 0;

			yy->ss_arc = NULL;

			yy->ss_deleted = 0;

			yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);

		 done:	;

		}

	}

	if (Py_DebugFlag)

		printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,

						"before minimizing");

	simplify(xx_nstates, xx_state);

	if (Py_DebugFlag)

		printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,

						"after minimizing");

	convert(d, xx_nstates, xx_state);

	/* XXX cleanup */

	PyObject_FREE(xx_state);

}

static void

printssdfa(int xx_nstates, ss_state *xx_state, int nbits,

	   labellist *ll, char *msg)

{

	int i, ibit, iarc;

	ss_state *yy;

	ss_arc *zz;

	printf("Subset DFA %s\n", msg);

	for (i = 0; i < xx_nstates; i++) {

		yy = &xx_state[i];

		if (yy->ss_deleted)

			continue;

		printf(" Subset %d", i);

		if (yy->ss_finish)

			printf(" (finish)");

		printf(" { ");

		for (ibit = 0; ibit < nbits; ibit++) {

			if (testbit(yy->ss_ss, ibit))

				printf("%d ", ibit);

		}

		printf("}\n");

		for (iarc = 0; iarc < yy->ss_narcs; iarc++) {

			zz = &yy->ss_arc[iarc];

			printf("  Arc to state %d, label %s\n",

				zz->sa_arrow,

				PyGrammar_LabelRepr(

					&ll->ll_label[zz->sa_label]));

		}

	}

}

/* PART THREE -- SIMPLIFY DFA */

/* Simplify the DFA by repeatedly eliminating states that are