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