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