/*
 * pred.c -- source for predicate detection, manipulation
 *
 * $Id: pred.c,v 1.6 95/09/26 12:58:44 parrt Exp $
 * $Revision: 1.6 $
 *
 * 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"
#include <ctype.h>

#ifdef __STDC__
static void complete_context_sets(RuleRefNode *, Predicate *);
static void complete_context_trees(RuleRefNode *, Predicate *);
#else
static void complete_context_sets();
static void complete_context_trees();
#endif

static Predicate pred_empty = {
	NULL,NULL,NULL,NULL,NULL,NULL,0,
	{set_init,set_init},set_init
};

char *PRED_AND_LIST = "AND";
char *PRED_OR_LIST = "OR";

/*
 * In C mode, return the largest constant integer found as the
 * sole argument to LATEXT(i).
 *
 * In C++ mode, return the largest constant integer found as the
 * sole argument to LT(i) given that the char before is nonalpha.
 */
static int
#ifdef __STDC__
predicateLookaheadDepth(ActionNode *a)
#else
predicateLookaheadDepth(a)
ActionNode *a;
#endif
{
	int max_k=0;

	if ( GenCC )
	{
		/* scan for LT(i) */
		int k = 0;
		char *p = a->action;
		while ( p!=NULL )
		{
			p = strstr(p, "LT(");
			if ( p!=NULL )
			{
				if ( p>=a->action && !isalpha(*(p-1)) )
				{
					k = atoi(p+strlen("LT("));
					if ( k>max_k ) max_k=k;
				}
				p += strlen("LT(");
			}
		}
	}
	else {
		/* scan for LATEXT(i) */
		int k = 0;
		char *p = a->action;
		while ( p!=NULL )
		{
			p = strstr(p, "LATEXT(");
			if ( p!=NULL )
			{
				p += strlen("LATEXT(");
				k = atoi(p);
				if ( k>max_k ) max_k=k;
			}
		}
	}

	if ( max_k==0 )
	{
		if ( !a->frmwarned )
		{
			a->frmwarned = 1;
			warnFL(eMsg1("predicate: %s missing, bad, or with i=0; assuming i=1",
						 GenCC?"LT(i)":"LATEXT(i)"),
				   FileStr[a->file], a->line);
		}
		max_k = 1;
	}

	return max_k;
}

/* Find all predicates in a block of alternatives.  DO NOT find predicates
 * behind the block because that predicate could depend on things set in
 * one of the nonoptional blocks
 */
Predicate *
#ifdef __STDC__
find_in_aSubBlk( Junction *alt )
#else
find_in_aSubBlk( alt )
Junction *alt;
#endif
{
	Predicate *a, *head=NULL, *tail, *root=NULL;
	Junction *p = alt;

	for (; p!=NULL; p=(Junction *)p->p2)
	{
		/* ignore empty alts */
		if ( p->p1->ntype != nJunction ||
			 ((Junction *)p->p1)->jtype != EndBlk )
		{
			a = find_predicates(p->p1);	/* get preds for this alt */
			if ( a==NULL ) continue;

			/* make an OR list of predicates */
			if ( head==NULL )
			{
				root = new_pred();
				root->expr = PRED_OR_LIST;
				head = tail = a;
				root->down = head;
			}
			else {
				tail->right = a;
				a->left = tail;
				a->up = tail->up;
				tail = a;
			}
		}
	}

	/* if just one pred, remove OR root */
	if ( root!=NULL && root->down->right == NULL )
	{
		Predicate *d = root->down;
		free(root);
		return d;
	}

	return root;
}

Predicate *
#ifdef __STDC__
find_in_aOptBlk( Junction *alt )
#else
find_in_aOptBlk( alt )
Junction *alt;
#endif
{
	return find_in_aSubBlk( alt );
}

Predicate *
#ifdef __STDC__
find_in_aLoopBegin( Junction *alt )
#else
find_in_aLoopBegin( alt )
Junction *alt;
#endif
{
	return find_in_aSubBlk( (Junction *) alt->p1 );	/* get preds in alts */
}

Predicate *
#ifdef __STDC__
find_in_aPlusBlk( Junction *alt )
#else
find_in_aPlusBlk( alt )
Junction *alt;
#endif
{
	require(alt!=NULL&&alt->p2!=NULL, "invalid aPlusBlk");
	return find_in_aSubBlk( alt );
}

/* Look for a predicate;
 *
 * Do not pass anything but Junction nodes; no Actions, Tokens, RuleRefs.
 * This means that a "hoisting distance" of zero is the only distance
 * allowable.  Init actions are ignored.
 *
 * WARNING:
 *		Assumes no (..)? block after predicate for the moment.
 *		Does not check to see if pred is in production that can generate
 *			a sequence contained in the set of ambiguous tuples.
 *
 * Return the predicate found if any.
 */
