1*e0b8e63eSJohn Marino /* $NetBSD: engine.c,v 1.7 2011/11/19 17:45:11 tnozaki Exp $ */
2*e0b8e63eSJohn Marino
3*e0b8e63eSJohn Marino /*-
4*e0b8e63eSJohn Marino * Copyright (c) 1992, 1993, 1994 Henry Spencer.
5*e0b8e63eSJohn Marino * Copyright (c) 1992, 1993, 1994
6*e0b8e63eSJohn Marino * The Regents of the University of California. All rights reserved.
7*e0b8e63eSJohn Marino *
8*e0b8e63eSJohn Marino * This code is derived from software contributed to Berkeley by
9*e0b8e63eSJohn Marino * Henry Spencer of the University of Toronto.
10*e0b8e63eSJohn Marino *
11*e0b8e63eSJohn Marino * Redistribution and use in source and binary forms, with or without
12*e0b8e63eSJohn Marino * modification, are permitted provided that the following conditions
13*e0b8e63eSJohn Marino * are met:
14*e0b8e63eSJohn Marino * 1. Redistributions of source code must retain the above copyright
15*e0b8e63eSJohn Marino * notice, this list of conditions and the following disclaimer.
16*e0b8e63eSJohn Marino * 2. Redistributions in binary form must reproduce the above copyright
17*e0b8e63eSJohn Marino * notice, this list of conditions and the following disclaimer in the
18*e0b8e63eSJohn Marino * documentation and/or other materials provided with the distribution.
19*e0b8e63eSJohn Marino * 3. Neither the name of the University nor the names of its contributors
20*e0b8e63eSJohn Marino * may be used to endorse or promote products derived from this software
21*e0b8e63eSJohn Marino * without specific prior written permission.
22*e0b8e63eSJohn Marino *
23*e0b8e63eSJohn Marino * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24*e0b8e63eSJohn Marino * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25*e0b8e63eSJohn Marino * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26*e0b8e63eSJohn Marino * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27*e0b8e63eSJohn Marino * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28*e0b8e63eSJohn Marino * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29*e0b8e63eSJohn Marino * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30*e0b8e63eSJohn Marino * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31*e0b8e63eSJohn Marino * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32*e0b8e63eSJohn Marino * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33*e0b8e63eSJohn Marino * SUCH DAMAGE.
34*e0b8e63eSJohn Marino *
35*e0b8e63eSJohn Marino * @(#)engine.c 8.4 (Berkeley) 3/19/94
36*e0b8e63eSJohn Marino */
37*e0b8e63eSJohn Marino
38*e0b8e63eSJohn Marino /*
39*e0b8e63eSJohn Marino * The matching engine and friends. This file is #included by regexec.c
40*e0b8e63eSJohn Marino * after suitable #defines of a variety of macros used herein, so that
41*e0b8e63eSJohn Marino * different state representations can be used without duplicating masses
42*e0b8e63eSJohn Marino * of code.
43*e0b8e63eSJohn Marino */
44*e0b8e63eSJohn Marino
45*e0b8e63eSJohn Marino #ifdef SNAMES
46*e0b8e63eSJohn Marino #define matcher smatcher
47*e0b8e63eSJohn Marino #define fast sfast
48*e0b8e63eSJohn Marino #define slow sslow
49*e0b8e63eSJohn Marino #define dissect sdissect
50*e0b8e63eSJohn Marino #define backref sbackref
51*e0b8e63eSJohn Marino #define step sstep
52*e0b8e63eSJohn Marino #define print sprint
53*e0b8e63eSJohn Marino #define at sat
54*e0b8e63eSJohn Marino #define match smat
55*e0b8e63eSJohn Marino #endif
56*e0b8e63eSJohn Marino #ifdef LNAMES
57*e0b8e63eSJohn Marino #define matcher lmatcher
58*e0b8e63eSJohn Marino #define fast lfast
59*e0b8e63eSJohn Marino #define slow lslow
60*e0b8e63eSJohn Marino #define dissect ldissect
61*e0b8e63eSJohn Marino #define backref lbackref
62*e0b8e63eSJohn Marino #define step lstep
63*e0b8e63eSJohn Marino #define print lprint
64*e0b8e63eSJohn Marino #define at lat
65*e0b8e63eSJohn Marino #define match lmat
66*e0b8e63eSJohn Marino #endif
67*e0b8e63eSJohn Marino
68*e0b8e63eSJohn Marino /* another structure passed up and down to avoid zillions of parameters */
69*e0b8e63eSJohn Marino struct match {
70*e0b8e63eSJohn Marino struct re_guts *g;
71*e0b8e63eSJohn Marino int eflags;
72*e0b8e63eSJohn Marino regmatch_t *pmatch; /* [nsub+1] (0 element unused) */
73*e0b8e63eSJohn Marino const RCHAR_T *offp; /* offsets work from here */
74*e0b8e63eSJohn Marino const RCHAR_T *beginp; /* start of string -- virtual NUL precedes */
75*e0b8e63eSJohn Marino const RCHAR_T *endp; /* end of string -- virtual NUL here */
76*e0b8e63eSJohn Marino const RCHAR_T *coldp; /* can be no match starting before here */
77*e0b8e63eSJohn Marino const RCHAR_T **lastpos; /* [nplus+1] */
78*e0b8e63eSJohn Marino STATEVARS;
79*e0b8e63eSJohn Marino states st; /* current states */
80*e0b8e63eSJohn Marino states fresh; /* states for a fresh start */
81*e0b8e63eSJohn Marino states tmp; /* temporary */
82*e0b8e63eSJohn Marino states empty; /* empty set of states */
83*e0b8e63eSJohn Marino };
84*e0b8e63eSJohn Marino
85*e0b8e63eSJohn Marino /* ========= begin header generated by ./mkh ========= */
86*e0b8e63eSJohn Marino #ifdef __cplusplus
87*e0b8e63eSJohn Marino extern "C" {
88*e0b8e63eSJohn Marino #endif
89*e0b8e63eSJohn Marino
90*e0b8e63eSJohn Marino /* === engine.c === */
91*e0b8e63eSJohn Marino static int matcher(struct re_guts *g, const RCHAR_T *string, size_t nmatch, regmatch_t pmatch[], int eflags);
92*e0b8e63eSJohn Marino static const RCHAR_T *dissect(struct match *m, const RCHAR_T *start, const RCHAR_T *stop, sopno startst, sopno stopst);
93*e0b8e63eSJohn Marino static const RCHAR_T *backref(struct match *m, const RCHAR_T *start, const RCHAR_T *stop, sopno startst, sopno stopst, sopno lev);
94*e0b8e63eSJohn Marino static const RCHAR_T *fast(struct match *m, const RCHAR_T *start, const RCHAR_T *stop, sopno startst, sopno stopst);
95*e0b8e63eSJohn Marino static const RCHAR_T *slow(struct match *m, const RCHAR_T *start, const RCHAR_T *stop, sopno startst, sopno stopst);
96*e0b8e63eSJohn Marino static states step(struct re_guts *g, sopno start, sopno stop, states bef, int flag, RCHAR_T ch, states aft);
97*e0b8e63eSJohn Marino #define BOL (1)
98*e0b8e63eSJohn Marino #define EOL (BOL+1)
99*e0b8e63eSJohn Marino #define BOLEOL (BOL+2)
100*e0b8e63eSJohn Marino #define NOTHING (BOL+3)
101*e0b8e63eSJohn Marino #define BOW (BOL+4)
102*e0b8e63eSJohn Marino #define EOW (BOL+5)
103*e0b8e63eSJohn Marino #ifdef REDEBUG
104*e0b8e63eSJohn Marino static void print(struct match *m, char *caption, states st, int ch, FILE *d);
105*e0b8e63eSJohn Marino #endif
106*e0b8e63eSJohn Marino #ifdef REDEBUG
107*e0b8e63eSJohn Marino static void at(struct match *m, char *title, char *start, char *stop, sopno startst, sopno stopst);
108*e0b8e63eSJohn Marino #endif
109*e0b8e63eSJohn Marino #ifdef REDEBUG
110*e0b8e63eSJohn Marino static char *pchar(int ch);
111*e0b8e63eSJohn Marino #endif
112*e0b8e63eSJohn Marino
113*e0b8e63eSJohn Marino #ifdef __cplusplus
114*e0b8e63eSJohn Marino }
115*e0b8e63eSJohn Marino #endif
116*e0b8e63eSJohn Marino /* ========= end header generated by ./mkh ========= */
117*e0b8e63eSJohn Marino
118*e0b8e63eSJohn Marino #ifdef REDEBUG
119*e0b8e63eSJohn Marino #define SP(t, s, c) print(m, t, s, c, stdout)
120*e0b8e63eSJohn Marino #define AT(t, p1, p2, s1, s2) at(m, t, p1, p2, s1, s2)
121*e0b8e63eSJohn Marino #define NOTE(str) { if (m->eflags®_TRACE) printf("=%s\n", (str)); }
122*e0b8e63eSJohn Marino #else
123*e0b8e63eSJohn Marino #define SP(t, s, c) /* nothing */
124*e0b8e63eSJohn Marino #define AT(t, p1, p2, s1, s2) /* nothing */
125*e0b8e63eSJohn Marino #define NOTE(s) /* nothing */
126*e0b8e63eSJohn Marino #endif
127*e0b8e63eSJohn Marino
128*e0b8e63eSJohn Marino /*
129*e0b8e63eSJohn Marino - matcher - the actual matching engine
130*e0b8e63eSJohn Marino */
131*e0b8e63eSJohn Marino static int /* 0 success, REG_NOMATCH failure */
matcher(struct re_guts * g,const RCHAR_T * string,size_t nmatch,regmatch_t pmatch[],int eflags)132*e0b8e63eSJohn Marino matcher(struct re_guts *g, const RCHAR_T *string, size_t nmatch,
133*e0b8e63eSJohn Marino regmatch_t pmatch[], int eflags)
134*e0b8e63eSJohn Marino {
135*e0b8e63eSJohn Marino const RCHAR_T *endp;
136*e0b8e63eSJohn Marino size_t i;
137*e0b8e63eSJohn Marino struct match mv;
138*e0b8e63eSJohn Marino struct match *m = &mv;
139*e0b8e63eSJohn Marino const RCHAR_T *dp;
140*e0b8e63eSJohn Marino const sopno gf = g->firststate+1; /* +1 for OEND */
141*e0b8e63eSJohn Marino const sopno gl = g->laststate;
142*e0b8e63eSJohn Marino const RCHAR_T *start;
143*e0b8e63eSJohn Marino const RCHAR_T *stop;
144*e0b8e63eSJohn Marino
145*e0b8e63eSJohn Marino /* simplify the situation where possible */
146*e0b8e63eSJohn Marino if (g->cflags®_NOSUB)
147*e0b8e63eSJohn Marino nmatch = 0;
148*e0b8e63eSJohn Marino if (eflags®_STARTEND) {
149*e0b8e63eSJohn Marino start = string + pmatch[0].rm_so;
150*e0b8e63eSJohn Marino stop = string + pmatch[0].rm_eo;
151*e0b8e63eSJohn Marino } else {
152*e0b8e63eSJohn Marino start = string;
153*e0b8e63eSJohn Marino stop = start + STRLEN(start);
154*e0b8e63eSJohn Marino }
155*e0b8e63eSJohn Marino if (stop < start)
156*e0b8e63eSJohn Marino return(REG_INVARG);
157*e0b8e63eSJohn Marino
158*e0b8e63eSJohn Marino /* prescreening; this does wonders for this rather slow code */
159*e0b8e63eSJohn Marino if (g->must != NULL) {
160*e0b8e63eSJohn Marino for (dp = start; dp < stop; dp++)
161*e0b8e63eSJohn Marino if (*dp == g->must[0] && (size_t)(stop - dp) >= g->mlen &&
162*e0b8e63eSJohn Marino MEMCMP(dp, g->must, g->mlen) == 0)
163*e0b8e63eSJohn Marino break;
164*e0b8e63eSJohn Marino if (dp == stop) /* we didn't find g->must */
165*e0b8e63eSJohn Marino return(REG_NOMATCH);
166*e0b8e63eSJohn Marino }
167*e0b8e63eSJohn Marino
168*e0b8e63eSJohn Marino /* match struct setup */
169*e0b8e63eSJohn Marino m->g = g;
170*e0b8e63eSJohn Marino m->eflags = eflags;
171*e0b8e63eSJohn Marino m->pmatch = NULL;
172*e0b8e63eSJohn Marino m->lastpos = NULL;
173*e0b8e63eSJohn Marino m->offp = string;
174*e0b8e63eSJohn Marino m->beginp = start;
175*e0b8e63eSJohn Marino m->endp = stop;
176*e0b8e63eSJohn Marino STATESETUP(m, 4);
177*e0b8e63eSJohn Marino SETUP(m->st);
178*e0b8e63eSJohn Marino SETUP(m->fresh);
179*e0b8e63eSJohn Marino SETUP(m->tmp);
180*e0b8e63eSJohn Marino SETUP(m->empty);
181*e0b8e63eSJohn Marino CLEAR(m->empty);
182*e0b8e63eSJohn Marino
183*e0b8e63eSJohn Marino /* this loop does only one repetition except for backrefs */
184*e0b8e63eSJohn Marino for (;;) {
185*e0b8e63eSJohn Marino endp = fast(m, start, stop, gf, gl);
186*e0b8e63eSJohn Marino if (endp == NULL) { /* a miss */
187*e0b8e63eSJohn Marino STATETEARDOWN(m);
188*e0b8e63eSJohn Marino return(REG_NOMATCH);
189*e0b8e63eSJohn Marino }
190*e0b8e63eSJohn Marino if (nmatch == 0 && !g->backrefs)
191*e0b8e63eSJohn Marino break; /* no further info needed */
192*e0b8e63eSJohn Marino
193*e0b8e63eSJohn Marino /* where? */
194*e0b8e63eSJohn Marino assert(m->coldp != NULL);
195*e0b8e63eSJohn Marino for (;;) {
196*e0b8e63eSJohn Marino NOTE("finding start");
197*e0b8e63eSJohn Marino endp = slow(m, m->coldp, stop, gf, gl);
198*e0b8e63eSJohn Marino if (endp != NULL)
199*e0b8e63eSJohn Marino break;
200*e0b8e63eSJohn Marino assert(m->coldp < m->endp);
201*e0b8e63eSJohn Marino m->coldp++;
202*e0b8e63eSJohn Marino }
203*e0b8e63eSJohn Marino if (nmatch == 1 && !g->backrefs)
204*e0b8e63eSJohn Marino break; /* no further info needed */
205*e0b8e63eSJohn Marino
206*e0b8e63eSJohn Marino /* oh my, he wants the subexpressions... */
207*e0b8e63eSJohn Marino if (m->pmatch == NULL)
208*e0b8e63eSJohn Marino m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) *
209*e0b8e63eSJohn Marino sizeof(regmatch_t));
210*e0b8e63eSJohn Marino if (m->pmatch == NULL) {
211*e0b8e63eSJohn Marino STATETEARDOWN(m);
212*e0b8e63eSJohn Marino return(REG_ESPACE);
213*e0b8e63eSJohn Marino }
214*e0b8e63eSJohn Marino for (i = 1; i <= m->g->nsub; i++)
215*e0b8e63eSJohn Marino m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
216*e0b8e63eSJohn Marino if (!g->backrefs && !(m->eflags®_BACKR)) {
217*e0b8e63eSJohn Marino NOTE("dissecting");
218*e0b8e63eSJohn Marino dp = dissect(m, m->coldp, endp, gf, gl);
219*e0b8e63eSJohn Marino } else {
220*e0b8e63eSJohn Marino if (g->nplus > 0 && m->lastpos == NULL)
221*e0b8e63eSJohn Marino m->lastpos = (const RCHAR_T **)malloc((g->nplus+1) *
222*e0b8e63eSJohn Marino sizeof(const RCHAR_T *));
223*e0b8e63eSJohn Marino if (g->nplus > 0 && m->lastpos == NULL) {
224*e0b8e63eSJohn Marino free(m->pmatch);
225*e0b8e63eSJohn Marino STATETEARDOWN(m);
226*e0b8e63eSJohn Marino return(REG_ESPACE);
227*e0b8e63eSJohn Marino }
228*e0b8e63eSJohn Marino NOTE("backref dissect");
229*e0b8e63eSJohn Marino dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
230*e0b8e63eSJohn Marino }
231*e0b8e63eSJohn Marino if (dp != NULL)
232*e0b8e63eSJohn Marino break;
233*e0b8e63eSJohn Marino
234*e0b8e63eSJohn Marino /* uh-oh... we couldn't find a subexpression-level match */
235*e0b8e63eSJohn Marino assert(g->backrefs); /* must be back references doing it */
236*e0b8e63eSJohn Marino assert(g->nplus == 0 || m->lastpos != NULL);
237*e0b8e63eSJohn Marino for (;;) {
238*e0b8e63eSJohn Marino if (dp != NULL || endp <= m->coldp)
239*e0b8e63eSJohn Marino break; /* defeat */
240*e0b8e63eSJohn Marino NOTE("backoff");
241*e0b8e63eSJohn Marino endp = slow(m, m->coldp, endp-1, gf, gl);
242*e0b8e63eSJohn Marino if (endp == NULL)
243*e0b8e63eSJohn Marino break; /* defeat */
244*e0b8e63eSJohn Marino /* try it on a shorter possibility */
245*e0b8e63eSJohn Marino #ifndef NDEBUG
246*e0b8e63eSJohn Marino for (i = 1; i <= m->g->nsub; i++) {
247*e0b8e63eSJohn Marino assert(m->pmatch[i].rm_so == -1);
248*e0b8e63eSJohn Marino assert(m->pmatch[i].rm_eo == -1);
249*e0b8e63eSJohn Marino }
250*e0b8e63eSJohn Marino #endif
251*e0b8e63eSJohn Marino NOTE("backoff dissect");
252*e0b8e63eSJohn Marino dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
253*e0b8e63eSJohn Marino }
254*e0b8e63eSJohn Marino assert(dp == NULL || dp == endp);
255*e0b8e63eSJohn Marino if (dp != NULL) /* found a shorter one */
256*e0b8e63eSJohn Marino break;
257*e0b8e63eSJohn Marino
258*e0b8e63eSJohn Marino /* despite initial appearances, there is no match here */
259*e0b8e63eSJohn Marino NOTE("false alarm");
260*e0b8e63eSJohn Marino start = m->coldp + 1; /* recycle starting later */
261*e0b8e63eSJohn Marino assert(start <= stop);
262*e0b8e63eSJohn Marino }
263*e0b8e63eSJohn Marino
264*e0b8e63eSJohn Marino /* fill in the details if requested */
265*e0b8e63eSJohn Marino if (nmatch > 0) {
266*e0b8e63eSJohn Marino pmatch[0].rm_so = m->coldp - m->offp;
267*e0b8e63eSJohn Marino pmatch[0].rm_eo = endp - m->offp;
268*e0b8e63eSJohn Marino }
269*e0b8e63eSJohn Marino if (nmatch > 1) {
270*e0b8e63eSJohn Marino assert(m->pmatch != NULL);
271*e0b8e63eSJohn Marino for (i = 1; i < nmatch; i++)
272*e0b8e63eSJohn Marino if (i <= m->g->nsub)
273*e0b8e63eSJohn Marino pmatch[i] = m->pmatch[i];
274*e0b8e63eSJohn Marino else {
275*e0b8e63eSJohn Marino pmatch[i].rm_so = -1;
276*e0b8e63eSJohn Marino pmatch[i].rm_eo = -1;
277*e0b8e63eSJohn Marino }
278*e0b8e63eSJohn Marino }
279*e0b8e63eSJohn Marino
280*e0b8e63eSJohn Marino if (m->pmatch != NULL)
281*e0b8e63eSJohn Marino free((char *)m->pmatch);
282*e0b8e63eSJohn Marino if (m->lastpos != NULL)
283*e0b8e63eSJohn Marino free((char *)m->lastpos);
284*e0b8e63eSJohn Marino STATETEARDOWN(m);
285*e0b8e63eSJohn Marino return(0);
286*e0b8e63eSJohn Marino }
287*e0b8e63eSJohn Marino
288*e0b8e63eSJohn Marino /*
289*e0b8e63eSJohn Marino - dissect - figure out what matched what, no back references
290*e0b8e63eSJohn Marino */
291*e0b8e63eSJohn Marino static const RCHAR_T * /* == stop (success) always */
dissect(struct match * m,const RCHAR_T * start,const RCHAR_T * stop,sopno startst,sopno stopst)292*e0b8e63eSJohn Marino dissect(struct match *m, const RCHAR_T *start, const RCHAR_T *stop,
293*e0b8e63eSJohn Marino sopno startst, sopno stopst)
294*e0b8e63eSJohn Marino {
295*e0b8e63eSJohn Marino int i;
296*e0b8e63eSJohn Marino sopno ss; /* start sop of current subRE */
297*e0b8e63eSJohn Marino sopno es; /* end sop of current subRE */
298*e0b8e63eSJohn Marino const RCHAR_T *sp; /* start of string matched by it */
299*e0b8e63eSJohn Marino const RCHAR_T *stp; /* string matched by it cannot pass here */
300*e0b8e63eSJohn Marino const RCHAR_T *rest; /* start of rest of string */
301*e0b8e63eSJohn Marino const RCHAR_T *tail; /* string unmatched by rest of RE */
302*e0b8e63eSJohn Marino sopno ssub; /* start sop of subsubRE */
303*e0b8e63eSJohn Marino sopno esub; /* end sop of subsubRE */
304*e0b8e63eSJohn Marino const RCHAR_T *ssp; /* start of string matched by subsubRE */
305*e0b8e63eSJohn Marino const RCHAR_T *sep; /* end of string matched by subsubRE */
306*e0b8e63eSJohn Marino const RCHAR_T *oldssp; /* previous ssp */
307*e0b8e63eSJohn Marino const RCHAR_T *dp;
308*e0b8e63eSJohn Marino
309*e0b8e63eSJohn Marino AT("diss", start, stop, startst, stopst);
310*e0b8e63eSJohn Marino sp = start;
311*e0b8e63eSJohn Marino for (ss = startst; ss < stopst; ss = es) {
312*e0b8e63eSJohn Marino /* identify end of subRE */
313*e0b8e63eSJohn Marino es = ss;
314*e0b8e63eSJohn Marino switch (m->g->strip[es]) {
315*e0b8e63eSJohn Marino case OPLUS_:
316*e0b8e63eSJohn Marino case OQUEST_:
317*e0b8e63eSJohn Marino es += m->g->stripdata[es];
318*e0b8e63eSJohn Marino break;
319*e0b8e63eSJohn Marino case OCH_:
320*e0b8e63eSJohn Marino while (m->g->strip[es] != O_CH)
321*e0b8e63eSJohn Marino es += m->g->stripdata[es];
322*e0b8e63eSJohn Marino break;
323*e0b8e63eSJohn Marino }
324*e0b8e63eSJohn Marino es++;
325*e0b8e63eSJohn Marino
326*e0b8e63eSJohn Marino /* figure out what it matched */
327*e0b8e63eSJohn Marino switch (m->g->strip[ss]) {
328*e0b8e63eSJohn Marino case OEND:
329*e0b8e63eSJohn Marino assert(nope);
330*e0b8e63eSJohn Marino break;
331*e0b8e63eSJohn Marino case OCHAR:
332*e0b8e63eSJohn Marino sp++;
333*e0b8e63eSJohn Marino break;
334*e0b8e63eSJohn Marino case OBOL:
335*e0b8e63eSJohn Marino case OEOL:
336*e0b8e63eSJohn Marino case OBOW:
337*e0b8e63eSJohn Marino case OEOW:
338*e0b8e63eSJohn Marino break;
339*e0b8e63eSJohn Marino case OANY:
340*e0b8e63eSJohn Marino case OANYOF:
341*e0b8e63eSJohn Marino sp++;
342*e0b8e63eSJohn Marino break;
343*e0b8e63eSJohn Marino case OBACK_:
344*e0b8e63eSJohn Marino case O_BACK:
345*e0b8e63eSJohn Marino assert(nope);
346*e0b8e63eSJohn Marino break;
347*e0b8e63eSJohn Marino /* cases where length of match is hard to find */
348*e0b8e63eSJohn Marino case OQUEST_:
349*e0b8e63eSJohn Marino stp = stop;
350*e0b8e63eSJohn Marino for (;;) {
351*e0b8e63eSJohn Marino /* how long could this one be? */
352*e0b8e63eSJohn Marino rest = slow(m, sp, stp, ss, es);
353*e0b8e63eSJohn Marino assert(rest != NULL); /* it did match */
354*e0b8e63eSJohn Marino /* could the rest match the rest? */
355*e0b8e63eSJohn Marino tail = slow(m, rest, stop, es, stopst);
356*e0b8e63eSJohn Marino if (tail == stop)
357*e0b8e63eSJohn Marino break; /* yes! */
358*e0b8e63eSJohn Marino /* no -- try a shorter match for this one */
359*e0b8e63eSJohn Marino stp = rest - 1;
360*e0b8e63eSJohn Marino assert(stp >= sp); /* it did work */
361*e0b8e63eSJohn Marino }
362*e0b8e63eSJohn Marino ssub = ss + 1;
363*e0b8e63eSJohn Marino esub = es - 1;
364*e0b8e63eSJohn Marino /* did innards match? */
365*e0b8e63eSJohn Marino if (slow(m, sp, rest, ssub, esub) != NULL) {
366*e0b8e63eSJohn Marino dp = dissect(m, sp, rest, ssub, esub);
367*e0b8e63eSJohn Marino assert(dp == rest);
368*e0b8e63eSJohn Marino } else /* no */
369*e0b8e63eSJohn Marino assert(sp == rest);
370*e0b8e63eSJohn Marino sp = rest;
371*e0b8e63eSJohn Marino break;
372*e0b8e63eSJohn Marino case OPLUS_:
373*e0b8e63eSJohn Marino stp = stop;
374*e0b8e63eSJohn Marino for (;;) {
375*e0b8e63eSJohn Marino /* how long could this one be? */
376*e0b8e63eSJohn Marino rest = slow(m, sp, stp, ss, es);
377*e0b8e63eSJohn Marino assert(rest != NULL); /* it did match */
378*e0b8e63eSJohn Marino /* could the rest match the rest? */
379*e0b8e63eSJohn Marino tail = slow(m, rest, stop, es, stopst);
380*e0b8e63eSJohn Marino if (tail == stop)
381*e0b8e63eSJohn Marino break; /* yes! */
382*e0b8e63eSJohn Marino /* no -- try a shorter match for this one */
383*e0b8e63eSJohn Marino stp = rest - 1;
384*e0b8e63eSJohn Marino assert(stp >= sp); /* it did work */
385*e0b8e63eSJohn Marino }
386*e0b8e63eSJohn Marino ssub = ss + 1;
387*e0b8e63eSJohn Marino esub = es - 1;
388*e0b8e63eSJohn Marino ssp = sp;
389*e0b8e63eSJohn Marino oldssp = ssp;
390*e0b8e63eSJohn Marino for (;;) { /* find last match of innards */
391*e0b8e63eSJohn Marino sep = slow(m, ssp, rest, ssub, esub);
392*e0b8e63eSJohn Marino if (sep == NULL || sep == ssp)
393*e0b8e63eSJohn Marino break; /* failed or matched null */
394*e0b8e63eSJohn Marino oldssp = ssp; /* on to next try */
395*e0b8e63eSJohn Marino ssp = sep;
396*e0b8e63eSJohn Marino }
397*e0b8e63eSJohn Marino if (sep == NULL) {
398*e0b8e63eSJohn Marino /* last successful match */
399*e0b8e63eSJohn Marino sep = ssp;
400*e0b8e63eSJohn Marino ssp = oldssp;
401*e0b8e63eSJohn Marino }
402*e0b8e63eSJohn Marino assert(sep == rest); /* must exhaust substring */
403*e0b8e63eSJohn Marino assert(slow(m, ssp, sep, ssub, esub) == rest);
404*e0b8e63eSJohn Marino dp = dissect(m, ssp, sep, ssub, esub);
405*e0b8e63eSJohn Marino assert(dp == sep);
406*e0b8e63eSJohn Marino sp = rest;
407*e0b8e63eSJohn Marino break;
408*e0b8e63eSJohn Marino case OCH_:
409*e0b8e63eSJohn Marino stp = stop;
410*e0b8e63eSJohn Marino for (;;) {
411*e0b8e63eSJohn Marino /* how long could this one be? */
412*e0b8e63eSJohn Marino rest = slow(m, sp, stp, ss, es);
413*e0b8e63eSJohn Marino assert(rest != NULL); /* it did match */
414*e0b8e63eSJohn Marino /* could the rest match the rest? */
415*e0b8e63eSJohn Marino tail = slow(m, rest, stop, es, stopst);
416*e0b8e63eSJohn Marino if (tail == stop)
417*e0b8e63eSJohn Marino break; /* yes! */
418*e0b8e63eSJohn Marino /* no -- try a shorter match for this one */
419*e0b8e63eSJohn Marino stp = rest - 1;
420*e0b8e63eSJohn Marino assert(stp >= sp); /* it did work */
421*e0b8e63eSJohn Marino }
422*e0b8e63eSJohn Marino ssub = ss + 1;
423*e0b8e63eSJohn Marino esub = ss + m->g->stripdata[ss] - 1;
424*e0b8e63eSJohn Marino assert(m->g->strip[esub] == OOR1);
425*e0b8e63eSJohn Marino for (;;) { /* find first matching branch */
426*e0b8e63eSJohn Marino if (slow(m, sp, rest, ssub, esub) == rest)
427*e0b8e63eSJohn Marino break; /* it matched all of it */
428*e0b8e63eSJohn Marino /* that one missed, try next one */
429*e0b8e63eSJohn Marino assert(m->g->strip[esub] == OOR1);
430*e0b8e63eSJohn Marino esub++;
431*e0b8e63eSJohn Marino assert(m->g->strip[esub] == OOR2);
432*e0b8e63eSJohn Marino ssub = esub + 1;
433*e0b8e63eSJohn Marino esub += m->g->stripdata[esub];
434*e0b8e63eSJohn Marino if (m->g->strip[esub] == OOR2)
435*e0b8e63eSJohn Marino esub--;
436*e0b8e63eSJohn Marino else
437*e0b8e63eSJohn Marino assert(m->g->strip[esub] == O_CH);
438*e0b8e63eSJohn Marino }
439*e0b8e63eSJohn Marino dp = dissect(m, sp, rest, ssub, esub);
440*e0b8e63eSJohn Marino assert(dp == rest);
441*e0b8e63eSJohn Marino sp = rest;
442*e0b8e63eSJohn Marino break;
443*e0b8e63eSJohn Marino case O_PLUS:
444*e0b8e63eSJohn Marino case O_QUEST:
445*e0b8e63eSJohn Marino case OOR1:
446*e0b8e63eSJohn Marino case OOR2:
447*e0b8e63eSJohn Marino case O_CH:
448*e0b8e63eSJohn Marino assert(nope);
449*e0b8e63eSJohn Marino break;
450*e0b8e63eSJohn Marino case OLPAREN:
451*e0b8e63eSJohn Marino i = m->g->stripdata[ss];
452*e0b8e63eSJohn Marino assert(0 < i && i <= m->g->nsub);
453*e0b8e63eSJohn Marino m->pmatch[i].rm_so = sp - m->offp;
454*e0b8e63eSJohn Marino break;
455*e0b8e63eSJohn Marino case ORPAREN:
456*e0b8e63eSJohn Marino i = m->g->stripdata[ss];
457*e0b8e63eSJohn Marino assert(0 < i && i <= m->g->nsub);
458*e0b8e63eSJohn Marino m->pmatch[i].rm_eo = sp - m->offp;
459*e0b8e63eSJohn Marino break;
460*e0b8e63eSJohn Marino default: /* uh oh */
461*e0b8e63eSJohn Marino assert(nope);
462*e0b8e63eSJohn Marino break;
463*e0b8e63eSJohn Marino }
464*e0b8e63eSJohn Marino }
465*e0b8e63eSJohn Marino
466*e0b8e63eSJohn Marino assert(sp == stop);
467*e0b8e63eSJohn Marino return(sp);
468*e0b8e63eSJohn Marino }
469*e0b8e63eSJohn Marino
470*e0b8e63eSJohn Marino /*
471*e0b8e63eSJohn Marino - backref - figure out what matched what, figuring in back references
472*e0b8e63eSJohn Marino */
473*e0b8e63eSJohn Marino static const RCHAR_T * /* == stop (success) or NULL (failure) */
backref(struct match * m,const RCHAR_T * start,const RCHAR_T * stop,sopno startst,sopno stopst,sopno lev)474*e0b8e63eSJohn Marino backref(struct match *m, const RCHAR_T *start, const RCHAR_T *stop,
475*e0b8e63eSJohn Marino sopno startst, sopno stopst, sopno lev) /* PLUS nesting level */
476*e0b8e63eSJohn Marino {
477*e0b8e63eSJohn Marino int i;
478*e0b8e63eSJohn Marino sopno ss; /* start sop of current subRE */
479*e0b8e63eSJohn Marino const RCHAR_T *sp; /* start of string matched by it */
480*e0b8e63eSJohn Marino sopno ssub; /* start sop of subsubRE */
481*e0b8e63eSJohn Marino sopno esub; /* end sop of subsubRE */
482*e0b8e63eSJohn Marino const RCHAR_T *ssp; /* start of string matched by subsubRE */
483*e0b8e63eSJohn Marino const RCHAR_T *dp;
484*e0b8e63eSJohn Marino size_t len;
485*e0b8e63eSJohn Marino int hard;
486*e0b8e63eSJohn Marino sop s;
487*e0b8e63eSJohn Marino RCHAR_T d;
488*e0b8e63eSJohn Marino regoff_t offsave;
489*e0b8e63eSJohn Marino cset *cs;
490*e0b8e63eSJohn Marino
491*e0b8e63eSJohn Marino AT("back", start, stop, startst, stopst);
492*e0b8e63eSJohn Marino sp = start;
493*e0b8e63eSJohn Marino
494*e0b8e63eSJohn Marino /* get as far as we can with easy stuff */
495*e0b8e63eSJohn Marino hard = 0;
496*e0b8e63eSJohn Marino for (ss = startst; !hard && ss < stopst; ss++) {
497*e0b8e63eSJohn Marino s = m->g->strip[ss];
498*e0b8e63eSJohn Marino d = m->g->stripdata[ss];
499*e0b8e63eSJohn Marino switch (s) {
500*e0b8e63eSJohn Marino case OCHAR:
501*e0b8e63eSJohn Marino if (sp == stop || *sp++ != d)
502*e0b8e63eSJohn Marino return(NULL);
503*e0b8e63eSJohn Marino break;
504*e0b8e63eSJohn Marino case OANY:
505*e0b8e63eSJohn Marino if (sp == stop)
506*e0b8e63eSJohn Marino return(NULL);
507*e0b8e63eSJohn Marino sp++;
508*e0b8e63eSJohn Marino break;
509*e0b8e63eSJohn Marino case OANYOF:
510*e0b8e63eSJohn Marino cs = &m->g->sets[d];
511*e0b8e63eSJohn Marino if (sp == stop || !CHIN(cs, *sp++))
512*e0b8e63eSJohn Marino return(NULL);
513*e0b8e63eSJohn Marino break;
514*e0b8e63eSJohn Marino case OBOL:
515*e0b8e63eSJohn Marino if ( (sp == m->beginp && !(m->eflags®_NOTBOL)) ||
516*e0b8e63eSJohn Marino (sp < m->endp && *(sp-1) == '\n' &&
517*e0b8e63eSJohn Marino (m->g->cflags®_NEWLINE)) )
518*e0b8e63eSJohn Marino { /* yes */ }
519*e0b8e63eSJohn Marino else
520*e0b8e63eSJohn Marino return(NULL);
521*e0b8e63eSJohn Marino break;
522*e0b8e63eSJohn Marino case OEOL:
523*e0b8e63eSJohn Marino if ( (sp == m->endp && !(m->eflags®_NOTEOL)) ||
524*e0b8e63eSJohn Marino (sp < m->endp && *sp == '\n' &&
525*e0b8e63eSJohn Marino (m->g->cflags®_NEWLINE)) )
526*e0b8e63eSJohn Marino { /* yes */ }
527*e0b8e63eSJohn Marino else
528*e0b8e63eSJohn Marino return(NULL);
529*e0b8e63eSJohn Marino break;
530*e0b8e63eSJohn Marino case OBOW:
531*e0b8e63eSJohn Marino if (( (sp == m->beginp && !(m->eflags®_NOTBOL)) ||
532*e0b8e63eSJohn Marino (sp < m->endp && *(sp-1) == '\n' &&
533*e0b8e63eSJohn Marino (m->g->cflags®_NEWLINE)) ||
534*e0b8e63eSJohn Marino (sp > m->beginp &&
535*e0b8e63eSJohn Marino !ISWORD(*(sp-1))) ) &&
536*e0b8e63eSJohn Marino (sp < m->endp && ISWORD(*sp)) )
537*e0b8e63eSJohn Marino { /* yes */ }
538*e0b8e63eSJohn Marino else
539*e0b8e63eSJohn Marino return(NULL);
540*e0b8e63eSJohn Marino break;
541*e0b8e63eSJohn Marino case OEOW:
542*e0b8e63eSJohn Marino if (( (sp == m->endp && !(m->eflags®_NOTEOL)) ||
543*e0b8e63eSJohn Marino (sp < m->endp && *sp == '\n' &&
544*e0b8e63eSJohn Marino (m->g->cflags®_NEWLINE)) ||
545*e0b8e63eSJohn Marino (sp < m->endp && !ISWORD(*sp)) ) &&
546*e0b8e63eSJohn Marino (sp > m->beginp && ISWORD(*(sp-1))) )
547*e0b8e63eSJohn Marino { /* yes */ }
548*e0b8e63eSJohn Marino else
549*e0b8e63eSJohn Marino return(NULL);
550*e0b8e63eSJohn Marino break;
551*e0b8e63eSJohn Marino case O_QUEST:
552*e0b8e63eSJohn Marino break;
553*e0b8e63eSJohn Marino case OOR1: /* matches null but needs to skip */
554*e0b8e63eSJohn Marino ss++;
555*e0b8e63eSJohn Marino s = m->g->strip[ss];
556*e0b8e63eSJohn Marino d = m->g->stripdata[ss];
557*e0b8e63eSJohn Marino do {
558*e0b8e63eSJohn Marino assert(s == OOR2);
559*e0b8e63eSJohn Marino ss += d;
560*e0b8e63eSJohn Marino s = m->g->strip[ss];
561*e0b8e63eSJohn Marino d = m->g->stripdata[ss];
562*e0b8e63eSJohn Marino } while (s != O_CH);
563*e0b8e63eSJohn Marino /* note that the ss++ gets us past the O_CH */
564*e0b8e63eSJohn Marino break;
565*e0b8e63eSJohn Marino default: /* have to make a choice */
566*e0b8e63eSJohn Marino hard = 1;
567*e0b8e63eSJohn Marino break;
568*e0b8e63eSJohn Marino }
569*e0b8e63eSJohn Marino }
570*e0b8e63eSJohn Marino if (!hard) { /* that was it! */
571*e0b8e63eSJohn Marino if (sp != stop)
572*e0b8e63eSJohn Marino return(NULL);
573*e0b8e63eSJohn Marino return(sp);
574*e0b8e63eSJohn Marino }
575*e0b8e63eSJohn Marino ss--; /* adjust for the for's final increment */
576*e0b8e63eSJohn Marino
577*e0b8e63eSJohn Marino /* the hard stuff */
578*e0b8e63eSJohn Marino AT("hard", sp, stop, ss, stopst);
579*e0b8e63eSJohn Marino s = m->g->strip[ss];
580*e0b8e63eSJohn Marino d = m->g->stripdata[ss];
581*e0b8e63eSJohn Marino switch (s) {
582*e0b8e63eSJohn Marino case OBACK_: /* the vilest depths */
583*e0b8e63eSJohn Marino i = d;
584*e0b8e63eSJohn Marino assert(0 < i && i <= m->g->nsub);
585*e0b8e63eSJohn Marino if (m->pmatch[i].rm_eo == -1)
586*e0b8e63eSJohn Marino return(NULL);
587*e0b8e63eSJohn Marino assert(m->pmatch[i].rm_so != -1);
588*e0b8e63eSJohn Marino len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
589*e0b8e63eSJohn Marino assert(stop - m->beginp >= len);
590*e0b8e63eSJohn Marino if (sp > stop - len)
591*e0b8e63eSJohn Marino return(NULL); /* not enough left to match */
592*e0b8e63eSJohn Marino ssp = m->offp + m->pmatch[i].rm_so;
593*e0b8e63eSJohn Marino if (memcmp(sp, ssp, len) != 0)
594*e0b8e63eSJohn Marino return(NULL);
595*e0b8e63eSJohn Marino while (m->g->strip[ss] != O_BACK || m->g->stripdata[ss] != i)
596*e0b8e63eSJohn Marino ss++;
597*e0b8e63eSJohn Marino return(backref(m, sp+len, stop, ss+1, stopst, lev));
598*e0b8e63eSJohn Marino break;
599*e0b8e63eSJohn Marino case OQUEST_: /* to null or not */
600*e0b8e63eSJohn Marino dp = backref(m, sp, stop, ss+1, stopst, lev);
601*e0b8e63eSJohn Marino if (dp != NULL)
602*e0b8e63eSJohn Marino return(dp); /* not */
603*e0b8e63eSJohn Marino return(backref(m, sp, stop, ss+d+1, stopst, lev));
604*e0b8e63eSJohn Marino break;
605*e0b8e63eSJohn Marino case OPLUS_:
606*e0b8e63eSJohn Marino assert(m->lastpos != NULL);
607*e0b8e63eSJohn Marino assert(lev+1 <= m->g->nplus);
608*e0b8e63eSJohn Marino m->lastpos[lev+1] = sp;
609*e0b8e63eSJohn Marino return(backref(m, sp, stop, ss+1, stopst, lev+1));
610*e0b8e63eSJohn Marino break;
611*e0b8e63eSJohn Marino case O_PLUS:
612*e0b8e63eSJohn Marino if (sp == m->lastpos[lev]) /* last pass matched null */
613*e0b8e63eSJohn Marino return(backref(m, sp, stop, ss+1, stopst, lev-1));
614*e0b8e63eSJohn Marino /* try another pass */
615*e0b8e63eSJohn Marino m->lastpos[lev] = sp;
616*e0b8e63eSJohn Marino dp = backref(m, sp, stop, ss-d+1, stopst, lev);
617*e0b8e63eSJohn Marino if (dp == NULL)
618*e0b8e63eSJohn Marino return(backref(m, sp, stop, ss+1, stopst, lev-1));
619*e0b8e63eSJohn Marino else
620*e0b8e63eSJohn Marino return(dp);
621*e0b8e63eSJohn Marino break;
622*e0b8e63eSJohn Marino case OCH_: /* find the right one, if any */
623*e0b8e63eSJohn Marino ssub = ss + 1;
624*e0b8e63eSJohn Marino esub = ss + d - 1;
625*e0b8e63eSJohn Marino assert(m->g->strip[esub] == OOR1);
626*e0b8e63eSJohn Marino for (;;) { /* find first matching branch */
627*e0b8e63eSJohn Marino dp = backref(m, sp, stop, ssub, esub, lev);
628*e0b8e63eSJohn Marino if (dp != NULL)
629*e0b8e63eSJohn Marino return(dp);
630*e0b8e63eSJohn Marino /* that one missed, try next one */
631*e0b8e63eSJohn Marino if (m->g->strip[esub] == O_CH)
632*e0b8e63eSJohn Marino return(NULL); /* there is none */
633*e0b8e63eSJohn Marino esub++;
634*e0b8e63eSJohn Marino assert(m->g->strip[esub] == OOR2);
635*e0b8e63eSJohn Marino ssub = esub + 1;
636*e0b8e63eSJohn Marino esub += m->g->stripdata[esub];
637*e0b8e63eSJohn Marino if (m->g->strip[esub] == OOR2)
638*e0b8e63eSJohn Marino esub--;
639*e0b8e63eSJohn Marino else
640*e0b8e63eSJohn Marino assert(m->g->strip[esub] == O_CH);
641*e0b8e63eSJohn Marino }
642*e0b8e63eSJohn Marino break;
643*e0b8e63eSJohn Marino case OLPAREN: /* must undo assignment if rest fails */
644*e0b8e63eSJohn Marino i = d;
645*e0b8e63eSJohn Marino assert(0 < i && i <= m->g->nsub);
646*e0b8e63eSJohn Marino offsave = m->pmatch[i].rm_so;
647*e0b8e63eSJohn Marino m->pmatch[i].rm_so = sp - m->offp;
648*e0b8e63eSJohn Marino dp = backref(m, sp, stop, ss+1, stopst, lev);
649*e0b8e63eSJohn Marino if (dp != NULL)
650*e0b8e63eSJohn Marino return(dp);
651*e0b8e63eSJohn Marino m->pmatch[i].rm_so = offsave;
652*e0b8e63eSJohn Marino return(NULL);
653*e0b8e63eSJohn Marino break;
654*e0b8e63eSJohn Marino case ORPAREN: /* must undo assignment if rest fails */
655*e0b8e63eSJohn Marino i = d;
656*e0b8e63eSJohn Marino assert(0 < i && i <= m->g->nsub);
657*e0b8e63eSJohn Marino offsave = m->pmatch[i].rm_eo;
658*e0b8e63eSJohn Marino m->pmatch[i].rm_eo = sp - m->offp;
659*e0b8e63eSJohn Marino dp = backref(m, sp, stop, ss+1, stopst, lev);
660*e0b8e63eSJohn Marino if (dp != NULL)
661*e0b8e63eSJohn Marino return(dp);
662*e0b8e63eSJohn Marino m->pmatch[i].rm_eo = offsave;
663*e0b8e63eSJohn Marino return(NULL);
664*e0b8e63eSJohn Marino break;
665*e0b8e63eSJohn Marino default: /* uh oh */
666*e0b8e63eSJohn Marino assert(nope);
667*e0b8e63eSJohn Marino break;
668*e0b8e63eSJohn Marino }
669*e0b8e63eSJohn Marino
670*e0b8e63eSJohn Marino /* "can't happen" */
671*e0b8e63eSJohn Marino assert(nope);
672*e0b8e63eSJohn Marino /* NOTREACHED */
673*e0b8e63eSJohn Marino return NULL;
674*e0b8e63eSJohn Marino }
675*e0b8e63eSJohn Marino
676*e0b8e63eSJohn Marino /*
677*e0b8e63eSJohn Marino - fast - step through the string at top speed
678*e0b8e63eSJohn Marino */
679*e0b8e63eSJohn Marino static const RCHAR_T * /* where tentative match ended, or NULL */
fast(struct match * m,const RCHAR_T * start,const RCHAR_T * stop,sopno startst,sopno stopst)680*e0b8e63eSJohn Marino fast(struct match *m, const RCHAR_T *start, const RCHAR_T *stop, sopno startst,
681*e0b8e63eSJohn Marino sopno stopst)
682*e0b8e63eSJohn Marino {
683*e0b8e63eSJohn Marino states st = m->st;
684*e0b8e63eSJohn Marino states fresh = m->fresh;
685*e0b8e63eSJohn Marino states tmp = m->tmp;
686*e0b8e63eSJohn Marino const RCHAR_T *p = start;
687*e0b8e63eSJohn Marino RCHAR_T c = (start == m->beginp) ? OUT : *(start-1);
688*e0b8e63eSJohn Marino RCHAR_T lastc; /* previous c */
689*e0b8e63eSJohn Marino int flag;
690*e0b8e63eSJohn Marino int i;
691*e0b8e63eSJohn Marino const RCHAR_T *coldp; /* last p after which no match was underway */
692*e0b8e63eSJohn Marino
693*e0b8e63eSJohn Marino CLEAR(st);
694*e0b8e63eSJohn Marino SET1(st, startst);
695*e0b8e63eSJohn Marino st = step(m->g, startst, stopst, st, NOTHING, OUT, st);
696*e0b8e63eSJohn Marino ASSIGN(fresh, st);
697*e0b8e63eSJohn Marino SP("start", st, *p);
698*e0b8e63eSJohn Marino coldp = NULL;
699*e0b8e63eSJohn Marino for (;;) {
700*e0b8e63eSJohn Marino /* next character */
701*e0b8e63eSJohn Marino lastc = c;
702*e0b8e63eSJohn Marino c = (p == m->endp) ? OUT : *p;
703*e0b8e63eSJohn Marino if (EQ(st, fresh))
704*e0b8e63eSJohn Marino coldp = p;
705*e0b8e63eSJohn Marino
706*e0b8e63eSJohn Marino /* is there an EOL and/or BOL between lastc and c? */
707*e0b8e63eSJohn Marino flag = 0;
708*e0b8e63eSJohn Marino i = 0;
709*e0b8e63eSJohn Marino if ( (lastc == '\n' && m->g->cflags®_NEWLINE) ||
710*e0b8e63eSJohn Marino (lastc == OUT && !(m->eflags®_NOTBOL)) ) {
711*e0b8e63eSJohn Marino flag = BOL;
712*e0b8e63eSJohn Marino i = m->g->nbol;
713*e0b8e63eSJohn Marino }
714*e0b8e63eSJohn Marino if ( (c == '\n' && m->g->cflags®_NEWLINE) ||
715*e0b8e63eSJohn Marino (c == OUT && !(m->eflags®_NOTEOL)) ) {
716*e0b8e63eSJohn Marino flag = (flag == BOL) ? BOLEOL : EOL;
717*e0b8e63eSJohn Marino i += m->g->neol;
718*e0b8e63eSJohn Marino }
719*e0b8e63eSJohn Marino if (i != 0) {
720*e0b8e63eSJohn Marino for (; i > 0; i--)
721*e0b8e63eSJohn Marino st = step(m->g, startst, stopst, st, flag, OUT, st);
722*e0b8e63eSJohn Marino SP("boleol", st, c);
723*e0b8e63eSJohn Marino }
724*e0b8e63eSJohn Marino
725*e0b8e63eSJohn Marino /* how about a word boundary? */
726*e0b8e63eSJohn Marino if ( (flag == BOL || (lastc != OUT && !ISWORD(lastc))) &&
727*e0b8e63eSJohn Marino (c != OUT && ISWORD(c)) ) {
728*e0b8e63eSJohn Marino flag = BOW;
729*e0b8e63eSJohn Marino }
730*e0b8e63eSJohn Marino if ( (lastc != OUT && ISWORD(lastc)) &&
731*e0b8e63eSJohn Marino (flag == EOL || (c != OUT && !ISWORD(c))) ) {
732*e0b8e63eSJohn Marino flag = EOW;
733*e0b8e63eSJohn Marino }
734*e0b8e63eSJohn Marino if (flag == BOW || flag == EOW) {
735*e0b8e63eSJohn Marino st = step(m->g, startst, stopst, st, flag, OUT, st);
736*e0b8e63eSJohn Marino SP("boweow", st, c);
737*e0b8e63eSJohn Marino }
738*e0b8e63eSJohn Marino
739*e0b8e63eSJohn Marino /* are we done? */
740*e0b8e63eSJohn Marino if (ISSET(st, stopst) || p == stop)
741*e0b8e63eSJohn Marino break; /* NOTE BREAK OUT */
742*e0b8e63eSJohn Marino
743*e0b8e63eSJohn Marino /* no, we must deal with this character */
744*e0b8e63eSJohn Marino ASSIGN(tmp, st);
745*e0b8e63eSJohn Marino ASSIGN(st, fresh);
746*e0b8e63eSJohn Marino assert(c != OUT);
747*e0b8e63eSJohn Marino st = step(m->g, startst, stopst, tmp, 0, c, st);
748*e0b8e63eSJohn Marino SP("aft", st, c);
749*e0b8e63eSJohn Marino assert(EQ(step(m->g, startst, stopst, st, NOTHING, OUT, st), st));
750*e0b8e63eSJohn Marino p++;
751*e0b8e63eSJohn Marino }
752*e0b8e63eSJohn Marino
753*e0b8e63eSJohn Marino assert(coldp != NULL);
754*e0b8e63eSJohn Marino m->coldp = coldp;
755*e0b8e63eSJohn Marino if (ISSET(st, stopst))
756*e0b8e63eSJohn Marino return(p+1);
757*e0b8e63eSJohn Marino else
758*e0b8e63eSJohn Marino return(NULL);
759*e0b8e63eSJohn Marino }
760*e0b8e63eSJohn Marino
761*e0b8e63eSJohn Marino /*
762*e0b8e63eSJohn Marino - slow - step through the string more deliberately
763*e0b8e63eSJohn Marino */
764*e0b8e63eSJohn Marino static const RCHAR_T * /* where it ended */
slow(struct match * m,const RCHAR_T * start,const RCHAR_T * stop,sopno startst,sopno stopst)765*e0b8e63eSJohn Marino slow(struct match *m, const RCHAR_T *start, const RCHAR_T *stop, sopno startst,
766*e0b8e63eSJohn Marino sopno stopst)
767*e0b8e63eSJohn Marino {
768*e0b8e63eSJohn Marino states st = m->st;
769*e0b8e63eSJohn Marino states empty = m->empty;
770*e0b8e63eSJohn Marino states tmp = m->tmp;
771*e0b8e63eSJohn Marino const RCHAR_T *p = start;
772*e0b8e63eSJohn Marino RCHAR_T c = (start == m->beginp) ? OUT : *(start-1);
773*e0b8e63eSJohn Marino RCHAR_T lastc; /* previous c */
774*e0b8e63eSJohn Marino int flag;
775*e0b8e63eSJohn Marino int i;
776*e0b8e63eSJohn Marino const RCHAR_T *matchp; /* last p at which a match ended */
777*e0b8e63eSJohn Marino
778*e0b8e63eSJohn Marino AT("slow", start, stop, startst, stopst);
779*e0b8e63eSJohn Marino CLEAR(st);
780*e0b8e63eSJohn Marino SET1(st, startst);
781*e0b8e63eSJohn Marino SP("sstart", st, *p);
782*e0b8e63eSJohn Marino st = step(m->g, startst, stopst, st, NOTHING, OUT, st);
783*e0b8e63eSJohn Marino matchp = NULL;
784*e0b8e63eSJohn Marino for (;;) {
785*e0b8e63eSJohn Marino /* next character */
786*e0b8e63eSJohn Marino lastc = c;
787*e0b8e63eSJohn Marino c = (p == m->endp) ? OUT : *p;
788*e0b8e63eSJohn Marino
789*e0b8e63eSJohn Marino /* is there an EOL and/or BOL between lastc and c? */
790*e0b8e63eSJohn Marino flag = 0;
791*e0b8e63eSJohn Marino i = 0;
792*e0b8e63eSJohn Marino if ( (lastc == '\n' && m->g->cflags®_NEWLINE) ||
793*e0b8e63eSJohn Marino (lastc == OUT && !(m->eflags®_NOTBOL)) ) {
794*e0b8e63eSJohn Marino flag = BOL;
795*e0b8e63eSJohn Marino i = m->g->nbol;
796*e0b8e63eSJohn Marino }
797*e0b8e63eSJohn Marino if ( (c == '\n' && m->g->cflags®_NEWLINE) ||
798*e0b8e63eSJohn Marino (c == OUT && !(m->eflags®_NOTEOL)) ) {
799*e0b8e63eSJohn Marino flag = (flag == BOL) ? BOLEOL : EOL;
800*e0b8e63eSJohn Marino i += m->g->neol;
801*e0b8e63eSJohn Marino }
802*e0b8e63eSJohn Marino if (i != 0) {
803*e0b8e63eSJohn Marino for (; i > 0; i--)
804*e0b8e63eSJohn Marino st = step(m->g, startst, stopst, st, flag, OUT, st);
805*e0b8e63eSJohn Marino SP("sboleol", st, c);
806*e0b8e63eSJohn Marino }
807*e0b8e63eSJohn Marino
808*e0b8e63eSJohn Marino /* how about a word boundary? */
809*e0b8e63eSJohn Marino if ( (flag == BOL || (lastc != OUT && !ISWORD(lastc))) &&
810*e0b8e63eSJohn Marino (c != OUT && ISWORD(c)) ) {
811*e0b8e63eSJohn Marino flag = BOW;
812*e0b8e63eSJohn Marino }
813*e0b8e63eSJohn Marino if ( (lastc != OUT && ISWORD(lastc)) &&
814*e0b8e63eSJohn Marino (flag == EOL || (c != OUT && !ISWORD(c))) ) {
815*e0b8e63eSJohn Marino flag = EOW;
816*e0b8e63eSJohn Marino }
817*e0b8e63eSJohn Marino if (flag == BOW || flag == EOW) {
818*e0b8e63eSJohn Marino st = step(m->g, startst, stopst, st, flag, OUT, st);
819*e0b8e63eSJohn Marino SP("sboweow", st, c);
820*e0b8e63eSJohn Marino }
821*e0b8e63eSJohn Marino
822*e0b8e63eSJohn Marino /* are we done? */
823*e0b8e63eSJohn Marino if (ISSET(st, stopst))
824*e0b8e63eSJohn Marino matchp = p;
825*e0b8e63eSJohn Marino if (EQ(st, empty) || p == stop)
826*e0b8e63eSJohn Marino break; /* NOTE BREAK OUT */
827*e0b8e63eSJohn Marino
828*e0b8e63eSJohn Marino /* no, we must deal with this character */
829*e0b8e63eSJohn Marino ASSIGN(tmp, st);
830*e0b8e63eSJohn Marino ASSIGN(st, empty);
831*e0b8e63eSJohn Marino assert(c != OUT);
832*e0b8e63eSJohn Marino st = step(m->g, startst, stopst, tmp, 0, c, st);
833*e0b8e63eSJohn Marino SP("saft", st, c);
834*e0b8e63eSJohn Marino assert(EQ(step(m->g, startst, stopst, st, NOTHING, OUT, st), st));
835*e0b8e63eSJohn Marino p++;
836*e0b8e63eSJohn Marino }
837*e0b8e63eSJohn Marino
838*e0b8e63eSJohn Marino return(matchp);
839*e0b8e63eSJohn Marino }
840*e0b8e63eSJohn Marino
841*e0b8e63eSJohn Marino
842*e0b8e63eSJohn Marino /*
843*e0b8e63eSJohn Marino - step - map set of states reachable before char to set reachable after
844*e0b8e63eSJohn Marino */
845*e0b8e63eSJohn Marino static states
step(struct re_guts * g,sopno start,sopno stop,states bef,int flag,RCHAR_T ch,states aft)846*e0b8e63eSJohn Marino step(struct re_guts *g,
847*e0b8e63eSJohn Marino sopno start, /* start state within strip */
848*e0b8e63eSJohn Marino sopno stop, /* state after stop state within strip */
849*e0b8e63eSJohn Marino states bef, /* states reachable before */
850*e0b8e63eSJohn Marino int flag, /* NONCHAR flag */
851*e0b8e63eSJohn Marino RCHAR_T ch, /* character code */
852*e0b8e63eSJohn Marino states aft) /* states already known reachable after */
853*e0b8e63eSJohn Marino {
854*e0b8e63eSJohn Marino cset *cs;
855*e0b8e63eSJohn Marino sop s;
856*e0b8e63eSJohn Marino RCHAR_T d;
857*e0b8e63eSJohn Marino sopno pc;
858*e0b8e63eSJohn Marino onestate here; /* note, macros know this name */
859*e0b8e63eSJohn Marino sopno look;
860*e0b8e63eSJohn Marino int i;
861*e0b8e63eSJohn Marino
862*e0b8e63eSJohn Marino for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
863*e0b8e63eSJohn Marino s = g->strip[pc];
864*e0b8e63eSJohn Marino d = g->stripdata[pc];
865*e0b8e63eSJohn Marino switch (s) {
866*e0b8e63eSJohn Marino case OEND:
867*e0b8e63eSJohn Marino assert(pc == stop-1);
868*e0b8e63eSJohn Marino break;
869*e0b8e63eSJohn Marino case OCHAR:
870*e0b8e63eSJohn Marino /* only characters can match */
871*e0b8e63eSJohn Marino assert(!flag || ch != d);
872*e0b8e63eSJohn Marino if (ch == d)
873*e0b8e63eSJohn Marino FWD(aft, bef, 1);
874*e0b8e63eSJohn Marino break;
875*e0b8e63eSJohn Marino case OBOL:
876*e0b8e63eSJohn Marino if (flag == BOL || flag == BOLEOL)
877*e0b8e63eSJohn Marino FWD(aft, bef, 1);
878*e0b8e63eSJohn Marino break;
879*e0b8e63eSJohn Marino case OEOL:
880*e0b8e63eSJohn Marino if (flag == EOL || flag == BOLEOL)
881*e0b8e63eSJohn Marino FWD(aft, bef, 1);
882*e0b8e63eSJohn Marino break;
883*e0b8e63eSJohn Marino case OBOW:
884*e0b8e63eSJohn Marino if (flag == BOW)
885*e0b8e63eSJohn Marino FWD(aft, bef, 1);
886*e0b8e63eSJohn Marino break;
887*e0b8e63eSJohn Marino case OEOW:
888*e0b8e63eSJohn Marino if (flag == EOW)
889*e0b8e63eSJohn Marino FWD(aft, bef, 1);
890*e0b8e63eSJohn Marino break;
891*e0b8e63eSJohn Marino case OANY:
892*e0b8e63eSJohn Marino if (!flag)
893*e0b8e63eSJohn Marino FWD(aft, bef, 1);
894*e0b8e63eSJohn Marino break;
895*e0b8e63eSJohn Marino case OANYOF:
896*e0b8e63eSJohn Marino cs = &g->sets[d];
897*e0b8e63eSJohn Marino if (!flag && CHIN(cs, ch))
898*e0b8e63eSJohn Marino FWD(aft, bef, 1);
899*e0b8e63eSJohn Marino break;
900*e0b8e63eSJohn Marino case OBACK_: /* ignored here */
901*e0b8e63eSJohn Marino case O_BACK:
902*e0b8e63eSJohn Marino FWD(aft, aft, 1);
903*e0b8e63eSJohn Marino break;
904*e0b8e63eSJohn Marino case OPLUS_: /* forward, this is just an empty */
905*e0b8e63eSJohn Marino FWD(aft, aft, 1);
906*e0b8e63eSJohn Marino break;
907*e0b8e63eSJohn Marino case O_PLUS: /* both forward and back */
908*e0b8e63eSJohn Marino FWD(aft, aft, 1);
909*e0b8e63eSJohn Marino i = ISSETBACK(aft, d);
910*e0b8e63eSJohn Marino BACK(aft, aft, d);
911*e0b8e63eSJohn Marino if (!i && ISSETBACK(aft, d)) {
912*e0b8e63eSJohn Marino /* oho, must reconsider loop body */
913*e0b8e63eSJohn Marino pc -= d + 1;
914*e0b8e63eSJohn Marino INIT(here, pc);
915*e0b8e63eSJohn Marino }
916*e0b8e63eSJohn Marino break;
917*e0b8e63eSJohn Marino case OQUEST_: /* two branches, both forward */
918*e0b8e63eSJohn Marino FWD(aft, aft, 1);
919*e0b8e63eSJohn Marino FWD(aft, aft, d);
920*e0b8e63eSJohn Marino break;
921*e0b8e63eSJohn Marino case O_QUEST: /* just an empty */
922*e0b8e63eSJohn Marino FWD(aft, aft, 1);
923*e0b8e63eSJohn Marino break;
924*e0b8e63eSJohn Marino case OLPAREN: /* not significant here */
925*e0b8e63eSJohn Marino case ORPAREN:
926*e0b8e63eSJohn Marino FWD(aft, aft, 1);
927*e0b8e63eSJohn Marino break;
928*e0b8e63eSJohn Marino case OCH_: /* mark the first two branches */
929*e0b8e63eSJohn Marino FWD(aft, aft, 1);
930*e0b8e63eSJohn Marino assert(OP(g->strip[pc+d]) == OOR2);
931*e0b8e63eSJohn Marino FWD(aft, aft, d);
932*e0b8e63eSJohn Marino break;
933*e0b8e63eSJohn Marino case OOR1: /* done a branch, find the O_CH */
934*e0b8e63eSJohn Marino if (ISSTATEIN(aft, here)) {
935*e0b8e63eSJohn Marino for (look = 1; /**/; look += d) {
936*e0b8e63eSJohn Marino s = g->strip[pc+look];
937*e0b8e63eSJohn Marino d = g->stripdata[pc+look];
938*e0b8e63eSJohn Marino if (s == O_CH)
939*e0b8e63eSJohn Marino break;
940*e0b8e63eSJohn Marino assert(s == OOR2);
941*e0b8e63eSJohn Marino }
942*e0b8e63eSJohn Marino FWD(aft, aft, look);
943*e0b8e63eSJohn Marino }
944*e0b8e63eSJohn Marino break;
945*e0b8e63eSJohn Marino case OOR2: /* propagate OCH_'s marking */
946*e0b8e63eSJohn Marino FWD(aft, aft, 1);
947*e0b8e63eSJohn Marino if (g->strip[pc+d] != O_CH) {
948*e0b8e63eSJohn Marino assert(g->strip[pc+d] == OOR2);
949*e0b8e63eSJohn Marino FWD(aft, aft, d);
950*e0b8e63eSJohn Marino }
951*e0b8e63eSJohn Marino break;
952*e0b8e63eSJohn Marino case O_CH: /* just empty */
953*e0b8e63eSJohn Marino FWD(aft, aft, 1);
954*e0b8e63eSJohn Marino break;
955*e0b8e63eSJohn Marino default: /* ooooops... */
956*e0b8e63eSJohn Marino assert(nope);
957*e0b8e63eSJohn Marino break;
958*e0b8e63eSJohn Marino }
959*e0b8e63eSJohn Marino }
960*e0b8e63eSJohn Marino
961*e0b8e63eSJohn Marino return(aft);
962*e0b8e63eSJohn Marino }
963*e0b8e63eSJohn Marino
964*e0b8e63eSJohn Marino #ifdef REDEBUG
965*e0b8e63eSJohn Marino /*
966*e0b8e63eSJohn Marino - print - print a set of states
967*e0b8e63eSJohn Marino */
968*e0b8e63eSJohn Marino static void
print(struct match * m,char * caption,states st,int ch,FILE * d)969*e0b8e63eSJohn Marino print(struct match *m, char *caption, states st, int ch, FILE *d)
970*e0b8e63eSJohn Marino {
971*e0b8e63eSJohn Marino struct re_guts *g = m->g;
972*e0b8e63eSJohn Marino int i;
973*e0b8e63eSJohn Marino int first = 1;
974*e0b8e63eSJohn Marino
975*e0b8e63eSJohn Marino if (!(m->eflags®_TRACE))
976*e0b8e63eSJohn Marino return;
977*e0b8e63eSJohn Marino
978*e0b8e63eSJohn Marino fprintf(d, "%s", caption);
979*e0b8e63eSJohn Marino if (ch != '\0')
980*e0b8e63eSJohn Marino fprintf(d, " %s", pchar(ch));
981*e0b8e63eSJohn Marino for (i = 0; i < g->nstates; i++)
982*e0b8e63eSJohn Marino if (ISSET(st, i)) {
983*e0b8e63eSJohn Marino fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
984*e0b8e63eSJohn Marino first = 0;
985*e0b8e63eSJohn Marino }
986*e0b8e63eSJohn Marino fprintf(d, "\n");
987*e0b8e63eSJohn Marino }
988*e0b8e63eSJohn Marino
989*e0b8e63eSJohn Marino /*
990*e0b8e63eSJohn Marino - at - print current situation
991*e0b8e63eSJohn Marino */
992*e0b8e63eSJohn Marino static void
at(struct match * m,char * title,char * start,char * stop,sopno startst,sopno stopst)993*e0b8e63eSJohn Marino at(struct match *m, char *title, char *start, char *stop, sopno startst,
994*e0b8e63eSJohn Marino sopno stopst)
995*e0b8e63eSJohn Marino {
996*e0b8e63eSJohn Marino if (!(m->eflags®_TRACE))
997*e0b8e63eSJohn Marino return;
998*e0b8e63eSJohn Marino
999*e0b8e63eSJohn Marino printf("%s %s-", title, pchar(*start));
1000*e0b8e63eSJohn Marino printf("%s ", pchar(*stop));
1001*e0b8e63eSJohn Marino printf("%ld-%ld\n", (long)startst, (long)stopst);
1002*e0b8e63eSJohn Marino }
1003*e0b8e63eSJohn Marino
1004*e0b8e63eSJohn Marino #ifndef PCHARDONE
1005*e0b8e63eSJohn Marino #define PCHARDONE /* never again */
1006*e0b8e63eSJohn Marino /*
1007*e0b8e63eSJohn Marino - pchar - make a character printable
1008*e0b8e63eSJohn Marino *
1009*e0b8e63eSJohn Marino * Is this identical to regchar() over in debug.c? Well, yes. But a
1010*e0b8e63eSJohn Marino * duplicate here avoids having a debugging-capable regexec.o tied to
1011*e0b8e63eSJohn Marino * a matching debug.o, and this is convenient. It all disappears in
1012*e0b8e63eSJohn Marino * the non-debug compilation anyway, so it doesn't matter much.
1013*e0b8e63eSJohn Marino */
1014*e0b8e63eSJohn Marino static char * /* -> representation */
pchar(int ch)1015*e0b8e63eSJohn Marino pchar(int ch)
1016*e0b8e63eSJohn Marino {
1017*e0b8e63eSJohn Marino static char pbuf[10];
1018*e0b8e63eSJohn Marino
1019*e0b8e63eSJohn Marino if (isprint(ch) || ch == ' ')
1020*e0b8e63eSJohn Marino snprintf(pbuf, sizeof(pbuf), "%c", ch);
1021*e0b8e63eSJohn Marino else
1022*e0b8e63eSJohn Marino snprintf(pbuf, sizeof(pbuf), "\\%o", ch);
1023*e0b8e63eSJohn Marino return(pbuf);
1024*e0b8e63eSJohn Marino }
1025*e0b8e63eSJohn Marino #endif
1026*e0b8e63eSJohn Marino #endif
1027*e0b8e63eSJohn Marino
1028*e0b8e63eSJohn Marino #undef matcher
1029*e0b8e63eSJohn Marino #undef fast
1030*e0b8e63eSJohn Marino #undef slow
1031*e0b8e63eSJohn Marino #undef dissect
1032*e0b8e63eSJohn Marino #undef backref
1033*e0b8e63eSJohn Marino #undef step
1034*e0b8e63eSJohn Marino #undef print
1035*e0b8e63eSJohn Marino #undef at
1036*e0b8e63eSJohn Marino #undef match
1037