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