~drizzle-trunk/drizzle/development

/*

 * The matching engine and friends.  This file is #included by regexec.c

 * after suitable #defines of a variety of macros used herein, so that

 * different state representations can be used without duplicating masses

 * of code.

 */

#ifdef SNAMES

#define	matcher	smatcher

#define	fast	sfast

#define	slow	sslow

#define	dissect	sdissect

#define	backref	sbackref

#define	step	sstep

#define	print	sprint

#define	at	sat

#define	match	smat

#endif

#ifdef LNAMES

#define	matcher	lmatcher

#define	fast	lfast

#define	slow	lslow

#define	dissect	ldissect

#define	backref	lbackref

#define	step	lstep

#define	print	lprint

#define	at	lat

#define	match	lmat

#endif

/* another structure passed up and down to avoid zillions of parameters */

struct match {

	struct re_guts *g;

	int eflags;

	my_regmatch_t *pmatch;	/* [nsub+1] (0 element unused) */

	char *offp;		/* offsets work from here */

	char *beginp;		/* start of string -- virtual NUL precedes */

	char *endp;		/* end of string -- virtual NUL here */

	char *coldp;		/* can be no match starting before here */

	char **lastpos;		/* [nplus+1] */

	STATEVARS;

	states st;		/* current states */

	states fresh;		/* states for a fresh start */

	states tmp;		/* temporary */

	states empty;		/* empty set of states */

};

#include "engine.ih"

#ifdef REDEBUG

#define	SP(t, s, c)	print(m, t, s, c, stdout)

#define	AT(t, p1, p2, s1, s2)	at(m, t, p1, p2, s1, s2)

#define	NOTE(str)	{ if (m->eflags&REG_TRACE) printf("=%s\n", (str)); }

#else

#define	SP(t, s, c)	/* nothing */

#define	AT(t, p1, p2, s1, s2)	/* nothing */

#define	NOTE(s)	/* nothing */

#endif

/*

 - matcher - the actual matching engine

 == static int matcher(register struct re_guts *g, char *string, \

 ==	size_t nmatch, regmatch_t pmatch[], int eflags);

 */

static int			/* 0 success, REG_NOMATCH failure */

matcher(charset,g, str, nmatch, pmatch, eflags)

CHARSET_INFO *charset;

register struct re_guts *g;

char *str;

size_t nmatch;

my_regmatch_t pmatch[];

int eflags;

