[perl5.git] / regexec.c

/* NOTE: this is derived from Henry Spencer's regexp code, and should not
 * confused with the original package (see point 3 below).  Thanks, Henry!
 */

/* Additional note: this code is very heavily munged from Henry's version
 * in places.  In some spots I've traded clarity for efficiency, so don't
 * blame Henry for some of the lack of readability.
 */

/* $Header: regexec.c,v 3.0.1.3 90/02/28 18:14:39 lwall Locked $
 *
 * $Log:	regexec.c,v $
 * Revision 3.0.1.3  90/02/28  18:14:39  lwall
 * patch9: /[\200-\377]/ didn't work on machines with signed chars
 * patch9: \d, \w, and \s could misfire on characters with high bit set
 * patch9: /\bfoo/i didn't work
 * 
 * Revision 3.0.1.2  89/12/21  20:16:27  lwall
 * patch7: certain patterns didn't match correctly at end of string
 * 
 * Revision 3.0.1.1  89/11/11  04:52:04  lwall
 * patch2: /\b$foo/ didn't work
 * 
 * Revision 3.0  89/10/18  15:22:53  lwall
 * 3.0 baseline
 * 
 */

/*
 * regcomp and regexec -- regsub and regerror are not used in perl
 *
 *	Copyright (c) 1986 by University of Toronto.
 *	Written by Henry Spencer.  Not derived from licensed software.
 *
 *	Permission is granted to anyone to use this software for any
 *	purpose on any computer system, and to redistribute it freely,
 *	subject to the following restrictions:
 *
 *	1. The author is not responsible for the consequences of use of
 *		this software, no matter how awful, even if they arise
 *		from defects in it.
 *
 *	2. The origin of this software must not be misrepresented, either
 *		by explicit claim or by omission.
 *
 *	3. Altered versions must be plainly marked as such, and must not
 *		be misrepresented as being the original software.
 *
 ****    Alterations to Henry's code are...
 ****
 ****    Copyright (c) 1989, Larry Wall
 ****
 ****    You may distribute under the terms of the GNU General Public License
 ****    as specified in the README file that comes with the perl 3.0 kit.
 *
 * Beware that some of this code is subtly aware of the way operator
 * precedence is structured in regular expressions.  Serious changes in
 * regular-expression syntax might require a total rethink.
 */
#include "EXTERN.h"
#include "perl.h"
#include "regcomp.h"

#ifndef STATIC
#define	STATIC	static
#endif

#ifdef DEBUGGING
int regnarrate = 0;
#endif

#define isALNUM(c) (isascii(c) && (isalpha(c) || isdigit(c) || c == '_'))
#define isSPACE(c) (isascii(c) && isspace(c))
#define isDIGIT(c) (isascii(c) && isdigit(c))
#define isUPPER(c) (isascii(c) && isupper(c))

/*
 * regexec and friends
 */

/*
 * Global work variables for regexec().
 */
static char *regprecomp;
static char *reginput;		/* String-input pointer. */
static char regprev;		/* char before regbol, \n if none */
static char *regbol;		/* Beginning of input, for ^ check. */
static char *regeol;		/* End of input, for $ check. */
static char **regstartp;	/* Pointer to startp array. */
static char **regendp;		/* Ditto for endp. */
static char *reglastparen;	/* Similarly for lastparen. */
static char *regtill;

static char *regmystartp[10];	/* For remembering backreferences. */
static char *regmyendp[10];

/*
 * Forwards.
 */
STATIC int regtry();
STATIC int regmatch();
STATIC int regrepeat();

extern int multiline;

/*
 - regexec - match a regexp against a string
 */
