/*
 * build.c -- functions associated with building syntax diagrams.
 *
 * $Id: build.c,v 1.3 95/06/15 18:07:00 parrt Exp $
 * $Revision: 1.3 $
 *
 * SOFTWARE RIGHTS
 *
 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
 * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
 * company may do whatever they wish with source code distributed with
 * PCCTS or the code generated by PCCTS, including the incorporation of
 * PCCTS, or its output, into commerical software.
 * 
 * We encourage users to develop software with PCCTS.  However, we do ask
 * that credit is given to us for developing PCCTS.  By "credit",
 * we mean that if you incorporate our source code into one of your
 * programs (commercial product, research project, or otherwise) that you
 * acknowledge this fact somewhere in the documentation, research report,
 * etc...  If you like PCCTS and have developed a nice tool with the
 * output, please mention that you developed it using PCCTS.  In
 * addition, we ask that this header remain intact in our source code.
 * As long as these guidelines are kept, we expect to continue enhancing
 * this system and expect to make other tools available as they are
 * completed.
 *
 * ANTLR 1.33
 * Terence Parr
 * Parr Research Corporation
 * with Purdue University and AHPCRC, University of Minnesota
 * 1989-1995
 */
#include <stdio.h>
#ifdef __cplusplus
#ifndef __STDC__
#define __STDC__
#endif
#endif
#include "set.h"
#include "syn.h"
#include "hash.h"
#include "generic.h"
#include "dlgdef.h"

#define SetBlk(g, t, approx) {						   			\
			((Junction *)g.left)->jtype = t;					\
			((Junction *)g.left)->approx = approx;				\
			((Junction *)g.left)->end = (Junction *) g.right;	\
			((Junction *)g.right)->jtype = EndBlk;}

/* Add the parameter string 'parm' to the parms field of a block-type junction
 * g.left points to the sentinel node on a block.  i.e. g.left->p1 points to
 * the actual junction with its jtype == some block-type.
 */
void
#ifdef __STDC__
addParm( Node *p, char *parm )
#else
addParm( p, parm )
Node *p;
char *parm;
#endif
{
	char *q = (char *) malloc( strlen(parm) + 1 );
	require(p!=NULL, "addParm: NULL object\n");
	require(q!=NULL, "addParm: unable to alloc parameter\n");

	strcpy(q, parm);
	if ( p->ntype == nRuleRef )
	{
		((RuleRefNode *)p)->parms = q;
	}
	else if ( p->ntype == nJunction )
	{
		((Junction *)p)->parm = q;	/* only one parameter allowed on subrules */
	}
	else fatal_internal("addParm: invalid node for adding parm");
}

/*
 * Build an action node for the syntax diagram
 *
 * buildAction(ACTION) ::= --o-->ACTION-->o--
 *
 * Where o is a junction node.
 */
Graph
#ifdef __STDC__
buildAction( char *action, int file, int line, int is_predicate )
#else
buildAction( action, file, line, is_predicate )
char *action;
int file;
int line;
int is_predicate;
#endif
{
	Junction *j1, *j2;
	Graph g;
	ActionNode *a;
	require(action!=NULL, "buildAction: invalid action");
	
	j1 = newJunction();
	j2 = newJunction();
	a = newActionNode();
	a->action = (char *) malloc( strlen(action)+1 );
	require(a->action!=NULL, "buildAction: cannot alloc space for action\n");
	strcpy(a->action, action);
	j1->p1 = (Node *) a;
	a->next = (Node *) j2;
	a->is_predicate = is_predicate;
	g.left = (Node *) j1; g.right = (Node *) j2;
	a->file = file;
	a->line = line;
	a->rname = "not filled in";
	return g;
}

/*
 * Build a token node for the syntax diagram
 *
 * buildToken(TOKEN) ::= --o-->TOKEN-->o--
 *
 * Where o is a junction node.
 */
Graph
#ifdef __STDC__
buildToken( char *text )
#else
buildToken( text )
char *text;
#endif
{
	Junction *j1, *j2;
	Graph g;
	TokNode *t;
	require(text!=NULL, "buildToken: invalid token name");
	
	j1 = newJunction();
	j2 = newJunction();
	t = newTokNode();
	t->altstart = CurAltStart;
	if ( *text == '"' ) {t->label=FALSE; t->token = addTexpr( text );}
	else {t->label=TRUE; t->token = addTname( text );}
	j1->p1 = (Node *) t;
	t->next = (Node *) j2;
	g.left = (Node *) j1; g.right = (Node *) j2;
	return g;
}

