Home | History | Annotate | Line # | Download | only in regex
      1 /* $NetBSD: engine.c,v 1.31 2026/11/16 17:36:40 christos Exp $ */
      2 
      3 /*-
      4  * SPDX-License-Identifier: BSD-3-Clause
      5  *
      6  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
      7  * Copyright (c) 1992, 1993, 1994
      8  *	The Regents of the University of California.  All rights reserved.
      9  *
     10  * This code is derived from software contributed to Berkeley by
     11  * Henry Spencer.
     12  *
     13  * Redistribution and use in source and binary forms, with or without
     14  * modification, are permitted provided that the following conditions
     15  * are met:
     16  * 1. Redistributions of source code must retain the above copyright
     17  *    notice, this list of conditions and the following disclaimer.
     18  * 2. Redistributions in binary form must reproduce the above copyright
     19  *    notice, this list of conditions and the following disclaimer in the
     20  *    documentation and/or other materials provided with the distribution.
     21  * 3. Neither the name of the University nor the names of its contributors
     22  *    may be used to endorse or promote products derived from this software
     23  *    without specific prior written permission.
     24  *
     25  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     26  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     27  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     28  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     29  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     30  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     31  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     32  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     33  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     34  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     35  * SUCH DAMAGE.
     36  *
     37  *	@(#)engine.c	8.5 (Berkeley) 3/20/94
     38  */
     39 
     40 #include <sys/cdefs.h>
     41 #ifdef __FBSDID
     42 __FBSDID("$FreeBSD: head/lib/libc/regex/engine.c 368358 2020-12-05 03:16:05Z kevans $");
     43 #endif
     44 __RCSID("$NetBSD: engine.c,v 1.31 2026/11/16 17:36:40 christos Exp $");
     45 
     46 #include <stdbool.h>
     47 
     48 /*
     49  * The matching engine and friends.  This file is #included by regexec.c
     50  * after suitable #defines of a variety of macros used herein, so that
     51  * different state representations can be used without duplicating masses
     52  * of code.
     53  */
     54 
     55 #ifdef SNAMES
     56 #define	stepback sstepback
     57 #define	prevchar sprevchar
     58 #define	matcher	smatcher
     59 #define	walk	swalk
     60 #define	dissect	sdissect
     61 #define	backref	sbackref
     62 #define	step	sstep
     63 #define	print	sprint
     64 #define	at	sat
     65 #define	match	smat
     66 #endif
     67 #ifdef LNAMES
     68 #define	stepback lstepback
     69 #define	prevchar lprevchar
     70 #define	matcher	lmatcher
     71 #define	walk	lwalk
     72 #define	dissect	ldissect
     73 #define	backref	lbackref
     74 #define	step	lstep
     75 #define	print	lprint
     76 #define	at	lat
     77 #define	match	lmat
     78 #endif
     79 #ifdef MNAMES
     80 #define	stepback mstepback
     81 #define	prevchar mprevchar
     82 #define	matcher	mmatcher
     83 #define	walk	mwalk
     84 #define	dissect	mdissect
     85 #define	backref	mbackref
     86 #define	step	mstep
     87 #define	print	mprint
     88 #define	at	mat
     89 #define	match	mmat
     90 #endif
     91 
     92 /* another structure passed up and down to avoid zillions of parameters */
     93 struct match {
     94 	struct re_guts *g;
     95 	int eflags;
     96 	regmatch_t *pmatch;	/* [nsub+1] (0 element unused) */
     97 	const char *offp;	/* offsets work from here */
     98 	const char *beginp;	/* start of string -- virtual NUL precedes */
     99 	const char *endp;	/* end of string -- virtual NUL here */
    100 	const char *coldp;	/* can be no match starting before here */
    101 	const char **lastpos;	/* [nplus+1] */
    102 	STATEVARS;
    103 	states st;		/* current states */
    104 	states fresh;		/* states for a fresh start */
    105 	states tmp;		/* temporary */
    106 	states empty;		/* empty set of states */
    107 	mbstate_t mbs;		/* multibyte conversion state */
    108 };
    109 
    110 /* ========= begin header generated by ./mkh ========= */
    111 #ifdef __cplusplus
    112 extern "C" {
    113 #endif
    114 
    115 /* === engine.c === */
    116 static int matcher(struct re_guts *g, const char *string, size_t nmatch, regmatch_t pmatch[], int eflags);
    117 static const char *dissect(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst);
    118 static const char *backref(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst, sopno lev, int);
    119 static const char *walk(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst, bool fast);
    120 static states step(struct re_guts *g, sopno start, sopno stop, states bef, wint_t ch, states aft, int sflags);
    121 #define MAX_RECURSION	100
    122 #define	BOL	(OUT-1)
    123 #define	EOL	(BOL-1)
    124 #define	BOLEOL	(BOL-2)
    125 #define	NOTHING	(BOL-3)
    126 #define	BOW	(BOL-4)
    127 #define	EOW	(BOL-5)
    128 #define	BADCHAR	(BOL-6)
    129 #define	NWBND	(BOL-7)
    130 #define	NONCHAR(c)	((c) <= OUT)
    131 /* sflags */
    132 #define	SBOS	0x0001
    133 #define	SEOS	0x0002
    134 
    135 #ifdef REDEBUG
    136 static void print(struct match *m, const char *caption, states st, int ch, FILE *d);
    137 #endif
    138 #ifdef REDEBUG
    139 static void at(struct match *m, const char *title, const char *start, const char *stop, sopno startst, sopno stopst);
    140 #endif
    141 #ifdef REDEBUG
    142 static const char *pchar(int ch);
    143 #endif
    144 
    145 #ifdef __cplusplus
    146 }
    147 #endif
    148 /* ========= end header generated by ./mkh ========= */
    149 
    150 #ifdef REDEBUG
    151 #define	SP(t, s, c)	print(m, t, s, c, stdout)
    152 #define	AT(t, p1, p2, s1, s2)	at(m, t, p1, p2, s1, s2)
    153 #define	NOTE(str)	{ if (m->eflags&REG_TRACE) printf("=%s\n", (str)); }
    154 #else
    155 #define	SP(t, s, c)	/* nothing */
    156 #define	AT(t, p1, p2, s1, s2)	/* nothing */
    157 #define	NOTE(s)	/* nothing */
    158 #endif
    159 
    160 /*
    161  * Given a multibyte string pointed to by start, step back nchar characters
    162  * from current position pointed to by cur.
    163  */
    164 static const char *
    165 stepback(const char *start, const char *cur, int nchar)
    166 {
    167 #ifdef NLS
    168 	const char *ret;
    169 	size_t wc, mbc;
    170 	mbstate_t mbs;
    171 	size_t clen;
    172 
    173 	if (MB_CUR_MAX == 1)
    174 		goto out;
    175 
    176 	ret = cur;
    177 	for (wc = nchar; wc > 0; wc--) {
    178 		for (mbc = 1; mbc <= MB_CUR_MAX; mbc++) {
    179 			if ((ret - mbc) < start)
    180 				return (NULL);
    181 			memset(&mbs, 0, sizeof(mbs));
    182 			clen = mbrtowc(NULL, ret - mbc, mbc, &mbs);
    183 			if (clen != (size_t)-1 && clen != (size_t)-2)
    184 				break;
    185 		}
    186 		if (mbc > MB_CUR_MAX)
    187 			return (NULL);
    188 		ret -= mbc;
    189 	}
    190 
    191 	return (ret);
    192 out:
    193 #endif
    194 	return (cur - nchar) > start ? cur - nchar : NULL;
    195 }
    196 
    197 /*
    198  * Return the character that ends at cur, without looking before start.
    199  * A multibyte character is decoded whole and an invalid byte gives
    200  * BADCHAR, so that a walk which starts at cur sees the same previous
    201  * character as a walk which reached cur from further left.
    202  */
    203 static wint_t
    204 prevchar(const char *start, const char *cur)
    205 {
    206 #ifdef NLS
    207 	mbstate_t mbs;
    208 	wchar_t wc;
    209 	size_t mbc, clen;
    210 
    211 	if (MB_CUR_MAX > 1) {
    212 		for (mbc = 1; mbc <= MB_CUR_MAX &&
    213 		    mbc <= (size_t)(cur - start); mbc++) {
    214 			memset(&mbs, 0, sizeof(mbs));
    215 			clen = mbrtowc(&wc, cur - mbc, mbc, &mbs);
    216 			if (clen == mbc || (clen == 0 && mbc == 1))
    217 				return wc;
    218 		}
    219 		return BADCHAR;
    220 	}
    221 #endif
    222 	return (uch)*(cur - 1);
    223 }
    224 
    225 /*
    226  - matcher - the actual matching engine
    227  == static int matcher(struct re_guts *g, const char *string, \
    228  ==	size_t nmatch, regmatch_t pmatch[], int eflags);
    229  */
    230 static int			/* 0 success, REG_NOMATCH failure */
    231 matcher(struct re_guts *g,
    232 	const char *string,
    233 	size_t nmatch,
    234 	regmatch_t pmatch[],
    235 	int eflags)
    236 {
    237 	const char *endp;
    238 	size_t i;
    239 	struct match mv;
    240 	struct match *m = &mv;
    241 	const char *dp = NULL;
    242 	const sopno gf = g->firststate+1;	/* +1 for OEND */
    243 	const sopno gl = g->laststate;
    244 	const char *start;
    245 	const char *stop;
    246 	/* Boyer-Moore algorithms variables */
    247 	const char *pp;
    248 	size_t cj, mj;
    249 	const char *mustfirst;
    250 	const char *mustlast;
    251 	size_t *matchjump;
    252 	size_t *charjump;
    253 	int error = 0;
    254 
    255 	_DIAGASSERT(g != NULL);
    256 	_DIAGASSERT(string != NULL);
    257 	/* pmatch checked below */
    258 
    259 	/* simplify the situation where possible */
    260 	if (g->cflags&REG_NOSUB)
    261 		nmatch = 0;
    262 	if (eflags&REG_STARTEND) {
    263 		_DIAGASSERT(pmatch != NULL);
    264 		start = string + (size_t)pmatch[0].rm_so;
    265 		stop = string + (size_t)pmatch[0].rm_eo;
    266 	} else {
    267 		start = string;
    268 		stop = start + strlen(start);
    269 	}
    270 	if (stop < start)
    271 		return(REG_INVARG);
    272 
    273 	/* prescreening; this does wonders for this rather slow code */
    274 	if (g->must != NULL) {
    275 		if (g->charjump != NULL && g->matchjump != NULL) {
    276 			mustfirst = g->must;
    277 			mustlast = g->must + g->mlen - 1;
    278 			charjump = g->charjump;
    279 			matchjump = g->matchjump;
    280 			pp = mustlast;
    281 			for (dp = start+g->mlen-1; dp < stop;) {
    282 				/* Fast skip non-matches */
    283 				while (dp < stop && charjump[(int)*dp])
    284 					dp += charjump[(int)*dp];
    285 
    286 				if (dp >= stop)
    287 					break;
    288 
    289 				/* Greedy matcher */
    290 				/* We depend on not being used for
    291 				 * for strings of length 1
    292 				 */
    293 				while (*--dp == *--pp && pp != mustfirst);
    294 
    295 				if (*dp == *pp)
    296 					break;
    297 
    298 				/* Jump to next possible match */
    299 				mj = matchjump[pp - mustfirst];
    300 				cj = charjump[(int)*dp];
    301 				dp += (cj < mj ? mj : cj);
    302 				pp = mustlast;
    303 			}
    304 			if (pp != mustfirst)
    305 				return(REG_NOMATCH);
    306 		} else {
    307 			for (dp = start; dp < stop; dp++)
    308 				if (*dp == g->must[0] &&
    309 				    (size_t)(stop - dp) >= g->mlen &&
    310 				    memcmp(dp, g->must, (size_t)g->mlen) == 0)
    311 					break;
    312 			if (dp == stop)		/* we didn't find g->must */
    313 				return(REG_NOMATCH);
    314 		}
    315 	}
    316 
    317 	/* match struct setup */
    318 	m->g = g;
    319 	m->eflags = eflags;
    320 	m->pmatch = NULL;
    321 	m->lastpos = NULL;
    322 	m->offp = string;
    323 	m->beginp = start;
    324 	m->endp = stop;
    325 	STATESETUP(m, 4);
    326 	SETUP(m->st);
    327 	SETUP(m->fresh);
    328 	SETUP(m->tmp);
    329 	SETUP(m->empty);
    330 	CLEAR(m->empty);
    331 	ZAPSTATE(&m->mbs);
    332 
    333 	/* Adjust start according to moffset, to speed things up */
    334 	if (dp != NULL && g->moffset > -1) {
    335 		const char *nstart;
    336 
    337 		nstart = stepback(start, dp, g->moffset);
    338 		if (nstart != NULL)
    339 			start = nstart;
    340 	}
    341 
    342 	SP("mloop", m->st, *start);
    343 
    344 	/* this loop does only one repetition except for backrefs */
    345 	for (;;) {
    346 		endp = walk(m, start, stop, gf, gl, true);
    347 		if (endp == NULL) {		/* a miss */
    348 			error = REG_NOMATCH;
    349 			goto done;
    350 		}
    351 		if (nmatch == 0 && !g->backrefs)
    352 			break;		/* no further info needed */
    353 
    354 		/* where? */
    355 		assert(m->coldp != NULL);
    356 		for (;;) {
    357 			NOTE("finding start");
    358 			endp = walk(m, m->coldp, stop, gf, gl, false);
    359 			if (endp != NULL)
    360 				break;
    361 			assert(m->coldp < m->endp);
    362 			if (m->coldp >= m->endp) {
    363 				/* never walk past the end of the string */
    364 				error = REG_NOMATCH;
    365 				goto done;
    366 			}
    367 			m->coldp += XMBRTOWC(NULL, m->coldp,
    368 			    (size_t)(m->endp - m->coldp), &m->mbs, 0);
    369 		}
    370 		if (nmatch == 1 && !g->backrefs)
    371 			break;		/* no further info needed */
    372 
    373 		/* oh my, he wants the subexpressions... */
    374 		if (m->pmatch == NULL)
    375 			m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) *
    376 							sizeof(regmatch_t));
    377 		if (m->pmatch == NULL) {
    378 			error = REG_ESPACE;
    379 			goto done;
    380 		}
    381 		for (i = 1; i <= m->g->nsub; i++)
    382 			m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
    383 		if (!g->backrefs && !(m->eflags&REG_BACKR)) {
    384 			NOTE("dissecting");
    385 			dp = dissect(m, m->coldp, endp, gf, gl);
    386 		} else {
    387 			if (g->nplus > 0 && m->lastpos == NULL)
    388 				m->lastpos = malloc((g->nplus+1) *
    389 						sizeof(const char *));
    390 			if (g->nplus > 0 && m->lastpos == NULL) {
    391 				error = REG_ESPACE;
    392 				goto done;
    393 			}
    394 			NOTE("backref dissect");
    395 			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
    396 		}
    397 		if (dp != NULL)
    398 			break;
    399 
    400 		/* uh-oh... we couldn't find a subexpression-level match */
    401 		assert(g->backrefs);	/* must be back references doing it */
    402 		assert(g->nplus == 0 || m->lastpos != NULL);
    403 		for (;;) {
    404 			if (dp != NULL || endp <= m->coldp)
    405 				break;		/* defeat */
    406 			NOTE("backoff");
    407 			endp = walk(m, m->coldp, endp-1, gf, gl, false);
    408 			if (endp == NULL)
    409 				break;		/* defeat */
    410 			/* try it on a shorter possibility */
    411 #ifndef NDEBUG
    412 			for (i = 1; i <= m->g->nsub; i++) {
    413 				assert(m->pmatch[i].rm_so == (regoff_t)-1);
    414 				assert(m->pmatch[i].rm_eo == (regoff_t)-1);
    415 			}
    416 #endif
    417 			NOTE("backoff dissect");
    418 			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
    419 		}
    420 		assert(dp == NULL || dp == endp);
    421 		if (dp != NULL)		/* found a shorter one */
    422 			break;
    423 
    424 		/* despite initial appearances, there is no match here */
    425 		NOTE("false alarm");
    426 		/* recycle starting later */
    427 		start = m->coldp + XMBRTOWC(NULL, m->coldp,
    428 		    (size_t)(stop - m->coldp), &m->mbs, 0);
    429 		assert(start <= stop);
    430 	}
    431 
    432 	/* fill in the details if requested */
    433 	if (nmatch > 0) {
    434 		_DIAGASSERT(pmatch != NULL);
    435 		pmatch[0].rm_so = m->coldp - m->offp;
    436 		pmatch[0].rm_eo = endp - m->offp;
    437 	}
    438 	if (nmatch > 1) {
    439 		assert(m->pmatch != NULL);
    440 		for (i = 1; i < nmatch; i++)
    441 			if (i <= m->g->nsub)
    442 				pmatch[i] = m->pmatch[i];
    443 			else {
    444 				pmatch[i].rm_so = (regoff_t)-1;
    445 				pmatch[i].rm_eo = (regoff_t)-1;
    446 			}
    447 	}
    448 
    449 done:
    450 	if (m->pmatch != NULL) {
    451 		free(m->pmatch);
    452 		m->pmatch = NULL;
    453 	}
    454 	if (m->lastpos != NULL) {
    455 		free(__UNCONST(m->lastpos));
    456 		m->lastpos = NULL;
    457 	}
    458 	STATETEARDOWN(m);
    459 	return error;
    460 }
    461 
    462 /*
    463  - dissect - figure out what matched what, no back references
    464  == static const char *dissect(struct match *m, const char *start, \
    465  ==	const char *stop, sopno startst, sopno stopst);
    466  */
    467 static const char *		/* == stop (success) always */
    468 dissect(
    469 	struct match *m,
    470 	const char *start,
    471 	const char *stop,
    472 	sopno startst,
    473 	sopno stopst)
    474 {
    475 	int i;
    476 	sopno ss;		/* start sop of current subRE */
    477 	sopno es;		/* end sop of current subRE */
    478 	const char *sp;		/* start of string matched by it */
    479 	const char *stp;	/* string matched by it cannot pass here */
    480 	const char *rest;	/* start of rest of string */
    481 	const char *tail;	/* string unmatched by rest of RE */
    482 	sopno ssub;		/* start sop of subsubRE */
    483 	sopno esub;		/* end sop of subsubRE */
    484 	const char *ssp;	/* start of string matched by subsubRE */
    485 	const char *sep;	/* end of string matched by subsubRE */
    486 	const char *oldssp;	/* previous ssp */
    487 	const char *dp __unused;
    488 
    489 	_DIAGASSERT(m != NULL);
    490 	_DIAGASSERT(start != NULL);
    491 	_DIAGASSERT(stop != NULL);
    492 
    493 	AT("diss", start, stop, startst, stopst);
    494 	sp = start;
    495 	for (ss = startst; ss < stopst; ss = es) {
    496 		/* identify end of subRE */
    497 		es = ss;
    498 		switch (OP(m->g->strip[es])) {
    499 		case OPLUS_:
    500 		case OQUEST_:
    501 			es += OPND(m->g->strip[es]);
    502 			break;
    503 		case OCH_:
    504 			while (OP(m->g->strip[es]) != O_CH)
    505 				es += OPND(m->g->strip[es]);
    506 			break;
    507 		}
    508 		es++;
    509 
    510 		/* figure out what it matched */
    511 		switch (OP(m->g->strip[ss])) {
    512 		case OEND:
    513 			assert(nope);
    514 			break;
    515 		case OCHAR:
    516 			sp += XMBRTOWC(NULL, sp, (size_t)(stop - start),
    517 			    &m->mbs, 0);
    518 			break;
    519 		case OBOL:
    520 		case OEOL:
    521 		case OBOW:
    522 		case OEOW:
    523 		case OBOS:
    524 		case OEOS:
    525 		case OWBND:
    526 		case ONWBND:
    527 			break;
    528 		case OANY:
    529 		case OANYOF:
    530 			sp += XMBRTOWC(NULL, sp, (size_t)(stop - start),
    531 			    &m->mbs, 0);
    532 			break;
    533 		case OBACK_:
    534 		case O_BACK:
    535 			assert(nope);
    536 			break;
    537 		/* cases where length of match is hard to find */
    538 		case OQUEST_:
    539 			stp = stop;
    540 			for (;;) {
    541 				/* how long could this one be? */
    542 				rest = walk(m, sp, stp, ss, es, false);
    543 				assert(rest != NULL);	/* it did match */
    544 				/* could the rest match the rest? */
    545 				tail = walk(m, rest, stop, es, stopst, false);
    546 				if (tail == stop)
    547 					break;		/* yes! */
    548 				/* no -- try a shorter match for this one */
    549 				stp = rest - 1;
    550 				assert(stp >= sp);	/* it did work */
    551 			}
    552 			ssub = ss + 1;
    553 			esub = es - 1;
    554 			/* did innards match? */
    555 			if (walk(m, sp, rest, ssub, esub, false) != NULL) {
    556 				dp = dissect(m, sp, rest, ssub, esub);
    557 				assert(dp == rest);
    558 			} else		/* no */
    559 				assert(sp == rest);
    560 			sp = rest;
    561 			break;
    562 		case OPLUS_:
    563 			stp = stop;
    564 			for (;;) {
    565 				/* how long could this one be? */
    566 				rest = walk(m, sp, stp, ss, es, false);
    567 				assert(rest != NULL);	/* it did match */
    568 				/* could the rest match the rest? */
    569 				tail = walk(m, rest, stop, es, stopst, false);
    570 				if (tail == stop)
    571 					break;		/* yes! */
    572 				/* no -- try a shorter match for this one */
    573 				stp = rest - 1;
    574 				assert(stp >= sp);	/* it did work */
    575 			}
    576 			ssub = ss + 1;
    577 			esub = es - 1;
    578 			ssp = sp;
    579 			oldssp = ssp;
    580 			for (;;) {	/* find last match of innards */
    581 				sep = walk(m, ssp, rest, ssub, esub, false);
    582 				if (sep == NULL || sep == ssp)
    583 					break;	/* failed or matched null */
    584 				oldssp = ssp;	/* on to next try */
    585 				ssp = sep;
    586 			}
    587 			if (sep == NULL) {
    588 				/* last successful match */
    589 				sep = ssp;
    590 				ssp = oldssp;
    591 			}
    592 			assert(sep == rest);	/* must exhaust substring */
    593 			assert(walk(m, ssp, sep, ssub, esub, false) == rest);
    594 			dp = dissect(m, ssp, sep, ssub, esub);
    595 			assert(dp == sep);
    596 			sp = rest;
    597 			break;
    598 		case OCH_:
    599 			stp = stop;
    600 			for (;;) {
    601 				/* how long could this one be? */
    602 				rest = walk(m, sp, stp, ss, es, false);
    603 				assert(rest != NULL);	/* it did match */
    604 				/* could the rest match the rest? */
    605 				tail = walk(m, rest, stop, es, stopst, false);
    606 				if (tail == stop)
    607 					break;		/* yes! */
    608 				/* no -- try a shorter match for this one */
    609 				stp = rest - 1;
    610 				assert(stp >= sp);	/* it did work */
    611 			}
    612 			ssub = ss + 1;
    613 			esub = ss + OPND(m->g->strip[ss]) - 1;
    614 			assert(OP(m->g->strip[esub]) == OOR1);
    615 			for (;;) {	/* find first matching branch */
    616 				if (walk(m, sp, rest, ssub, esub, false) == rest)
    617 					break;	/* it matched all of it */
    618 				/* that one missed, try next one */
    619 				assert(OP(m->g->strip[esub]) == OOR1);
    620 				esub++;
    621 				assert(OP(m->g->strip[esub]) == OOR2);
    622 				ssub = esub + 1;
    623 				esub += OPND(m->g->strip[esub]);
    624 				if (OP(m->g->strip[esub]) == OOR2)
    625 					esub--;
    626 				else
    627 					assert(OP(m->g->strip[esub]) == O_CH);
    628 			}
    629 			dp = dissect(m, sp, rest, ssub, esub);
    630 			assert(dp == rest);
    631 			sp = rest;
    632 			break;
    633 		case O_PLUS:
    634 		case O_QUEST:
    635 		case OOR1:
    636 		case OOR2:
    637 		case O_CH:
    638 			assert(nope);
    639 			break;
    640 		case OLPAREN:
    641 			i = OPND(m->g->strip[ss]);
    642 			assert(0 < i && i <= m->g->nsub);
    643 			m->pmatch[i].rm_so = sp - m->offp;
    644 			break;
    645 		case ORPAREN:
    646 			i = OPND(m->g->strip[ss]);
    647 			assert(0 < i && i <= m->g->nsub);
    648 			m->pmatch[i].rm_eo = sp - m->offp;
    649 			break;
    650 		default:		/* uh oh */
    651 			assert(nope);
    652 			break;
    653 		}
    654 	}
    655 
    656 	assert(sp == stop);
    657 	return(sp);
    658 }
    659 
    660 #define	ISBOW(m, sp)					\
    661     (sp < m->endp && ISWORD(*sp) &&			\
    662     ((sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||	\
    663     (sp > m->offp && !ISWORD(*(sp-1)))))
    664 #define	ISEOW(m, sp)					\
    665     (((sp == m->endp && !(m->eflags&REG_NOTEOL)) ||	\
    666     (sp < m->endp && *sp == '\n' &&			\
    667     (m->g->cflags&REG_NEWLINE)) ||			\
    668     (sp < m->endp && !ISWORD(*sp)) ) &&			\
    669     (sp > m->beginp && ISWORD(*(sp-1))))		\
    670 
    671 /*
    672  - backref - figure out what matched what, figuring in back references
    673  == static const char *backref(struct match *m, const char *start, \
    674  ==	const char *stop, sopno startst, sopno stopst, sopno lev);
    675  */
    676 static const char *		/* == stop (success) or NULL (failure) */
    677 backref(
    678 	struct match *m,
    679 	const char *start,
    680 	const char *stop,
    681 	sopno startst,
    682 	sopno stopst,
    683 	sopno lev,		/* PLUS nesting level */
    684 	int rec)
    685 {
    686 	int i;
    687 	sopno ss;		/* start sop of current subRE */
    688 	const char *sp;		/* start of string matched by it */
    689 	sopno ssub;		/* start sop of subsubRE */
    690 	sopno esub;		/* end sop of subsubRE */
    691 	const char *ssp;	/* start of string matched by subsubRE */
    692 	const char *dp;
    693 	size_t len;
    694 	int hard;
    695 	sop s;
    696 	regoff_t offsave;
    697 	cset *cs;
    698 	wint_t wc;
    699 
    700 	_DIAGASSERT(m != NULL);
    701 	_DIAGASSERT(start != NULL);
    702 	_DIAGASSERT(stop != NULL);
    703 
    704 	AT("back", start, stop, startst, stopst);
    705 	sp = start;
    706 
    707 	/* get as far as we can with easy stuff */
    708 	hard = 0;
    709 	for (ss = startst; !hard && ss < stopst; ss++)
    710 		switch (OP(s = m->g->strip[ss])) {
    711 		case OCHAR:
    712 			if (sp == stop)
    713 				return(NULL);
    714 			sp += XMBRTOWC(&wc, sp, (size_t)(stop - sp),
    715 			    &m->mbs, BADCHAR);
    716 			if (wc != (wint_t)OPND(s))
    717 				return(NULL);
    718 			break;
    719 		case OANY:
    720 			if (sp == stop)
    721 				return(NULL);
    722 			sp += XMBRTOWC(&wc, sp, (size_t)(stop - sp),
    723 			    &m->mbs, BADCHAR);
    724 			if (wc == BADCHAR)
    725 				return (NULL);
    726 			break;
    727 		case OANYOF:
    728 			if (sp == stop)
    729 				return (NULL);
    730 			cs = &m->g->sets[OPND(s)];
    731 			sp += XMBRTOWC(&wc, sp, (size_t)(stop - sp),
    732 			    &m->mbs, BADCHAR);
    733 			if (wc == BADCHAR || !CHIN(cs, wc))
    734 				return(NULL);
    735 			break;
    736 		case OBOS:
    737 			if (sp == m->beginp && (m->eflags & REG_NOTBOL) == 0)
    738 				{ /* yes */ }
    739 			else
    740 				return(NULL);
    741 			break;
    742 		case OEOS:
    743 			if (sp == m->endp && (m->eflags & REG_NOTEOL) == 0)
    744 				{ /* yes */ }
    745 			else
    746 				return(NULL);
    747 			break;
    748 		case OBOL:
    749 			if ((sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
    750 			    (sp > m->offp && sp < m->endp &&
    751 			    *(sp-1) == '\n' && (m->g->cflags&REG_NEWLINE)))
    752 				{ /* yes */ }
    753 			else
    754 				return(NULL);
    755 			break;
    756 		case OEOL:
    757 			if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
    758 					(sp < m->endp && *sp == '\n' &&
    759 						(m->g->cflags&REG_NEWLINE)) )
    760 				{ /* yes */ }
    761 			else
    762 				return(NULL);
    763 			break;
    764 		case OWBND:
    765 			if (ISBOW(m, sp) || ISEOW(m, sp))
    766 				{ /* yes */ }
    767 			else
    768 				return(NULL);
    769 			break;
    770 		case ONWBND:
    771 			if (((sp == m->beginp) && !ISWORD(*sp)) ||
    772 			    (sp == m->endp && !ISWORD(*(sp - 1))))
    773 				{ /* yes, beginning/end of subject */ }
    774 			else if (ISWORD(*(sp - 1)) == ISWORD(*sp))
    775 				{ /* yes, beginning/end of subject */ }
    776 			else
    777 				return(NULL);
    778 			break;
    779 		case OBOW:
    780 			if (ISBOW(m, sp))
    781 				{ /* yes */ }
    782 			else
    783 				return(NULL);
    784 			break;
    785 		case OEOW:
    786 			if (ISEOW(m, sp))
    787 				{ /* yes */ }
    788 			else
    789 				return(NULL);
    790 			break;
    791 		case O_QUEST:
    792 			break;
    793 		case OOR1:	/* matches null but needs to skip */
    794 			ss++;
    795 			s = m->g->strip[ss];
    796 			do {
    797 				assert(OP(s) == OOR2);
    798 				ss += OPND(s);
    799 			} while (OP(s = m->g->strip[ss]) != O_CH);
    800 			/* note that the ss++ gets us past the O_CH */
    801 			break;
    802 		default:	/* have to make a choice */
    803 			hard = 1;
    804 			break;
    805 		}
    806 	if (!hard) {		/* that was it! */
    807 		if (sp != stop)
    808 			return(NULL);
    809 		return(sp);
    810 	}
    811 	ss--;			/* adjust for the for's final increment */
    812 
    813 	/* the hard stuff */
    814 	AT("hard", sp, stop, ss, stopst);
    815 	s = m->g->strip[ss];
    816 	switch (OP(s)) {
    817 	case OBACK_:		/* the vilest depths */
    818 		i = OPND(s);
    819 		assert(0 < i && i <= m->g->nsub);
    820 		if (m->pmatch[i].rm_eo == -1)
    821 			return(NULL);
    822 		assert(m->pmatch[i].rm_so != -1);
    823 		len = (size_t)(m->pmatch[i].rm_eo - m->pmatch[i].rm_so);
    824 		if (len == 0 && rec++ > MAX_RECURSION)
    825 			return(NULL);
    826 		assert(stop - m->beginp >= len);
    827 		if (sp > stop - len)
    828 			return(NULL);	/* not enough left to match */
    829 		ssp = m->offp + (size_t)m->pmatch[i].rm_so;
    830 		if (memcmp(sp, ssp, len) != 0)
    831 			return(NULL);
    832 		while (m->g->strip[ss] != SOP(O_BACK, i))
    833 			ss++;
    834 		return(backref(m, sp+len, stop, ss+1, stopst, lev, rec));
    835 	case OQUEST_:		/* to null or not */
    836 		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
    837 		if (dp != NULL)
    838 			return(dp);	/* not */
    839 		return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev, rec));
    840 	case OPLUS_:
    841 		assert(m->lastpos != NULL);
    842 		assert(lev+1 <= m->g->nplus);
    843 		m->lastpos[lev+1] = sp;
    844 		return(backref(m, sp, stop, ss+1, stopst, lev+1, rec));
    845 	case O_PLUS:
    846 		if (sp == m->lastpos[lev])	/* last pass matched null */
    847 			return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
    848 		/* try another pass */
    849 		m->lastpos[lev] = sp;
    850 		dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev, rec);
    851 		if (dp == NULL)
    852 			return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
    853 		else
    854 			return(dp);
    855 	case OCH_:		/* find the right one, if any */
    856 		ssub = ss + 1;
    857 		esub = ss + OPND(s) - 1;
    858 		assert(OP(m->g->strip[esub]) == OOR1);
    859 		for (;;) {	/* find first matching branch */
    860 			dp = backref(m, sp, stop, ssub, esub, lev, rec);
    861 			if (dp != NULL)
    862 				return(dp);
    863 			/* that one missed, try next one */
    864 			if (OP(m->g->strip[esub]) == O_CH)
    865 				return(NULL);	/* there is none */
    866 			esub++;
    867 			assert(OP(m->g->strip[esub]) == OOR2);
    868 			ssub = esub + 1;
    869 			esub += OPND(m->g->strip[esub]);
    870 			if (OP(m->g->strip[esub]) == OOR2)
    871 				esub--;
    872 			else
    873 				assert(OP(m->g->strip[esub]) == O_CH);
    874 		}
    875 		/* NOTREACHED */
    876 		break;
    877 	case OLPAREN:		/* must undo assignment if rest fails */
    878 		i = OPND(s);
    879 		assert(0 < i && i <= m->g->nsub);
    880 		offsave = m->pmatch[i].rm_so;
    881 		m->pmatch[i].rm_so = sp - m->offp;
    882 		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
    883 		if (dp != NULL)
    884 			return(dp);
    885 		m->pmatch[i].rm_so = offsave;
    886 		return(NULL);
    887 	case ORPAREN:		/* must undo assignment if rest fails */
    888 		i = OPND(s);
    889 		assert(0 < i && i <= m->g->nsub);
    890 		offsave = m->pmatch[i].rm_eo;
    891 		m->pmatch[i].rm_eo = sp - m->offp;
    892 		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
    893 		if (dp != NULL)
    894 			return(dp);
    895 		m->pmatch[i].rm_eo = offsave;
    896 		return(NULL);
    897 	default:		/* uh oh */
    898 		assert(nope);
    899 		break;
    900 	}
    901 
    902 	/* "can't happen" */
    903 	assert(nope);
    904 	/* NOTREACHED */
    905 	return "shut up gcc";
    906 }
    907 
    908 /*
    909  - walk - step through the string either quickly or slowly
    910  == static const char *walk(struct match *m, const char *start, \
    911  ==	const char *stop, sopno startst, sopno stopst, bool fast);
    912  */
    913 static const char * /* where it ended, or NULL */
    914 walk(struct match *m, const char *start, const char *stop, sopno startst,
    915 	sopno stopst, bool fast)
    916 {
    917 	states st = m->st;
    918 	states fresh = m->fresh;
    919 	states empty = m->empty;
    920 	states tmp = m->tmp;
    921 	const char *p = start;
    922 	wint_t c;
    923 	wint_t lastc;		/* previous c */
    924 	wint_t flagch;
    925 	int sflags;
    926 	const char *matchp;	/* last p at which a match ended */
    927 	size_t i, clen;
    928 
    929 	_DIAGASSERT(m != NULL);
    930 	_DIAGASSERT(start != NULL);
    931 	_DIAGASSERT(stop != NULL);
    932 
    933 	sflags = 0;
    934 	AT("walk", start, stop, startst, stopst);
    935 	CLEAR(st);
    936 	SET1(st, startst);
    937 	SP("sstart", st, *p);
    938 	st = step(m->g, startst, stopst, st, NOTHING, st, sflags);
    939 	if (fast)
    940 		ASSIGN(fresh, st);
    941 	matchp = NULL;
    942 	if (start == m->offp || (start == m->beginp && !(m->eflags&REG_NOTBOL)))
    943 		c = OUT;
    944 	else
    945 		c = prevchar(m->offp, start);
    946 	for (;;) {
    947 		/* next character */
    948 		lastc = c;
    949 		sflags = 0;
    950 		if (p == m->endp) {
    951 			c = OUT;
    952 			clen = 0;
    953 		} else
    954 			clen = XMBRTOWC(&c, p, (size_t)(m->endp - p),
    955 			    &m->mbs, BADCHAR);
    956 
    957 		if (fast && EQ(st, fresh))
    958 			matchp = p;
    959 
    960 		/* is there an EOL and/or BOL between lastc and c? */
    961 		flagch = '\0';
    962 		i = 0;
    963 		if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
    964 				(lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
    965 			flagch = BOL;
    966 			i = m->g->nbol;
    967 		}
    968 		if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
    969 				(c == OUT && !(m->eflags&REG_NOTEOL)) ) {
    970 			flagch = (flagch == BOL) ? BOLEOL : EOL;
    971 			i += m->g->neol;
    972 		}
    973 		if (lastc == OUT && (m->eflags & REG_NOTBOL) == 0) {
    974 			sflags |= SBOS;
    975 			/* Step one more for BOS. */
    976 			i++;
    977 		}
    978 		if (c == OUT && (m->eflags & REG_NOTEOL) == 0) {
    979 			sflags |= SEOS;
    980 			/* Step one more for EOS. */
    981 			i++;
    982 		}
    983 		if (i != 0) {
    984 			for (; i > 0; i--)
    985 				st = step(m->g, startst, stopst, st, flagch, st,
    986 				    sflags);
    987 			SP("sboleol", st, c);
    988 		}
    989 
    990 		/* how about a word boundary? */
    991 		if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
    992 					(c != OUT && ISWORD(c)) ) {
    993 			flagch = BOW;
    994 		}
    995 		if ( (lastc != OUT && ISWORD(lastc)) &&
    996 				(flagch == EOL || (c != OUT && !ISWORD(c))) ) {
    997 			flagch = EOW;
    998 		}
    999 		if (flagch == BOW || flagch == EOW) {
   1000 			st = step(m->g, startst, stopst, st, flagch, st, sflags);
   1001 			SP("sboweow", st, c);
   1002 		}
   1003 		if (lastc != OUT && c != OUT &&
   1004 		    ISWORD(lastc) == ISWORD(c)) {
   1005 			flagch = NWBND;
   1006 		} else if ((lastc == OUT && !ISWORD(c)) ||
   1007 		    (c == OUT && !ISWORD(lastc))) {
   1008 			flagch = NWBND;
   1009 		}
   1010 		if (flagch == NWBND) {
   1011 			st = step(m->g, startst, stopst, st, flagch, st, sflags);
   1012 			SP("snwbnd", st, c);
   1013 		}
   1014 
   1015 		/* are we done? */
   1016 		if (ISSET(st, stopst)) {
   1017 			if (fast)
   1018 				break;
   1019 			else
   1020 				matchp = p;
   1021 		}
   1022 		if (EQ(st, empty) || p == stop || clen > (size_t)(stop - p))
   1023 			break;		/* NOTE BREAK OUT */
   1024 
   1025 		/* no, we must deal with this character */
   1026 		ASSIGN(tmp, st);
   1027 		if (fast)
   1028 			ASSIGN(st, fresh);
   1029 		else
   1030 			ASSIGN(st, empty);
   1031 		assert(c != OUT);
   1032 		st = step(m->g, startst, stopst, tmp, c, st, sflags);
   1033 		SP("saft", st, c);
   1034 		assert(EQ(step(m->g, startst, stopst, st, NOTHING, st, sflags),
   1035 		    st));
   1036 		p += clen;
   1037 	}
   1038 
   1039 	if (fast) {
   1040 		assert(matchp != NULL);
   1041 		m->coldp = matchp;
   1042 		if (ISSET(st, stopst))
   1043 			return (p + XMBRTOWC(NULL, p, (size_t)(stop - p),
   1044 			    &m->mbs, 0));
   1045 		else
   1046 			return (NULL);
   1047 	} else
   1048 		return (matchp);
   1049 }
   1050 
   1051 /*
   1052  - step - map set of states reachable before char to set reachable after
   1053  == static states step(struct re_guts *g, sopno start, sopno stop, \
   1054  ==	states bef, int ch, states aft);
   1055  == #define	BOL	(OUT-1)
   1056  == #define	EOL	(BOL-1)
   1057  == #define	BOLEOL	(BOL-2)
   1058  == #define	NOTHING	(BOL-3)
   1059  == #define	BOW	(BOL-4)
   1060  == #define	EOW	(BOL-5)
   1061  == #define	BADCHAR	(BOL-6)
   1062  == #define	NONCHAR(c)	((c) <= OUT)
   1063  */
   1064 static states
   1065 step(struct re_guts *g,
   1066 	sopno start,		/* start state within strip */
   1067 	sopno stop,		/* state after stop state within strip */
   1068 	states bef,		/* states reachable before */
   1069 	wint_t ch,		/* character or NONCHAR code */
   1070 	states aft,		/* states already known reachable after */
   1071 	int sflags)		/* state flags */
   1072 {
   1073 	cset *cs;
   1074 	sop s;
   1075 	sopno pc;
   1076 	onestate here;		/* note, macros know this name */
   1077 	sopno look;
   1078 	int i;
   1079 
   1080 	_DIAGASSERT(g != NULL);
   1081 
   1082 	for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
   1083 		s = g->strip[pc];
   1084 		switch (OP(s)) {
   1085 		case OEND:
   1086 			assert(pc == stop-1);
   1087 			break;
   1088 		case OCHAR:
   1089 			/* only characters can match */
   1090 			assert(!NONCHAR(ch) || ch != OPND(s));
   1091 			if (ch == (wint_t)OPND(s))
   1092 				FWD(aft, bef, 1);
   1093 			break;
   1094 		case OBOS:
   1095 			if ((ch == BOL || ch == BOLEOL) && (sflags & SBOS) != 0)
   1096 				FWD(aft, bef, 1);
   1097 			break;
   1098 		case OEOS:
   1099 			if ((ch == EOL || ch == BOLEOL) && (sflags & SEOS) != 0)
   1100 				FWD(aft, bef, 1);
   1101 			break;
   1102 		case OBOL:
   1103 			if (ch == BOL || ch == BOLEOL)
   1104 				FWD(aft, bef, 1);
   1105 			break;
   1106 		case OEOL:
   1107 			if (ch == EOL || ch == BOLEOL)
   1108 				FWD(aft, bef, 1);
   1109 			break;
   1110 		case OBOW:
   1111 			if (ch == BOW)
   1112 				FWD(aft, bef, 1);
   1113 			break;
   1114 		case OEOW:
   1115 			if (ch == EOW)
   1116 				FWD(aft, bef, 1);
   1117 			break;
   1118 		case OWBND:
   1119 			if (ch == BOW || ch == EOW)
   1120 				FWD(aft, bef, 1);
   1121 			break;
   1122 		case ONWBND:
   1123 			if (ch == NWBND)
   1124 				FWD(aft, aft, 1);
   1125 			break;
   1126 		case OANY:
   1127 			if (!NONCHAR(ch))
   1128 				FWD(aft, bef, 1);
   1129 			break;
   1130 		case OANYOF:
   1131 			cs = &g->sets[OPND(s)];
   1132 			if (!NONCHAR(ch) && CHIN(cs, ch))
   1133 				FWD(aft, bef, 1);
   1134 			break;
   1135 		case OBACK_:		/* ignored here */
   1136 		case O_BACK:
   1137 			FWD(aft, aft, 1);
   1138 			break;
   1139 		case OPLUS_:		/* forward, this is just an empty */
   1140 			FWD(aft, aft, 1);
   1141 			break;
   1142 		case O_PLUS:		/* both forward and back */
   1143 			FWD(aft, aft, 1);
   1144 			i = ISSETBACK(aft, OPND(s));
   1145 			BACK(aft, aft, OPND(s));
   1146 			if (!i && ISSETBACK(aft, OPND(s))) {
   1147 				/* oho, must reconsider loop body */
   1148 				pc -= OPND(s) + 1;
   1149 				INIT(here, pc);
   1150 			}
   1151 			break;
   1152 		case OQUEST_:		/* two branches, both forward */
   1153 			FWD(aft, aft, 1);
   1154 			FWD(aft, aft, OPND(s));
   1155 			break;
   1156 		case O_QUEST:		/* just an empty */
   1157 			FWD(aft, aft, 1);
   1158 			break;
   1159 		case OLPAREN:		/* not significant here */
   1160 		case ORPAREN:
   1161 			FWD(aft, aft, 1);
   1162 			break;
   1163 		case OCH_:		/* mark the first two branches */
   1164 			FWD(aft, aft, 1);
   1165 			assert(OP(g->strip[pc+OPND(s)]) == OOR2);
   1166 			FWD(aft, aft, OPND(s));
   1167 			break;
   1168 		case OOR1:		/* done a branch, find the O_CH */
   1169 			if (ISSTATEIN(aft, here)) {
   1170 				for (look = 1;
   1171 				    OP(s = g->strip[pc+look]) != O_CH;
   1172 				    look += OPND(s))
   1173 					assert(OP(s) == OOR2);
   1174 				FWD(aft, aft, look + 1);
   1175 			}
   1176 			break;
   1177 		case OOR2:		/* propagate OCH_'s marking */
   1178 			FWD(aft, aft, 1);
   1179 			if (OP(g->strip[pc+OPND(s)]) != O_CH) {
   1180 				assert(OP(g->strip[pc+OPND(s)]) == OOR2);
   1181 				FWD(aft, aft, OPND(s));
   1182 			}
   1183 			break;
   1184 		case O_CH:		/* just empty */
   1185 			FWD(aft, aft, 1);
   1186 			break;
   1187 		default:		/* ooooops... */
   1188 			assert(nope);
   1189 			break;
   1190 		}
   1191 	}
   1192 
   1193 	return(aft);
   1194 }
   1195 
   1196 #ifdef REDEBUG
   1197 /*
   1198  - print - print a set of states
   1199  == #ifdef REDEBUG
   1200  == static void print(struct match *m, const char *caption, states st, \
   1201  ==	int ch, FILE *d);
   1202  == #endif
   1203  */
   1204 static void
   1205 print(struct match *m,
   1206 	const char *caption,
   1207 	states st,
   1208 	int ch,
   1209 	FILE *d)
   1210 {
   1211 	struct re_guts *g = m->g;
   1212 	sopno i;
   1213 	int first = 1;
   1214 
   1215 	_DIAGASSERT(m != NULL);
   1216 	_DIAGASSERT(caption != NULL);
   1217 
   1218 	if (!(m->eflags&REG_TRACE))
   1219 		return;
   1220 
   1221 	_DIAGASSERT(d != NULL);
   1222 
   1223 	fprintf(d, "%s", caption);
   1224 	if (ch != '\0')
   1225 		fprintf(d, " %s", pchar(ch));
   1226 	for (i = 0; i < g->nstates; i++)
   1227 		if (ISSET(st, i)) {
   1228 			fprintf(d, "%s%lu", (first) ? "\t" : ", ", i);
   1229 			first = 0;
   1230 		}
   1231 	fprintf(d, "\n");
   1232 }
   1233 
   1234 /*
   1235  - at - print current situation
   1236  == #ifdef REDEBUG
   1237  == static void at(struct match *m, const char *title, const char *start, \
   1238  ==			 const char *stop, sopno startst, sopno stopst);
   1239  == #endif
   1240  */
   1241 static void
   1242 at(	struct match *m,
   1243 	const char *title,
   1244 	const char *start,
   1245 	const char *stop,
   1246 	sopno startst,
   1247 	sopno stopst)
   1248 {
   1249 
   1250 	_DIAGASSERT(m != NULL);
   1251 	_DIAGASSERT(title != NULL);
   1252 	_DIAGASSERT(start != NULL);
   1253 	_DIAGASSERT(stop != NULL);
   1254 
   1255 	if (!(m->eflags&REG_TRACE))
   1256 		return;
   1257 
   1258 	printf("%s %s-", title, pchar(*start));
   1259 	printf("%s ", pchar(*stop));
   1260 	printf("%ld-%ld\n", (long)startst, (long)stopst);
   1261 }
   1262 
   1263 #ifndef PCHARDONE
   1264 #define	PCHARDONE	/* never again */
   1265 /*
   1266  - pchar - make a character printable
   1267  == #ifdef REDEBUG
   1268  == static const char *pchar(int ch);
   1269  == #endif
   1270  *
   1271  * Is this identical to regchar() over in debug.c?  Well, yes.  But a
   1272  * duplicate here avoids having a debugging-capable regexec.o tied to
   1273  * a matching debug.o, and this is convenient.  It all disappears in
   1274  * the non-debug compilation anyway, so it doesn't matter much.
   1275  */
   1276 static const char *		/* -> representation */
   1277 pchar(int ch)
   1278 {
   1279 	static char pbuf[10];
   1280 
   1281 	if (isprint((uch)ch) || ch == ' ')
   1282 		snprintf(pbuf, sizeof(pbuf), "%c", ch);
   1283 	else
   1284 		snprintf(pbuf, sizeof(pbuf), "\\%o", ch);
   1285 	return(pbuf);
   1286 }
   1287 #endif
   1288 #endif
   1289 
   1290 #undef	stepback
   1291 #undef	prevchar
   1292 #undef	matcher
   1293 #undef	walk
   1294 #undef	dissect
   1295 #undef	backref
   1296 #undef	step
   1297 #undef	print
   1298 #undef	at
   1299 #undef	match
   1300