#include	<limits.h>
#include	"global.h"
#include	"list.h"
#include	"source.h"
#include	"lex.h"
#include	"nodes.h"
#include	"conf.h"
#include	"parser.h"
#include	"parparse.h"
#include	"partab.h"
#include	"gen.h"

// The constructor function for ParTable converts the configuration set
// information and transitions into a table form for convenient output.

ParTable::ParTable()
{
	states = ConfSet::NextId;
	symbols = ParRule::RuleId;
	actionTable = (short int **) allocate(ConfSet::NextId*sizeof(int *));
	for (int i = 0; i<ConfSet::NextId; i++) {
	    actionTable[i] = (short int *)
				allocate(ParRule::RuleId*sizeof(short int));
	    for (int j = 0; j<ParRule::RuleId; j++)
		actionTable[i][j] = 0;
	}
	fillTable();
}

void ParTable::fillTable()
{

	// The parse table is constructed by visiting every configuration set
	// and each possible transition for each state.

	listIter<ConfSet *> eachConf(&ConfSet::confSets);
	ConfSet **cs;
	while (cs = eachConf()) {
	    listIter<ParRule *> eachSymbol(&ParRule::ruleSet);
	    ParRule **r;
	    while (r = eachSymbol()) {

		// For each symbol from a configuration set, we can determine if shift
		// or reduce actions are possible.

		ConfSet *shiftDest = (*cs)->destOf(*r);
		LConfList reduceCogs;
		listIter<LConf *> eachCog((*cs)->closure);
		LConf **cg;
		while (cg = eachCog())
		    if ((*cg)->conf->dot->parseItem() == 0)
			// just look out for reductions
			if ((*cg)->conf->rule == ParRule::systemRoot)
			// special consideration for reducing to root nonterm
			    acceptState = (*cs)->id();
			else if ((*cg)->lookAhead.find(*r))
			    reduceCogs.append(*cg);

		// When a shift destination is not found, but only one reduction
		// possibility, the correct action is clear a reduction.

		if (shiftDest == 0 && reduceCogs.length() == 1)
		    reduceIs((*cs)->id(), (*r)->id(), reduceCogs.get());

		// When a shift destination is found, and no reductions are possible,
		// the correct action is clear a shift.

		else if (shiftDest && reduceCogs.length() == 0)
		    shiftIs((*cs)->id(), (*r)->id(), shiftDest->id());
		else {

			// Since productions with a conditional reduction predicate are resolved
			// dynamically, they are seperated from ordinary reductions.

		    LConfList conditionals;
		    listIter<LConf *> eachRed(&reduceCogs);
		    LConf **cog; LConf *toRemove = 0;
		    while (cog = eachRed()) {
			ParNode *nd = (*cog)->conf->dot->condNode();
			if (toRemove) reduceCogs.remove(toRemove);
			toRemove = 0;
			if (nd) {
			    conditionals.append(*cog);
			    toRemove = *cog;
			}
		    }
		    if (toRemove) reduceCogs.remove(toRemove);

			// For whatever reductions are left, the first is chosen to be used,
			// while the reminder are hidden due to the earlier rule.

		    if (reduceCogs.length() > 0) {
			LConf *chosen = reduceCogs.get();
			if (reduceCogs.length()) {
			    error(WARNING,
				  "config set %d: reduce-reduce conflict\n",
				  (*cs)->id());
			    ParNode *prod = chosen->conf->rule->rhs()->leadsTo
						(chosen->conf->dot);
			    fprintf(stderr, "use: %s =", chosen->conf->rule->name());
			    prod->show(chosen->conf->dot, stderr);
			    fprintf(stderr, ", %s\n", (*r)->name());
			}

			// Where there is a shift-reduce conflict, precedence and associativity
			// rules may be used for static resolution.

			if (shiftDest) {
			    ParNode *prod = chosen->conf->rule->rhs()->leadsTo
						(chosen->conf->dot);
			    if (prod->precedence() > (*r)->precedence)
				reduceIs((*cs)->id(), (*r)->id(), chosen);
			    else if (prod->precedence() < (*r)->precedence)
				shiftIs((*cs)->id(), (*r)->id(), shiftDest->id());
			    else if (prod->associativity() == ASSOC_LEFT &&
					(*r)->associativity == ASSOC_LEFT)
				reduceIs((*cs)->id(), (*r)->id(), chosen);
			    else if (prod->associativity() == ASSOC_RIGHT &&
					(*r)->associativity == ASSOC_RIGHT)
				shiftIs((*cs)->id(), (*r)->id(), shiftDest->id());
			    else if (prod->associativity() == ASSOC_NONE &&
					(*r)->associativity == ASSOC_NONE)
				; // error -- no action
			    else {
				error(WARNING, "config set %d: shift-reduce conflict\n",
						(*cs)->id());
				fprintf(stderr, "not using: %s =",
						chosen->conf->rule->name());
				prod->show(chosen->conf->dot, stderr);
				fprintf(stderr, ", %s\n", (*r)->name());
				condShiftIs((*cs)->id(), (*r)->id(),
					    shiftDest->id(), conditionals);
			    }
			} else

				// If a shift move is not possible, the first reduction is chosen after
				// conditional reductions are exhausted.

			    condReduceIs((*cs)->id(), (*r)->id(),
					 chosen, conditionals);
		    } else

			// If a shift move is possible, it is chosen after conditional
			// reductions are exhausted.

			if (shiftDest)
			    condShiftIs((*cs)->id(), (*r)->id(),
					shiftDest->id(), conditionals);
		}
		
	    }
	}
}