/*
 * Build a wild-card node for the syntax diagram
 *
 * buildToken(TOKEN) ::= --o-->'.'-->o--
 *
 * Where o is a junction node.
 */
Graph
#ifdef __STDC__
buildWildCard( char *text )
#else
buildWildCard( text )
char *text;
#endif
{
	Junction *j1, *j2;
	Graph g;
	TokNode *t;
	TCnode *w;
	TermEntry *p;
	require(text!=NULL, "buildWildCard: invalid token name");
	
	j1 = newJunction();
	j2 = newJunction();
	t = newTokNode();

	/* If the ref a wild card, make a token class for it */
	if ( Tnum(WildCardString) == 0 )
	{
		w = newTCnode;
	  	w->tok = addTname( WildCardString );
		set_orel(w->tok, &imag_tokens);
		set_orel(w->tok, &tokclasses);
		WildCardToken = w->tok;
		require((p=(TermEntry *)hash_get(Tname, WildCardString)) != NULL,
				"hash table mechanism is broken");
		p->classname = 1;	/* entry is class name, not token */
		p->tclass = w;		/* save ptr to this tclass def */
		list_add(&tclasses, (char *)w);
	}
	else {
		p=(TermEntry *)hash_get(Tname, WildCardString);
		require( p!= NULL, "hash table mechanism is broken");
		w = p->tclass;
	}

	t->token = w->tok;
	t->wild_card = 1;
	t->tclass = w;

	t->altstart = CurAltStart;
	j1->p1 = (Node *) t;
	t->next = (Node *) j2;
	g.left = (Node *) j1; g.right = (Node *) j2;
	return g;
}

void
#ifdef __STDC__
setUpperRange(TokNode *t, char *text)
#else
setUpperRange(t, text)
TokNode *t;
char *text;
#endif
{
	require(t!=NULL, "setUpperRange: NULL token node");
	require(text!=NULL, "setUpperRange: NULL token string");

	if ( *text == '"' ) {t->upper_range = addTexpr( text );}
	else {t->upper_range = addTname( text );}
}

/*
 * Build a rule reference node of the syntax diagram
 *
 * buildRuleRef(RULE) ::= --o-->RULE-->o--
 *
 * Where o is a junction node.
 *
 * If rule 'text' has been defined already, don't alloc new space to store string.
 * Set r->text to point to old copy in string table.
 */
Graph
#ifdef __STDC__
buildRuleRef( char *text )
#else
buildRuleRef( text )
char *text;
#endif
{
	Junction *j1, *j2;
	Graph g;
	RuleRefNode *r;
	RuleEntry *p;
	require(text!=NULL, "buildRuleRef: invalid rule name");
	
	j1 = newJunction();
	j2 = newJunction();
	r = newRNode();
	r->altstart = CurAltStart;
	r->assign = NULL;
	if ( (p=(RuleEntry *)hash_get(Rname, text)) != NULL ) r->text = p->str;
	else r->text = mystrdup( text );
	j1->p1  = (Node *) r;
	r->next = (Node *) j2;
	g.left = (Node *) j1; g.right = (Node *) j2;
	return g;
}

/*
 * Or two subgraphs into one graph via:
 *
 * Or(G1, G2) ::= --o-G1-o--
 *                  |    ^
 *					v    |
 *                  o-G2-o
 *
 * Set the altnum of junction starting G2 to 1 + altnum of junction starting G1.
 * If, however, the G1 altnum is 0, make it 1 and then
 * make G2 altnum = G1 altnum + 1.
 */
Graph
#ifdef __STDC__
Or( Graph g1, Graph g2 )
#else
Or( g1, g2 )
Graph g1;
Graph g2;
#endif
{
	Graph g;
	require(g1.left != NULL, "Or: invalid graph");
	require(g2.left != NULL && g2.right != NULL, "Or: invalid graph");

	((Junction *)g1.left)->p2 = g2.left;
	((Junction *)g2.right)->p1 = g1.right;
	/* set altnums */
	if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
	((Junction *)g2.left)->altnum = ((Junction *)g1.left)->altnum + 1;
	g.left = g2.left;
	g.right = g1.right;
	return g;
}

