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