int
regexec(prog, stringarg, strend, strbeg, minend, screamer, safebase)
register regexp *prog;
char *stringarg;
register char *strend;	/* pointer to null at end of string */
char *strbeg;	/* real beginning of string */
int minend;	/* end of match must be at least minend after stringarg */
STR *screamer;
int safebase;	/* no need to remember string in subbase */
{
	register char *s;
	register int i;
	register char *c;
	register char *string = stringarg;
	register int tmp;
	int minlen = 0;		/* must match at least this many chars */
	int dontbother = 0;	/* how many characters not to try at end */

	/* Be paranoid... */
	if (prog == NULL || string == NULL) {
		fatal("NULL regexp parameter");
		return(0);
	}

	if (string == strbeg)	/* is ^ valid at stringarg? */
	    regprev = '\n';
	else
	    regprev = stringarg[-1];
	regprecomp = prog->precomp;
	/* Check validity of program. */
	if (UCHARAT(prog->program) != MAGIC) {
		FAIL("corrupted regexp program");
	}

	if (prog->do_folding) {
		safebase = FALSE;
		i = strend - string;
		New(1101,c,i+1,char);
		(void)bcopy(string, c, i+1);
		string = c;
		strend = string + i;
		for (s = string; s < strend; s++)
			if (isUPPER(*s))
				*s = tolower(*s);
	}

	/* If there is a "must appear" string, look for it. */
	s = string;
	if (prog->regmust != Nullstr) {
		if (stringarg == strbeg && screamer) {
			if (screamfirst[prog->regmust->str_rare] >= 0)
				s = screaminstr(screamer,prog->regmust);
			else
				s = Nullch;
		}
#ifndef lint
		else
			s = fbminstr((unsigned char*)s, (unsigned char*)strend,
			    prog->regmust);
#endif
		if (!s) {
			++prog->regmust->str_u.str_useful;	/* hooray */
			goto phooey;	/* not present */
		}
		else if (prog->regback >= 0) {
			s -= prog->regback;
			if (s < string)
			    s = string;
			minlen = prog->regback + prog->regmust->str_cur;
		}
		else if (--prog->regmust->str_u.str_useful < 0) { /* boo */
			str_free(prog->regmust);
			prog->regmust = Nullstr;	/* disable regmust */
			s = string;
		}
		else {
			s = string;
			minlen = prog->regmust->str_cur;
		}
	}

	/* Mark beginning of line for ^ . */
	regbol = string;

	/* Mark end of line for $ (and such) */
	regeol = strend;

	/* see how far we have to get to not match where we matched before */
	regtill = string+minend;

	/* Simplest case:  anchored match need be tried only once. */
	/*  [unless multiline is set] */
	if (prog->reganch) {
		if (regtry(prog, string))
			goto got_it;
		else if (multiline) {
			if (minlen)
			    dontbother = minlen - 1;
			strend -= dontbother;
			/* for multiline we only have to try after newlines */
			if (s > string)
			    s--;
			for (; s < strend; s++) {
			    if (*s == '\n') {
				if (++s < strend && regtry(prog, s))
				    goto got_it;
			    }
			}
		}
		goto phooey;
	}

	/* Messy cases:  unanchored match. */
	if (prog->regstart) {
		/* We know what string it must start with. */
		if (prog->regstart->str_pok == 3) {
#ifndef lint
		    while ((s = fbminstr((unsigned char*)s,
		      (unsigned char*)strend, prog->regstart)) != NULL)
#else
		    while (s = Nullch)
#endif
		    {
			    if (regtry(prog, s))
				    goto got_it;
			    s++;
		    }
		}
		else {
		    c = prog->regstart->str_ptr;
		    while ((s = ninstr(s, strend,
		      c, c + prog->regstart->str_cur )) != NULL) {
			    if (regtry(prog, s))
				    goto got_it;
			    s++;
		    }
		}
		goto phooey;
	}
	if (c = prog->regstclass) {
		if (minlen)
		    dontbother = minlen - 1;
		strend -= dontbother;	/* don't bother with what can't match */
		/* We know what class it must start with. */
		switch (OP(c)) {
		case ANYOF: case ANYBUT:
		    c = OPERAND(c);
		    while (s < strend) {
			    i = UCHARAT(s);
			    if (!(c[i >> 3] & (1 << (i&7))))
				    if (regtry(prog, s))
					    goto got_it;
			    s++;
		    }
		    break;
		case BOUND:
		    if (minlen)
			dontbother++,strend--;
		    if (s != string) {
			i = s[-1];
			tmp = isALNUM(i);
		    }
		    else
			tmp = isALNUM(regprev);	/* assume not alphanumeric */
		    while (s < strend) {
			    i = *s;
			    if (tmp != isALNUM(i)) {
				    tmp = !tmp;
				    if (regtry(prog, s))
					    goto got_it;
			    }
			    s++;
		    }
		    if ((minlen || tmp) && regtry(prog,s))
			    goto got_it;
		    break;
		case NBOUND:
		    if (minlen)
			dontbother++,strend--;
		    if (s != string) {
			i = s[-1];
			tmp = isALNUM(i);
		    }
		    else
			tmp = isALNUM(regprev);	/* assume not alphanumeric */
		    while (s < strend) {
			    i = *s;
			    if (tmp != isALNUM(i))
				    tmp = !tmp;
			    else if (regtry(prog, s))
				    goto got_it;
			    s++;
		    }
		    if ((minlen || !tmp) && regtry(prog,s))
			    goto got_it;
		    break;
		case ALNUM:
		    while (s < strend) {
			    i = *s;
			    if (isALNUM(i))
				    if (regtry(prog, s))
					    goto got_it;
			    s++;
		    }
		    break;
		case NALNUM:
		    while (s < strend) {
			    i = *s;
			    if (!isALNUM(i))
				    if (regtry(prog, s))
					    goto got_it;
			    s++;
		    }
		    break;
		case SPACE:
		    while (s < strend) {
			    if (isSPACE(*s))
				    if (regtry(prog, s))
					    goto got_it;
			    s++;
		    }
		    break;
		case NSPACE:
		    while (s < strend) {
			    if (!isSPACE(*s))
				    if (regtry(prog, s))
					    goto got_it;
			    s++;
		    }
		    break;
		case DIGIT:
		    while (s < strend) {
			    if (isDIGIT(*s))
				    if (regtry(prog, s))
					    goto got_it;
			    s++;
		    }
		    break;
		case NDIGIT:
		    while (s < strend) {
			    if (!isDIGIT(*s))
				    if (regtry(prog, s))
					    goto got_it;
			    s++;
		    }
		    break;
		}
	}
	else {
		if (minlen)
		    dontbother = minlen - 1;
		strend -= dontbother;
		/* We don't know much -- general case. */
		do {
			if (regtry(prog, s))
				goto got_it;
		} while (s++ < strend);
	}

	/* Failure. */
	goto phooey;

    got_it:
	if ((!safebase && (prog->nparens || sawampersand)) || prog->do_folding){
		strend += dontbother;	/* uncheat */
		if (safebase)			/* no need for $digit later */
		    s = strbeg;
		else if (strbeg != prog->subbase) {
		    i = strend - string + (stringarg - strbeg);
		    s = nsavestr(strbeg,i);	/* so $digit will work later */
		    if (prog->subbase)
			    Safefree(prog->subbase);
		    prog->subbase = s;
		}
		else
		    s = prog->subbase;
		s += (stringarg - strbeg);
		for (i = 0; i <= prog->nparens; i++) {
			if (prog->endp[i]) {
			    prog->startp[i] = s + (prog->startp[i] - string);
			    prog->endp[i] = s + (prog->endp[i] - string);
			}
		}
		if (prog->do_folding)
			Safefree(string);
	}
	return(1);

    phooey:
	if (prog->do_folding)
		Safefree(string);
	return(0);
}

/*
 - regtry - try match at specific point
 */
static int			/* 0 failure, 1 success */
regtry(prog, string)
regexp *prog;
char *string;
{
	register int i;
	register char **sp;
	register char **ep;

	reginput = string;
	regstartp = prog->startp;
	regendp = prog->endp;
	reglastparen = &prog->lastparen;
	prog->lastparen = 0;

	sp = prog->startp;
	ep = prog->endp;
	if (prog->nparens) {
		for (i = NSUBEXP; i > 0; i--) {
			*sp++ = NULL;
			*ep++ = NULL;
		}
	}
	if (regmatch(prog->program + 1) && reginput >= regtill) {
		prog->startp[0] = string;
		prog->endp[0] = reginput;
		return(1);
	} else
		return(0);
}

