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 * Copyright (c) 2011 The FreeBSD Foundation 9 * 10 * Portions of this software were developed by David Chisnall 11 * under sponsorship from the FreeBSD Foundation. 12 * 13 * This code is derived from software contributed to Berkeley by 14 * Henry Spencer. 15 * 16 * Redistribution and use in source and binary forms, with or without 17 * modification, are permitted provided that the following conditions 18 * are met: 19 * 1. Redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer. 21 * 2. Redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution. 24 * 3. Neither the name of the University nor the names of its contributors 25 * may be used to endorse or promote products derived from this software 26 * without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 31 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 38 * SUCH DAMAGE. 39 */ 40 41 #include <sys/types.h> 42 #include <stdio.h> 43 #include <string.h> 44 #include <ctype.h> 45 #include <limits.h> 46 #include <stdlib.h> 47 #include <regex.h> 48 #include <stdbool.h> 49 #include <wchar.h> 50 #include <wctype.h> 51 52 #ifndef LIBREGEX 53 #include "collate.h" 54 #endif 55 56 #include "utils.h" 57 #include "regex2.h" 58 59 #include "cname.h" 60 61 /* 62 * Branching context, used to keep track of branch state for all of the branch- 63 * aware functions. In addition to keeping track of branch positions for the 64 * p_branch_* functions, we use this to simplify some clumsiness in BREs for 65 * detection of whether ^ is acting as an anchor or being used erroneously and 66 * also for whether we're in a sub-expression or not. 67 */ 68 struct branchc { 69 sopno start; 70 sopno back; 71 sopno fwd; 72 73 int nbranch; 74 int nchain; 75 bool outer; 76 bool terminate; 77 }; 78 79 /* 80 * parse structure, passed up and down to avoid global variables and 81 * other clumsinesses 82 */ 83 struct parse { 84 const char *next; /* next character in RE */ 85 const char *end; /* end of string (-> NUL normally) */ 86 int error; /* has an error been seen? */ 87 int gnuext; 88 sop *strip; /* malloced strip */ 89 sopno ssize; /* malloced strip size (allocated) */ 90 sopno slen; /* malloced strip length (used) */ 91 int ncsalloc; /* number of csets allocated */ 92 struct re_guts *g; 93 # define NPAREN 10 /* we need to remember () 1-9 for back refs */ 94 sopno pbegin[NPAREN]; /* -> ( ([0] unused) */ 95 sopno pend[NPAREN]; /* -> ) ([0] unused) */ 96 bool allowbranch; /* can this expression branch? */ 97 bool bre; /* convenience; is this a BRE? */ 98 int pflags; /* other parsing flags -- legacy escapes? */ 99 bool (*parse_expr)(struct parse *, struct branchc *); 100 void (*pre_parse)(struct parse *, struct branchc *); 101 void (*post_parse)(struct parse *, struct branchc *); 102 }; 103 104 #define PFLAG_LEGACY_ESC 0x00000001 105 106 /* ========= begin header generated by ./mkh ========= */ 107 #ifdef __cplusplus 108 extern "C" { 109 #endif 110 111 /* === regcomp.c === */ 112 static bool p_ere_exp(struct parse *p, struct branchc *bc); 113 static void p_str(struct parse *p); 114 static int p_branch_eat_delim(struct parse *p, struct branchc *bc); 115 static void p_branch_ins_offset(struct parse *p, struct branchc *bc); 116 static void p_branch_fix_tail(struct parse *p, struct branchc *bc); 117 static bool p_branch_empty(struct parse *p, struct branchc *bc); 118 static bool p_branch_do(struct parse *p, struct branchc *bc); 119 static void p_bre_pre_parse(struct parse *p, struct branchc *bc); 120 static void p_bre_post_parse(struct parse *p, struct branchc *bc); 121 static void p_re(struct parse *p, int end1, int end2); 122 static bool p_simp_re(struct parse *p, struct branchc *bc); 123 static int p_count(struct parse *p); 124 static void p_bracket(struct parse *p); 125 static int p_range_cmp(wchar_t c1, wchar_t c2); 126 static void p_b_term(struct parse *p, cset *cs); 127 static int p_b_pseudoclass(struct parse *p, char c); 128 static void p_b_cclass(struct parse *p, cset *cs); 129 static void p_b_cclass_named(struct parse *p, cset *cs, const char[]); 130 static void p_b_eclass(struct parse *p, cset *cs); 131 static wint_t p_b_symbol(struct parse *p); 132 static wint_t p_b_coll_elem(struct parse *p, wint_t endc); 133 static bool may_escape(struct parse *p, const wint_t ch); 134 static wint_t othercase(wint_t ch); 135 static void bothcases(struct parse *p, wint_t ch); 136 static void ordinary(struct parse *p, wint_t ch); 137 static void nonnewline(struct parse *p); 138 static void repeat(struct parse *p, sopno start, int from, int to); 139 static int seterr(struct parse *p, int e); 140 static cset *allocset(struct parse *p); 141 static void freeset(struct parse *p, cset *cs); 142 static void CHadd(struct parse *p, cset *cs, wint_t ch); 143 static void CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max); 144 static void CHaddtype(struct parse *p, cset *cs, wctype_t wct); 145 static wint_t singleton(cset *cs); 146 static sopno dupl(struct parse *p, sopno start, sopno finish); 147 static void doemit(struct parse *p, sop op, size_t opnd); 148 static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos); 149 static void dofwd(struct parse *p, sopno pos, sop value); 150 static int enlarge(struct parse *p, sopno size); 151 static void stripsnug(struct parse *p, struct re_guts *g); 152 static void findmust(struct parse *p, struct re_guts *g); 153 static int altoffset(sop *scan, int offset); 154 static void computejumps(struct parse *p, struct re_guts *g); 155 static void computematchjumps(struct parse *p, struct re_guts *g); 156 static sopno pluscount(struct parse *p, struct re_guts *g); 157 static wint_t wgetnext(struct parse *p); 158 159 #ifdef __cplusplus 160 } 161 #endif 162 /* ========= end header generated by ./mkh ========= */ 163 164 static char nuls[10]; /* place to point scanner in event of error */ 165 166 /* 167 * macros for use with parse structure 168 * BEWARE: these know that the parse structure is named `p' !!! 169 */ 170 #define PEEK() (*p->next) 171 #define PEEK2() (*(p->next+1)) 172 #define MORE() (p->end - p->next > 0) 173 #define MORE2() (p->end - p->next > 1) 174 #define SEE(c) (MORE() && PEEK() == (c)) 175 #define SEETWO(a, b) (MORE2() && PEEK() == (a) && PEEK2() == (b)) 176 #define SEESPEC(a) (p->bre ? SEETWO('\\', a) : SEE(a)) 177 #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0) 178 #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0) 179 #define EATSPEC(a) (p->bre ? EATTWO('\\', a) : EAT(a)) 180 #define NEXT() (p->next++) 181 #define NEXT2() (p->next += 2) 182 #define NEXTn(n) (p->next += (n)) 183 #define GETNEXT() (*p->next++) 184 #define WGETNEXT() wgetnext(p) 185 #define SETERROR(e) seterr(p, (e)) 186 #define REQUIRE(co, e) ((co) || SETERROR(e)) 187 #define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e)) 188 #define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e)) 189 #define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e)) 190 #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd)) 191 #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos) 192 #define AHEAD(pos) dofwd(p, pos, HERE()-(pos)) 193 #define ASTERN(sop, pos) EMIT(sop, HERE()-pos) 194 #define HERE() (p->slen) 195 #define THERE() (p->slen - 1) 196 #define THERETHERE() (p->slen - 2) 197 #define DROP(n) (p->slen -= (n)) 198 199 /* Macro used by computejump()/computematchjump() */ 200 #define MIN(a,b) ((a)<(b)?(a):(b)) 201 202 static int /* 0 success, otherwise REG_something */ 203 regcomp_internal(regex_t * __restrict preg, 204 const char * __restrict pattern, 205 int cflags, int pflags) 206 { 207 struct parse pa; 208 struct re_guts *g; 209 struct parse *p = &pa; 210 int i; 211 size_t len; 212 size_t maxlen; 213 #ifdef REDEBUG 214 # define GOODFLAGS(f) (f) 215 #else 216 # define GOODFLAGS(f) ((f)&~REG_DUMP) 217 #endif 218 219 cflags = GOODFLAGS(cflags); 220 if ((cflags®_EXTENDED) && (cflags®_NOSPEC)) 221 return(REG_INVARG); 222 223 if (cflags®_PEND) { 224 if (preg->re_endp < pattern) 225 return(REG_INVARG); 226 len = preg->re_endp - pattern; 227 } else 228 len = strlen(pattern); 229 230 /* do the mallocs early so failure handling is easy */ 231 g = (struct re_guts *)malloc(sizeof(struct re_guts)); 232 if (g == NULL) 233 return(REG_ESPACE); 234 /* 235 * Limit the pattern space to avoid a 32-bit overflow on buffer 236 * extension. Also avoid any signed overflow in case of conversion 237 * so make the real limit based on a 31-bit overflow. 238 * 239 * Likely not applicable on 64-bit systems but handle the case 240 * generically (who are we to stop people from using ~715MB+ 241 * patterns?). 242 */ 243 maxlen = ((size_t)-1 >> 1) / sizeof(sop) * 2 / 3; 244 if (len >= maxlen) { 245 free((char *)g); 246 return(REG_ESPACE); 247 } 248 p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */ 249 assert(p->ssize >= len); 250 251 p->strip = (sop *)malloc(p->ssize * sizeof(sop)); 252 p->slen = 0; 253 if (p->strip == NULL) { 254 free((char *)g); 255 return(REG_ESPACE); 256 } 257 258 /* set things up */ 259 p->g = g; 260 p->next = pattern; /* convenience; we do not modify it */ 261 p->end = p->next + len; 262 p->error = 0; 263 p->ncsalloc = 0; 264 p->pflags = pflags; 265 for (i = 0; i < NPAREN; i++) { 266 p->pbegin[i] = 0; 267 p->pend[i] = 0; 268 } 269 #ifdef LIBREGEX 270 if (cflags®_POSIX) { 271 p->gnuext = false; 272 p->allowbranch = (cflags & REG_EXTENDED) != 0; 273 } else 274 p->gnuext = p->allowbranch = true; 275 #else 276 p->gnuext = false; 277 p->allowbranch = (cflags & REG_EXTENDED) != 0; 278 #endif 279 if (cflags & REG_EXTENDED) { 280 p->bre = false; 281 p->parse_expr = p_ere_exp; 282 p->pre_parse = NULL; 283 p->post_parse = NULL; 284 } else { 285 p->bre = true; 286 p->parse_expr = p_simp_re; 287 p->pre_parse = p_bre_pre_parse; 288 p->post_parse = p_bre_post_parse; 289 } 290 g->sets = NULL; 291 g->ncsets = 0; 292 g->cflags = cflags; 293 g->iflags = 0; 294 g->nbol = 0; 295 g->neol = 0; 296 g->must = NULL; 297 g->moffset = -1; 298 g->charjump = NULL; 299 g->matchjump = NULL; 300 g->mlen = 0; 301 g->nsub = 0; 302 g->backrefs = 0; 303 304 /* do it */ 305 EMIT(OEND, 0); 306 g->firststate = THERE(); 307 if (cflags & REG_NOSPEC) 308 p_str(p); 309 else 310 p_re(p, OUT, OUT); 311 EMIT(OEND, 0); 312 g->laststate = THERE(); 313 314 /* tidy up loose ends and fill things in */ 315 stripsnug(p, g); 316 findmust(p, g); 317 /* only use Boyer-Moore algorithm if the pattern is bigger 318 * than three characters 319 */ 320 if(g->mlen > 3) { 321 computejumps(p, g); 322 computematchjumps(p, g); 323 if(g->matchjump == NULL && g->charjump != NULL) { 324 free(g->charjump); 325 g->charjump = NULL; 326 } 327 } 328 g->nplus = pluscount(p, g); 329 g->magic = MAGIC2; 330 preg->re_nsub = g->nsub; 331 preg->re_g = g; 332 preg->re_magic = MAGIC1; 333 #ifndef REDEBUG 334 /* not debugging, so can't rely on the assert() in regexec() */ 335 if (g->iflags&BAD) 336 SETERROR(REG_ASSERT); 337 #endif 338 339 /* win or lose, we're done */ 340 if (p->error != 0) /* lose */ 341 regfree(preg); 342 return(p->error); 343 } 344 345 /* 346 - regcomp - interface for parser and compilation 347 = extern int regcomp(regex_t *, const char *, int); 348 = #define REG_BASIC 0000 349 = #define REG_EXTENDED 0001 350 = #define REG_ICASE 0002 351 = #define REG_NOSUB 0004 352 = #define REG_NEWLINE 0010 353 = #define REG_NOSPEC 0020 354 = #define REG_PEND 0040 355 = #define REG_DUMP 0200 356 */ 357 int /* 0 success, otherwise REG_something */ 358 regcomp(regex_t * __restrict preg, 359 const char * __restrict pattern, 360 int cflags) 361 { 362 363 return (regcomp_internal(preg, pattern, cflags, 0)); 364 } 365 366 #ifndef LIBREGEX 367 /* 368 * Legacy interface that requires more lax escaping behavior. 369 */ 370 int 371 freebsd12_regcomp(regex_t * __restrict preg, 372 const char * __restrict pattern, 373 int cflags, int pflags) 374 { 375 376 return (regcomp_internal(preg, pattern, cflags, PFLAG_LEGACY_ESC)); 377 } 378 379 __sym_compat(regcomp, freebsd12_regcomp, FBSD_1.0); 380 #endif /* !LIBREGEX */ 381 382 /* 383 - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op, 384 - return whether we should terminate or not 385 == static bool p_ere_exp(struct parse *p); 386 */ 387 static bool 388 p_ere_exp(struct parse *p, struct branchc *bc) 389 { 390 char c; 391 wint_t wc; 392 sopno pos; 393 int count; 394 int count2; 395 #ifdef LIBREGEX 396 int i; 397 int handled; 398 #endif 399 sopno subno; 400 int wascaret = 0; 401 402 (void)bc; 403 assert(MORE()); /* caller should have ensured this */ 404 c = GETNEXT(); 405 406 #ifdef LIBREGEX 407 handled = 0; 408 #endif 409 pos = HERE(); 410 switch (c) { 411 case '(': 412 (void)REQUIRE(MORE(), REG_EPAREN); 413 p->g->nsub++; 414 subno = p->g->nsub; 415 if (subno < NPAREN) 416 p->pbegin[subno] = HERE(); 417 EMIT(OLPAREN, subno); 418 if (!SEE(')')) 419 p_re(p, ')', IGN); 420 if (subno < NPAREN) { 421 p->pend[subno] = HERE(); 422 assert(p->pend[subno] != 0); 423 } 424 EMIT(ORPAREN, subno); 425 (void)MUSTEAT(')', REG_EPAREN); 426 break; 427 #ifndef POSIX_MISTAKE 428 case ')': /* happens only if no current unmatched ( */ 429 /* 430 * You may ask, why the ifndef? Because I didn't notice 431 * this until slightly too late for 1003.2, and none of the 432 * other 1003.2 regular-expression reviewers noticed it at 433 * all. So an unmatched ) is legal POSIX, at least until 434 * we can get it fixed. 435 */ 436 SETERROR(REG_EPAREN); 437 break; 438 #endif 439 case '^': 440 EMIT(OBOL, 0); 441 p->g->iflags |= USEBOL; 442 p->g->nbol++; 443 wascaret = 1; 444 break; 445 case '$': 446 EMIT(OEOL, 0); 447 p->g->iflags |= USEEOL; 448 p->g->neol++; 449 break; 450 case '|': 451 SETERROR(REG_EMPTY); 452 break; 453 case '*': 454 case '+': 455 case '?': 456 case '{': 457 SETERROR(REG_BADRPT); 458 break; 459 case '.': 460 if (p->g->cflags®_NEWLINE) 461 nonnewline(p); 462 else 463 EMIT(OANY, 0); 464 break; 465 case '[': 466 p_bracket(p); 467 break; 468 case '\\': 469 (void)REQUIRE(MORE(), REG_EESCAPE); 470 wc = WGETNEXT(); 471 #ifdef LIBREGEX 472 if (p->gnuext) { 473 handled = 1; 474 switch (wc) { 475 case '`': 476 EMIT(OBOS, 0); 477 break; 478 case '\'': 479 EMIT(OEOS, 0); 480 break; 481 case 'B': 482 EMIT(ONWBND, 0); 483 break; 484 case 'b': 485 EMIT(OWBND, 0); 486 break; 487 case 'W': 488 case 'w': 489 case 'S': 490 case 's': 491 p_b_pseudoclass(p, wc); 492 break; 493 case '1': 494 case '2': 495 case '3': 496 case '4': 497 case '5': 498 case '6': 499 case '7': 500 case '8': 501 case '9': 502 i = wc - '0'; 503 assert(i < NPAREN); 504 if (p->pend[i] != 0) { 505 assert(i <= p->g->nsub); 506 EMIT(OBACK_, i); 507 assert(p->pbegin[i] != 0); 508 assert(OP(p->strip[p->pbegin[i]]) == OLPAREN); 509 assert(OP(p->strip[p->pend[i]]) == ORPAREN); 510 (void) dupl(p, p->pbegin[i]+1, p->pend[i]); 511 EMIT(O_BACK, i); 512 } else 513 SETERROR(REG_ESUBREG); 514 p->g->backrefs = 1; 515 break; 516 default: 517 handled = 0; 518 } 519 /* Don't proceed to the POSIX bits if we've already handled it */ 520 if (handled) 521 break; 522 } 523 #endif 524 switch (wc) { 525 case '<': 526 EMIT(OBOW, 0); 527 break; 528 case '>': 529 EMIT(OEOW, 0); 530 break; 531 default: 532 if (may_escape(p, wc)) 533 ordinary(p, wc); 534 else 535 SETERROR(REG_EESCAPE); 536 break; 537 } 538 break; 539 default: 540 if (p->error != 0) 541 return (false); 542 p->next--; 543 wc = WGETNEXT(); 544 ordinary(p, wc); 545 break; 546 } 547 548 if (!MORE()) 549 return (false); 550 c = PEEK(); 551 /* we call { a repetition if followed by a digit */ 552 if (!( c == '*' || c == '+' || c == '?' || c == '{')) 553 return (false); /* no repetition, we're done */ 554 else if (c == '{') 555 (void)REQUIRE(MORE2() && \ 556 (isdigit((uch)PEEK2()) || PEEK2() == ','), REG_BADRPT); 557 NEXT(); 558 559 (void)REQUIRE(!wascaret, REG_BADRPT); 560 switch (c) { 561 case '*': /* implemented as +? */ 562 /* this case does not require the (y|) trick, noKLUDGE */ 563 INSERT(OPLUS_, pos); 564 ASTERN(O_PLUS, pos); 565 INSERT(OQUEST_, pos); 566 ASTERN(O_QUEST, pos); 567 break; 568 case '+': 569 INSERT(OPLUS_, pos); 570 ASTERN(O_PLUS, pos); 571 break; 572 case '?': 573 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 574 INSERT(OCH_, pos); /* offset slightly wrong */ 575 ASTERN(OOR1, pos); /* this one's right */ 576 AHEAD(pos); /* fix the OCH_ */ 577 EMIT(OOR2, 0); /* offset very wrong... */ 578 AHEAD(THERE()); /* ...so fix it */ 579 ASTERN(O_CH, THERETHERE()); 580 break; 581 case '{': 582 count = p_count(p); 583 if (EAT(',')) { 584 if (isdigit((uch)PEEK())) { 585 count2 = p_count(p); 586 (void)REQUIRE(count <= count2, REG_BADBR); 587 } else /* single number with comma */ 588 count2 = INFINITY; 589 } else /* just a single number */ 590 count2 = count; 591 repeat(p, pos, count, count2); 592 if (!EAT('}')) { /* error heuristics */ 593 while (MORE() && PEEK() != '}') 594 NEXT(); 595 (void)REQUIRE(MORE(), REG_EBRACE); 596 SETERROR(REG_BADBR); 597 } 598 break; 599 } 600 601 if (!MORE()) 602 return (false); 603 c = PEEK(); 604 if (!( c == '*' || c == '+' || c == '?' || 605 (c == '{' && MORE2() && isdigit((uch)PEEK2())) ) ) 606 return (false); 607 SETERROR(REG_BADRPT); 608 return (false); 609 } 610 611 /* 612 - p_str - string (no metacharacters) "parser" 613 == static void p_str(struct parse *p); 614 */ 615 static void 616 p_str(struct parse *p) 617 { 618 (void)REQUIRE(MORE(), REG_EMPTY); 619 while (MORE()) 620 ordinary(p, WGETNEXT()); 621 } 622 623 /* 624 * Eat consecutive branch delimiters for the kind of expression that we are 625 * parsing, return the number of delimiters that we ate. 626 */ 627 static int 628 p_branch_eat_delim(struct parse *p, struct branchc *bc) 629 { 630 int nskip; 631 632 (void)bc; 633 nskip = 0; 634 while (EATSPEC('|')) 635 ++nskip; 636 return (nskip); 637 } 638 639 /* 640 * Insert necessary branch book-keeping operations. This emits a 641 * bogus 'next' offset, since we still have more to parse 642 */ 643 static void 644 p_branch_ins_offset(struct parse *p, struct branchc *bc) 645 { 646 647 if (bc->nbranch == 0) { 648 INSERT(OCH_, bc->start); /* offset is wrong */ 649 bc->fwd = bc->start; 650 bc->back = bc->start; 651 } 652 653 ASTERN(OOR1, bc->back); 654 bc->back = THERE(); 655 AHEAD(bc->fwd); /* fix previous offset */ 656 bc->fwd = HERE(); 657 EMIT(OOR2, 0); /* offset is very wrong */ 658 ++bc->nbranch; 659 } 660 661 /* 662 * Fix the offset of the tail branch, if we actually had any branches. 663 * This is to correct the bogus placeholder offset that we use. 664 */ 665 static void 666 p_branch_fix_tail(struct parse *p, struct branchc *bc) 667 { 668 669 /* Fix bogus offset at the tail if we actually have branches */ 670 if (bc->nbranch > 0) { 671 AHEAD(bc->fwd); 672 ASTERN(O_CH, bc->back); 673 } 674 } 675 676 /* 677 * Signal to the parser that an empty branch has been encountered; this will, 678 * in the future, be used to allow for more permissive behavior with empty 679 * branches. The return value should indicate whether parsing may continue 680 * or not. 681 */ 682 static bool 683 p_branch_empty(struct parse *p, struct branchc *bc) 684 { 685 686 (void)bc; 687 SETERROR(REG_EMPTY); 688 return (false); 689 } 690 691 /* 692 * Take care of any branching requirements. This includes inserting the 693 * appropriate branching instructions as well as eating all of the branch 694 * delimiters until we either run out of pattern or need to parse more pattern. 695 */ 696 static bool 697 p_branch_do(struct parse *p, struct branchc *bc) 698 { 699 int ate = 0; 700 701 ate = p_branch_eat_delim(p, bc); 702 if (ate == 0) 703 return (false); 704 else if ((ate > 1 || (bc->outer && !MORE())) && !p_branch_empty(p, bc)) 705 /* 706 * Halt parsing only if we have an empty branch and p_branch_empty 707 * indicates that we must not continue. In the future, this will not 708 * necessarily be an error. 709 */ 710 return (false); 711 p_branch_ins_offset(p, bc); 712 713 return (true); 714 } 715 716 static void 717 p_bre_pre_parse(struct parse *p, struct branchc *bc) 718 { 719 720 (void) bc; 721 /* 722 * Does not move cleanly into expression parser because of 723 * ordinary interpration of * at the beginning position of 724 * an expression. 725 */ 726 if (EAT('^')) { 727 EMIT(OBOL, 0); 728 p->g->iflags |= USEBOL; 729 p->g->nbol++; 730 } 731 } 732 733 static void 734 p_bre_post_parse(struct parse *p, struct branchc *bc) 735 { 736 737 /* Expression is terminating due to EOL token */ 738 if (bc->terminate) { 739 DROP(1); 740 EMIT(OEOL, 0); 741 p->g->iflags |= USEEOL; 742 p->g->neol++; 743 } 744 } 745 746 /* 747 - p_re - Top level parser, concatenation and BRE anchoring 748 == static void p_re(struct parse *p, int end1, int end2); 749 * Giving end1 as OUT essentially eliminates the end1/end2 check. 750 * 751 * This implementation is a bit of a kludge, in that a trailing $ is first 752 * taken as an ordinary character and then revised to be an anchor. 753 * The amount of lookahead needed to avoid this kludge is excessive. 754 */ 755 static void 756 p_re(struct parse *p, 757 int end1, /* first terminating character */ 758 int end2) /* second terminating character; ignored for EREs */ 759 { 760 struct branchc bc; 761 762 bc.nbranch = 0; 763 if (end1 == OUT && end2 == OUT) 764 bc.outer = true; 765 else 766 bc.outer = false; 767 #define SEEEND() (!p->bre ? SEE(end1) : SEETWO(end1, end2)) 768 for (;;) { 769 bc.start = HERE(); 770 bc.nchain = 0; 771 bc.terminate = false; 772 if (p->pre_parse != NULL) 773 p->pre_parse(p, &bc); 774 while (MORE() && (!p->allowbranch || !SEESPEC('|')) && !SEEEND()) { 775 bc.terminate = p->parse_expr(p, &bc); 776 ++bc.nchain; 777 } 778 if (p->post_parse != NULL) 779 p->post_parse(p, &bc); 780 (void) REQUIRE(p->gnuext || HERE() != bc.start, REG_EMPTY); 781 #ifdef LIBREGEX 782 if (HERE() == bc.start && !p_branch_empty(p, &bc)) 783 break; 784 #endif 785 if (!p->allowbranch) 786 break; 787 /* 788 * p_branch_do's return value indicates whether we should 789 * continue parsing or not. This is both for correctness and 790 * a slight optimization, because it will check if we've 791 * encountered an empty branch or the end of the string 792 * immediately following a branch delimiter. 793 */ 794 if (!p_branch_do(p, &bc)) 795 break; 796 } 797 #undef SEE_END 798 if (p->allowbranch) 799 p_branch_fix_tail(p, &bc); 800 assert(!MORE() || SEE(end1)); 801 } 802 803 /* 804 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition 805 == static bool p_simp_re(struct parse *p, struct branchc *bc); 806 */ 807 static bool /* was the simple RE an unbackslashed $? */ 808 p_simp_re(struct parse *p, struct branchc *bc) 809 { 810 int c; 811 int cc; /* convenient/control character */ 812 int count; 813 int count2; 814 sopno pos; 815 bool handled; 816 int i; 817 wint_t wc; 818 sopno subno; 819 # define BACKSL (1<<CHAR_BIT) 820 821 pos = HERE(); /* repetition op, if any, covers from here */ 822 handled = false; 823 824 assert(MORE()); /* caller should have ensured this */ 825 c = (uch)GETNEXT(); 826 if (c == '\\') { 827 (void)REQUIRE(MORE(), REG_EESCAPE); 828 cc = (uch)GETNEXT(); 829 c = BACKSL | cc; 830 #ifdef LIBREGEX 831 if (p->gnuext) { 832 handled = true; 833 switch (c) { 834 case BACKSL|'`': 835 EMIT(OBOS, 0); 836 break; 837 case BACKSL|'\'': 838 EMIT(OEOS, 0); 839 break; 840 case BACKSL|'B': 841 EMIT(ONWBND, 0); 842 break; 843 case BACKSL|'b': 844 EMIT(OWBND, 0); 845 break; 846 case BACKSL|'W': 847 case BACKSL|'w': 848 case BACKSL|'S': 849 case BACKSL|'s': 850 p_b_pseudoclass(p, cc); 851 break; 852 default: 853 handled = false; 854 } 855 } 856 #endif 857 } 858 if (!handled) { 859 switch (c) { 860 case '.': 861 if (p->g->cflags®_NEWLINE) 862 nonnewline(p); 863 else 864 EMIT(OANY, 0); 865 break; 866 case '[': 867 p_bracket(p); 868 break; 869 case BACKSL|'<': 870 EMIT(OBOW, 0); 871 break; 872 case BACKSL|'>': 873 EMIT(OEOW, 0); 874 break; 875 case BACKSL|'{': 876 SETERROR(REG_BADRPT); 877 break; 878 case BACKSL|'(': 879 p->g->nsub++; 880 subno = p->g->nsub; 881 if (subno < NPAREN) 882 p->pbegin[subno] = HERE(); 883 EMIT(OLPAREN, subno); 884 /* the MORE here is an error heuristic */ 885 if (MORE() && !SEETWO('\\', ')')) 886 p_re(p, '\\', ')'); 887 if (subno < NPAREN) { 888 p->pend[subno] = HERE(); 889 assert(p->pend[subno] != 0); 890 } 891 EMIT(ORPAREN, subno); 892 (void)REQUIRE(EATTWO('\\', ')'), REG_EPAREN); 893 break; 894 case BACKSL|')': /* should not get here -- must be user */ 895 SETERROR(REG_EPAREN); 896 break; 897 case BACKSL|'1': 898 case BACKSL|'2': 899 case BACKSL|'3': 900 case BACKSL|'4': 901 case BACKSL|'5': 902 case BACKSL|'6': 903 case BACKSL|'7': 904 case BACKSL|'8': 905 case BACKSL|'9': 906 i = (c&~BACKSL) - '0'; 907 assert(i < NPAREN); 908 if (p->pend[i] != 0) { 909 assert(i <= p->g->nsub); 910 EMIT(OBACK_, i); 911 assert(p->pbegin[i] != 0); 912 assert(OP(p->strip[p->pbegin[i]]) == OLPAREN); 913 assert(OP(p->strip[p->pend[i]]) == ORPAREN); 914 (void) dupl(p, p->pbegin[i]+1, p->pend[i]); 915 EMIT(O_BACK, i); 916 } else 917 SETERROR(REG_ESUBREG); 918 p->g->backrefs = 1; 919 break; 920 case '*': 921 /* 922 * Ordinary if used as the first character beyond BOL anchor of 923 * a (sub-)expression, counts as a bad repetition operator if it 924 * appears otherwise. 925 */ 926 (void)REQUIRE(bc->nchain == 0, REG_BADRPT); 927 /* FALLTHROUGH */ 928 default: 929 if (p->error != 0) 930 return (false); /* Definitely not $... */ 931 p->next--; 932 wc = WGETNEXT(); 933 if ((c & BACKSL) == 0 || may_escape(p, wc)) 934 ordinary(p, wc); 935 else 936 SETERROR(REG_EESCAPE); 937 break; 938 } 939 } 940 941 if (EAT('*')) { /* implemented as +? */ 942 /* this case does not require the (y|) trick, noKLUDGE */ 943 INSERT(OPLUS_, pos); 944 ASTERN(O_PLUS, pos); 945 INSERT(OQUEST_, pos); 946 ASTERN(O_QUEST, pos); 947 #ifdef LIBREGEX 948 } else if (p->gnuext && EATTWO('\\', '?')) { 949 INSERT(OQUEST_, pos); 950 ASTERN(O_QUEST, pos); 951 } else if (p->gnuext && EATTWO('\\', '+')) { 952 INSERT(OPLUS_, pos); 953 ASTERN(O_PLUS, pos); 954 #endif 955 } else if (EATTWO('\\', '{')) { 956 count = p_count(p); 957 if (EAT(',')) { 958 if (MORE() && isdigit((uch)PEEK())) { 959 count2 = p_count(p); 960 (void)REQUIRE(count <= count2, REG_BADBR); 961 } else /* single number with comma */ 962 count2 = INFINITY; 963 } else /* just a single number */ 964 count2 = count; 965 repeat(p, pos, count, count2); 966 if (!EATTWO('\\', '}')) { /* error heuristics */ 967 while (MORE() && !SEETWO('\\', '}')) 968 NEXT(); 969 (void)REQUIRE(MORE(), REG_EBRACE); 970 SETERROR(REG_BADBR); 971 } 972 } else if (c == '$') /* $ (but not \$) ends it */ 973 return (true); 974 975 return (false); 976 } 977 978 /* 979 - p_count - parse a repetition count 980 == static int p_count(struct parse *p); 981 */ 982 static int /* the value */ 983 p_count(struct parse *p) 984 { 985 int count = 0; 986 int ndigits = 0; 987 988 while (MORE() && isdigit((uch)PEEK()) && count <= DUPMAX) { 989 count = count*10 + ((uch)GETNEXT() - '0'); 990 ndigits++; 991 } 992 993 (void)REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR); 994 return(count); 995 } 996 997 /* 998 - p_bracket - parse a bracketed character list 999 == static void p_bracket(struct parse *p); 1000 */ 1001 static void 1002 p_bracket(struct parse *p) 1003 { 1004 cset *cs; 1005 wint_t ch; 1006 1007 /* Dept of Truly Sickening Special-Case Kludges */ 1008 if (p->end - p->next > 5) { 1009 if (strncmp(p->next, "[:<:]]", 6) == 0) { 1010 EMIT(OBOW, 0); 1011 NEXTn(6); 1012 return; 1013 } 1014 if (strncmp(p->next, "[:>:]]", 6) == 0) { 1015 EMIT(OEOW, 0); 1016 NEXTn(6); 1017 return; 1018 } 1019 } 1020 1021 if ((cs = allocset(p)) == NULL) 1022 return; 1023 1024 if (p->g->cflags®_ICASE) 1025 cs->icase = 1; 1026 if (EAT('^')) 1027 cs->invert = 1; 1028 if (EAT(']')) 1029 CHadd(p, cs, ']'); 1030 else if (EAT('-')) 1031 CHadd(p, cs, '-'); 1032 while (MORE() && PEEK() != ']' && !SEETWO('-', ']')) 1033 p_b_term(p, cs); 1034 if (EAT('-')) 1035 CHadd(p, cs, '-'); 1036 (void)MUSTEAT(']', REG_EBRACK); 1037 1038 if (p->error != 0) /* don't mess things up further */ 1039 return; 1040 1041 if (cs->invert && p->g->cflags®_NEWLINE) 1042 cs->bmp['\n' >> 3] |= 1 << ('\n' & 7); 1043 1044 if ((ch = singleton(cs)) != OUT) { /* optimize singleton sets */ 1045 ordinary(p, ch); 1046 freeset(p, cs); 1047 } else 1048 EMIT(OANYOF, (int)(cs - p->g->sets)); 1049 } 1050 1051 static int 1052 p_range_cmp(wchar_t c1, wchar_t c2) 1053 { 1054 #ifndef LIBREGEX 1055 return __wcollate_range_cmp(c1, c2); 1056 #else 1057 /* Copied from libc/collate __wcollate_range_cmp */ 1058 wchar_t s1[2], s2[2]; 1059 1060 s1[0] = c1; 1061 s1[1] = L'\0'; 1062 s2[0] = c2; 1063 s2[1] = L'\0'; 1064 return (wcscoll(s1, s2)); 1065 #endif 1066 } 1067 1068 /* 1069 - p_b_term - parse one term of a bracketed character list 1070 == static void p_b_term(struct parse *p, cset *cs); 1071 */ 1072 static void 1073 p_b_term(struct parse *p, cset *cs) 1074 { 1075 char c; 1076 wint_t start, finish; 1077 wint_t i; 1078 #ifndef LIBREGEX 1079 struct xlocale_collate *table = 1080 (struct xlocale_collate*)__get_locale()->components[XLC_COLLATE]; 1081 #endif 1082 /* classify what we've got */ 1083 switch ((MORE()) ? PEEK() : '\0') { 1084 case '[': 1085 c = (MORE2()) ? PEEK2() : '\0'; 1086 break; 1087 case '-': 1088 SETERROR(REG_ERANGE); 1089 return; /* NOTE RETURN */ 1090 default: 1091 c = '\0'; 1092 break; 1093 } 1094 1095 switch (c) { 1096 case ':': /* character class */ 1097 NEXT2(); 1098 (void)REQUIRE(MORE(), REG_EBRACK); 1099 c = PEEK(); 1100 (void)REQUIRE(c != '-' && c != ']', REG_ECTYPE); 1101 p_b_cclass(p, cs); 1102 (void)REQUIRE(MORE(), REG_EBRACK); 1103 (void)REQUIRE(EATTWO(':', ']'), REG_ECTYPE); 1104 break; 1105 case '=': /* equivalence class */ 1106 NEXT2(); 1107 (void)REQUIRE(MORE(), REG_EBRACK); 1108 c = PEEK(); 1109 (void)REQUIRE(c != '-' && c != ']', REG_ECOLLATE); 1110 p_b_eclass(p, cs); 1111 (void)REQUIRE(MORE(), REG_EBRACK); 1112 (void)REQUIRE(EATTWO('=', ']'), REG_ECOLLATE); 1113 break; 1114 default: /* symbol, ordinary character, or range */ 1115 start = p_b_symbol(p); 1116 if (SEE('-') && MORE2() && PEEK2() != ']') { 1117 /* range */ 1118 NEXT(); 1119 if (EAT('-')) 1120 finish = '-'; 1121 else 1122 finish = p_b_symbol(p); 1123 } else 1124 finish = start; 1125 if (start == finish) 1126 CHadd(p, cs, start); 1127 else { 1128 #ifndef LIBREGEX 1129 if (table->__collate_load_error || MB_CUR_MAX > 1) { 1130 #else 1131 if (MB_CUR_MAX > 1) { 1132 #endif 1133 (void)REQUIRE(start <= finish, REG_ERANGE); 1134 CHaddrange(p, cs, start, finish); 1135 } else { 1136 (void)REQUIRE(p_range_cmp(start, finish) <= 0, REG_ERANGE); 1137 for (i = 0; i <= UCHAR_MAX; i++) { 1138 if (p_range_cmp(start, i) <= 0 && 1139 p_range_cmp(i, finish) <= 0 ) 1140 CHadd(p, cs, i); 1141 } 1142 } 1143 } 1144 break; 1145 } 1146 } 1147 1148 /* 1149 - p_b_pseudoclass - parse a pseudo-class (\w, \W, \s, \S) 1150 == static int p_b_pseudoclass(struct parse *p, char c) 1151 */ 1152 static int 1153 p_b_pseudoclass(struct parse *p, char c) { 1154 cset *cs; 1155 1156 if ((cs = allocset(p)) == NULL) 1157 return(0); 1158 1159 if (p->g->cflags®_ICASE) 1160 cs->icase = 1; 1161 1162 switch (c) { 1163 case 'W': 1164 cs->invert = 1; 1165 /* PASSTHROUGH */ 1166 case 'w': 1167 p_b_cclass_named(p, cs, "alnum"); 1168 break; 1169 case 'S': 1170 cs->invert = 1; 1171 /* PASSTHROUGH */ 1172 case 's': 1173 p_b_cclass_named(p, cs, "space"); 1174 break; 1175 default: 1176 return(0); 1177 } 1178 1179 EMIT(OANYOF, (int)(cs - p->g->sets)); 1180 return(1); 1181 } 1182 1183 /* 1184 - p_b_cclass - parse a character-class name and deal with it 1185 == static void p_b_cclass(struct parse *p, cset *cs); 1186 */ 1187 static void 1188 p_b_cclass(struct parse *p, cset *cs) 1189 { 1190 const char *sp = p->next; 1191 size_t len; 1192 char clname[16]; 1193 1194 while (MORE() && isalpha((uch)PEEK())) 1195 NEXT(); 1196 len = p->next - sp; 1197 if (len >= sizeof(clname) - 1) { 1198 SETERROR(REG_ECTYPE); 1199 return; 1200 } 1201 memcpy(clname, sp, len); 1202 clname[len] = '\0'; 1203 1204 p_b_cclass_named(p, cs, clname); 1205 } 1206 /* 1207 - p_b_cclass_named - deal with a named character class 1208 == static void p_b_cclass_named(struct parse *p, cset *cs, const char []); 1209 */ 1210 static void 1211 p_b_cclass_named(struct parse *p, cset *cs, const char clname[]) { 1212 wctype_t wct; 1213 1214 if ((wct = wctype(clname)) == 0) { 1215 SETERROR(REG_ECTYPE); 1216 return; 1217 } 1218 CHaddtype(p, cs, wct); 1219 } 1220 1221 /* 1222 - p_b_eclass - parse an equivalence-class name and deal with it 1223 == static void p_b_eclass(struct parse *p, cset *cs); 1224 * 1225 * This implementation is incomplete. xxx 1226 */ 1227 static void 1228 p_b_eclass(struct parse *p, cset *cs) 1229 { 1230 wint_t c; 1231 1232 c = p_b_coll_elem(p, '='); 1233 CHadd(p, cs, c); 1234 } 1235 1236 /* 1237 - p_b_symbol - parse a character or [..]ed multicharacter collating symbol 1238 == static wint_t p_b_symbol(struct parse *p); 1239 */ 1240 static wint_t /* value of symbol */ 1241 p_b_symbol(struct parse *p) 1242 { 1243 wint_t value; 1244 1245 (void)REQUIRE(MORE(), REG_EBRACK); 1246 if (!EATTWO('[', '.')) 1247 return(WGETNEXT()); 1248 1249 /* collating symbol */ 1250 value = p_b_coll_elem(p, '.'); 1251 (void)REQUIRE(EATTWO('.', ']'), REG_ECOLLATE); 1252 return(value); 1253 } 1254 1255 /* 1256 - p_b_coll_elem - parse a collating-element name and look it up 1257 == static wint_t p_b_coll_elem(struct parse *p, wint_t endc); 1258 */ 1259 static wint_t /* value of collating element */ 1260 p_b_coll_elem(struct parse *p, 1261 wint_t endc) /* name ended by endc,']' */ 1262 { 1263 const char *sp = p->next; 1264 struct cname *cp; 1265 mbstate_t mbs; 1266 wchar_t wc; 1267 size_t clen, len; 1268 1269 while (MORE() && !SEETWO(endc, ']')) 1270 NEXT(); 1271 if (!MORE()) { 1272 SETERROR(REG_EBRACK); 1273 return(0); 1274 } 1275 len = p->next - sp; 1276 for (cp = cnames; cp->name != NULL; cp++) 1277 if (strncmp(cp->name, sp, len) == 0 && strlen(cp->name) == len) 1278 return(cp->code); /* known name */ 1279 memset(&mbs, 0, sizeof(mbs)); 1280 if ((clen = mbrtowc(&wc, sp, len, &mbs)) == len) 1281 return (wc); /* single character */ 1282 else if (clen == (size_t)-1 || clen == (size_t)-2) 1283 SETERROR(REG_ILLSEQ); 1284 else 1285 SETERROR(REG_ECOLLATE); /* neither */ 1286 return(0); 1287 } 1288 1289 /* 1290 - may_escape - determine whether 'ch' is escape-able in the current context 1291 == static int may_escape(struct parse *p, const wint_t ch) 1292 */ 1293 static bool 1294 may_escape(struct parse *p, const wint_t ch) 1295 { 1296 1297 if ((p->pflags & PFLAG_LEGACY_ESC) != 0) 1298 return (true); 1299 if (iswalpha(ch) || ch == '\'' || ch == '`') 1300 return (false); 1301 return (true); 1302 #ifdef NOTYET 1303 /* 1304 * Build a whitelist of characters that may be escaped to produce an 1305 * ordinary in the current context. This assumes that these have not 1306 * been otherwise interpreted as a special character. Escaping an 1307 * ordinary character yields undefined results according to 1308 * IEEE 1003.1-2008. Some extensions (notably, some GNU extensions) take 1309 * advantage of this and use escaped ordinary characters to provide 1310 * special meaning, e.g. \b, \B, \w, \W, \s, \S. 1311 */ 1312 switch(ch) { 1313 case '|': 1314 case '+': 1315 case '?': 1316 /* The above characters may not be escaped in BREs */ 1317 if (!(p->g->cflags®_EXTENDED)) 1318 return (false); 1319 /* Fallthrough */ 1320 case '(': 1321 case ')': 1322 case '{': 1323 case '}': 1324 case '.': 1325 case '[': 1326 case ']': 1327 case '\\': 1328 case '*': 1329 case '^': 1330 case '$': 1331 return (true); 1332 default: 1333 return (false); 1334 } 1335 #endif 1336 } 1337 1338 /* 1339 - othercase - return the case counterpart of an alphabetic 1340 == static wint_t othercase(wint_t ch); 1341 */ 1342 static wint_t /* if no counterpart, return ch */ 1343 othercase(wint_t ch) 1344 { 1345 assert(iswalpha(ch)); 1346 if (iswupper(ch)) 1347 return(towlower(ch)); 1348 else if (iswlower(ch)) 1349 return(towupper(ch)); 1350 else /* peculiar, but could happen */ 1351 return(ch); 1352 } 1353 1354 /* 1355 - bothcases - emit a dualcase version of a two-case character 1356 == static void bothcases(struct parse *p, wint_t ch); 1357 * 1358 * Boy, is this implementation ever a kludge... 1359 */ 1360 static void 1361 bothcases(struct parse *p, wint_t ch) 1362 { 1363 const char *oldnext = p->next; 1364 const char *oldend = p->end; 1365 char bracket[3 + MB_LEN_MAX]; 1366 size_t n; 1367 mbstate_t mbs; 1368 1369 assert(othercase(ch) != ch); /* p_bracket() would recurse */ 1370 p->next = bracket; 1371 memset(&mbs, 0, sizeof(mbs)); 1372 n = wcrtomb(bracket, ch, &mbs); 1373 assert(n != (size_t)-1); 1374 bracket[n] = ']'; 1375 bracket[n + 1] = '\0'; 1376 p->end = bracket+n+1; 1377 p_bracket(p); 1378 assert(p->next == p->end); 1379 p->next = oldnext; 1380 p->end = oldend; 1381 } 1382 1383 /* 1384 - ordinary - emit an ordinary character 1385 == static void ordinary(struct parse *p, wint_t ch); 1386 */ 1387 static void 1388 ordinary(struct parse *p, wint_t ch) 1389 { 1390 cset *cs; 1391 1392 if ((p->g->cflags®_ICASE) && iswalpha(ch) && othercase(ch) != ch) 1393 bothcases(p, ch); 1394 else if ((ch & OPDMASK) == ch) 1395 EMIT(OCHAR, ch); 1396 else { 1397 /* 1398 * Kludge: character is too big to fit into an OCHAR operand. 1399 * Emit a singleton set. 1400 */ 1401 if ((cs = allocset(p)) == NULL) 1402 return; 1403 CHadd(p, cs, ch); 1404 EMIT(OANYOF, (int)(cs - p->g->sets)); 1405 } 1406 } 1407 1408 /* 1409 - nonnewline - emit REG_NEWLINE version of OANY 1410 == static void nonnewline(struct parse *p); 1411 * 1412 * Boy, is this implementation ever a kludge... 1413 */ 1414 static void 1415 nonnewline(struct parse *p) 1416 { 1417 const char *oldnext = p->next; 1418 const char *oldend = p->end; 1419 char bracket[4]; 1420 1421 p->next = bracket; 1422 p->end = bracket+3; 1423 bracket[0] = '^'; 1424 bracket[1] = '\n'; 1425 bracket[2] = ']'; 1426 bracket[3] = '\0'; 1427 p_bracket(p); 1428 assert(p->next == bracket+3); 1429 p->next = oldnext; 1430 p->end = oldend; 1431 } 1432 1433 /* 1434 - repeat - generate code for a bounded repetition, recursively if needed 1435 == static void repeat(struct parse *p, sopno start, int from, int to); 1436 */ 1437 static void 1438 repeat(struct parse *p, 1439 sopno start, /* operand from here to end of strip */ 1440 int from, /* repeated from this number */ 1441 int to) /* to this number of times (maybe INFINITY) */ 1442 { 1443 sopno finish = HERE(); 1444 # define N 2 1445 # define INF 3 1446 # define REP(f, t) ((f)*8 + (t)) 1447 # define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N) 1448 sopno copy; 1449 1450 if (p->error != 0) /* head off possible runaway recursion */ 1451 return; 1452 1453 assert(from <= to); 1454 1455 switch (REP(MAP(from), MAP(to))) { 1456 case REP(0, 0): /* must be user doing this */ 1457 DROP(finish-start); /* drop the operand */ 1458 break; 1459 case REP(0, 1): /* as x{1,1}? */ 1460 case REP(0, N): /* as x{1,n}? */ 1461 case REP(0, INF): /* as x{1,}? */ 1462 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 1463 INSERT(OCH_, start); /* offset is wrong... */ 1464 repeat(p, start+1, 1, to); 1465 ASTERN(OOR1, start); 1466 AHEAD(start); /* ... fix it */ 1467 EMIT(OOR2, 0); 1468 AHEAD(THERE()); 1469 ASTERN(O_CH, THERETHERE()); 1470 break; 1471 case REP(1, 1): /* trivial case */ 1472 /* done */ 1473 break; 1474 case REP(1, N): /* as x?x{1,n-1} */ 1475 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 1476 INSERT(OCH_, start); 1477 ASTERN(OOR1, start); 1478 AHEAD(start); 1479 EMIT(OOR2, 0); /* offset very wrong... */ 1480 AHEAD(THERE()); /* ...so fix it */ 1481 ASTERN(O_CH, THERETHERE()); 1482 copy = dupl(p, start+1, finish+1); 1483 assert(copy == finish+4); 1484 repeat(p, copy, 1, to-1); 1485 break; 1486 case REP(1, INF): /* as x+ */ 1487 INSERT(OPLUS_, start); 1488 ASTERN(O_PLUS, start); 1489 break; 1490 case REP(N, N): /* as xx{m-1,n-1} */ 1491 copy = dupl(p, start, finish); 1492 repeat(p, copy, from-1, to-1); 1493 break; 1494 case REP(N, INF): /* as xx{n-1,INF} */ 1495 copy = dupl(p, start, finish); 1496 repeat(p, copy, from-1, to); 1497 break; 1498 default: /* "can't happen" */ 1499 SETERROR(REG_ASSERT); /* just in case */ 1500 break; 1501 } 1502 } 1503 1504 /* 1505 - wgetnext - helper function for WGETNEXT() macro. Gets the next wide 1506 - character from the parse struct, signals a REG_ILLSEQ error if the 1507 - character can't be converted. Returns the number of bytes consumed. 1508 */ 1509 static wint_t 1510 wgetnext(struct parse *p) 1511 { 1512 mbstate_t mbs; 1513 wchar_t wc; 1514 size_t n; 1515 1516 memset(&mbs, 0, sizeof(mbs)); 1517 n = mbrtowc(&wc, p->next, p->end - p->next, &mbs); 1518 if (n == (size_t)-1 || n == (size_t)-2) { 1519 SETERROR(REG_ILLSEQ); 1520 return (0); 1521 } 1522 if (n == 0) 1523 n = 1; 1524 p->next += n; 1525 return (wc); 1526 } 1527 1528 /* 1529 - seterr - set an error condition 1530 == static int seterr(struct parse *p, int e); 1531 */ 1532 static int /* useless but makes type checking happy */ 1533 seterr(struct parse *p, int e) 1534 { 1535 if (p->error == 0) /* keep earliest error condition */ 1536 p->error = e; 1537 p->next = nuls; /* try to bring things to a halt */ 1538 p->end = nuls; 1539 return(0); /* make the return value well-defined */ 1540 } 1541 1542 /* 1543 - allocset - allocate a set of characters for [] 1544 == static cset *allocset(struct parse *p); 1545 */ 1546 static cset * 1547 allocset(struct parse *p) 1548 { 1549 cset *cs, *ncs; 1550 1551 ncs = reallocarray(p->g->sets, p->g->ncsets + 1, sizeof(*ncs)); 1552 if (ncs == NULL) { 1553 SETERROR(REG_ESPACE); 1554 return (NULL); 1555 } 1556 p->g->sets = ncs; 1557 cs = &p->g->sets[p->g->ncsets++]; 1558 memset(cs, 0, sizeof(*cs)); 1559 1560 return(cs); 1561 } 1562 1563 /* 1564 - freeset - free a now-unused set 1565 == static void freeset(struct parse *p, cset *cs); 1566 */ 1567 static void 1568 freeset(struct parse *p, cset *cs) 1569 { 1570 cset *top = &p->g->sets[p->g->ncsets]; 1571 1572 free(cs->wides); 1573 free(cs->ranges); 1574 free(cs->types); 1575 memset(cs, 0, sizeof(*cs)); 1576 if (cs == top-1) /* recover only the easy case */ 1577 p->g->ncsets--; 1578 } 1579 1580 /* 1581 - singleton - Determine whether a set contains only one character, 1582 - returning it if so, otherwise returning OUT. 1583 */ 1584 static wint_t 1585 singleton(cset *cs) 1586 { 1587 wint_t i, s, n; 1588 1589 /* Exclude the complicated cases we don't want to deal with */ 1590 if (cs->nranges != 0 || cs->ntypes != 0 || cs->icase != 0) 1591 return (OUT); 1592 1593 if (cs->nwides > 1) 1594 return (OUT); 1595 1596 /* Count the number of characters present in the bitmap */ 1597 for (i = n = 0; i < NC; i++) 1598 if (CHIN(cs, i)) { 1599 n++; 1600 s = i; 1601 } 1602 1603 if (n > 1) 1604 return (OUT); 1605 1606 if (n == 1) { 1607 if (cs->nwides == 0) 1608 return (s); 1609 else 1610 return (OUT); 1611 } 1612 if (cs->nwides == 1) 1613 return (cs->wides[0]); 1614 1615 return (OUT); 1616 } 1617 1618 /* 1619 - CHadd - add character to character set. 1620 */ 1621 static void 1622 CHadd(struct parse *p, cset *cs, wint_t ch) 1623 { 1624 wint_t nch, *newwides; 1625 assert(ch >= 0); 1626 if (ch < NC) 1627 cs->bmp[ch >> 3] |= 1 << (ch & 7); 1628 else { 1629 newwides = reallocarray(cs->wides, cs->nwides + 1, 1630 sizeof(*cs->wides)); 1631 if (newwides == NULL) { 1632 SETERROR(REG_ESPACE); 1633 return; 1634 } 1635 cs->wides = newwides; 1636 cs->wides[cs->nwides++] = ch; 1637 } 1638 if (cs->icase) { 1639 if ((nch = towlower(ch)) < NC) 1640 cs->bmp[nch >> 3] |= 1 << (nch & 7); 1641 if ((nch = towupper(ch)) < NC) 1642 cs->bmp[nch >> 3] |= 1 << (nch & 7); 1643 } 1644 } 1645 1646 /* 1647 - CHaddrange - add all characters in the range [min,max] to a character set. 1648 */ 1649 static void 1650 CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max) 1651 { 1652 crange *newranges; 1653 1654 for (; min < NC && min <= max; min++) 1655 CHadd(p, cs, min); 1656 if (min >= max) 1657 return; 1658 newranges = reallocarray(cs->ranges, cs->nranges + 1, 1659 sizeof(*cs->ranges)); 1660 if (newranges == NULL) { 1661 SETERROR(REG_ESPACE); 1662 return; 1663 } 1664 cs->ranges = newranges; 1665 cs->ranges[cs->nranges].min = min; 1666 cs->ranges[cs->nranges].max = max; 1667 cs->nranges++; 1668 } 1669 1670 /* 1671 - CHaddtype - add all characters of a certain type to a character set. 1672 */ 1673 static void 1674 CHaddtype(struct parse *p, cset *cs, wctype_t wct) 1675 { 1676 wint_t i; 1677 wctype_t *newtypes; 1678 1679 for (i = 0; i < NC; i++) 1680 if (iswctype(i, wct)) 1681 CHadd(p, cs, i); 1682 newtypes = reallocarray(cs->types, cs->ntypes + 1, 1683 sizeof(*cs->types)); 1684 if (newtypes == NULL) { 1685 SETERROR(REG_ESPACE); 1686 return; 1687 } 1688 cs->types = newtypes; 1689 cs->types[cs->ntypes++] = wct; 1690 } 1691 1692 /* 1693 - dupl - emit a duplicate of a bunch of sops 1694 == static sopno dupl(struct parse *p, sopno start, sopno finish); 1695 */ 1696 static sopno /* start of duplicate */ 1697 dupl(struct parse *p, 1698 sopno start, /* from here */ 1699 sopno finish) /* to this less one */ 1700 { 1701 sopno ret = HERE(); 1702 sopno len = finish - start; 1703 1704 assert(finish >= start); 1705 if (len == 0) 1706 return(ret); 1707 if (!enlarge(p, p->ssize + len)) /* this many unexpected additions */ 1708 return(ret); 1709 (void) memcpy((char *)(p->strip + p->slen), 1710 (char *)(p->strip + start), (size_t)len*sizeof(sop)); 1711 p->slen += len; 1712 return(ret); 1713 } 1714 1715 /* 1716 - doemit - emit a strip operator 1717 == static void doemit(struct parse *p, sop op, size_t opnd); 1718 * 1719 * It might seem better to implement this as a macro with a function as 1720 * hard-case backup, but it's just too big and messy unless there are 1721 * some changes to the data structures. Maybe later. 1722 */ 1723 static void 1724 doemit(struct parse *p, sop op, size_t opnd) 1725 { 1726 /* avoid making error situations worse */ 1727 if (p->error != 0) 1728 return; 1729 1730 /* deal with oversize operands ("can't happen", more or less) */ 1731 assert(opnd < 1<<OPSHIFT); 1732 1733 /* deal with undersized strip */ 1734 if (p->slen >= p->ssize) 1735 if (!enlarge(p, (p->ssize+1) / 2 * 3)) /* +50% */ 1736 return; 1737 1738 /* finally, it's all reduced to the easy case */ 1739 p->strip[p->slen++] = SOP(op, opnd); 1740 } 1741 1742 /* 1743 - doinsert - insert a sop into the strip 1744 == static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos); 1745 */ 1746 static void 1747 doinsert(struct parse *p, sop op, size_t opnd, sopno pos) 1748 { 1749 sopno sn; 1750 sop s; 1751 int i; 1752 1753 /* avoid making error situations worse */ 1754 if (p->error != 0) 1755 return; 1756 1757 sn = HERE(); 1758 EMIT(op, opnd); /* do checks, ensure space */ 1759 assert(HERE() == sn+1); 1760 s = p->strip[sn]; 1761 1762 /* adjust paren pointers */ 1763 assert(pos > 0); 1764 for (i = 1; i < NPAREN; i++) { 1765 if (p->pbegin[i] >= pos) { 1766 p->pbegin[i]++; 1767 } 1768 if (p->pend[i] >= pos) { 1769 p->pend[i]++; 1770 } 1771 } 1772 1773 memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos], 1774 (HERE()-pos-1)*sizeof(sop)); 1775 p->strip[pos] = s; 1776 } 1777 1778 /* 1779 - dofwd - complete a forward reference 1780 == static void dofwd(struct parse *p, sopno pos, sop value); 1781 */ 1782 static void 1783 dofwd(struct parse *p, sopno pos, sop value) 1784 { 1785 /* avoid making error situations worse */ 1786 if (p->error != 0) 1787 return; 1788 1789 assert(value < 1<<OPSHIFT); 1790 p->strip[pos] = OP(p->strip[pos]) | value; 1791 } 1792 1793 /* 1794 - enlarge - enlarge the strip 1795 == static int enlarge(struct parse *p, sopno size); 1796 */ 1797 static int 1798 enlarge(struct parse *p, sopno size) 1799 { 1800 sop *sp; 1801 1802 if (p->ssize >= size) 1803 return 1; 1804 1805 sp = reallocarray(p->strip, size, sizeof(sop)); 1806 if (sp == NULL) { 1807 SETERROR(REG_ESPACE); 1808 return 0; 1809 } 1810 p->strip = sp; 1811 p->ssize = size; 1812 return 1; 1813 } 1814 1815 /* 1816 - stripsnug - compact the strip 1817 == static void stripsnug(struct parse *p, struct re_guts *g); 1818 */ 1819 static void 1820 stripsnug(struct parse *p, struct re_guts *g) 1821 { 1822 g->nstates = p->slen; 1823 g->strip = reallocarray((char *)p->strip, p->slen, sizeof(sop)); 1824 if (g->strip == NULL) { 1825 SETERROR(REG_ESPACE); 1826 g->strip = p->strip; 1827 } 1828 } 1829 1830 /* 1831 - findmust - fill in must and mlen with longest mandatory literal string 1832 == static void findmust(struct parse *p, struct re_guts *g); 1833 * 1834 * This algorithm could do fancy things like analyzing the operands of | 1835 * for common subsequences. Someday. This code is simple and finds most 1836 * of the interesting cases. 1837 * 1838 * Note that must and mlen got initialized during setup. 1839 */ 1840 static void 1841 findmust(struct parse *p, struct re_guts *g) 1842 { 1843 sop *scan; 1844 sop *start = NULL; 1845 sop *newstart = NULL; 1846 sopno newlen; 1847 sop s; 1848 char *cp; 1849 int offset; 1850 char buf[MB_LEN_MAX]; 1851 size_t clen; 1852 mbstate_t mbs; 1853 1854 /* avoid making error situations worse */ 1855 if (p->error != 0) 1856 return; 1857 1858 /* 1859 * It's not generally safe to do a ``char'' substring search on 1860 * multibyte character strings, but it's safe for at least 1861 * UTF-8 (see RFC 3629). 1862 */ 1863 if (MB_CUR_MAX > 1 && 1864 strcmp(_CurrentRuneLocale->__encoding, "UTF-8") != 0) 1865 return; 1866 1867 /* find the longest OCHAR sequence in strip */ 1868 newlen = 0; 1869 offset = 0; 1870 g->moffset = 0; 1871 scan = g->strip + 1; 1872 do { 1873 s = *scan++; 1874 switch (OP(s)) { 1875 case OCHAR: /* sequence member */ 1876 if (newlen == 0) { /* new sequence */ 1877 memset(&mbs, 0, sizeof(mbs)); 1878 newstart = scan - 1; 1879 } 1880 clen = wcrtomb(buf, OPND(s), &mbs); 1881 if (clen == (size_t)-1) 1882 goto toohard; 1883 newlen += clen; 1884 break; 1885 case OPLUS_: /* things that don't break one */ 1886 case OLPAREN: 1887 case ORPAREN: 1888 break; 1889 case OQUEST_: /* things that must be skipped */ 1890 case OCH_: 1891 offset = altoffset(scan, offset); 1892 scan--; 1893 do { 1894 scan += OPND(s); 1895 s = *scan; 1896 /* assert() interferes w debug printouts */ 1897 if (OP(s) != (sop)O_QUEST && 1898 OP(s) != (sop)O_CH && OP(s) != (sop)OOR2) { 1899 g->iflags |= BAD; 1900 return; 1901 } 1902 } while (OP(s) != (sop)O_QUEST && OP(s) != (sop)O_CH); 1903 /* FALLTHROUGH */ 1904 case OBOW: /* things that break a sequence */ 1905 case OEOW: 1906 case OBOL: 1907 case OEOL: 1908 case OBOS: 1909 case OEOS: 1910 case OWBND: 1911 case ONWBND: 1912 case O_QUEST: 1913 case O_CH: 1914 case OEND: 1915 if (newlen > (sopno)g->mlen) { /* ends one */ 1916 start = newstart; 1917 g->mlen = newlen; 1918 if (offset > -1) { 1919 g->moffset += offset; 1920 offset = newlen; 1921 } else 1922 g->moffset = offset; 1923 } else { 1924 if (offset > -1) 1925 offset += newlen; 1926 } 1927 newlen = 0; 1928 break; 1929 case OANY: 1930 if (newlen > (sopno)g->mlen) { /* ends one */ 1931 start = newstart; 1932 g->mlen = newlen; 1933 if (offset > -1) { 1934 g->moffset += offset; 1935 offset = newlen; 1936 } else 1937 g->moffset = offset; 1938 } else { 1939 if (offset > -1) 1940 offset += newlen; 1941 } 1942 if (offset > -1) 1943 offset++; 1944 newlen = 0; 1945 break; 1946 case OANYOF: /* may or may not invalidate offset */ 1947 /* First, everything as OANY */ 1948 if (newlen > (sopno)g->mlen) { /* ends one */ 1949 start = newstart; 1950 g->mlen = newlen; 1951 if (offset > -1) { 1952 g->moffset += offset; 1953 offset = newlen; 1954 } else 1955 g->moffset = offset; 1956 } else { 1957 if (offset > -1) 1958 offset += newlen; 1959 } 1960 if (offset > -1) 1961 offset++; 1962 newlen = 0; 1963 break; 1964 toohard: 1965 default: 1966 /* Anything here makes it impossible or too hard 1967 * to calculate the offset -- so we give up; 1968 * save the last known good offset, in case the 1969 * must sequence doesn't occur later. 1970 */ 1971 if (newlen > (sopno)g->mlen) { /* ends one */ 1972 start = newstart; 1973 g->mlen = newlen; 1974 if (offset > -1) 1975 g->moffset += offset; 1976 else 1977 g->moffset = offset; 1978 } 1979 offset = -1; 1980 newlen = 0; 1981 break; 1982 } 1983 } while (OP(s) != OEND); 1984 1985 if (g->mlen == 0) { /* there isn't one */ 1986 g->moffset = -1; 1987 return; 1988 } 1989 1990 /* turn it into a character string */ 1991 g->must = malloc((size_t)g->mlen + 1); 1992 if (g->must == NULL) { /* argh; just forget it */ 1993 g->mlen = 0; 1994 g->moffset = -1; 1995 return; 1996 } 1997 cp = g->must; 1998 scan = start; 1999 memset(&mbs, 0, sizeof(mbs)); 2000 while (cp < g->must + g->mlen) { 2001 while (OP(s = *scan++) != OCHAR) 2002 continue; 2003 clen = wcrtomb(cp, OPND(s), &mbs); 2004 assert(clen != (size_t)-1); 2005 cp += clen; 2006 } 2007 assert(cp == g->must + g->mlen); 2008 *cp++ = '\0'; /* just on general principles */ 2009 } 2010 2011 /* 2012 - altoffset - choose biggest offset among multiple choices 2013 == static int altoffset(sop *scan, int offset); 2014 * 2015 * Compute, recursively if necessary, the largest offset among multiple 2016 * re paths. 2017 */ 2018 static int 2019 altoffset(sop *scan, int offset) 2020 { 2021 int largest; 2022 int try; 2023 sop s; 2024 2025 /* If we gave up already on offsets, return */ 2026 if (offset == -1) 2027 return -1; 2028 2029 largest = 0; 2030 try = 0; 2031 s = *scan++; 2032 while (OP(s) != (sop)O_QUEST && OP(s) != (sop)O_CH) { 2033 switch (OP(s)) { 2034 case OOR1: 2035 if (try > largest) 2036 largest = try; 2037 try = 0; 2038 break; 2039 case OQUEST_: 2040 case OCH_: 2041 try = altoffset(scan, try); 2042 if (try == -1) 2043 return -1; 2044 scan--; 2045 do { 2046 scan += OPND(s); 2047 s = *scan; 2048 if (OP(s) != (sop)O_QUEST && 2049 OP(s) != (sop)O_CH && OP(s) != (sop)OOR2) 2050 return -1; 2051 } while (OP(s) != (sop)O_QUEST && OP(s) != (sop)O_CH); 2052 /* We must skip to the next position, or we'll 2053 * leave altoffset() too early. 2054 */ 2055 scan++; 2056 break; 2057 case OANYOF: 2058 case OCHAR: 2059 case OANY: 2060 try++; 2061 case OBOW: 2062 case OEOW: 2063 case OWBND: 2064 case ONWBND: 2065 case OLPAREN: 2066 case ORPAREN: 2067 case OOR2: 2068 break; 2069 default: 2070 try = -1; 2071 break; 2072 } 2073 if (try == -1) 2074 return -1; 2075 s = *scan++; 2076 } 2077 2078 if (try > largest) 2079 largest = try; 2080 2081 return largest+offset; 2082 } 2083 2084 /* 2085 - computejumps - compute char jumps for BM scan 2086 == static void computejumps(struct parse *p, struct re_guts *g); 2087 * 2088 * This algorithm assumes g->must exists and is has size greater than 2089 * zero. It's based on the algorithm found on Computer Algorithms by 2090 * Sara Baase. 2091 * 2092 * A char jump is the number of characters one needs to jump based on 2093 * the value of the character from the text that was mismatched. 2094 */ 2095 static void 2096 computejumps(struct parse *p, struct re_guts *g) 2097 { 2098 int ch; 2099 int mindex; 2100 2101 /* Avoid making errors worse */ 2102 if (p->error != 0) 2103 return; 2104 2105 g->charjump = (int *)malloc((NC_MAX + 1) * sizeof(int)); 2106 if (g->charjump == NULL) /* Not a fatal error */ 2107 return; 2108 /* Adjust for signed chars, if necessary */ 2109 g->charjump = &g->charjump[-(CHAR_MIN)]; 2110 2111 /* If the character does not exist in the pattern, the jump 2112 * is equal to the number of characters in the pattern. 2113 */ 2114 for (ch = CHAR_MIN; ch < (CHAR_MAX + 1); ch++) 2115 g->charjump[ch] = g->mlen; 2116 2117 /* If the character does exist, compute the jump that would 2118 * take us to the last character in the pattern equal to it 2119 * (notice that we match right to left, so that last character 2120 * is the first one that would be matched). 2121 */ 2122 for (mindex = 0; mindex < g->mlen; mindex++) 2123 g->charjump[(int)g->must[mindex]] = g->mlen - mindex - 1; 2124 } 2125 2126 /* 2127 - computematchjumps - compute match jumps for BM scan 2128 == static void computematchjumps(struct parse *p, struct re_guts *g); 2129 * 2130 * This algorithm assumes g->must exists and is has size greater than 2131 * zero. It's based on the algorithm found on Computer Algorithms by 2132 * Sara Baase. 2133 * 2134 * A match jump is the number of characters one needs to advance based 2135 * on the already-matched suffix. 2136 * Notice that all values here are minus (g->mlen-1), because of the way 2137 * the search algorithm works. 2138 */ 2139 static void 2140 computematchjumps(struct parse *p, struct re_guts *g) 2141 { 2142 int mindex; /* General "must" iterator */ 2143 int suffix; /* Keeps track of matching suffix */ 2144 int ssuffix; /* Keeps track of suffixes' suffix */ 2145 int* pmatches; /* pmatches[k] points to the next i 2146 * such that i+1...mlen is a substring 2147 * of k+1...k+mlen-i-1 2148 */ 2149 2150 /* Avoid making errors worse */ 2151 if (p->error != 0) 2152 return; 2153 2154 pmatches = (int*) malloc(g->mlen * sizeof(int)); 2155 if (pmatches == NULL) { 2156 g->matchjump = NULL; 2157 return; 2158 } 2159 2160 g->matchjump = (int*) malloc(g->mlen * sizeof(int)); 2161 if (g->matchjump == NULL) { /* Not a fatal error */ 2162 free(pmatches); 2163 return; 2164 } 2165 2166 /* Set maximum possible jump for each character in the pattern */ 2167 for (mindex = 0; mindex < g->mlen; mindex++) 2168 g->matchjump[mindex] = 2*g->mlen - mindex - 1; 2169 2170 /* Compute pmatches[] */ 2171 for (mindex = g->mlen - 1, suffix = g->mlen; mindex >= 0; 2172 mindex--, suffix--) { 2173 pmatches[mindex] = suffix; 2174 2175 /* If a mismatch is found, interrupting the substring, 2176 * compute the matchjump for that position. If no 2177 * mismatch is found, then a text substring mismatched 2178 * against the suffix will also mismatch against the 2179 * substring. 2180 */ 2181 while (suffix < g->mlen 2182 && g->must[mindex] != g->must[suffix]) { 2183 g->matchjump[suffix] = MIN(g->matchjump[suffix], 2184 g->mlen - mindex - 1); 2185 suffix = pmatches[suffix]; 2186 } 2187 } 2188 2189 /* Compute the matchjump up to the last substring found to jump 2190 * to the beginning of the largest must pattern prefix matching 2191 * it's own suffix. 2192 */ 2193 for (mindex = 0; mindex <= suffix; mindex++) 2194 g->matchjump[mindex] = MIN(g->matchjump[mindex], 2195 g->mlen + suffix - mindex); 2196 2197 ssuffix = pmatches[suffix]; 2198 while (suffix < g->mlen) { 2199 while (suffix <= ssuffix && suffix < g->mlen) { 2200 g->matchjump[suffix] = MIN(g->matchjump[suffix], 2201 g->mlen + ssuffix - suffix); 2202 suffix++; 2203 } 2204 if (suffix < g->mlen) 2205 ssuffix = pmatches[ssuffix]; 2206 } 2207 2208 free(pmatches); 2209 } 2210 2211 /* 2212 - pluscount - count + nesting 2213 == static sopno pluscount(struct parse *p, struct re_guts *g); 2214 */ 2215 static sopno /* nesting depth */ 2216 pluscount(struct parse *p, struct re_guts *g) 2217 { 2218 sop *scan; 2219 sop s; 2220 sopno plusnest = 0; 2221 sopno maxnest = 0; 2222 2223 if (p->error != 0) 2224 return(0); /* there may not be an OEND */ 2225 2226 scan = g->strip + 1; 2227 do { 2228 s = *scan++; 2229 switch (OP(s)) { 2230 case OPLUS_: 2231 plusnest++; 2232 break; 2233 case O_PLUS: 2234 if (plusnest > maxnest) 2235 maxnest = plusnest; 2236 plusnest--; 2237 break; 2238 } 2239 } while (OP(s) != OEND); 2240 if (plusnest != 0) 2241 g->iflags |= BAD; 2242 return(maxnest); 2243 } 2244