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