/* @(#)match.c	1.18 00/11/12 Copyright 1985 J. Schilling */
#include <standard.h>
#include <patmatch.h>
/*
 *	Pattern matching functions
 *
 *	Copyright (c) 1985,1995 J. Schilling
 */
/*
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; see the file COPYING.  If not, write to
 * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
 */
/*
 *	The pattern matching functions below are based on the algorithm
 *	presented by Martin Richards in:
 *
 *	"A Compact Function for Regular Expression Pattern Matching", 
 *	Software-Practice and Experience, Vol. 9, 527-534 (1979)
 *
 *	Several changes have been made to the original source which has been
 *	written in BCPL:
 *
 *	'/'	is replaced by	'!'		(to allow UNIX filenames)
 *	'(',')' are replaced by	'{', '}'
 *	'\''	is replaced by	'\\'		(UNIX compatible quote)
 *
 *	Character classes have been added to allow "[<character list>]"
 *	to be used.
 *	Start of line '^' and end of line '$' have been added.
 */

#ifdef	__LINE_MATCH
#define	opatmatch	opatlmatch
#define	patmatch	patlmatch
#endif

#define	ENDSTATE	(-1)
typedef	unsigned char	Uchar;

/*---------------------------------------------------------------------------
|
|	The Interpreter
|
+---------------------------------------------------------------------------*/


/*
 *	put adds a new state to the active list
 */
#define put(ret, state, sp, n)	{		\
	register int *lstate	= state;	\
	register int *lsp	= sp;		\
	register int ln		= n;		\
						\
	while (lstate < lsp) {			\
		if (*lstate++ == ln) {		\
			ret = lsp;		\
			lsp = 0;		\
			break;			\
		}				\
	}					\
	if (lsp) {				\
		*lstate++ = ln;			\
		ret = lstate;			\
	}					\
}


/*
 *	match a character in class
 */
#define in_class(found, pat, c)	{			\
	register const Uchar	*lpat	= pat;		\
	register int		lc	= c;		\
	int	lo_bound;				\
	int	hi_bound;				\
							\
	found = FALSE;					\
							\
	if (*lpat == NOT) {				\
		lpat++;					\
		found = TRUE;				\
	}						\
	while (*lpat != RCLASS) {			\
		if (*lpat == QUOTE)			\
			lpat++;				\
		lo_bound = *lpat++;			\
		if (*lpat == RANGE) {			\
			lpat++;				\
			if (*lpat == QUOTE)		\
				lpat++;			\
			hi_bound = *lpat++;		\
		} else {				\
			hi_bound = lo_bound;		\
		}					\
		if (lo_bound <= lc && lc <= hi_bound) {	\
			found = !found;			\
			break;				\
		}					\
	}						\
}

/*
 *	opatmatch - the old external interpreter interface.
 *
 *	Trys to match a string beginning at offset
 *	against the compiled pattern.
 */
Uchar *opatmatch(pat, aux, str, soff, slen, alt)
	const Uchar	*pat;
	const int	*aux;
	const Uchar	*str;
	int		soff;
	int		slen;
	int		alt;
{
	int		state[MAXPAT];

	return (patmatch(pat, aux, str, soff, slen, alt, state));
}

/*
 *	patmatch - the external interpreter interface.
 *
 *	Trys to match a string beginning at offset
 *	against the compiled pattern.
 */
Uchar *patmatch(pat, aux, str, soff, slen, alt, state)
	const Uchar	*pat;
	const int	*aux;
	const Uchar	*str;
	int		soff;
	int		slen;
	int		alt;
	int		state[];
{
	register int	*sp;
	register int	*n;
	register int	*i;
	register int	p;
	register int	q, s, k;
	int		c;
	const Uchar	*lastp = (Uchar *)NULL;

#ifdef	__LINE_MATCH
for( ;soff <= slen; soff++) {
#endif

	sp = state;
	put(sp, state, state, 0);
	if (alt != ENDSTATE)
		put(sp, state, sp, alt);

	for(s = soff; ; s++) {
		/*
		 * next char from input string
		 */
		if (s >= slen)
			c = 0;
		else
			c = str[s];
		/*
		 * first complete the closure
		 */
		for(n = state; n < sp;) {
			p = *n++;		/* next state number */
			if (p == ENDSTATE)
				continue;
			q = aux[p];		/* get next state for pat */
			k = pat[p];		/* get next char from pat */
			switch (k) {

			case REP:
				put(sp, state, sp, p+1);
			case NIL:		/* NIL matches always */
			case STAR:
				put(sp, state, sp, q);
				break;
			case LBRACK:		/* alternations */
			case ALT:
				put(sp, state, sp, p+1);
				if (q != ENDSTATE)
					put(sp, state, sp, q);
				break;
			case START:
				if (s == 0)
					put(sp, state, sp, q);
				break;
			case END:
				if (c == '\0')
					put(sp, state, sp, q);
				break;
			}
		}

		for (i = state; i < sp;) {
			if (*i++ == ENDSTATE) {
				lastp = &str[s];
				break;
			}
		}
		if (c == 0)
			return ((Uchar *)lastp);

		/*
		 * now try to match next character
		 */
		n = sp;
		sp = state;
		for(i = sp; i < n;) {
			p = *i++;		/* next active state number */
			if (p == ENDSTATE)
				continue;
			k = pat[p];
			switch (k) {

			case ALT:
			case REP:
			case NIL:
			case LBRACK:
			case START:
			case END:
				continue;
			case LCLASS:
				in_class(q, &pat[p+1], c);
				if (!q)
					continue;
				break;
			case STAR:
				put(sp, state, sp, p);
				continue;
			case QUOTE:
				k = pat[p+1];
			default:
				if (k != c)
					continue;
			case ANY:
				break;
			}
			put(sp, state, sp, aux[p]);
		}
		if (sp == state) {		/* if no new states return */
#ifdef	__LINE_MATCH

			if (lastp || (soff == slen - 1))
				return ((Uchar *)lastp);
			else
				break;
#else
			return ((Uchar *)lastp);
#endif
		}
	}
#ifdef	__LINE_MATCH
   }
   return ((Uchar *)lastp);
#endif
}