// The ReduceInfo class records information pertaining to reductions.
// Ultimately, it provides the non-terminal name when a handle is
// recognised, and the length of the handle.

class ReduceInfo {
	public:
		ReduceInfo() { index = 1; }
		int size() { return index; }
		int makeReduce(ParRule *, ParNode *);
		ParRule *head(int i) { return(reduceTable[i].head); }
		ParNode *prod(int i) { return(reduceTable[i].prod); }

	protected:
		enum { MAXTABLE = 4*1024 };

		struct ReduceRecord {
			ParRule *head;
			ParNode *prod;
		} reduceTable[MAXTABLE];
		int index;
} reduceInfo;

int ReduceInfo::makeReduce(ParRule *r, ParNode *p)
{
	for (int i=1; i<index; i++)
		if (reduceTable[i].head == r && reduceTable[i].prod == p)
			return(i);
	reduceTable[index].head = r;
	reduceTable[index].prod = p;
	return(index++);
}

void ParTable::shiftIs(int state, int sy, int newState)
{
	actionTable[state][sy] = newState;
}

void ParTable::reduceIs(int state, int sy, LConf *c)
{
	ParRule *newSy = c->conf->rule;
	ParNode *prod = newSy->rhs()->leadsTo(c->conf->dot);
	actionTable[state][sy] = - reduceInfo.makeReduce(newSy, prod);
}

// The CondInfo class records information pertaining to conditional
// reductions.  In this case, a configuration possibly has more than one
// predicate.  This sequence of conditionals for the state are
// represented consecutively in condInfo, and is terminated by a zero
// entry.

class CondInfo {
	enum { MAXTABLE = 1024 };

	int condTable[MAXTABLE];
	int _index;
public:
	CondInfo() { _index = 0; }
	int index() { return _index; }
	void add(int x) { condTable[_index++] = x; }
	int val(int x) { return condTable[x]; }
} condInfo;

void ParTable::condShiftIs(int state, int sy, int newState, LConfList &cond)
{
	if (cond.length() == 0) {
	    shiftIs(state, sy, newState);
	    return;
	}

	actionTable[state][sy] = ConfSet::NextId+condInfo.index();
	listIter<LConf *> forEach(&cond);
	LConf **cg;
	while (cg = forEach()) {
		ParRule *newSy = (*cg)->conf->rule;
		ParNode *prod = newSy->rhs()->leadsTo((*cg)->conf->dot);
		condInfo.add
		  (ConfSet::NextId+reduceInfo.makeReduce(newSy, prod));
	}
	condInfo.add(newState);
	condInfo.add(0);
}

