1 /* 2 * Copyright (c) 1992, 1993, 1994 Henry Spencer. 3 * Copyright (c) 1992, 1993, 1994 4 * The Regents of the University of California. All rights reserved. 5 * 6 * This code is derived from software contributed to Berkeley by 7 * Henry Spencer. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 4. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34 /* 35 * Copyright 2010 Nexenta Systems, Inc. All rights reserved. 36 * Use is subject to license terms. 37 */ 38 39 #include "lint.h" 40 #include "file64.h" 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 <wchar.h> 49 #include <wctype.h> 50 51 #include "runetype.h" 52 #include "collate.h" 53 54 #include "utils.h" 55 #include "regex2.h" 56 57 #include "cname.h" 58 #include "mblocal.h" 59 60 /* 61 * parse structure, passed up and down to avoid global variables and 62 * other clumsinesses 63 */ 64 struct parse { 65 char *next; /* next character in RE */ 66 char *end; /* end of string (-> NUL normally) */ 67 int error; /* has an error been seen? */ 68 sop *strip; /* malloced strip */ 69 sopno ssize; /* malloced strip size (allocated) */ 70 sopno slen; /* malloced strip length (used) */ 71 int ncsalloc; /* number of csets allocated */ 72 struct re_guts *g; 73 #define NPAREN 10 /* we need to remember () 1-9 for back refs */ 74 sopno pbegin[NPAREN]; /* -> ( ([0] unused) */ 75 sopno pend[NPAREN]; /* -> ) ([0] unused) */ 76 }; 77 78 /* ========= begin header generated by ./mkh ========= */ 79 #ifdef __cplusplus 80 extern "C" { 81 #endif 82 83 /* === regcomp.c === */ 84 static void p_ere(struct parse *p, wint_t stop); 85 static void p_ere_exp(struct parse *p); 86 static void p_str(struct parse *p); 87 static void p_bre(struct parse *p, wint_t end1, wint_t end2); 88 static int p_simp_re(struct parse *p, int starordinary); 89 static int p_count(struct parse *p); 90 static void p_bracket(struct parse *p); 91 static void p_b_term(struct parse *p, cset *cs); 92 static void p_b_cclass(struct parse *p, cset *cs); 93 static void p_b_eclass(struct parse *p, cset *cs); 94 static wint_t p_b_symbol(struct parse *p); 95 static wint_t p_b_coll_elem(struct parse *p, wint_t endc); 96 static wint_t othercase(wint_t ch); 97 static void bothcases(struct parse *p, wint_t ch); 98 static void ordinary(struct parse *p, wint_t ch); 99 static void nonnewline(struct parse *p); 100 static void repeat(struct parse *p, sopno start, int from, int to); 101 static int seterr(struct parse *p, int e); 102 static cset *allocset(struct parse *p); 103 static void freeset(struct parse *p, cset *cs); 104 static void CHadd(struct parse *p, cset *cs, wint_t ch); 105 static void CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max); 106 static void CHaddtype(struct parse *p, cset *cs, wctype_t wct); 107 static wint_t singleton(cset *cs); 108 static sopno dupl(struct parse *p, sopno start, sopno finish); 109 static void doemit(struct parse *p, sop op, size_t opnd); 110 static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos); 111 static void dofwd(struct parse *p, sopno pos, sop value); 112 static void enlarge(struct parse *p, sopno size); 113 static void stripsnug(struct parse *p, struct re_guts *g); 114 static void findmust(struct parse *p, struct re_guts *g); 115 static int altoffset(sop *scan, int offset); 116 static void computejumps(struct parse *p, struct re_guts *g); 117 static void computematchjumps(struct parse *p, struct re_guts *g); 118 static sopno pluscount(struct parse *p, struct re_guts *g); 119 static wint_t wgetnext(struct parse *p); 120 121 #ifdef __cplusplus 122 } 123 #endif 124 /* ========= end header generated by ./mkh ========= */ 125 126 static char nuls[10]; /* place to point scanner in event of error */ 127 128 /* 129 * macros for use with parse structure 130 * BEWARE: these know that the parse structure is named `p' !!! 131 */ 132 #define PEEK() (*p->next) 133 #define PEEK2() (*(p->next+1)) 134 #define MORE() (p->next < p->end) 135 #define MORE2() (p->next+1 < p->end) 136 #define SEE(c) (MORE() && PEEK() == (c)) 137 #define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b)) 138 #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0) 139 #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0) 140 #define NEXT() (p->next++) 141 #define NEXT2() (p->next += 2) 142 #define NEXTn(n) (p->next += (n)) 143 #define GETNEXT() (*p->next++) 144 #define WGETNEXT() wgetnext(p) 145 #define SETERROR(e) ((void)seterr(p, (e))) 146 #define REQUIRE(co, e) ((co) || seterr(p, e)) 147 #define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e)) 148 #define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e)) 149 #define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e)) 150 #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd)) 151 #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos) 152 #define AHEAD(pos) dofwd(p, pos, HERE()-(pos)) 153 #define ASTERN(sop, pos) EMIT(sop, HERE()-pos) 154 #define HERE() (p->slen) 155 #define THERE() (p->slen - 1) 156 #define THERETHERE() (p->slen - 2) 157 #define DROP(n) (p->slen -= (n)) 158 159 #ifndef NDEBUG 160 static int never = 0; /* for use in asserts; shuts lint up */ 161 #else 162 #define never 0 /* some <assert.h>s have bugs too */ 163 #endif 164 165 /* 166 * regcomp - interface for parser and compilation 167 */ 168 int /* 0 success, otherwise REG_something */ 169 regcomp(regex_t *_RESTRICT_KYWD preg, 170 const char *_RESTRICT_KYWD pattern, 171 int cflags) 172 { 173 struct parse pa; 174 struct re_guts *g; 175 struct parse *p = &pa; 176 int i; 177 size_t len; 178 #ifdef REDEBUG 179 #define GOODFLAGS(f) (f) 180 #else 181 #define GOODFLAGS(f) ((f)&~REG_DUMP) 182 #endif 183 184 /* We had REG_INVARG, but we don't have that on Solaris. */ 185 cflags = GOODFLAGS(cflags); 186 if ((cflags®_EXTENDED) && (cflags®_NOSPEC)) 187 return (REG_EFATAL); 188 189 if (cflags®_PEND) { 190 if (preg->re_endp < pattern) 191 return (REG_EFATAL); 192 len = preg->re_endp - pattern; 193 } else 194 len = strlen((char *)pattern); 195 196 /* do the mallocs early so failure handling is easy */ 197 g = (struct re_guts *)malloc(sizeof (struct re_guts)); 198 if (g == NULL) 199 return (REG_ESPACE); 200 p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */ 201 p->strip = (sop *)malloc(p->ssize * sizeof (sop)); 202 p->slen = 0; 203 if (p->strip == NULL) { 204 free((char *)g); 205 return (REG_ESPACE); 206 } 207 208 /* set things up */ 209 p->g = g; 210 p->next = (char *)pattern; /* convenience; we do not modify it */ 211 p->end = p->next + len; 212 p->error = 0; 213 p->ncsalloc = 0; 214 for (i = 0; i < NPAREN; i++) { 215 p->pbegin[i] = 0; 216 p->pend[i] = 0; 217 } 218 g->sets = NULL; 219 g->ncsets = 0; 220 g->cflags = cflags; 221 g->iflags = 0; 222 g->nbol = 0; 223 g->neol = 0; 224 g->must = NULL; 225 g->moffset = -1; 226 g->charjump = NULL; 227 g->matchjump = NULL; 228 g->mlen = 0; 229 g->nsub = 0; 230 g->backrefs = 0; 231 232 /* do it */ 233 EMIT(OEND, 0); 234 g->firststate = THERE(); 235 if (cflags®_EXTENDED) 236 p_ere(p, OUT); 237 else if (cflags®_NOSPEC) 238 p_str(p); 239 else 240 p_bre(p, OUT, OUT); 241 EMIT(OEND, 0); 242 g->laststate = THERE(); 243 244 /* tidy up loose ends and fill things in */ 245 stripsnug(p, g); 246 findmust(p, g); 247 /* 248 * only use Boyer-Moore algorithm if the pattern is bigger 249 * than three characters 250 */ 251 if (g->mlen > 3) { 252 computejumps(p, g); 253 computematchjumps(p, g); 254 if (g->matchjump == NULL && g->charjump != NULL) { 255 free(g->charjump); 256 g->charjump = NULL; 257 } 258 } 259 g->nplus = pluscount(p, g); 260 g->magic = MAGIC2; 261 preg->re_nsub = g->nsub; 262 preg->re_g = g; 263 preg->re_magic = MAGIC1; 264 #ifndef REDEBUG 265 /* not debugging, so can't rely on the assert() in regexec() */ 266 if (g->iflags&BAD) 267 SETERROR(REG_EFATAL); 268 #endif 269 270 /* win or lose, we're done */ 271 if (p->error != 0) /* lose */ 272 regfree(preg); 273 return (p->error); 274 } 275 276 /* 277 * p_ere - ERE parser top level, concatenation and alternation 278 */ 279 static void 280 p_ere(struct parse *p, 281 wint_t stop) /* character this ERE should end at */ 282 { 283 char c; 284 sopno prevback; 285 sopno prevfwd; 286 sopno conc; 287 int first = 1; /* is this the first alternative? */ 288 289 for (;;) { 290 /* do a bunch of concatenated expressions */ 291 conc = HERE(); 292 while (MORE() && (c = PEEK()) != '|' && c != stop) 293 p_ere_exp(p); 294 /* require nonempty */ 295 (void) REQUIRE(HERE() != conc, REG_BADPAT); 296 297 if (!EAT('|')) 298 break; /* NOTE BREAK OUT */ 299 300 if (first) { 301 INSERT(OCH_, conc); /* offset is wrong */ 302 prevfwd = conc; 303 prevback = conc; 304 first = 0; 305 } 306 ASTERN(OOR1, prevback); 307 prevback = THERE(); 308 AHEAD(prevfwd); /* fix previous offset */ 309 prevfwd = HERE(); 310 EMIT(OOR2, 0); /* offset is very wrong */ 311 } 312 313 if (!first) { /* tail-end fixups */ 314 AHEAD(prevfwd); 315 ASTERN(O_CH, prevback); 316 } 317 318 assert(!MORE() || SEE(stop)); 319 } 320 321 /* 322 * p_ere_exp - parse one subERE, an atom possibly followed by a repetition op 323 */ 324 static void 325 p_ere_exp(struct parse *p) 326 { 327 char c; 328 wint_t wc; 329 sopno pos; 330 int count; 331 int count2; 332 sopno subno; 333 int wascaret = 0; 334 335 assert(MORE()); /* caller should have ensured this */ 336 c = GETNEXT(); 337 338 pos = HERE(); 339 switch (c) { 340 case '(': 341 (void) REQUIRE(MORE(), REG_EPAREN); 342 p->g->nsub++; 343 subno = p->g->nsub; 344 if (subno < NPAREN) 345 p->pbegin[subno] = HERE(); 346 EMIT(OLPAREN, subno); 347 if (!SEE(')')) 348 p_ere(p, ')'); 349 if (subno < NPAREN) { 350 p->pend[subno] = HERE(); 351 assert(p->pend[subno] != 0); 352 } 353 EMIT(ORPAREN, subno); 354 (void) MUSTEAT(')', REG_EPAREN); 355 break; 356 #ifndef POSIX_MISTAKE 357 case ')': /* happens only if no current unmatched ( */ 358 /* 359 * You may ask, why the ifndef? Because I didn't notice 360 * this until slightly too late for 1003.2, and none of the 361 * other 1003.2 regular-expression reviewers noticed it at 362 * all. So an unmatched ) is legal POSIX, at least until 363 * we can get it fixed. 364 */ 365 SETERROR(REG_EPAREN); 366 break; 367 #endif 368 case '^': 369 EMIT(OBOL, 0); 370 p->g->iflags |= USEBOL; 371 p->g->nbol++; 372 wascaret = 1; 373 break; 374 case '$': 375 EMIT(OEOL, 0); 376 p->g->iflags |= USEEOL; 377 p->g->neol++; 378 break; 379 case '|': 380 SETERROR(REG_BADPAT); 381 break; 382 case '*': 383 case '+': 384 case '?': 385 SETERROR(REG_BADRPT); 386 break; 387 case '.': 388 if (p->g->cflags®_NEWLINE) 389 nonnewline(p); 390 else 391 EMIT(OANY, 0); 392 break; 393 case '[': 394 p_bracket(p); 395 break; 396 case '\\': 397 (void) REQUIRE(MORE(), REG_EESCAPE); 398 wc = WGETNEXT(); 399 ordinary(p, wc); 400 break; 401 case '{': /* okay as ordinary except if digit follows */ 402 (void) REQUIRE(!MORE() || !isdigit((uch)PEEK()), REG_BADRPT); 403 /* FALLTHROUGH */ 404 default: 405 p->next--; 406 wc = WGETNEXT(); 407 ordinary(p, wc); 408 break; 409 } 410 411 if (!MORE()) 412 return; 413 c = PEEK(); 414 /* we call { a repetition if followed by a digit */ 415 if (!(c == '*' || c == '+' || c == '?' || 416 (c == '{' && MORE2() && isdigit((uch)PEEK2())))) 417 return; /* no repetition, we're done */ 418 NEXT(); 419 420 (void) REQUIRE(!wascaret, REG_BADRPT); 421 switch (c) { 422 case '*': /* implemented as +? */ 423 /* this case does not require the (y|) trick, noKLUDGE */ 424 INSERT(OPLUS_, pos); 425 ASTERN(O_PLUS, pos); 426 INSERT(OQUEST_, pos); 427 ASTERN(O_QUEST, pos); 428 break; 429 case '+': 430 INSERT(OPLUS_, pos); 431 ASTERN(O_PLUS, pos); 432 break; 433 case '?': 434 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 435 INSERT(OCH_, pos); /* offset slightly wrong */ 436 ASTERN(OOR1, pos); /* this one's right */ 437 AHEAD(pos); /* fix the OCH_ */ 438 EMIT(OOR2, 0); /* offset very wrong... */ 439 AHEAD(THERE()); /* ...so fix it */ 440 ASTERN(O_CH, THERETHERE()); 441 break; 442 case '{': 443 count = p_count(p); 444 if (EAT(',')) { 445 if (isdigit((uch)PEEK())) { 446 count2 = p_count(p); 447 (void) REQUIRE(count <= count2, REG_BADBR); 448 } else /* single number with comma */ 449 count2 = INFINITY; 450 } else /* just a single number */ 451 count2 = count; 452 repeat(p, pos, count, count2); 453 if (!EAT('}')) { /* error heuristics */ 454 while (MORE() && PEEK() != '}') 455 NEXT(); 456 (void) REQUIRE(MORE(), REG_EBRACE); 457 SETERROR(REG_BADBR); 458 } 459 break; 460 } 461 462 if (!MORE()) 463 return; 464 c = PEEK(); 465 if (!(c == '*' || c == '+' || c == '?' || 466 (c == '{' && MORE2() && isdigit((uch)PEEK2())))) 467 return; 468 SETERROR(REG_BADRPT); 469 } 470 471 /* 472 * p_str - string (no metacharacters) "parser" 473 */ 474 static void 475 p_str(struct parse *p) 476 { 477 (void) REQUIRE(MORE(), REG_BADPAT); 478 while (MORE()) 479 ordinary(p, WGETNEXT()); 480 } 481 482 /* 483 * p_bre - BRE parser top level, anchoring and concatenation 484 * Giving end1 as OUT essentially eliminates the end1/end2 check. 485 * 486 * This implementation is a bit of a kludge, in that a trailing $ is first 487 * taken as an ordinary character and then revised to be an anchor. 488 * The amount of lookahead needed to avoid this kludge is excessive. 489 */ 490 static void 491 p_bre(struct parse *p, 492 wint_t end1, /* first terminating character */ 493 wint_t end2) /* second terminating character */ 494 { 495 sopno start = HERE(); 496 int first = 1; /* first subexpression? */ 497 int wasdollar = 0; 498 499 if (EAT('^')) { 500 EMIT(OBOL, 0); 501 p->g->iflags |= USEBOL; 502 p->g->nbol++; 503 } 504 while (MORE() && !SEETWO(end1, end2)) { 505 wasdollar = p_simp_re(p, first); 506 first = 0; 507 } 508 if (wasdollar) { /* oops, that was a trailing anchor */ 509 DROP(1); 510 EMIT(OEOL, 0); 511 p->g->iflags |= USEEOL; 512 p->g->neol++; 513 } 514 515 (void) REQUIRE(HERE() != start, REG_BADPAT); /* require nonempty */ 516 } 517 518 /* 519 * p_simp_re - parse a simple RE, an atom possibly followed by a repetition 520 */ 521 static int /* was the simple RE an unbackslashed $? */ 522 p_simp_re(struct parse *p, 523 int starordinary) /* is a leading * an ordinary character? */ 524 { 525 int c; 526 int count; 527 int count2; 528 sopno pos; 529 int i; 530 wint_t wc; 531 sopno subno; 532 #define BACKSL (1<<CHAR_BIT) 533 534 pos = HERE(); /* repetion op, if any, covers from here */ 535 536 assert(MORE()); /* caller should have ensured this */ 537 c = GETNEXT(); 538 if (c == '\\') { 539 (void) REQUIRE(MORE(), REG_EESCAPE); 540 c = BACKSL | GETNEXT(); 541 } 542 switch (c) { 543 case '.': 544 if (p->g->cflags®_NEWLINE) 545 nonnewline(p); 546 else 547 EMIT(OANY, 0); 548 break; 549 case '[': 550 p_bracket(p); 551 break; 552 case BACKSL|'{': 553 SETERROR(REG_BADRPT); 554 break; 555 case BACKSL|'(': 556 p->g->nsub++; 557 subno = p->g->nsub; 558 if (subno < NPAREN) 559 p->pbegin[subno] = HERE(); 560 EMIT(OLPAREN, subno); 561 /* the MORE here is an error heuristic */ 562 if (MORE() && !SEETWO('\\', ')')) 563 p_bre(p, '\\', ')'); 564 if (subno < NPAREN) { 565 p->pend[subno] = HERE(); 566 assert(p->pend[subno] != 0); 567 } 568 EMIT(ORPAREN, subno); 569 (void) REQUIRE(EATTWO('\\', ')'), REG_EPAREN); 570 break; 571 case BACKSL|')': /* should not get here -- must be user */ 572 case BACKSL|'}': 573 SETERROR(REG_EPAREN); 574 break; 575 case BACKSL|'1': 576 case BACKSL|'2': 577 case BACKSL|'3': 578 case BACKSL|'4': 579 case BACKSL|'5': 580 case BACKSL|'6': 581 case BACKSL|'7': 582 case BACKSL|'8': 583 case BACKSL|'9': 584 i = (c&~BACKSL) - '0'; 585 assert(i < NPAREN); 586 if (p->pend[i] != 0) { 587 assert(i <= p->g->nsub); 588 EMIT(OBACK_, i); 589 assert(p->pbegin[i] != 0); 590 assert(OP(p->strip[p->pbegin[i]]) == OLPAREN); 591 assert(OP(p->strip[p->pend[i]]) == ORPAREN); 592 (void) dupl(p, p->pbegin[i]+1, p->pend[i]); 593 EMIT(O_BACK, i); 594 } else 595 SETERROR(REG_ESUBREG); 596 p->g->backrefs = 1; 597 break; 598 case '*': 599 (void) REQUIRE(starordinary, REG_BADRPT); 600 /* FALLTHROUGH */ 601 default: 602 p->next--; 603 wc = WGETNEXT(); 604 ordinary(p, wc); 605 break; 606 } 607 608 if (EAT('*')) { /* implemented as +? */ 609 /* this case does not require the (y|) trick, noKLUDGE */ 610 INSERT(OPLUS_, pos); 611 ASTERN(O_PLUS, pos); 612 INSERT(OQUEST_, pos); 613 ASTERN(O_QUEST, pos); 614 } else if (EATTWO('\\', '{')) { 615 count = p_count(p); 616 if (EAT(',')) { 617 if (MORE() && isdigit((uch)PEEK())) { 618 count2 = p_count(p); 619 (void) REQUIRE(count <= count2, REG_BADBR); 620 } else /* single number with comma */ 621 count2 = INFINITY; 622 } else /* just a single number */ 623 count2 = count; 624 repeat(p, pos, count, count2); 625 if (!EATTWO('\\', '}')) { /* error heuristics */ 626 while (MORE() && !SEETWO('\\', '}')) 627 NEXT(); 628 (void) REQUIRE(MORE(), REG_EBRACE); 629 SETERROR(REG_BADBR); 630 } 631 } else if (c == '$') /* $ (but not \$) ends it */ 632 return (1); 633 634 return (0); 635 } 636 637 /* 638 * p_count - parse a repetition count 639 */ 640 static int /* the value */ 641 p_count(struct parse *p) 642 { 643 int count = 0; 644 int ndigits = 0; 645 646 while (MORE() && isdigit((uch)PEEK()) && count <= DUPMAX) { 647 count = count*10 + (GETNEXT() - '0'); 648 ndigits++; 649 } 650 651 (void) REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR); 652 return (count); 653 } 654 655 /* 656 * p_bracket - parse a bracketed character list 657 */ 658 static void 659 p_bracket(struct parse *p) 660 { 661 cset *cs; 662 wint_t ch; 663 664 /* Dept of Truly Sickening Special-Case Kludges */ 665 if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) { 666 EMIT(OBOW, 0); 667 NEXTn(6); 668 return; 669 } 670 if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) { 671 EMIT(OEOW, 0); 672 NEXTn(6); 673 return; 674 } 675 676 if ((cs = allocset(p)) == NULL) 677 return; 678 679 if (p->g->cflags®_ICASE) 680 cs->icase = 1; 681 if (EAT('^')) 682 cs->invert = 1; 683 if (EAT(']')) 684 CHadd(p, cs, ']'); 685 else if (EAT('-')) 686 CHadd(p, cs, '-'); 687 while (MORE() && PEEK() != ']' && !SEETWO('-', ']')) 688 p_b_term(p, cs); 689 if (EAT('-')) 690 CHadd(p, cs, '-'); 691 (void) MUSTEAT(']', REG_EBRACK); 692 693 if (p->error != 0) /* don't mess things up further */ 694 return; 695 696 if (cs->invert && p->g->cflags®_NEWLINE) 697 cs->bmp['\n' >> 3] |= 1 << ('\n' & 7); 698 699 if ((ch = singleton(cs)) != OUT) { /* optimize singleton sets */ 700 ordinary(p, ch); 701 freeset(p, cs); 702 } else 703 EMIT(OANYOF, (int)(cs - p->g->sets)); 704 } 705 706 /* 707 * p_b_term - parse one term of a bracketed character list 708 */ 709 static void 710 p_b_term(struct parse *p, cset *cs) 711 { 712 char c; 713 wint_t start, finish; 714 wint_t i; 715 716 /* classify what we've got */ 717 switch ((MORE()) ? PEEK() : '\0') { 718 case '[': 719 c = (MORE2()) ? PEEK2() : '\0'; 720 break; 721 case '-': 722 SETERROR(REG_ERANGE); 723 return; /* NOTE RETURN */ 724 break; 725 default: 726 c = '\0'; 727 break; 728 } 729 730 switch (c) { 731 case ':': /* character class */ 732 NEXT2(); 733 (void) REQUIRE(MORE(), REG_EBRACK); 734 c = PEEK(); 735 (void) REQUIRE(c != '-' && c != ']', REG_ECTYPE); 736 p_b_cclass(p, cs); 737 (void) REQUIRE(MORE(), REG_EBRACK); 738 (void) REQUIRE(EATTWO(':', ']'), REG_ECTYPE); 739 break; 740 case '=': /* equivalence class */ 741 NEXT2(); 742 (void) REQUIRE(MORE(), REG_EBRACK); 743 c = PEEK(); 744 (void) REQUIRE(c != '-' && c != ']', REG_ECOLLATE); 745 p_b_eclass(p, cs); 746 (void) REQUIRE(MORE(), REG_EBRACK); 747 (void) REQUIRE(EATTWO('=', ']'), REG_ECOLLATE); 748 break; 749 default: /* symbol, ordinary character, or range */ 750 start = p_b_symbol(p); 751 if (SEE('-') && MORE2() && PEEK2() != ']') { 752 /* range */ 753 NEXT(); 754 if (EAT('-')) 755 finish = '-'; 756 else 757 finish = p_b_symbol(p); 758 } else 759 finish = start; 760 if (start == finish) 761 CHadd(p, cs, start); 762 else { 763 if (__collate_load_error) { 764 (void) REQUIRE((uch)start <= (uch)finish, 765 REG_ERANGE); 766 CHaddrange(p, cs, start, finish); 767 } else { 768 (void) REQUIRE(__collate_range_cmp(start, 769 finish) <= 0, REG_ERANGE); 770 for (i = 0; i <= UCHAR_MAX; i++) { 771 if (__collate_range_cmp(start, i) <= 772 0 && 773 __collate_range_cmp(i, finish) <= 774 0) 775 CHadd(p, cs, i); 776 } 777 } 778 } 779 break; 780 } 781 } 782 783 /* 784 * p_b_cclass - parse a character-class name and deal with it 785 */ 786 static void 787 p_b_cclass(struct parse *p, cset *cs) 788 { 789 char *sp = p->next; 790 size_t len; 791 wctype_t wct; 792 char clname[16]; 793 794 while (MORE() && isalpha((uch)PEEK())) 795 NEXT(); 796 len = p->next - sp; 797 if (len >= sizeof (clname) - 1) { 798 SETERROR(REG_ECTYPE); 799 return; 800 } 801 (void) memcpy(clname, sp, len); 802 clname[len] = '\0'; 803 if ((wct = wctype(clname)) == 0) { 804 SETERROR(REG_ECTYPE); 805 return; 806 } 807 CHaddtype(p, cs, wct); 808 } 809 810 /* 811 * p_b_eclass - parse an equivalence-class name and deal with it 812 * 813 * This implementation is incomplete. xxx 814 */ 815 static void 816 p_b_eclass(struct parse *p, cset *cs) 817 { 818 wint_t c; 819 820 c = p_b_coll_elem(p, '='); 821 CHadd(p, cs, c); 822 } 823 824 /* 825 * p_b_symbol - parse a character or [..]ed multicharacter collating symbol 826 */ 827 static wint_t /* value of symbol */ 828 p_b_symbol(struct parse *p) 829 { 830 wint_t value; 831 832 (void) REQUIRE(MORE(), REG_EBRACK); 833 if (!EATTWO('[', '.')) 834 return (WGETNEXT()); 835 836 /* collating symbol */ 837 value = p_b_coll_elem(p, '.'); 838 (void) REQUIRE(EATTWO('.', ']'), REG_ECOLLATE); 839 return (value); 840 } 841 842 /* 843 * p_b_coll_elem - parse a collating-element name and look it up 844 */ 845 static wint_t /* value of collating element */ 846 p_b_coll_elem(struct parse *p, 847 wint_t endc) /* name ended by endc,']' */ 848 { 849 char *sp = p->next; 850 struct cname *cp; 851 int len; 852 mbstate_t mbs; 853 wchar_t wc; 854 size_t clen; 855 856 while (MORE() && !SEETWO(endc, ']')) 857 NEXT(); 858 if (!MORE()) { 859 SETERROR(REG_EBRACK); 860 return (0); 861 } 862 len = p->next - sp; 863 for (cp = cnames; cp->name != NULL; cp++) 864 if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0') 865 return (cp->code); /* known name */ 866 (void) memset(&mbs, 0, sizeof (mbs)); 867 if ((clen = mbrtowc(&wc, sp, len, &mbs)) == len) 868 return (wc); /* single character */ 869 else if (clen == (size_t)-1 || clen == (size_t)-2) 870 SETERROR(REG_ECHAR); 871 else 872 SETERROR(REG_ECOLLATE); /* neither */ 873 return (0); 874 } 875 876 /* 877 * othercase - return the case counterpart of an alphabetic 878 */ 879 static wint_t /* if no counterpart, return ch */ 880 othercase(wint_t ch) 881 { 882 assert(iswalpha(ch)); 883 if (iswupper(ch)) 884 return (towlower(ch)); 885 else if (iswlower(ch)) 886 return (towupper(ch)); 887 else /* peculiar, but could happen */ 888 return (ch); 889 } 890 891 /* 892 * bothcases - emit a dualcase version of a two-case character 893 * 894 * Boy, is this implementation ever a kludge... 895 */ 896 static void 897 bothcases(struct parse *p, wint_t ch) 898 { 899 char *oldnext = p->next; 900 char *oldend = p->end; 901 char bracket[3 + MB_LEN_MAX]; 902 size_t n; 903 mbstate_t mbs; 904 905 assert(othercase(ch) != ch); /* p_bracket() would recurse */ 906 p->next = bracket; 907 (void) memset(&mbs, 0, sizeof (mbs)); 908 n = wcrtomb(bracket, ch, &mbs); 909 assert(n != (size_t)-1); 910 bracket[n] = ']'; 911 bracket[n + 1] = '\0'; 912 p->end = bracket+n+1; 913 p_bracket(p); 914 assert(p->next == p->end); 915 p->next = oldnext; 916 p->end = oldend; 917 } 918 919 /* 920 * ordinary - emit an ordinary character 921 */ 922 static void 923 ordinary(struct parse *p, wint_t ch) 924 { 925 cset *cs; 926 927 if ((p->g->cflags®_ICASE) && iswalpha(ch) && othercase(ch) != ch) 928 bothcases(p, ch); 929 else if ((ch & OPDMASK) == ch) 930 EMIT(OCHAR, ch); 931 else { 932 /* 933 * Kludge: character is too big to fit into an OCHAR operand. 934 * Emit a singleton set. 935 */ 936 if ((cs = allocset(p)) == NULL) 937 return; 938 CHadd(p, cs, ch); 939 EMIT(OANYOF, (int)(cs - p->g->sets)); 940 } 941 } 942 943 /* 944 * nonnewline - emit REG_NEWLINE version of OANY 945 * 946 * Boy, is this implementation ever a kludge... 947 */ 948 static void 949 nonnewline(struct parse *p) 950 { 951 char *oldnext = p->next; 952 char *oldend = p->end; 953 char bracket[4]; 954 955 p->next = bracket; 956 p->end = bracket+3; 957 bracket[0] = '^'; 958 bracket[1] = '\n'; 959 bracket[2] = ']'; 960 bracket[3] = '\0'; 961 p_bracket(p); 962 assert(p->next == bracket+3); 963 p->next = oldnext; 964 p->end = oldend; 965 } 966 967 /* 968 * repeat - generate code for a bounded repetition, recursively if needed 969 */ 970 static void 971 repeat(struct parse *p, 972 sopno start, /* operand from here to end of strip */ 973 int from, /* repeated from this number */ 974 int to) /* to this number of times (maybe INFINITY) */ 975 { 976 sopno finish = HERE(); 977 #define N 2 978 #define INF 3 979 #define REP(f, t) ((f)*8 + (t)) 980 #define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N) 981 sopno copy; 982 983 if (p->error != 0) /* head off possible runaway recursion */ 984 return; 985 986 assert(from <= to); 987 988 switch (REP(MAP(from), MAP(to))) { 989 case REP(0, 0): /* must be user doing this */ 990 DROP(finish-start); /* drop the operand */ 991 break; 992 case REP(0, 1): /* as x{1,1}? */ 993 case REP(0, N): /* as x{1,n}? */ 994 case REP(0, INF): /* as x{1,}? */ 995 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 996 INSERT(OCH_, start); /* offset is wrong... */ 997 repeat(p, start+1, 1, to); 998 ASTERN(OOR1, start); 999 AHEAD(start); /* ... fix it */ 1000 EMIT(OOR2, 0); 1001 AHEAD(THERE()); 1002 ASTERN(O_CH, THERETHERE()); 1003 break; 1004 case REP(1, 1): /* trivial case */ 1005 /* done */ 1006 break; 1007 case REP(1, N): /* as x?x{1,n-1} */ 1008 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 1009 INSERT(OCH_, start); 1010 ASTERN(OOR1, start); 1011 AHEAD(start); 1012 EMIT(OOR2, 0); /* offset very wrong... */ 1013 AHEAD(THERE()); /* ...so fix it */ 1014 ASTERN(O_CH, THERETHERE()); 1015 copy = dupl(p, start+1, finish+1); 1016 assert(copy == finish+4); 1017 repeat(p, copy, 1, to-1); 1018 break; 1019 case REP(1, INF): /* as x+ */ 1020 INSERT(OPLUS_, start); 1021 ASTERN(O_PLUS, start); 1022 break; 1023 case REP(N, N): /* as xx{m-1,n-1} */ 1024 copy = dupl(p, start, finish); 1025 repeat(p, copy, from-1, to-1); 1026 break; 1027 case REP(N, INF): /* as xx{n-1,INF} */ 1028 copy = dupl(p, start, finish); 1029 repeat(p, copy, from-1, to); 1030 break; 1031 default: /* "can't happen" */ 1032 SETERROR(REG_EFATAL); /* just in case */ 1033 break; 1034 } 1035 } 1036 1037 /* 1038 * wgetnext - helper function for WGETNEXT() macro. Gets the next wide 1039 * character from the parse struct, signals a REG_ILLSEQ error if the 1040 * character can't be converted. Returns the number of bytes consumed. 1041 */ 1042 static wint_t 1043 wgetnext(struct parse *p) 1044 { 1045 mbstate_t mbs; 1046 wchar_t wc; 1047 size_t n; 1048 1049 (void) memset(&mbs, 0, sizeof (mbs)); 1050 n = mbrtowc(&wc, p->next, p->end - p->next, &mbs); 1051 if (n == (size_t)-1 || n == (size_t)-2) { 1052 SETERROR(REG_ECHAR); 1053 return (0); 1054 } 1055 if (n == 0) 1056 n = 1; 1057 p->next += n; 1058 return (wc); 1059 } 1060 1061 /* 1062 * seterr - set an error condition 1063 */ 1064 static int /* useless but makes type checking happy */ 1065 seterr(struct parse *p, int e) 1066 { 1067 if (p->error == 0) /* keep earliest error condition */ 1068 p->error = e; 1069 p->next = nuls; /* try to bring things to a halt */ 1070 p->end = nuls; 1071 return (0); /* make the return value well-defined */ 1072 } 1073 1074 /* 1075 * allocset - allocate a set of characters for [] 1076 */ 1077 static cset * 1078 allocset(struct parse *p) 1079 { 1080 cset *cs, *ncs; 1081 1082 ncs = realloc(p->g->sets, (p->g->ncsets + 1) * sizeof (*ncs)); 1083 if (ncs == NULL) { 1084 SETERROR(REG_ESPACE); 1085 return (NULL); 1086 } 1087 p->g->sets = ncs; 1088 cs = &p->g->sets[p->g->ncsets++]; 1089 (void) memset(cs, 0, sizeof (*cs)); 1090 1091 return (cs); 1092 } 1093 1094 /* 1095 * freeset - free a now-unused set 1096 */ 1097 static void 1098 freeset(struct parse *p, cset *cs) 1099 { 1100 cset *top = &p->g->sets[p->g->ncsets]; 1101 1102 free(cs->wides); 1103 free(cs->ranges); 1104 free(cs->types); 1105 (void) memset(cs, 0, sizeof (*cs)); 1106 if (cs == top-1) /* recover only the easy case */ 1107 p->g->ncsets--; 1108 } 1109 1110 /* 1111 * singleton - Determine whether a set contains only one character, 1112 * returning it if so, otherwise returning OUT. 1113 */ 1114 static wint_t 1115 singleton(cset *cs) 1116 { 1117 wint_t i, s, n; 1118 1119 for (i = n = 0; i < NC; i++) 1120 if (CHIN(cs, i)) { 1121 n++; 1122 s = i; 1123 } 1124 if (n == 1) 1125 return (s); 1126 if (cs->nwides == 1 && cs->nranges == 0 && cs->ntypes == 0 && 1127 cs->icase == 0) 1128 return (cs->wides[0]); 1129 /* Don't bother handling the other cases. */ 1130 return (OUT); 1131 } 1132 1133 /* 1134 * CHadd - add character to character set. 1135 */ 1136 static void 1137 CHadd(struct parse *p, cset *cs, wint_t ch) 1138 { 1139 wint_t nch, *newwides; 1140 assert(ch >= 0); 1141 if (ch < NC) 1142 cs->bmp[ch >> 3] |= 1 << (ch & 7); 1143 else { 1144 newwides = realloc(cs->wides, (cs->nwides + 1) * 1145 sizeof (*cs->wides)); 1146 if (newwides == NULL) { 1147 SETERROR(REG_ESPACE); 1148 return; 1149 } 1150 cs->wides = newwides; 1151 cs->wides[cs->nwides++] = ch; 1152 } 1153 if (cs->icase) { 1154 if ((nch = towlower(ch)) < NC) 1155 cs->bmp[nch >> 3] |= 1 << (nch & 7); 1156 if ((nch = towupper(ch)) < NC) 1157 cs->bmp[nch >> 3] |= 1 << (nch & 7); 1158 } 1159 } 1160 1161 /* 1162 * CHaddrange - add all characters in the range [min,max] to a character set. 1163 */ 1164 static void 1165 CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max) 1166 { 1167 crange *newranges; 1168 1169 for (; min < NC && min <= max; min++) 1170 CHadd(p, cs, min); 1171 if (min >= max) 1172 return; 1173 newranges = realloc(cs->ranges, (cs->nranges + 1) * 1174 sizeof (*cs->ranges)); 1175 if (newranges == NULL) { 1176 SETERROR(REG_ESPACE); 1177 return; 1178 } 1179 cs->ranges = newranges; 1180 cs->ranges[cs->nranges].min = min; 1181 cs->ranges[cs->nranges].min = max; 1182 cs->nranges++; 1183 } 1184 1185 /* 1186 * CHaddtype - add all characters of a certain type to a character set. 1187 */ 1188 static void 1189 CHaddtype(struct parse *p, cset *cs, wctype_t wct) 1190 { 1191 wint_t i; 1192 wctype_t *newtypes; 1193 1194 for (i = 0; i < NC; i++) 1195 if (iswctype(i, wct)) 1196 CHadd(p, cs, i); 1197 newtypes = realloc(cs->types, (cs->ntypes + 1) * 1198 sizeof (*cs->types)); 1199 if (newtypes == NULL) { 1200 SETERROR(REG_ESPACE); 1201 return; 1202 } 1203 cs->types = newtypes; 1204 cs->types[cs->ntypes++] = wct; 1205 } 1206 1207 /* 1208 * dupl - emit a duplicate of a bunch of sops 1209 */ 1210 static sopno /* start of duplicate */ 1211 dupl(struct parse *p, 1212 sopno start, /* from here */ 1213 sopno finish) /* to this less one */ 1214 { 1215 sopno ret = HERE(); 1216 sopno len = finish - start; 1217 1218 assert(finish >= start); 1219 if (len == 0) 1220 return (ret); 1221 enlarge(p, p->ssize + len); /* this many unexpected additions */ 1222 assert(p->ssize >= p->slen + len); 1223 (void) memcpy((char *)(p->strip + p->slen), 1224 (char *)(p->strip + start), (size_t)len*sizeof (sop)); 1225 p->slen += len; 1226 return (ret); 1227 } 1228 1229 /* 1230 * doemit - emit a strip operator 1231 * 1232 * It might seem better to implement this as a macro with a function as 1233 * hard-case backup, but it's just too big and messy unless there are 1234 * some changes to the data structures. Maybe later. 1235 */ 1236 static void 1237 doemit(struct parse *p, sop op, size_t opnd) 1238 { 1239 /* avoid making error situations worse */ 1240 if (p->error != 0) 1241 return; 1242 1243 /* deal with oversize operands ("can't happen", more or less) */ 1244 assert(opnd < 1<<OPSHIFT); 1245 1246 /* deal with undersized strip */ 1247 if (p->slen >= p->ssize) 1248 enlarge(p, (p->ssize+1) / 2 * 3); /* +50% */ 1249 assert(p->slen < p->ssize); 1250 1251 /* finally, it's all reduced to the easy case */ 1252 p->strip[p->slen++] = SOP(op, opnd); 1253 } 1254 1255 /* 1256 * doinsert - insert a sop into the strip 1257 */ 1258 static void 1259 doinsert(struct parse *p, sop op, size_t opnd, sopno pos) 1260 { 1261 sopno sn; 1262 sop s; 1263 int i; 1264 1265 /* avoid making error situations worse */ 1266 if (p->error != 0) 1267 return; 1268 1269 sn = HERE(); 1270 EMIT(op, opnd); /* do checks, ensure space */ 1271 assert(HERE() == sn+1); 1272 s = p->strip[sn]; 1273 1274 /* adjust paren pointers */ 1275 assert(pos > 0); 1276 for (i = 1; i < NPAREN; i++) { 1277 if (p->pbegin[i] >= pos) { 1278 p->pbegin[i]++; 1279 } 1280 if (p->pend[i] >= pos) { 1281 p->pend[i]++; 1282 } 1283 } 1284 1285 (void) memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos], 1286 (HERE()-pos-1)*sizeof (sop)); 1287 p->strip[pos] = s; 1288 } 1289 1290 /* 1291 * dofwd - complete a forward reference 1292 */ 1293 static void 1294 dofwd(struct parse *p, sopno pos, sop value) 1295 { 1296 /* avoid making error situations worse */ 1297 if (p->error != 0) 1298 return; 1299 1300 assert(value < 1<<OPSHIFT); 1301 p->strip[pos] = OP(p->strip[pos]) | value; 1302 } 1303 1304 /* 1305 * enlarge - enlarge the strip 1306 */ 1307 static void 1308 enlarge(struct parse *p, sopno size) 1309 { 1310 sop *sp; 1311 1312 if (p->ssize >= size) 1313 return; 1314 1315 sp = (sop *)realloc(p->strip, size*sizeof (sop)); 1316 if (sp == NULL) { 1317 SETERROR(REG_ESPACE); 1318 return; 1319 } 1320 p->strip = sp; 1321 p->ssize = size; 1322 } 1323 1324 /* 1325 * stripsnug - compact the strip 1326 */ 1327 static void 1328 stripsnug(struct parse *p, struct re_guts *g) 1329 { 1330 g->nstates = p->slen; 1331 g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof (sop)); 1332 if (g->strip == NULL) { 1333 SETERROR(REG_ESPACE); 1334 g->strip = p->strip; 1335 } 1336 } 1337 1338 /* 1339 * findmust - fill in must and mlen with longest mandatory literal string 1340 * 1341 * This algorithm could do fancy things like analyzing the operands of | 1342 * for common subsequences. Someday. This code is simple and finds most 1343 * of the interesting cases. 1344 * 1345 * Note that must and mlen got initialized during setup. 1346 */ 1347 static void 1348 findmust(struct parse *p, struct re_guts *g) 1349 { 1350 sop *scan; 1351 sop *start; 1352 sop *newstart; 1353 sopno newlen; 1354 sop s; 1355 char *cp; 1356 int offset; 1357 char buf[MB_LEN_MAX]; 1358 size_t clen; 1359 mbstate_t mbs; 1360 1361 /* avoid making error situations worse */ 1362 if (p->error != 0) 1363 return; 1364 1365 /* 1366 * It's not generally safe to do a ``char'' substring search on 1367 * multibyte character strings, but it's safe for at least 1368 * UTF-8 (see RFC 3629). 1369 */ 1370 if (MB_CUR_MAX > 1 && 1371 strcmp(_CurrentRuneLocale->__encoding, "UTF-8") != 0) 1372 return; 1373 1374 /* find the longest OCHAR sequence in strip */ 1375 newlen = 0; 1376 offset = 0; 1377 g->moffset = 0; 1378 scan = g->strip + 1; 1379 do { 1380 s = *scan++; 1381 switch (OP(s)) { 1382 case OCHAR: /* sequence member */ 1383 if (newlen == 0) { /* new sequence */ 1384 (void) memset(&mbs, 0, sizeof (mbs)); 1385 newstart = scan - 1; 1386 } 1387 clen = wcrtomb(buf, OPND(s), &mbs); 1388 if (clen == (size_t)-1) 1389 goto toohard; 1390 newlen += clen; 1391 break; 1392 case OPLUS_: /* things that don't break one */ 1393 case OLPAREN: 1394 case ORPAREN: 1395 break; 1396 case OQUEST_: /* things that must be skipped */ 1397 case OCH_: 1398 offset = altoffset(scan, offset); 1399 scan--; 1400 do { 1401 scan += OPND(s); 1402 s = *scan; 1403 /* assert() interferes w debug printouts */ 1404 if (OP(s) != O_QUEST && OP(s) != O_CH && 1405 OP(s) != OOR2) { 1406 g->iflags |= BAD; 1407 return; 1408 } 1409 } while (OP(s) != O_QUEST && OP(s) != O_CH); 1410 /* FALLTHROUGH */ 1411 case OBOW: /* things that break a sequence */ 1412 case OEOW: 1413 case OBOL: 1414 case OEOL: 1415 case O_QUEST: 1416 case O_CH: 1417 case OEND: 1418 if (newlen > g->mlen) { /* ends one */ 1419 start = newstart; 1420 g->mlen = newlen; 1421 if (offset > -1) { 1422 g->moffset += offset; 1423 offset = newlen; 1424 } else 1425 g->moffset = offset; 1426 } else { 1427 if (offset > -1) 1428 offset += newlen; 1429 } 1430 newlen = 0; 1431 break; 1432 case OANY: 1433 if (newlen > g->mlen) { /* ends one */ 1434 start = newstart; 1435 g->mlen = newlen; 1436 if (offset > -1) { 1437 g->moffset += offset; 1438 offset = newlen; 1439 } else 1440 g->moffset = offset; 1441 } else { 1442 if (offset > -1) 1443 offset += newlen; 1444 } 1445 if (offset > -1) 1446 offset++; 1447 newlen = 0; 1448 break; 1449 case OANYOF: /* may or may not invalidate offset */ 1450 /* First, everything as OANY */ 1451 if (newlen > g->mlen) { /* ends one */ 1452 start = newstart; 1453 g->mlen = newlen; 1454 if (offset > -1) { 1455 g->moffset += offset; 1456 offset = newlen; 1457 } else 1458 g->moffset = offset; 1459 } else { 1460 if (offset > -1) 1461 offset += newlen; 1462 } 1463 if (offset > -1) 1464 offset++; 1465 newlen = 0; 1466 break; 1467 toohard: 1468 default: 1469 /* 1470 * Anything here makes it impossible or too hard 1471 * to calculate the offset -- so we give up; 1472 * save the last known good offset, in case the 1473 * must sequence doesn't occur later. 1474 */ 1475 if (newlen > g->mlen) { /* ends one */ 1476 start = newstart; 1477 g->mlen = newlen; 1478 if (offset > -1) 1479 g->moffset += offset; 1480 else 1481 g->moffset = offset; 1482 } 1483 offset = -1; 1484 newlen = 0; 1485 break; 1486 } 1487 } while (OP(s) != OEND); 1488 1489 if (g->mlen == 0) { /* there isn't one */ 1490 g->moffset = -1; 1491 return; 1492 } 1493 1494 /* turn it into a character string */ 1495 g->must = malloc((size_t)g->mlen + 1); 1496 if (g->must == NULL) { /* argh; just forget it */ 1497 g->mlen = 0; 1498 g->moffset = -1; 1499 return; 1500 } 1501 cp = g->must; 1502 scan = start; 1503 (void) memset(&mbs, 0, sizeof (mbs)); 1504 while (cp < g->must + g->mlen) { 1505 while (OP(s = *scan++) != OCHAR) 1506 continue; 1507 clen = wcrtomb(cp, OPND(s), &mbs); 1508 assert(clen != (size_t)-1); 1509 cp += clen; 1510 } 1511 assert(cp == g->must + g->mlen); 1512 *cp++ = '\0'; /* just on general principles */ 1513 } 1514 1515 /* 1516 * altoffset - choose biggest offset among multiple choices 1517 * 1518 * Compute, recursively if necessary, the largest offset among multiple 1519 * re paths. 1520 */ 1521 static int 1522 altoffset(sop *scan, int offset) 1523 { 1524 int largest; 1525 int try; 1526 sop s; 1527 1528 /* If we gave up already on offsets, return */ 1529 if (offset == -1) 1530 return (-1); 1531 1532 largest = 0; 1533 try = 0; 1534 s = *scan++; 1535 while (OP(s) != O_QUEST && OP(s) != O_CH) { 1536 switch (OP(s)) { 1537 case OOR1: 1538 if (try > largest) 1539 largest = try; 1540 try = 0; 1541 break; 1542 case OQUEST_: 1543 case OCH_: 1544 try = altoffset(scan, try); 1545 if (try == -1) 1546 return (-1); 1547 scan--; 1548 do { 1549 scan += OPND(s); 1550 s = *scan; 1551 if (OP(s) != O_QUEST && OP(s) != O_CH && 1552 OP(s) != OOR2) 1553 return (-1); 1554 } while (OP(s) != O_QUEST && OP(s) != O_CH); 1555 /* 1556 * We must skip to the next position, or we'll 1557 * leave altoffset() too early. 1558 */ 1559 scan++; 1560 break; 1561 case OANYOF: 1562 case OCHAR: 1563 case OANY: 1564 try++; 1565 /*FALLTHRU*/ 1566 case OBOW: 1567 case OEOW: 1568 case OLPAREN: 1569 case ORPAREN: 1570 case OOR2: 1571 break; 1572 default: 1573 try = -1; 1574 break; 1575 } 1576 if (try == -1) 1577 return (-1); 1578 s = *scan++; 1579 } 1580 1581 if (try > largest) 1582 largest = try; 1583 1584 return (largest+offset); 1585 } 1586 1587 /* 1588 * computejumps - compute char jumps for BM scan 1589 * 1590 * This algorithm assumes g->must exists and is has size greater than 1591 * zero. It's based on the algorithm found on Computer Algorithms by 1592 * Sara Baase. 1593 * 1594 * A char jump is the number of characters one needs to jump based on 1595 * the value of the character from the text that was mismatched. 1596 */ 1597 static void 1598 computejumps(struct parse *p, struct re_guts *g) 1599 { 1600 int ch; 1601 int mindex; 1602 1603 /* Avoid making errors worse */ 1604 if (p->error != 0) 1605 return; 1606 1607 g->charjump = (int *)malloc((NC + 1) * sizeof (int)); 1608 if (g->charjump == NULL) /* Not a fatal error */ 1609 return; 1610 /* Adjust for signed chars, if necessary */ 1611 g->charjump = &g->charjump[-(CHAR_MIN)]; 1612 1613 /* 1614 * If the character does not exist in the pattern, the jump 1615 * is equal to the number of characters in the pattern. 1616 */ 1617 for (ch = CHAR_MIN; ch < (CHAR_MAX + 1); ch++) 1618 g->charjump[ch] = g->mlen; 1619 1620 /* 1621 * If the character does exist, compute the jump that would 1622 * take us to the last character in the pattern equal to it 1623 * (notice that we match right to left, so that last character 1624 * is the first one that would be matched). 1625 */ 1626 for (mindex = 0; mindex < g->mlen; mindex++) 1627 g->charjump[(int)g->must[mindex]] = g->mlen - mindex - 1; 1628 } 1629 1630 /* 1631 * computematchjumps - compute match jumps for BM scan 1632 * 1633 * This algorithm assumes g->must exists and is has size greater than 1634 * zero. It's based on the algorithm found on Computer Algorithms by 1635 * Sara Baase. 1636 * 1637 * A match jump is the number of characters one needs to advance based 1638 * on the already-matched suffix. 1639 * Notice that all values here are minus (g->mlen-1), because of the way 1640 * the search algorithm works. 1641 */ 1642 static void 1643 computematchjumps(struct parse *p, struct re_guts *g) 1644 { 1645 int mindex; /* General "must" iterator */ 1646 int suffix; /* Keeps track of matching suffix */ 1647 int ssuffix; /* Keeps track of suffixes' suffix */ 1648 int *pmatches; 1649 /* 1650 * pmatches[k] points to the next i 1651 * such that i+1...mlen is a substring 1652 * of k+1...k+mlen-i-1 1653 */ 1654 1655 /* Avoid making errors worse */ 1656 if (p->error != 0) 1657 return; 1658 1659 pmatches = (int *)malloc(g->mlen * sizeof (unsigned int)); 1660 if (pmatches == NULL) { 1661 g->matchjump = NULL; 1662 return; 1663 } 1664 1665 g->matchjump = (int *)malloc(g->mlen * sizeof (unsigned int)); 1666 if (g->matchjump == NULL) /* Not a fatal error */ 1667 return; 1668 1669 /* Set maximum possible jump for each character in the pattern */ 1670 for (mindex = 0; mindex < g->mlen; mindex++) 1671 g->matchjump[mindex] = 2*g->mlen - mindex - 1; 1672 1673 /* Compute pmatches[] */ 1674 for (mindex = g->mlen - 1, suffix = g->mlen; mindex >= 0; 1675 mindex--, suffix--) { 1676 pmatches[mindex] = suffix; 1677 1678 /* 1679 * If a mismatch is found, interrupting the substring, 1680 * compute the matchjump for that position. If no 1681 * mismatch is found, then a text substring mismatched 1682 * against the suffix will also mismatch against the 1683 * substring. 1684 */ 1685 while (suffix < g->mlen && g->must[mindex] != g->must[suffix]) { 1686 g->matchjump[suffix] = MIN(g->matchjump[suffix], 1687 g->mlen - mindex - 1); 1688 suffix = pmatches[suffix]; 1689 } 1690 } 1691 1692 /* 1693 * Compute the matchjump up to the last substring found to jump 1694 * to the beginning of the largest must pattern prefix matching 1695 * it's own suffix. 1696 */ 1697 for (mindex = 0; mindex <= suffix; mindex++) 1698 g->matchjump[mindex] = MIN(g->matchjump[mindex], 1699 g->mlen + suffix - mindex); 1700 1701 ssuffix = pmatches[suffix]; 1702 while (suffix < g->mlen) { 1703 while (suffix <= ssuffix && suffix < g->mlen) { 1704 g->matchjump[suffix] = MIN(g->matchjump[suffix], 1705 g->mlen + ssuffix - suffix); 1706 suffix++; 1707 } 1708 if (suffix < g->mlen) 1709 ssuffix = pmatches[ssuffix]; 1710 } 1711 1712 free(pmatches); 1713 } 1714 1715 /* 1716 * pluscount - count + nesting 1717 */ 1718 static sopno /* nesting depth */ 1719 pluscount(struct parse *p, struct re_guts *g) 1720 { 1721 sop *scan; 1722 sop s; 1723 sopno plusnest = 0; 1724 sopno maxnest = 0; 1725 1726 if (p->error != 0) 1727 return (0); /* there may not be an OEND */ 1728 1729 scan = g->strip + 1; 1730 do { 1731 s = *scan++; 1732 switch (OP(s)) { 1733 case OPLUS_: 1734 plusnest++; 1735 break; 1736 case O_PLUS: 1737 if (plusnest > maxnest) 1738 maxnest = plusnest; 1739 plusnest--; 1740 break; 1741 } 1742 } while (OP(s) != OEND); 1743 if (plusnest != 0) 1744 g->iflags |= BAD; 1745 return (maxnest); 1746 } 1747