regexec.c

早期freebsd实现

		    i = strend - string + (stringarg - strbeg);
		    s = nsavestr(strbeg,i);	/* so $digit will work later */
		    if (prog->subbase)
			    Safefree(prog->subbase);
		    prog->subbeg = prog->subbase = s;
		    prog->subend = s+i;
		}
		else {
		    i = strend - string + (stringarg - strbeg);
		    prog->subbeg = s = prog->subbase;
		    prog->subend = s+i;
		}
		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 = prog->nparens; 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 = regbol; */
				break;
			}
			return(0);
		case EOL:
			if ((nextchar || locinput < regeol) && nextchar != '\n')
				return(0);
			if (!multiline && regeol - locinput > 1)
				return 0;
			/* regtill = regbol; */
			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 (regeol - locinput < ln)
				return 0;
			if (ln > 1 && bcmp(s, locinput, ln) != 0)
				return(0);
			locinput += ln;
			nextchar = *locinput;
			break;
		case ANYOF:
			s = OPERAND(scan);
			if (nextchar < 0)
				nextchar = UCHARAT(locinput);
			if (s[nextchar >> 3] & (1 << (nextchar&7)))
				return(0);
			if (!nextchar && locinput >= regeol)
				return 0;
			nextchar = *++locinput;
			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:
			n = ARG1(scan);  /* which paren pair */
			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:
			n = ARG1(scan);  /* which paren pair */
			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: {
				n = ARG1(scan);  /* which paren pair */
				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
						/*SUPPRESS 560*/
						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 CURLY:
			ln = ARG1(scan);  /* min to match */
			n  = ARG2(scan);  /* max to match */
			scan = NEXTOPER(scan) + 4;
			goto repeat;
		case STAR:
			ln = 0;
			n = 32767;
			scan = NEXTOPER(scan);
			goto repeat;
		case PLUS:
			/*
			 * Lookahead to avoid useless match attempts
			 * when we know what character comes next.
			 */
			ln = 1;
			n = 32767;
			scan = NEXTOPER(scan);
		    repeat:
			if (OP(next) == EXACTLY)
				nextchar = *(OPERAND(next)+1);
			else
				nextchar = -1000;
			reginput = locinput;
			n = regrepeat(scan, n);
			if (!multiline && OP(next) == EOL && ln < n)
			    ln = n;			/* why back off? */
			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, max)
char *p;
int max;
{
	register char *scan;
	register char *opnd;
	register int c;
	register char *loceol = regeol;

	scan = reginput;
	if (max != 32767 && max < loceol - scan)
	    loceol = scan + max;
	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:
		c = UCHARAT(scan);
		while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
			scan++;
			c = UCHARAT(scan);
		}
		break;
	case ALNUM:
		while (scan < loceol && 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 (scan < loceol && 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
}