xref: /illumos-gate/usr/src/lib/libc/port/regex/engine.c (revision 695dd8d1)
14297a3b0SGarrett D'Amore /*
2*695dd8d1SYuri Pankov  * Copyright 2019 Nexenta by DDN, Inc. All rights reserved.
333f5ff17SMilan Jurik  * Copyright 2012 Milan Jurik. All rights reserved.
448bbca81SDaniel Hoffman  * Copyright (c) 2016 by Delphix. All rights reserved.
54297a3b0SGarrett D'Amore  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
64297a3b0SGarrett D'Amore  * Copyright (c) 1992, 1993, 1994
74297a3b0SGarrett D'Amore  *	The Regents of the University of California.  All rights reserved.
84297a3b0SGarrett D'Amore  *
94297a3b0SGarrett D'Amore  * This code is derived from software contributed to Berkeley by
104297a3b0SGarrett D'Amore  * Henry Spencer.
114297a3b0SGarrett D'Amore  *
124297a3b0SGarrett D'Amore  * Redistribution and use in source and binary forms, with or without
134297a3b0SGarrett D'Amore  * modification, are permitted provided that the following conditions
144297a3b0SGarrett D'Amore  * are met:
154297a3b0SGarrett D'Amore  * 1. Redistributions of source code must retain the above copyright
164297a3b0SGarrett D'Amore  *    notice, this list of conditions and the following disclaimer.
174297a3b0SGarrett D'Amore  * 2. Redistributions in binary form must reproduce the above copyright
184297a3b0SGarrett D'Amore  *    notice, this list of conditions and the following disclaimer in the
194297a3b0SGarrett D'Amore  *    documentation and/or other materials provided with the distribution.
207641c5eaSYuri Pankov  * 3. Neither the name of the University nor the names of its contributors
214297a3b0SGarrett D'Amore  *    may be used to endorse or promote products derived from this software
224297a3b0SGarrett D'Amore  *    without specific prior written permission.
234297a3b0SGarrett D'Amore  *
244297a3b0SGarrett D'Amore  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
254297a3b0SGarrett D'Amore  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
264297a3b0SGarrett D'Amore  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
274297a3b0SGarrett D'Amore  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
284297a3b0SGarrett D'Amore  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
294297a3b0SGarrett D'Amore  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
304297a3b0SGarrett D'Amore  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
314297a3b0SGarrett D'Amore  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
324297a3b0SGarrett D'Amore  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
334297a3b0SGarrett D'Amore  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
344297a3b0SGarrett D'Amore  * SUCH DAMAGE.
354297a3b0SGarrett D'Amore  */
364297a3b0SGarrett D'Amore 
3762e74980SKyle Evans #include <stdbool.h>
3862e74980SKyle Evans 
394297a3b0SGarrett D'Amore /*
404297a3b0SGarrett D'Amore  * The matching engine and friends.  This file is #included by regexec.c
414297a3b0SGarrett D'Amore  * after suitable #defines of a variety of macros used herein, so that
424297a3b0SGarrett D'Amore  * different state representations can be used without duplicating masses
434297a3b0SGarrett D'Amore  * of code.
444297a3b0SGarrett D'Amore  */
454297a3b0SGarrett D'Amore 
464297a3b0SGarrett D'Amore #ifdef SNAMES
47*695dd8d1SYuri Pankov #define	stepback sstepback
484297a3b0SGarrett D'Amore #define	matcher	smatcher
4962e74980SKyle Evans #define	walk	swalk
504297a3b0SGarrett D'Amore #define	dissect	sdissect
514297a3b0SGarrett D'Amore #define	backref	sbackref
524297a3b0SGarrett D'Amore #define	step	sstep
534297a3b0SGarrett D'Amore #define	print	sprint
544297a3b0SGarrett D'Amore #define	at	sat
554297a3b0SGarrett D'Amore #define	match	smat
564297a3b0SGarrett D'Amore #endif
574297a3b0SGarrett D'Amore #ifdef LNAMES
58*695dd8d1SYuri Pankov #define	stepback lstepback
594297a3b0SGarrett D'Amore #define	matcher	lmatcher
6062e74980SKyle Evans #define	walk	lwalk
614297a3b0SGarrett D'Amore #define	dissect	ldissect
624297a3b0SGarrett D'Amore #define	backref	lbackref
634297a3b0SGarrett D'Amore #define	step	lstep
644297a3b0SGarrett D'Amore #define	print	lprint
654297a3b0SGarrett D'Amore #define	at	lat
664297a3b0SGarrett D'Amore #define	match	lmat
674297a3b0SGarrett D'Amore #endif
684297a3b0SGarrett D'Amore #ifdef MNAMES
69*695dd8d1SYuri Pankov #define	stepback mstepback
704297a3b0SGarrett D'Amore #define	matcher	mmatcher
7162e74980SKyle Evans #define	walk	mwalk
724297a3b0SGarrett D'Amore #define	dissect	mdissect
734297a3b0SGarrett D'Amore #define	backref	mbackref
744297a3b0SGarrett D'Amore #define	step	mstep
754297a3b0SGarrett D'Amore #define	print	mprint
764297a3b0SGarrett D'Amore #define	at	mat
774297a3b0SGarrett D'Amore #define	match	mmat
784297a3b0SGarrett D'Amore #endif
794297a3b0SGarrett D'Amore 
804297a3b0SGarrett D'Amore /* another structure passed up and down to avoid zillions of parameters */
814297a3b0SGarrett D'Amore struct match {
824297a3b0SGarrett D'Amore 	struct re_guts *g;
834297a3b0SGarrett D'Amore 	int eflags;
844297a3b0SGarrett D'Amore 	regmatch_t *pmatch;	/* [nsub+1] (0 element unused) */
854297a3b0SGarrett D'Amore 	const char *offp;	/* offsets work from here */
864297a3b0SGarrett D'Amore 	const char *beginp;	/* start of string -- virtual NUL precedes */
874297a3b0SGarrett D'Amore 	const char *endp;	/* end of string -- virtual NUL here */
884297a3b0SGarrett D'Amore 	const char *coldp;	/* can be no match starting before here */
894297a3b0SGarrett D'Amore 	const char **lastpos;	/* [nplus+1] */
904297a3b0SGarrett D'Amore 	STATEVARS;
914297a3b0SGarrett D'Amore 	states st;		/* current states */
924297a3b0SGarrett D'Amore 	states fresh;		/* states for a fresh start */
934297a3b0SGarrett D'Amore 	states tmp;		/* temporary */
944297a3b0SGarrett D'Amore 	states empty;		/* empty set of states */
954297a3b0SGarrett D'Amore 	mbstate_t mbs;		/* multibyte conversion state */
964297a3b0SGarrett D'Amore };
974297a3b0SGarrett D'Amore 
984297a3b0SGarrett D'Amore /* ========= begin header generated by ./mkh ========= */
994297a3b0SGarrett D'Amore #ifdef __cplusplus
1004297a3b0SGarrett D'Amore extern "C" {
1014297a3b0SGarrett D'Amore #endif
1024297a3b0SGarrett D'Amore 
1034297a3b0SGarrett D'Amore /* === engine.c === */
1044297a3b0SGarrett D'Amore static int matcher(struct re_guts *, const char *, size_t, regmatch_t[], int);
1054297a3b0SGarrett D'Amore static const char *dissect(struct match *, const char *, const char *,
1064297a3b0SGarrett D'Amore     sopno, sopno);
1074297a3b0SGarrett D'Amore static const char *backref(struct match *, const char *, const char *, sopno,
1084297a3b0SGarrett D'Amore     sopno, sopno, int);
10962e74980SKyle Evans static const char *walk(struct match *m, const char *start, const char *stop,
11062e74980SKyle Evans     sopno startst, sopno stopst, bool fast);
1114297a3b0SGarrett D'Amore static states step(struct re_guts *, sopno, sopno, states, wint_t, states);
1124297a3b0SGarrett D'Amore #define	MAX_RECURSION	100
1134297a3b0SGarrett D'Amore #define	BOL	(OUT-1)
1144297a3b0SGarrett D'Amore #define	EOL	(BOL-1)
1154297a3b0SGarrett D'Amore #define	BOLEOL	(BOL-2)
1164297a3b0SGarrett D'Amore #define	NOTHING	(BOL-3)
1174297a3b0SGarrett D'Amore #define	BOW	(BOL-4)
1184297a3b0SGarrett D'Amore #define	EOW	(BOL-5)
1194297a3b0SGarrett D'Amore #define	BADCHAR	(BOL-6)
1204297a3b0SGarrett D'Amore #define	NONCHAR(c)	((c) <= OUT)
1214297a3b0SGarrett D'Amore #ifdef REDEBUG
1224297a3b0SGarrett D'Amore static void print(struct match *, const char *, states, int, FILE *);
1234297a3b0SGarrett D'Amore #endif
1244297a3b0SGarrett D'Amore #ifdef REDEBUG
1254297a3b0SGarrett D'Amore static void at(struct match *, const char *, const char *, const char *,
1264297a3b0SGarrett D'Amore     sopno, sopno);
1274297a3b0SGarrett D'Amore #endif
1284297a3b0SGarrett D'Amore #ifdef REDEBUG
1294297a3b0SGarrett D'Amore static const char *pchar(int ch);
1304297a3b0SGarrett D'Amore #endif
1314297a3b0SGarrett D'Amore 
1324297a3b0SGarrett D'Amore #ifdef __cplusplus
1334297a3b0SGarrett D'Amore }
1344297a3b0SGarrett D'Amore #endif
1354297a3b0SGarrett D'Amore /* ========= end header generated by ./mkh ========= */
1364297a3b0SGarrett D'Amore 
1374297a3b0SGarrett D'Amore #ifdef REDEBUG
1384297a3b0SGarrett D'Amore #define	SP(t, s, c)	print(m, t, s, c, stdout)
1394297a3b0SGarrett D'Amore #define	AT(t, p1, p2, s1, s2)	at(m, t, p1, p2, s1, s2)
1404297a3b0SGarrett D'Amore #define	NOTE(str)	{ if (m->eflags&REG_TRACE) printf("=%s\n", (str)); }
1414297a3b0SGarrett D'Amore #else
1424297a3b0SGarrett D'Amore #define	SP(t, s, c)	/* nothing */
1434297a3b0SGarrett D'Amore #define	AT(t, p1, p2, s1, s2)	/* nothing */
1444297a3b0SGarrett D'Amore #define	NOTE(s)	/* nothing */
1454297a3b0SGarrett D'Amore #endif
1464297a3b0SGarrett D'Amore 
147*695dd8d1SYuri Pankov /*
148*695dd8d1SYuri Pankov  * Given a multibyte string pointed to by start, step back nchar characters
149*695dd8d1SYuri Pankov  * from current position pointed to by cur.
150*695dd8d1SYuri Pankov  */
151*695dd8d1SYuri Pankov static const char *
stepback(const char * start,const char * cur,int nchar)152*695dd8d1SYuri Pankov stepback(const char *start, const char *cur, int nchar)
153*695dd8d1SYuri Pankov {
154*695dd8d1SYuri Pankov 	const char *ret;
155*695dd8d1SYuri Pankov 	int wc, mbc;
156*695dd8d1SYuri Pankov 	mbstate_t mbs;
157*695dd8d1SYuri Pankov 	size_t clen;
158*695dd8d1SYuri Pankov 
159*695dd8d1SYuri Pankov 	if (MB_CUR_MAX == 1)
160*695dd8d1SYuri Pankov 		return ((cur - nchar) > start ? cur - nchar : NULL);
161*695dd8d1SYuri Pankov 
162*695dd8d1SYuri Pankov 	ret = cur;
163*695dd8d1SYuri Pankov 	for (wc = nchar; wc > 0; wc--) {
164*695dd8d1SYuri Pankov 		for (mbc = 1; mbc <= MB_CUR_MAX; mbc++) {
165*695dd8d1SYuri Pankov 			if ((ret - mbc) < start)
166*695dd8d1SYuri Pankov 				return (NULL);
167*695dd8d1SYuri Pankov 			memset(&mbs, 0, sizeof (mbs));
168*695dd8d1SYuri Pankov 			clen = mbrtowc(NULL, ret - mbc, mbc, &mbs);
169*695dd8d1SYuri Pankov 			if (clen != (size_t)-1 && clen != (size_t)-2)
170*695dd8d1SYuri Pankov 				break;
171*695dd8d1SYuri Pankov 		}
172*695dd8d1SYuri Pankov 		if (mbc > MB_CUR_MAX)
173*695dd8d1SYuri Pankov 			return (NULL);
174*695dd8d1SYuri Pankov 		ret -= mbc;
175*695dd8d1SYuri Pankov 	}
176*695dd8d1SYuri Pankov 
177*695dd8d1SYuri Pankov 	return (ret);
178*695dd8d1SYuri Pankov }
179*695dd8d1SYuri Pankov 
1804297a3b0SGarrett D'Amore /*
1814297a3b0SGarrett D'Amore  * matcher - the actual matching engine
1824297a3b0SGarrett D'Amore  */
1834297a3b0SGarrett D'Amore static int			/* 0 success, REG_NOMATCH failure */
matcher(struct re_guts * g,const char * string,size_t nmatch,regmatch_t pmatch[],int eflags)1847641c5eaSYuri Pankov matcher(struct re_guts *g, const char *string, size_t nmatch,
1857641c5eaSYuri Pankov     regmatch_t pmatch[], int eflags)
1864297a3b0SGarrett D'Amore {
1874297a3b0SGarrett D'Amore 	const char *endp;
1887641c5eaSYuri Pankov 	size_t i;
1894297a3b0SGarrett D'Amore 	struct match mv;
1904297a3b0SGarrett D'Amore 	struct match *m = &mv;
1917641c5eaSYuri Pankov 	const char *dp = NULL;
1924297a3b0SGarrett D'Amore 	const sopno gf = g->firststate+1;	/* +1 for OEND */
1934297a3b0SGarrett D'Amore 	const sopno gl = g->laststate;
1944297a3b0SGarrett D'Amore 	const char *start;
1954297a3b0SGarrett D'Amore 	const char *stop;
1964297a3b0SGarrett D'Amore 	/* Boyer-Moore algorithms variables */
1974297a3b0SGarrett D'Amore 	const char *pp;
1984297a3b0SGarrett D'Amore 	int cj, mj;
1994297a3b0SGarrett D'Amore 	const char *mustfirst;
2004297a3b0SGarrett D'Amore 	const char *mustlast;
2014297a3b0SGarrett D'Amore 	int *matchjump;
2024297a3b0SGarrett D'Amore 	int *charjump;
2034297a3b0SGarrett D'Amore 
2044297a3b0SGarrett D'Amore 	/* simplify the situation where possible */
2054297a3b0SGarrett D'Amore 	if (g->cflags&REG_NOSUB)
2064297a3b0SGarrett D'Amore 		nmatch = 0;
20784441f85SGarrett D'Amore 
2084297a3b0SGarrett D'Amore 	if (eflags&REG_STARTEND) {
2094297a3b0SGarrett D'Amore 		start = string + pmatch[0].rm_so;
2104297a3b0SGarrett D'Amore 		stop = string + pmatch[0].rm_eo;
2114297a3b0SGarrett D'Amore 	} else {
2124297a3b0SGarrett D'Amore 		start = string;
2134297a3b0SGarrett D'Amore 		stop = start + strlen(start);
2144297a3b0SGarrett D'Amore 	}
21584441f85SGarrett D'Amore 
2164297a3b0SGarrett D'Amore 	if (stop < start)
2174297a3b0SGarrett D'Amore 		return (REG_EFATAL);
2184297a3b0SGarrett D'Amore 
2194297a3b0SGarrett D'Amore 	/* prescreening; this does wonders for this rather slow code */
2204297a3b0SGarrett D'Amore 	if (g->must != NULL) {
2214297a3b0SGarrett D'Amore 		if (g->charjump != NULL && g->matchjump != NULL) {
2224297a3b0SGarrett D'Amore 			mustfirst = g->must;
2234297a3b0SGarrett D'Amore 			mustlast = g->must + g->mlen - 1;
2244297a3b0SGarrett D'Amore 			charjump = g->charjump;
2254297a3b0SGarrett D'Amore 			matchjump = g->matchjump;
2264297a3b0SGarrett D'Amore 			pp = mustlast;
2274297a3b0SGarrett D'Amore 			for (dp = start+g->mlen-1; dp < stop; ) {
2284297a3b0SGarrett D'Amore 				/* Fast skip non-matches */
2294297a3b0SGarrett D'Amore 				while (dp < stop && charjump[(int)*dp])
2304297a3b0SGarrett D'Amore 					dp += charjump[(int)*dp];
2314297a3b0SGarrett D'Amore 
2324297a3b0SGarrett D'Amore 				if (dp >= stop)
2334297a3b0SGarrett D'Amore 					break;
2344297a3b0SGarrett D'Amore 
2354297a3b0SGarrett D'Amore 				/* Greedy matcher */
2364297a3b0SGarrett D'Amore 				/*
2374297a3b0SGarrett D'Amore 				 * We depend on not being used for
2384297a3b0SGarrett D'Amore 				 * for strings of length 1
2394297a3b0SGarrett D'Amore 				 */
2404297a3b0SGarrett D'Amore 				while (*--dp == *--pp && pp != mustfirst)
2414297a3b0SGarrett D'Amore 					;
2424297a3b0SGarrett D'Amore 
2434297a3b0SGarrett D'Amore 				if (*dp == *pp)
2444297a3b0SGarrett D'Amore 					break;
2454297a3b0SGarrett D'Amore 
2464297a3b0SGarrett D'Amore 				/* Jump to next possible match */
2474297a3b0SGarrett D'Amore 				mj = matchjump[pp - mustfirst];
2484297a3b0SGarrett D'Amore 				cj = charjump[(int)*dp];
2494297a3b0SGarrett D'Amore 				dp += (cj < mj ? mj : cj);
2504297a3b0SGarrett D'Amore 				pp = mustlast;
2514297a3b0SGarrett D'Amore 			}
2524297a3b0SGarrett D'Amore 			if (pp != mustfirst)
2534297a3b0SGarrett D'Amore 				return (REG_NOMATCH);
2544297a3b0SGarrett D'Amore 		} else {
2554297a3b0SGarrett D'Amore 			for (dp = start; dp < stop; dp++)
2564297a3b0SGarrett D'Amore 				if (*dp == g->must[0] &&
2574297a3b0SGarrett D'Amore 				    stop - dp >= g->mlen &&
2584297a3b0SGarrett D'Amore 				    memcmp(dp, g->must, (size_t)g->mlen) == 0)
2594297a3b0SGarrett D'Amore 					break;
2604297a3b0SGarrett D'Amore 			if (dp == stop)		/* we didn't find g->must */
2614297a3b0SGarrett D'Amore 				return (REG_NOMATCH);
2624297a3b0SGarrett D'Amore 		}
2634297a3b0SGarrett D'Amore 	}
2644297a3b0SGarrett D'Amore 
2654297a3b0SGarrett D'Amore 	/* match struct setup */
2664297a3b0SGarrett D'Amore 	m->g = g;
2674297a3b0SGarrett D'Amore 	m->eflags = eflags;
2684297a3b0SGarrett D'Amore 	m->pmatch = NULL;
2694297a3b0SGarrett D'Amore 	m->lastpos = NULL;
2704297a3b0SGarrett D'Amore 	m->offp = string;
2714297a3b0SGarrett D'Amore 	m->beginp = start;
2724297a3b0SGarrett D'Amore 	m->endp = stop;
2734297a3b0SGarrett D'Amore 	STATESETUP(m, 4);
2744297a3b0SGarrett D'Amore 	SETUP(m->st);
2754297a3b0SGarrett D'Amore 	SETUP(m->fresh);
2764297a3b0SGarrett D'Amore 	SETUP(m->tmp);
2774297a3b0SGarrett D'Amore 	SETUP(m->empty);
2784297a3b0SGarrett D'Amore 	CLEAR(m->empty);
2794297a3b0SGarrett D'Amore 	ZAPSTATE(&m->mbs);
2804297a3b0SGarrett D'Amore 
2814297a3b0SGarrett D'Amore 	/* Adjust start according to moffset, to speed things up */
282*695dd8d1SYuri Pankov 	if (dp != NULL && g->moffset > -1) {
283*695dd8d1SYuri Pankov 		const char *nstart;
284*695dd8d1SYuri Pankov 
285*695dd8d1SYuri Pankov 		nstart = stepback(start, dp, g->moffset);
286*695dd8d1SYuri Pankov 		if (nstart != NULL)
287*695dd8d1SYuri Pankov 			start = nstart;
288*695dd8d1SYuri Pankov 	}
2894297a3b0SGarrett D'Amore 
2904297a3b0SGarrett D'Amore 	SP("mloop", m->st, *start);
2914297a3b0SGarrett D'Amore 
2924297a3b0SGarrett D'Amore 	/* this loop does only one repetition except for backrefs */
2934297a3b0SGarrett D'Amore 	for (;;) {
29462e74980SKyle Evans 		endp = walk(m, start, stop, gf, gl, true);
2954297a3b0SGarrett D'Amore 		if (endp == NULL) {		/* a miss */
2964297a3b0SGarrett D'Amore 			if (m->pmatch != NULL)
2974297a3b0SGarrett D'Amore 				free((char *)m->pmatch);
2984297a3b0SGarrett D'Amore 			if (m->lastpos != NULL)
2994297a3b0SGarrett D'Amore 				free((char *)m->lastpos);
3004297a3b0SGarrett D'Amore 			STATETEARDOWN(m);
3014297a3b0SGarrett D'Amore 			return (REG_NOMATCH);
3024297a3b0SGarrett D'Amore 		}
3034297a3b0SGarrett D'Amore 		if (nmatch == 0 && !g->backrefs)
3044297a3b0SGarrett D'Amore 			break;		/* no further info needed */
3054297a3b0SGarrett D'Amore 
3064297a3b0SGarrett D'Amore 		/* where? */
3074297a3b0SGarrett D'Amore 		assert(m->coldp != NULL);
3084297a3b0SGarrett D'Amore 		for (;;) {
3094297a3b0SGarrett D'Amore 			NOTE("finding start");
31062e74980SKyle Evans 			endp = walk(m, m->coldp, stop, gf, gl, false);
3114297a3b0SGarrett D'Amore 			if (endp != NULL)
3124297a3b0SGarrett D'Amore 				break;
3134297a3b0SGarrett D'Amore 			assert(m->coldp < m->endp);
3144297a3b0SGarrett D'Amore 			m->coldp += XMBRTOWC(NULL, m->coldp,
3154297a3b0SGarrett D'Amore 			    m->endp - m->coldp, &m->mbs, 0);
3164297a3b0SGarrett D'Amore 		}
3174297a3b0SGarrett D'Amore 		if (nmatch == 1 && !g->backrefs)
3184297a3b0SGarrett D'Amore 			break;		/* no further info needed */
3194297a3b0SGarrett D'Amore 
32048bbca81SDaniel Hoffman 		/* oh my, it wants the subexpressions... */
3214297a3b0SGarrett D'Amore 		if (m->pmatch == NULL)
3224297a3b0SGarrett D'Amore 			m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) *
3234297a3b0SGarrett D'Amore 			    sizeof (regmatch_t));
3244297a3b0SGarrett D'Amore 		if (m->pmatch == NULL) {
3254297a3b0SGarrett D'Amore 			STATETEARDOWN(m);
3264297a3b0SGarrett D'Amore 			return (REG_ESPACE);
3274297a3b0SGarrett D'Amore 		}
3284297a3b0SGarrett D'Amore 		for (i = 1; i <= m->g->nsub; i++)
3294297a3b0SGarrett D'Amore 			m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
330490fea6bSYuri Pankov 		if (!g->backrefs && !(m->eflags&REG_BACKR)) {
3314297a3b0SGarrett D'Amore 			NOTE("dissecting");
3324297a3b0SGarrett D'Amore 			dp = dissect(m, m->coldp, endp, gf, gl);
3334297a3b0SGarrett D'Amore 		} else {
3344297a3b0SGarrett D'Amore 			if (g->nplus > 0 && m->lastpos == NULL)
3354297a3b0SGarrett D'Amore 				m->lastpos = malloc((g->nplus+1) *
3364297a3b0SGarrett D'Amore 				    sizeof (const char *));
3374297a3b0SGarrett D'Amore 			if (g->nplus > 0 && m->lastpos == NULL) {
3384297a3b0SGarrett D'Amore 				free(m->pmatch);
3394297a3b0SGarrett D'Amore 				STATETEARDOWN(m);
3404297a3b0SGarrett D'Amore 				return (REG_ESPACE);
3414297a3b0SGarrett D'Amore 			}
3424297a3b0SGarrett D'Amore 			NOTE("backref dissect");
3434297a3b0SGarrett D'Amore 			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
3444297a3b0SGarrett D'Amore 		}
3454297a3b0SGarrett D'Amore 		if (dp != NULL)
3464297a3b0SGarrett D'Amore 			break;
3474297a3b0SGarrett D'Amore 
3484297a3b0SGarrett D'Amore 		/* uh-oh... we couldn't find a subexpression-level match */
3494297a3b0SGarrett D'Amore 		assert(g->backrefs);	/* must be back references doing it */
3504297a3b0SGarrett D'Amore 		assert(g->nplus == 0 || m->lastpos != NULL);
3514297a3b0SGarrett D'Amore 		for (;;) {
3524297a3b0SGarrett D'Amore 			if (dp != NULL || endp <= m->coldp)
3534297a3b0SGarrett D'Amore 				break;		/* defeat */
3544297a3b0SGarrett D'Amore 			NOTE("backoff");
35562e74980SKyle Evans 			endp = walk(m, m->coldp, endp-1, gf, gl, false);
3564297a3b0SGarrett D'Amore 			if (endp == NULL)
3574297a3b0SGarrett D'Amore 				break;		/* defeat */
3584297a3b0SGarrett D'Amore 			/* try it on a shorter possibility */
3594297a3b0SGarrett D'Amore #ifndef NDEBUG
3604297a3b0SGarrett D'Amore 			for (i = 1; i <= m->g->nsub; i++) {
3614297a3b0SGarrett D'Amore 				assert(m->pmatch[i].rm_so == -1);
3624297a3b0SGarrett D'Amore 				assert(m->pmatch[i].rm_eo == -1);
3634297a3b0SGarrett D'Amore 			}
3644297a3b0SGarrett D'Amore #endif
3654297a3b0SGarrett D'Amore 			NOTE("backoff dissect");
3664297a3b0SGarrett D'Amore 			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
3674297a3b0SGarrett D'Amore 		}
3684297a3b0SGarrett D'Amore 		assert(dp == NULL || dp == endp);
3694297a3b0SGarrett D'Amore 		if (dp != NULL)		/* found a shorter one */
3704297a3b0SGarrett D'Amore 			break;
3714297a3b0SGarrett D'Amore 
3724297a3b0SGarrett D'Amore 		/* despite initial appearances, there is no match here */
3734297a3b0SGarrett D'Amore 		NOTE("false alarm");
3744297a3b0SGarrett D'Amore 		/* recycle starting later */
3754297a3b0SGarrett D'Amore 		start = m->coldp + XMBRTOWC(NULL, m->coldp,
3764297a3b0SGarrett D'Amore 		    stop - m->coldp, &m->mbs, 0);
3774297a3b0SGarrett D'Amore 		assert(start <= stop);
3784297a3b0SGarrett D'Amore 	}
3794297a3b0SGarrett D'Amore 
3804297a3b0SGarrett D'Amore 	/* fill in the details if requested */
3814297a3b0SGarrett D'Amore 	if (nmatch > 0) {
3824297a3b0SGarrett D'Amore 		pmatch[0].rm_so = m->coldp - m->offp;
3834297a3b0SGarrett D'Amore 		pmatch[0].rm_eo = endp - m->offp;
3844297a3b0SGarrett D'Amore 	}
3854297a3b0SGarrett D'Amore 	if (nmatch > 1) {
3864297a3b0SGarrett D'Amore 		assert(m->pmatch != NULL);
3874297a3b0SGarrett D'Amore 		for (i = 1; i < nmatch; i++)
3884297a3b0SGarrett D'Amore 			if (i <= m->g->nsub)
3894297a3b0SGarrett D'Amore 				pmatch[i] = m->pmatch[i];
3904297a3b0SGarrett D'Amore 			else {
3914297a3b0SGarrett D'Amore 				pmatch[i].rm_so = -1;
3924297a3b0SGarrett D'Amore 				pmatch[i].rm_eo = -1;
3934297a3b0SGarrett D'Amore 			}
3944297a3b0SGarrett D'Amore 	}
3954297a3b0SGarrett D'Amore 
3964297a3b0SGarrett D'Amore 	if (m->pmatch != NULL)
3974297a3b0SGarrett D'Amore 		free((char *)m->pmatch);
3984297a3b0SGarrett D'Amore 	if (m->lastpos != NULL)
3994297a3b0SGarrett D'Amore 		free((char *)m->lastpos);
4004297a3b0SGarrett D'Amore 	STATETEARDOWN(m);
4014297a3b0SGarrett D'Amore 	return (0);
4024297a3b0SGarrett D'Amore }
4034297a3b0SGarrett D'Amore 
4044297a3b0SGarrett D'Amore /*
4054297a3b0SGarrett D'Amore  * dissect - figure out what matched what, no back references
4064297a3b0SGarrett D'Amore  */
4074297a3b0SGarrett D'Amore static const char *
dissect(struct match * m,const char * start,const char * stop,sopno startst,sopno stopst)4084297a3b0SGarrett D'Amore dissect(struct match *m, const char *start, const char *stop, sopno startst,
4094297a3b0SGarrett D'Amore     sopno stopst)
4104297a3b0SGarrett D'Amore {
4114297a3b0SGarrett D'Amore 	int i;
4124297a3b0SGarrett D'Amore 	sopno ss;		/* start sop of current subRE */
4134297a3b0SGarrett D'Amore 	sopno es;		/* end sop of current subRE */
4144297a3b0SGarrett D'Amore 	const char *sp;		/* start of string matched by it */
4154297a3b0SGarrett D'Amore 	const char *stp;	/* string matched by it cannot pass here */
4164297a3b0SGarrett D'Amore 	const char *rest;	/* start of rest of string */
4174297a3b0SGarrett D'Amore 	const char *tail;	/* string unmatched by rest of RE */
4184297a3b0SGarrett D'Amore 	sopno ssub;		/* start sop of subsubRE */
4194297a3b0SGarrett D'Amore 	sopno esub;		/* end sop of subsubRE */
4204297a3b0SGarrett D'Amore 	const char *ssp;	/* start of string matched by subsubRE */
4214297a3b0SGarrett D'Amore 	const char *sep;	/* end of string matched by subsubRE */
4224297a3b0SGarrett D'Amore 	const char *oldssp;	/* previous ssp */
4239c3b8506SToomas Soome 	const char *dp __unused;
4244297a3b0SGarrett D'Amore 
4254297a3b0SGarrett D'Amore 	AT("diss", start, stop, startst, stopst);
4264297a3b0SGarrett D'Amore 	sp = start;
4274297a3b0SGarrett D'Amore 	for (ss = startst; ss < stopst; ss = es) {
4284297a3b0SGarrett D'Amore 		/* identify end of subRE */
4294297a3b0SGarrett D'Amore 		es = ss;
4304297a3b0SGarrett D'Amore 		switch (OP(m->g->strip[es])) {
4314297a3b0SGarrett D'Amore 		case OPLUS_:
4324297a3b0SGarrett D'Amore 		case OQUEST_:
4334297a3b0SGarrett D'Amore 			es += OPND(m->g->strip[es]);
4344297a3b0SGarrett D'Amore 			break;
4354297a3b0SGarrett D'Amore 		case OCH_:
43662e74980SKyle Evans 			while (OP(m->g->strip[es]) != (sop)O_CH)
4374297a3b0SGarrett D'Amore 				es += OPND(m->g->strip[es]);
4384297a3b0SGarrett D'Amore 			break;
4394297a3b0SGarrett D'Amore 		}
4404297a3b0SGarrett D'Amore 		es++;
4414297a3b0SGarrett D'Amore 
4424297a3b0SGarrett D'Amore 		/* figure out what it matched */
4434297a3b0SGarrett D'Amore 		switch (OP(m->g->strip[ss])) {
4444297a3b0SGarrett D'Amore 		case OEND:
4454297a3b0SGarrett D'Amore 			assert(0);
4464297a3b0SGarrett D'Amore 			break;
4474297a3b0SGarrett D'Amore 		case OCHAR:
4484297a3b0SGarrett D'Amore 			sp += XMBRTOWC(NULL, sp, stop - start, &m->mbs, 0);
4494297a3b0SGarrett D'Amore 			break;
4504297a3b0SGarrett D'Amore 		case OBOL:
4514297a3b0SGarrett D'Amore 		case OEOL:
4524297a3b0SGarrett D'Amore 		case OBOW:
4534297a3b0SGarrett D'Amore 		case OEOW:
4544297a3b0SGarrett D'Amore 			break;
4554297a3b0SGarrett D'Amore 		case OANY:
4564297a3b0SGarrett D'Amore 		case OANYOF:
4574297a3b0SGarrett D'Amore 			sp += XMBRTOWC(NULL, sp, stop - start, &m->mbs, 0);
4584297a3b0SGarrett D'Amore 			break;
4594297a3b0SGarrett D'Amore 		case OBACK_:
4604297a3b0SGarrett D'Amore 		case O_BACK:
4614297a3b0SGarrett D'Amore 			assert(0);
4624297a3b0SGarrett D'Amore 			break;
4634297a3b0SGarrett D'Amore 		/* cases where length of match is hard to find */
4644297a3b0SGarrett D'Amore 		case OQUEST_:
4654297a3b0SGarrett D'Amore 			stp = stop;
4664297a3b0SGarrett D'Amore 			for (;;) {
4674297a3b0SGarrett D'Amore 				/* how long could this one be? */
46862e74980SKyle Evans 				rest = walk(m, sp, stp, ss, es, false);
4694297a3b0SGarrett D'Amore 				assert(rest != NULL);	/* it did match */
4704297a3b0SGarrett D'Amore 				/* could the rest match the rest? */
47162e74980SKyle Evans 				tail = walk(m, rest, stop, es, stopst, false);
4724297a3b0SGarrett D'Amore 				if (tail == stop)
4734297a3b0SGarrett D'Amore 					break;		/* yes! */
4744297a3b0SGarrett D'Amore 				/* no -- try a shorter match for this one */
4754297a3b0SGarrett D'Amore 				stp = rest - 1;
4764297a3b0SGarrett D'Amore 				assert(stp >= sp);	/* it did work */
4774297a3b0SGarrett D'Amore 			}
4784297a3b0SGarrett D'Amore 			ssub = ss + 1;
4794297a3b0SGarrett D'Amore 			esub = es - 1;
4804297a3b0SGarrett D'Amore 			/* did innards match? */
48162e74980SKyle Evans 			if (walk(m, sp, rest, ssub, esub, false) != NULL) {
4824297a3b0SGarrett D'Amore 				dp = dissect(m, sp, rest, ssub, esub);
4834297a3b0SGarrett D'Amore 				assert(dp == rest);
4844297a3b0SGarrett D'Amore 			} else		/* no */
4854297a3b0SGarrett D'Amore 				assert(sp == rest);
4864297a3b0SGarrett D'Amore 			sp = rest;
4874297a3b0SGarrett D'Amore 			break;
4884297a3b0SGarrett D'Amore 		case OPLUS_:
4894297a3b0SGarrett D'Amore 			stp = stop;
4904297a3b0SGarrett D'Amore 			for (;;) {
4914297a3b0SGarrett D'Amore 				/* how long could this one be? */
49262e74980SKyle Evans 				rest = walk(m, sp, stp, ss, es, false);
4934297a3b0SGarrett D'Amore 				assert(rest != NULL);	/* it did match */
4944297a3b0SGarrett D'Amore 				/* could the rest match the rest? */
49562e74980SKyle Evans 				tail = walk(m, rest, stop, es, stopst, false);
4964297a3b0SGarrett D'Amore 				if (tail == stop)
4974297a3b0SGarrett D'Amore 					break;		/* yes! */
4984297a3b0SGarrett D'Amore 				/* no -- try a shorter match for this one */
4994297a3b0SGarrett D'Amore 				stp = rest - 1;
5004297a3b0SGarrett D'Amore 				assert(stp >= sp);	/* it did work */
5014297a3b0SGarrett D'Amore 			}
5024297a3b0SGarrett D'Amore 			ssub = ss + 1;
5034297a3b0SGarrett D'Amore 			esub = es - 1;
5044297a3b0SGarrett D'Amore 			ssp = sp;
5054297a3b0SGarrett D'Amore 			oldssp = ssp;
5064297a3b0SGarrett D'Amore 			for (;;) {	/* find last match of innards */
50762e74980SKyle Evans 				sep = walk(m, ssp, rest, ssub, esub, false);
5084297a3b0SGarrett D'Amore 				if (sep == NULL || sep == ssp)
5094297a3b0SGarrett D'Amore 					break;	/* failed or matched null */
5104297a3b0SGarrett D'Amore 				oldssp = ssp;	/* on to next try */
5114297a3b0SGarrett D'Amore 				ssp = sep;
5124297a3b0SGarrett D'Amore 			}
5134297a3b0SGarrett D'Amore 			if (sep == NULL) {
5144297a3b0SGarrett D'Amore 				/* last successful match */
5154297a3b0SGarrett D'Amore 				sep = ssp;
5164297a3b0SGarrett D'Amore 				ssp = oldssp;
5174297a3b0SGarrett D'Amore 			}
5184297a3b0SGarrett D'Amore 			assert(sep == rest);	/* must exhaust substring */
51962e74980SKyle Evans 			assert(walk(m, ssp, sep, ssub, esub, false) == rest);
5204297a3b0SGarrett D'Amore 			dp = dissect(m, ssp, sep, ssub, esub);
5214297a3b0SGarrett D'Amore 			assert(dp == sep);
5224297a3b0SGarrett D'Amore 			sp = rest;
5234297a3b0SGarrett D'Amore 			break;
5244297a3b0SGarrett D'Amore 		case OCH_:
5254297a3b0SGarrett D'Amore 			stp = stop;
5264297a3b0SGarrett D'Amore 			for (;;) {
5274297a3b0SGarrett D'Amore 				/* how long could this one be? */
52862e74980SKyle Evans 				rest = walk(m, sp, stp, ss, es, false);
5294297a3b0SGarrett D'Amore 				assert(rest != NULL);	/* it did match */
5304297a3b0SGarrett D'Amore 				/* could the rest match the rest? */
53162e74980SKyle Evans 				tail = walk(m, rest, stop, es, stopst, false);
5324297a3b0SGarrett D'Amore 				if (tail == stop)
5334297a3b0SGarrett D'Amore 					break;		/* yes! */
5344297a3b0SGarrett D'Amore 				/* no -- try a shorter match for this one */
5354297a3b0SGarrett D'Amore 				stp = rest - 1;
5364297a3b0SGarrett D'Amore 				assert(stp >= sp);	/* it did work */
5374297a3b0SGarrett D'Amore 			}
5384297a3b0SGarrett D'Amore 			ssub = ss + 1;
5394297a3b0SGarrett D'Amore 			esub = ss + OPND(m->g->strip[ss]) - 1;
5404297a3b0SGarrett D'Amore 			assert(OP(m->g->strip[esub]) == OOR1);
5414297a3b0SGarrett D'Amore 			for (;;) {	/* find first matching branch */
54262e74980SKyle Evans 				if (walk(m, sp, rest, ssub, esub,
54362e74980SKyle Evans 				    false) == rest)
5444297a3b0SGarrett D'Amore 					break;	/* it matched all of it */
5454297a3b0SGarrett D'Amore 				/* that one missed, try next one */
5464297a3b0SGarrett D'Amore 				assert(OP(m->g->strip[esub]) == OOR1);
5474297a3b0SGarrett D'Amore 				esub++;
5484297a3b0SGarrett D'Amore 				assert(OP(m->g->strip[esub]) == OOR2);
5494297a3b0SGarrett D'Amore 				ssub = esub + 1;
5504297a3b0SGarrett D'Amore 				esub += OPND(m->g->strip[esub]);
55162e74980SKyle Evans 				if (OP(m->g->strip[esub]) == (sop)OOR2)
5524297a3b0SGarrett D'Amore 					esub--;
5534297a3b0SGarrett D'Amore 				else
5544297a3b0SGarrett D'Amore 					assert(OP(m->g->strip[esub]) == O_CH);
5554297a3b0SGarrett D'Amore 			}
5564297a3b0SGarrett D'Amore 			dp = dissect(m, sp, rest, ssub, esub);
5574297a3b0SGarrett D'Amore 			assert(dp == rest);
5584297a3b0SGarrett D'Amore 			sp = rest;
5594297a3b0SGarrett D'Amore 			break;
5604297a3b0SGarrett D'Amore 		case O_PLUS:
5614297a3b0SGarrett D'Amore 		case O_QUEST:
5624297a3b0SGarrett D'Amore 		case OOR1:
5634297a3b0SGarrett D'Amore 		case OOR2:
5644297a3b0SGarrett D'Amore 		case O_CH:
5654297a3b0SGarrett D'Amore 			assert(0);
5664297a3b0SGarrett D'Amore 			break;
5674297a3b0SGarrett D'Amore 		case OLPAREN:
5684297a3b0SGarrett D'Amore 			i = OPND(m->g->strip[ss]);
5694297a3b0SGarrett D'Amore 			assert(0 < i && i <= m->g->nsub);
5704297a3b0SGarrett D'Amore 			m->pmatch[i].rm_so = sp - m->offp;
5714297a3b0SGarrett D'Amore 			break;
5724297a3b0SGarrett D'Amore 		case ORPAREN:
5734297a3b0SGarrett D'Amore 			i = OPND(m->g->strip[ss]);
5744297a3b0SGarrett D'Amore 			assert(0 < i && i <= m->g->nsub);
5754297a3b0SGarrett D'Amore 			m->pmatch[i].rm_eo = sp - m->offp;
5764297a3b0SGarrett D'Amore 			break;
5774297a3b0SGarrett D'Amore 		default:		/* uh oh */
5784297a3b0SGarrett D'Amore 			assert(0);
5794297a3b0SGarrett D'Amore 			break;
5804297a3b0SGarrett D'Amore 		}
5814297a3b0SGarrett D'Amore 	}
5824297a3b0SGarrett D'Amore 
5834297a3b0SGarrett D'Amore 	assert(sp == stop);
5844297a3b0SGarrett D'Amore 	return (sp);
5854297a3b0SGarrett D'Amore }
5864297a3b0SGarrett D'Amore 
5874297a3b0SGarrett D'Amore /*
5884297a3b0SGarrett D'Amore  * backref - figure out what matched what, figuring in back references
5894297a3b0SGarrett D'Amore  */
5904297a3b0SGarrett D'Amore static const char *
backref(struct match * m,const char * start,const char * stop,sopno startst,sopno stopst,sopno lev,int rec)5914297a3b0SGarrett D'Amore backref(struct match *m, const char *start, const char *stop, sopno startst,
5924297a3b0SGarrett D'Amore     sopno stopst, sopno lev,		/* PLUS nesting level */
5934297a3b0SGarrett D'Amore     int rec)
5944297a3b0SGarrett D'Amore {
5954297a3b0SGarrett D'Amore 	int i;
5964297a3b0SGarrett D'Amore 	sopno ss;		/* start sop of current subRE */
5974297a3b0SGarrett D'Amore 	const char *sp;		/* start of string matched by it */
5984297a3b0SGarrett D'Amore 	sopno ssub;		/* start sop of subsubRE */
5994297a3b0SGarrett D'Amore 	sopno esub;		/* end sop of subsubRE */
6004297a3b0SGarrett D'Amore 	const char *ssp;	/* start of string matched by subsubRE */
6014297a3b0SGarrett D'Amore 	const char *dp;
6024297a3b0SGarrett D'Amore 	size_t len;
6034297a3b0SGarrett D'Amore 	int hard;
6044297a3b0SGarrett D'Amore 	sop s;
6054297a3b0SGarrett D'Amore 	regoff_t offsave;
6064297a3b0SGarrett D'Amore 	cset *cs;
6074297a3b0SGarrett D'Amore 	wint_t wc;
6084297a3b0SGarrett D'Amore 
6094297a3b0SGarrett D'Amore 	AT("back", start, stop, startst, stopst);
6104297a3b0SGarrett D'Amore 	sp = start;
6114297a3b0SGarrett D'Amore 
6124297a3b0SGarrett D'Amore 	/* get as far as we can with easy stuff */
6134297a3b0SGarrett D'Amore 	hard = 0;
6144297a3b0SGarrett D'Amore 	for (ss = startst; !hard && ss < stopst; ss++)
6154297a3b0SGarrett D'Amore 		switch (OP(s = m->g->strip[ss])) {
6164297a3b0SGarrett D'Amore 		case OCHAR:
6174297a3b0SGarrett D'Amore 			if (sp == stop)
6184297a3b0SGarrett D'Amore 				return (NULL);
6194297a3b0SGarrett D'Amore 			sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR);
6204297a3b0SGarrett D'Amore 			if (wc != OPND(s))
6214297a3b0SGarrett D'Amore 				return (NULL);
6224297a3b0SGarrett D'Amore 			break;
6234297a3b0SGarrett D'Amore 		case OANY:
6244297a3b0SGarrett D'Amore 			if (sp == stop)
6254297a3b0SGarrett D'Amore 				return (NULL);
6264297a3b0SGarrett D'Amore 			sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR);
6274297a3b0SGarrett D'Amore 			if (wc == BADCHAR)
6284297a3b0SGarrett D'Amore 				return (NULL);
6294297a3b0SGarrett D'Amore 			break;
6304297a3b0SGarrett D'Amore 		case OANYOF:
6314297a3b0SGarrett D'Amore 			if (sp == stop)
6324297a3b0SGarrett D'Amore 				return (NULL);
6334297a3b0SGarrett D'Amore 			cs = &m->g->sets[OPND(s)];
6344297a3b0SGarrett D'Amore 			sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR);
6354297a3b0SGarrett D'Amore 			if (wc == BADCHAR || !CHIN(cs, wc))
6364297a3b0SGarrett D'Amore 				return (NULL);
6374297a3b0SGarrett D'Amore 			break;
6384297a3b0SGarrett D'Amore 		case OBOL:
6394297a3b0SGarrett D'Amore 			if ((sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
6407641c5eaSYuri Pankov 			    (sp > m->offp && sp < m->endp &&
6417641c5eaSYuri Pankov 			    *(sp-1) == '\n' && (m->g->cflags&REG_NEWLINE))) {
6424297a3b0SGarrett D'Amore 				break;
6434297a3b0SGarrett D'Amore 			}
64433f5ff17SMilan Jurik 			return (NULL);
6454297a3b0SGarrett D'Amore 		case OEOL:
6464297a3b0SGarrett D'Amore 			if ((sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
6474297a3b0SGarrett D'Amore 			    (sp < m->endp && *sp == '\n' &&
6484297a3b0SGarrett D'Amore 			    (m->g->cflags&REG_NEWLINE))) {
6494297a3b0SGarrett D'Amore 				break;
6504297a3b0SGarrett D'Amore 			}
65133f5ff17SMilan Jurik 			return (NULL);
6524297a3b0SGarrett D'Amore 		case OBOW:
6537641c5eaSYuri Pankov 			if (sp < m->endp && ISWORD(*sp) &&
6547641c5eaSYuri Pankov 			    ((sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
6557641c5eaSYuri Pankov 			    (sp > m->offp && !ISWORD(*(sp-1))))) {
6564297a3b0SGarrett D'Amore 				break;
65733f5ff17SMilan Jurik 			}
65833f5ff17SMilan Jurik 			return (NULL);
6594297a3b0SGarrett D'Amore 		case OEOW:
6604297a3b0SGarrett D'Amore 			if (((sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
6614297a3b0SGarrett D'Amore 			    (sp < m->endp && *sp == '\n' &&
6624297a3b0SGarrett D'Amore 			    (m->g->cflags&REG_NEWLINE)) ||
6634297a3b0SGarrett D'Amore 			    (sp < m->endp && !ISWORD(*sp))) &&
6644297a3b0SGarrett D'Amore 			    (sp > m->beginp && ISWORD(*(sp-1)))) {
6654297a3b0SGarrett D'Amore 				break;
66633f5ff17SMilan Jurik 			}
66733f5ff17SMilan Jurik 			return (NULL);
6684297a3b0SGarrett D'Amore 		case O_QUEST:
6694297a3b0SGarrett D'Amore 			break;
6704297a3b0SGarrett D'Amore 		case OOR1:	/* matches null but needs to skip */
6714297a3b0SGarrett D'Amore 			ss++;
6724297a3b0SGarrett D'Amore 			s = m->g->strip[ss];
6734297a3b0SGarrett D'Amore 			do {
6744297a3b0SGarrett D'Amore 				assert(OP(s) == OOR2);
6754297a3b0SGarrett D'Amore 				ss += OPND(s);
67662e74980SKyle Evans 			} while (OP(s = m->g->strip[ss]) != (sop)O_CH);
6774297a3b0SGarrett D'Amore 			/* note that the ss++ gets us past the O_CH */
6784297a3b0SGarrett D'Amore 			break;
6794297a3b0SGarrett D'Amore 		default:	/* have to make a choice */
6804297a3b0SGarrett D'Amore 			hard = 1;
6814297a3b0SGarrett D'Amore 			break;
6824297a3b0SGarrett D'Amore 		}
6834297a3b0SGarrett D'Amore 	if (!hard) {		/* that was it! */
6844297a3b0SGarrett D'Amore 		if (sp != stop)
6854297a3b0SGarrett D'Amore 			return (NULL);
6864297a3b0SGarrett D'Amore 		return (sp);
6874297a3b0SGarrett D'Amore 	}
6884297a3b0SGarrett D'Amore 	ss--;			/* adjust for the for's final increment */
6894297a3b0SGarrett D'Amore 
6904297a3b0SGarrett D'Amore 	/* the hard stuff */
6914297a3b0SGarrett D'Amore 	AT("hard", sp, stop, ss, stopst);
6924297a3b0SGarrett D'Amore 	s = m->g->strip[ss];
6934297a3b0SGarrett D'Amore 	switch (OP(s)) {
6944297a3b0SGarrett D'Amore 	case OBACK_:		/* the vilest depths */
6954297a3b0SGarrett D'Amore 		i = OPND(s);
6964297a3b0SGarrett D'Amore 		assert(0 < i && i <= m->g->nsub);
6974297a3b0SGarrett D'Amore 		if (m->pmatch[i].rm_eo == -1)
6984297a3b0SGarrett D'Amore 			return (NULL);
6994297a3b0SGarrett D'Amore 		assert(m->pmatch[i].rm_so != -1);
7004297a3b0SGarrett D'Amore 		len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
7014297a3b0SGarrett D'Amore 		if (len == 0 && rec++ > MAX_RECURSION)
7024297a3b0SGarrett D'Amore 			return (NULL);
7034297a3b0SGarrett D'Amore 		assert(stop - m->beginp >= len);
7044297a3b0SGarrett D'Amore 		if (sp > stop - len)
7054297a3b0SGarrett D'Amore 			return (NULL);	/* not enough left to match */
7064297a3b0SGarrett D'Amore 		ssp = m->offp + m->pmatch[i].rm_so;
7074297a3b0SGarrett D'Amore 		if (memcmp(sp, ssp, len) != 0)
7084297a3b0SGarrett D'Amore 			return (NULL);
70962e74980SKyle Evans 		while (m->g->strip[ss] != (sop)SOP(O_BACK, i))
7104297a3b0SGarrett D'Amore 			ss++;
7114297a3b0SGarrett D'Amore 		return (backref(m, sp+len, stop, ss+1, stopst, lev, rec));
7124297a3b0SGarrett D'Amore 	case OQUEST_:		/* to null or not */
7134297a3b0SGarrett D'Amore 		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
7144297a3b0SGarrett D'Amore 		if (dp != NULL)
7154297a3b0SGarrett D'Amore 			return (dp);	/* not */
7164297a3b0SGarrett D'Amore 		return (backref(m, sp, stop, ss+OPND(s)+1, stopst, lev, rec));
7174297a3b0SGarrett D'Amore 	case OPLUS_:
7184297a3b0SGarrett D'Amore 		assert(m->lastpos != NULL);
7194297a3b0SGarrett D'Amore 		assert(lev+1 <= m->g->nplus);
7204297a3b0SGarrett D'Amore 		m->lastpos[lev+1] = sp;
7214297a3b0SGarrett D'Amore 		return (backref(m, sp, stop, ss+1, stopst, lev+1, rec));
7224297a3b0SGarrett D'Amore 	case O_PLUS:
7234297a3b0SGarrett D'Amore 		if (sp == m->lastpos[lev])	/* last pass matched null */
7244297a3b0SGarrett D'Amore 			return (backref(m, sp, stop, ss+1, stopst, lev-1, rec));
7254297a3b0SGarrett D'Amore 		/* try another pass */
7264297a3b0SGarrett D'Amore 		m->lastpos[lev] = sp;
7274297a3b0SGarrett D'Amore 		dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev, rec);
7284297a3b0SGarrett D'Amore 		if (dp == NULL)
7294297a3b0SGarrett D'Amore 			return (backref(m, sp, stop, ss+1, stopst, lev-1, rec));
73033f5ff17SMilan Jurik 		return (dp);
7314297a3b0SGarrett D'Amore 	case OCH_:		/* find the right one, if any */
7324297a3b0SGarrett D'Amore 		ssub = ss + 1;
7334297a3b0SGarrett D'Amore 		esub = ss + OPND(s) - 1;
7344297a3b0SGarrett D'Amore 		assert(OP(m->g->strip[esub]) == OOR1);
7354297a3b0SGarrett D'Amore 		for (;;) {	/* find first matching branch */
7364297a3b0SGarrett D'Amore 			dp = backref(m, sp, stop, ssub, esub, lev, rec);
7374297a3b0SGarrett D'Amore 			if (dp != NULL)
7384297a3b0SGarrett D'Amore 				return (dp);
7394297a3b0SGarrett D'Amore 			/* that one missed, try next one */
74062e74980SKyle Evans 			if (OP(m->g->strip[esub]) == (sop)O_CH)
7414297a3b0SGarrett D'Amore 				return (NULL);	/* there is none */
7424297a3b0SGarrett D'Amore 			esub++;
74362e74980SKyle Evans 			assert(OP(m->g->strip[esub]) == (sop)OOR2);
7444297a3b0SGarrett D'Amore 			ssub = esub + 1;
7454297a3b0SGarrett D'Amore 			esub += OPND(m->g->strip[esub]);
74662e74980SKyle Evans 			if (OP(m->g->strip[esub]) == (sop)OOR2)
7474297a3b0SGarrett D'Amore 				esub--;
7484297a3b0SGarrett D'Amore 			else
7494297a3b0SGarrett D'Amore 				assert(OP(m->g->strip[esub]) == O_CH);
7504297a3b0SGarrett D'Amore 		}
75133f5ff17SMilan Jurik 		/* NOTREACHED */
7524297a3b0SGarrett D'Amore 		break;
7534297a3b0SGarrett D'Amore 	case OLPAREN:		/* must undo assignment if rest fails */
7544297a3b0SGarrett D'Amore 		i = OPND(s);
7554297a3b0SGarrett D'Amore 		assert(0 < i && i <= m->g->nsub);
7564297a3b0SGarrett D'Amore 		offsave = m->pmatch[i].rm_so;
7574297a3b0SGarrett D'Amore 		m->pmatch[i].rm_so = sp - m->offp;
7584297a3b0SGarrett D'Amore 		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
7594297a3b0SGarrett D'Amore 		if (dp != NULL)
7604297a3b0SGarrett D'Amore 			return (dp);
7614297a3b0SGarrett D'Amore 		m->pmatch[i].rm_so = offsave;
7624297a3b0SGarrett D'Amore 		return (NULL);
7634297a3b0SGarrett D'Amore 	case ORPAREN:		/* must undo assignment if rest fails */
7644297a3b0SGarrett D'Amore 		i = OPND(s);
7654297a3b0SGarrett D'Amore 		assert(0 < i && i <= m->g->nsub);
7664297a3b0SGarrett D'Amore 		offsave = m->pmatch[i].rm_eo;
7674297a3b0SGarrett D'Amore 		m->pmatch[i].rm_eo = sp - m->offp;
7684297a3b0SGarrett D'Amore 		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
7694297a3b0SGarrett D'Amore 		if (dp != NULL)
7704297a3b0SGarrett D'Amore 			return (dp);
7714297a3b0SGarrett D'Amore 		m->pmatch[i].rm_eo = offsave;
7724297a3b0SGarrett D'Amore 		return (NULL);
7734297a3b0SGarrett D'Amore 	default:		/* uh oh */
7744297a3b0SGarrett D'Amore 		assert(0);
7754297a3b0SGarrett D'Amore 		break;
7764297a3b0SGarrett D'Amore 	}
7774297a3b0SGarrett D'Amore 
7784297a3b0SGarrett D'Amore 	/* "can't happen" */
7794297a3b0SGarrett D'Amore 	assert(0);
7804297a3b0SGarrett D'Amore 	return (NULL);
7814297a3b0SGarrett D'Amore }
7824297a3b0SGarrett D'Amore 
7834297a3b0SGarrett D'Amore /*
78462e74980SKyle Evans  * Step through the string either quickly or slowly.  Returns where it ended
78562e74980SKyle Evans  * or NULL.
7864297a3b0SGarrett D'Amore  */
7874297a3b0SGarrett D'Amore static const char *
walk(struct match * m,const char * start,const char * stop,sopno startst,sopno stopst,bool fast)78862e74980SKyle Evans walk(struct match *m, const char *start, const char *stop, sopno startst,
78962e74980SKyle Evans     sopno stopst, bool fast)
7904297a3b0SGarrett D'Amore {
7914297a3b0SGarrett D'Amore 	states st = m->st;
7924297a3b0SGarrett D'Amore 	states fresh = m->fresh;
7934297a3b0SGarrett D'Amore 	states empty = m->empty;
7944297a3b0SGarrett D'Amore 	states tmp = m->tmp;
7954297a3b0SGarrett D'Amore 	const char *p = start;
7964297a3b0SGarrett D'Amore 	wint_t c;
7974297a3b0SGarrett D'Amore 	wint_t lastc;		/* previous c */
7984297a3b0SGarrett D'Amore 	wint_t flagch;
7994297a3b0SGarrett D'Amore 	int i;
8004297a3b0SGarrett D'Amore 	const char *matchp;	/* last p at which a match ended */
8014297a3b0SGarrett D'Amore 	size_t clen;
8024297a3b0SGarrett D'Amore 
8034297a3b0SGarrett D'Amore 	AT("slow", start, stop, startst, stopst);
8044297a3b0SGarrett D'Amore 	CLEAR(st);
8054297a3b0SGarrett D'Amore 	SET1(st, startst);
8064297a3b0SGarrett D'Amore 	SP("sstart", st, *p);
8074297a3b0SGarrett D'Amore 	st = step(m->g, startst, stopst, st, NOTHING, st);
80862e74980SKyle Evans 	if (fast)
80962e74980SKyle Evans 		ASSIGN(fresh, st);
8104297a3b0SGarrett D'Amore 	matchp = NULL;
8117641c5eaSYuri Pankov 	if (start == m->offp || (start == m->beginp && !(m->eflags&REG_NOTBOL)))
8124297a3b0SGarrett D'Amore 		c = OUT;
8134297a3b0SGarrett D'Amore 	else {
8144297a3b0SGarrett D'Amore 		/*
8154297a3b0SGarrett D'Amore 		 * XXX Wrong if the previous character was multi-byte.
8164297a3b0SGarrett D'Amore 		 * Newline never is (in encodings supported by FreeBSD),
8174297a3b0SGarrett D'Amore 		 * so this only breaks the ISWORD tests below.
8184297a3b0SGarrett D'Amore 		 */
8194297a3b0SGarrett D'Amore 		c = (uch)*(start - 1);
8204297a3b0SGarrett D'Amore 	}
8214297a3b0SGarrett D'Amore 	for (;;) {
8224297a3b0SGarrett D'Amore 		/* next character */
8234297a3b0SGarrett D'Amore 		lastc = c;
8244297a3b0SGarrett D'Amore 		if (p == m->endp) {
8254297a3b0SGarrett D'Amore 			c = OUT;
8264297a3b0SGarrett D'Amore 			clen = 0;
8274297a3b0SGarrett D'Amore 		} else
8284297a3b0SGarrett D'Amore 			clen = XMBRTOWC(&c, p, m->endp - p, &m->mbs, BADCHAR);
8294297a3b0SGarrett D'Amore 
83062e74980SKyle Evans 		if (fast && EQ(st, fresh))
83162e74980SKyle Evans 			matchp = p;
83262e74980SKyle Evans 
8334297a3b0SGarrett D'Amore 		/* is there an EOL and/or BOL between lastc and c? */
8344297a3b0SGarrett D'Amore 		flagch = '\0';
8354297a3b0SGarrett D'Amore 		i = 0;
8364297a3b0SGarrett D'Amore 		if ((lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
8374297a3b0SGarrett D'Amore 		    (lastc == OUT && !(m->eflags&REG_NOTBOL))) {
8384297a3b0SGarrett D'Amore 			flagch = BOL;
8394297a3b0SGarrett D'Amore 			i = m->g->nbol;
8404297a3b0SGarrett D'Amore 		}
8414297a3b0SGarrett D'Amore 		if ((c == '\n' && m->g->cflags&REG_NEWLINE) ||
8424297a3b0SGarrett D'Amore 		    (c == OUT && !(m->eflags&REG_NOTEOL))) {
8434297a3b0SGarrett D'Amore 			flagch = (flagch == BOL) ? BOLEOL : EOL;
8444297a3b0SGarrett D'Amore 			i += m->g->neol;
8454297a3b0SGarrett D'Amore 		}
8464297a3b0SGarrett D'Amore 		if (i != 0) {
8474297a3b0SGarrett D'Amore 			for (; i > 0; i--)
8484297a3b0SGarrett D'Amore 				st = step(m->g, startst, stopst, st,
8494297a3b0SGarrett D'Amore 				    flagch, st);
8504297a3b0SGarrett D'Amore 			SP("sboleol", st, c);
8514297a3b0SGarrett D'Amore 		}
8524297a3b0SGarrett D'Amore 
8534297a3b0SGarrett D'Amore 		/* how about a word boundary? */
8544297a3b0SGarrett D'Amore 		if ((flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
8554297a3b0SGarrett D'Amore 		    (c != OUT && ISWORD(c))) {
8564297a3b0SGarrett D'Amore 			flagch = BOW;
8574297a3b0SGarrett D'Amore 		}
8584297a3b0SGarrett D'Amore 		if ((lastc != OUT && ISWORD(lastc)) &&
8594297a3b0SGarrett D'Amore 		    (flagch == EOL || (c != OUT && !ISWORD(c)))) {
8604297a3b0SGarrett D'Amore 			flagch = EOW;
8614297a3b0SGarrett D'Amore 		}
8624297a3b0SGarrett D'Amore 		if (flagch == BOW || flagch == EOW) {
8634297a3b0SGarrett D'Amore 			st = step(m->g, startst, stopst, st, flagch, st);
8644297a3b0SGarrett D'Amore 			SP("sboweow", st, c);
8654297a3b0SGarrett D'Amore 		}
8664297a3b0SGarrett D'Amore 
8674297a3b0SGarrett D'Amore 		/* are we done? */
86862e74980SKyle Evans 		if (ISSET(st, stopst)) {
86962e74980SKyle Evans 			if (fast)
87062e74980SKyle Evans 				break;
87162e74980SKyle Evans 			else
87262e74980SKyle Evans 				matchp = p;
87362e74980SKyle Evans 		}
87462e74980SKyle Evans 		if (EQ(st, empty) || p == stop || clen > (size_t)(stop - p))
8754297a3b0SGarrett D'Amore 			break;		/* NOTE BREAK OUT */
8764297a3b0SGarrett D'Amore 
8774297a3b0SGarrett D'Amore 		/* no, we must deal with this character */
8784297a3b0SGarrett D'Amore 		ASSIGN(tmp, st);
87962e74980SKyle Evans 		if (fast)
88062e74980SKyle Evans 			ASSIGN(st, fresh);
88162e74980SKyle Evans 		else
88262e74980SKyle Evans 			ASSIGN(st, empty);
8834297a3b0SGarrett D'Amore 		assert(c != OUT);
8844297a3b0SGarrett D'Amore 		st = step(m->g, startst, stopst, tmp, c, st);
8854297a3b0SGarrett D'Amore 		SP("saft", st, c);
8864297a3b0SGarrett D'Amore 		assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
8874297a3b0SGarrett D'Amore 		p += clen;
8884297a3b0SGarrett D'Amore 	}
8894297a3b0SGarrett D'Amore 
89062e74980SKyle Evans 	if (fast) {
89162e74980SKyle Evans 		assert(matchp != NULL);
89262e74980SKyle Evans 		m->coldp = matchp;
89362e74980SKyle Evans 		if (ISSET(st, stopst))
89462e74980SKyle Evans 			return (p + XMBRTOWC(NULL, p, stop - p, &m->mbs, 0));
89562e74980SKyle Evans 		else
89662e74980SKyle Evans 			return (NULL);
89762e74980SKyle Evans 	} else
89862e74980SKyle Evans 		return (matchp);
8994297a3b0SGarrett D'Amore }
9004297a3b0SGarrett D'Amore 
9014297a3b0SGarrett D'Amore /*
9024297a3b0SGarrett D'Amore  * step - map set of states reachable before char to set reachable after
9034297a3b0SGarrett D'Amore  */
9044297a3b0SGarrett D'Amore static states
step(struct re_guts * g,sopno start,sopno stop,states bef,wint_t ch,states aft)9054297a3b0SGarrett D'Amore step(struct re_guts *g,
9067641c5eaSYuri Pankov     sopno start,	/* start state within strip */
9077641c5eaSYuri Pankov     sopno stop,		/* state after stop state within strip */
9087641c5eaSYuri Pankov     states bef,		/* states reachable before */
9097641c5eaSYuri Pankov     wint_t ch,		/* character or NONCHAR code */
9107641c5eaSYuri Pankov     states aft)		/* states already known reachable after */
9114297a3b0SGarrett D'Amore {
9124297a3b0SGarrett D'Amore 	cset *cs;
9134297a3b0SGarrett D'Amore 	sop s;
9144297a3b0SGarrett D'Amore 	sopno pc;
9154297a3b0SGarrett D'Amore 	onestate here;		/* note, macros know this name */
9164297a3b0SGarrett D'Amore 	sopno look;
9174297a3b0SGarrett D'Amore 	int i;
9184297a3b0SGarrett D'Amore 
9194297a3b0SGarrett D'Amore 	for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
9204297a3b0SGarrett D'Amore 		s = g->strip[pc];
9214297a3b0SGarrett D'Amore 		switch (OP(s)) {
9224297a3b0SGarrett D'Amore 		case OEND:
9234297a3b0SGarrett D'Amore 			assert(pc == stop-1);
9244297a3b0SGarrett D'Amore 			break;
9254297a3b0SGarrett D'Amore 		case OCHAR:
9264297a3b0SGarrett D'Amore 			/* only characters can match */
9274297a3b0SGarrett D'Amore 			assert(!NONCHAR(ch) || ch != OPND(s));
9284297a3b0SGarrett D'Amore 			if (ch == OPND(s))
9294297a3b0SGarrett D'Amore 				FWD(aft, bef, 1);
9304297a3b0SGarrett D'Amore 			break;
9314297a3b0SGarrett D'Amore 		case OBOL:
9324297a3b0SGarrett D'Amore 			if (ch == BOL || ch == BOLEOL)
9334297a3b0SGarrett D'Amore 				FWD(aft, bef, 1);
9344297a3b0SGarrett D'Amore 			break;
9354297a3b0SGarrett D'Amore 		case OEOL:
9364297a3b0SGarrett D'Amore 			if (ch == EOL || ch == BOLEOL)
9374297a3b0SGarrett D'Amore 				FWD(aft, bef, 1);
9384297a3b0SGarrett D'Amore 			break;
9394297a3b0SGarrett D'Amore 		case OBOW:
9404297a3b0SGarrett D'Amore 			if (ch == BOW)
9414297a3b0SGarrett D'Amore 				FWD(aft, bef, 1);
9424297a3b0SGarrett D'Amore 			break;
9434297a3b0SGarrett D'Amore 		case OEOW:
9444297a3b0SGarrett D'Amore 			if (ch == EOW)
9454297a3b0SGarrett D'Amore 				FWD(aft, bef, 1);
9464297a3b0SGarrett D'Amore 			break;
9474297a3b0SGarrett D'Amore 		case OANY:
9484297a3b0SGarrett D'Amore 			if (!NONCHAR(ch))
9494297a3b0SGarrett D'Amore 				FWD(aft, bef, 1);
9504297a3b0SGarrett D'Amore 			break;
9514297a3b0SGarrett D'Amore 		case OANYOF:
9524297a3b0SGarrett D'Amore 			cs = &g->sets[OPND(s)];
9534297a3b0SGarrett D'Amore 			if (!NONCHAR(ch) && CHIN(cs, ch))
9544297a3b0SGarrett D'Amore 				FWD(aft, bef, 1);
9554297a3b0SGarrett D'Amore 			break;
9564297a3b0SGarrett D'Amore 		case OBACK_:		/* ignored here */
9574297a3b0SGarrett D'Amore 		case O_BACK:
9584297a3b0SGarrett D'Amore 			FWD(aft, aft, 1);
9594297a3b0SGarrett D'Amore 			break;
9604297a3b0SGarrett D'Amore 		case OPLUS_:		/* forward, this is just an empty */
9614297a3b0SGarrett D'Amore 			FWD(aft, aft, 1);
9624297a3b0SGarrett D'Amore 			break;
9634297a3b0SGarrett D'Amore 		case O_PLUS:		/* both forward and back */
9644297a3b0SGarrett D'Amore 			FWD(aft, aft, 1);
9654297a3b0SGarrett D'Amore 			i = ISSETBACK(aft, OPND(s));
9664297a3b0SGarrett D'Amore 			BACK(aft, aft, OPND(s));
9674297a3b0SGarrett D'Amore 			if (!i && ISSETBACK(aft, OPND(s))) {
9684297a3b0SGarrett D'Amore 				/* oho, must reconsider loop body */
9694297a3b0SGarrett D'Amore 				pc -= OPND(s) + 1;
9704297a3b0SGarrett D'Amore 				INIT(here, pc);
9714297a3b0SGarrett D'Amore 			}
9724297a3b0SGarrett D'Amore 			break;
9734297a3b0SGarrett D'Amore 		case OQUEST_:		/* two branches, both forward */
9744297a3b0SGarrett D'Amore 			FWD(aft, aft, 1);
9754297a3b0SGarrett D'Amore 			FWD(aft, aft, OPND(s));
9764297a3b0SGarrett D'Amore 			break;
9774297a3b0SGarrett D'Amore 		case O_QUEST:		/* just an empty */
9784297a3b0SGarrett D'Amore 			FWD(aft, aft, 1);
9794297a3b0SGarrett D'Amore 			break;
9804297a3b0SGarrett D'Amore 		case OLPAREN:		/* not significant here */
9814297a3b0SGarrett D'Amore 		case ORPAREN:
9824297a3b0SGarrett D'Amore 			FWD(aft, aft, 1);
9834297a3b0SGarrett D'Amore 			break;
9844297a3b0SGarrett D'Amore 		case OCH_:		/* mark the first two branches */
9854297a3b0SGarrett D'Amore 			FWD(aft, aft, 1);
98662e74980SKyle Evans 			assert(OP(g->strip[pc+OPND(s)]) == (sop)OOR2);
9874297a3b0SGarrett D'Amore 			FWD(aft, aft, OPND(s));
9884297a3b0SGarrett D'Amore 			break;
9894297a3b0SGarrett D'Amore 		case OOR1:		/* done a branch, find the O_CH */
9904297a3b0SGarrett D'Amore 			if (ISSTATEIN(aft, here)) {
9914297a3b0SGarrett D'Amore 				for (look = 1;
99262e74980SKyle Evans 				    OP(s = g->strip[pc+look]) != (sop)O_CH;
9934297a3b0SGarrett D'Amore 				    look += OPND(s))
99462e74980SKyle Evans 					assert(OP(s) == (sop)OOR2);
9954297a3b0SGarrett D'Amore 				FWD(aft, aft, look + 1);
9964297a3b0SGarrett D'Amore 			}
9974297a3b0SGarrett D'Amore 			break;
9984297a3b0SGarrett D'Amore 		case OOR2:		/* propagate OCH_'s marking */
9994297a3b0SGarrett D'Amore 			FWD(aft, aft, 1);
100062e74980SKyle Evans 			if (OP(g->strip[pc+OPND(s)]) != (sop)O_CH) {
100162e74980SKyle Evans 				assert(OP(g->strip[pc+OPND(s)]) == (sop)OOR2);
10024297a3b0SGarrett D'Amore 				FWD(aft, aft, OPND(s));
10034297a3b0SGarrett D'Amore 			}
10044297a3b0SGarrett D'Amore 			break;
10054297a3b0SGarrett D'Amore 		case O_CH:		/* just empty */
10064297a3b0SGarrett D'Amore 			FWD(aft, aft, 1);
10074297a3b0SGarrett D'Amore 			break;
10084297a3b0SGarrett D'Amore 		default:		/* ooooops... */
10094297a3b0SGarrett D'Amore 			assert(0);
10104297a3b0SGarrett D'Amore 			break;
10114297a3b0SGarrett D'Amore 		}
10124297a3b0SGarrett D'Amore 	}
10134297a3b0SGarrett D'Amore 
10144297a3b0SGarrett D'Amore 	return (aft);
10154297a3b0SGarrett D'Amore }
10164297a3b0SGarrett D'Amore 
10174297a3b0SGarrett D'Amore #ifdef REDEBUG
10184297a3b0SGarrett D'Amore /*
10194297a3b0SGarrett D'Amore  * print - print a set of states
10204297a3b0SGarrett D'Amore  */
10214297a3b0SGarrett D'Amore static void
print(struct match * m,const char * caption,states st,int ch,FILE * d)10224297a3b0SGarrett D'Amore print(struct match *m, const char *caption, states st, int ch, FILE *d)
10234297a3b0SGarrett D'Amore {
10244297a3b0SGarrett D'Amore 	struct re_guts *g = m->g;
10257641c5eaSYuri Pankov 	sopno i;
10264297a3b0SGarrett D'Amore 	int first = 1;
10274297a3b0SGarrett D'Amore 
10284297a3b0SGarrett D'Amore 	if (!(m->eflags&REG_TRACE))
10294297a3b0SGarrett D'Amore 		return;
10304297a3b0SGarrett D'Amore 
10314297a3b0SGarrett D'Amore 	(void) fprintf(d, "%s", caption);
10324297a3b0SGarrett D'Amore 	if (ch != '\0')
10334297a3b0SGarrett D'Amore 		(void) fprintf(d, " %s", pchar(ch));
10344297a3b0SGarrett D'Amore 	for (i = 0; i < g->nstates; i++)
10354297a3b0SGarrett D'Amore 		if (ISSET(st, i)) {
10364297a3b0SGarrett D'Amore 			(void) fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
10374297a3b0SGarrett D'Amore 			first = 0;
10384297a3b0SGarrett D'Amore 		}
10394297a3b0SGarrett D'Amore 	(void) fprintf(d, "\n");
10404297a3b0SGarrett D'Amore }
10414297a3b0SGarrett D'Amore 
10424297a3b0SGarrett D'Amore /*
10434297a3b0SGarrett D'Amore  * at - print current situation
10444297a3b0SGarrett D'Amore  */
10454297a3b0SGarrett D'Amore static void
at(struct match * m,const char * title,const char * start,const char * stop,sopno startst,sopno stopst)10464297a3b0SGarrett D'Amore at(struct match *m, const char *title, const char *start, const char *stop,
10474297a3b0SGarrett D'Amore     sopno startst, sopno stopst)
10484297a3b0SGarrett D'Amore {
10494297a3b0SGarrett D'Amore 	if (!(m->eflags&REG_TRACE))
10504297a3b0SGarrett D'Amore 		return;
10514297a3b0SGarrett D'Amore 
10524297a3b0SGarrett D'Amore 	(void) printf("%s %s-", title, pchar(*start));
10534297a3b0SGarrett D'Amore 	(void) printf("%s ", pchar(*stop));
10544297a3b0SGarrett D'Amore 	(void) printf("%ld-%ld\n", (long)startst, (long)stopst);
10554297a3b0SGarrett D'Amore }
10564297a3b0SGarrett D'Amore 
10574297a3b0SGarrett D'Amore #ifndef PCHARDONE
10584297a3b0SGarrett D'Amore #define	PCHARDONE	/* never again */
10594297a3b0SGarrett D'Amore /*
10604297a3b0SGarrett D'Amore  * pchar - make a character printable
10614297a3b0SGarrett D'Amore  *
10624297a3b0SGarrett D'Amore  * Is this identical to regchar() over in debug.c?  Well, yes.  But a
10634297a3b0SGarrett D'Amore  * duplicate here avoids having a debugging-capable regexec.o tied to
10644297a3b0SGarrett D'Amore  * a matching debug.o, and this is convenient.  It all disappears in
10654297a3b0SGarrett D'Amore  * the non-debug compilation anyway, so it doesn't matter much.
10664297a3b0SGarrett D'Amore  */
10674297a3b0SGarrett D'Amore static const char *
pchar(int ch)10684297a3b0SGarrett D'Amore pchar(int ch)
10694297a3b0SGarrett D'Amore {
10704297a3b0SGarrett D'Amore 	static char pbuf[10];
10714297a3b0SGarrett D'Amore 
10724297a3b0SGarrett D'Amore 	if (isprint((uch)ch) || ch == ' ')
10734297a3b0SGarrett D'Amore 		(void) sprintf(pbuf, "%c", ch);
10744297a3b0SGarrett D'Amore 	else
10754297a3b0SGarrett D'Amore 		(void) sprintf(pbuf, "\\%o", ch);
10764297a3b0SGarrett D'Amore 	return (pbuf);
10774297a3b0SGarrett D'Amore }
10784297a3b0SGarrett D'Amore #endif
10794297a3b0SGarrett D'Amore #endif
10804297a3b0SGarrett D'Amore 
1081*695dd8d1SYuri Pankov #undef	stepback
10824297a3b0SGarrett D'Amore #undef	matcher
108362e74980SKyle Evans #undef	walk
10844297a3b0SGarrett D'Amore #undef	dissect
10854297a3b0SGarrett D'Amore #undef	backref
10864297a3b0SGarrett D'Amore #undef	step
10874297a3b0SGarrett D'Amore #undef	print
10884297a3b0SGarrett D'Amore #undef	at
10894297a3b0SGarrett D'Amore #undef	match
1090