{

	register char *endp;

	register uint i;

	struct match mv;

	register struct match *m = &mv;

	register char *dp;

	register const sopno gf = g->firststate+1;	/* +1 for OEND */

	register const sopno gl = g->laststate;

	char *start;

	char *stop;

	/* simplify the situation where possible */

	if (g->cflags&REG_NOSUB)

		nmatch = 0;

	if (eflags&REG_STARTEND) {

		start = str + pmatch[0].rm_so;

		stop = str + pmatch[0].rm_eo;

	} else {

		start = str;

		stop = start + strlen(start);

	}

	if (stop < start)

		return(REG_INVARG);

	/* prescreening; this does wonders for this rather slow code */

	if (g->must != NULL) {

		for (dp = start; dp < stop; dp++)

			if (*dp == g->must[0] && stop - dp >= g->mlen &&

				memcmp(dp, g->must, (size_t)g->mlen) == 0)

				break;

		if (dp == stop)		/* we didn't find g->must */

			return(REG_NOMATCH);

	}

	/* match struct setup */

	m->g = g;

	m->eflags = eflags;

	m->pmatch = NULL;

	m->lastpos = NULL;

	m->offp = str;

	m->beginp = start;

	m->endp = stop;

	STATESETUP(m, 4);

	SETUP(m->st);

	SETUP(m->fresh);

	SETUP(m->tmp);

	SETUP(m->empty);

	CLEAR(m->empty);

	/* this loop does only one repetition except for backrefs */

	for (;;) {

		endp = fast(charset, m, start, stop, gf, gl);

		if (endp == NULL) {		/* a miss */

		  if (m->pmatch != NULL)

		    free((char *)m->pmatch);

		  if (m->lastpos != NULL)

		    free((char *)m->lastpos);

		  STATETEARDOWN(m);

		  return(REG_NOMATCH);

		}

		if (nmatch == 0 && !g->backrefs)

			break;		/* no further info needed */

		/* where? */

		assert(m->coldp != NULL);

		for (;;) {

			NOTE("finding start");

			endp = slow(charset, m, m->coldp, stop, gf, gl);

			if (endp != NULL)

				break;

			assert(m->coldp < m->endp);

			m->coldp++;

		}

		if (nmatch == 1 && !g->backrefs)

			break;		/* no further info needed */

		/* oh my, he wants the subexpressions... */

		if (m->pmatch == NULL)

			m->pmatch = (my_regmatch_t *)malloc((m->g->nsub + 1) *

							sizeof(my_regmatch_t));

		if (m->pmatch == NULL) {

		  	if (m->lastpos != NULL)

		    	free((char *)m->lastpos);

			STATETEARDOWN(m);

			return(REG_ESPACE);

		}

		for (i = 1; i <= m->g->nsub; i++)

			m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;

		if (!g->backrefs && !(m->eflags&REG_BACKR)) {

			NOTE("dissecting");

			dp = dissect(charset, m, m->coldp, endp, gf, gl);

		} else {

			if (g->nplus > 0 && m->lastpos == NULL)

				m->lastpos = (char **)malloc((g->nplus+1) *

							sizeof(char *));

			if (g->nplus > 0 && m->lastpos == NULL) {

				free(m->pmatch);

				STATETEARDOWN(m);

				return(REG_ESPACE);

			}

			NOTE("backref dissect");

			dp = backref(charset, m, m->coldp, endp, gf, gl, (sopno)0);

		}

		if (dp != NULL)

			break;

		/* uh-oh... we couldn't find a subexpression-level match */

		assert(g->backrefs);	/* must be back references doing it */

		assert(g->nplus == 0 || m->lastpos != NULL);

		for (;;) {

			if (dp != NULL || endp <= m->coldp)

				break;		/* defeat */

			NOTE("backoff");

			endp = slow(charset, m, m->coldp, endp-1, gf, gl);

			if (endp == NULL)

				break;		/* defeat */

			/* try it on a shorter possibility */

#ifndef NDEBUG

			for (i = 1; i <= m->g->nsub; i++) {

				assert(m->pmatch[i].rm_so == -1);

				assert(m->pmatch[i].rm_eo == -1);

			}

#endif

			NOTE("backoff dissect");

			dp = backref(charset, m, m->coldp, endp, gf, gl, (sopno)0);

		}

		assert(dp == NULL || dp == endp);

		if (dp != NULL)		/* found a shorter one */

			break;

		/* despite initial appearances, there is no match here */

		NOTE("false alarm");

		start = m->coldp + 1;	/* recycle starting later */

		assert(start <= stop);

	}

	/* fill in the details if requested */

	if (nmatch > 0) {

		pmatch[0].rm_so = m->coldp - m->offp;

		pmatch[0].rm_eo = endp - m->offp;

	}

	if (nmatch > 1) {

		assert(m->pmatch != NULL);

		for (i = 1; i < nmatch; i++)

			if (i <= m->g->nsub)

				pmatch[i] = m->pmatch[i];

			else {

				pmatch[i].rm_so = -1;

				pmatch[i].rm_eo = -1;

			}

	}

	if (m->pmatch != NULL)

		free((char *)m->pmatch);

	if (m->lastpos != NULL)

		free((char *)m->lastpos);

	STATETEARDOWN(m);

	return(0);

}

/*

 - dissect - figure out what matched what, no back references

 == static char *dissect(register struct match *m, char *start, \

 ==	char *stop, sopno startst, sopno stopst);

 */

static char *			/* == stop (success) always */

dissect(charset, m, start, stop, startst, stopst)

CHARSET_INFO *charset;

register struct match *m;

char *start;

char *stop;

sopno startst;

sopno stopst;