#ifndef	__LINE_MATCH
/*---------------------------------------------------------------------------
|
|	The Compiler
|
+---------------------------------------------------------------------------*/

typedef	struct args {
	const Uchar	*pattern;
	int		*aux;
	int		patp;
	int		length;
	Uchar		Ch;
} arg_t;

static	void	nextitem __PR((arg_t *));
static	int	prim	 __PR((arg_t *));
static	int	exp	 __PR((arg_t *, int *));
static	void	setexits __PR((int *, int, int));
static	int	join	 __PR((int *, int, int));
	
/*
 *	'read' the next character from pattern
 */
#define	rch(ap)						\
{							\
	if (++(ap)->patp >= (ap)->length)		\
		(ap)->Ch = 0;				\
	else						\
		(ap)->Ch = (ap)->pattern[(ap)->patp];	\
}

/*
 *	get the next item from pattern
 */
static void nextitem(ap)
	arg_t	*ap;
{
	if (ap->Ch == QUOTE)
		rch(ap);
	rch(ap);
}

/*
 *	parse a primary
 */
static int prim(ap)
	arg_t	*ap;
{
	int	a  = ap->patp;
	int	op = ap->Ch;
	int	t;

	nextitem(ap);
	switch (op) {

	case '\0':
	case ALT:
	case RBRACK:
		return (ENDSTATE);
	case LCLASS:
		while (ap->Ch != RCLASS && ap->Ch != '\0')
			nextitem(ap);
		if (ap->Ch == '\0')
			return (ENDSTATE);
		nextitem(ap);
		break;
	case REP:
		t = prim(ap);
		if (t == ENDSTATE)
			return (ENDSTATE);
		setexits(ap->aux, t, a);
		break;
	case LBRACK:
		a = exp(ap, &ap->aux[a]);
		if (a == ENDSTATE || ap->Ch != RBRACK)
			return (ENDSTATE);
		nextitem(ap);
		break;
	}
	return (a);
}

/*
 *	parse an expression (a sequence of primaries)
 */
static int exp(ap, altp)
	arg_t	*ap;
	int	*altp;
{
	int	exits = ENDSTATE;
	int	a;
	int	*aux = ap->aux;
	Uchar	Ch;

	for(;;) {
		a = prim(ap);
		Ch = ap->Ch;
		if (Ch == ALT || Ch == RBRACK || Ch == '\0') {
			exits = join(aux, exits, a);
			if (Ch != ALT)
				return (exits);
			*altp = ap->patp;
			altp = &aux[ap->patp];
			nextitem(ap);
		} else
			setexits(aux, a, ap->patp);
	}
}

/*
 *	set all exits in a list to a specified value
 */
static void setexits(aux, list, val)
	int	*aux;
	int	list;
	int	val;
{
	int	a;

	while (list != ENDSTATE) {
		a = aux[list];
		aux[list] = val;
		list = a;
	}
}

/*
 *	concatenate two lists
 */
static int join(aux, a, b)
	int	*aux;
	int	a;
	int	b;
{
	int	t;

	if (a == ENDSTATE)
		return (b);
	t = a;
	while (aux[t] != ENDSTATE)
		t = aux[t];
	aux[t] = b;
	return (a);
}

/*
 *	patcompile - the external compiler interface.
 *
 *	The pattern is compiled into the aux array.
 *	Return value on success, is the outermost alternate which is != 0.
 *	Error is indicated by return of 0.
 */
int patcompile(pat, len, aux)
	const Uchar	*pat;
	int		len;
	int		*aux;
{
	arg_t	a;
	int	alt = ENDSTATE;
	int	i;

	a.pattern = pat;
	a.length  = len;
	a.aux     = aux;
	a.patp    = -1;

	for(i = 0; i < len; i++)
		aux[i] = ENDSTATE;
	rch(&a);
	i = exp(&a, &alt);
	if (i == ENDSTATE)
		return (0);
	setexits(aux, i, ENDSTATE);
	return (alt);
}
#endif	/* LMATCH */