void ParTable::condReduceIs(int state, int sy, LConf *c, LConfList &cond)
{
	if (cond.length() == 0) {
	    reduceIs(state, sy, c);
	    return;
	}

	actionTable[state][sy] = ConfSet::NextId+condInfo.index();
	listIter<LConf *> forEach(&cond);
	LConf **cg;
	while (cg = forEach()) {
		ParRule *newSy = (*cg)->conf->rule;
		ParNode *prod = newSy->rhs()->leadsTo((*cg)->conf->dot);
		condInfo.add
		  (ConfSet::NextId+reduceInfo.makeReduce(newSy, prod));
	}
	ParRule *newSy = c->conf->rule;
	ParNode *prod = newSy->rhs()->leadsTo(c->conf->dot);
	condInfo.add(-reduceInfo.makeReduce(newSy, prod));
	condInfo.add(0);
}

// The following are member functions for printing out appropriate code
// fragements in response to the predetermined markers in the template
// file.

void ParTable::pr_nomodsWarning(FILE *ofdes) {
	fprintf(ofdes, "This is a generated file. Modifications are futile.");
}

void ParTable::pr_states(FILE *ofdes)
{
	fprintf(ofdes, "%d", states);
}

void ParTable::pr_symbols(FILE *ofdes)
{
	fprintf(ofdes, "%d", symbols);
}

void ParTable::pr_acceptState(FILE *ofdes)
{
	fprintf(ofdes, "%d", acceptState);
}

void ParTable::pr_tokens(FILE *ofdes)
{
	listIter<ParRule *> forEach(&ParRule::ruleSet);
	ParRule **r;

	// internal _tokens
	fprintf(ofdes, "/* internal _tokens */\n");
	fprintf(ofdes, "#define _ERR_TOKEN (0)\n");
	fprintf(ofdes, "#define _EOF_TOKEN (1)\n");
	
	fprintf(ofdes, "/* tokens defined in the language specs */\n");
	while (r = forEach())
	    if (!(*r)->isNonTerm() && (strcmp((*r)->name(), SYSEOF)))
		fprintf(ofdes, "#define %s_TOKEN (%d)\n",
				(*r)->name(), (*r)->id());
}

// The writer class produces formatted tables.  This is useful for the
// initialisation of large arrays to represent transition functions.

class writer {
	FILE *fdes;
	int col, first;
	char buf[16];
public:
	void print(int);
	void print(char *);
	writer(FILE *);
	~writer();
};

void ParTable::pr_actionTable(FILE *ofdes)
{
	writer v(ofdes);
	for (int i=0; i<ConfSet::NextId; i++) {
		v.print("\n");
		{ writer w(ofdes);
		  for (int j=0; j<ParRule::RuleId; j++)
			w.print(actionTable[i][j]);
		}
	}
}

void ParTable::pr_reduceTable(FILE *ofdes)
{
	fprintf(ofdes, "{\n{ 0, 0, 0, 0}");
	for (int i=1; i<reduceInfo.size(); i++) {
	    int nt = reduceInfo.head(i)->id();
	    fprintf(ofdes, ",\n{ %d, ", nt);
	    if (nt < ParRule::systemRoot->id()) {
		fprintf(ofdes, "%d, %d, ", reduceInfo.prod(i)->parseItems(),
					   reduceInfo.prod(i)->parseItems() -
					   reduceInfo.prod(i)->inhItems());
		if (reduceInfo.prod(i)->actionNode())
		    fprintf(ofdes, "p_%s_%d, ", reduceInfo.head(i)->name(), i);
		else
		    fprintf(ofdes, "0, ");
		if (reduceInfo.prod(i)->condNode())
		    fprintf(ofdes, "c_%s_%d }", reduceInfo.head(i)->name(), i);
		else
		    fprintf(ofdes, "0 }");
	    } else {
		InhMarker *nod = (InhMarker *) reduceInfo.head(i);
		Conf *cf = Conf::confs.find(nod->context);
		ParNode *prod = cf->rule->rhs()->leadsTo(cf->dot);
		fprintf(ofdes, "-1, %d, i_%s, 0 }",
			(prod->parseItems()-prod->inhItems())-
			 (cf->dot->parseItems()-cf->dot->inhItems()),
			reduceInfo.head(i)->name());
	    }
	}
	fprintf(ofdes, "}");
}

