/* PatMatch.c - Implements AmigaDos Regular Expression Pattern Matching.
**
**  This program will test whether a string is an AmigaDos  regular expression
**  It may be used to implement wild expressions such as:
**
**    "copy #?.c to <dir>" to copy any file ending in .c
**
**  The program has two entry points: CmplPat, and Match.
**
**    CmplPat - takes a pattern and returns an auxilliary integer vector
**              which is used by Match.  The pattern is not modified in
**              any way.  CmplPat returns 1 if no errors were detected
**              while compiling the pattern; otherwise it returns 0;
**
**    Match   - takes the pattern, the auxilliary vector, and the string
**              to be matched.  It returns 1 if the string matches the
**              pattern; otherwise it returns 0;
**
**  Translated from BCPL by:
**              Jeff Lydiatt
**              Richmond B.C. Canada
**              16 May 1986.
**
**  Source: "A Compact Function for Regular Expression Pattern Matching",
**           Software - Practice and Experience, September 1979.
**
**  Useage:
**     To test if "file.c" matches the regular expression "#?.c"
**     char *Pat = "#?.c";
**     char *Str = "file.c";
**     WORD Aux[128];
**
**     if ( CmplPat( Pat, Aux ) == 0 )
**        {
**           printf("Bad Wildcard Expression\n");
**           exit(1);
**        }
**     if ( Match( Pat, Aux, Str ) == 1 )
**        printf("String matches the pattern\n");
**     else
**        printf("String does NOT match the pattern\n");
**/

/*--- Included files ----*/

#include <stdio.h>
#include <exec/types.h>
#include <ctype.h>

#define  EOS '\0'

/*--- Global Variables  ---*/

static char     Ch;      /* The current character in Pattern */
static char     *Pat;    /* Pointer to the Pattern */
static int      *Aux;    /* Pointer to returned auxilliary vector */
static int      PatP;    /* Current position in Pat */
static int      Patlen;  /* strlen(pat) */
static BOOL     Errflag; /* TRUE if error */
static int      *Work;   /* Pointer to Active work area */
static int      Wp;      /* Current position in work */
static BOOL     Succflag;/* True if "str" matches "pat" */

/*----------------------------------------------------------------*/
/*                   The Interpreter                              */
/*----------------------------------------------------------------*/

static void Put(N)
int N;
{
   register int *ip;
   register int *to;

   if ( N == 0 )
      Succflag = TRUE;
   else
      {
	for ( ip = &Work[ 1 ], to = &Work[ Wp ]; ip <= to; ip++)
	   if ( *ip == N )
	      return;
	Work[ ++Wp ] = N;
      }
}

int Match( Pat, Aux, Str )
char Pat[];
int  Aux[];
char Str[];
{
   int W[ 128 ];
   int  S = 0;
   int  I, N, Q, P, Strlength;
   char K;
   int  strlen();
   void Put();

   Work = W;
   Wp = 0;
   Succflag = FALSE;
   Strlength = strlen( Str );
   Put( 1 );

   if ( Aux[ 0 ] != 0 )
      Put( Aux[ 0 ] );

   for(;;)
      {
        /* First complete the closure */
        for( N=1; N <= Wp; N++ )
          {
	     P = Work[ N ];
	     K = Pat[ P-1 ];
	     Q = Aux[ P ];
	     switch( K )
	   	{
		  case '#': Put( P + 1 );
		  case '%': Put( Q );
		  default : break;
		  case '(':
		  case '|': Put( P + 1);
			    if ( Q != 0 )
			       Put( Q );
		}
	   }

	if ( S >= Strlength )
	   return Succflag;
	if ( Wp == 0 )
	   return FALSE;
	Ch = Str[ S++ ];

	/* Now deal with the match items */

	N = Wp;
	Wp = 0;
	Succflag = FALSE;

	for ( I = 1; I <= N; I++)
	  {
	     P = Work[ I ];
	     K = Pat[ P - 1 ];
	     switch( K )
	       {
		 case '#':
		 case '|':
		 case '%':
		 case '(': break;
		 case '\'': K = Pat[ P ];
		 default : if ( _toupper( Ch ) != _toupper( K ) )
			      break;
		 case '?': /* Successful match */
		 	   Put ( Aux[ P ] );
		} /* End Switch */
	  } /* End For I */
     } /* End for(;;) */
}


/*----------------------------------------------------------------*/
/*                     The Compiler                               */
/*----------------------------------------------------------------*/

static void  Rch() /* Read next character from Pat */
{
   if ( PatP >= Patlen )
      Ch = EOS;
   else
      Ch = Pat[ PatP++ ];
}

static void Nextitem() /* Get next char from Pat; recognize the ' escape char */
{
   if ( Ch == '\'' )
      Rch();
   Rch();
}

static void Setexits( List, Val )
int List;
int Val;
{
   int A;

   do
     {
	A = Aux[ List ];
	Aux[ List ] = Val;
	List = A;
     }
	while ( List != 0 );
}

static int Join( A, B )
int A, B;
{
    int T = A;

    if ( A == 0 )
	return B;
    while ( Aux[ A ] != 0 )
	A = Aux[ A ];
    Aux[ A ] = B;
    return T;
}

static int Prim()      /* Parse a Prim symbol */
{
   int   A = PatP;
   char Op = Ch;
   int  Exp();
   void Setexits(), Nextitem();

   Nextitem();
   switch( Op )
     {
        case EOS:
        case ')':
        case '|': Errflag = TRUE;
        default : return A;
        case '#': Setexits( Prim(), A ); return A;
        case '(': A = Exp( A );
		  if ( Ch != ')' )
		    {
			Errflag = TRUE;
		    }
		  Nextitem();
		  return A;
     }
}

static int Exp( AltP )    /* Parse an expression */
int AltP;
{
   int Exits = 0;
   int A;
   int Prim(), Exits(), Join();
   void Nextitem(), Setexits();

   for (;;)
	{
	   A = Prim();
	   if ( Ch == '|' || Ch == ')' || Ch == EOS )
	      {
		Exits = Join( Exits, A );
		if ( Ch != '|' )
		   return Exits;
		Aux[ AltP ] = PatP;
		AltP = PatP;
		Nextitem();
	      }
	   else
	      Setexits( A, PatP );
	}
}

int CmplPat( Pattern, CmplPattern)
char Pattern[];
int  CmplPattern[];
{
   int i, strlen();
   void Rch(), Setexits();

   Pat = Pattern;
   Aux = CmplPattern;
   PatP = 0;
   Patlen = strlen( Pat );
   Errflag = FALSE;

   for ( i = 0; i <= Patlen; i++ )
      Aux[ i ] = 0;
   Rch();
   Setexits( Exp(0), 0 );
   return (!Errflag);
}