/*
 - regmatch - main matching routine
 *
 * Conceptually the strategy is simple:  check to see whether the current
 * node matches, call self recursively to see whether the rest matches,
 * and then act accordingly.  In practice we make some effort to avoid
 * recursion, in particular by going through "ordinary" nodes (that don't
 * need to know whether the rest of the match failed) by a loop instead of
 * by recursion.
 */
/* [lwall] I've hoisted the register declarations to the outer block in order to
 * maybe save a little bit of pushing and popping on the stack.  It also takes
 * advantage of machines that use a register save mask on subroutine entry.
 */
static int			/* 0 failure, 1 success */
regmatch(prog)
char *prog;
{
	register char *scan;	/* Current node. */
	char *next;		/* Next node. */
	register int nextchar;
	register int n;		/* no or next */
	register int ln;        /* len or last */
	register char *s;	/* operand or save */
	register char *locinput = reginput;

	nextchar = *locinput;
	scan = prog;
#ifdef DEBUGGING
	if (scan != NULL && regnarrate)
		fprintf(stderr, "%s(\n", regprop(scan));
#endif
	while (scan != NULL) {
#ifdef DEBUGGING
		if (regnarrate)
			fprintf(stderr, "%s...\n", regprop(scan));
#endif

#ifdef REGALIGN
		next = scan + NEXT(scan);
		if (next == scan)
		    next = NULL;
#else
		next = regnext(scan);
#endif

		switch (OP(scan)) {
		case BOL:
			if (locinput == regbol ? regprev == '\n' :
			    ((nextchar || locinput < regeol) &&
			      locinput[-1] == '\n') )
			{
				regtill--;
				break;
			}
			return(0);
		case EOL:
			if ((nextchar || locinput < regeol) && nextchar != '\n')
				return(0);
			regtill--;
			break;
		case ANY:
			if ((nextchar == '\0' && locinput >= regeol) ||
			  nextchar == '\n')
				return(0);
			nextchar = *++locinput;
			break;
		case EXACTLY:
			s = OPERAND(scan);
			ln = *s++;
			/* Inline the first character, for speed. */
			if (*s != nextchar)
				return(0);
			if (locinput + ln > regeol)
				return 0;
			if (ln > 1 && bcmp(s, locinput, ln) != 0)
				return(0);
			locinput += ln;
			nextchar = *locinput;
			break;
		case ANYOF:
		case ANYBUT:
			s = OPERAND(scan);
			if (nextchar < 0)
				nextchar = UCHARAT(locinput);
			if (s[nextchar >> 3] & (1 << (nextchar&7)))
				return(0);
			nextchar = *++locinput;
			if (!nextchar && locinput > regeol)
				return 0;
			break;
		case ALNUM:
			if (!nextchar)
				return(0);
			if (!isALNUM(nextchar))
				return(0);
			nextchar = *++locinput;
			break;
		case NALNUM:
			if (!nextchar && locinput >= regeol)
				return(0);
			if (isALNUM(nextchar))
				return(0);
			nextchar = *++locinput;
			break;
		case NBOUND:
		case BOUND:
			if (locinput == regbol)	/* was last char in word? */
				ln = isALNUM(regprev);
			else 
				ln = isALNUM(locinput[-1]);
			n = isALNUM(nextchar); /* is next char in word? */
			if ((ln == n) == (OP(scan) == BOUND))
				return(0);
			break;
		case SPACE:
			if (!nextchar && locinput >= regeol)
				return(0);
			if (!isSPACE(nextchar))
				return(0);
			nextchar = *++locinput;
			break;
		case NSPACE:
			if (!nextchar)
				return(0);
			if (isSPACE(nextchar))
				return(0);
			nextchar = *++locinput;
			break;
		case DIGIT:
			if (!isDIGIT(nextchar))
				return(0);
			nextchar = *++locinput;
			break;
		case NDIGIT:
			if (!nextchar && locinput >= regeol)
				return(0);
			if (isDIGIT(nextchar))
				return(0);
			nextchar = *++locinput;
			break;
		case REF:
		case REF+1:
		case REF+2:
		case REF+3:
		case REF+4:
		case REF+5:
		case REF+6:
		case REF+7:
		case REF+8:
		case REF+9:
			n = OP(scan) - REF;
			s = regmystartp[n];
			if (!s)
			    return(0);
			if (!regmyendp[n])
			    return(0);
			if (s == regmyendp[n])
			    break;
			/* Inline the first character, for speed. */
			if (*s != nextchar)
				return(0);
			ln = regmyendp[n] - s;
			if (locinput + ln > regeol)
				return 0;
			if (ln > 1 && bcmp(s, locinput, ln) != 0)
				return(0);
			locinput += ln;
			nextchar = *locinput;
			break;

		case NOTHING:
			break;
		case BACK:
			break;
		case OPEN+1:
		case OPEN+2:
		case OPEN+3:
		case OPEN+4:
		case OPEN+5:
		case OPEN+6:
		case OPEN+7:
		case OPEN+8:
		case OPEN+9:
			n = OP(scan) - OPEN;
			reginput = locinput;

			regmystartp[n] = locinput;	/* for REF */
			if (regmatch(next)) {
				/*
				 * Don't set startp if some later
				 * invocation of the same parentheses
				 * already has.
				 */
				if (regstartp[n] == NULL)
					regstartp[n] = locinput;
				return(1);
			} else
				return(0);
			/* NOTREACHED */
		case CLOSE+1:
		case CLOSE+2:
		case CLOSE+3:
		case CLOSE+4:
		case CLOSE+5:
		case CLOSE+6:
		case CLOSE+7:
		case CLOSE+8:
		case CLOSE+9: {
				n = OP(scan) - CLOSE;
				reginput = locinput;

				regmyendp[n] = locinput;	/* for REF */
				if (regmatch(next)) {
					/*
					 * Don't set endp if some later
					 * invocation of the same parentheses
					 * already has.
					 */
					if (regendp[n] == NULL) {
						regendp[n] = locinput;
						if (n > *reglastparen)
						    *reglastparen = n;
					}
					return(1);
				} else
					return(0);
			}
			/*NOTREACHED*/
		case BRANCH: {
				if (OP(next) != BRANCH)		/* No choice. */
					next = NEXTOPER(scan);	/* Avoid recursion. */
				else {
					do {
						reginput = locinput;
						if (regmatch(NEXTOPER(scan)))
							return(1);
#ifdef REGALIGN
						if (n = NEXT(scan))
						    scan += n;
						else
						    scan = NULL;
#else
						scan = regnext(scan);
#endif
					} while (scan != NULL && OP(scan) == BRANCH);
					return(0);
					/* NOTREACHED */
				}
			}
			break;
		case STAR:
		case PLUS:
			/*
			 * Lookahead to avoid useless match attempts
			 * when we know what character comes next.
			 */
			if (OP(next) == EXACTLY)
				nextchar = *(OPERAND(next)+1);
			else
				nextchar = -1000;
			ln = (OP(scan) == STAR) ? 0 : 1;
			reginput = locinput;
			n = regrepeat(NEXTOPER(scan));
			while (n >= ln) {
				/* If it could work, try it. */
				if (nextchar == -1000 || *reginput == nextchar)
					if (regmatch(next))
						return(1);
				/* Couldn't or didn't -- back up. */
				n--;
				reginput = locinput + n;
			}
			return(0);
		case END:
			reginput = locinput; /* put where regtry can find it */
			return(1);	/* Success! */
		default:
			printf("%x %d\n",scan,scan[1]);
			FAIL("regexp memory corruption");
		}

		scan = next;
	}

	/*
	 * We get here only if there's trouble -- normally "case END" is
	 * the terminating point.
	 */
	FAIL("corrupted regexp pointers");
	/*NOTREACHED*/
#ifdef lint
	return 0;
#endif
}