/*
 * Catenate two subgraphs
 *
 * Cat(G1, G2) ::= --o-G1-o-->o-G2-o--
 * Cat(NULL,G2)::= --o-G2-o--
 * Cat(G1,NULL)::= --o-G1-o--
 */
Graph
#ifdef __STDC__
Cat( Graph g1, Graph g2 )
#else
Cat( g1, g2 )
Graph g1;
Graph g2;
#endif
{
	Graph g;
	
	if ( g1.left == NULL && g1.right == NULL ) return g2;
	if ( g2.left == NULL && g2.right == NULL ) return g1;
	((Junction *)g1.right)->p1 = g2.left;
	g.left = g1.left;
	g.right = g2.right;
	return g;
}

/*
 * Make a subgraph an optional block
 *
 * makeOpt(G) ::= --o-->o-G-o-->o--
 *                      | 	    ^
 *						v  	    |
 *					    o-------o
 *
 * Note that this constructs {A|B|...|Z} as if (A|B|...|Z|) was found.
 *
 * The node on the far right is added so that every block owns its own
 * EndBlk node.
 */
Graph
#ifdef __STDC__
makeOpt( Graph g1, int approx )
#else
makeOpt( g1, approx )
Graph g1;
int approx;
#endif
{
	Junction *j1,*j2,*p;
	Graph g;
	require(g1.left != NULL && g1.right != NULL, "makeOpt: invalid graph");

	j1 = newJunction();
	j2 = newJunction();
	((Junction *)g1.right)->p1 = (Node *) j2;	/* add node to G at end */
	g = emptyAlt();
	if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
	((Junction *)g.left)->altnum = ((Junction *)g1.left)->altnum + 1;
	for(p=(Junction *)g1.left; p->p2!=NULL; p=(Junction *)p->p2)
		{;}										/* find last alt */
	p->p2 = g.left;								/* add optional alternative */
	((Junction *)g.right)->p1 = (Node *)j2;		/* opt alt points to EndBlk */
	g1.right = (Node *)j2;
	SetBlk(g1, aOptBlk, approx);
	j1->p1 = g1.left;							/* add generic node in front */
	g.left = (Node *) j1;
	g.right = g1.right;

	return g;
}

/*
 * Make a graph into subblock
 *
 * makeBlk(G) ::= --o-->o-G-o-->o--
 *
 * The node on the far right is added so that every block owns its own
 * EndBlk node.
 */
Graph
#ifdef __STDC__
makeBlk( Graph g1, int approx )
#else
makeBlk( g1, approx )
Graph g1;
int approx;
#endif
{
	Junction *j,*j2;
	Graph g;
	require(g1.left != NULL && g1.right != NULL, "makeBlk: invalid graph");

	j = newJunction();
	j2 = newJunction();
	((Junction *)g1.right)->p1 = (Node *) j2;	/* add node to G at end */
	g1.right = (Node *)j2;
	SetBlk(g1, aSubBlk, approx);
	j->p1 = g1.left;							/* add node in front */
	g.left = (Node *) j;
	g.right = g1.right;

	return g;
}

/*
 * Make a subgraph into a loop (closure) block -- (...)*
 *
 * makeLoop(G) ::=       |---|
 *					     v   |
 *			   --o-->o-->o-G-o-->o--
 *                   |           ^
 *                   v           |
 *					 o-----------o
 *
 * After making loop, always place generic node out front.  It becomes
 * the start of enclosing block.  The aLoopBlk is the target of the loop.
 *
 * Loop blks have TWO EndBlk nodes--the far right and the node that loops back
 * to the aLoopBlk node.  Node with which we can branch past loop == aLoopBegin and
 * one which is loop target == aLoopBlk.
 * The branch-past (initial) aLoopBegin node has end
 * pointing to the last EndBlk node.  The loop-target node has end==NULL.
 *
 * Loop blocks have a set of locks (from 1..CLL_k) on the aLoopBlk node.
 */