void ParTable::pr_condTable(FILE *ofdes)
{
	writer w(ofdes);
	for (int j=0; j<condInfo.index(); j++)
		w.print(condInfo.val(j));
}

void ParTable::pr_attrdef(FILE *ofdes)
{
	listIter<ParRule *> forEach(&ParRule::ruleSet);
	ParRule **r;

#if PLAYING_WITH_FIRE
	// first, write out forward declarations of classes
	// NOTE: the compiler would not know how to cast correctly
	// if real declaration is not available!
	while (r = forEach())
	    if ((*r)->isNonTerm() && (*r)->id() < ParRule::systemRoot->id())
		fprintf(ofdes, "class %sSym;\n", (*r)->name());
	fprintf(ofdes, "\n");
#endif

#if OLD_CODE
	// next, write out class templates
	forEach.init(&ParRule::ruleSet);
	while (r = forEach())
	    // write out attribute definition in terms of C++ class
	    if ((*r)->isNonTerm() && (*r)->id() < ParRule::systemRoot->id()) {
		fprintf(ofdes, "struct %s_attr:public Attr {\n", (*r)->name());
		fprintf(ofdes, "virtual~%s_attr(){}\n", (*r)->name());
		if ((*r)->attributes)
		    fprintf(ofdes, "%s\n\n", (*r)->attributes);
		for (int i=1; i<reduceInfo.size(); i++) {
		    if (reduceInfo.head(i) != (*r))
			continue;
		    if (reduceInfo.prod(i)->actionNode()) {
			// write out member function for evaluating attributes
			fprintf(ofdes, "void action_%d", i);
			pr_signature(reduceInfo.prod(i), 0, ofdes);
			fprintf(ofdes, ";\n");
		    }
		}
		fprintf(ofdes, "};\n\n");
	    }

	fprintf(ofdes, "#line %d \"%s\"\n",
			Copier::position,
			Copier::currentfile);
#endif
}

void ParTable::pr_inhAttrdef(FILE *ofdes)
{
#if OLD_CODE
	if (ParGenParser::inhAttr)
		fprintf(ofdes, "%s\n",
				ParGenParser::inhAttr);
	for (int i=1; i<reduceInfo.size(); i++)
	    if (reduceInfo.head(i)->id() > ParRule::systemRoot->id()) {
		InhMarker *n = (InhMarker *) reduceInfo.head(i);
		fprintf(ofdes, "void i_%s", n->name());
		Conf *cf = Conf::confs.find(n->context);
		ParNode *prod = cf->rule->rhs()->leadsTo(cf->dot);
		pr_signature(prod, cf->dot->parseItem(), ofdes);
		fprintf(ofdes, ";\n");
	    }
	fprintf(ofdes, "#line %d \"%s\"\n",
			Copier::position,
			Copier::currentfile);
#endif
}