{

	register uint i;

	register sopno ss;	/* start sop of current subRE */

	register sopno es;	/* end sop of current subRE */

	register char *sp;	/* start of string matched by it */

	register char *stp;	/* string matched by it cannot pass here */

	register char *rest;	/* start of rest of string */

	register char *tail;	/* string unmatched by rest of RE */

	register sopno ssub;	/* start sop of subsubRE */

	register sopno esub;	/* end sop of subsubRE */

	register char *ssp;	/* start of string matched by subsubRE */

	register char *sep;	/* end of string matched by subsubRE */

	register char *oldssp;	/* previous ssp */

	register char *dp;      /* used in debug mode to check asserts */

	AT("diss", start, stop, startst, stopst);

	sp = start;

	for (ss = startst; ss < stopst; ss = es) {

		/* identify end of subRE */

		es = ss;

		switch (OP(m->g->strip[es])) {

		case OPLUS_:

		case OQUEST_:

			es += OPND(m->g->strip[es]);

			break;

		case OCH_:

			while (OP(m->g->strip[es]) != O_CH)

				es += OPND(m->g->strip[es]);

			break;

		}

		es++;

		/* figure out what it matched */

		switch (OP(m->g->strip[ss])) {

		case OEND:

			assert(nope);

			break;

		case OCHAR:

			sp++;

			break;

		case OBOL:

		case OEOL:

		case OBOW:

		case OEOW:

			break;

		case OANY:

		case OANYOF:

			sp++;

			break;

		case OBACK_:

		case O_BACK:

			assert(nope);

			break;

		/* cases where length of match is hard to find */

		case OQUEST_:

			stp = stop;

			for (;;) {

				/* how long could this one be? */

				rest = slow(charset, m, sp, stp, ss, es);

				assert(rest != NULL);	/* it did match */

				/* could the rest match the rest? */

				tail = slow(charset, m, rest, stop, es, stopst);

				if (tail == stop)

					break;		/* yes! */

				/* no -- try a shorter match for this one */

				stp = rest - 1;

				assert(stp >= sp);	/* it did work */

			}

			ssub = ss + 1;

			esub = es - 1;

			/* did innards match? */

			if (slow(charset, m, sp, rest, ssub, esub) != NULL) {

				dp = dissect(charset, m, sp, rest, ssub, esub);

				assert(dp == rest);

			} else		/* no */

				assert(sp == rest);

			sp = rest;

			break;

		case OPLUS_:

			stp = stop;

			for (;;) {

				/* how long could this one be? */

				rest = slow(charset, m, sp, stp, ss, es);

				assert(rest != NULL);	/* it did match */

				/* could the rest match the rest? */

				tail = slow(charset, m, rest, stop, es, stopst);

				if (tail == stop)

					break;		/* yes! */

				/* no -- try a shorter match for this one */

				stp = rest - 1;

				assert(stp >= sp);	/* it did work */

			}

			ssub = ss + 1;

			esub = es - 1;

			ssp = sp;

			oldssp = ssp;

			for (;;) {	/* find last match of innards */

				sep = slow(charset, m, ssp, rest, ssub, esub);

				if (sep == NULL || sep == ssp)

					break;	/* failed or matched null */

				oldssp = ssp;	/* on to next try */

				ssp = sep;

			}

			if (sep == NULL) {

				/* last successful match */

				sep = ssp;

				ssp = oldssp;

			}

			assert(sep == rest);	/* must exhaust substring */

			assert(slow(charset, m, ssp, sep, ssub, esub) == rest);

			dp = dissect(charset, m, ssp, sep, ssub, esub);

			assert(dp == sep);

			sp = rest;

			break;

		case OCH_:

			stp = stop;

			for (;;) {

				/* how long could this one be? */

				rest = slow(charset, m, sp, stp, ss, es);

				assert(rest != NULL);	/* it did match */

				/* could the rest match the rest? */

				tail = slow(charset, m, rest, stop, es, stopst);

				if (tail == stop)

					break;		/* yes! */

				/* no -- try a shorter match for this one */

				stp = rest - 1;

				assert(stp >= sp);	/* it did work */

			}

			ssub = ss + 1;

			esub = ss + OPND(m->g->strip[ss]) - 1;

			assert(OP(m->g->strip[esub]) == OOR1);

			for (;;) {	/* find first matching branch */

				if (slow(charset, m, sp, rest, ssub, esub) == rest)

					break;	/* it matched all of it */

				/* that one missed, try next one */

				assert(OP(m->g->strip[esub]) == OOR1);

				esub++;

				assert(OP(m->g->strip[esub]) == OOR2);

				ssub = esub + 1;

				esub += OPND(m->g->strip[esub]);

				if (OP(m->g->strip[esub]) == OOR2)

					esub--;

				else

					assert(OP(m->g->strip[esub]) == O_CH);

			}

			dp = dissect(charset, m, sp, rest, ssub, esub);

			assert(dp == rest);

			sp = rest;

			break;

		case O_PLUS:

		case O_QUEST:

		case OOR1:

		case OOR2:

		case O_CH:

			assert(nope);

			break;

		case OLPAREN:

			i = OPND(m->g->strip[ss]);

			assert(0 < i && i <= m->g->nsub);

			m->pmatch[i].rm_so = sp - m->offp;

			break;

		case ORPAREN:

			i = OPND(m->g->strip[ss]);

			assert(0 < i && i <= m->g->nsub);

			m->pmatch[i].rm_eo = sp - m->offp;

			break;

		default:		/* uh oh */

			assert(nope);

			break;

		}

	}

	assert(sp == stop);

	return(sp);

}

