/*@A (C) 1992 Allen I. Holub                                                */
  /* YYSTATE.C	Routines to manufacture the lr(1) state table.  */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <tools/debug.h>
#include <tools/set.h>
#include <tools/hash.h>
#include <tools/compiler.h>
#include <tools/l.h>
#include "parser.h"
#include "llout.h"			/* For _EOI_ definition */

/*----------------------------------------------------------------------*/
					/* For statistics only:		     */
PRIVATE int	Nitems		= 0;	/* number of LR(1) items	     */
PRIVATE int	Npairs		= 0;	/* # of pairs in output tables	     */
PRIVATE int	Ntab_entries	= 0;	/* number of transitions in tables    */
PRIVATE int	Shift_reduce    = 0;	/* number of shift/reduce conflicts  */
PRIVATE int	Reduce_reduce   = 0;	/* number of reduce/reduce conflicts */

#define MAXSTATE   512    /* Max # of LALR(1) states.			*/
#define MAXOBUF	   256    /* Buffer size for various output routines	*/

/*----------------------------------------------------------------------*/

typedef struct _item_		    /* LR(1) item:		   	      */
{
   int		 prod_num;	    /* production number 		      */
   PRODUCTION 	 *prod;		    /* the production itself 		      */
   SYMBOL	 *right_of_dot;     /* symbol to the right of the dot	      */
   unsigned char dot_posn;	    /* offset of dot from start of production */
   SET		 *lookaheads;	    /* set of lookahead symbols for this item */

} ITEM;


#define RIGHT_OF_DOT(p) ( (p)->right_of_dot ? (p)->right_of_dot->val : 0 )

#define MAXKERNEL  32	/* Maximum number of kernel items in a state.	      */
#define MAXCLOSE   128	/* Maximum number of closure items in a state (less   */
			/* the epsilon productions).			      */
#define MAXEPSILON 8	/* Maximum number of epsilon productions that can be  */
			/* in a closure set for any given state.	      */

typedef short STATENUM;


typedef struct _state_			/* LR(1) state			    */
{
   ITEM	 *kernel_items  [MAXKERNEL ];	/* Set of kernel items.		    */
   ITEM	 *epsilon_items [MAXEPSILON];	/* Set of epsilon items.	    */

   unsigned nkitems  : 7 ;		/* # items in kernel_items[].	    */
   unsigned neitems  : 7 ;		/* # items in epsilon_items[].	    */
   unsigned closed   : 1 ;		/* State has had closure performed. */

   STATENUM num;			/* State number (0 is start state). */

} STATE;


typedef struct act_or_goto
{
    int	sym;			/* Given this input symbol, 		   */
    int do_this;		/* do this. >0 == shift, <0 == reduce 	   */
    struct act_or_goto *next;	/* Pointer to next ACT in the linked list. */

} ACT;

typedef ACT GOTO;		/* GOTO is an alias for ACT */

PRIVATE ACT *Actions[MAXSTATE];	/* Array of pointers to the head of the action
			         * chains. Indexed by state number.
			 	 * I'm counting on initialization to NULL here.
			         */
PRIVATE GOTO *Gotos[MAXSTATE]; 	/* Array of pointers to the head of the goto
			 	 * chains.
			 	 */
#define CHUNK	   128		 /* New() gets this many structures at once */
PRIVATE HASH_TAB *States      = NULL;	/* LR(1) states 		 */
PRIVATE int	 Nstates      = 0;	/* Number of states.	 	 */

#define MAX_UNFINISHED	128

typedef struct tnode
{
    STATE	 *state;
    struct tnode *left, *right;

} TNODE;


PRIVATE TNODE	Heap[ MAX_UNFINISHED ]; /* Source of all TNODEs		  */
PRIVATE TNODE	*Next_allocate = Heap ; /* Ptr to next node to allocate   */

PRIVATE TNODE	 *Available  = NULL;	/* Free list of available nodes   */
					/* linked list of TNODES. p->left */
					/* is used as the link.		  */
PRIVATE TNODE	 *Unfinished = NULL;	/* Tree of unfinished states.	  */