void ParTable::pr_code(FILE *ofdes)
{
	// write out the drivers for action routines
	for (int i = 1; i < reduceInfo.size(); ++i) {
		if (reduceInfo.head(i)->id() > ParRule::systemRoot->id())
			continue;
		ParNode *prod = reduceInfo.prod(i);
		if (prod && prod->actionNode()) {
			const char *name = reduceInfo.head(i)->name();

			fprintf(ofdes, "static\nSynSym *p_%s_%d(SynSym **%s) {\n",
				name, i, prod->parseItems() ? "base" : "");

			// extern-declaration
			//fprintf(ofdes, "\textern SynSym *make_%s", name);
			//pr_form_argument(prod, 0, ofdes);
			//fprintf(ofdes, ";\n");

			// call
			// fprintf(ofdes, "\treturn new %sSym", name);
			// pr_argument(prod, 0, ofdes);
			// fprintf(ofdes, ";\n");

			// create parsed symbol
			int tokenCount = 0;
			int symCount = 0;
			countTokens(prod, tokenCount, symCount);
			fprintf(ofdes, "\t// %s =", name);
			pr_rule_rhs(prod, 0, ofdes);
			fprintf(ofdes, " .\n");
			fprintf(ofdes, 
				"\tParsSym *p = new ParsSym(\"%s\", %d);\n", 
				name, symCount);
			pr_argument_add(prod, 0, ofdes);
			fprintf(ofdes, "\treturn p;\n");

			fprintf(ofdes, "}\n\n");
		}
	}

#if OLD_CODE /* replaced */
    int i;
    // write out action code as member function code
    for (i=1; i<reduceInfo.size(); i++) {
	if (reduceInfo.head(i)->id() > ParRule::systemRoot->id())
	    continue;
	char *name = reduceInfo.head(i)->name();
	ParEndNode *n = (ParEndNode *) reduceInfo.prod(i)->actionNode();
	if (n) {
		// write out member function for evaluating attributes
		fprintf(ofdes, "void %s_attr::action_%d", name, i);
		pr_signature(reduceInfo.prod(i), 0, ofdes);
		fprintf(ofdes, "\n{%s\n}\n\n", n->code());
	}
	n = (ParEndNode *) reduceInfo.prod(i)->condNode();
	if (n) {
		// write out member function for evaluating attributes
		fprintf(ofdes, "int _%s_%d", name, i);
		pr_signature(reduceInfo.prod(i), 0, ofdes);
		fprintf(ofdes, "\n{%s\n}\n", n->condCode());
		fprintf(ofdes, "inline int c_%s_%d(Attr **base)\n", name, i);
		fprintf(ofdes, "{  return _%s_%d", name, i);
		pr_argument(reduceInfo.prod(i), 0, ofdes);
		fprintf(ofdes, "; }\n\n");
	}
    }

    // write out the drivers for action routines
    for (i=1; i<reduceInfo.size(); i++)
	if (reduceInfo.head(i)->id() < ParRule::systemRoot->id()) {
	    char *name = reduceInfo.head(i)->name();
	    ParNode *prod = reduceInfo.prod(i);
	    if (prod && prod->actionNode()) {
		fprintf(ofdes, "Attr *p_%s_%d(Attr **base)\n", name, i);
		fprintf(ofdes, "{ %s_attr *x = new %s_attr();\n", name, name);
		fprintf(ofdes, "  x->action_%d", i);
		pr_argument(prod, 0, ofdes);
		fprintf(ofdes, ";\n  return x;\n}\n\n");
	    }
	}
#endif

#if OLD_CODE
    // write out inhertied action code as member function code
    for (i=1; i<reduceInfo.size(); i++)
	if (reduceInfo.head(i)->id() > ParRule::systemRoot->id()) {
	    InhMarker *n = (InhMarker *) reduceInfo.head(i);
 	    fprintf(ofdes, "void Inh_Attr::i_%s", n->name());
	    Conf *cf = Conf::confs.find(n->context);
	    ParNode *prod = cf->rule->rhs()->leadsTo(cf->dot);
	    pr_signature(prod, cf->dot->parseItem(), ofdes);
 	    fprintf(ofdes, "\n{ %s\n}\n\n",
				((ParActionNode *)cf->dot)->code());
	}

    // write out the drivers for inhertied routines
    for (i=1; i<reduceInfo.size(); i++)
	if (reduceInfo.head(i)->id() > ParRule::systemRoot->id()) {
	    InhMarker *n = (InhMarker *) reduceInfo.head(i);
	    char *name;
	    fprintf(ofdes, "Attr *i_%s(Attr **base){\n",
				name = n->name());
	    fprintf(ofdes, "  Inh_Attr *x = new Inh_Attr();\n");
	    fprintf(ofdes, "  x->i_%s", name);
	    Conf *cf = Conf::confs.find(n->context);
	    ParNode *prod = cf->rule->rhs()->leadsTo(cf->dot);
		pr_argument(prod, cf->dot->parseItem(), ofdes);
	    fprintf(ofdes, ";\n}\n\n", name);
	}
#endif

	fprintf(ofdes, "#line %d \"%s\"\n",
			Copier::position,
			Copier::currentfile);
}