/*

 - backref - figure out what matched what, figuring in back references

 == static char *backref(register struct match *m, char *start, \

 ==	char *stop, sopno startst, sopno stopst, sopno lev);

 */

static char *			/* == stop (success) or NULL (failure) */

backref(charset,m, start, stop, startst, stopst, lev)

CHARSET_INFO *charset;

register struct match *m;

char *start;

char *stop;

sopno startst;

sopno stopst;

sopno lev;			/* PLUS nesting level */

{

	register uint i;

	register sopno ss;	/* start sop of current subRE */

	register char *sp;	/* start of string matched by it */

	register sopno ssub;	/* start sop of subsubRE */

	register sopno esub;	/* end sop of subsubRE */

	register char *ssp;	/* start of string matched by subsubRE */

	register char *dp;

	register size_t len;

	register int hard;

	register sop s;

	register regoff_t offsave;

	register cset *cs;

	AT("back", start, stop, startst, stopst);

	sp = start;

	/* get as far as we can with easy stuff */

	hard = 0;

	for (ss = startst; !hard && ss < stopst; ss++)

		switch (OP(s = m->g->strip[ss])) {

		case OCHAR:

			if (sp == stop || *sp++ != (char)OPND(s))

				return(NULL);

			break;

		case OANY:

			if (sp == stop)

				return(NULL);

			sp++;

			break;

		case OANYOF:

			cs = &m->g->sets[OPND(s)];

			if (sp == stop || !CHIN(cs, *sp++))

				return(NULL);

			break;

		case OBOL:

			if ( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||

					(sp < m->endp && *(sp-1) == '\n' &&

						(m->g->cflags&REG_NEWLINE)) )

				{ /* yes */ }

			else

				return(NULL);

			break;

		case OEOL:

			if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||

					(sp < m->endp && *sp == '\n' &&

						(m->g->cflags&REG_NEWLINE)) )

				{ /* yes */ }

			else

				return(NULL);

			break;

		case OBOW:

			if (( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||

					(sp < m->endp && *(sp-1) == '\n' &&

						(m->g->cflags&REG_NEWLINE)) ||

					(sp > m->beginp &&

							!ISWORD(charset,*(sp-1))) ) &&

					(sp < m->endp && ISWORD(charset,*sp)) )

				{ /* yes */ }

			else

				return(NULL);

			break;

		case OEOW:

			if (( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||

					(sp < m->endp && *sp == '\n' &&

						(m->g->cflags&REG_NEWLINE)) ||

					(sp < m->endp && !ISWORD(charset,*sp)) ) &&

					(sp > m->beginp && ISWORD(charset,*(sp-1))) )

				{ /* yes */ }

			else

				return(NULL);

			break;

		case O_QUEST:

			break;

		case OOR1:	/* matches null but needs to skip */

			ss++;

			s = m->g->strip[ss];

			do {

				assert(OP(s) == OOR2);

				ss += OPND(s);

			} while (OP(s = m->g->strip[ss]) != O_CH);

			/* note that the ss++ gets us past the O_CH */

			break;

		default:	/* have to make a choice */

			hard = 1;

			break;

		}

	if (!hard) {		/* that was it! */

		if (sp != stop)

			return(NULL);

		return(sp);

	}

	ss--;			/* adjust for the for's final increment */

	/* the hard stuff */

	AT("hard", sp, stop, ss, stopst);

	s = m->g->strip[ss];

	switch (OP(s)) {

	case OBACK_:		/* the vilest depths */

		i = OPND(s);

		assert(0 < i && i <= m->g->nsub);

		if (m->pmatch[i].rm_eo == -1)

			return(NULL);

		assert(m->pmatch[i].rm_so != -1);

		len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;

		assert((size_t) (stop - m->beginp) >= len);

		if (sp > stop - len)

			return(NULL);	/* not enough left to match */

		ssp = m->offp + m->pmatch[i].rm_so;

		if (memcmp(sp, ssp, len) != 0)

			return(NULL);

		while (m->g->strip[ss] != SOP(O_BACK, i))

			ss++;

		return(backref(charset, m, sp+len, stop, ss+1, stopst, lev));

		break;

	case OQUEST_:		/* to null or not */

		dp = backref(charset, m, sp, stop, ss+1, stopst, lev);

		if (dp != NULL)

			return(dp);	/* not */

		return(backref(charset, m, sp, stop, ss+OPND(s)+1, stopst, lev));

		break;

	case OPLUS_:

		assert(m->lastpos != NULL);

		assert(lev+1 <= m->g->nplus);

		m->lastpos[lev+1] = sp;

		return(backref(charset, m, sp, stop, ss+1, stopst, lev+1));

		break;

	case O_PLUS:

		if (sp == m->lastpos[lev])	/* last pass matched null */

			return(backref(charset, m, sp, stop, ss+1, stopst, lev-1));

		/* try another pass */

		m->lastpos[lev] = sp;

		dp = backref(charset, m, sp, stop, ss-OPND(s)+1, stopst, lev);

		if (dp == NULL)

			return(backref(charset, m, sp, stop, ss+1, stopst, lev-1));

		else

			return(dp);

		break;

	case OCH_:		/* find the right one, if any */

		ssub = ss + 1;

		esub = ss + OPND(s) - 1;

		assert(OP(m->g->strip[esub]) == OOR1);

		for (;;) {	/* find first matching branch */

			dp = backref(charset, m, sp, stop, ssub, esub, lev);

			if (dp != NULL)

				return(dp);

			/* that one missed, try next one */

			if (OP(m->g->strip[esub]) == O_CH)

				return(NULL);	/* there is none */

			esub++;

			assert(OP(m->g->strip[esub]) == OOR2);

			ssub = esub + 1;

			esub += OPND(m->g->strip[esub]);

			if (OP(m->g->strip[esub]) == OOR2)

				esub--;

			else

				assert(OP(m->g->strip[esub]) == O_CH);

		}

		break;

	case OLPAREN:		/* must undo assignment if rest fails */

		i = OPND(s);

		assert(0 < i && i <= m->g->nsub);

		offsave = m->pmatch[i].rm_so;

		m->pmatch[i].rm_so = sp - m->offp;

		dp = backref(charset, m, sp, stop, ss+1, stopst, lev);

		if (dp != NULL)

			return(dp);

		m->pmatch[i].rm_so = offsave;

		return(NULL);

		break;

	case ORPAREN:		/* must undo assignment if rest fails */

		i = OPND(s);

		assert(0 < i && i <= m->g->nsub);

		offsave = m->pmatch[i].rm_eo;

		m->pmatch[i].rm_eo = sp - m->offp;

		dp = backref(charset, m, sp, stop, ss+1, stopst, lev);

		if (dp != NULL)

			return(dp);

		m->pmatch[i].rm_eo = offsave;

		return(NULL);

		break;

	default:		/* uh oh */

		assert(nope);

		break;

	}

	/* "can't happen" */

	assert(nope);

	/* NOTREACHED */

	return 0;				/* Keep gcc happy */

}