PRIVATE ITEM	**State_items;		/* Used to pass info to state_cmp */
PRIVATE int	State_nitems;		/* 		"		  */
PRIVATE int	Sort_by_number = 0;	/*		"		  */

#define NEW	 0			/* Possible return values from 	  */
#define UNCLOSED 1			/* newstate().			  */
#define CLOSED	 2

ITEM	*Recycled_items = NULL;

#define MAX_TOK_PER_LINE  10
PRIVATE int Tokens_printed;	/* Controls number of lookaheads printed */
				/* on a single line of yyout.doc.	 */
#ifdef DEBUG
#ifdef __TURBOC__
#pragma warn -use
#endif
PRIVATE char *strprod       P((PRODUCTION *prod				     ));
#endif
void	add_action	  P(( int state, int input_sym, int do_this	     ));
void	add_goto	  P(( int state, int nonterminal, int go_here	     ));
int	add_lookahead	  P(( SET *dst, SET *src			     ));
void	addreductions	  P(( STATE *state, void *junk			     ));
void	add_unfinished	  P(( STATE *state				     ));
int	closure		  P(( STATE *kernel, ITEM **closure_items, \
					     int maxitems		     ));
int	do_close	  P(( ITEM *item,    ITEM **closure_items, \
					     int *nitems, int *maxitems	     ));
void	freeitem	  P(( ITEM *item				     ));
void	free_recycled_items P(( void 					     ));
STATE	*get_unfinished	  P(( void					     ));
ITEM	*in_closure_items P(( PRODUCTION *production, ITEM **closure_item, \
								int nitems   ));
int	item_cmp	  P(( ITEM **item1p, ITEM **item2p		     ));
int	kclosure	  P(( STATE *kernel, ITEM **closure_items,  \
					     int maxitems, int nclose	     ));
int	lr		  P(( STATE *cur_state				     ));
void	make_yy_lhs	  P(( PRODUCTION **prodtab			     ));
void	make_yy_reduce	  P(( PRODUCTION **prodtab			     ));
void	make_yy_slhs	  P(( PRODUCTION **prodtab			     ));
void	make_yy_srhs	  P(( PRODUCTION **prodtab			     ));
int	merge_lookaheads  P(( ITEM **dst_items, ITEM **src_items, int nitems ));
void	mkprod		  P(( SYMBOL *sym, PRODUCTION **prodtab		     ));
void	movedot		  P(( ITEM *item				     ));
int	move_eps	  P(( STATE *cur_state, ITEM **closure_items, \
						int nclose		     ));
MS  ( void *new )
UNIX( ACT  *new )  	  P(( void 					     ));
ITEM	*newitem	  P(( PRODUCTION *production			     ));
int	newstate	  P(( ITEM **items, int nitems, STATE **statep	     ));
ACT	*p_action	  P(( int state, int input_sym			     ));
void	pclosure	  P(( STATE *kernel, ITEM **closure_items, int nitems));
GOTO	*p_goto		  P(( int state, int nonterminal		     ));
void	print_reductions  P(( void					     ));
void	print_tab	  P(( ACT **table, char *row_name, char *col_name, \
							   int  private      ));
void	 pstate		  P(( STATE *state				     ));
void	 pstate_stdout	  P(( STATE *state				     ));
void	 reduce_one_item  P(( STATE *state, ITEM *item			     ));
void	 reductions	  P(( void					     ));
void	 sprint_tok	  P(( char **bp,     char *format, int arg	     ));
int	 state_cmp	  P(( STATE *new, STATE *tab_node		     ));
unsigned state_hash	  P(( STATE *sym				     ));
char	 *stritem	  P(( ITEM *item,    int lookaheads		     ));


void	lr_stats	  P(( FILE *fp ));			/* public */
int	lr_conflicts	  P(( FILE *fp ));
void	make_parse_tables P(( void     ));


  ANSI( PRIVATE void	*new( void ) )
  KnR ( PRIVATE ACT	*new() 	     )

