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