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 #define ISBOW(m, sp) \ 593 (sp < m->endp && ISWORD(*sp) && \ 594 ((sp == m->beginp && !(m->eflags®_NOTBOL)) || \ 595 (sp > m->offp && !ISWORD(*(sp-1))))) 596 #define ISEOW(m, sp) \ 597 (((sp == m->endp && !(m->eflags®_NOTEOL)) || \ 598 (sp < m->endp && *sp == '\n' && \ 599 (m->g->cflags®_NEWLINE)) || \ 600 (sp < m->endp && !ISWORD(*sp)) ) && \ 601 (sp > m->beginp && ISWORD(*(sp-1)))) \ 602 603 /* 604 - backref - figure out what matched what, figuring in back references 605 == static const char *backref(struct match *m, const char *start, \ 606 == const char *stop, sopno startst, sopno stopst, sopno lev); 607 */ 608 static const char * /* == stop (success) or NULL (failure) */ 609 backref(struct match *m, 610 const char *start, 611 const char *stop, 612 sopno startst, 613 sopno stopst, 614 sopno lev, /* PLUS nesting level */ 615 int rec) 616 { 617 int i; 618 sopno ss; /* start sop of current subRE */ 619 const char *sp; /* start of string matched by it */ 620 sopno ssub; /* start sop of subsubRE */ 621 sopno esub; /* end sop of subsubRE */ 622 const char *ssp; /* start of string matched by subsubRE */ 623 const char *dp; 624 size_t len; 625 int hard; 626 sop s; 627 regoff_t offsave; 628 cset *cs; 629 wint_t wc; 630 631 AT("back", start, stop, startst, stopst); 632 sp = start; 633 634 /* get as far as we can with easy stuff */ 635 hard = 0; 636 for (ss = startst; !hard && ss < stopst; ss++) 637 switch (OP(s = m->g->strip[ss])) { 638 case OCHAR: 639 if (sp == stop) 640 return(NULL); 641 sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR); 642 if (wc != OPND(s)) 643 return(NULL); 644 break; 645 case OANY: 646 if (sp == stop) 647 return(NULL); 648 sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR); 649 if (wc == BADCHAR) 650 return (NULL); 651 break; 652 case OANYOF: 653 if (sp == stop) 654 return (NULL); 655 cs = &m->g->sets[OPND(s)]; 656 sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR); 657 if (wc == BADCHAR || !CHIN(cs, wc)) 658 return(NULL); 659 break; 660 case OBOL: 661 if ((sp == m->beginp && !(m->eflags®_NOTBOL)) || 662 (sp > m->offp && sp < m->endp && 663 *(sp-1) == '\n' && (m->g->cflags®_NEWLINE))) 664 { /* yes */ } 665 else 666 return(NULL); 667 break; 668 case OEOL: 669 if ( (sp == m->endp && !(m->eflags®_NOTEOL)) || 670 (sp < m->endp && *sp == '\n' && 671 (m->g->cflags®_NEWLINE)) ) 672 { /* yes */ } 673 else 674 return(NULL); 675 break; 676 case OBOW: 677 if (ISBOW(m, sp)) 678 { /* yes */ } 679 else 680 return(NULL); 681 break; 682 case OEOW: 683 if (ISEOW(m, sp)) 684 { /* yes */ } 685 else 686 return(NULL); 687 break; 688 case O_QUEST: 689 break; 690 case OOR1: /* matches null but needs to skip */ 691 ss++; 692 s = m->g->strip[ss]; 693 do { 694 assert(OP(s) == OOR2); 695 ss += OPND(s); 696 } while (OP(s = m->g->strip[ss]) != (sop)O_CH); 697 /* note that the ss++ gets us past the O_CH */ 698 break; 699 default: /* have to make a choice */ 700 hard = 1; 701 break; 702 } 703 if (!hard) { /* that was it! */ 704 if (sp != stop) 705 return(NULL); 706 return(sp); 707 } 708 ss--; /* adjust for the for's final increment */ 709 710 /* the hard stuff */ 711 AT("hard", sp, stop, ss, stopst); 712 s = m->g->strip[ss]; 713 switch (OP(s)) { 714 case OBACK_: /* the vilest depths */ 715 i = OPND(s); 716 assert(0 < i && i <= m->g->nsub); 717 if (m->pmatch[i].rm_eo == -1) 718 return(NULL); 719 assert(m->pmatch[i].rm_so != -1); 720 len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so; 721 if (len == 0 && rec++ > MAX_RECURSION) 722 return(NULL); 723 assert(stop - m->beginp >= len); 724 if (sp > stop - len) 725 return(NULL); /* not enough left to match */ 726 ssp = m->offp + m->pmatch[i].rm_so; 727 if (memcmp(sp, ssp, len) != 0) 728 return(NULL); 729 while (m->g->strip[ss] != (sop)SOP(O_BACK, i)) 730 ss++; 731 return(backref(m, sp+len, stop, ss+1, stopst, lev, rec)); 732 case OQUEST_: /* to null or not */ 733 dp = backref(m, sp, stop, ss+1, stopst, lev, rec); 734 if (dp != NULL) 735 return(dp); /* not */ 736 return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev, rec)); 737 case OPLUS_: 738 assert(m->lastpos != NULL); 739 assert(lev+1 <= m->g->nplus); 740 m->lastpos[lev+1] = sp; 741 return(backref(m, sp, stop, ss+1, stopst, lev+1, rec)); 742 case O_PLUS: 743 if (sp == m->lastpos[lev]) /* last pass matched null */ 744 return(backref(m, sp, stop, ss+1, stopst, lev-1, rec)); 745 /* try another pass */ 746 m->lastpos[lev] = sp; 747 dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev, rec); 748 if (dp == NULL) 749 return(backref(m, sp, stop, ss+1, stopst, lev-1, rec)); 750 else 751 return(dp); 752 case OCH_: /* find the right one, if any */ 753 ssub = ss + 1; 754 esub = ss + OPND(s) - 1; 755 assert(OP(m->g->strip[esub]) == OOR1); 756 for (;;) { /* find first matching branch */ 757 dp = backref(m, sp, stop, ssub, esub, lev, rec); 758 if (dp != NULL) 759 return(dp); 760 /* that one missed, try next one */ 761 if (OP(m->g->strip[esub]) == (sop)O_CH) 762 return(NULL); /* there is none */ 763 esub++; 764 assert(OP(m->g->strip[esub]) == (sop)OOR2); 765 ssub = esub + 1; 766 esub += OPND(m->g->strip[esub]); 767 if (OP(m->g->strip[esub]) == (sop)OOR2) 768 esub--; 769 else 770 assert(OP(m->g->strip[esub]) == O_CH); 771 } 772 /* NOTREACHED */ 773 break; 774 case OLPAREN: /* must undo assignment if rest fails */ 775 i = OPND(s); 776 assert(0 < i && i <= m->g->nsub); 777 offsave = m->pmatch[i].rm_so; 778 m->pmatch[i].rm_so = sp - m->offp; 779 dp = backref(m, sp, stop, ss+1, stopst, lev, rec); 780 if (dp != NULL) 781 return(dp); 782 m->pmatch[i].rm_so = offsave; 783 return(NULL); 784 case ORPAREN: /* must undo assignment if rest fails */ 785 i = OPND(s); 786 assert(0 < i && i <= m->g->nsub); 787 offsave = m->pmatch[i].rm_eo; 788 m->pmatch[i].rm_eo = sp - m->offp; 789 dp = backref(m, sp, stop, ss+1, stopst, lev, rec); 790 if (dp != NULL) 791 return(dp); 792 m->pmatch[i].rm_eo = offsave; 793 return(NULL); 794 default: /* uh oh */ 795 assert(nope); 796 break; 797 } 798 799 /* "can't happen" */ 800 assert(nope); 801 /* NOTREACHED */ 802 return "shut up gcc"; 803 } 804 805 /* 806 - walk - step through the string either quickly or slowly 807 == static const char *walk(struct match *m, const char *start, \ 808 == const char *stop, sopno startst, sopno stopst, bool fast); 809 */ 810 static const char * /* where it ended, or NULL */ 811 walk(struct match *m, const char *start, const char *stop, sopno startst, 812 sopno stopst, bool fast) 813 { 814 states st = m->st; 815 states fresh = m->fresh; 816 states empty = m->empty; 817 states tmp = m->tmp; 818 const char *p = start; 819 wint_t c; 820 wint_t lastc; /* previous c */ 821 wint_t flagch; 822 int i; 823 const char *matchp; /* last p at which a match ended */ 824 size_t clen; 825 826 AT("slow", start, stop, startst, stopst); 827 CLEAR(st); 828 SET1(st, startst); 829 SP("sstart", st, *p); 830 st = step(m->g, startst, stopst, st, NOTHING, st); 831 if (fast) 832 ASSIGN(fresh, st); 833 matchp = NULL; 834 if (start == m->offp || (start == m->beginp && !(m->eflags®_NOTBOL))) 835 c = OUT; 836 else { 837 /* 838 * XXX Wrong if the previous character was multi-byte. 839 * Newline never is (in encodings supported by FreeBSD), 840 * so this only breaks the ISWORD tests below. 841 */ 842 c = (uch)*(start - 1); 843 } 844 for (;;) { 845 /* next character */ 846 lastc = c; 847 if (p == m->endp) { 848 c = OUT; 849 clen = 0; 850 } else 851 clen = XMBRTOWC(&c, p, m->endp - p, &m->mbs, BADCHAR); 852 853 if (fast && EQ(st, fresh)) 854 matchp = p; 855 856 /* is there an EOL and/or BOL between lastc and c? */ 857 flagch = '\0'; 858 i = 0; 859 if ( (lastc == '\n' && m->g->cflags®_NEWLINE) || 860 (lastc == OUT && !(m->eflags®_NOTBOL)) ) { 861 flagch = BOL; 862 i = m->g->nbol; 863 } 864 if ( (c == '\n' && m->g->cflags®_NEWLINE) || 865 (c == OUT && !(m->eflags®_NOTEOL)) ) { 866 flagch = (flagch == BOL) ? BOLEOL : EOL; 867 i += m->g->neol; 868 } 869 if (i != 0) { 870 for (; i > 0; i--) 871 st = step(m->g, startst, stopst, st, flagch, st); 872 SP("sboleol", st, c); 873 } 874 875 /* how about a word boundary? */ 876 if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) && 877 (c != OUT && ISWORD(c)) ) { 878 flagch = BOW; 879 } 880 if ( (lastc != OUT && ISWORD(lastc)) && 881 (flagch == EOL || (c != OUT && !ISWORD(c))) ) { 882 flagch = EOW; 883 } 884 if (flagch == BOW || flagch == EOW) { 885 st = step(m->g, startst, stopst, st, flagch, st); 886 SP("sboweow", st, c); 887 } 888 889 /* are we done? */ 890 if (ISSET(st, stopst)) { 891 if (fast) 892 break; 893 else 894 matchp = p; 895 } 896 if (EQ(st, empty) || p == stop || clen > (size_t)(stop - p)) 897 break; /* NOTE BREAK OUT */ 898 899 /* no, we must deal with this character */ 900 ASSIGN(tmp, st); 901 if (fast) 902 ASSIGN(st, fresh); 903 else 904 ASSIGN(st, empty); 905 assert(c != OUT); 906 st = step(m->g, startst, stopst, tmp, c, st); 907 SP("saft", st, c); 908 assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st)); 909 p += clen; 910 } 911 912 if (fast) { 913 assert(matchp != NULL); 914 m->coldp = matchp; 915 if (ISSET(st, stopst)) 916 return (p + XMBRTOWC(NULL, p, stop - p, &m->mbs, 0)); 917 else 918 return (NULL); 919 } else 920 return (matchp); 921 } 922 923 /* 924 - step - map set of states reachable before char to set reachable after 925 == static states step(struct re_guts *g, sopno start, sopno stop, \ 926 == states bef, int ch, states aft); 927 == #define BOL (OUT-1) 928 == #define EOL (BOL-1) 929 == #define BOLEOL (BOL-2) 930 == #define NOTHING (BOL-3) 931 == #define BOW (BOL-4) 932 == #define EOW (BOL-5) 933 == #define BADCHAR (BOL-6) 934 == #define NONCHAR(c) ((c) <= OUT) 935 */ 936 static states 937 step(struct re_guts *g, 938 sopno start, /* start state within strip */ 939 sopno stop, /* state after stop state within strip */ 940 states bef, /* states reachable before */ 941 wint_t ch, /* character or NONCHAR code */ 942 states aft) /* states already known reachable after */ 943 { 944 cset *cs; 945 sop s; 946 sopno pc; 947 onestate here; /* note, macros know this name */ 948 sopno look; 949 int i; 950 951 for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) { 952 s = g->strip[pc]; 953 switch (OP(s)) { 954 case OEND: 955 assert(pc == stop-1); 956 break; 957 case OCHAR: 958 /* only characters can match */ 959 assert(!NONCHAR(ch) || ch != OPND(s)); 960 if (ch == OPND(s)) 961 FWD(aft, bef, 1); 962 break; 963 case OBOL: 964 if (ch == BOL || ch == BOLEOL) 965 FWD(aft, bef, 1); 966 break; 967 case OEOL: 968 if (ch == EOL || ch == BOLEOL) 969 FWD(aft, bef, 1); 970 break; 971 case OBOW: 972 if (ch == BOW) 973 FWD(aft, bef, 1); 974 break; 975 case OEOW: 976 if (ch == EOW) 977 FWD(aft, bef, 1); 978 break; 979 case OANY: 980 if (!NONCHAR(ch)) 981 FWD(aft, bef, 1); 982 break; 983 case OANYOF: 984 cs = &g->sets[OPND(s)]; 985 if (!NONCHAR(ch) && CHIN(cs, ch)) 986 FWD(aft, bef, 1); 987 break; 988 case OBACK_: /* ignored here */ 989 case O_BACK: 990 FWD(aft, aft, 1); 991 break; 992 case OPLUS_: /* forward, this is just an empty */ 993 FWD(aft, aft, 1); 994 break; 995 case O_PLUS: /* both forward and back */ 996 FWD(aft, aft, 1); 997 i = ISSETBACK(aft, OPND(s)); 998 BACK(aft, aft, OPND(s)); 999 if (!i && ISSETBACK(aft, OPND(s))) { 1000 /* oho, must reconsider loop body */ 1001 pc -= OPND(s) + 1; 1002 INIT(here, pc); 1003 } 1004 break; 1005 case OQUEST_: /* two branches, both forward */ 1006 FWD(aft, aft, 1); 1007 FWD(aft, aft, OPND(s)); 1008 break; 1009 case O_QUEST: /* just an empty */ 1010 FWD(aft, aft, 1); 1011 break; 1012 case OLPAREN: /* not significant here */ 1013 case ORPAREN: 1014 FWD(aft, aft, 1); 1015 break; 1016 case OCH_: /* mark the first two branches */ 1017 FWD(aft, aft, 1); 1018 assert(OP(g->strip[pc+OPND(s)]) == (sop)OOR2); 1019 FWD(aft, aft, OPND(s)); 1020 break; 1021 case OOR1: /* done a branch, find the O_CH */ 1022 if (ISSTATEIN(aft, here)) { 1023 for (look = 1; 1024 OP(s = g->strip[pc+look]) != (sop)O_CH; 1025 look += OPND(s)) 1026 assert(OP(s) == (sop)OOR2); 1027 FWD(aft, aft, look + 1); 1028 } 1029 break; 1030 case OOR2: /* propagate OCH_'s marking */ 1031 FWD(aft, aft, 1); 1032 if (OP(g->strip[pc+OPND(s)]) != (sop)O_CH) { 1033 assert(OP(g->strip[pc+OPND(s)]) == (sop)OOR2); 1034 FWD(aft, aft, OPND(s)); 1035 } 1036 break; 1037 case O_CH: /* just empty */ 1038 FWD(aft, aft, 1); 1039 break; 1040 default: /* ooooops... */ 1041 assert(nope); 1042 break; 1043 } 1044 } 1045 1046 return(aft); 1047 } 1048 1049 #ifdef REDEBUG 1050 /* 1051 - print - print a set of states 1052 == #ifdef REDEBUG 1053 == static void print(struct match *m, const char *caption, states st, \ 1054 == int ch, FILE *d); 1055 == #endif 1056 */ 1057 static void 1058 print(struct match *m, 1059 const char *caption, 1060 states st, 1061 int ch, 1062 FILE *d) 1063 { 1064 struct re_guts *g = m->g; 1065 sopno i; 1066 int first = 1; 1067 1068 if (!(m->eflags®_TRACE)) 1069 return; 1070 1071 fprintf(d, "%s", caption); 1072 if (ch != '\0') 1073 fprintf(d, " %s", pchar(ch)); 1074 for (i = 0; i < g->nstates; i++) 1075 if (ISSET(st, i)) { 1076 fprintf(d, "%s%lu", (first) ? "\t" : ", ", i); 1077 first = 0; 1078 } 1079 fprintf(d, "\n"); 1080 } 1081 1082 /* 1083 - at - print current situation 1084 == #ifdef REDEBUG 1085 == static void at(struct match *m, const char *title, const char *start, \ 1086 == const char *stop, sopno startst, sopno stopst); 1087 == #endif 1088 */ 1089 static void 1090 at( struct match *m, 1091 const char *title, 1092 const char *start, 1093 const char *stop, 1094 sopno startst, 1095 sopno stopst) 1096 { 1097 if (!(m->eflags®_TRACE)) 1098 return; 1099 1100 printf("%s %s-", title, pchar(*start)); 1101 printf("%s ", pchar(*stop)); 1102 printf("%ld-%ld\n", (long)startst, (long)stopst); 1103 } 1104 1105 #ifndef PCHARDONE 1106 #define PCHARDONE /* never again */ 1107 /* 1108 - pchar - make a character printable 1109 == #ifdef REDEBUG 1110 == static const char *pchar(int ch); 1111 == #endif 1112 * 1113 * Is this identical to regchar() over in debug.c? Well, yes. But a 1114 * duplicate here avoids having a debugging-capable regexec.o tied to 1115 * a matching debug.o, and this is convenient. It all disappears in 1116 * the non-debug compilation anyway, so it doesn't matter much. 1117 */ 1118 static const char * /* -> representation */ 1119 pchar(int ch) 1120 { 1121 static char pbuf[10]; 1122 1123 if (isprint((uch)ch) || ch == ' ') 1124 sprintf(pbuf, "%c", ch); 1125 else 1126 sprintf(pbuf, "\\%o", ch); 1127 return(pbuf); 1128 } 1129 #endif 1130 #endif 1131 1132 #undef stepback 1133 #undef matcher 1134 #undef walk 1135 #undef dissect 1136 #undef backref 1137 #undef step 1138 #undef print 1139 #undef at 1140 #undef match 1141