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