xref: /minix3/external/bsd/nvi/dist/regex/engine.c (revision 0a6a1f1d05b60e214de2f05a7310ddd1f0e590e7)
1*0a6a1f1dSLionel Sambuc /*	$NetBSD: engine.c,v 1.3 2014/01/07 21:48:12 christos Exp $ */
284d9c625SLionel Sambuc /*-
384d9c625SLionel Sambuc  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
484d9c625SLionel Sambuc  * Copyright (c) 1992, 1993, 1994
584d9c625SLionel Sambuc  *	The Regents of the University of California.  All rights reserved.
684d9c625SLionel Sambuc  *
784d9c625SLionel Sambuc  * This code is derived from software contributed to Berkeley by
884d9c625SLionel Sambuc  * Henry Spencer of the University of Toronto.
984d9c625SLionel Sambuc  *
1084d9c625SLionel Sambuc  * Redistribution and use in source and binary forms, with or without
1184d9c625SLionel Sambuc  * modification, are permitted provided that the following conditions
1284d9c625SLionel Sambuc  * are met:
1384d9c625SLionel Sambuc  * 1. Redistributions of source code must retain the above copyright
1484d9c625SLionel Sambuc  *    notice, this list of conditions and the following disclaimer.
1584d9c625SLionel Sambuc  * 2. Redistributions in binary form must reproduce the above copyright
1684d9c625SLionel Sambuc  *    notice, this list of conditions and the following disclaimer in the
1784d9c625SLionel Sambuc  *    documentation and/or other materials provided with the distribution.
1884d9c625SLionel Sambuc  * 3. All advertising materials mentioning features or use of this software
1984d9c625SLionel Sambuc  *    must display the following acknowledgement:
2084d9c625SLionel Sambuc  *	This product includes software developed by the University of
2184d9c625SLionel Sambuc  *	California, Berkeley and its contributors.
2284d9c625SLionel Sambuc  * 4. Neither the name of the University nor the names of its contributors
2384d9c625SLionel Sambuc  *    may be used to endorse or promote products derived from this software
2484d9c625SLionel Sambuc  *    without specific prior written permission.
2584d9c625SLionel Sambuc  *
2684d9c625SLionel Sambuc  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
2784d9c625SLionel Sambuc  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
2884d9c625SLionel Sambuc  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2984d9c625SLionel Sambuc  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
3084d9c625SLionel Sambuc  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
3184d9c625SLionel Sambuc  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
3284d9c625SLionel Sambuc  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
3384d9c625SLionel Sambuc  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
3484d9c625SLionel Sambuc  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
3584d9c625SLionel Sambuc  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
3684d9c625SLionel Sambuc  * SUCH DAMAGE.
3784d9c625SLionel Sambuc  *
3884d9c625SLionel Sambuc  *	@(#)engine.c	8.4 (Berkeley) 3/19/94
3984d9c625SLionel Sambuc  */
4084d9c625SLionel Sambuc 
4184d9c625SLionel Sambuc /*
4284d9c625SLionel Sambuc  * The matching engine and friends.  This file is #included by regexec.c
4384d9c625SLionel Sambuc  * after suitable #defines of a variety of macros used herein, so that
4484d9c625SLionel Sambuc  * different state representations can be used without duplicating masses
4584d9c625SLionel Sambuc  * of code.
4684d9c625SLionel Sambuc  */
4784d9c625SLionel Sambuc 
4884d9c625SLionel Sambuc #ifdef SNAMES
4984d9c625SLionel Sambuc #define	matcher	smatcher
5084d9c625SLionel Sambuc #define	fast	sfast
5184d9c625SLionel Sambuc #define	slow	sslow
5284d9c625SLionel Sambuc #define	dissect	sdissect
5384d9c625SLionel Sambuc #define	backref	sbackref
5484d9c625SLionel Sambuc #define	step	sstep
5584d9c625SLionel Sambuc #define	print	sprint
5684d9c625SLionel Sambuc #define	at	sat
5784d9c625SLionel Sambuc #define	match	smat
5884d9c625SLionel Sambuc #endif
5984d9c625SLionel Sambuc #ifdef LNAMES
6084d9c625SLionel Sambuc #define	matcher	lmatcher
6184d9c625SLionel Sambuc #define	fast	lfast
6284d9c625SLionel Sambuc #define	slow	lslow
6384d9c625SLionel Sambuc #define	dissect	ldissect
6484d9c625SLionel Sambuc #define	backref	lbackref
6584d9c625SLionel Sambuc #define	step	lstep
6684d9c625SLionel Sambuc #define	print	lprint
6784d9c625SLionel Sambuc #define	at	lat
6884d9c625SLionel Sambuc #define	match	lmat
6984d9c625SLionel Sambuc #endif
7084d9c625SLionel Sambuc 
7184d9c625SLionel Sambuc /* another structure passed up and down to avoid zillions of parameters */
7284d9c625SLionel Sambuc struct match {
7384d9c625SLionel Sambuc 	struct re_guts *g;
7484d9c625SLionel Sambuc 	int eflags;
7584d9c625SLionel Sambuc 	regmatch_t *pmatch;	/* [nsub+1] (0 element unused) */
7684d9c625SLionel Sambuc 	RCHAR_T *offp;		/* offsets work from here */
7784d9c625SLionel Sambuc 	RCHAR_T *beginp;		/* start of string -- virtual NUL precedes */
7884d9c625SLionel Sambuc 	RCHAR_T *endp;		/* end of string -- virtual NUL here */
7984d9c625SLionel Sambuc 	RCHAR_T *coldp;		/* can be no match starting before here */
8084d9c625SLionel Sambuc 	RCHAR_T **lastpos;	/* [nplus+1] */
8184d9c625SLionel Sambuc 	STATEVARS;
8284d9c625SLionel Sambuc 	states st;		/* current states */
8384d9c625SLionel Sambuc 	states fresh;		/* states for a fresh start */
8484d9c625SLionel Sambuc 	states tmp;		/* temporary */
8584d9c625SLionel Sambuc 	states empty;		/* empty set of states */
8684d9c625SLionel Sambuc };
8784d9c625SLionel Sambuc 
8884d9c625SLionel Sambuc /* ========= begin header generated by ./mkh ========= */
8984d9c625SLionel Sambuc #ifdef __cplusplus
9084d9c625SLionel Sambuc extern "C" {
9184d9c625SLionel Sambuc #endif
9284d9c625SLionel Sambuc 
9384d9c625SLionel Sambuc /* === engine.c === */
9484d9c625SLionel Sambuc static int matcher __P((struct re_guts *g, RCHAR_T *string, size_t nmatch, regmatch_t pmatch[], int eflags));
9584d9c625SLionel Sambuc static RCHAR_T *dissect __P((struct match *m, RCHAR_T *start, RCHAR_T *stop, sopno startst, sopno stopst));
9684d9c625SLionel Sambuc static RCHAR_T *backref __P((struct match *m, RCHAR_T *start, RCHAR_T *stop, sopno startst, sopno stopst, sopno lev));
9784d9c625SLionel Sambuc static RCHAR_T *fast __P((struct match *m, RCHAR_T *start, RCHAR_T *stop, sopno startst, sopno stopst));
9884d9c625SLionel Sambuc static RCHAR_T *slow __P((struct match *m, RCHAR_T *start, RCHAR_T *stop, sopno startst, sopno stopst));
9984d9c625SLionel Sambuc static states step __P((struct re_guts *g, sopno start, sopno stop, states bef, int flag, RCHAR_T ch, states aft));
10084d9c625SLionel Sambuc #define	BOL	(1)
10184d9c625SLionel Sambuc #define	EOL	(BOL+1)
10284d9c625SLionel Sambuc #define	BOLEOL	(BOL+2)
10384d9c625SLionel Sambuc #define	NOTHING	(BOL+3)
10484d9c625SLionel Sambuc #define	BOW	(BOL+4)
10584d9c625SLionel Sambuc #define	EOW	(BOL+5)
10684d9c625SLionel Sambuc #ifdef REDEBUG
10784d9c625SLionel Sambuc static void print __P((struct match *m, char *caption, states st, int ch, FILE *d));
10884d9c625SLionel Sambuc #endif
10984d9c625SLionel Sambuc #ifdef REDEBUG
11084d9c625SLionel Sambuc static void at __P((struct match *m, char *title, char *start, char *stop, sopno startst, sopno stopst));
11184d9c625SLionel Sambuc #endif
11284d9c625SLionel Sambuc #ifdef REDEBUG
11384d9c625SLionel Sambuc static char *pchar __P((int ch));
11484d9c625SLionel Sambuc #endif
11584d9c625SLionel Sambuc 
11684d9c625SLionel Sambuc #ifdef __cplusplus
11784d9c625SLionel Sambuc }
11884d9c625SLionel Sambuc #endif
11984d9c625SLionel Sambuc /* ========= end header generated by ./mkh ========= */
12084d9c625SLionel Sambuc 
12184d9c625SLionel Sambuc #ifdef REDEBUG
12284d9c625SLionel Sambuc #define	SP(t, s, c)	print(m, t, s, c, stdout)
12384d9c625SLionel Sambuc #define	AT(t, p1, p2, s1, s2)	at(m, t, p1, p2, s1, s2)
12484d9c625SLionel Sambuc #define	NOTE(str)	{ if (m->eflags&REG_TRACE) printf("=%s\n", (str)); }
12584d9c625SLionel Sambuc #else
12684d9c625SLionel Sambuc #define	SP(t, s, c)	/* nothing */
12784d9c625SLionel Sambuc #define	AT(t, p1, p2, s1, s2)	/* nothing */
12884d9c625SLionel Sambuc #define	NOTE(s)	/* nothing */
12984d9c625SLionel Sambuc #endif
13084d9c625SLionel Sambuc 
13184d9c625SLionel Sambuc /*
13284d9c625SLionel Sambuc  - matcher - the actual matching engine
133*0a6a1f1dSLionel Sambuc  == static int matcher(struct re_guts *g, RCHAR_T *string, \
13484d9c625SLionel Sambuc  ==	size_t nmatch, regmatch_t pmatch[], int eflags);
13584d9c625SLionel Sambuc  */
13684d9c625SLionel Sambuc static int			/* 0 success, REG_NOMATCH failure */
matcher(g,string,nmatch,pmatch,eflags)13784d9c625SLionel Sambuc matcher(g, string, nmatch, pmatch, eflags)
138*0a6a1f1dSLionel Sambuc struct re_guts *g;
13984d9c625SLionel Sambuc RCHAR_T *string;
14084d9c625SLionel Sambuc size_t nmatch;
14184d9c625SLionel Sambuc regmatch_t pmatch[];
14284d9c625SLionel Sambuc int eflags;
14384d9c625SLionel Sambuc {
144*0a6a1f1dSLionel Sambuc 	RCHAR_T *endp;
145*0a6a1f1dSLionel Sambuc 	size_t i;
14684d9c625SLionel Sambuc 	struct match mv;
147*0a6a1f1dSLionel Sambuc 	struct match *m = &mv;
148*0a6a1f1dSLionel Sambuc 	RCHAR_T *dp;
149*0a6a1f1dSLionel Sambuc 	const sopno gf = g->firststate+1;	/* +1 for OEND */
150*0a6a1f1dSLionel Sambuc 	const sopno gl = g->laststate;
15184d9c625SLionel Sambuc 	RCHAR_T *start;
15284d9c625SLionel Sambuc 	RCHAR_T *stop;
15384d9c625SLionel Sambuc 
15484d9c625SLionel Sambuc 	/* simplify the situation where possible */
15584d9c625SLionel Sambuc 	if (g->cflags&REG_NOSUB)
15684d9c625SLionel Sambuc 		nmatch = 0;
15784d9c625SLionel Sambuc 	if (eflags&REG_STARTEND) {
15884d9c625SLionel Sambuc 		start = string + pmatch[0].rm_so;
15984d9c625SLionel Sambuc 		stop = string + pmatch[0].rm_eo;
16084d9c625SLionel Sambuc 	} else {
16184d9c625SLionel Sambuc 		start = string;
16284d9c625SLionel Sambuc 		stop = start + STRLEN(start);
16384d9c625SLionel Sambuc 	}
16484d9c625SLionel Sambuc 	if (stop < start)
16584d9c625SLionel Sambuc 		return(REG_INVARG);
16684d9c625SLionel Sambuc 
16784d9c625SLionel Sambuc 	/* prescreening; this does wonders for this rather slow code */
16884d9c625SLionel Sambuc 	if (g->must != NULL) {
16984d9c625SLionel Sambuc 		for (dp = start; dp < stop; dp++)
17084d9c625SLionel Sambuc 			if (*dp == g->must[0] && (size_t)(stop - dp) >= g->mlen &&
17184d9c625SLionel Sambuc 				MEMCMP(dp, g->must, g->mlen) == 0)
17284d9c625SLionel Sambuc 				break;
17384d9c625SLionel Sambuc 		if (dp == stop)		/* we didn't find g->must */
17484d9c625SLionel Sambuc 			return(REG_NOMATCH);
17584d9c625SLionel Sambuc 	}
17684d9c625SLionel Sambuc 
17784d9c625SLionel Sambuc 	/* match struct setup */
17884d9c625SLionel Sambuc 	m->g = g;
17984d9c625SLionel Sambuc 	m->eflags = eflags;
18084d9c625SLionel Sambuc 	m->pmatch = NULL;
18184d9c625SLionel Sambuc 	m->lastpos = NULL;
18284d9c625SLionel Sambuc 	m->offp = string;
18384d9c625SLionel Sambuc 	m->beginp = start;
18484d9c625SLionel Sambuc 	m->endp = stop;
18584d9c625SLionel Sambuc 	STATESETUP(m, 4);
18684d9c625SLionel Sambuc 	SETUP(m->st);
18784d9c625SLionel Sambuc 	SETUP(m->fresh);
18884d9c625SLionel Sambuc 	SETUP(m->tmp);
18984d9c625SLionel Sambuc 	SETUP(m->empty);
19084d9c625SLionel Sambuc 	CLEAR(m->empty);
19184d9c625SLionel Sambuc 
19284d9c625SLionel Sambuc 	/* this loop does only one repetition except for backrefs */
19384d9c625SLionel Sambuc 	for (;;) {
19484d9c625SLionel Sambuc 		endp = fast(m, start, stop, gf, gl);
19584d9c625SLionel Sambuc 		if (endp == NULL) {		/* a miss */
19684d9c625SLionel Sambuc 			STATETEARDOWN(m);
19784d9c625SLionel Sambuc 			return(REG_NOMATCH);
19884d9c625SLionel Sambuc 		}
19984d9c625SLionel Sambuc 		if (nmatch == 0 && !g->backrefs)
20084d9c625SLionel Sambuc 			break;		/* no further info needed */
20184d9c625SLionel Sambuc 
20284d9c625SLionel Sambuc 		/* where? */
20384d9c625SLionel Sambuc 		assert(m->coldp != NULL);
20484d9c625SLionel Sambuc 		for (;;) {
20584d9c625SLionel Sambuc 			NOTE("finding start");
20684d9c625SLionel Sambuc 			endp = slow(m, m->coldp, stop, gf, gl);
20784d9c625SLionel Sambuc 			if (endp != NULL)
20884d9c625SLionel Sambuc 				break;
20984d9c625SLionel Sambuc 			assert(m->coldp < m->endp);
21084d9c625SLionel Sambuc 			m->coldp++;
21184d9c625SLionel Sambuc 		}
21284d9c625SLionel Sambuc 		if (nmatch == 1 && !g->backrefs)
21384d9c625SLionel Sambuc 			break;		/* no further info needed */
21484d9c625SLionel Sambuc 
21584d9c625SLionel Sambuc 		/* oh my, he wants the subexpressions... */
21684d9c625SLionel Sambuc 		if (m->pmatch == NULL)
21784d9c625SLionel Sambuc 			m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) *
21884d9c625SLionel Sambuc 							sizeof(regmatch_t));
21984d9c625SLionel Sambuc 		if (m->pmatch == NULL) {
22084d9c625SLionel Sambuc 			STATETEARDOWN(m);
22184d9c625SLionel Sambuc 			return(REG_ESPACE);
22284d9c625SLionel Sambuc 		}
22384d9c625SLionel Sambuc 		for (i = 1; i <= m->g->nsub; i++)
22484d9c625SLionel Sambuc 			m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
22584d9c625SLionel Sambuc 		if (!g->backrefs && !(m->eflags&REG_BACKR)) {
22684d9c625SLionel Sambuc 			NOTE("dissecting");
22784d9c625SLionel Sambuc 			dp = dissect(m, m->coldp, endp, gf, gl);
22884d9c625SLionel Sambuc 		} else {
22984d9c625SLionel Sambuc 			if (g->nplus > 0 && m->lastpos == NULL)
23084d9c625SLionel Sambuc 				m->lastpos = (RCHAR_T **)malloc((g->nplus+1) *
23184d9c625SLionel Sambuc 							sizeof(RCHAR_T *));
23284d9c625SLionel Sambuc 			if (g->nplus > 0 && m->lastpos == NULL) {
23384d9c625SLionel Sambuc 				free(m->pmatch);
23484d9c625SLionel Sambuc 				STATETEARDOWN(m);
23584d9c625SLionel Sambuc 				return(REG_ESPACE);
23684d9c625SLionel Sambuc 			}
23784d9c625SLionel Sambuc 			NOTE("backref dissect");
23884d9c625SLionel Sambuc 			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
23984d9c625SLionel Sambuc 		}
24084d9c625SLionel Sambuc 		if (dp != NULL)
24184d9c625SLionel Sambuc 			break;
24284d9c625SLionel Sambuc 
24384d9c625SLionel Sambuc 		/* uh-oh... we couldn't find a subexpression-level match */
24484d9c625SLionel Sambuc 		assert(g->backrefs);	/* must be back references doing it */
24584d9c625SLionel Sambuc 		assert(g->nplus == 0 || m->lastpos != NULL);
24684d9c625SLionel Sambuc 		for (;;) {
24784d9c625SLionel Sambuc 			if (dp != NULL || endp <= m->coldp)
24884d9c625SLionel Sambuc 				break;		/* defeat */
24984d9c625SLionel Sambuc 			NOTE("backoff");
25084d9c625SLionel Sambuc 			endp = slow(m, m->coldp, endp-1, gf, gl);
25184d9c625SLionel Sambuc 			if (endp == NULL)
25284d9c625SLionel Sambuc 				break;		/* defeat */
25384d9c625SLionel Sambuc 			/* try it on a shorter possibility */
25484d9c625SLionel Sambuc #ifndef NDEBUG
25584d9c625SLionel Sambuc 			for (i = 1; i <= m->g->nsub; i++) {
25684d9c625SLionel Sambuc 				assert(m->pmatch[i].rm_so == -1);
25784d9c625SLionel Sambuc 				assert(m->pmatch[i].rm_eo == -1);
25884d9c625SLionel Sambuc 			}
25984d9c625SLionel Sambuc #endif
26084d9c625SLionel Sambuc 			NOTE("backoff dissect");
26184d9c625SLionel Sambuc 			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
26284d9c625SLionel Sambuc 		}
26384d9c625SLionel Sambuc 		assert(dp == NULL || dp == endp);
26484d9c625SLionel Sambuc 		if (dp != NULL)		/* found a shorter one */
26584d9c625SLionel Sambuc 			break;
26684d9c625SLionel Sambuc 
26784d9c625SLionel Sambuc 		/* despite initial appearances, there is no match here */
26884d9c625SLionel Sambuc 		NOTE("false alarm");
26984d9c625SLionel Sambuc 		start = m->coldp + 1;	/* recycle starting later */
27084d9c625SLionel Sambuc 		assert(start <= stop);
27184d9c625SLionel Sambuc 	}
27284d9c625SLionel Sambuc 
27384d9c625SLionel Sambuc 	/* fill in the details if requested */
27484d9c625SLionel Sambuc 	if (nmatch > 0) {
27584d9c625SLionel Sambuc 		pmatch[0].rm_so = m->coldp - m->offp;
27684d9c625SLionel Sambuc 		pmatch[0].rm_eo = endp - m->offp;
27784d9c625SLionel Sambuc 	}
27884d9c625SLionel Sambuc 	if (nmatch > 1) {
27984d9c625SLionel Sambuc 		assert(m->pmatch != NULL);
28084d9c625SLionel Sambuc 		for (i = 1; i < nmatch; i++)
28184d9c625SLionel Sambuc 			if (i <= m->g->nsub)
28284d9c625SLionel Sambuc 				pmatch[i] = m->pmatch[i];
28384d9c625SLionel Sambuc 			else {
28484d9c625SLionel Sambuc 				pmatch[i].rm_so = -1;
28584d9c625SLionel Sambuc 				pmatch[i].rm_eo = -1;
28684d9c625SLionel Sambuc 			}
28784d9c625SLionel Sambuc 	}
28884d9c625SLionel Sambuc 
28984d9c625SLionel Sambuc 	if (m->pmatch != NULL)
29084d9c625SLionel Sambuc 		free((char *)m->pmatch);
29184d9c625SLionel Sambuc 	if (m->lastpos != NULL)
29284d9c625SLionel Sambuc 		free((char *)m->lastpos);
29384d9c625SLionel Sambuc 	STATETEARDOWN(m);
29484d9c625SLionel Sambuc 	return(0);
29584d9c625SLionel Sambuc }
29684d9c625SLionel Sambuc 
29784d9c625SLionel Sambuc /*
29884d9c625SLionel Sambuc  - dissect - figure out what matched what, no back references
299*0a6a1f1dSLionel Sambuc  == static RCHAR_T *dissect(struct match *m, RCHAR_T *start, \
30084d9c625SLionel Sambuc  ==	RCHAR_T *stop, sopno startst, sopno stopst);
30184d9c625SLionel Sambuc  */
30284d9c625SLionel Sambuc static RCHAR_T *			/* == stop (success) always */
dissect(m,start,stop,startst,stopst)30384d9c625SLionel Sambuc dissect(m, start, stop, startst, stopst)
304*0a6a1f1dSLionel Sambuc struct match *m;
30584d9c625SLionel Sambuc RCHAR_T *start;
30684d9c625SLionel Sambuc RCHAR_T *stop;
30784d9c625SLionel Sambuc sopno startst;
30884d9c625SLionel Sambuc sopno stopst;
30984d9c625SLionel Sambuc {
310*0a6a1f1dSLionel Sambuc 	int i;
311*0a6a1f1dSLionel Sambuc 	sopno ss;	/* start sop of current subRE */
312*0a6a1f1dSLionel Sambuc 	sopno es;	/* end sop of current subRE */
313*0a6a1f1dSLionel Sambuc 	RCHAR_T *sp;	/* start of string matched by it */
314*0a6a1f1dSLionel Sambuc 	RCHAR_T *stp;	/* string matched by it cannot pass here */
315*0a6a1f1dSLionel Sambuc 	RCHAR_T *rest;	/* start of rest of string */
316*0a6a1f1dSLionel Sambuc 	RCHAR_T *tail;	/* string unmatched by rest of RE */
317*0a6a1f1dSLionel Sambuc 	sopno ssub;	/* start sop of subsubRE */
318*0a6a1f1dSLionel Sambuc 	sopno esub;	/* end sop of subsubRE */
319*0a6a1f1dSLionel Sambuc 	RCHAR_T *ssp;	/* start of string matched by subsubRE */
320*0a6a1f1dSLionel Sambuc 	RCHAR_T *sep;	/* end of string matched by subsubRE */
321*0a6a1f1dSLionel Sambuc 	RCHAR_T *oldssp;	/* previous ssp */
322*0a6a1f1dSLionel Sambuc 	RCHAR_T *dp;
32384d9c625SLionel Sambuc 
32484d9c625SLionel Sambuc 	AT("diss", start, stop, startst, stopst);
32584d9c625SLionel Sambuc 	sp = start;
32684d9c625SLionel Sambuc 	for (ss = startst; ss < stopst; ss = es) {
32784d9c625SLionel Sambuc 		/* identify end of subRE */
32884d9c625SLionel Sambuc 		es = ss;
32984d9c625SLionel Sambuc 		switch (m->g->strip[es]) {
33084d9c625SLionel Sambuc 		case OPLUS_:
33184d9c625SLionel Sambuc 		case OQUEST_:
33284d9c625SLionel Sambuc 			es += m->g->stripdata[es];
33384d9c625SLionel Sambuc 			break;
33484d9c625SLionel Sambuc 		case OCH_:
33584d9c625SLionel Sambuc 			while (m->g->strip[es] != O_CH)
33684d9c625SLionel Sambuc 				es += m->g->stripdata[es];
33784d9c625SLionel Sambuc 			break;
33884d9c625SLionel Sambuc 		}
33984d9c625SLionel Sambuc 		es++;
34084d9c625SLionel Sambuc 
34184d9c625SLionel Sambuc 		/* figure out what it matched */
34284d9c625SLionel Sambuc 		switch (m->g->strip[ss]) {
34384d9c625SLionel Sambuc 		case OEND:
34484d9c625SLionel Sambuc 			assert(nope);
34584d9c625SLionel Sambuc 			break;
34684d9c625SLionel Sambuc 		case OCHAR:
34784d9c625SLionel Sambuc 			sp++;
34884d9c625SLionel Sambuc 			break;
34984d9c625SLionel Sambuc 		case OBOL:
35084d9c625SLionel Sambuc 		case OEOL:
35184d9c625SLionel Sambuc 		case OBOW:
35284d9c625SLionel Sambuc 		case OEOW:
35384d9c625SLionel Sambuc 			break;
35484d9c625SLionel Sambuc 		case OANY:
35584d9c625SLionel Sambuc 		case OANYOF:
35684d9c625SLionel Sambuc 			sp++;
35784d9c625SLionel Sambuc 			break;
35884d9c625SLionel Sambuc 		case OBACK_:
35984d9c625SLionel Sambuc 		case O_BACK:
36084d9c625SLionel Sambuc 			assert(nope);
36184d9c625SLionel Sambuc 			break;
36284d9c625SLionel Sambuc 		/* cases where length of match is hard to find */
36384d9c625SLionel Sambuc 		case OQUEST_:
36484d9c625SLionel Sambuc 			stp = stop;
36584d9c625SLionel Sambuc 			for (;;) {
36684d9c625SLionel Sambuc 				/* how long could this one be? */
36784d9c625SLionel Sambuc 				rest = slow(m, sp, stp, ss, es);
36884d9c625SLionel Sambuc 				assert(rest != NULL);	/* it did match */
36984d9c625SLionel Sambuc 				/* could the rest match the rest? */
37084d9c625SLionel Sambuc 				tail = slow(m, rest, stop, es, stopst);
37184d9c625SLionel Sambuc 				if (tail == stop)
37284d9c625SLionel Sambuc 					break;		/* yes! */
37384d9c625SLionel Sambuc 				/* no -- try a shorter match for this one */
37484d9c625SLionel Sambuc 				stp = rest - 1;
37584d9c625SLionel Sambuc 				assert(stp >= sp);	/* it did work */
37684d9c625SLionel Sambuc 			}
37784d9c625SLionel Sambuc 			ssub = ss + 1;
37884d9c625SLionel Sambuc 			esub = es - 1;
37984d9c625SLionel Sambuc 			/* did innards match? */
38084d9c625SLionel Sambuc 			if (slow(m, sp, rest, ssub, esub) != NULL) {
38184d9c625SLionel Sambuc 				dp = dissect(m, sp, rest, ssub, esub);
38284d9c625SLionel Sambuc 				__USE(dp);
38384d9c625SLionel Sambuc 				assert(dp == rest);
38484d9c625SLionel Sambuc 			} else		/* no */
38584d9c625SLionel Sambuc 				assert(sp == rest);
38684d9c625SLionel Sambuc 			sp = rest;
38784d9c625SLionel Sambuc 			break;
38884d9c625SLionel Sambuc 		case OPLUS_:
38984d9c625SLionel Sambuc 			stp = stop;
39084d9c625SLionel Sambuc 			for (;;) {
39184d9c625SLionel Sambuc 				/* how long could this one be? */
39284d9c625SLionel Sambuc 				rest = slow(m, sp, stp, ss, es);
39384d9c625SLionel Sambuc 				assert(rest != NULL);	/* it did match */
39484d9c625SLionel Sambuc 				/* could the rest match the rest? */
39584d9c625SLionel Sambuc 				tail = slow(m, rest, stop, es, stopst);
39684d9c625SLionel Sambuc 				if (tail == stop)
39784d9c625SLionel Sambuc 					break;		/* yes! */
39884d9c625SLionel Sambuc 				/* no -- try a shorter match for this one */
39984d9c625SLionel Sambuc 				stp = rest - 1;
40084d9c625SLionel Sambuc 				assert(stp >= sp);	/* it did work */
40184d9c625SLionel Sambuc 			}
40284d9c625SLionel Sambuc 			ssub = ss + 1;
40384d9c625SLionel Sambuc 			esub = es - 1;
40484d9c625SLionel Sambuc 			ssp = sp;
40584d9c625SLionel Sambuc 			oldssp = ssp;
40684d9c625SLionel Sambuc 			for (;;) {	/* find last match of innards */
40784d9c625SLionel Sambuc 				sep = slow(m, ssp, rest, ssub, esub);
40884d9c625SLionel Sambuc 				if (sep == NULL || sep == ssp)
40984d9c625SLionel Sambuc 					break;	/* failed or matched null */
41084d9c625SLionel Sambuc 				oldssp = ssp;	/* on to next try */
41184d9c625SLionel Sambuc 				ssp = sep;
41284d9c625SLionel Sambuc 			}
41384d9c625SLionel Sambuc 			if (sep == NULL) {
41484d9c625SLionel Sambuc 				/* last successful match */
41584d9c625SLionel Sambuc 				sep = ssp;
41684d9c625SLionel Sambuc 				ssp = oldssp;
41784d9c625SLionel Sambuc 			}
41884d9c625SLionel Sambuc 			assert(sep == rest);	/* must exhaust substring */
41984d9c625SLionel Sambuc 			assert(slow(m, ssp, sep, ssub, esub) == rest);
42084d9c625SLionel Sambuc 			dp = dissect(m, ssp, sep, ssub, esub);
42184d9c625SLionel Sambuc 			assert(dp == sep);
42284d9c625SLionel Sambuc 			sp = rest;
42384d9c625SLionel Sambuc 			break;
42484d9c625SLionel Sambuc 		case OCH_:
42584d9c625SLionel Sambuc 			stp = stop;
42684d9c625SLionel Sambuc 			for (;;) {
42784d9c625SLionel Sambuc 				/* how long could this one be? */
42884d9c625SLionel Sambuc 				rest = slow(m, sp, stp, ss, es);
42984d9c625SLionel Sambuc 				assert(rest != NULL);	/* it did match */
43084d9c625SLionel Sambuc 				/* could the rest match the rest? */
43184d9c625SLionel Sambuc 				tail = slow(m, rest, stop, es, stopst);
43284d9c625SLionel Sambuc 				if (tail == stop)
43384d9c625SLionel Sambuc 					break;		/* yes! */
43484d9c625SLionel Sambuc 				/* no -- try a shorter match for this one */
43584d9c625SLionel Sambuc 				stp = rest - 1;
43684d9c625SLionel Sambuc 				assert(stp >= sp);	/* it did work */
43784d9c625SLionel Sambuc 			}
43884d9c625SLionel Sambuc 			ssub = ss + 1;
43984d9c625SLionel Sambuc 			esub = ss + m->g->stripdata[ss] - 1;
44084d9c625SLionel Sambuc 			assert(m->g->strip[esub] == OOR1);
44184d9c625SLionel Sambuc 			for (;;) {	/* find first matching branch */
44284d9c625SLionel Sambuc 				if (slow(m, sp, rest, ssub, esub) == rest)
44384d9c625SLionel Sambuc 					break;	/* it matched all of it */
44484d9c625SLionel Sambuc 				/* that one missed, try next one */
44584d9c625SLionel Sambuc 				assert(m->g->strip[esub] == OOR1);
44684d9c625SLionel Sambuc 				esub++;
44784d9c625SLionel Sambuc 				assert(m->g->strip[esub] == OOR2);
44884d9c625SLionel Sambuc 				ssub = esub + 1;
44984d9c625SLionel Sambuc 				esub += m->g->stripdata[esub];
45084d9c625SLionel Sambuc 				if (m->g->strip[esub] == OOR2)
45184d9c625SLionel Sambuc 					esub--;
45284d9c625SLionel Sambuc 				else
45384d9c625SLionel Sambuc 					assert(m->g->strip[esub] == O_CH);
45484d9c625SLionel Sambuc 			}
45584d9c625SLionel Sambuc 			dp = dissect(m, sp, rest, ssub, esub);
45684d9c625SLionel Sambuc 			assert(dp == rest);
45784d9c625SLionel Sambuc 			sp = rest;
45884d9c625SLionel Sambuc 			break;
45984d9c625SLionel Sambuc 		case O_PLUS:
46084d9c625SLionel Sambuc 		case O_QUEST:
46184d9c625SLionel Sambuc 		case OOR1:
46284d9c625SLionel Sambuc 		case OOR2:
46384d9c625SLionel Sambuc 		case O_CH:
46484d9c625SLionel Sambuc 			assert(nope);
46584d9c625SLionel Sambuc 			break;
46684d9c625SLionel Sambuc 		case OLPAREN:
46784d9c625SLionel Sambuc 			i = m->g->stripdata[ss];
46884d9c625SLionel Sambuc 			assert(0 < i && i <= m->g->nsub);
46984d9c625SLionel Sambuc 			m->pmatch[i].rm_so = sp - m->offp;
47084d9c625SLionel Sambuc 			break;
47184d9c625SLionel Sambuc 		case ORPAREN:
47284d9c625SLionel Sambuc 			i = m->g->stripdata[ss];
47384d9c625SLionel Sambuc 			assert(0 < i && i <= m->g->nsub);
47484d9c625SLionel Sambuc 			m->pmatch[i].rm_eo = sp - m->offp;
47584d9c625SLionel Sambuc 			break;
47684d9c625SLionel Sambuc 		default:		/* uh oh */
47784d9c625SLionel Sambuc 			assert(nope);
47884d9c625SLionel Sambuc 			break;
47984d9c625SLionel Sambuc 		}
48084d9c625SLionel Sambuc 	}
48184d9c625SLionel Sambuc 
48284d9c625SLionel Sambuc 	assert(sp == stop);
48384d9c625SLionel Sambuc 	return(sp);
48484d9c625SLionel Sambuc }
48584d9c625SLionel Sambuc 
48684d9c625SLionel Sambuc /*
48784d9c625SLionel Sambuc  - backref - figure out what matched what, figuring in back references
488*0a6a1f1dSLionel Sambuc  == static RCHAR_T *backref(struct match *m, RCHAR_T *start, \
48984d9c625SLionel Sambuc  ==	RCHAR_T *stop, sopno startst, sopno stopst, sopno lev);
49084d9c625SLionel Sambuc  */
49184d9c625SLionel Sambuc static RCHAR_T *			/* == stop (success) or NULL (failure) */
backref(m,start,stop,startst,stopst,lev)49284d9c625SLionel Sambuc backref(m, start, stop, startst, stopst, lev)
493*0a6a1f1dSLionel Sambuc struct match *m;
49484d9c625SLionel Sambuc RCHAR_T *start;
49584d9c625SLionel Sambuc RCHAR_T *stop;
49684d9c625SLionel Sambuc sopno startst;
49784d9c625SLionel Sambuc sopno stopst;
49884d9c625SLionel Sambuc sopno lev;			/* PLUS nesting level */
49984d9c625SLionel Sambuc {
500*0a6a1f1dSLionel Sambuc 	int i;
501*0a6a1f1dSLionel Sambuc 	sopno ss;	/* start sop of current subRE */
502*0a6a1f1dSLionel Sambuc 	RCHAR_T *sp;	/* start of string matched by it */
503*0a6a1f1dSLionel Sambuc 	sopno ssub;	/* start sop of subsubRE */
504*0a6a1f1dSLionel Sambuc 	sopno esub;	/* end sop of subsubRE */
505*0a6a1f1dSLionel Sambuc 	RCHAR_T *ssp;	/* start of string matched by subsubRE */
506*0a6a1f1dSLionel Sambuc 	RCHAR_T *dp;
507*0a6a1f1dSLionel Sambuc 	size_t len;
508*0a6a1f1dSLionel Sambuc 	int hard;
509*0a6a1f1dSLionel Sambuc 	sop s;
510*0a6a1f1dSLionel Sambuc 	RCHAR_T d;
511*0a6a1f1dSLionel Sambuc 	regoff_t offsave;
512*0a6a1f1dSLionel Sambuc 	cset *cs;
51384d9c625SLionel Sambuc 
51484d9c625SLionel Sambuc 	AT("back", start, stop, startst, stopst);
51584d9c625SLionel Sambuc 	sp = start;
51684d9c625SLionel Sambuc 
51784d9c625SLionel Sambuc 	/* get as far as we can with easy stuff */
51884d9c625SLionel Sambuc 	hard = 0;
51984d9c625SLionel Sambuc 	for (ss = startst; !hard && ss < stopst; ss++) {
52084d9c625SLionel Sambuc 		s = m->g->strip[ss];
52184d9c625SLionel Sambuc 		d = m->g->stripdata[ss];
52284d9c625SLionel Sambuc 		switch (s) {
52384d9c625SLionel Sambuc 		case OCHAR:
52484d9c625SLionel Sambuc 			if (sp == stop || *sp++ != d)
52584d9c625SLionel Sambuc 				return(NULL);
52684d9c625SLionel Sambuc 			break;
52784d9c625SLionel Sambuc 		case OANY:
52884d9c625SLionel Sambuc 			if (sp == stop)
52984d9c625SLionel Sambuc 				return(NULL);
53084d9c625SLionel Sambuc 			sp++;
53184d9c625SLionel Sambuc 			break;
53284d9c625SLionel Sambuc 		case OANYOF:
53384d9c625SLionel Sambuc 			cs = &m->g->sets[d];
53484d9c625SLionel Sambuc 			if (sp == stop || !CHIN(cs, *sp++))
53584d9c625SLionel Sambuc 				return(NULL);
53684d9c625SLionel Sambuc 			break;
53784d9c625SLionel Sambuc 		case OBOL:
53884d9c625SLionel Sambuc 			if ( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
53984d9c625SLionel Sambuc 					(sp < m->endp && *(sp-1) == '\n' &&
54084d9c625SLionel Sambuc 						(m->g->cflags&REG_NEWLINE)) )
54184d9c625SLionel Sambuc 				{ /* yes */ }
54284d9c625SLionel Sambuc 			else
54384d9c625SLionel Sambuc 				return(NULL);
54484d9c625SLionel Sambuc 			break;
54584d9c625SLionel Sambuc 		case OEOL:
54684d9c625SLionel Sambuc 			if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
54784d9c625SLionel Sambuc 					(sp < m->endp && *sp == '\n' &&
54884d9c625SLionel Sambuc 						(m->g->cflags&REG_NEWLINE)) )
54984d9c625SLionel Sambuc 				{ /* yes */ }
55084d9c625SLionel Sambuc 			else
55184d9c625SLionel Sambuc 				return(NULL);
55284d9c625SLionel Sambuc 			break;
55384d9c625SLionel Sambuc 		case OBOW:
55484d9c625SLionel Sambuc 			if (( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
55584d9c625SLionel Sambuc 					(sp < m->endp && *(sp-1) == '\n' &&
55684d9c625SLionel Sambuc 						(m->g->cflags&REG_NEWLINE)) ||
55784d9c625SLionel Sambuc 					(sp > m->beginp &&
55884d9c625SLionel Sambuc 							!ISWORD(*(sp-1))) ) &&
55984d9c625SLionel Sambuc 					(sp < m->endp && ISWORD(*sp)) )
56084d9c625SLionel Sambuc 				{ /* yes */ }
56184d9c625SLionel Sambuc 			else
56284d9c625SLionel Sambuc 				return(NULL);
56384d9c625SLionel Sambuc 			break;
56484d9c625SLionel Sambuc 		case OEOW:
56584d9c625SLionel Sambuc 			if (( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
56684d9c625SLionel Sambuc 					(sp < m->endp && *sp == '\n' &&
56784d9c625SLionel Sambuc 						(m->g->cflags&REG_NEWLINE)) ||
56884d9c625SLionel Sambuc 					(sp < m->endp && !ISWORD(*sp)) ) &&
56984d9c625SLionel Sambuc 					(sp > m->beginp && ISWORD(*(sp-1))) )
57084d9c625SLionel Sambuc 				{ /* yes */ }
57184d9c625SLionel Sambuc 			else
57284d9c625SLionel Sambuc 				return(NULL);
57384d9c625SLionel Sambuc 			break;
57484d9c625SLionel Sambuc 		case O_QUEST:
57584d9c625SLionel Sambuc 			break;
57684d9c625SLionel Sambuc 		case OOR1:	/* matches null but needs to skip */
57784d9c625SLionel Sambuc 			ss++;
57884d9c625SLionel Sambuc 			s = m->g->strip[ss];
57984d9c625SLionel Sambuc 			d = m->g->stripdata[ss];
58084d9c625SLionel Sambuc 			do {
58184d9c625SLionel Sambuc 				assert(s == OOR2);
58284d9c625SLionel Sambuc 				ss += d;
58384d9c625SLionel Sambuc 				s = m->g->strip[ss];
58484d9c625SLionel Sambuc 				d = m->g->stripdata[ss];
58584d9c625SLionel Sambuc 			} while (s != O_CH);
58684d9c625SLionel Sambuc 			/* note that the ss++ gets us past the O_CH */
58784d9c625SLionel Sambuc 			break;
58884d9c625SLionel Sambuc 		default:	/* have to make a choice */
58984d9c625SLionel Sambuc 			hard = 1;
59084d9c625SLionel Sambuc 			break;
59184d9c625SLionel Sambuc 		}
59284d9c625SLionel Sambuc 	}
59384d9c625SLionel Sambuc 	if (!hard) {		/* that was it! */
59484d9c625SLionel Sambuc 		if (sp != stop)
59584d9c625SLionel Sambuc 			return(NULL);
59684d9c625SLionel Sambuc 		return(sp);
59784d9c625SLionel Sambuc 	}
59884d9c625SLionel Sambuc 	ss--;			/* adjust for the for's final increment */
59984d9c625SLionel Sambuc 
60084d9c625SLionel Sambuc 	/* the hard stuff */
60184d9c625SLionel Sambuc 	AT("hard", sp, stop, ss, stopst);
60284d9c625SLionel Sambuc 	s = m->g->strip[ss];
60384d9c625SLionel Sambuc 	d = m->g->stripdata[ss];
60484d9c625SLionel Sambuc 	switch (s) {
60584d9c625SLionel Sambuc 	case OBACK_:		/* the vilest depths */
60684d9c625SLionel Sambuc 		i = d;
60784d9c625SLionel Sambuc 		assert(0 < i && i <= m->g->nsub);
60884d9c625SLionel Sambuc 		if (m->pmatch[i].rm_eo == -1)
60984d9c625SLionel Sambuc 			return(NULL);
61084d9c625SLionel Sambuc 		assert(m->pmatch[i].rm_so != -1);
61184d9c625SLionel Sambuc 		len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
61284d9c625SLionel Sambuc 		assert(stop - m->beginp >= len);
61384d9c625SLionel Sambuc 		if (sp > stop - len)
61484d9c625SLionel Sambuc 			return(NULL);	/* not enough left to match */
61584d9c625SLionel Sambuc 		ssp = m->offp + m->pmatch[i].rm_so;
61684d9c625SLionel Sambuc 		if (memcmp(sp, ssp, len) != 0)
61784d9c625SLionel Sambuc 			return(NULL);
61884d9c625SLionel Sambuc 		while (m->g->strip[ss] != O_BACK || m->g->stripdata[ss] != i)
61984d9c625SLionel Sambuc 			ss++;
62084d9c625SLionel Sambuc 		return(backref(m, sp+len, stop, ss+1, stopst, lev));
62184d9c625SLionel Sambuc 		break;
62284d9c625SLionel Sambuc 	case OQUEST_:		/* to null or not */
62384d9c625SLionel Sambuc 		dp = backref(m, sp, stop, ss+1, stopst, lev);
62484d9c625SLionel Sambuc 		if (dp != NULL)
62584d9c625SLionel Sambuc 			return(dp);	/* not */
62684d9c625SLionel Sambuc 		return(backref(m, sp, stop, ss+d+1, stopst, lev));
62784d9c625SLionel Sambuc 		break;
62884d9c625SLionel Sambuc 	case OPLUS_:
62984d9c625SLionel Sambuc 		assert(m->lastpos != NULL);
63084d9c625SLionel Sambuc 		assert(lev+1 <= m->g->nplus);
63184d9c625SLionel Sambuc 		m->lastpos[lev+1] = sp;
63284d9c625SLionel Sambuc 		return(backref(m, sp, stop, ss+1, stopst, lev+1));
63384d9c625SLionel Sambuc 		break;
63484d9c625SLionel Sambuc 	case O_PLUS:
63584d9c625SLionel Sambuc 		if (sp == m->lastpos[lev])	/* last pass matched null */
63684d9c625SLionel Sambuc 			return(backref(m, sp, stop, ss+1, stopst, lev-1));
63784d9c625SLionel Sambuc 		/* try another pass */
63884d9c625SLionel Sambuc 		m->lastpos[lev] = sp;
63984d9c625SLionel Sambuc 		dp = backref(m, sp, stop, ss-d+1, stopst, lev);
64084d9c625SLionel Sambuc 		if (dp == NULL)
64184d9c625SLionel Sambuc 			return(backref(m, sp, stop, ss+1, stopst, lev-1));
64284d9c625SLionel Sambuc 		else
64384d9c625SLionel Sambuc 			return(dp);
64484d9c625SLionel Sambuc 		break;
64584d9c625SLionel Sambuc 	case OCH_:		/* find the right one, if any */
64684d9c625SLionel Sambuc 		ssub = ss + 1;
64784d9c625SLionel Sambuc 		esub = ss + d - 1;
64884d9c625SLionel Sambuc 		assert(m->g->strip[esub] == OOR1);
64984d9c625SLionel Sambuc 		for (;;) {	/* find first matching branch */
65084d9c625SLionel Sambuc 			dp = backref(m, sp, stop, ssub, esub, lev);
65184d9c625SLionel Sambuc 			if (dp != NULL)
65284d9c625SLionel Sambuc 				return(dp);
65384d9c625SLionel Sambuc 			/* that one missed, try next one */
65484d9c625SLionel Sambuc 			if (m->g->strip[esub] == O_CH)
65584d9c625SLionel Sambuc 				return(NULL);	/* there is none */
65684d9c625SLionel Sambuc 			esub++;
65784d9c625SLionel Sambuc 			assert(m->g->strip[esub] == OOR2);
65884d9c625SLionel Sambuc 			ssub = esub + 1;
65984d9c625SLionel Sambuc 			esub += m->g->stripdata[esub];
66084d9c625SLionel Sambuc 			if (m->g->strip[esub] == OOR2)
66184d9c625SLionel Sambuc 				esub--;
66284d9c625SLionel Sambuc 			else
66384d9c625SLionel Sambuc 				assert(m->g->strip[esub] == O_CH);
66484d9c625SLionel Sambuc 		}
66584d9c625SLionel Sambuc 		break;
66684d9c625SLionel Sambuc 	case OLPAREN:		/* must undo assignment if rest fails */
66784d9c625SLionel Sambuc 		i = d;
66884d9c625SLionel Sambuc 		assert(0 < i && i <= m->g->nsub);
66984d9c625SLionel Sambuc 		offsave = m->pmatch[i].rm_so;
67084d9c625SLionel Sambuc 		m->pmatch[i].rm_so = sp - m->offp;
67184d9c625SLionel Sambuc 		dp = backref(m, sp, stop, ss+1, stopst, lev);
67284d9c625SLionel Sambuc 		if (dp != NULL)
67384d9c625SLionel Sambuc 			return(dp);
67484d9c625SLionel Sambuc 		m->pmatch[i].rm_so = offsave;
67584d9c625SLionel Sambuc 		return(NULL);
67684d9c625SLionel Sambuc 		break;
67784d9c625SLionel Sambuc 	case ORPAREN:		/* must undo assignment if rest fails */
67884d9c625SLionel Sambuc 		i = d;
67984d9c625SLionel Sambuc 		assert(0 < i && i <= m->g->nsub);
68084d9c625SLionel Sambuc 		offsave = m->pmatch[i].rm_eo;
68184d9c625SLionel Sambuc 		m->pmatch[i].rm_eo = sp - m->offp;
68284d9c625SLionel Sambuc 		dp = backref(m, sp, stop, ss+1, stopst, lev);
68384d9c625SLionel Sambuc 		if (dp != NULL)
68484d9c625SLionel Sambuc 			return(dp);
68584d9c625SLionel Sambuc 		m->pmatch[i].rm_eo = offsave;
68684d9c625SLionel Sambuc 		return(NULL);
68784d9c625SLionel Sambuc 		break;
68884d9c625SLionel Sambuc 	default:		/* uh oh */
68984d9c625SLionel Sambuc 		assert(nope);
69084d9c625SLionel Sambuc 		break;
69184d9c625SLionel Sambuc 	}
69284d9c625SLionel Sambuc 
69384d9c625SLionel Sambuc 	/* "can't happen" */
69484d9c625SLionel Sambuc 	assert(nope);
69584d9c625SLionel Sambuc 	/* NOTREACHED */
69684d9c625SLionel Sambuc 	return NULL;
69784d9c625SLionel Sambuc }
69884d9c625SLionel Sambuc 
69984d9c625SLionel Sambuc /*
70084d9c625SLionel Sambuc  - fast - step through the string at top speed
701*0a6a1f1dSLionel Sambuc  == static RCHAR_T *fast(struct match *m, RCHAR_T *start, \
70284d9c625SLionel Sambuc  ==	RCHAR_T *stop, sopno startst, sopno stopst);
70384d9c625SLionel Sambuc  */
70484d9c625SLionel Sambuc static RCHAR_T *			/* where tentative match ended, or NULL */
fast(m,start,stop,startst,stopst)70584d9c625SLionel Sambuc fast(m, start, stop, startst, stopst)
706*0a6a1f1dSLionel Sambuc struct match *m;
70784d9c625SLionel Sambuc RCHAR_T *start;
70884d9c625SLionel Sambuc RCHAR_T *stop;
70984d9c625SLionel Sambuc sopno startst;
71084d9c625SLionel Sambuc sopno stopst;
71184d9c625SLionel Sambuc {
712*0a6a1f1dSLionel Sambuc 	states st = m->st;
713*0a6a1f1dSLionel Sambuc 	states fresh = m->fresh;
714*0a6a1f1dSLionel Sambuc 	states tmp = m->tmp;
715*0a6a1f1dSLionel Sambuc 	RCHAR_T *p = start;
716*0a6a1f1dSLionel Sambuc 	RCHAR_T c = (start == m->beginp) ? OUT : *(start-1);
717*0a6a1f1dSLionel Sambuc 	RCHAR_T lastc;	/* previous c */
718*0a6a1f1dSLionel Sambuc 	int flag;
719*0a6a1f1dSLionel Sambuc 	int i;
720*0a6a1f1dSLionel Sambuc 	RCHAR_T *coldp;	/* last p after which no match was underway */
72184d9c625SLionel Sambuc 
72284d9c625SLionel Sambuc 	CLEAR(st);
72384d9c625SLionel Sambuc 	SET1(st, startst);
72484d9c625SLionel Sambuc 	st = step(m->g, startst, stopst, st, NOTHING, OUT, st);
72584d9c625SLionel Sambuc 	ASSIGN(fresh, st);
72684d9c625SLionel Sambuc 	SP("start", st, *p);
72784d9c625SLionel Sambuc 	coldp = NULL;
72884d9c625SLionel Sambuc 	for (;;) {
72984d9c625SLionel Sambuc 		/* next character */
73084d9c625SLionel Sambuc 		lastc = c;
73184d9c625SLionel Sambuc 		c = (p == m->endp) ? OUT : *p;
73284d9c625SLionel Sambuc 		if (EQ(st, fresh))
73384d9c625SLionel Sambuc 			coldp = p;
73484d9c625SLionel Sambuc 
73584d9c625SLionel Sambuc 		/* is there an EOL and/or BOL between lastc and c? */
73684d9c625SLionel Sambuc 		flag = 0;
73784d9c625SLionel Sambuc 		i = 0;
73884d9c625SLionel Sambuc 		if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
73984d9c625SLionel Sambuc 				(lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
74084d9c625SLionel Sambuc 			flag = BOL;
74184d9c625SLionel Sambuc 			i = m->g->nbol;
74284d9c625SLionel Sambuc 		}
74384d9c625SLionel Sambuc 		if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
74484d9c625SLionel Sambuc 				(c == OUT && !(m->eflags&REG_NOTEOL)) ) {
74584d9c625SLionel Sambuc 			flag = (flag == BOL) ? BOLEOL : EOL;
74684d9c625SLionel Sambuc 			i += m->g->neol;
74784d9c625SLionel Sambuc 		}
74884d9c625SLionel Sambuc 		if (i != 0) {
74984d9c625SLionel Sambuc 			for (; i > 0; i--)
75084d9c625SLionel Sambuc 				st = step(m->g, startst, stopst, st, flag, OUT, st);
75184d9c625SLionel Sambuc 			SP("boleol", st, c);
75284d9c625SLionel Sambuc 		}
75384d9c625SLionel Sambuc 
75484d9c625SLionel Sambuc 		/* how about a word boundary? */
75584d9c625SLionel Sambuc 		if ( (flag == BOL || (lastc != OUT && !ISWORD(lastc))) &&
75684d9c625SLionel Sambuc 					(c != OUT && ISWORD(c)) ) {
75784d9c625SLionel Sambuc 			flag = BOW;
75884d9c625SLionel Sambuc 		}
75984d9c625SLionel Sambuc 		if ( (lastc != OUT && ISWORD(lastc)) &&
76084d9c625SLionel Sambuc 				(flag == EOL || (c != OUT && !ISWORD(c))) ) {
76184d9c625SLionel Sambuc 			flag = EOW;
76284d9c625SLionel Sambuc 		}
76384d9c625SLionel Sambuc 		if (flag == BOW || flag == EOW) {
76484d9c625SLionel Sambuc 			st = step(m->g, startst, stopst, st, flag, OUT, st);
76584d9c625SLionel Sambuc 			SP("boweow", st, c);
76684d9c625SLionel Sambuc 		}
76784d9c625SLionel Sambuc 
76884d9c625SLionel Sambuc 		/* are we done? */
76984d9c625SLionel Sambuc 		if (ISSET(st, stopst) || p == stop)
77084d9c625SLionel Sambuc 			break;		/* NOTE BREAK OUT */
77184d9c625SLionel Sambuc 
77284d9c625SLionel Sambuc 		/* no, we must deal with this character */
77384d9c625SLionel Sambuc 		ASSIGN(tmp, st);
77484d9c625SLionel Sambuc 		ASSIGN(st, fresh);
77584d9c625SLionel Sambuc 		assert(c != OUT);
77684d9c625SLionel Sambuc 		st = step(m->g, startst, stopst, tmp, 0, c, st);
77784d9c625SLionel Sambuc 		SP("aft", st, c);
77884d9c625SLionel Sambuc 		assert(EQ(step(m->g, startst, stopst, st, NOTHING, OUT, st), st));
77984d9c625SLionel Sambuc 		p++;
78084d9c625SLionel Sambuc 	}
78184d9c625SLionel Sambuc 
78284d9c625SLionel Sambuc 	assert(coldp != NULL);
78384d9c625SLionel Sambuc 	m->coldp = coldp;
78484d9c625SLionel Sambuc 	if (ISSET(st, stopst))
78584d9c625SLionel Sambuc 		return(p+1);
78684d9c625SLionel Sambuc 	else
78784d9c625SLionel Sambuc 		return(NULL);
78884d9c625SLionel Sambuc }
78984d9c625SLionel Sambuc 
79084d9c625SLionel Sambuc /*
79184d9c625SLionel Sambuc  - slow - step through the string more deliberately
792*0a6a1f1dSLionel Sambuc  == static RCHAR_T *slow(struct match *m, RCHAR_T *start, \
79384d9c625SLionel Sambuc  ==	RCHAR_T *stop, sopno startst, sopno stopst);
79484d9c625SLionel Sambuc  */
79584d9c625SLionel Sambuc static RCHAR_T *			/* where it ended */
slow(m,start,stop,startst,stopst)79684d9c625SLionel Sambuc slow(m, start, stop, startst, stopst)
797*0a6a1f1dSLionel Sambuc struct match *m;
79884d9c625SLionel Sambuc RCHAR_T *start;
79984d9c625SLionel Sambuc RCHAR_T *stop;
80084d9c625SLionel Sambuc sopno startst;
80184d9c625SLionel Sambuc sopno stopst;
80284d9c625SLionel Sambuc {
803*0a6a1f1dSLionel Sambuc 	states st = m->st;
804*0a6a1f1dSLionel Sambuc 	states empty = m->empty;
805*0a6a1f1dSLionel Sambuc 	states tmp = m->tmp;
806*0a6a1f1dSLionel Sambuc 	RCHAR_T *p = start;
807*0a6a1f1dSLionel Sambuc 	RCHAR_T c = (start == m->beginp) ? OUT : *(start-1);
808*0a6a1f1dSLionel Sambuc 	RCHAR_T lastc;	/* previous c */
809*0a6a1f1dSLionel Sambuc 	int flag;
810*0a6a1f1dSLionel Sambuc 	int i;
811*0a6a1f1dSLionel Sambuc 	RCHAR_T *matchp;	/* last p at which a match ended */
81284d9c625SLionel Sambuc 
81384d9c625SLionel Sambuc 	AT("slow", start, stop, startst, stopst);
81484d9c625SLionel Sambuc 	CLEAR(st);
81584d9c625SLionel Sambuc 	SET1(st, startst);
81684d9c625SLionel Sambuc 	SP("sstart", st, *p);
81784d9c625SLionel Sambuc 	st = step(m->g, startst, stopst, st, NOTHING, OUT, st);
81884d9c625SLionel Sambuc 	matchp = NULL;
81984d9c625SLionel Sambuc 	for (;;) {
82084d9c625SLionel Sambuc 		/* next character */
82184d9c625SLionel Sambuc 		lastc = c;
82284d9c625SLionel Sambuc 		c = (p == m->endp) ? OUT : *p;
82384d9c625SLionel Sambuc 
82484d9c625SLionel Sambuc 		/* is there an EOL and/or BOL between lastc and c? */
82584d9c625SLionel Sambuc 		flag = 0;
82684d9c625SLionel Sambuc 		i = 0;
82784d9c625SLionel Sambuc 		if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
82884d9c625SLionel Sambuc 				(lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
82984d9c625SLionel Sambuc 			flag = BOL;
83084d9c625SLionel Sambuc 			i = m->g->nbol;
83184d9c625SLionel Sambuc 		}
83284d9c625SLionel Sambuc 		if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
83384d9c625SLionel Sambuc 				(c == OUT && !(m->eflags&REG_NOTEOL)) ) {
83484d9c625SLionel Sambuc 			flag = (flag == BOL) ? BOLEOL : EOL;
83584d9c625SLionel Sambuc 			i += m->g->neol;
83684d9c625SLionel Sambuc 		}
83784d9c625SLionel Sambuc 		if (i != 0) {
83884d9c625SLionel Sambuc 			for (; i > 0; i--)
83984d9c625SLionel Sambuc 				st = step(m->g, startst, stopst, st, flag, OUT, st);
84084d9c625SLionel Sambuc 			SP("sboleol", st, c);
84184d9c625SLionel Sambuc 		}
84284d9c625SLionel Sambuc 
84384d9c625SLionel Sambuc 		/* how about a word boundary? */
84484d9c625SLionel Sambuc 		if ( (flag == BOL || (lastc != OUT && !ISWORD(lastc))) &&
84584d9c625SLionel Sambuc 					(c != OUT && ISWORD(c)) ) {
84684d9c625SLionel Sambuc 			flag = BOW;
84784d9c625SLionel Sambuc 		}
84884d9c625SLionel Sambuc 		if ( (lastc != OUT && ISWORD(lastc)) &&
84984d9c625SLionel Sambuc 				(flag == EOL || (c != OUT && !ISWORD(c))) ) {
85084d9c625SLionel Sambuc 			flag = EOW;
85184d9c625SLionel Sambuc 		}
85284d9c625SLionel Sambuc 		if (flag == BOW || flag == EOW) {
85384d9c625SLionel Sambuc 			st = step(m->g, startst, stopst, st, flag, OUT, st);
85484d9c625SLionel Sambuc 			SP("sboweow", st, c);
85584d9c625SLionel Sambuc 		}
85684d9c625SLionel Sambuc 
85784d9c625SLionel Sambuc 		/* are we done? */
85884d9c625SLionel Sambuc 		if (ISSET(st, stopst))
85984d9c625SLionel Sambuc 			matchp = p;
86084d9c625SLionel Sambuc 		if (EQ(st, empty) || p == stop)
86184d9c625SLionel Sambuc 			break;		/* NOTE BREAK OUT */
86284d9c625SLionel Sambuc 
86384d9c625SLionel Sambuc 		/* no, we must deal with this character */
86484d9c625SLionel Sambuc 		ASSIGN(tmp, st);
86584d9c625SLionel Sambuc 		ASSIGN(st, empty);
86684d9c625SLionel Sambuc 		assert(c != OUT);
86784d9c625SLionel Sambuc 		st = step(m->g, startst, stopst, tmp, 0, c, st);
86884d9c625SLionel Sambuc 		SP("saft", st, c);
86984d9c625SLionel Sambuc 		assert(EQ(step(m->g, startst, stopst, st, NOTHING, OUT, st), st));
87084d9c625SLionel Sambuc 		p++;
87184d9c625SLionel Sambuc 	}
87284d9c625SLionel Sambuc 
87384d9c625SLionel Sambuc 	return(matchp);
87484d9c625SLionel Sambuc }
87584d9c625SLionel Sambuc 
87684d9c625SLionel Sambuc 
87784d9c625SLionel Sambuc /*
87884d9c625SLionel Sambuc  - step - map set of states reachable before char to set reachable after
879*0a6a1f1dSLionel Sambuc  == static states step(struct re_guts *g, sopno start, sopno stop, \
880*0a6a1f1dSLionel Sambuc  ==	states bef, int flag, RCHAR_T ch, states aft);
88184d9c625SLionel Sambuc  == #define	BOL	(1)
88284d9c625SLionel Sambuc  == #define	EOL	(BOL+1)
88384d9c625SLionel Sambuc  == #define	BOLEOL	(BOL+2)
88484d9c625SLionel Sambuc  == #define	NOTHING	(BOL+3)
88584d9c625SLionel Sambuc  == #define	BOW	(BOL+4)
88684d9c625SLionel Sambuc  == #define	EOW	(BOL+5)
88784d9c625SLionel Sambuc  */
88884d9c625SLionel Sambuc static states
step(g,start,stop,bef,flag,ch,aft)88984d9c625SLionel Sambuc step(g, start, stop, bef, flag, ch, aft)
890*0a6a1f1dSLionel Sambuc struct re_guts *g;
89184d9c625SLionel Sambuc sopno start;			/* start state within strip */
89284d9c625SLionel Sambuc sopno stop;			/* state after stop state within strip */
893*0a6a1f1dSLionel Sambuc states bef;		/* states reachable before */
89484d9c625SLionel Sambuc int flag;			/* NONCHAR flag */
89584d9c625SLionel Sambuc RCHAR_T ch;			/* character code */
896*0a6a1f1dSLionel Sambuc states aft;		/* states already known reachable after */
89784d9c625SLionel Sambuc {
898*0a6a1f1dSLionel Sambuc 	cset *cs;
899*0a6a1f1dSLionel Sambuc 	sop s;
900*0a6a1f1dSLionel Sambuc 	RCHAR_T d;
901*0a6a1f1dSLionel Sambuc 	sopno pc;
902*0a6a1f1dSLionel Sambuc 	onestate here;		/* note, macros know this name */
903*0a6a1f1dSLionel Sambuc 	sopno look;
904*0a6a1f1dSLionel Sambuc 	int i;
90584d9c625SLionel Sambuc 
90684d9c625SLionel Sambuc 	for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
90784d9c625SLionel Sambuc 		s = g->strip[pc];
90884d9c625SLionel Sambuc 		d = g->stripdata[pc];
90984d9c625SLionel Sambuc 		switch (s) {
91084d9c625SLionel Sambuc 		case OEND:
91184d9c625SLionel Sambuc 			assert(pc == stop-1);
91284d9c625SLionel Sambuc 			break;
91384d9c625SLionel Sambuc 		case OCHAR:
91484d9c625SLionel Sambuc 			/* only characters can match */
91584d9c625SLionel Sambuc 			assert(!flag || ch != d);
91684d9c625SLionel Sambuc 			if (ch == d)
91784d9c625SLionel Sambuc 				FWD(aft, bef, 1);
91884d9c625SLionel Sambuc 			break;
91984d9c625SLionel Sambuc 		case OBOL:
92084d9c625SLionel Sambuc 			if (flag == BOL || flag == BOLEOL)
92184d9c625SLionel Sambuc 				FWD(aft, bef, 1);
92284d9c625SLionel Sambuc 			break;
92384d9c625SLionel Sambuc 		case OEOL:
92484d9c625SLionel Sambuc 			if (flag == EOL || flag == BOLEOL)
92584d9c625SLionel Sambuc 				FWD(aft, bef, 1);
92684d9c625SLionel Sambuc 			break;
92784d9c625SLionel Sambuc 		case OBOW:
92884d9c625SLionel Sambuc 			if (flag == BOW)
92984d9c625SLionel Sambuc 				FWD(aft, bef, 1);
93084d9c625SLionel Sambuc 			break;
93184d9c625SLionel Sambuc 		case OEOW:
93284d9c625SLionel Sambuc 			if (flag == EOW)
93384d9c625SLionel Sambuc 				FWD(aft, bef, 1);
93484d9c625SLionel Sambuc 			break;
93584d9c625SLionel Sambuc 		case OANY:
93684d9c625SLionel Sambuc 			if (!flag)
93784d9c625SLionel Sambuc 				FWD(aft, bef, 1);
93884d9c625SLionel Sambuc 			break;
93984d9c625SLionel Sambuc 		case OANYOF:
94084d9c625SLionel Sambuc 			cs = &g->sets[d];
94184d9c625SLionel Sambuc 			if (!flag && CHIN(cs, ch))
94284d9c625SLionel Sambuc 				FWD(aft, bef, 1);
94384d9c625SLionel Sambuc 			break;
94484d9c625SLionel Sambuc 		case OBACK_:		/* ignored here */
94584d9c625SLionel Sambuc 		case O_BACK:
94684d9c625SLionel Sambuc 			FWD(aft, aft, 1);
94784d9c625SLionel Sambuc 			break;
94884d9c625SLionel Sambuc 		case OPLUS_:		/* forward, this is just an empty */
94984d9c625SLionel Sambuc 			FWD(aft, aft, 1);
95084d9c625SLionel Sambuc 			break;
95184d9c625SLionel Sambuc 		case O_PLUS:		/* both forward and back */
95284d9c625SLionel Sambuc 			FWD(aft, aft, 1);
95384d9c625SLionel Sambuc 			i = ISSETBACK(aft, d);
95484d9c625SLionel Sambuc 			BACK(aft, aft, d);
95584d9c625SLionel Sambuc 			if (!i && ISSETBACK(aft, d)) {
95684d9c625SLionel Sambuc 				/* oho, must reconsider loop body */
95784d9c625SLionel Sambuc 				pc -= d + 1;
95884d9c625SLionel Sambuc 				INIT(here, pc);
95984d9c625SLionel Sambuc 			}
96084d9c625SLionel Sambuc 			break;
96184d9c625SLionel Sambuc 		case OQUEST_:		/* two branches, both forward */
96284d9c625SLionel Sambuc 			FWD(aft, aft, 1);
96384d9c625SLionel Sambuc 			FWD(aft, aft, d);
96484d9c625SLionel Sambuc 			break;
96584d9c625SLionel Sambuc 		case O_QUEST:		/* just an empty */
96684d9c625SLionel Sambuc 			FWD(aft, aft, 1);
96784d9c625SLionel Sambuc 			break;
96884d9c625SLionel Sambuc 		case OLPAREN:		/* not significant here */
96984d9c625SLionel Sambuc 		case ORPAREN:
97084d9c625SLionel Sambuc 			FWD(aft, aft, 1);
97184d9c625SLionel Sambuc 			break;
97284d9c625SLionel Sambuc 		case OCH_:		/* mark the first two branches */
97384d9c625SLionel Sambuc 			FWD(aft, aft, 1);
97484d9c625SLionel Sambuc 			assert(OP(g->strip[pc+d]) == OOR2);
97584d9c625SLionel Sambuc 			FWD(aft, aft, d);
97684d9c625SLionel Sambuc 			break;
97784d9c625SLionel Sambuc 		case OOR1:		/* done a branch, find the O_CH */
97884d9c625SLionel Sambuc 			if (ISSTATEIN(aft, here)) {
97984d9c625SLionel Sambuc 				for (look = 1; /**/; look += d) {
98084d9c625SLionel Sambuc 					s = g->strip[pc+look];
98184d9c625SLionel Sambuc 					d = g->stripdata[pc+look];
98284d9c625SLionel Sambuc 					if (s == O_CH)
98384d9c625SLionel Sambuc 						break;
98484d9c625SLionel Sambuc 					assert(s == OOR2);
98584d9c625SLionel Sambuc 				}
98684d9c625SLionel Sambuc 				FWD(aft, aft, look);
98784d9c625SLionel Sambuc 			}
98884d9c625SLionel Sambuc 			break;
98984d9c625SLionel Sambuc 		case OOR2:		/* propagate OCH_'s marking */
99084d9c625SLionel Sambuc 			FWD(aft, aft, 1);
99184d9c625SLionel Sambuc 			if (g->strip[pc+d] != O_CH) {
99284d9c625SLionel Sambuc 				assert(g->strip[pc+d] == OOR2);
99384d9c625SLionel Sambuc 				FWD(aft, aft, d);
99484d9c625SLionel Sambuc 			}
99584d9c625SLionel Sambuc 			break;
99684d9c625SLionel Sambuc 		case O_CH:		/* just empty */
99784d9c625SLionel Sambuc 			FWD(aft, aft, 1);
99884d9c625SLionel Sambuc 			break;
99984d9c625SLionel Sambuc 		default:		/* ooooops... */
100084d9c625SLionel Sambuc 			assert(nope);
100184d9c625SLionel Sambuc 			break;
100284d9c625SLionel Sambuc 		}
100384d9c625SLionel Sambuc 	}
100484d9c625SLionel Sambuc 
100584d9c625SLionel Sambuc 	return(aft);
100684d9c625SLionel Sambuc }
100784d9c625SLionel Sambuc 
100884d9c625SLionel Sambuc #ifdef REDEBUG
100984d9c625SLionel Sambuc /*
101084d9c625SLionel Sambuc  - print - print a set of states
101184d9c625SLionel Sambuc  == #ifdef REDEBUG
101284d9c625SLionel Sambuc  == static void print(struct match *m, char *caption, states st, \
101384d9c625SLionel Sambuc  ==	int ch, FILE *d);
101484d9c625SLionel Sambuc  == #endif
101584d9c625SLionel Sambuc  */
101684d9c625SLionel Sambuc static void
print(m,caption,st,ch,d)101784d9c625SLionel Sambuc print(m, caption, st, ch, d)
101884d9c625SLionel Sambuc struct match *m;
101984d9c625SLionel Sambuc char *caption;
102084d9c625SLionel Sambuc states st;
102184d9c625SLionel Sambuc int ch;
102284d9c625SLionel Sambuc FILE *d;
102384d9c625SLionel Sambuc {
1024*0a6a1f1dSLionel Sambuc 	struct re_guts *g = m->g;
1025*0a6a1f1dSLionel Sambuc 	int i;
1026*0a6a1f1dSLionel Sambuc 	int first = 1;
102784d9c625SLionel Sambuc 
102884d9c625SLionel Sambuc 	if (!(m->eflags&REG_TRACE))
102984d9c625SLionel Sambuc 		return;
103084d9c625SLionel Sambuc 
103184d9c625SLionel Sambuc 	fprintf(d, "%s", caption);
103284d9c625SLionel Sambuc 	if (ch != '\0')
103384d9c625SLionel Sambuc 		fprintf(d, " %s", pchar(ch));
103484d9c625SLionel Sambuc 	for (i = 0; i < g->nstates; i++)
103584d9c625SLionel Sambuc 		if (ISSET(st, i)) {
103684d9c625SLionel Sambuc 			fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
103784d9c625SLionel Sambuc 			first = 0;
103884d9c625SLionel Sambuc 		}
103984d9c625SLionel Sambuc 	fprintf(d, "\n");
104084d9c625SLionel Sambuc }
104184d9c625SLionel Sambuc 
104284d9c625SLionel Sambuc /*
104384d9c625SLionel Sambuc  - at - print current situation
104484d9c625SLionel Sambuc  == #ifdef REDEBUG
104584d9c625SLionel Sambuc  == static void at(struct match *m, char *title, char *start, char *stop, \
104684d9c625SLionel Sambuc  ==						sopno startst, sopno stopst);
104784d9c625SLionel Sambuc  == #endif
104884d9c625SLionel Sambuc  */
104984d9c625SLionel Sambuc static void
at(m,title,start,stop,startst,stopst)105084d9c625SLionel Sambuc at(m, title, start, stop, startst, stopst)
105184d9c625SLionel Sambuc struct match *m;
105284d9c625SLionel Sambuc char *title;
105384d9c625SLionel Sambuc char *start;
105484d9c625SLionel Sambuc char *stop;
105584d9c625SLionel Sambuc sopno startst;
105684d9c625SLionel Sambuc sopno stopst;
105784d9c625SLionel Sambuc {
105884d9c625SLionel Sambuc 	if (!(m->eflags&REG_TRACE))
105984d9c625SLionel Sambuc 		return;
106084d9c625SLionel Sambuc 
106184d9c625SLionel Sambuc 	printf("%s %s-", title, pchar(*start));
106284d9c625SLionel Sambuc 	printf("%s ", pchar(*stop));
106384d9c625SLionel Sambuc 	printf("%ld-%ld\n", (long)startst, (long)stopst);
106484d9c625SLionel Sambuc }
106584d9c625SLionel Sambuc 
106684d9c625SLionel Sambuc #ifndef PCHARDONE
106784d9c625SLionel Sambuc #define	PCHARDONE	/* never again */
106884d9c625SLionel Sambuc /*
106984d9c625SLionel Sambuc  - pchar - make a character printable
107084d9c625SLionel Sambuc  == #ifdef REDEBUG
107184d9c625SLionel Sambuc  == static char *pchar(int ch);
107284d9c625SLionel Sambuc  == #endif
107384d9c625SLionel Sambuc  *
107484d9c625SLionel Sambuc  * Is this identical to regchar() over in debug.c?  Well, yes.  But a
107584d9c625SLionel Sambuc  * duplicate here avoids having a debugging-capable regexec.o tied to
107684d9c625SLionel Sambuc  * a matching debug.o, and this is convenient.  It all disappears in
107784d9c625SLionel Sambuc  * the non-debug compilation anyway, so it doesn't matter much.
107884d9c625SLionel Sambuc  */
107984d9c625SLionel Sambuc static char *			/* -> representation */
pchar(ch)108084d9c625SLionel Sambuc pchar(ch)
108184d9c625SLionel Sambuc int ch;
108284d9c625SLionel Sambuc {
108384d9c625SLionel Sambuc 	static char pbuf[10];
108484d9c625SLionel Sambuc 
108584d9c625SLionel Sambuc 	if (isprint(ch) || ch == ' ')
108684d9c625SLionel Sambuc 		sprintf(pbuf, "%c", ch);
108784d9c625SLionel Sambuc 	else
108884d9c625SLionel Sambuc 		sprintf(pbuf, "\\%o", ch);
108984d9c625SLionel Sambuc 	return(pbuf);
109084d9c625SLionel Sambuc }
109184d9c625SLionel Sambuc #endif
109284d9c625SLionel Sambuc #endif
109384d9c625SLionel Sambuc 
109484d9c625SLionel Sambuc #undef	matcher
109584d9c625SLionel Sambuc #undef	fast
109684d9c625SLionel Sambuc #undef	slow
109784d9c625SLionel Sambuc #undef	dissect
109884d9c625SLionel Sambuc #undef	backref
109984d9c625SLionel Sambuc #undef	step
110084d9c625SLionel Sambuc #undef	print
110184d9c625SLionel Sambuc #undef	at
110284d9c625SLionel Sambuc #undef	match
1103