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