engine.c revision 1.1.1.1
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 /* 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 */ 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 */ 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) */ 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 */ 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 */ 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 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 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 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 */ 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
Indexes created Sat Sep 20 22:09:52 GMT 2025