Graph
#ifdef __STDC__
makeLoop( Graph g1, int approx )
#else
makeLoop( g1, approx )
Graph g1;
int approx;
#endif
{
	Junction *back, *front, *begin;
	Graph g;
	require(g1.left != NULL && g1.right != NULL, "makeLoop: invalid graph");

	back = newJunction();
	front = newJunction();
	begin = newJunction();
	g = emptyAlt();
	((Junction *)g1.right)->p2 = g1.left;		/* add loop branch to G */
	((Junction *)g1.right)->p1 = (Node *) back;	/* add node to G at end */
	((Junction *)g1.right)->jtype = EndBlk;		/* mark 1st EndBlk node */
	((Junction *)g1.left)->jtype = aLoopBlk;	/* mark 2nd aLoopBlk node */
	((Junction *)g1.left)->end = (Junction *) g1.right;
	((Junction *)g1.left)->lock = makelocks();
	((Junction *)g1.left)->pred_lock = makelocks();
	g1.right = (Node *) back;
	begin->p1 = (Node *) g1.left;
	g1.left = (Node *) begin;
	begin->p2 = (Node *) g.left;				/* make bypass arc */
	((Junction *)g.right)->p1 = (Node *) back;
	SetBlk(g1, aLoopBegin, approx);
	front->p1 = g1.left;						/* add node to front */
	g1.left = (Node *) front;

	return g1;
}

/*
 * Make a subgraph into a plus block -- (...)+ -- 1 or more times
 *
 * makePlus(G) ::=	 |---|
 *					 v   |
 *			   --o-->o-G-o-->o--
 *
 * After making loop, always place generic node out front.  It becomes
 * the start of enclosing block.  The aPlusBlk is the target of the loop.
 *
 * Plus blks have TWO EndBlk nodes--the far right and the node that loops back
 * to the aPlusBlk node.
 *
 * Plus blocks have a set of locks (from 1..CLL_k) on the aPlusBlk node.
 */
Graph
#ifdef __STDC__
makePlus( Graph g1, int approx )
#else
makePlus( g1, approx )
Graph g1;
int approx;
#endif
{
	int has_empty_alt_already = 0;
	Graph g;
	Junction *j2, *j3, *first_alt;
	Junction *last_alt, *p;
	require(g1.left != NULL && g1.right != NULL, "makePlus: invalid graph");

	first_alt = (Junction *)g1.left;
	j2 = newJunction();
	j3 = newJunction();
	if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
	((Junction *)g1.right)->p2 = g1.left;		/* add loop branch to G */
	((Junction *)g1.right)->p1 = (Node *) j2;	/* add node to G at end */
	((Junction *)g1.right)->jtype = EndBlk;		/* mark 1st EndBlk node */
	g1.right = (Node *) j2;
	SetBlk(g1, aPlusBlk, approx);
	((Junction *)g1.left)->lock = makelocks();
	((Junction *)g1.left)->pred_lock = makelocks();
	j3->p1 = g1.left;							/* add node to front */
	g1.left = (Node *) j3;

	/* add an optional branch which is the "exit" branch of loop */
	/* FIRST, check to ensure that there does not already exist
	 * an optional path.
	 */
	/* find last alt */
	for(p=first_alt; p!=NULL; p=(Junction *)p->p2)
	{
		if ( p->p1->ntype == nJunction &&
			 p->p1!=NULL &&
			 ((Junction *)p->p1)->jtype==Generic &&
			 ((Junction *)p->p1)->p1!=NULL &&
			 ((Junction *)((Junction *)p->p1)->p1)->jtype==EndBlk )
		{
			has_empty_alt_already = 1;
		}
		last_alt = p;
	}
	if ( !has_empty_alt_already )
	{
		require(last_alt!=NULL, "last_alt==NULL; bad (..)+");
		g = emptyAlt();
		last_alt->p2 = g.left;
		((Junction *)g.right)->p1 = (Node *) j2;

		/* make sure lookahead computation ignores this alt for
		* FIRST("(..)+"); but it's still used for computing the FIRST
		* of each alternative.
		*/
		((Junction *)g.left)->ignore = 1;
	}

	return g1;
}

/*
 * Return an optional path:  --o-->o--
 */
Graph
#ifdef __STDC__
emptyAlt( void )
#else
emptyAlt( )
#endif
{
	Junction *j1, *j2;
	Graph g;

	j1 = newJunction();
	j2 = newJunction();
	j1->p1 = (Node *) j2;
	g.left = (Node *) j1;
	g.right = (Node *) j2;
	
	return g;
}

/* N o d e  A l l o c a t i o n */