/*
 - regrepeat - repeatedly match something simple, report how many
 */
/*
 * [This routine now assumes that it will only match on things of length 1.
 * That was true before, but now we assume scan - reginput is the count,
 * rather than incrementing count on every character.]
 */
static int
regrepeat(p)
char *p;
{
	register char *scan;
	register char *opnd;
	register int c;
	register char *loceol = regeol;

	scan = reginput;
	opnd = OPERAND(p);
	switch (OP(p)) {
	case ANY:
		while (scan < loceol && *scan != '\n')
			scan++;
		break;
	case EXACTLY:		/* length of string is 1 */
		opnd++;
		while (scan < loceol && *opnd == *scan)
			scan++;
		break;
	case ANYOF:
	case ANYBUT:
		c = UCHARAT(scan);
		while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
			scan++;
			c = UCHARAT(scan);
		}
		break;
	case ALNUM:
		while (isALNUM(*scan))
			scan++;
		break;
	case NALNUM:
		while (scan < loceol && !isALNUM(*scan))
			scan++;
		break;
	case SPACE:
		while (scan < loceol && isSPACE(*scan))
			scan++;
		break;
	case NSPACE:
		while (scan < loceol && !isSPACE(*scan))
			scan++;
		break;
	case DIGIT:
		while (isDIGIT(*scan))
			scan++;
		break;
	case NDIGIT:
		while (scan < loceol && !isDIGIT(*scan))
			scan++;
		break;
	default:		/* Oh dear.  Called inappropriately. */
		FAIL("internal regexp foulup");
		/* NOTREACHED */
	}

	c = scan - reginput;
	reginput = scan;

	return(c);
}

/*
 - regnext - dig the "next" pointer out of a node
 *
 * [Note, when REGALIGN is defined there are two places in regmatch()
 * that bypass this code for speed.]
 */
char *
regnext(p)
register char *p;
{
	register int offset;

	if (p == &regdummy)
		return(NULL);

	offset = NEXT(p);
	if (offset == 0)
		return(NULL);

#ifdef REGALIGN
	return(p+offset);
#else
	if (OP(p) == BACK)
		return(p-offset);
	else
		return(p+offset);
#endif
}
Commit	Line	Data
a687059c LW	1	/* NOTE: this is derived from Henry Spencer's regexp code, and should not
	2	* confused with the original package (see point 3 below). Thanks, Henry!
	3	*/
	4
	5	/* Additional note: this code is very heavily munged from Henry's version
	6	* in places. In some spots I've traded clarity for efficiency, so don't
	7	* blame Henry for some of the lack of readability.
	8	*/
	9
ac58e20f	10	/* $Header: regexec.c,v 3.0.1.3 90/02/28 18:14:39 lwall Locked $
a687059c LW	11	*
a687059c LW	12	* $Log: regexec.c,v $
ac58e20f LW	13	* Revision 3.0.1.3 90/02/28 18:14:39 lwall
	14	* patch9: /[\200-\377]/ didn't work on machines with signed chars
	15	* patch9: \d, \w, and \s could misfire on characters with high bit set
	16	* patch9: /\bfoo/i didn't work
	17	*
663a0e37 LW	18	* Revision 3.0.1.2 89/12/21 20:16:27 lwall
	19	* patch7: certain patterns didn't match correctly at end of string
	20	*
ae986130 LW	21	* Revision 3.0.1.1 89/11/11 04:52:04 lwall
	22	* patch2: /\b$foo/ didn't work
	23	*
a687059c LW	24	* Revision 3.0 89/10/18 15:22:53 lwall
	25	* 3.0 baseline
	26	*
	27	*/
	28
	29	/*
	30	* regcomp and regexec -- regsub and regerror are not used in perl
	31	*
	32	* Copyright (c) 1986 by University of Toronto.
	33	* Written by Henry Spencer. Not derived from licensed software.
	34	*
	35	* Permission is granted to anyone to use this software for any
	36	* purpose on any computer system, and to redistribute it freely,
	37	* subject to the following restrictions:
	38	*
	39	* 1. The author is not responsible for the consequences of use of
	40	* this software, no matter how awful, even if they arise
	41	* from defects in it.
	42	*
	43	* 2. The origin of this software must not be misrepresented, either
	44	* by explicit claim or by omission.
	45	*
	46	* 3. Altered versions must be plainly marked as such, and must not
	47	* be misrepresented as being the original software.
	48	*
	49	**** Alterations to Henry's code are...
	50	****
	51	**** Copyright (c) 1989, Larry Wall
	52	****
	53	**** You may distribute under the terms of the GNU General Public License
	54	**** as specified in the README file that comes with the perl 3.0 kit.
	55	*
	56	* Beware that some of this code is subtly aware of the way operator
	57	* precedence is structured in regular expressions. Serious changes in
	58	* regular-expression syntax might require a total rethink.
	59	*/
	60	#include "EXTERN.h"
	61	#include "perl.h"
	62	#include "regcomp.h"
	63
	64	#ifndef STATIC
	65	#define STATIC static
	66	#endif
	67
	68	#ifdef DEBUGGING
	69	int regnarrate = 0;
	70	#endif
	71