/*

 - fast - step through the string at top speed

 == static char *fast(register struct match *m, char *start, \

 ==	char *stop, sopno startst, sopno stopst);

 */

static char *			/* where tentative match ended, or NULL */

fast(charset, m, start, stop, startst, stopst)

CHARSET_INFO *charset;

register struct match *m;

char *start;

char *stop;

sopno startst;

sopno stopst;

{

	register states st = m->st;

	register states fresh = m->fresh;

	register states tmp = m->tmp;

	register char *p = start;

	register int c = (start == m->beginp) ? OUT : *(start-1);

	register int lastc;	/* previous c */

	register int flagch;

	register int i;

	register char *coldp;	/* last p after which no match was underway */

	CLEAR(st);

	SET1(st, startst);

	st = step(m->g, startst, stopst, st, NOTHING, st);

	ASSIGN(fresh, st);

	SP("start", st, *p);

	coldp = NULL;

	for (;;) {

		/* next character */

		lastc = c;

		c = (p == m->endp) ? OUT : *p;

		if (EQ(st, fresh))

			coldp = p;

		/* is there an EOL and/or BOL between lastc and c? */

		flagch = '\0';

		i = 0;

		if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||

				(lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {

			flagch = BOL;

			i = m->g->nbol;

		}

		if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||

				(c == OUT && !(m->eflags&REG_NOTEOL)) ) {

			flagch = (flagch == BOL) ? BOLEOL : EOL;