Predicate *
#ifdef __STDC__
find_predicates( Node *alt )
#else
find_predicates( alt )
Node *alt;
#endif
{
#ifdef DBG_PRED
	Junction *j;
	RuleRefNode *r;
	TokNode *t;
#endif
	Predicate *pred;

	if ( alt==NULL ) return NULL;

#ifdef DBG_PRED
	switch ( alt->ntype )
	{
		case nJunction :
			j = (Junction *) alt;
			fprintf(stderr, "Junction(in %s)", j->rname);
			switch ( j->jtype )
			{
				case aSubBlk :
					fprintf(stderr,"aSubBlk\n");
					break;
				case aOptBlk :
					fprintf(stderr,"aOptBlk\n");
					break;
				case aLoopBegin :
					fprintf(stderr,"aLoopBeginBlk\n");
					break;
				case aLoopBlk :
					fprintf(stderr,"aLoopBlk\n");
					break;
				case aPlusBlk :
					fprintf(stderr,"aPlusBlk\n");
					break;
				case EndBlk :
					fprintf(stderr,"EndBlk\n");
					break;
				case RuleBlk :
					fprintf(stderr,"RuleBlk\n");
					break;
				case Generic :
					fprintf(stderr,"Generic\n");
					break;
				case EndRule :
					fprintf(stderr,"EndRule\n");
					break;
			}
			break;
		case nRuleRef :
			r = (RuleRefNode *) alt;
			fprintf(stderr, "RuleRef(in %s)\n", r->rname);
			break;
		case nToken :
			t = (TokNode *) alt;
			fprintf(stderr, "TokenNode(in %s)%s\n", t->rname, TokenString(t->token));
			break;
		case nAction :
			fprintf(stderr, "Action\n");
			break;
	}
#endif

	switch ( alt->ntype )
	{
		case nJunction :
		{
			Predicate *a, *b;
			Junction *p = (Junction *) alt;	

			/* lock nodes */
			if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
				 p->jtype==aPlusBlk || p->jtype==EndRule )
			{
				require(p->pred_lock!=NULL, "rJunc: lock array is NULL");
				if ( p->pred_lock[1] )
				{
					return NULL;
				}
				p->pred_lock[1] = TRUE;
			}

			switch ( p->jtype )
			{
				case aSubBlk :
					a = find_in_aSubBlk(p);
					return a;	/* nothing is visible past this guy */
				case aOptBlk :
					a = find_in_aOptBlk(p);
					return a;
				case aLoopBegin :
					a = find_in_aLoopBegin(p);
					return a;
				case aLoopBlk :
					a = find_in_aSubBlk(p);
					p->pred_lock[1] = FALSE;
					return a;
				case aPlusBlk :
					a = find_in_aPlusBlk(p);
					p->pred_lock[1] = FALSE;
					return a;	/* nothing is visible past this guy */
				case RuleBlk :
					a = find_predicates(p->p1);
					p->pred_lock[1] = FALSE;
					return a;
				case Generic :
					a = find_predicates(p->p1);
					b = find_predicates(p->p2);
					if ( p->pred_lock!=NULL ) p->pred_lock[1] = FALSE;
					if ( a==NULL ) return b;
					if ( b==NULL ) return a;
					/* otherwise OR the two preds together */
					{
					fatal_internal("hit unknown situation during predicate hoisting");
					}
				case EndBlk :
				case EndRule :	/* Find no predicates after a rule ref */
					return NULL;
				default:
					fatal_internal("this cannot be printed\n");
					break;
			}
		}
		case nAction :
		{
			ActionNode *p = (ActionNode *) alt;
			if ( p->init_action ) return find_predicates(p->next);
			if ( p->is_predicate )
			{
				Tree *t;
#ifdef DBG_PRED
				fprintf(stderr, "predicate: <<%s>>?\n", p->action);
#endif
				if ( p->guardpred!=NULL )
				{
					pred = p->guardpred;
				}
				else
				{
					pred = new_pred();
					pred->k = predicateLookaheadDepth(p);
					pred->source = p;
					pred->expr = p->action;
					if ( HoistPredicateContext && pred->k > 1 )
					{
						if ( first_item_is_guess_block((Junction *)p->next) )
						{
							warnFL("cannot compute context of predicate in front of (..)? block", FileStr[p->file], p->line);
						}
						else
						{
							ConstrainSearch = 0;
							TRAV(p->next,
								 pred->k,
								 &(pred->completion), t);
							pred->tcontext = t;
#ifdef DBG_PRED
							fprintf(stderr, "LL(%d) context:", pred->k);
							preorder(t);
							fprintf(stderr, "\n");
#endif
						}
					}
					else if ( HoistPredicateContext && pred->k == 1 )
					{
						pred->scontext[1] = empty;
						if ( first_item_is_guess_block((Junction *)p->next) )
						{
							warnFL("cannot compute context of predicate in front of (..)? block", FileStr[p->file], p->line);
						}
						else
						{
							REACH((Junction *)p->next,
								  1,
								  &(pred->completion),
								  pred->scontext[1]);
#ifdef DBG_PRED
							fprintf(stderr, "LL(1) context:");
							s_fprT(stderr, pred->scontext[1]);
							fprintf(stderr, "\n");
#endif
						}
					}
				}
				{
					Predicate *d = find_predicates(p->next), *root;
/* Warning: Doesn't seem like the up pointers will all be set correctly;
 * TJP: that's ok, we're not using them now.
 */
					if ( d!=NULL )
					{
						root = new_pred();
						root->expr = PRED_AND_LIST;
						root->down = pred;
						pred->right = d;
						pred->up = root;
						d->left = pred;
						d->up = pred->up;
						return root;
					}
				}
				return pred;
			}
			return NULL;
		}
		case nRuleRef :
		{
			Predicate *a;
			RuleRefNode *p = (RuleRefNode *) alt;
			Junction *r;
			int save_halt;
			RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
			if ( q == NULL )
			{
				warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );
				return NULL;
			}
			r = RulePtr[q->rulenum];
			if ( r->pred_lock[1] )
			{
				/* infinite left-recursion; ignore 'cause LL sup 1 (k) analysis
				 * must have seen it earlier.
				 */
				return NULL;
			}
			save_halt = r->end->halt;
			r->end->halt = TRUE;
/*			a = find_predicates((Node *)r->p1);*/
			a = find_predicates((Node *)r);
			r->end->halt = save_halt;
			if ( a==NULL ) return NULL;
			/* attempt to compute the "local" FOLLOW just like in normal lookahead
			 * computation if needed
			 */
			complete_context_sets(p,a);
			complete_context_trees(p,a);
			return a;
		}
		case nToken :
			break;
	}

	return NULL;
}