ac58e20f LW	72	#define isALNUM(c) (isascii(c) && (isalpha(c) \|\| isdigit(c) \|\| c == '_'))
	73	#define isSPACE(c) (isascii(c) && isspace(c))
	74	#define isDIGIT(c) (isascii(c) && isdigit(c))
	75	#define isUPPER(c) (isascii(c) && isupper(c))
	76
a687059c LW	77	/*
	78	* regexec and friends
	79	*/
	80
	81	/*
	82	* Global work variables for regexec().
	83	*/
	84	static char *regprecomp;
	85	static char reginput; / String-input pointer. */
ac58e20f	86	static char regprev; /* char before regbol, \n if none */
a687059c LW	87	static char regbol; / Beginning of input, for ^ check. */
	88	static char regeol; / End of input, for $ check. */
	89	static char *regstartp; / Pointer to startp array. */
	90	static char *regendp; / Ditto for endp. */
	91	static char reglastparen; / Similarly for lastparen. */
	92	static char *regtill;
	93
	94	static char regmystartp[10]; / For remembering backreferences. */
	95	static char *regmyendp[10];
	96
	97	/*
	98	* Forwards.
	99	*/
	100	STATIC int regtry();
	101	STATIC int regmatch();
	102	STATIC int regrepeat();
	103
	104	extern int multiline;
	105
	106	/*
	107	- regexec - match a regexp against a string
	108	*/
	109	int
	110	regexec(prog, stringarg, strend, strbeg, minend, screamer, safebase)
	111	register regexp *prog;
	112	char *stringarg;
	113	register char strend; / pointer to null at end of string */
	114	char strbeg; / real beginning of string */
	115	int minend; /* end of match must be at least minend after stringarg */
	116	STR *screamer;
	117	int safebase; /* no need to remember string in subbase */
	118	{
	119	register char *s;
	120	register int i;
	121	register char *c;
	122	register char *string = stringarg;
	123	register int tmp;
	124	int minlen = 0; /* must match at least this many chars */
	125	int dontbother = 0; /* how many characters not to try at end */
a687059c LW	126
	127	/* Be paranoid... */
	128	if (prog == NULL \|\| string == NULL) {
	129	fatal("NULL regexp parameter");
	130	return(0);
	131	}
	132
ac58e20f LW	133	if (string == strbeg) /* is ^ valid at stringarg? */
	134	regprev = '\n';
	135	else
	136	regprev = stringarg[-1];
a687059c LW	137	regprecomp = prog->precomp;
	138	/* Check validity of program. */
	139	if (UCHARAT(prog->program) != MAGIC) {
	140	FAIL("corrupted regexp program");
	141	}
	142
	143	if (prog->do_folding) {
	144	safebase = FALSE;
	145	i = strend - string;
	146	New(1101,c,i+1,char);
	147	(void)bcopy(string, c, i+1);
	148	string = c;
	149	strend = string + i;
	150	for (s = string; s < strend; s++)
ac58e20f	151	if (isUPPER(*s))
a687059c LW	152	s = tolower(s);
	153	}
	154
	155	/* If there is a "must appear" string, look for it. */
	156	s = string;
	157	if (prog->regmust != Nullstr) {
ac58e20f	158	if (stringarg == strbeg && screamer) {
a687059c LW	159	if (screamfirst[prog->regmust->str_rare] >= 0)
	160	s = screaminstr(screamer,prog->regmust);
	161	else
	162	s = Nullch;
	163	}
	164	#ifndef lint
	165	else
	166	s = fbminstr((unsigned char)s, (unsigned char)strend,
	167	prog->regmust);
	168	#endif
	169	if (!s) {
	170	++prog->regmust->str_u.str_useful; /* hooray */
	171	goto phooey; /* not present */
	172	}
	173	else if (prog->regback >= 0) {
	174	s -= prog->regback;
	175	if (s < string)
	176	s = string;
	177	minlen = prog->regback + prog->regmust->str_cur;
	178	}
	179	else if (--prog->regmust->str_u.str_useful < 0) { /* boo */
	180	str_free(prog->regmust);
	181	prog->regmust = Nullstr; /* disable regmust */
	182	s = string;
	183	}
	184	else {
	185	s = string;
	186	minlen = prog->regmust->str_cur;
	187	}
	188	}
	189
	190	/* Mark beginning of line for ^ . */
ac58e20f	191	regbol = string;
a687059c LW	192
	193	/* Mark end of line for $ (and such) */
	194	regeol = strend;
	195
	196	/* see how far we have to get to not match where we matched before */
	197	regtill = string+minend;
	198
	199	/* Simplest case: anchored match need be tried only once. */
	200	/* [unless multiline is set] */
	201	if (prog->reganch) {
	202	if (regtry(prog, string))
	203	goto got_it;
	204	else if (multiline) {
	205	if (minlen)
	206	dontbother = minlen - 1;
	207	strend -= dontbother;
	208	/* for multiline we only have to try after newlines */
	209	if (s > string)
	210	s--;
	211	for (; s < strend; s++) {
	212	if (*s == '\n') {
	213	if (++s < strend && regtry(prog, s))
	214	goto got_it;
	215	}
	216	}
	217	}
	218	goto phooey;
	219	}
	220
	221	/* Messy cases: unanchored match. */
	222	if (prog->regstart) {
	223	/* We know what string it must start with. */
	224	if (prog->regstart->str_pok == 3) {
	225	#ifndef lint
	226	while ((s = fbminstr((unsigned char*)s,
	227	(unsigned char*)strend, prog->regstart)) != NULL)
	228	#else
	229	while (s = Nullch)
	230	#endif
	231	{
	232	if (regtry(prog, s))
	233	goto got_it;
	234	s++;
	235	}
	236	}
	237	else {
	238	c = prog->regstart->str_ptr;
	239	while ((s = ninstr(s, strend,
	240	c, c + prog->regstart->str_cur )) != NULL) {
	241	if (regtry(prog, s))
	242	goto got_it;
	243	s++;
	244	}
	245	}
	246	goto phooey;
	247	}
	248	if (c = prog->regstclass) {
	249	if (minlen)
	250	dontbother = minlen - 1;
	251	strend -= dontbother; /* don't bother with what can't match */
	252	/* We know what class it must start with. */
	253	switch (OP(c)) {
	254	case ANYOF: case ANYBUT:
	255	c = OPERAND(c);
256	while (s < strend) {
ac58e20f	257	i = UCHARAT(s);
a687059c LW	258	if (!(c[i >> 3] & (1 << (i&7))))
	259	if (regtry(prog, s))
	260	goto got_it;
	261	s++;
	262	}
	263	break;
	264	case BOUND:
	265	if (minlen)
	266	dontbother++,strend--;
	267	if (s != string) {
	268	i = s[-1];
ac58e20f	269	tmp = isALNUM(i);
a687059c LW	270	}
a687059c LW	271	else
ac58e20f	272	tmp = isALNUM(regprev); /* assume not alphanumeric */
a687059c LW	273	while (s < strend) {
a687059c LW	274	i = *s;
ac58e20f	275	if (tmp != isALNUM(i)) {
a687059c LW	276	tmp = !tmp;
	277	if (regtry(prog, s))
	278	goto got_it;
	279	}
	280	s++;
	281	}
ae986130	282	if ((minlen \|\| tmp) && regtry(prog,s))
a687059c LW	283	goto got_it;
	284	break;
	285	case NBOUND:
	286	if (minlen)
	287	dontbother++,strend--;
	288	if (s != string) {
	289	i = s[-1];
ac58e20f	290	tmp = isALNUM(i);
a687059c LW	291	}
a687059c LW	292	else
ac58e20f	293	tmp = isALNUM(regprev); /* assume not alphanumeric */
a687059c LW	294	while (s < strend) {
a687059c LW	295	i = *s;
ac58e20f	296	if (tmp != isALNUM(i))
a687059c LW	297	tmp = !tmp;
	298	else if (regtry(prog, s))
	299	goto got_it;
	300	s++;
	301	}
ae986130	302	if ((minlen \|\| !tmp) && regtry(prog,s))
a687059c LW	303	goto got_it;
	304	break;
	305	case ALNUM:
	306	while (s < strend) {
	307	i = *s;
ac58e20f	308	if (isALNUM(i))
a687059c LW	309	if (regtry(prog, s))
	310	goto got_it;
	311	s++;
	312	}
	313	break;
	314	case NALNUM:
	315	while (s < strend) {
	316	i = *s;
ac58e20f	317	if (!isALNUM(i))
a687059c LW	318	if (regtry(prog, s))
	319	goto got_it;
	320	s++;
	321	}
	322	break;
	323	case SPACE:
	324	while (s < strend) {
ac58e20f	325	if (isSPACE(*s))
a687059c LW	326	if (regtry(prog, s))
	327	goto got_it;
	328	s++;
	329	}
	330	break;
	331	case NSPACE:
	332	while (s < strend) {
ac58e20f	333	if (!isSPACE(*s))
a687059c LW	334	if (regtry(prog, s))
	335	goto got_it;
	336	s++;
	337	}
	338	break;
	339	case DIGIT:
	340	while (s < strend) {
ac58e20f	341	if (isDIGIT(*s))
a687059c LW	342	if (regtry(prog, s))
	343	goto got_it;
	344	s++;
	345	}
	346	break;
	347	case NDIGIT:
	348	while (s < strend) {
ac58e20f	349	if (!isDIGIT(*s))
a687059c LW	350	if (regtry(prog, s))
	351	goto got_it;
	352	s++;
	353	}
	354	break;
	355	}
	356	}
	357	else {
663a0e37 LW	358	if (minlen)
663a0e37 LW	359	dontbother = minlen - 1;
a687059c LW	360	strend -= dontbother;
	361	/* We don't know much -- general case. */
	362	do {
	363	if (regtry(prog, s))
	364	goto got_it;
	365	} while (s++ < strend);
	366	}
	367
	368	/* Failure. */
	369	goto phooey;
	370
	371	got_it:
	372	if ((!safebase && (prog->nparens \|\| sawampersand)) \|\| prog->do_folding){
	373	strend += dontbother; /* uncheat */
	374	if (safebase) /* no need for $digit later */
	375	s = strbeg;
	376	else if (strbeg != prog->subbase) {
	377	i = strend - string + (stringarg - strbeg);
	378	s = nsavestr(strbeg,i); /* so $digit will work later */
	379	if (prog->subbase)
	380	Safefree(prog->subbase);
	381	prog->subbase = s;
	382	}
	383	else
	384	s = prog->subbase;
	385	s += (stringarg - strbeg);
	386	for (i = 0; i <= prog->nparens; i++) {
	387	if (prog->endp[i]) {
	388	prog->startp[i] = s + (prog->startp[i] - string);
	389	prog->endp[i] = s + (prog->endp[i] - string);
	390	}
	391	}
	392	if (prog->do_folding)
	393	Safefree(string);
	394	}
	395	return(1);
	396
	397	phooey:
	398	if (prog->do_folding)
	399	Safefree(string);
	400	return(0);
	401	}
	402
	403	/*
	404	- regtry - try match at specific point
	405	*/
	406	static int /* 0 failure, 1 success */
	407	regtry(prog, string)
	408	regexp *prog;
	409	char *string;
	410	{
	411	register int i;
	412	register char **sp;
	413	register char **ep;
	414
	415	reginput = string;
	416	regstartp = prog->startp;
	417	regendp = prog->endp;
	418	reglastparen = &prog->lastparen;
	419	prog->lastparen = 0;
	420
	421	sp = prog->startp;
	422	ep = prog->endp;
	423	if (prog->nparens) {
424	for (i = NSUBEXP; i > 0; i--) {
425	*sp++ = NULL;
426	*ep++ = NULL;
427	}
428	}
429	if (regmatch(prog->program + 1) && reginput >= regtill) {
430	prog->startp[0] = string;
431	prog->endp[0] = reginput;
432	return(1);
433	} else
434	return(0);
435	}
436
437	/*
438	- regmatch - main matching routine
439	*
440	* Conceptually the strategy is simple: check to see whether the current
441	* node matches, call self recursively to see whether the rest matches,
442	* and then act accordingly. In practice we make some effort to avoid
443	* recursion, in particular by going through "ordinary" nodes (that don't
444	* need to know whether the rest of the match failed) by a loop instead of
445	* by recursion.
446	*/
447	/* [lwall] I've hoisted the register declarations to the outer block in order to
448	* maybe save a little bit of pushing and popping on the stack. It also takes
449	* advantage of machines that use a register save mask on subroutine entry.
450	*/
451	static int /* 0 failure, 1 success */
452	regmatch(prog)
453	char *prog;
454	{
455	register char scan; / Current node. */
456	char next; / Next node. */
457	register int nextchar;
458	register int n; /* no or next */
459	register int ln; /* len or last */
460	register char s; / operand or save */
461	register char *locinput = reginput;
462
463	nextchar = *locinput;
464	scan = prog;
465	#ifdef DEBUGGING
466	if (scan != NULL && regnarrate)
467	fprintf(stderr, "%s(\n", regprop(scan));
468	#endif
469	while (scan != NULL) {
470	#ifdef DEBUGGING
471	if (regnarrate)
472	fprintf(stderr, "%s...\n", regprop(scan));
473	#endif
474
475	#ifdef REGALIGN
476	next = scan + NEXT(scan);
477	if (next == scan)
478	next = NULL;
479	#else
480	next = regnext(scan);
481	#endif
482
483	switch (OP(scan)) {
484	case BOL:
ac58e20f	485	if (locinput == regbol ? regprev == '\n' :
a687059c LW	486	((nextchar \|\| locinput < regeol) &&
	487	locinput[-1] == '\n') )
	488	{
	489	regtill--;
	490	break;
	491	}
	492	return(0);
	493	case EOL:
	494	if ((nextchar \|\| locinput < regeol) && nextchar != '\n')
	495	return(0);
	496	regtill--;
	497	break;
	498	case ANY:
	499	if ((nextchar == '\0' && locinput >= regeol) \|\|
	500	nextchar == '\n')
	501	return(0);
	502	nextchar = *++locinput;
	503	break;
	504	case EXACTLY:
	505	s = OPERAND(scan);
	506	ln = *s++;
	507	/* Inline the first character, for speed. */
	508	if (*s != nextchar)
	509	return(0);
	510	if (locinput + ln > regeol)
	511	return 0;
	512	if (ln > 1 && bcmp(s, locinput, ln) != 0)
	513	return(0);
	514	locinput += ln;
	515	nextchar = *locinput;
	516	break;
	517	case ANYOF:
	518	case ANYBUT:
	519	s = OPERAND(scan);
	520	if (nextchar < 0)
	521	nextchar = UCHARAT(locinput);
	522	if (s[nextchar >> 3] & (1 << (nextchar&7)))
	523	return(0);
	524	nextchar = *++locinput;
	525	if (!nextchar && locinput > regeol)
	526	return 0;
	527	break;
	528	case ALNUM:
	529	if (!nextchar)
	530	return(0);
ac58e20f	531	if (!isALNUM(nextchar))
a687059c LW	532	return(0);
	533	nextchar = *++locinput;
	534	break;
	535	case NALNUM:
	536	if (!nextchar && locinput >= regeol)
	537	return(0);
ac58e20f	538	if (isALNUM(nextchar))
a687059c LW	539	return(0);
	540	nextchar = *++locinput;
	541	break;
	542	case NBOUND:
	543	case BOUND:
	544	if (locinput == regbol) /* was last char in word? */
ac58e20f	545	ln = isALNUM(regprev);
a687059c	546	else
ac58e20f LW	547	ln = isALNUM(locinput[-1]);
ac58e20f LW	548	n = isALNUM(nextchar); /* is next char in word? */
a687059c LW	549	if ((ln == n) == (OP(scan) == BOUND))
	550	return(0);
	551	break;
	552	case SPACE:
	553	if (!nextchar && locinput >= regeol)
	554	return(0);
ac58e20f	555	if (!isSPACE(nextchar))
a687059c LW	556	return(0);
	557	nextchar = *++locinput;
	558	break;
	559	case NSPACE:
	560	if (!nextchar)
	561	return(0);
ac58e20f	562	if (isSPACE(nextchar))
a687059c LW	563	return(0);
	564	nextchar = *++locinput;
	565	break;
	566	case DIGIT:
ac58e20f	567	if (!isDIGIT(nextchar))
a687059c LW	568	return(0);
	569	nextchar = *++locinput;
	570	break;
	571	case NDIGIT:
	572	if (!nextchar && locinput >= regeol)
	573	return(0);
ac58e20f	574	if (isDIGIT(nextchar))
a687059c LW	575	return(0);
	576	nextchar = *++locinput;
	577	break;
	578	case REF:
	579	case REF+1:
	580	case REF+2:
	581	case REF+3:
	582	case REF+4:
	583	case REF+5:
	584	case REF+6:
	585	case REF+7:
	586	case REF+8:
	587	case REF+9:
	588	n = OP(scan) - REF;
	589	s = regmystartp[n];
	590	if (!s)
	591	return(0);
	592	if (!regmyendp[n])
	593	return(0);
	594	if (s == regmyendp[n])
	595	break;
	596	/* Inline the first character, for speed. */
	597	if (*s != nextchar)
	598	return(0);
	599	ln = regmyendp[n] - s;
	600	if (locinput + ln > regeol)
	601	return 0;
	602	if (ln > 1 && bcmp(s, locinput, ln) != 0)
	603	return(0);
	604	locinput += ln;
	605	nextchar = *locinput;
	606	break;
	607
	608	case NOTHING:
	609	break;
	610	case BACK:
	611	break;
	612	case OPEN+1:
	613	case OPEN+2:
	614	case OPEN+3:
	615	case OPEN+4:
	616	case OPEN+5:
	617	case OPEN+6:
	618	case OPEN+7:
	619	case OPEN+8:
	620	case OPEN+9:
	621	n = OP(scan) - OPEN;
	622	reginput = locinput;
	623
	624	regmystartp[n] = locinput; /* for REF */
	625	if (regmatch(next)) {
	626	/*
	627	* Don't set startp if some later
	628	* invocation of the same parentheses
	629	* already has.
	630	*/
	631	if (regstartp[n] == NULL)
	632	regstartp[n] = locinput;
	633	return(1);
	634	} else
	635	return(0);
	636	/* NOTREACHED */
	637	case CLOSE+1:
	638	case CLOSE+2:
639	case CLOSE+3:
640	case CLOSE+4:
641	case CLOSE+5:
642	case CLOSE+6:
643	case CLOSE+7:
644	case CLOSE+8:
645	case CLOSE+9: {
646	n = OP(scan) - CLOSE;
647	reginput = locinput;
648
649	regmyendp[n] = locinput; /* for REF */
650	if (regmatch(next)) {
651	/*
652	* Don't set endp if some later
653	* invocation of the same parentheses
654	* already has.
655	*/
656	if (regendp[n] == NULL) {
657	regendp[n] = locinput;
658	if (n > *reglastparen)
659	*reglastparen = n;
660	}
661	return(1);
662	} else
663	return(0);
664	}
665	/NOTREACHED/
666	case BRANCH: {
667	if (OP(next) != BRANCH) /* No choice. */
668	next = NEXTOPER(scan); /* Avoid recursion. */
669	else {
670	do {
671	reginput = locinput;
672	if (regmatch(NEXTOPER(scan)))
673	return(1);
674	#ifdef REGALIGN
675	if (n = NEXT(scan))
676	scan += n;
677	else
678	scan = NULL;
679	#else
680	scan = regnext(scan);
681	#endif
682	} while (scan != NULL && OP(scan) == BRANCH);
683	return(0);
684	/* NOTREACHED */
685	}
686	}
687	break;
688	case STAR:
689	case PLUS:
690	/*
691	* Lookahead to avoid useless match attempts
692	* when we know what character comes next.
693	*/
694	if (OP(next) == EXACTLY)
695	nextchar = *(OPERAND(next)+1);
696	else
697	nextchar = -1000;
698	ln = (OP(scan) == STAR) ? 0 : 1;
699	reginput = locinput;
700	n = regrepeat(NEXTOPER(scan));
701	while (n >= ln) {
702	/* If it could work, try it. */
703	if (nextchar == -1000 \|\| *reginput == nextchar)
704	if (regmatch(next))
705	return(1);
706	/* Couldn't or didn't -- back up. */
707	n--;
708	reginput = locinput + n;
709	}
710	return(0);
711	case END:
712	reginput = locinput; /* put where regtry can find it */
713	return(1); /* Success! */
714	default:
715	printf("%x %d\n",scan,scan[1]);
716	FAIL("regexp memory corruption");
717	}
718
719	scan = next;
720	}
721
722	/*
723	* We get here only if there's trouble -- normally "case END" is
724	* the terminating point.
725	*/
726	FAIL("corrupted regexp pointers");
727	/NOTREACHED/
728	#ifdef lint
729	return 0;
730	#endif
731	}
732
733	/*
734	- regrepeat - repeatedly match something simple, report how many
735	*/
736	/*
737	* [This routine now assumes that it will only match on things of length 1.
738	* That was true before, but now we assume scan - reginput is the count,
739	* rather than incrementing count on every character.]
740	*/
741	static int
742	regrepeat(p)
743	char *p;
744	{
745	register char *scan;
746	register char *opnd;
747	register int c;
748	register char *loceol = regeol;
749
750	scan = reginput;
751	opnd = OPERAND(p);
752	switch (OP(p)) {
753	case ANY:
754	while (scan < loceol && *scan != '\n')
755	scan++;
756	break;
757	case EXACTLY: /* length of string is 1 */
758	opnd++;
759	while (scan < loceol && opnd == scan)
760	scan++;
761	break;
762	case ANYOF:
763	case ANYBUT:
764	c = UCHARAT(scan);
765	while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
766	scan++;
767	c = UCHARAT(scan);
768	}
769	break;
770	case ALNUM:
ac58e20f	771	while (isALNUM(*scan))
a687059c LW	772	scan++;
	773	break;
	774	case NALNUM:
ac58e20f	775	while (scan < loceol && !isALNUM(*scan))
a687059c LW	776	scan++;
	777	break;
	778	case SPACE:
ac58e20f	779	while (scan < loceol && isSPACE(*scan))
a687059c LW	780	scan++;
	781	break;
	782	case NSPACE:
ac58e20f	783	while (scan < loceol && !isSPACE(*scan))
a687059c LW	784	scan++;
	785	break;
	786	case DIGIT:
ac58e20f	787	while (isDIGIT(*scan))
a687059c LW	788	scan++;
	789	break;
	790	case NDIGIT:
ac58e20f	791	while (scan < loceol && !isDIGIT(*scan))
a687059c LW	792	scan++;
	793	break;
	794	default: /* Oh dear. Called inappropriately. */
	795	FAIL("internal regexp foulup");
	796	/* NOTREACHED */
	797	}
	798
	799	c = scan - reginput;
	800	reginput = scan;
	801
	802	return(c);
	803	}
	804
	805	/*
	806	- regnext - dig the "next" pointer out of a node
	807	*
	808	* [Note, when REGALIGN is defined there are two places in regmatch()
	809	* that bypass this code for speed.]
	810	*/
	811	char *
	812	regnext(p)
	813	register char *p;
	814	{
	815	register int offset;
	816
	817	if (p == &regdummy)
	818	return(NULL);
	819
	820	offset = NEXT(p);
	821	if (offset == 0)
	822	return(NULL);
	823
	824	#ifdef REGALIGN
	825	return(p+offset);
	826	#else
	827	if (OP(p) == BACK)
	828	return(p-offset);
	829	else
	830	return(p+offset);
	831	#endif
	832	}