TokNode *
#ifdef __STDC__
newTokNode( void )
#else
newTokNode( )
#endif
{
	static TokNode *FreeList = NULL;
	TokNode *p, *newblk;

	if ( FreeList == NULL )
	{
		newblk = (TokNode *)calloc(TokenBlockAllocSize, sizeof(TokNode));
		if ( newblk == NULL )
			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
		for (p=newblk; p<&(newblk[TokenBlockAllocSize]); p++)
		{
			p->next = (Node *)FreeList;	/* add all new token nodes to FreeList */
			FreeList = p;
		}
	}
	p = FreeList;
	FreeList = (TokNode *)FreeList->next;/* remove a TokNode node */
	p->next = NULL;						/* NULL the ptr we used */

	p->ntype = nToken;
	p->rname = CurRule;
	p->file = CurFile;
	p->line = zzline;
	p->altstart = NULL;

	return p;
}

RuleRefNode *
#ifdef __STDC__
newRNode( void )
#else
newRNode( )
#endif
{
	static RuleRefNode *FreeList = NULL;
	RuleRefNode *p, *newblk;

	if ( FreeList == NULL )
	{
		newblk = (RuleRefNode *)calloc(RRefBlockAllocSize, sizeof(RuleRefNode));
		if ( newblk == NULL )
			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
		for (p=newblk; p<&(newblk[RRefBlockAllocSize]); p++)
		{
			p->next = (Node *)FreeList;	/* add all new rref nodes to FreeList */
			FreeList = p;
		}
	}
	p = FreeList;
	FreeList = (RuleRefNode *)FreeList->next;/* remove a Junction node */
	p->next = NULL;						/* NULL the ptr we used */

	p->ntype = nRuleRef;
	p->rname = CurRule;
	p->file = CurFile;
	p->line = zzline;
	p->astnode = ASTinclude;
	p->altstart = NULL;
	
	return p;
}

Junction *
#ifdef __STDC__
newJunction( void )
#else
newJunction( )
#endif
{
	static Junction *FreeList = NULL;
	Junction *p, *newblk;

	if ( FreeList == NULL )
	{
		newblk = (Junction *)calloc(JunctionBlockAllocSize, sizeof(Junction));
		if ( newblk == NULL )
			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
		for (p=newblk; p<&(newblk[JunctionBlockAllocSize]); p++)
		{
			p->p1 = (Node *)FreeList;	/* add all new Junction nodes to FreeList */
			FreeList = p;
		}
	}
	p = FreeList;
	FreeList = (Junction *)FreeList->p1;/* remove a Junction node */
	p->p1 = NULL;						/* NULL the ptr we used */

	p->ntype = nJunction;	p->visited = 0;
	p->jtype = Generic;
	p->rname = CurRule;
	p->file = CurFile;
	p->line = zzline;
	p->exception_label = NULL;
	p->fset = (set *) calloc(CLL_k+1, sizeof(set));
	require(p->fset!=NULL, "cannot allocate fset in newJunction");

	return p;
}

ActionNode *
#ifdef __STDC__
newActionNode( void )
#else
newActionNode( )
#endif
{
	static ActionNode *FreeList = NULL;
	ActionNode *p, *newblk;

	if ( FreeList == NULL )
	{
		newblk = (ActionNode *)calloc(ActionBlockAllocSize, sizeof(ActionNode));
		if ( newblk == NULL )
			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
		for (p=newblk; p<&(newblk[ActionBlockAllocSize]); p++)
		{
			p->next = (Node *)FreeList;	/* add all new Action nodes to FreeList */
			FreeList = p;
		}
	}
	p = FreeList;
	FreeList = (ActionNode *)FreeList->next;/* remove an Action node */
	p->ntype = nAction;
	p->next = NULL;						/* NULL the ptr we used */
	p->done = 0;
	p->pred_fail = NULL;
	p->guardpred = NULL;

	return p;
}

/*
 * allocate the array of locks (1..CLL_k) used to inhibit infinite recursion.
 * Infinite recursion can occur in (..)* blocks, FIRST calcs and FOLLOW calcs.
 * Therefore, we need locks on aLoopBlk, RuleBlk, EndRule nodes.
 *
 * if ( lock[k]==TRUE ) then we have been here before looking for k tokens
 * of lookahead.
 */
char *
#ifdef __STDC__
makelocks( void )
#else
makelocks( )
#endif
{
	char *p = (char *) calloc(CLL_k+1, sizeof(char));
	require(p!=NULL, "cannot allocate lock array");
	
	return p;
}