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