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