/********************************************
rexp.c
copyright 1991, Michael D. Brennan

This is a source file for mawk, an implementation of
the AWK programming language.

Mawk is distributed without warranty under the terms of
the GNU General Public License, version 2, 1991.
********************************************/

/*$Log: rexp.c,v $
 *Revision 1.3  1996/09/02 18:47:36  mike
 *Make ^* and ^+ syntax errors.
 *
 *Revision 1.2  1993/07/23 13:21:32  mike
 *cleanup rexp code
 *
 * Revision 1.1.1.1  1993/07/03	 18:58:26  mike
 * move source to cvs
 *
 * Revision 3.4	 1991/08/13  09:09:59  brennan
 * VERSION .9994
 *
 * Revision 3.3	 91/08/04  15:45:03  brennan
 * no longer attempt to recover mem on failed REcompile
 * Its not worth the effort
 *
 * Revision 3.2	 91/08/03  07:24:06  brennan
 * check for empty machine stack (missing operand) wasn't quite right
 *
 * Revision 3.1	 91/06/07  10:33:16  brennan
 * VERSION 0.995
 *
 * Revision 1.7	 91/06/05  08:58:47  brennan
 * change RE_free to free
 *
 * Revision 1.6	 91/06/03  07:07:17  brennan
 * moved parser stacks inside REcompile
 * removed unnecessary copying
 *
*/

/*  op precedence  parser for regular expressions  */

#include  "rexp.h"


/*  DATA   */
int REerrno ;
char *REerrlist[] =
{(char *) 0,
 /* 1  */ "missing '('",
 /* 2  */ "missing ')'",
 /* 3  */ "bad class -- [], [^] or [",
 /* 4  */ "missing operand",
 /* 5  */ "resource exhaustion -- regular expression too large" ,
 /* 6  */ "syntax error ^* or ^+"
} ;
/* E5 is very unlikely to occur */


/* This table drives the operator precedence parser */
static  short  table[8][8]  =  {

/*        0   |   CAT   *   +   ?   (   )   */
/* 0 */   0,  L,  L,    L,  L,  L,  L,  E1,
/* | */   G,  G,  L,    L,  L,  L,  L,  G,
/* CAT*/  G,  G,  G,    L,  L,  L,  L,  G,
/* * */   G,  G,  G,    G,  G,  G, E7,  G,
/* + */   G,  G,  G,    G,  G,  G, E7,  G,
/* ? */   G,  G,  G,    G,  G,  G, E7,  G,
/* ( */   E2, L,  L,    L,  L,  L,  L,  EQ,
/* ) */   G , G,  G,    G,  G,  G,  E7,  G     }   ;


#define	 STACKSZ   64


static jmp_buf err_buf ;	 /*  used to trap on error */

void
RE_error_trap(x)
   int x ;
{
   REerrno = x ;
   longjmp(err_buf, 1) ;
}


PTR
REcompile(re)
   char *re ;
{
   MACHINE m_stack[STACKSZ] ;
   struct op
   {
      int token ;
      int prec ;
   }
   op_stack[STACKSZ] ;
   register MACHINE *m_ptr ;
   register struct op *op_ptr ;
   register int t ;

   /* do this first because it also checks if we have a
     run time stack */
   RE_lex_init(re) ;

   if (*re == 0)
   {
      STATE *p = (STATE *) RE_malloc(sizeof(STATE)) ;
      p->type = M_ACCEPT ;
      return (PTR) p ;
   }

   if (setjmp(err_buf))	 return (PTR) 0 ;
   /* we used to try to recover memory left on machine stack ;
     but now m_ptr is in a register so it won't be right unless
     we force it out of a register which isn't worth the trouble */

   /* initialize the stacks  */
   m_ptr = m_stack - 1 ;
   op_ptr = op_stack ;
   op_ptr->token = 0 ;

   t = RE_lex(m_stack) ;

   while (1)
   {
      switch (t)
      {
	 case T_STR:
	 case T_ANY:
	 case T_U:
	 case T_START:
	 case T_END:
	 case T_CLASS:
	    m_ptr++ ; 
	    break ;

	 case 0:		/*  end of reg expr   */
	    if (op_ptr->token == 0)
	    {
	       /*  done	  */
	       if (m_ptr == m_stack)  return (PTR) m_ptr->start ;
	       else  
	       {
		  /* machines still on the stack  */
		  RE_panic("values still on machine stack") ;
	       }
	    }

	    /*	otherwise  fall	 thru to default
	     which is operator case  */

	 default:

	    if ((op_ptr->prec = table[op_ptr->token][t]) == G)
	    {
	       do
	       {		/* op_pop   */

		  if (op_ptr->token <= T_CAT)	/*binary op*/
		     m_ptr-- ;
		  /* if not enough values on machine stack
		   then we have a missing operand */
		  if (m_ptr < m_stack)	RE_error_trap(-E4) ;

		  switch (op_ptr->token)
		  {
		     case T_CAT:
			RE_cat(m_ptr, m_ptr + 1) ;
			break ;

		     case T_OR:
			RE_or(m_ptr, m_ptr + 1) ;
			break ;

		     case T_STAR:
			RE_close(m_ptr) ;
			break ;

		     case T_PLUS:
			RE_poscl(m_ptr) ;
			break ;

		     case T_Q:
			RE_01(m_ptr) ;
			break ;

		     default:
			/*nothing on ( or ) */
			break ;
		  }

		  op_ptr-- ;
	       }
	       while (op_ptr->prec != L);

	       continue ;	 /* back thru switch at top */
	    }

	    if (op_ptr->prec < 0)
	    {
	       if (op_ptr->prec == E7)	RE_panic("parser returns E7") ;
	       else  RE_error_trap(-op_ptr->prec) ;
	    }

	    if (++op_ptr == op_stack + STACKSZ)
	    {
	       /* stack overflow */
	       RE_error_trap(-E5) ;
	    }

	    op_ptr->token = t ;
      }				/* end of switch */

      if (m_ptr == m_stack + (STACKSZ - 1))
      {
	 /*overflow*/
	 RE_error_trap(-E5) ;
      }

      t = RE_lex(m_ptr + 1) ;
   }
}


/* getting here means a logic flaw or unforeseen case */
void
RE_panic(s)
   char *s ;
{
   fprintf(stderr, "REcompile() - panic:  %s\n", s) ;
   exit(100) ;
}