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