void ParTable::pr_argument(ParNode *prod, ParNode *limit, FILE *ofdes) {
	fprintf(ofdes, "(");
	int j;
	for (j = 0, prod = prod->parseItem(); prod != limit; ++j) {
		ParRule *rule = prod->nontermRule();
		const char *name = rule->isNonTerm() ? rule->name() : "Token";
		fprintf(ofdes, "\n\t\t(const %sSym &)base[%d]->cast(%sSym::TheType)",
			name, j+1, name);
		prod = prod->next()->parseItem();
		if (prod != limit)
			fprintf(ofdes, ",");
	}
	fprintf(ofdes, ")");
}

void ParTable::pr_rule_rhs(ParNode *prod, ParNode *limit, FILE *ofdes) {
	int j;
	for (j = 0, prod = prod->parseItem(); prod != limit; ++j) {
		ParRule *rule = prod->nontermRule();
		fprintf(ofdes, " %s", rule->name());
		prod = prod->next()->parseItem();
	}
}

void ParTable::pr_argument_add(ParNode *prod, ParNode *limit, FILE *ofdes) {
	int j;
	for (j = 0, prod = prod->parseItem(); prod != limit; ++j) {
		ParRule *rule = prod->nontermRule();
		const char *name = rule->isNonTerm() ? rule->name() : "Token";
		fprintf(ofdes, "\tp->append(*base[%d]);\n", j+1, name);
		prod = prod->next()->parseItem();
	}
}

void ParTable::pr_form_argument(ParNode *prod, ParNode *limit, FILE *ofdes)
{
	fprintf(ofdes, "(");
	int j;
	for (j = 0, prod = prod->parseItem(); prod != limit; ++j) {
		ParRule *rule = prod->nontermRule();
		fprintf(ofdes, "const %sSym &",
			rule->isNonTerm() ? rule->name() : "Token", j);
		prod = prod->next()->parseItem();
		if (prod != limit)
			fprintf(ofdes, ", ");
	}
	fprintf(ofdes, ")");
}

void ParTable::pr_signature(ParNode *p, ParNode *limit, FILE *ofdes)
{
	fprintf(ofdes, "(");
	p = p->parseItem();
	while (p != limit) {
		ParRule *rule = p->nontermRule();
		fprintf(ofdes,"%sSym *%s",
			   (rule->isNonTerm() ? rule->name() : "Token"),
			   p->alias());
		p = p->next()->parseItem();
		if (p == limit) break;
		fprintf(ofdes, ", ");
	}
	fprintf(ofdes, ")");
}

void ParTable::pr_prelude(FILE *ofdes)
{
	if (ParGenParser::prelude)
		fprintf(ofdes, "%s\n", ParGenParser::prelude);
}

void ParTable::pr_postlude(FILE *ofdes)
{
	if (ParGenParser::postlude)
		fprintf(ofdes, "%s\n", ParGenParser::postlude);
}

void ParTable::countTokens(ParNode *prod, int &tokenCount, int &totalCount) {
	tokenCount = 0;
	totalCount = 0;
	int j;
	for (j = 0, prod = prod->parseItem(); prod != 0; ++j) {
		ParRule *rule = prod->nontermRule();
		totalCount++;
		if (!rule->isNonTerm())
			tokenCount++;
		prod = prod->next()->parseItem();
	}
}

void writer::print(char *s)
{
	if (!first) {
		fprintf(fdes, ", "); col += 2;
	}
	first = FALSE;
	col += strlen(s);
	if (col > 70) {
		col = 0;
		fprintf(fdes, "\n");
	}
	fprintf(fdes, "%s", s);
}

void writer::print(int i)
{
	if (!first) {
		fprintf(fdes, ", "); col += 2;
	}
	first = FALSE;
	sprintf(buf, "%d", i);
	col += strlen(buf);
	if (col > 70) {
		col = 0;
		fprintf(fdes, "\n");
	}
	fprintf(fdes, "%s", buf);
}

writer::writer(FILE *fd)
{
	fdes = fd;
	col = 0;
	first = TRUE;
	fprintf(fdes, "{");
}

writer::~writer()
{
	fprintf(fdes, "}");
}