Predicate *
#ifdef __STDC__
new_pred( void )
#else
new_pred( )
#endif
{
	Predicate *p = (Predicate *) malloc(sizeof(Predicate));
	require(p!=NULL, "new_pred: cannot alloc predicate");
	*p = pred_empty;
	return p;
}

static void
#ifdef __STDC__
complete_context_sets( RuleRefNode *p, Predicate *a )
#else
complete_context_sets( p, a )
RuleRefNode *p;
Predicate *a;
#endif
{
	set rk2, b;
	int k2;

#ifdef DBG_PRED
	fprintf(stderr, "enter complete_context_sets\n");
#endif
	for (; a!=NULL; a=a->right)
	{
		if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )
		{
			complete_context_sets(p, a->down);
			continue;
		}
		rk2 = b = empty;
		while ( !set_nil(a->completion) )
		{
			k2 = set_int(a->completion);
			set_rm(k2, a->completion);
			REACH(p->next, k2, &rk2, b);
			set_orin(&(a->scontext[1]), b);
			set_free(b);
		}
		set_orin(&(a->completion), rk2);/* remember what we couldn't do */
		set_free(rk2);
#ifdef DBG_PRED
		fprintf(stderr, "LL(1) context for %s(addr 0x%x) after ruleref:", a->expr, a);
		s_fprT(stderr, a->scontext[1]);
		fprintf(stderr, "\n");
#endif
/*		complete_context_sets(p, a->down);*/
	}
#ifdef DBG_PRED
	fprintf(stderr, "exit complete_context_sets\n");
#endif
}

static void
#ifdef __STDC__
complete_context_trees( RuleRefNode *p, Predicate *a )
#else
complete_context_trees( p, a )
RuleRefNode *p;
Predicate *a;
#endif
{
	set rk2;
	int k2;
	Tree *u;

#ifdef DBG_PRED
	fprintf(stderr, "enter complete_context_trees\n");
#endif
	for (; a!=NULL; a=a->right)
	{
		if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )
		{
			complete_context_trees(p, a->down);
			continue;
		}
		rk2 = empty;
		/* any k left to do? if so, link onto tree */
		while ( !set_nil(a->completion) )
		{	
			k2 = set_int(a->completion);
			set_rm(k2, a->completion);
			u = NULL;
			TRAV(p->next, k2, &rk2, u);
			/* any subtrees missing k2 tokens, add u onto end */
			a->tcontext = tlink(a->tcontext, u, k2);
		}
		set_orin(&(a->completion), rk2);/* remember what we couldn't do */
		set_free(rk2);
#ifdef DBG_PRED
		fprintf(stderr, "LL(i<%d) context after ruleref:", LL_k);
		preorder(a->tcontext);
		fprintf(stderr, "\n");
#endif
/*		complete_context_trees(p, a->down);*/
	}
#ifdef DBG_PRED
	fprintf(stderr, "exit complete_context_trees\n");
#endif
}

/* Walk a list of predicates and return the set of all tokens in scontext[1]'s */
set
#ifdef __STDC__
covered_set( Predicate *p )
#else
covered_set( p )
Predicate *p;
#endif
{
	set a;

	a = empty;
	for (; p!=NULL; p=p->right)
	{
		if ( p->expr == PRED_AND_LIST || p->expr == PRED_OR_LIST )
		{
			set_orin(&a, covered_set(p->down));
			continue;
		}
		set_orin(&a, p->scontext[1]);
		set_orin(&a, covered_set(p->down));
	}
	return a;
}