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