source: vendor/FreeBSD-libc/5.3/regex/engine.c

Last change on this file was 1695, checked in by bird, 21 years ago

FreeBSD 5.3 libc sources.
  • Property cvs2svn:cvs-rev set to 1.1.1.2
  • Property svn:eol-style set to native
  • Property svn:executable set to *
File size: 29.9 KB
Line 
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 */
85struct 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
104extern "C" {
105#endif
106
107/* === engine.c === */
108static int matcher(struct re_guts *g, char *string, size_t nmatch, regmatch_t pmatch[], int eflags);
109static char *dissect(struct match *m, char *start, char *stop, sopno startst, sopno stopst);
110static char *backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst, sopno lev);
111static char *fast(struct match *m, char *start, char *stop, sopno startst, sopno stopst);
112static char *slow(struct match *m, char *start, char *stop, sopno startst, sopno stopst);
113static 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
123static void print(struct match *m, char *caption, states st, int ch, FILE *d);
124#endif
125#ifdef REDEBUG
126static void at(struct match *m, char *title, char *start, char *stop, sopno startst, sopno stopst);
127#endif
128#ifdef REDEBUG
129static 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 */
152static int /* 0 success, REG_NOMATCH failure */
153matcher(g, string, nmatch, pmatch, eflags)
154struct re_guts *g;
155char *string;
156size_t nmatch;
157regmatch_t pmatch[];
158int 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);
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);
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 */
367static char * /* == stop (success) always */
368dissect(m, start, stop, startst, stopst)
369struct match *m;
370char *start;
371char *stop;
372sopno startst;
373sopno 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);
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);
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 assert(sep == rest); /* must exhaust substring */
483 assert(slow(m, ssp, sep, ssub, esub) == rest);
484 dp = dissect(m, ssp, sep, ssub, esub);
485 assert(dp == sep);
486 sp = rest;
487 break;
488 case OCH_:
489 stp = stop;
490 for (;;) {
491 /* how long could this one be? */
492 rest = slow(m, sp, stp, ss, es);
493 assert(rest != NULL); /* it did match */
494 /* could the rest match the rest? */
495 tail = slow(m, rest, stop, es, stopst);
496 if (tail == stop)
497 break; /* yes! */
498 /* no -- try a shorter match for this one */
499 stp = rest - 1;
500 assert(stp >= sp); /* it did work */
501 }
502 ssub = ss + 1;
503 esub = ss + OPND(m->g->strip[ss]) - 1;
504 assert(OP(m->g->strip[esub]) == OOR1);
505 for (;;) { /* find first matching branch */
506 if (slow(m, sp, rest, ssub, esub) == rest)
507 break; /* it matched all of it */
508 /* that one missed, try next one */
509 assert(OP(m->g->strip[esub]) == OOR1);
510 esub++;
511 assert(OP(m->g->strip[esub]) == OOR2);
512 ssub = esub + 1;
513 esub += OPND(m->g->strip[esub]);
514 if (OP(m->g->strip[esub]) == OOR2)
515 esub--;
516 else
517 assert(OP(m->g->strip[esub]) == O_CH);
518 }
519 dp = dissect(m, sp, rest, ssub, esub);
520 assert(dp == rest);
521 sp = rest;
522 break;
523 case O_PLUS:
524 case O_QUEST:
525 case OOR1:
526 case OOR2:
527 case O_CH:
528 assert(nope);
529 break;
530 case OLPAREN:
531 i = OPND(m->g->strip[ss]);
532 assert(0 < i && i <= m->g->nsub);
533 m->pmatch[i].rm_so = sp - m->offp;
534 break;
535 case ORPAREN:
536 i = OPND(m->g->strip[ss]);
537 assert(0 < i && i <= m->g->nsub);
538 m->pmatch[i].rm_eo = sp - m->offp;
539 break;
540 default: /* uh oh */
541 assert(nope);
542 break;
543 }
544 }
545
546 assert(sp == stop);
547 return(sp);
548}
549
550/*
551 - backref - figure out what matched what, figuring in back references
552 == static char *backref(struct match *m, char *start, \
553 == char *stop, sopno startst, sopno stopst, sopno lev);
554 */
555static char * /* == stop (success) or NULL (failure) */
556backref(m, start, stop, startst, stopst, lev)
557struct match *m;
558char *start;
559char *stop;
560sopno startst;
561sopno stopst;
562sopno lev; /* PLUS nesting level */
563{
564 int i;
565 sopno ss; /* start sop of current subRE */
566 char *sp; /* start of string matched by it */
567 sopno ssub; /* start sop of subsubRE */
568 sopno esub; /* end sop of subsubRE */
569 char *ssp; /* start of string matched by subsubRE */
570 char *dp;
571 size_t len;
572 int hard;
573 sop s;
574 regoff_t offsave;
575 cset *cs;
576 wint_t wc;
577
578 AT("back", start, stop, startst, stopst);
579 sp = start;
580
581 /* get as far as we can with easy stuff */
582 hard = 0;
583 for (ss = startst; !hard && ss < stopst; ss++)
584 switch (OP(s = m->g->strip[ss])) {
585 case OCHAR:
586 if (sp == stop)
587 return(NULL);
588 sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR);
589 if (wc != OPND(s))
590 return(NULL);
591 break;
592 case OANY:
593 if (sp == stop)
594 return(NULL);
595 sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR);
596 if (wc == BADCHAR)
597 return (NULL);
598 break;
599 case OANYOF:
600 if (sp == stop)
601 return (NULL);
602 cs = &m->g->sets[OPND(s)];
603 sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR);
604 if (wc == BADCHAR || !CHIN(cs, wc))
605 return(NULL);
606 break;
607 case OBOL:
608 if ( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
609 (sp < m->endp && *(sp-1) == '\n' &&
610 (m->g->cflags&REG_NEWLINE)) )
611 { /* yes */ }
612 else
613 return(NULL);
614 break;
615 case OEOL:
616 if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
617 (sp < m->endp && *sp == '\n' &&
618 (m->g->cflags&REG_NEWLINE)) )
619 { /* yes */ }
620 else
621 return(NULL);
622 break;
623 case OBOW:
624 if (( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
625 (sp < m->endp && *(sp-1) == '\n' &&
626 (m->g->cflags&REG_NEWLINE)) ||
627 (sp > m->beginp &&
628 !ISWORD(*(sp-1))) ) &&
629 (sp < m->endp && ISWORD(*sp)) )
630 { /* yes */ }
631 else
632 return(NULL);
633 break;
634 case OEOW:
635 if (( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
636 (sp < m->endp && *sp == '\n' &&
637 (m->g->cflags&REG_NEWLINE)) ||
638 (sp < m->endp && !ISWORD(*sp)) ) &&
639 (sp > m->beginp && ISWORD(*(sp-1))) )
640 { /* yes */ }
641 else
642 return(NULL);
643 break;
644 case O_QUEST:
645 break;
646 case OOR1: /* matches null but needs to skip */
647 ss++;
648 s = m->g->strip[ss];
649 do {
650 assert(OP(s) == OOR2);
651 ss += OPND(s);
652 } while (OP(s = m->g->strip[ss]) != O_CH);
653 /* note that the ss++ gets us past the O_CH */
654 break;
655 default: /* have to make a choice */
656 hard = 1;
657 break;
658 }
659 if (!hard) { /* that was it! */
660 if (sp != stop)
661 return(NULL);
662 return(sp);
663 }
664 ss--; /* adjust for the for's final increment */
665
666 /* the hard stuff */
667 AT("hard", sp, stop, ss, stopst);
668 s = m->g->strip[ss];
669 switch (OP(s)) {
670 case OBACK_: /* the vilest depths */
671 i = OPND(s);
672 assert(0 < i && i <= m->g->nsub);
673 if (m->pmatch[i].rm_eo == -1)
674 return(NULL);
675 assert(m->pmatch[i].rm_so != -1);
676 len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
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));
686 break;
687 case OQUEST_: /* to null or not */
688 dp = backref(m, sp, stop, ss+1, stopst, lev);
689 if (dp != NULL)
690 return(dp); /* not */
691 return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev));
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));
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));
702 /* try another pass */
703 m->lastpos[lev] = sp;
704 dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev);
705 if (dp == NULL)
706 return(backref(m, sp, stop, ss+1, stopst, lev-1));
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);
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);
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);
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 char *fast(struct match *m, char *start, \
767 == char *stop, sopno startst, sopno stopst);
768 */
769static char * /* where tentative match ended, or NULL */
770fast(m, start, stop, startst, stopst)
771struct match *m;
772char *start;
773char *stop;
774sopno startst;
775sopno stopst;
776{
777 states st = m->st;
778 states fresh = m->fresh;
779 states tmp = m->tmp;
780 char *p = start;
781 wint_t c;
782 wint_t lastc; /* previous c */
783 wint_t flagch;
784 int i;
785 char *coldp; /* last p after which no match was underway */
786 size_t clen;
787
788 CLEAR(st);
789 SET1(st, startst);
790 st = step(m->g, startst, stopst, st, NOTHING, st);
791 ASSIGN(fresh, st);
792 SP("start", st, *p);
793 coldp = NULL;
794 if (start == m->beginp)
795 c = OUT;
796 else {
797 /*
798 * XXX Wrong if the previous character was multi-byte.
799 * Newline never is (in encodings supported by FreeBSD),
800 * so this only breaks the ISWORD tests below.
801 */
802 c = (uch)*(start - 1);
803 }
804 for (;;) {
805 /* next character */
806 lastc = c;
807 if (p == m->endp)
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)
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, m->endp - p, &m->mbs, 0));
865 else
866 return(NULL);
867}
868
869/*
870 - slow - step through the string more deliberately
871 == static char *slow(struct match *m, char *start, \
872 == char *stop, sopno startst, sopno stopst);
873 */
874static char * /* where it ended */
875slow(m, start, stop, startst, stopst)
876struct match *m;
877char *start;
878char *stop;
879sopno startst;
880sopno stopst;
881{
882 states st = m->st;
883 states empty = m->empty;
884 states tmp = m->tmp;
885 char *p = start;
886 wint_t c;
887 wint_t lastc; /* previous c */
888 wint_t flagch;
889 int i;
890 char *matchp; /* last p at which a match ended */
891 size_t clen;
892
893 AT("slow", start, stop, startst, stopst);
894 CLEAR(st);
895 SET1(st, startst);
896 SP("sstart", st, *p);
897 st = step(m->g, startst, stopst, st, NOTHING, st);
898 matchp = NULL;
899 if (start == m->beginp)
900 c = OUT;
901 else {
902 /*
903 * XXX Wrong if the previous character was multi-byte.
904 * Newline never is (in encodings supported by FreeBSD),
905 * so this only breaks the ISWORD tests below.
906 */
907 c = (uch)*(start - 1);
908 }
909 for (;;) {
910 /* next character */
911 lastc = c;
912 if (p == m->endp) {
913 c = OUT;
914 clen = 0;
915 } else
916 clen = XMBRTOWC(&c, p, m->endp - p, &m->mbs, BADCHAR);
917
918 /* is there an EOL and/or BOL between lastc and c? */
919 flagch = '\0';
920 i = 0;
921 if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
922 (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
923 flagch = BOL;
924 i = m->g->nbol;
925 }
926 if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
927 (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
928 flagch = (flagch == BOL) ? BOLEOL : EOL;
929 i += m->g->neol;
930 }
931 if (i != 0) {
932 for (; i > 0; i--)
933 st = step(m->g, startst, stopst, st, flagch, st);
934 SP("sboleol", st, c);
935 }
936
937 /* how about a word boundary? */
938 if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
939 (c != OUT && ISWORD(c)) ) {
940 flagch = BOW;
941 }
942 if ( (lastc != OUT && ISWORD(lastc)) &&
943 (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
944 flagch = EOW;
945 }
946 if (flagch == BOW || flagch == EOW) {
947 st = step(m->g, startst, stopst, st, flagch, st);
948 SP("sboweow", st, c);
949 }
950
951 /* are we done? */
952 if (ISSET(st, stopst))
953 matchp = p;
954 if (EQ(st, empty) || p == stop)
955 break; /* NOTE BREAK OUT */
956
957 /* no, we must deal with this character */
958 ASSIGN(tmp, st);
959 ASSIGN(st, empty);
960 assert(c != OUT);
961 st = step(m->g, startst, stopst, tmp, c, st);
962 SP("saft", st, c);
963 assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
964 p += clen;
965 }
966
967 return(matchp);
968}
969
970
971/*
972 - step - map set of states reachable before char to set reachable after
973 == static states step(struct re_guts *g, sopno start, sopno stop, \
974 == states bef, int ch, states aft);
975 == #define BOL (OUT-1)
976 == #define EOL (BOL-1)
977 == #define BOLEOL (BOL-2)
978 == #define NOTHING (BOL-3)
979 == #define BOW (BOL-4)
980 == #define EOW (BOL-5)
981 == #define BADCHAR (BOL-6)
982 == #define NONCHAR(c) ((c) <= OUT)
983 */
984static states
985step(g, start, stop, bef, ch, aft)
986struct re_guts *g;
987sopno start; /* start state within strip */
988sopno stop; /* state after stop state within strip */
989states bef; /* states reachable before */
990wint_t ch; /* character or NONCHAR code */
991states aft; /* states already known reachable after */
992{
993 cset *cs;
994 sop s;
995 sopno pc;
996 onestate here; /* note, macros know this name */
997 sopno look;
998 int i;
999
1000 for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
1001 s = g->strip[pc];
1002 switch (OP(s)) {
1003 case OEND:
1004 assert(pc == stop-1);
1005 break;
1006 case OCHAR:
1007 /* only characters can match */
1008 assert(!NONCHAR(ch) || ch != OPND(s));
1009 if (ch == OPND(s))
1010 FWD(aft, bef, 1);
1011 break;
1012 case OBOL:
1013 if (ch == BOL || ch == BOLEOL)
1014 FWD(aft, bef, 1);
1015 break;
1016 case OEOL:
1017 if (ch == EOL || ch == BOLEOL)
1018 FWD(aft, bef, 1);
1019 break;
1020 case OBOW:
1021 if (ch == BOW)
1022 FWD(aft, bef, 1);
1023 break;
1024 case OEOW:
1025 if (ch == EOW)
1026 FWD(aft, bef, 1);
1027 break;
1028 case OANY:
1029 if (!NONCHAR(ch))
1030 FWD(aft, bef, 1);
1031 break;
1032 case OANYOF:
1033 cs = &g->sets[OPND(s)];
1034 if (!NONCHAR(ch) && CHIN(cs, ch))
1035 FWD(aft, bef, 1);
1036 break;
1037 case OBACK_: /* ignored here */
1038 case O_BACK:
1039 FWD(aft, aft, 1);
1040 break;
1041 case OPLUS_: /* forward, this is just an empty */
1042 FWD(aft, aft, 1);
1043 break;
1044 case O_PLUS: /* both forward and back */
1045 FWD(aft, aft, 1);
1046 i = ISSETBACK(aft, OPND(s));
1047 BACK(aft, aft, OPND(s));
1048 if (!i && ISSETBACK(aft, OPND(s))) {
1049 /* oho, must reconsider loop body */
1050 pc -= OPND(s) + 1;
1051 INIT(here, pc);
1052 }
1053 break;
1054 case OQUEST_: /* two branches, both forward */
1055 FWD(aft, aft, 1);
1056 FWD(aft, aft, OPND(s));
1057 break;
1058 case O_QUEST: /* just an empty */
1059 FWD(aft, aft, 1);
1060 break;
1061 case OLPAREN: /* not significant here */
1062 case ORPAREN:
1063 FWD(aft, aft, 1);
1064 break;
1065 case OCH_: /* mark the first two branches */
1066 FWD(aft, aft, 1);
1067 assert(OP(g->strip[pc+OPND(s)]) == OOR2);
1068 FWD(aft, aft, OPND(s));
1069 break;
1070 case OOR1: /* done a branch, find the O_CH */
1071 if (ISSTATEIN(aft, here)) {
1072 for (look = 1;
1073 OP(s = g->strip[pc+look]) != O_CH;
1074 look += OPND(s))
1075 assert(OP(s) == OOR2);
1076 FWD(aft, aft, look);
1077 }
1078 break;
1079 case OOR2: /* propagate OCH_'s marking */
1080 FWD(aft, aft, 1);
1081 if (OP(g->strip[pc+OPND(s)]) != O_CH) {
1082 assert(OP(g->strip[pc+OPND(s)]) == OOR2);
1083 FWD(aft, aft, OPND(s));
1084 }
1085 break;
1086 case O_CH: /* just empty */
1087 FWD(aft, aft, 1);
1088 break;
1089 default: /* ooooops... */
1090 assert(nope);
1091 break;
1092 }
1093 }
1094
1095 return(aft);
1096}
1097
1098#ifdef REDEBUG
1099/*
1100 - print - print a set of states
1101 == #ifdef REDEBUG
1102 == static void print(struct match *m, char *caption, states st, \
1103 == int ch, FILE *d);
1104 == #endif
1105 */
1106static void
1107print(m, caption, st, ch, d)
1108struct match *m;
1109char *caption;
1110states st;
1111int ch;
1112FILE *d;
1113{
1114 struct re_guts *g = m->g;
1115 int i;
1116 int first = 1;
1117
1118 if (!(m->eflags&REG_TRACE))
1119 return;
1120
1121 fprintf(d, "%s", caption);
1122 if (ch != '\0')
1123 fprintf(d, " %s", pchar(ch));
1124 for (i = 0; i < g->nstates; i++)
1125 if (ISSET(st, i)) {
1126 fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
1127 first = 0;
1128 }
1129 fprintf(d, "\n");
1130}
1131
1132/*
1133 - at - print current situation
1134 == #ifdef REDEBUG
1135 == static void at(struct match *m, char *title, char *start, char *stop, \
1136 == sopno startst, sopno stopst);
1137 == #endif
1138 */
1139static void
1140at(m, title, start, stop, startst, stopst)
1141struct match *m;
1142char *title;
1143char *start;
1144char *stop;
1145sopno startst;
1146sopno stopst;
1147{
1148 if (!(m->eflags&REG_TRACE))
1149 return;
1150
1151 printf("%s %s-", title, pchar(*start));
1152 printf("%s ", pchar(*stop));
1153 printf("%ld-%ld\n", (long)startst, (long)stopst);
1154}
1155
1156#ifndef PCHARDONE
1157#define PCHARDONE /* never again */
1158/*
1159 - pchar - make a character printable
1160 == #ifdef REDEBUG
1161 == static char *pchar(int ch);
1162 == #endif
1163 *
1164 * Is this identical to regchar() over in debug.c? Well, yes. But a
1165 * duplicate here avoids having a debugging-capable regexec.o tied to
1166 * a matching debug.o, and this is convenient. It all disappears in
1167 * the non-debug compilation anyway, so it doesn't matter much.
1168 */
1169static char * /* -> representation */
1170pchar(ch)
1171int ch;
1172{
1173 static char pbuf[10];
1174
1175 if (isprint((uch)ch) || ch == ' ')
1176 sprintf(pbuf, "%c", ch);
1177 else
1178 sprintf(pbuf, "\\%o", ch);
1179 return(pbuf);
1180}
1181#endif
1182#endif
1183
1184#undef matcher
1185#undef fast
1186#undef slow
1187#undef dissect
1188#undef backref
1189#undef step
1190#undef print
1191#undef at
1192#undef match
Note: See TracBrowser for help on using the repository browser.