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 * 4. 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) 42static 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: stable/10/lib/libc/regex/regcomp.c 325394 2017-11-04 14:45:36Z pfg $"); 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 */ 68struct 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 84extern "C" { 85#endif 86 87/* === regcomp.c === */ 88static void p_ere(struct parse *p, int stop); 89static void p_ere_exp(struct parse *p); 90static void p_str(struct parse *p); 91static void p_bre(struct parse *p, int end1, int end2); 92static int p_simp_re(struct parse *p, int starordinary); 93static int p_count(struct parse *p); 94static void p_bracket(struct parse *p); 95static void p_b_term(struct parse *p, cset *cs); 96static void p_b_cclass(struct parse *p, cset *cs); 97static void p_b_eclass(struct parse *p, cset *cs); 98static wint_t p_b_symbol(struct parse *p); 99static wint_t p_b_coll_elem(struct parse *p, wint_t endc); 100static wint_t othercase(wint_t ch); 101static void bothcases(struct parse *p, wint_t ch); 102static void ordinary(struct parse *p, wint_t ch); 103static void nonnewline(struct parse *p); 104static void repeat(struct parse *p, sopno start, int from, int to); 105static int seterr(struct parse *p, int e); 106static cset *allocset(struct parse *p); 107static void freeset(struct parse *p, cset *cs); 108static void CHadd(struct parse *p, cset *cs, wint_t ch); 109static void CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max); 110static void CHaddtype(struct parse *p, cset *cs, wctype_t wct); 111static wint_t singleton(cset *cs); 112static sopno dupl(struct parse *p, sopno start, sopno finish); 113static void doemit(struct parse *p, sop op, size_t opnd); 114static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos); 115static void dofwd(struct parse *p, sopno pos, sop value); 116static int enlarge(struct parse *p, sopno size); 117static void stripsnug(struct parse *p, struct re_guts *g); 118static void findmust(struct parse *p, struct re_guts *g); 119static int altoffset(sop *scan, int offset); 120static void computejumps(struct parse *p, struct re_guts *g); 121static void computematchjumps(struct parse *p, struct re_guts *g); 122static sopno pluscount(struct parse *p, struct re_guts *g); 123static wint_t wgetnext(struct parse *p); 124 125#ifdef __cplusplus 126} 127#endif 128/* ========= end header generated by ./mkh ========= */ 129 130static 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 164static 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 */ 184int /* 0 success, otherwise REG_something */ 185regcomp(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 */ 311static void 312p_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 */ 356static void 357p_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 if (p->error != 0) 448 return; 449 p->next--; 450 wc = WGETNEXT(); 451 ordinary(p, wc); 452 break; 453 } 454 455 if (!MORE()) 456 return; 457 c = PEEK(); 458 /* we call { a repetition if followed by a digit */ 459 if (!( c == '*' || c == '+' || c == '?' || 460 (c == '{' && MORE2() && isdigit((uch)PEEK2())) )) 461 return; /* no repetition, we're done */ 462 NEXT(); 463 464 (void)REQUIRE(!wascaret, REG_BADRPT); 465 switch (c) { 466 case '*': /* implemented as +? */ 467 /* this case does not require the (y|) trick, noKLUDGE */ 468 INSERT(OPLUS_, pos); 469 ASTERN(O_PLUS, pos); 470 INSERT(OQUEST_, pos); 471 ASTERN(O_QUEST, pos); 472 break; 473 case '+': 474 INSERT(OPLUS_, pos); 475 ASTERN(O_PLUS, pos); 476 break; 477 case '?': 478 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 479 INSERT(OCH_, pos); /* offset slightly wrong */ 480 ASTERN(OOR1, pos); /* this one's right */ 481 AHEAD(pos); /* fix the OCH_ */ 482 EMIT(OOR2, 0); /* offset very wrong... */ 483 AHEAD(THERE()); /* ...so fix it */ 484 ASTERN(O_CH, THERETHERE()); 485 break; 486 case '{': 487 count = p_count(p); 488 if (EAT(',')) { 489 if (isdigit((uch)PEEK())) { 490 count2 = p_count(p); 491 (void)REQUIRE(count <= count2, REG_BADBR); 492 } else /* single number with comma */ 493 count2 = INFINITY; 494 } else /* just a single number */ 495 count2 = count; 496 repeat(p, pos, count, count2); 497 if (!EAT('}')) { /* error heuristics */ 498 while (MORE() && PEEK() != '}') 499 NEXT(); 500 (void)REQUIRE(MORE(), REG_EBRACE); 501 SETERROR(REG_BADBR); 502 } 503 break; 504 } 505 506 if (!MORE()) 507 return; 508 c = PEEK(); 509 if (!( c == '*' || c == '+' || c == '?' || 510 (c == '{' && MORE2() && isdigit((uch)PEEK2())) ) ) 511 return; 512 SETERROR(REG_BADRPT); 513} 514 515/* 516 - p_str - string (no metacharacters) "parser" 517 == static void p_str(struct parse *p); 518 */ 519static void 520p_str(struct parse *p) 521{ 522 (void)REQUIRE(MORE(), REG_EMPTY); 523 while (MORE()) 524 ordinary(p, WGETNEXT()); 525} 526 527/* 528 - p_bre - BRE parser top level, anchoring and concatenation 529 == static void p_bre(struct parse *p, int end1, \ 530 == int end2); 531 * Giving end1 as OUT essentially eliminates the end1/end2 check. 532 * 533 * This implementation is a bit of a kludge, in that a trailing $ is first 534 * taken as an ordinary character and then revised to be an anchor. 535 * The amount of lookahead needed to avoid this kludge is excessive. 536 */ 537static void 538p_bre(struct parse *p, 539 int end1, /* first terminating character */ 540 int end2) /* second terminating character */ 541{ 542 sopno start = HERE(); 543 int first = 1; /* first subexpression? */ 544 int wasdollar = 0; 545 546 if (EAT('^')) { 547 EMIT(OBOL, 0); 548 p->g->iflags |= USEBOL; 549 p->g->nbol++; 550 } 551 while (MORE() && !SEETWO(end1, end2)) { 552 wasdollar = p_simp_re(p, first); 553 first = 0; 554 } 555 if (wasdollar) { /* oops, that was a trailing anchor */ 556 DROP(1); 557 EMIT(OEOL, 0); 558 p->g->iflags |= USEEOL; 559 p->g->neol++; 560 } 561 562 (void)REQUIRE(HERE() != start, REG_EMPTY); /* require nonempty */ 563} 564 565/* 566 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition 567 == static int p_simp_re(struct parse *p, int starordinary); 568 */ 569static int /* was the simple RE an unbackslashed $? */ 570p_simp_re(struct parse *p, 571 int starordinary) /* is a leading * an ordinary character? */ 572{ 573 int c; 574 int count; 575 int count2; 576 sopno pos; 577 int i; 578 wint_t wc; 579 sopno subno; 580# define BACKSL (1<<CHAR_BIT) 581 582 pos = HERE(); /* repetion op, if any, covers from here */ 583 584 assert(MORE()); /* caller should have ensured this */ 585 c = GETNEXT(); 586 if (c == '\\') { 587 (void)REQUIRE(MORE(), REG_EESCAPE); 588 c = BACKSL | GETNEXT(); 589 } 590 switch (c) { 591 case '.': 592 if (p->g->cflags®_NEWLINE) 593 nonnewline(p); 594 else 595 EMIT(OANY, 0); 596 break; 597 case '[': 598 p_bracket(p); 599 break; 600 case BACKSL|'<': 601 EMIT(OBOW, 0); 602 break; 603 case BACKSL|'>': 604 EMIT(OEOW, 0); 605 break; 606 case BACKSL|'{': 607 SETERROR(REG_BADRPT); 608 break; 609 case BACKSL|'(': 610 p->g->nsub++; 611 subno = p->g->nsub; 612 if (subno < NPAREN) 613 p->pbegin[subno] = HERE(); 614 EMIT(OLPAREN, subno); 615 /* the MORE here is an error heuristic */ 616 if (MORE() && !SEETWO('\\', ')')) 617 p_bre(p, '\\', ')'); 618 if (subno < NPAREN) { 619 p->pend[subno] = HERE(); 620 assert(p->pend[subno] != 0); 621 } 622 EMIT(ORPAREN, subno); 623 (void)REQUIRE(EATTWO('\\', ')'), REG_EPAREN); 624 break; 625 case BACKSL|')': /* should not get here -- must be user */ 626 case BACKSL|'}': 627 SETERROR(REG_EPAREN); 628 break; 629 case BACKSL|'1': 630 case BACKSL|'2': 631 case BACKSL|'3': 632 case BACKSL|'4': 633 case BACKSL|'5': 634 case BACKSL|'6': 635 case BACKSL|'7': 636 case BACKSL|'8': 637 case BACKSL|'9': 638 i = (c&~BACKSL) - '0'; 639 assert(i < NPAREN); 640 if (p->pend[i] != 0) { 641 assert(i <= p->g->nsub); 642 EMIT(OBACK_, i); 643 assert(p->pbegin[i] != 0); 644 assert(OP(p->strip[p->pbegin[i]]) == OLPAREN); 645 assert(OP(p->strip[p->pend[i]]) == ORPAREN); 646 (void) dupl(p, p->pbegin[i]+1, p->pend[i]); 647 EMIT(O_BACK, i); 648 } else 649 SETERROR(REG_ESUBREG); 650 p->g->backrefs = 1; 651 break; 652 case '*': 653 (void)REQUIRE(starordinary, REG_BADRPT); 654 /* FALLTHROUGH */ 655 default: 656 if (p->error != 0) 657 return(0); /* Definitely not $... */ 658 p->next--; 659 wc = WGETNEXT(); 660 ordinary(p, wc); 661 break; 662 } 663 664 if (EAT('*')) { /* implemented as +? */ 665 /* this case does not require the (y|) trick, noKLUDGE */ 666 INSERT(OPLUS_, pos); 667 ASTERN(O_PLUS, pos); 668 INSERT(OQUEST_, pos); 669 ASTERN(O_QUEST, pos); 670 } else if (EATTWO('\\', '{')) { 671 count = p_count(p); 672 if (EAT(',')) { 673 if (MORE() && isdigit((uch)PEEK())) { 674 count2 = p_count(p); 675 (void)REQUIRE(count <= count2, REG_BADBR); 676 } else /* single number with comma */ 677 count2 = INFINITY; 678 } else /* just a single number */ 679 count2 = count; 680 repeat(p, pos, count, count2); 681 if (!EATTWO('\\', '}')) { /* error heuristics */ 682 while (MORE() && !SEETWO('\\', '}')) 683 NEXT(); 684 (void)REQUIRE(MORE(), REG_EBRACE); 685 SETERROR(REG_BADBR); 686 } 687 } else if (c == '$') /* $ (but not \$) ends it */ 688 return(1); 689 690 return(0); 691} 692 693/* 694 - p_count - parse a repetition count 695 == static int p_count(struct parse *p); 696 */ 697static int /* the value */ 698p_count(struct parse *p) 699{ 700 int count = 0; 701 int ndigits = 0; 702 703 while (MORE() && isdigit((uch)PEEK()) && count <= DUPMAX) { 704 count = count*10 + (GETNEXT() - '0'); 705 ndigits++; 706 } 707 708 (void)REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR); 709 return(count); 710} 711 712/* 713 - p_bracket - parse a bracketed character list 714 == static void p_bracket(struct parse *p); 715 */ 716static void 717p_bracket(struct parse *p) 718{ 719 cset *cs; 720 wint_t ch; 721 722 /* Dept of Truly Sickening Special-Case Kludges */ 723 if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) { 724 EMIT(OBOW, 0); 725 NEXTn(6); 726 return; 727 } 728 if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) { 729 EMIT(OEOW, 0); 730 NEXTn(6); 731 return; 732 } 733 734 if ((cs = allocset(p)) == NULL) 735 return; 736 737 if (p->g->cflags®_ICASE) 738 cs->icase = 1; 739 if (EAT('^')) 740 cs->invert = 1; 741 if (EAT(']')) 742 CHadd(p, cs, ']'); 743 else if (EAT('-')) 744 CHadd(p, cs, '-'); 745 while (MORE() && PEEK() != ']' && !SEETWO('-', ']')) 746 p_b_term(p, cs); 747 if (EAT('-')) 748 CHadd(p, cs, '-'); 749 (void)MUSTEAT(']', REG_EBRACK); 750 751 if (p->error != 0) /* don't mess things up further */ 752 return; 753 754 if (cs->invert && p->g->cflags®_NEWLINE) 755 cs->bmp['\n' >> 3] |= 1 << ('\n' & 7); 756 757 if ((ch = singleton(cs)) != OUT) { /* optimize singleton sets */ 758 ordinary(p, ch); 759 freeset(p, cs); 760 } else 761 EMIT(OANYOF, (int)(cs - p->g->sets)); 762} 763 764/* 765 - p_b_term - parse one term of a bracketed character list 766 == static void p_b_term(struct parse *p, cset *cs); 767 */ 768static void 769p_b_term(struct parse *p, cset *cs) 770{ 771 char c; 772 wint_t start, finish; 773 wint_t i; 774 struct xlocale_collate *table = 775 (struct xlocale_collate*)__get_locale()->components[XLC_COLLATE]; 776 777 /* classify what we've got */ 778 switch ((MORE()) ? PEEK() : '\0') { 779 case '[': 780 c = (MORE2()) ? PEEK2() : '\0'; 781 break; 782 case '-': 783 SETERROR(REG_ERANGE); 784 return; /* NOTE RETURN */ 785 default: 786 c = '\0'; 787 break; 788 } 789 790 switch (c) { 791 case ':': /* character class */ 792 NEXT2(); 793 (void)REQUIRE(MORE(), REG_EBRACK); 794 c = PEEK(); 795 (void)REQUIRE(c != '-' && c != ']', REG_ECTYPE); 796 p_b_cclass(p, cs); 797 (void)REQUIRE(MORE(), REG_EBRACK); 798 (void)REQUIRE(EATTWO(':', ']'), REG_ECTYPE); 799 break; 800 case '=': /* equivalence class */ 801 NEXT2(); 802 (void)REQUIRE(MORE(), REG_EBRACK); 803 c = PEEK(); 804 (void)REQUIRE(c != '-' && c != ']', REG_ECOLLATE); 805 p_b_eclass(p, cs); 806 (void)REQUIRE(MORE(), REG_EBRACK); 807 (void)REQUIRE(EATTWO('=', ']'), REG_ECOLLATE); 808 break; 809 default: /* symbol, ordinary character, or range */ 810 start = p_b_symbol(p); 811 if (SEE('-') && MORE2() && PEEK2() != ']') { 812 /* range */ 813 NEXT(); 814 if (EAT('-')) 815 finish = '-'; 816 else 817 finish = p_b_symbol(p); 818 } else 819 finish = start; 820 if (start == finish) 821 CHadd(p, cs, start); 822 else { 823 if (table->__collate_load_error || MB_CUR_MAX > 1) { 824 (void)REQUIRE(start <= finish, REG_ERANGE); 825 CHaddrange(p, cs, start, finish); 826 } else { 827 (void)REQUIRE(__wcollate_range_cmp(start, finish) <= 0, REG_ERANGE); 828 for (i = 0; i <= UCHAR_MAX; i++) { 829 if ( __wcollate_range_cmp(start, i) <= 0 830 && __wcollate_range_cmp(i, finish) <= 0 831 ) 832 CHadd(p, cs, i); 833 } 834 } 835 } 836 break; 837 } 838} 839 840/* 841 - p_b_cclass - parse a character-class name and deal with it 842 == static void p_b_cclass(struct parse *p, cset *cs); 843 */ 844static void 845p_b_cclass(struct parse *p, cset *cs) 846{ 847 char *sp = p->next; 848 size_t len; 849 wctype_t wct; 850 char clname[16]; 851 852 while (MORE() && isalpha((uch)PEEK())) 853 NEXT(); 854 len = p->next - sp; 855 if (len >= sizeof(clname) - 1) { 856 SETERROR(REG_ECTYPE); 857 return; 858 } 859 memcpy(clname, sp, len); 860 clname[len] = '\0'; 861 if ((wct = wctype(clname)) == 0) { 862 SETERROR(REG_ECTYPE); 863 return; 864 } 865 CHaddtype(p, cs, wct); 866} 867 868/* 869 - p_b_eclass - parse an equivalence-class name and deal with it 870 == static void p_b_eclass(struct parse *p, cset *cs); 871 * 872 * This implementation is incomplete. xxx 873 */ 874static void 875p_b_eclass(struct parse *p, cset *cs) 876{ 877 wint_t c; 878 879 c = p_b_coll_elem(p, '='); 880 CHadd(p, cs, c); 881} 882 883/* 884 - p_b_symbol - parse a character or [..]ed multicharacter collating symbol 885 == static wint_t p_b_symbol(struct parse *p); 886 */ 887static wint_t /* value of symbol */ 888p_b_symbol(struct parse *p) 889{ 890 wint_t value; 891 892 (void)REQUIRE(MORE(), REG_EBRACK); 893 if (!EATTWO('[', '.')) 894 return(WGETNEXT()); 895 896 /* collating symbol */ 897 value = p_b_coll_elem(p, '.'); 898 (void)REQUIRE(EATTWO('.', ']'), REG_ECOLLATE); 899 return(value); 900} 901 902/* 903 - p_b_coll_elem - parse a collating-element name and look it up 904 == static wint_t p_b_coll_elem(struct parse *p, wint_t endc); 905 */ 906static wint_t /* value of collating element */ 907p_b_coll_elem(struct parse *p, 908 wint_t endc) /* name ended by endc,']' */ 909{ 910 char *sp = p->next; 911 struct cname *cp; 912 int len; 913 mbstate_t mbs; 914 wchar_t wc; 915 size_t clen; 916 917 while (MORE() && !SEETWO(endc, ']')) 918 NEXT(); 919 if (!MORE()) { 920 SETERROR(REG_EBRACK); 921 return(0); 922 } 923 len = p->next - sp; 924 for (cp = cnames; cp->name != NULL; cp++) 925 if (strncmp(cp->name, sp, len) == 0 && strlen(cp->name) == len) 926 return(cp->code); /* known name */ 927 memset(&mbs, 0, sizeof(mbs)); 928 if ((clen = mbrtowc(&wc, sp, len, &mbs)) == len) 929 return (wc); /* single character */ 930 else if (clen == (size_t)-1 || clen == (size_t)-2) 931 SETERROR(REG_ILLSEQ); 932 else 933 SETERROR(REG_ECOLLATE); /* neither */ 934 return(0); 935} 936 937/* 938 - othercase - return the case counterpart of an alphabetic 939 == static wint_t othercase(wint_t ch); 940 */ 941static wint_t /* if no counterpart, return ch */ 942othercase(wint_t ch) 943{ 944 assert(iswalpha(ch)); 945 if (iswupper(ch)) 946 return(towlower(ch)); 947 else if (iswlower(ch)) 948 return(towupper(ch)); 949 else /* peculiar, but could happen */ 950 return(ch); 951} 952 953/* 954 - bothcases - emit a dualcase version of a two-case character 955 == static void bothcases(struct parse *p, wint_t ch); 956 * 957 * Boy, is this implementation ever a kludge... 958 */ 959static void 960bothcases(struct parse *p, wint_t ch) 961{ 962 char *oldnext = p->next; 963 char *oldend = p->end; 964 char bracket[3 + MB_LEN_MAX]; 965 size_t n; 966 mbstate_t mbs; 967 968 assert(othercase(ch) != ch); /* p_bracket() would recurse */ 969 p->next = bracket; 970 memset(&mbs, 0, sizeof(mbs)); 971 n = wcrtomb(bracket, ch, &mbs); 972 assert(n != (size_t)-1); 973 bracket[n] = ']'; 974 bracket[n + 1] = '\0'; 975 p->end = bracket+n+1; 976 p_bracket(p); 977 assert(p->next == p->end); 978 p->next = oldnext; 979 p->end = oldend; 980} 981 982/* 983 - ordinary - emit an ordinary character 984 == static void ordinary(struct parse *p, wint_t ch); 985 */ 986static void 987ordinary(struct parse *p, wint_t ch) 988{ 989 cset *cs; 990 991 if ((p->g->cflags®_ICASE) && iswalpha(ch) && othercase(ch) != ch) 992 bothcases(p, ch); 993 else if ((ch & OPDMASK) == ch) 994 EMIT(OCHAR, ch); 995 else { 996 /* 997 * Kludge: character is too big to fit into an OCHAR operand. 998 * Emit a singleton set. 999 */ 1000 if ((cs = allocset(p)) == NULL) 1001 return; 1002 CHadd(p, cs, ch); 1003 EMIT(OANYOF, (int)(cs - p->g->sets)); 1004 } 1005} 1006 1007/* 1008 - nonnewline - emit REG_NEWLINE version of OANY 1009 == static void nonnewline(struct parse *p); 1010 * 1011 * Boy, is this implementation ever a kludge... 1012 */ 1013static void 1014nonnewline(struct parse *p) 1015{ 1016 char *oldnext = p->next; 1017 char *oldend = p->end; 1018 char bracket[4]; 1019 1020 p->next = bracket; 1021 p->end = bracket+3; 1022 bracket[0] = '^'; 1023 bracket[1] = '\n'; 1024 bracket[2] = ']'; 1025 bracket[3] = '\0'; 1026 p_bracket(p); 1027 assert(p->next == bracket+3); 1028 p->next = oldnext; 1029 p->end = oldend; 1030} 1031 1032/* 1033 - repeat - generate code for a bounded repetition, recursively if needed 1034 == static void repeat(struct parse *p, sopno start, int from, int to); 1035 */ 1036static void 1037repeat(struct parse *p, 1038 sopno start, /* operand from here to end of strip */ 1039 int from, /* repeated from this number */ 1040 int to) /* to this number of times (maybe INFINITY) */ 1041{ 1042 sopno finish = HERE(); 1043# define N 2 1044# define INF 3 1045# define REP(f, t) ((f)*8 + (t)) 1046# define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N) 1047 sopno copy; 1048 1049 if (p->error != 0) /* head off possible runaway recursion */ 1050 return; 1051 1052 assert(from <= to); 1053 1054 switch (REP(MAP(from), MAP(to))) { 1055 case REP(0, 0): /* must be user doing this */ 1056 DROP(finish-start); /* drop the operand */ 1057 break; 1058 case REP(0, 1): /* as x{1,1}? */ 1059 case REP(0, N): /* as x{1,n}? */ 1060 case REP(0, INF): /* as x{1,}? */ 1061 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 1062 INSERT(OCH_, start); /* offset is wrong... */ 1063 repeat(p, start+1, 1, to); 1064 ASTERN(OOR1, start); 1065 AHEAD(start); /* ... fix it */ 1066 EMIT(OOR2, 0); 1067 AHEAD(THERE()); 1068 ASTERN(O_CH, THERETHERE()); 1069 break; 1070 case REP(1, 1): /* trivial case */ 1071 /* done */ 1072 break; 1073 case REP(1, N): /* as x?x{1,n-1} */ 1074 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 1075 INSERT(OCH_, start); 1076 ASTERN(OOR1, start); 1077 AHEAD(start); 1078 EMIT(OOR2, 0); /* offset very wrong... */ 1079 AHEAD(THERE()); /* ...so fix it */ 1080 ASTERN(O_CH, THERETHERE()); 1081 copy = dupl(p, start+1, finish+1); 1082 assert(copy == finish+4); 1083 repeat(p, copy, 1, to-1); 1084 break; 1085 case REP(1, INF): /* as x+ */ 1086 INSERT(OPLUS_, start); 1087 ASTERN(O_PLUS, start); 1088 break; 1089 case REP(N, N): /* as xx{m-1,n-1} */ 1090 copy = dupl(p, start, finish); 1091 repeat(p, copy, from-1, to-1); 1092 break; 1093 case REP(N, INF): /* as xx{n-1,INF} */ 1094 copy = dupl(p, start, finish); 1095 repeat(p, copy, from-1, to); 1096 break; 1097 default: /* "can't happen" */ 1098 SETERROR(REG_ASSERT); /* just in case */ 1099 break; 1100 } 1101} 1102 1103/* 1104 - wgetnext - helper function for WGETNEXT() macro. Gets the next wide 1105 - character from the parse struct, signals a REG_ILLSEQ error if the 1106 - character can't be converted. Returns the number of bytes consumed. 1107 */ 1108static wint_t 1109wgetnext(struct parse *p) 1110{ 1111 mbstate_t mbs; 1112 wchar_t wc; 1113 size_t n; 1114 1115 memset(&mbs, 0, sizeof(mbs)); 1116 n = mbrtowc(&wc, p->next, p->end - p->next, &mbs); 1117 if (n == (size_t)-1 || n == (size_t)-2) { 1118 SETERROR(REG_ILLSEQ); 1119 return (0); 1120 } 1121 if (n == 0) 1122 n = 1; 1123 p->next += n; 1124 return (wc); 1125} 1126 1127/* 1128 - seterr - set an error condition 1129 == static int seterr(struct parse *p, int e); 1130 */ 1131static int /* useless but makes type checking happy */ 1132seterr(struct parse *p, int e) 1133{ 1134 if (p->error == 0) /* keep earliest error condition */ 1135 p->error = e; 1136 p->next = nuls; /* try to bring things to a halt */ 1137 p->end = nuls; 1138 return(0); /* make the return value well-defined */ 1139} 1140 1141/* 1142 - allocset - allocate a set of characters for [] 1143 == static cset *allocset(struct parse *p); 1144 */ 1145static cset * 1146allocset(struct parse *p) 1147{ 1148 cset *cs, *ncs; 1149 1150 ncs = realloc(p->g->sets, (p->g->ncsets + 1) * sizeof(*ncs)); 1151 if (ncs == NULL) { 1152 SETERROR(REG_ESPACE); 1153 return (NULL); 1154 } 1155 p->g->sets = ncs; 1156 cs = &p->g->sets[p->g->ncsets++]; 1157 memset(cs, 0, sizeof(*cs)); 1158 1159 return(cs); 1160} 1161 1162/* 1163 - freeset - free a now-unused set 1164 == static void freeset(struct parse *p, cset *cs); 1165 */ 1166static void 1167freeset(struct parse *p, cset *cs) 1168{ 1169 cset *top = &p->g->sets[p->g->ncsets]; 1170 1171 free(cs->wides); 1172 free(cs->ranges); 1173 free(cs->types); 1174 memset(cs, 0, sizeof(*cs)); 1175 if (cs == top-1) /* recover only the easy case */ 1176 p->g->ncsets--; 1177} 1178 1179/* 1180 - singleton - Determine whether a set contains only one character, 1181 - returning it if so, otherwise returning OUT. 1182 */ 1183static wint_t 1184singleton(cset *cs) 1185{ 1186 wint_t i, s, n; 1187 1188 for (i = n = 0; i < NC; i++) 1189 if (CHIN(cs, i)) { 1190 n++; 1191 s = i; 1192 } 1193 if (n == 1) 1194 return (s); 1195 if (cs->nwides == 1 && cs->nranges == 0 && cs->ntypes == 0 && 1196 cs->icase == 0) 1197 return (cs->wides[0]); 1198 /* Don't bother handling the other cases. */ 1199 return (OUT); 1200} 1201 1202/* 1203 - CHadd - add character to character set. 1204 */ 1205static void 1206CHadd(struct parse *p, cset *cs, wint_t ch) 1207{ 1208 wint_t nch, *newwides; 1209 assert(ch >= 0); 1210 if (ch < NC) 1211 cs->bmp[ch >> 3] |= 1 << (ch & 7); 1212 else { 1213 newwides = realloc(cs->wides, (cs->nwides + 1) * 1214 sizeof(*cs->wides)); 1215 if (newwides == NULL) { 1216 SETERROR(REG_ESPACE); 1217 return; 1218 } 1219 cs->wides = newwides; 1220 cs->wides[cs->nwides++] = ch; 1221 } 1222 if (cs->icase) { 1223 if ((nch = towlower(ch)) < NC) 1224 cs->bmp[nch >> 3] |= 1 << (nch & 7); 1225 if ((nch = towupper(ch)) < NC) 1226 cs->bmp[nch >> 3] |= 1 << (nch & 7); 1227 } 1228} 1229 1230/* 1231 - CHaddrange - add all characters in the range [min,max] to a character set. 1232 */ 1233static void 1234CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max) 1235{ 1236 crange *newranges; 1237 1238 for (; min < NC && min <= max; min++) 1239 CHadd(p, cs, min); 1240 if (min >= max) 1241 return; 1242 newranges = realloc(cs->ranges, (cs->nranges + 1) * 1243 sizeof(*cs->ranges)); 1244 if (newranges == NULL) { 1245 SETERROR(REG_ESPACE); 1246 return; 1247 } 1248 cs->ranges = newranges; 1249 cs->ranges[cs->nranges].min = min; 1250 cs->ranges[cs->nranges].max = max; 1251 cs->nranges++; 1252} 1253 1254/* 1255 - CHaddtype - add all characters of a certain type to a character set. 1256 */ 1257static void 1258CHaddtype(struct parse *p, cset *cs, wctype_t wct) 1259{ 1260 wint_t i; 1261 wctype_t *newtypes; 1262 1263 for (i = 0; i < NC; i++) 1264 if (iswctype(i, wct)) 1265 CHadd(p, cs, i); 1266 newtypes = realloc(cs->types, (cs->ntypes + 1) * 1267 sizeof(*cs->types)); 1268 if (newtypes == NULL) { 1269 SETERROR(REG_ESPACE); 1270 return; 1271 } 1272 cs->types = newtypes; 1273 cs->types[cs->ntypes++] = wct; 1274} 1275 1276/* 1277 - dupl - emit a duplicate of a bunch of sops 1278 == static sopno dupl(struct parse *p, sopno start, sopno finish); 1279 */ 1280static sopno /* start of duplicate */ 1281dupl(struct parse *p, 1282 sopno start, /* from here */ 1283 sopno finish) /* to this less one */ 1284{ 1285 sopno ret = HERE(); 1286 sopno len = finish - start; 1287 1288 assert(finish >= start); 1289 if (len == 0) 1290 return(ret); 1291 if (!enlarge(p, p->ssize + len)) /* this many unexpected additions */ 1292 return(ret); 1293 (void) memcpy((char *)(p->strip + p->slen), 1294 (char *)(p->strip + start), (size_t)len*sizeof(sop)); 1295 p->slen += len; 1296 return(ret); 1297} 1298 1299/* 1300 - doemit - emit a strip operator 1301 == static void doemit(struct parse *p, sop op, size_t opnd); 1302 * 1303 * It might seem better to implement this as a macro with a function as 1304 * hard-case backup, but it's just too big and messy unless there are 1305 * some changes to the data structures. Maybe later. 1306 */ 1307static void 1308doemit(struct parse *p, sop op, size_t opnd) 1309{ 1310 /* avoid making error situations worse */ 1311 if (p->error != 0) 1312 return; 1313 1314 /* deal with oversize operands ("can't happen", more or less) */ 1315 assert(opnd < 1<<OPSHIFT); 1316 1317 /* deal with undersized strip */ 1318 if (p->slen >= p->ssize) 1319 if (!enlarge(p, (p->ssize+1) / 2 * 3)) /* +50% */ 1320 return; 1321 1322 /* finally, it's all reduced to the easy case */ 1323 p->strip[p->slen++] = SOP(op, opnd); 1324} 1325 1326/* 1327 - doinsert - insert a sop into the strip 1328 == static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos); 1329 */ 1330static void 1331doinsert(struct parse *p, sop op, size_t opnd, sopno pos) 1332{ 1333 sopno sn; 1334 sop s; 1335 int i; 1336 1337 /* avoid making error situations worse */ 1338 if (p->error != 0) 1339 return; 1340 1341 sn = HERE(); 1342 EMIT(op, opnd); /* do checks, ensure space */ 1343 assert(HERE() == sn+1); 1344 s = p->strip[sn]; 1345 1346 /* adjust paren pointers */ 1347 assert(pos > 0); 1348 for (i = 1; i < NPAREN; i++) { 1349 if (p->pbegin[i] >= pos) { 1350 p->pbegin[i]++; 1351 } 1352 if (p->pend[i] >= pos) { 1353 p->pend[i]++; 1354 } 1355 } 1356 1357 memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos], 1358 (HERE()-pos-1)*sizeof(sop)); 1359 p->strip[pos] = s; 1360} 1361 1362/* 1363 - dofwd - complete a forward reference 1364 == static void dofwd(struct parse *p, sopno pos, sop value); 1365 */ 1366static void 1367dofwd(struct parse *p, sopno pos, sop value) 1368{ 1369 /* avoid making error situations worse */ 1370 if (p->error != 0) 1371 return; 1372 1373 assert(value < 1<<OPSHIFT); 1374 p->strip[pos] = OP(p->strip[pos]) | value; 1375} 1376 1377/* 1378 - enlarge - enlarge the strip 1379 == static int enlarge(struct parse *p, sopno size); 1380 */ 1381static int 1382enlarge(struct parse *p, sopno size) 1383{ 1384 sop *sp; 1385 1386 if (p->ssize >= size) 1387 return 1; 1388 1389 sp = (sop *)realloc(p->strip, size*sizeof(sop)); 1390 if (sp == NULL) { 1391 SETERROR(REG_ESPACE); 1392 return 0; 1393 } 1394 p->strip = sp; 1395 p->ssize = size; 1396 return 1; 1397} 1398 1399/* 1400 - stripsnug - compact the strip 1401 == static void stripsnug(struct parse *p, struct re_guts *g); 1402 */ 1403static void 1404stripsnug(struct parse *p, struct re_guts *g) 1405{ 1406 g->nstates = p->slen; 1407 g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop)); 1408 if (g->strip == NULL) { 1409 SETERROR(REG_ESPACE); 1410 g->strip = p->strip; 1411 } 1412} 1413 1414/* 1415 - findmust - fill in must and mlen with longest mandatory literal string 1416 == static void findmust(struct parse *p, struct re_guts *g); 1417 * 1418 * This algorithm could do fancy things like analyzing the operands of | 1419 * for common subsequences. Someday. This code is simple and finds most 1420 * of the interesting cases. 1421 * 1422 * Note that must and mlen got initialized during setup. 1423 */ 1424static void 1425findmust(struct parse *p, struct re_guts *g) 1426{ 1427 sop *scan; 1428 sop *start; 1429 sop *newstart; 1430 sopno newlen; 1431 sop s; 1432 char *cp; 1433 int offset; 1434 char buf[MB_LEN_MAX]; 1435 size_t clen; 1436 mbstate_t mbs; 1437 1438 /* avoid making error situations worse */ 1439 if (p->error != 0) 1440 return; 1441 1442 /* 1443 * It's not generally safe to do a ``char'' substring search on 1444 * multibyte character strings, but it's safe for at least 1445 * UTF-8 (see RFC 3629). 1446 */ 1447 if (MB_CUR_MAX > 1 && 1448 strcmp(_CurrentRuneLocale->__encoding, "UTF-8") != 0) 1449 return; 1450 1451 /* find the longest OCHAR sequence in strip */ 1452 newlen = 0; 1453 offset = 0; 1454 g->moffset = 0; 1455 scan = g->strip + 1; 1456 do { 1457 s = *scan++; 1458 switch (OP(s)) { 1459 case OCHAR: /* sequence member */ 1460 if (newlen == 0) { /* new sequence */ 1461 memset(&mbs, 0, sizeof(mbs)); 1462 newstart = scan - 1; 1463 } 1464 clen = wcrtomb(buf, OPND(s), &mbs); 1465 if (clen == (size_t)-1) 1466 goto toohard; 1467 newlen += clen; 1468 break; 1469 case OPLUS_: /* things that don't break one */ 1470 case OLPAREN: 1471 case ORPAREN: 1472 break; 1473 case OQUEST_: /* things that must be skipped */ 1474 case OCH_: 1475 offset = altoffset(scan, offset); 1476 scan--; 1477 do { 1478 scan += OPND(s); 1479 s = *scan; 1480 /* assert() interferes w debug printouts */ 1481 if (OP(s) != O_QUEST && OP(s) != O_CH && 1482 OP(s) != OOR2) { 1483 g->iflags |= BAD; 1484 return; 1485 } 1486 } while (OP(s) != O_QUEST && OP(s) != O_CH); 1487 /* FALLTHROUGH */ 1488 case OBOW: /* things that break a sequence */ 1489 case OEOW: 1490 case OBOL: 1491 case OEOL: 1492 case O_QUEST: 1493 case O_CH: 1494 case OEND: 1495 if (newlen > g->mlen) { /* ends one */ 1496 start = newstart; 1497 g->mlen = newlen; 1498 if (offset > -1) { 1499 g->moffset += offset; 1500 offset = newlen; 1501 } else 1502 g->moffset = offset; 1503 } else { 1504 if (offset > -1) 1505 offset += newlen; 1506 } 1507 newlen = 0; 1508 break; 1509 case OANY: 1510 if (newlen > g->mlen) { /* ends one */ 1511 start = newstart; 1512 g->mlen = newlen; 1513 if (offset > -1) { 1514 g->moffset += offset; 1515 offset = newlen; 1516 } else 1517 g->moffset = offset; 1518 } else { 1519 if (offset > -1) 1520 offset += newlen; 1521 } 1522 if (offset > -1) 1523 offset++; 1524 newlen = 0; 1525 break; 1526 case OANYOF: /* may or may not invalidate offset */ 1527 /* First, everything as OANY */ 1528 if (newlen > g->mlen) { /* ends one */ 1529 start = newstart; 1530 g->mlen = newlen; 1531 if (offset > -1) { 1532 g->moffset += offset; 1533 offset = newlen; 1534 } else 1535 g->moffset = offset; 1536 } else { 1537 if (offset > -1) 1538 offset += newlen; 1539 } 1540 if (offset > -1) 1541 offset++; 1542 newlen = 0; 1543 break; 1544 toohard: 1545 default: 1546 /* Anything here makes it impossible or too hard 1547 * to calculate the offset -- so we give up; 1548 * save the last known good offset, in case the 1549 * must sequence doesn't occur later. 1550 */ 1551 if (newlen > g->mlen) { /* ends one */ 1552 start = newstart; 1553 g->mlen = newlen; 1554 if (offset > -1) 1555 g->moffset += offset; 1556 else 1557 g->moffset = offset; 1558 } 1559 offset = -1; 1560 newlen = 0; 1561 break; 1562 } 1563 } while (OP(s) != OEND); 1564 1565 if (g->mlen == 0) { /* there isn't one */ 1566 g->moffset = -1; 1567 return; 1568 } 1569 1570 /* turn it into a character string */ 1571 g->must = malloc((size_t)g->mlen + 1); 1572 if (g->must == NULL) { /* argh; just forget it */ 1573 g->mlen = 0; 1574 g->moffset = -1; 1575 return; 1576 } 1577 cp = g->must; 1578 scan = start; 1579 memset(&mbs, 0, sizeof(mbs)); 1580 while (cp < g->must + g->mlen) { 1581 while (OP(s = *scan++) != OCHAR) 1582 continue; 1583 clen = wcrtomb(cp, OPND(s), &mbs); 1584 assert(clen != (size_t)-1); 1585 cp += clen; 1586 } 1587 assert(cp == g->must + g->mlen); 1588 *cp++ = '\0'; /* just on general principles */ 1589} 1590 1591/* 1592 - altoffset - choose biggest offset among multiple choices 1593 == static int altoffset(sop *scan, int offset); 1594 * 1595 * Compute, recursively if necessary, the largest offset among multiple 1596 * re paths. 1597 */ 1598static int 1599altoffset(sop *scan, int offset) 1600{ 1601 int largest; 1602 int try; 1603 sop s; 1604 1605 /* If we gave up already on offsets, return */ 1606 if (offset == -1) 1607 return -1; 1608 1609 largest = 0; 1610 try = 0; 1611 s = *scan++; 1612 while (OP(s) != O_QUEST && OP(s) != O_CH) { 1613 switch (OP(s)) { 1614 case OOR1: 1615 if (try > largest) 1616 largest = try; 1617 try = 0; 1618 break; 1619 case OQUEST_: 1620 case OCH_: 1621 try = altoffset(scan, try); 1622 if (try == -1) 1623 return -1; 1624 scan--; 1625 do { 1626 scan += OPND(s); 1627 s = *scan; 1628 if (OP(s) != O_QUEST && OP(s) != O_CH && 1629 OP(s) != OOR2) 1630 return -1; 1631 } while (OP(s) != O_QUEST && OP(s) != O_CH); 1632 /* We must skip to the next position, or we'll 1633 * leave altoffset() too early. 1634 */ 1635 scan++; 1636 break; 1637 case OANYOF: 1638 case OCHAR: 1639 case OANY: 1640 try++; 1641 case OBOW: 1642 case OEOW: 1643 case OLPAREN: 1644 case ORPAREN: 1645 case OOR2: 1646 break; 1647 default: 1648 try = -1; 1649 break; 1650 } 1651 if (try == -1) 1652 return -1; 1653 s = *scan++; 1654 } 1655 1656 if (try > largest) 1657 largest = try; 1658 1659 return largest+offset; 1660} 1661 1662/* 1663 - computejumps - compute char jumps for BM scan 1664 == static void computejumps(struct parse *p, struct re_guts *g); 1665 * 1666 * This algorithm assumes g->must exists and is has size greater than 1667 * zero. It's based on the algorithm found on Computer Algorithms by 1668 * Sara Baase. 1669 * 1670 * A char jump is the number of characters one needs to jump based on 1671 * the value of the character from the text that was mismatched. 1672 */ 1673static void 1674computejumps(struct parse *p, struct re_guts *g) 1675{ 1676 int ch; 1677 int mindex; 1678 1679 /* Avoid making errors worse */ 1680 if (p->error != 0) 1681 return; 1682 1683 g->charjump = (int*) malloc((NC + 1) * sizeof(int)); 1684 if (g->charjump == NULL) /* Not a fatal error */ 1685 return; 1686 /* Adjust for signed chars, if necessary */ 1687 g->charjump = &g->charjump[-(CHAR_MIN)]; 1688 1689 /* If the character does not exist in the pattern, the jump 1690 * is equal to the number of characters in the pattern. 1691 */ 1692 for (ch = CHAR_MIN; ch < (CHAR_MAX + 1); ch++) 1693 g->charjump[ch] = g->mlen; 1694 1695 /* If the character does exist, compute the jump that would 1696 * take us to the last character in the pattern equal to it 1697 * (notice that we match right to left, so that last character 1698 * is the first one that would be matched). 1699 */ 1700 for (mindex = 0; mindex < g->mlen; mindex++) 1701 g->charjump[(int)g->must[mindex]] = g->mlen - mindex - 1; 1702} 1703 1704/* 1705 - computematchjumps - compute match jumps for BM scan 1706 == static void computematchjumps(struct parse *p, struct re_guts *g); 1707 * 1708 * This algorithm assumes g->must exists and is has size greater than 1709 * zero. It's based on the algorithm found on Computer Algorithms by 1710 * Sara Baase. 1711 * 1712 * A match jump is the number of characters one needs to advance based 1713 * on the already-matched suffix. 1714 * Notice that all values here are minus (g->mlen-1), because of the way 1715 * the search algorithm works. 1716 */ 1717static void 1718computematchjumps(struct parse *p, struct re_guts *g) 1719{ 1720 int mindex; /* General "must" iterator */ 1721 int suffix; /* Keeps track of matching suffix */ 1722 int ssuffix; /* Keeps track of suffixes' suffix */ 1723 int* pmatches; /* pmatches[k] points to the next i 1724 * such that i+1...mlen is a substring 1725 * of k+1...k+mlen-i-1 1726 */ 1727 1728 /* Avoid making errors worse */ 1729 if (p->error != 0) 1730 return; 1731 1732 pmatches = (int*) malloc(g->mlen * sizeof(unsigned int)); 1733 if (pmatches == NULL) { 1734 g->matchjump = NULL; 1735 return; 1736 } 1737 1738 g->matchjump = (int*) malloc(g->mlen * sizeof(unsigned int)); 1739 if (g->matchjump == NULL) { /* Not a fatal error */ 1740 free(pmatches); 1741 return; 1742 } 1743 1744 /* Set maximum possible jump for each character in the pattern */ 1745 for (mindex = 0; mindex < g->mlen; mindex++) 1746 g->matchjump[mindex] = 2*g->mlen - mindex - 1; 1747 1748 /* Compute pmatches[] */ 1749 for (mindex = g->mlen - 1, suffix = g->mlen; mindex >= 0; 1750 mindex--, suffix--) { 1751 pmatches[mindex] = suffix; 1752 1753 /* If a mismatch is found, interrupting the substring, 1754 * compute the matchjump for that position. If no 1755 * mismatch is found, then a text substring mismatched 1756 * against the suffix will also mismatch against the 1757 * substring. 1758 */ 1759 while (suffix < g->mlen 1760 && g->must[mindex] != g->must[suffix]) { 1761 g->matchjump[suffix] = MIN(g->matchjump[suffix], 1762 g->mlen - mindex - 1); 1763 suffix = pmatches[suffix]; 1764 } 1765 } 1766 1767 /* Compute the matchjump up to the last substring found to jump 1768 * to the beginning of the largest must pattern prefix matching 1769 * it's own suffix. 1770 */ 1771 for (mindex = 0; mindex <= suffix; mindex++) 1772 g->matchjump[mindex] = MIN(g->matchjump[mindex], 1773 g->mlen + suffix - mindex); 1774 1775 ssuffix = pmatches[suffix]; 1776 while (suffix < g->mlen) { 1777 while (suffix <= ssuffix && suffix < g->mlen) { 1778 g->matchjump[suffix] = MIN(g->matchjump[suffix], 1779 g->mlen + ssuffix - suffix); 1780 suffix++; 1781 } 1782 if (suffix < g->mlen) 1783 ssuffix = pmatches[ssuffix]; 1784 } 1785 1786 free(pmatches); 1787} 1788 1789/* 1790 - pluscount - count + nesting 1791 == static sopno pluscount(struct parse *p, struct re_guts *g); 1792 */ 1793static sopno /* nesting depth */ 1794pluscount(struct parse *p, struct re_guts *g) 1795{ 1796 sop *scan; 1797 sop s; 1798 sopno plusnest = 0; 1799 sopno maxnest = 0; 1800 1801 if (p->error != 0) 1802 return(0); /* there may not be an OEND */ 1803 1804 scan = g->strip + 1; 1805 do { 1806 s = *scan++; 1807 switch (OP(s)) { 1808 case OPLUS_: 1809 plusnest++; 1810 break; 1811 case O_PLUS: 1812 if (plusnest > maxnest) 1813 maxnest = plusnest; 1814 plusnest--; 1815 break; 1816 } 1817 } while (OP(s) != OEND); 1818 if (plusnest != 0) 1819 g->iflags |= BAD; 1820 return(maxnest); 1821} 1822