{
    /* Return an area of memory that can be used as either an ACT or GOTO.
     * These objects cannot be freed.
     */

    static ACT  *eheap;	/* Assuming default initialization to NULL here */
    static ACT	*heap ; /* Ditto.					*/

    if( heap >= eheap )	   /* The > is cheap insurance, == is sufficient */
    {
	if( !(heap = (ACT *) malloc( sizeof(ACT) * CHUNK) ))
	    error( FATAL, "No memory for action or goto\n" );

	eheap = heap + CHUNK ;
    }
    ++Ntab_entries ;
    return heap++  ;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

PRIVATE ACT	*p_action( state, input_sym )
int state, input_sym;
{
    /* Return a pointer to the existing ACT structure representing the indicated
     * state and input symbol (or NULL if no such symbol exists).
     */

    ACT	*p;

    D( if( state > MAXSTATE )  						)
    D(    error(FATAL, "bad state argument to p_action (%d)\n", state);	)

    for( p = Actions[state]; p ; p = p->next )
	if( p->sym == input_sym )
	    return p;

    return NULL;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

PRIVATE void	add_action( state, input_sym, do_this )
int state, input_sym, do_this;
{
    /* Add an element to the action part of the parse table. The cell is
     * indexed by the state number and input symbol, and holds do_this.
     */

    ACT	*p;

#ifdef INTERNAL
     if( state > MAXSTATE )
         error(FATAL, "bad state argument to add_action (%d)\n", state );

      if( (p = p_action(state, input_sym)) )
      {
  	error( FATAL,   "Tried to add duplicate action in state %d:\n"
  			"   (1) shift/reduce %d on %s <-existing\n"
  			"   (2) shift/reduce %d on %s <-new\n" ,
  			state, p->do_this, Terms[  p->sym ]->name,
  				  do_this, Terms[input_sym]->name );
     }
#endif

    if( Verbose > 1 )
	printf("Adding shift or reduce action from state %d:  %d on %s\n",
				      state, do_this, Terms[ input_sym ]->name);
    p		   = (ACT *) new();
    p->sym         = input_sym ;
    p->do_this     = do_this ;
    p->next        = Actions[state];
    Actions[state] = p;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

PRIVATE GOTO	*p_goto( state, nonterminal )
int state, nonterminal;
{
    /* Return a pointer to the existing GOTO structure representing the
     * indicated state and nonterminal (or NULL if no such symbol exists). The
     * value used for the nonterminal is the one in the symbol table; it is
     * adjusted down (so that the smallest nonterminal has the value 0)
     * before doing the table look up, however.
     */

    GOTO   *p;

    nonterminal = ADJ_VAL( nonterminal );

    D( if( nonterminal > NUMNONTERMS ) 			)
    D(    error(FATAL, "bad argument to p_goto\n");	)

    for( p = Gotos[ state ] ; p ; p = p->next )
	if( p->sym == nonterminal )
	    return p;

    return NULL;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

PRIVATE void	add_goto( state, nonterminal, go_here )
int	state, nonterminal, go_here;
{
    /* Add an element to the goto part of the parse table, the cell is indexed
     * by current state number and nonterminal value, and holds go_here. Note
     * that the input nonterminal value is the one that appears in the symbol
     * table. It is adjusted downwards (so that the smallest nonterminal will
     * have the value 0) before being inserted into the table, however.
     */

    GOTO	*p;
    int		unadjusted;		/* Original value of nonterminal   */

    unadjusted  = nonterminal;
    nonterminal = ADJ_VAL( nonterminal );

#ifdef INTERNAL
      if( nonterminal > NUMNONTERMS )
          error(FATAL, "bad argument to add_goto\n");

      if( p = p_goto( state, unadjusted) )
          error(  FATAL,  "Tried to add duplicate goto on nonterminal %s\n"
      			"   (1) goto %3d from %3d <-existing\n"
      			"   (2) goto %3d from %3d <-new\n" ,
  			Terms[unadjusted]->name ,
  			p->go_here, p->state,
  			   go_here,    state );
#endif


    if( Verbose > 1 )
	    printf( "Adding goto from state %d to %d on %s\n",
				      state, go_here, Terms[unadjusted]->name );
    p            = (GOTO *) new();
    p->sym       = nonterminal;
    p->do_this   = go_here;
    p->next      = Gotos[state];
    Gotos[state] = p;
}

PRIVATE int	newstate( items, nitems, statep )
ITEM	**items;
int	nitems;
STATE	**statep;
{
    STATE  *state;
    STATE  *existing;
    int	   state_cmp() ;

    if( nitems > MAXKERNEL )
	error( FATAL, "Kernel of new state %d too large\n", Nstates );


    State_items  = items;	/* set up parameters for state_cmp */
    State_nitems = nitems;	/* and state_hash.		   */

    if( existing = (STATE *) findsym( States, NULL ) )
    {
	/* State exists; by not setting "state" to NULL, we'll recycle	*/
	/* the newly allocated state on the next call.			*/

	*statep = existing;
	if( Verbose > 1 )
	{
	    printf("Using existing state (%sclosed): ",
						existing->closed ? "" : "un" );
	    pstate_stdout( existing );
	}
	return existing->closed ? CLOSED : UNCLOSED ;
    }
    else
    {
	if( Nstates >= MAXSTATE )
	    error(FATAL, "Too many LALR(1) states\n");

	if( !(state = (STATE *) newsym(sizeof(STATE)) ))
	    error( FATAL, "Insufficient memory for states\n" );

	memcpy( state->kernel_items, items, nitems * sizeof(ITEM*) );
	state->nkitems  = nitems;
	state->neitems  = 0;
	state->closed   = 0;
	state->num 	= Nstates++ ;
	*statep 	= state;
	addsym( States, state );

	if( Verbose > 1 )
	{
	    printf("Forming new state:");
	    pstate_stdout( state );
	}

	return NEW;
    }
}

/*----------------------------------------------------------------------*/

PRIVATE void	add_unfinished( state )
STATE	*state;
{
    TNODE **parent, *root;
    int   cmp;

    parent = &Unfinished;
    root   = Unfinished;
    while( root )			/* look for the node in the tree */
    {
	if( (cmp = state->num - root->state->num) == 0 )
	    break;
	else
	{
	    parent = (cmp < 0) ? &root->left : &root->right ;
	    root   = (cmp < 0) ?  root->left :  root->right ;
	}
    }

    if( !root )				      /* Node isn't in tree.         */
    {
	if( Available )			      /* Allocate a new node and      */
	{				      /* put it into the tree.       */
	    *parent   = Available ;	      /* Use node from Available     */
	    Available = Available->left ;     /* list if possible, otherwise */
	}				      /* get the node from the Heap. */
	else
	{
	    if( Next_allocate >= &Heap[ MAX_UNFINISHED ] )
		error(FATAL, "Internal: No memory for unfinished state\n");
	    *parent = Next_allocate++;
	}

	(*parent)->state = state;		      /* initialize the node */
	(*parent)->left  = (*parent)->right = NULL;
    }

    D( printf("\nAdded state %d to unfinished tree:\n", state->num );	)
    D( prnt_unfin( Unfinished );					)
    D( printf("\n");							)
}

/*----------------------------------------------------------------------*/

PRIVATE STATE	*get_unfinished()
{
    /* Returns a pointer to the next unfinished state and deletes that
     * state from the unfinished tree. Returns NULL if the tree is empty.
     */

    TNODE	*root;
    TNODE	**parent;

    if( !Unfinished )
	return NULL;

    parent = &Unfinished;		/* find leftmost node */
    if( root = Unfinished )
    {
	while( root->left )
	{
	    parent = &root->left ;
	    root   = root->left ;
	}
    }

    *parent    = root->right ;	  	/* Unlink node from the tree	*/
    root->left = Available;	  	/* Put it into the free list	*/
    Available  = root;

    D(printf("\nReturning state %d from unfinished tree:\n",root->state->num);)
    D(prnt_unfin( Unfinished );	)
    D(printf("\n");		)