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