/* 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 (TRUE) if no errors were detected
**		  while compiling the pattern; otherwise it returns 0 (FALSE);
**
**	Match   - takes the pattern, the auxilliary vector, and the string
**		  to be matched.  It returns 1 (TRUE) if the string matches the
**		  pattern; otherwise it returns 0 (FALSE);
**
**  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.
**
**  Usage:	To test if "file.c" matches the regular expression "#?.c"
**		char *Pat = "#?.c";
**		char *Str = "file.c";
**		WORD Aux[128];
**
**		if( !CmplPat( Pat, Aux ) )
**		{
**			printf("Bad Wildcard Expression\n");
**				exit(RETURN_ERROR);
**		}
**
**		if( Match( Pat, Aux, Str ) )
**			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)
register 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 )
register int List;
register int Val;
{
	register int A;

	do
	{
		A = Aux[ List ];
		Aux[ List ] = Val;
		List = A;
	}

	while ( List != 0 );
}

static int
Join( A, B )
register int A, B;
{
	register 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 */
{
	register 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 */
register int AltP;
{
	register int Exits = 0;
	register 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[];
{
	register int i;
	int 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);
}