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