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