1 /**************************************************************** 2 Copyright (C) Lucent Technologies 1997 3 All Rights Reserved 4 5 Permission to use, copy, modify, and distribute this software and 6 its documentation for any purpose and without fee is hereby 7 granted, provided that the above copyright notice appear in all 8 copies and that both that the copyright notice and this 9 permission notice and warranty disclaimer appear in supporting 10 documentation, and that the name Lucent Technologies or any of 11 its entities not be used in advertising or publicity pertaining 12 to distribution of the software without specific, written prior 13 permission. 14 15 LUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, 16 INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 17 IN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY 18 SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 19 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER 20 IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 21 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF 22 THIS SOFTWARE. 23 ****************************************************************/ 24 25 /* lasciate ogne speranza, voi ch'intrate. */ 26 27 #define DEBUG 28 29 #include <ctype.h> 30 #include <limits.h> 31 #include <stdio.h> 32 #include <string.h> 33 #include <stdlib.h> 34 #include "awk.h" 35 #include "awkgram.tab.h" 36 37 #define MAXLIN 22 38 39 #define type(v) (v)->nobj /* badly overloaded here */ 40 #define info(v) (v)->ntype /* badly overloaded here */ 41 #define left(v) (v)->narg[0] 42 #define right(v) (v)->narg[1] 43 #define parent(v) (v)->nnext 44 45 #define LEAF case CCL: case NCCL: case CHAR: case DOT: case FINAL: case ALL: 46 #define ELEAF case EMPTYRE: /* empty string in regexp */ 47 #define UNARY case STAR: case PLUS: case QUEST: 48 49 /* encoding in tree Nodes: 50 leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL, EMPTYRE): 51 left is index, right contains value or pointer to value 52 unary (STAR, PLUS, QUEST): left is child, right is null 53 binary (CAT, OR): left and right are children 54 parent contains pointer to parent 55 */ 56 57 58 int *setvec; 59 int *tmpset; 60 int maxsetvec = 0; 61 62 int rtok; /* next token in current re */ 63 int rlxval; 64 static const uschar *rlxstr; 65 static const uschar *prestr; /* current position in current re */ 66 static const uschar *lastre; /* origin of last re */ 67 static const uschar *lastatom; /* origin of last Atom */ 68 static const uschar *starttok; 69 static const uschar *basestr; /* starts with original, replaced during 70 repetition processing */ 71 static const uschar *firstbasestr; 72 73 static int setcnt; 74 static int poscnt; 75 76 const char *patbeg; 77 int patlen; 78 79 #define NFA 128 /* cache this many dynamic fa's */ 80 fa *fatab[NFA]; 81 int nfatab = 0; /* entries in fatab */ 82 83 static int * 84 intalloc(size_t n, const char *f) 85 { 86 int *p = (int *) calloc(n, sizeof(int)); 87 if (p == NULL) 88 overflo(f); 89 return p; 90 } 91 92 static void 93 resizesetvec(const char *f) 94 { 95 if (maxsetvec == 0) 96 maxsetvec = MAXLIN; 97 else 98 maxsetvec *= 4; 99 setvec = (int *) realloc(setvec, maxsetvec * sizeof(*setvec)); 100 tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(*tmpset)); 101 if (setvec == NULL || tmpset == NULL) 102 overflo(f); 103 } 104 105 static void 106 resize_state(fa *f, int state) 107 { 108 unsigned int **p; 109 uschar *p2; 110 int **p3; 111 int i, new_count; 112 113 if (++state < f->state_count) 114 return; 115 116 new_count = state + 10; /* needs to be tuned */ 117 118 p = (unsigned int **) realloc(f->gototab, new_count * sizeof(f->gototab[0])); 119 if (p == NULL) 120 goto out; 121 f->gototab = p; 122 123 p2 = (uschar *) realloc(f->out, new_count * sizeof(f->out[0])); 124 if (p2 == NULL) 125 goto out; 126 f->out = p2; 127 128 p3 = (int **) realloc(f->posns, new_count * sizeof(f->posns[0])); 129 if (p3 == NULL) 130 goto out; 131 f->posns = p3; 132 133 for (i = f->state_count; i < new_count; ++i) { 134 f->gototab[i] = (unsigned int *) calloc(NCHARS, sizeof(**f->gototab)); 135 if (f->gototab[i] == NULL) 136 goto out; 137 f->out[i] = 0; 138 f->posns[i] = NULL; 139 } 140 f->state_count = new_count; 141 return; 142 out: 143 overflo(__func__); 144 } 145 146 fa *makedfa(const char *s, bool anchor) /* returns dfa for reg expr s */ 147 { 148 int i, use, nuse; 149 fa *pfa; 150 static int now = 1; 151 152 if (setvec == NULL) { /* first time through any RE */ 153 resizesetvec(__func__); 154 } 155 156 if (compile_time != RUNNING) /* a constant for sure */ 157 return mkdfa(s, anchor); 158 for (i = 0; i < nfatab; i++) /* is it there already? */ 159 if (fatab[i]->anchor == anchor 160 && strcmp((const char *) fatab[i]->restr, s) == 0) { 161 fatab[i]->use = now++; 162 return fatab[i]; 163 } 164 pfa = mkdfa(s, anchor); 165 if (nfatab < NFA) { /* room for another */ 166 fatab[nfatab] = pfa; 167 fatab[nfatab]->use = now++; 168 nfatab++; 169 return pfa; 170 } 171 use = fatab[0]->use; /* replace least-recently used */ 172 nuse = 0; 173 for (i = 1; i < nfatab; i++) 174 if (fatab[i]->use < use) { 175 use = fatab[i]->use; 176 nuse = i; 177 } 178 freefa(fatab[nuse]); 179 fatab[nuse] = pfa; 180 pfa->use = now++; 181 return pfa; 182 } 183 184 fa *mkdfa(const char *s, bool anchor) /* does the real work of making a dfa */ 185 /* anchor = true for anchored matches, else false */ 186 { 187 Node *p, *p1; 188 fa *f; 189 190 firstbasestr = (const uschar *) s; 191 basestr = firstbasestr; 192 p = reparse(s); 193 p1 = op2(CAT, op2(STAR, op2(ALL, NIL, NIL), NIL), p); 194 /* put ALL STAR in front of reg. exp. */ 195 p1 = op2(CAT, p1, op2(FINAL, NIL, NIL)); 196 /* put FINAL after reg. exp. */ 197 198 poscnt = 0; 199 penter(p1); /* enter parent pointers and leaf indices */ 200 if ((f = (fa *) calloc(1, sizeof(fa) + poscnt * sizeof(rrow))) == NULL) 201 overflo(__func__); 202 f->accept = poscnt-1; /* penter has computed number of positions in re */ 203 cfoll(f, p1); /* set up follow sets */ 204 freetr(p1); 205 resize_state(f, 1); 206 f->posns[0] = intalloc(*(f->re[0].lfollow), __func__); 207 f->posns[1] = intalloc(1, __func__); 208 *f->posns[1] = 0; 209 f->initstat = makeinit(f, anchor); 210 f->anchor = anchor; 211 f->restr = (uschar *) tostring(s); 212 if (firstbasestr != basestr) { 213 if (basestr) 214 xfree(basestr); 215 } 216 return f; 217 } 218 219 int makeinit(fa *f, bool anchor) 220 { 221 int i, k; 222 223 f->curstat = 2; 224 f->out[2] = 0; 225 k = *(f->re[0].lfollow); 226 xfree(f->posns[2]); 227 f->posns[2] = intalloc(k + 1, __func__); 228 for (i = 0; i <= k; i++) { 229 (f->posns[2])[i] = (f->re[0].lfollow)[i]; 230 } 231 if ((f->posns[2])[1] == f->accept) 232 f->out[2] = 1; 233 for (i = 0; i < NCHARS; i++) 234 f->gototab[2][i] = 0; 235 f->curstat = cgoto(f, 2, HAT); 236 if (anchor) { 237 *f->posns[2] = k-1; /* leave out position 0 */ 238 for (i = 0; i < k; i++) { 239 (f->posns[0])[i] = (f->posns[2])[i]; 240 } 241 242 f->out[0] = f->out[2]; 243 if (f->curstat != 2) 244 --(*f->posns[f->curstat]); 245 } 246 return f->curstat; 247 } 248 249 void penter(Node *p) /* set up parent pointers and leaf indices */ 250 { 251 switch (type(p)) { 252 ELEAF 253 LEAF 254 info(p) = poscnt; 255 poscnt++; 256 break; 257 UNARY 258 penter(left(p)); 259 parent(left(p)) = p; 260 break; 261 case CAT: 262 case OR: 263 penter(left(p)); 264 penter(right(p)); 265 parent(left(p)) = p; 266 parent(right(p)) = p; 267 break; 268 case ZERO: 269 break; 270 default: /* can't happen */ 271 FATAL("can't happen: unknown type %d in penter", type(p)); 272 break; 273 } 274 } 275 276 void freetr(Node *p) /* free parse tree */ 277 { 278 switch (type(p)) { 279 ELEAF 280 LEAF 281 xfree(p); 282 break; 283 UNARY 284 case ZERO: 285 freetr(left(p)); 286 xfree(p); 287 break; 288 case CAT: 289 case OR: 290 freetr(left(p)); 291 freetr(right(p)); 292 xfree(p); 293 break; 294 default: /* can't happen */ 295 FATAL("can't happen: unknown type %d in freetr", type(p)); 296 break; 297 } 298 } 299 300 /* in the parsing of regular expressions, metacharacters like . have */ 301 /* to be seen literally; \056 is not a metacharacter. */ 302 303 int hexstr(const uschar **pp) /* find and eval hex string at pp, return new p */ 304 { /* only pick up one 8-bit byte (2 chars) */ 305 const uschar *p; 306 int n = 0; 307 int i; 308 309 for (i = 0, p = *pp; i < 2 && isxdigit(*p); i++, p++) { 310 if (isdigit(*p)) 311 n = 16 * n + *p - '0'; 312 else if (*p >= 'a' && *p <= 'f') 313 n = 16 * n + *p - 'a' + 10; 314 else if (*p >= 'A' && *p <= 'F') 315 n = 16 * n + *p - 'A' + 10; 316 } 317 *pp = p; 318 return n; 319 } 320 321 #define isoctdigit(c) ((c) >= '0' && (c) <= '7') /* multiple use of arg */ 322 323 int quoted(const uschar **pp) /* pick up next thing after a \\ */ 324 /* and increment *pp */ 325 { 326 const uschar *p = *pp; 327 int c; 328 329 if ((c = *p++) == 't') 330 c = '\t'; 331 else if (c == 'n') 332 c = '\n'; 333 else if (c == 'f') 334 c = '\f'; 335 else if (c == 'r') 336 c = '\r'; 337 else if (c == 'b') 338 c = '\b'; 339 else if (c == 'v') 340 c = '\v'; 341 else if (c == 'a') 342 c = '\a'; 343 else if (c == '\\') 344 c = '\\'; 345 else if (c == 'x') { /* hexadecimal goo follows */ 346 c = hexstr(&p); /* this adds a null if number is invalid */ 347 } else if (isoctdigit(c)) { /* \d \dd \ddd */ 348 int n = c - '0'; 349 if (isoctdigit(*p)) { 350 n = 8 * n + *p++ - '0'; 351 if (isoctdigit(*p)) 352 n = 8 * n + *p++ - '0'; 353 } 354 c = n; 355 } /* else */ 356 /* c = c; */ 357 *pp = p; 358 return c; 359 } 360 361 char *cclenter(const char *argp) /* add a character class */ 362 { 363 int i, c, c2; 364 const uschar *op, *p = (const uschar *) argp; 365 uschar *bp; 366 static uschar *buf = NULL; 367 static int bufsz = 100; 368 369 op = p; 370 if (buf == NULL && (buf = (uschar *) malloc(bufsz)) == NULL) 371 FATAL("out of space for character class [%.10s...] 1", p); 372 bp = buf; 373 for (i = 0; (c = *p++) != 0; ) { 374 if (c == '\\') { 375 c = quoted(&p); 376 } else if (c == '-' && i > 0 && bp[-1] != 0) { 377 if (*p != 0) { 378 c = bp[-1]; 379 c2 = *p++; 380 if (c2 == '\\') 381 c2 = quoted(&p); 382 if (c > c2) { /* empty; ignore */ 383 bp--; 384 i--; 385 continue; 386 } 387 while (c < c2) { 388 if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, "cclenter1")) 389 FATAL("out of space for character class [%.10s...] 2", p); 390 *bp++ = ++c; 391 i++; 392 } 393 continue; 394 } 395 } 396 if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, "cclenter2")) 397 FATAL("out of space for character class [%.10s...] 3", p); 398 *bp++ = c; 399 i++; 400 } 401 *bp = 0; 402 DPRINTF("cclenter: in = |%s|, out = |%s|\n", op, buf); 403 xfree(op); 404 return (char *) tostring((char *) buf); 405 } 406 407 void overflo(const char *s) 408 { 409 FATAL("regular expression too big: out of space in %.30s...", s); 410 } 411 412 void cfoll(fa *f, Node *v) /* enter follow set of each leaf of vertex v into lfollow[leaf] */ 413 { 414 int i; 415 int *p; 416 417 switch (type(v)) { 418 ELEAF 419 LEAF 420 f->re[info(v)].ltype = type(v); 421 f->re[info(v)].lval.np = right(v); 422 while (f->accept >= maxsetvec) { /* guessing here! */ 423 resizesetvec(__func__); 424 } 425 for (i = 0; i <= f->accept; i++) 426 setvec[i] = 0; 427 setcnt = 0; 428 follow(v); /* computes setvec and setcnt */ 429 p = intalloc(setcnt + 1, __func__); 430 f->re[info(v)].lfollow = p; 431 *p = setcnt; 432 for (i = f->accept; i >= 0; i--) 433 if (setvec[i] == 1) 434 *++p = i; 435 break; 436 UNARY 437 cfoll(f,left(v)); 438 break; 439 case CAT: 440 case OR: 441 cfoll(f,left(v)); 442 cfoll(f,right(v)); 443 break; 444 case ZERO: 445 break; 446 default: /* can't happen */ 447 FATAL("can't happen: unknown type %d in cfoll", type(v)); 448 } 449 } 450 451 int first(Node *p) /* collects initially active leaves of p into setvec */ 452 /* returns 0 if p matches empty string */ 453 { 454 int b, lp; 455 456 switch (type(p)) { 457 ELEAF 458 LEAF 459 lp = info(p); /* look for high-water mark of subscripts */ 460 while (setcnt >= maxsetvec || lp >= maxsetvec) { /* guessing here! */ 461 resizesetvec(__func__); 462 } 463 if (type(p) == EMPTYRE) { 464 setvec[lp] = 0; 465 return(0); 466 } 467 if (setvec[lp] != 1) { 468 setvec[lp] = 1; 469 setcnt++; 470 } 471 if (type(p) == CCL && (*(char *) right(p)) == '\0') 472 return(0); /* empty CCL */ 473 return(1); 474 case PLUS: 475 if (first(left(p)) == 0) 476 return(0); 477 return(1); 478 case STAR: 479 case QUEST: 480 first(left(p)); 481 return(0); 482 case CAT: 483 if (first(left(p)) == 0 && first(right(p)) == 0) return(0); 484 return(1); 485 case OR: 486 b = first(right(p)); 487 if (first(left(p)) == 0 || b == 0) return(0); 488 return(1); 489 case ZERO: 490 return 0; 491 } 492 FATAL("can't happen: unknown type %d in first", type(p)); /* can't happen */ 493 return(-1); 494 } 495 496 void follow(Node *v) /* collects leaves that can follow v into setvec */ 497 { 498 Node *p; 499 500 if (type(v) == FINAL) 501 return; 502 p = parent(v); 503 switch (type(p)) { 504 case STAR: 505 case PLUS: 506 first(v); 507 follow(p); 508 return; 509 510 case OR: 511 case QUEST: 512 follow(p); 513 return; 514 515 case CAT: 516 if (v == left(p)) { /* v is left child of p */ 517 if (first(right(p)) == 0) { 518 follow(p); 519 return; 520 } 521 } else /* v is right child */ 522 follow(p); 523 return; 524 } 525 } 526 527 int member(int c, const char *sarg) /* is c in s? */ 528 { 529 const uschar *s = (const uschar *) sarg; 530 531 while (*s) 532 if (c == *s++) 533 return(1); 534 return(0); 535 } 536 537 int match(fa *f, const char *p0) /* shortest match ? */ 538 { 539 int s, ns; 540 const uschar *p = (const uschar *) p0; 541 542 s = f->initstat; 543 assert (s < f->state_count); 544 545 if (f->out[s]) 546 return(1); 547 do { 548 /* assert(*p < NCHARS); */ 549 if ((ns = f->gototab[s][*p]) != 0) 550 s = ns; 551 else 552 s = cgoto(f, s, *p); 553 if (f->out[s]) 554 return(1); 555 } while (*p++ != 0); 556 return(0); 557 } 558 559 int pmatch(fa *f, const char *p0) /* longest match, for sub */ 560 { 561 int s, ns; 562 const uschar *p = (const uschar *) p0; 563 const uschar *q; 564 565 s = f->initstat; 566 assert(s < f->state_count); 567 568 patbeg = (const char *)p; 569 patlen = -1; 570 do { 571 q = p; 572 do { 573 if (f->out[s]) /* final state */ 574 patlen = q-p; 575 /* assert(*q < NCHARS); */ 576 if ((ns = f->gototab[s][*q]) != 0) 577 s = ns; 578 else 579 s = cgoto(f, s, *q); 580 581 assert(s < f->state_count); 582 583 if (s == 1) { /* no transition */ 584 if (patlen >= 0) { 585 patbeg = (const char *) p; 586 return(1); 587 } 588 else 589 goto nextin; /* no match */ 590 } 591 } while (*q++ != 0); 592 if (f->out[s]) 593 patlen = q-p-1; /* don't count $ */ 594 if (patlen >= 0) { 595 patbeg = (const char *) p; 596 return(1); 597 } 598 nextin: 599 s = 2; 600 } while (*p++); 601 return (0); 602 } 603 604 int nematch(fa *f, const char *p0) /* non-empty match, for sub */ 605 { 606 int s, ns; 607 const uschar *p = (const uschar *) p0; 608 const uschar *q; 609 610 s = f->initstat; 611 assert(s < f->state_count); 612 613 patbeg = (const char *)p; 614 patlen = -1; 615 while (*p) { 616 q = p; 617 do { 618 if (f->out[s]) /* final state */ 619 patlen = q-p; 620 /* assert(*q < NCHARS); */ 621 if ((ns = f->gototab[s][*q]) != 0) 622 s = ns; 623 else 624 s = cgoto(f, s, *q); 625 if (s == 1) { /* no transition */ 626 if (patlen > 0) { 627 patbeg = (const char *) p; 628 return(1); 629 } else 630 goto nnextin; /* no nonempty match */ 631 } 632 } while (*q++ != 0); 633 if (f->out[s]) 634 patlen = q-p-1; /* don't count $ */ 635 if (patlen > 0 ) { 636 patbeg = (const char *) p; 637 return(1); 638 } 639 nnextin: 640 s = 2; 641 p++; 642 } 643 return (0); 644 } 645 646 647 /* 648 * NAME 649 * fnematch 650 * 651 * DESCRIPTION 652 * A stream-fed version of nematch which transfers characters to a 653 * null-terminated buffer. All characters up to and including the last 654 * character of the matching text or EOF are placed in the buffer. If 655 * a match is found, patbeg and patlen are set appropriately. 656 * 657 * RETURN VALUES 658 * false No match found. 659 * true Match found. 660 */ 661 662 bool fnematch(fa *pfa, FILE *f, char **pbuf, int *pbufsize, int quantum) 663 { 664 char *buf = *pbuf; 665 int bufsize = *pbufsize; 666 int c, i, j, k, ns, s; 667 668 s = pfa->initstat; 669 patlen = 0; 670 671 /* 672 * All indices relative to buf. 673 * i <= j <= k <= bufsize 674 * 675 * i: origin of active substring 676 * j: current character 677 * k: destination of next getc() 678 */ 679 i = -1, k = 0; 680 do { 681 j = i++; 682 do { 683 if (++j == k) { 684 if (k == bufsize) 685 if (!adjbuf((char **) &buf, &bufsize, bufsize+1, quantum, 0, "fnematch")) 686 FATAL("stream '%.30s...' too long", buf); 687 buf[k++] = (c = getc(f)) != EOF ? c : 0; 688 } 689 c = (uschar)buf[j]; 690 /* assert(c < NCHARS); */ 691 692 if ((ns = pfa->gototab[s][c]) != 0) 693 s = ns; 694 else 695 s = cgoto(pfa, s, c); 696 697 if (pfa->out[s]) { /* final state */ 698 patlen = j - i + 1; 699 if (c == 0) /* don't count $ */ 700 patlen--; 701 } 702 } while (buf[j] && s != 1); 703 s = 2; 704 } while (buf[i] && !patlen); 705 706 /* adjbuf() may have relocated a resized buffer. Inform the world. */ 707 *pbuf = buf; 708 *pbufsize = bufsize; 709 710 if (patlen) { 711 patbeg = (char *) buf + i; 712 /* 713 * Under no circumstances is the last character fed to 714 * the automaton part of the match. It is EOF's nullbyte, 715 * or it sent the automaton into a state with no further 716 * transitions available (s==1), or both. Room for a 717 * terminating nullbyte is guaranteed. 718 * 719 * ungetc any chars after the end of matching text 720 * (except for EOF's nullbyte, if present) and null 721 * terminate the buffer. 722 */ 723 do 724 if (buf[--k] && ungetc(buf[k], f) == EOF) 725 FATAL("unable to ungetc '%c'", buf[k]); 726 while (k > i + patlen); 727 buf[k] = '\0'; 728 return true; 729 } 730 else 731 return false; 732 } 733 734 Node *reparse(const char *p) /* parses regular expression pointed to by p */ 735 { /* uses relex() to scan regular expression */ 736 Node *np; 737 738 DPRINTF("reparse <%s>\n", p); 739 lastre = prestr = (const uschar *) p; /* prestr points to string to be parsed */ 740 rtok = relex(); 741 /* GNU compatibility: an empty regexp matches anything */ 742 if (rtok == '\0') { 743 /* FATAL("empty regular expression"); previous */ 744 return(op2(EMPTYRE, NIL, NIL)); 745 } 746 np = regexp(); 747 if (rtok != '\0') 748 FATAL("syntax error in regular expression %s at %s", lastre, prestr); 749 return(np); 750 } 751 752 Node *regexp(void) /* top-level parse of reg expr */ 753 { 754 return (alt(concat(primary()))); 755 } 756 757 Node *primary(void) 758 { 759 Node *np; 760 int savelastatom; 761 762 switch (rtok) { 763 case CHAR: 764 lastatom = starttok; 765 np = op2(CHAR, NIL, itonp(rlxval)); 766 rtok = relex(); 767 return (unary(np)); 768 case ALL: 769 rtok = relex(); 770 return (unary(op2(ALL, NIL, NIL))); 771 case EMPTYRE: 772 rtok = relex(); 773 return (unary(op2(EMPTYRE, NIL, NIL))); 774 case DOT: 775 lastatom = starttok; 776 rtok = relex(); 777 return (unary(op2(DOT, NIL, NIL))); 778 case CCL: 779 np = op2(CCL, NIL, (Node*) cclenter((const char *) rlxstr)); 780 lastatom = starttok; 781 rtok = relex(); 782 return (unary(np)); 783 case NCCL: 784 np = op2(NCCL, NIL, (Node *) cclenter((const char *) rlxstr)); 785 lastatom = starttok; 786 rtok = relex(); 787 return (unary(np)); 788 case '^': 789 rtok = relex(); 790 return (unary(op2(CHAR, NIL, itonp(HAT)))); 791 case '$': 792 rtok = relex(); 793 return (unary(op2(CHAR, NIL, NIL))); 794 case '(': 795 lastatom = starttok; 796 savelastatom = starttok - basestr; /* Retain over recursion */ 797 rtok = relex(); 798 if (rtok == ')') { /* special pleading for () */ 799 rtok = relex(); 800 return unary(op2(CCL, NIL, (Node *) tostring(""))); 801 } 802 np = regexp(); 803 if (rtok == ')') { 804 lastatom = basestr + savelastatom; /* Restore */ 805 rtok = relex(); 806 return (unary(np)); 807 } 808 else 809 FATAL("syntax error in regular expression %s at %s", lastre, prestr); 810 default: 811 FATAL("illegal primary in regular expression %s at %s", lastre, prestr); 812 } 813 return 0; /*NOTREACHED*/ 814 } 815 816 Node *concat(Node *np) 817 { 818 switch (rtok) { 819 case CHAR: case DOT: case ALL: case CCL: case NCCL: case '$': case '(': 820 return (concat(op2(CAT, np, primary()))); 821 case EMPTYRE: 822 rtok = relex(); 823 return (concat(op2(CAT, op2(CCL, NIL, (Node *) tostring("")), 824 primary()))); 825 } 826 return (np); 827 } 828 829 Node *alt(Node *np) 830 { 831 if (rtok == OR) { 832 rtok = relex(); 833 return (alt(op2(OR, np, concat(primary())))); 834 } 835 return (np); 836 } 837 838 Node *unary(Node *np) 839 { 840 switch (rtok) { 841 case STAR: 842 rtok = relex(); 843 return (unary(op2(STAR, np, NIL))); 844 case PLUS: 845 rtok = relex(); 846 return (unary(op2(PLUS, np, NIL))); 847 case QUEST: 848 rtok = relex(); 849 return (unary(op2(QUEST, np, NIL))); 850 case ZERO: 851 rtok = relex(); 852 return (unary(op2(ZERO, np, NIL))); 853 default: 854 return (np); 855 } 856 } 857 858 /* 859 * Character class definitions conformant to the POSIX locale as 860 * defined in IEEE P1003.1 draft 7 of June 2001, assuming the source 861 * and operating character sets are both ASCII (ISO646) or supersets 862 * thereof. 863 * 864 * Note that to avoid overflowing the temporary buffer used in 865 * relex(), the expanded character class (prior to range expansion) 866 * must be less than twice the size of their full name. 867 */ 868 869 /* Because isblank doesn't show up in any of the header files on any 870 * system i use, it's defined here. if some other locale has a richer 871 * definition of "blank", define HAS_ISBLANK and provide your own 872 * version. 873 * the parentheses here are an attempt to find a path through the maze 874 * of macro definition and/or function and/or version provided. thanks 875 * to nelson beebe for the suggestion; let's see if it works everywhere. 876 */ 877 878 /* #define HAS_ISBLANK */ 879 #ifndef HAS_ISBLANK 880 881 int (xisblank)(int c) 882 { 883 return c==' ' || c=='\t'; 884 } 885 886 #endif 887 888 static const struct charclass { 889 const char *cc_name; 890 int cc_namelen; 891 int (*cc_func)(int); 892 } charclasses[] = { 893 { "alnum", 5, isalnum }, 894 { "alpha", 5, isalpha }, 895 #ifndef HAS_ISBLANK 896 { "blank", 5, xisblank }, 897 #else 898 { "blank", 5, isblank }, 899 #endif 900 { "cntrl", 5, iscntrl }, 901 { "digit", 5, isdigit }, 902 { "graph", 5, isgraph }, 903 { "lower", 5, islower }, 904 { "print", 5, isprint }, 905 { "punct", 5, ispunct }, 906 { "space", 5, isspace }, 907 { "upper", 5, isupper }, 908 { "xdigit", 6, isxdigit }, 909 { NULL, 0, NULL }, 910 }; 911 912 #define REPEAT_SIMPLE 0 913 #define REPEAT_PLUS_APPENDED 1 914 #define REPEAT_WITH_Q 2 915 #define REPEAT_ZERO 3 916 917 static int 918 replace_repeat(const uschar *reptok, int reptoklen, const uschar *atom, 919 int atomlen, int firstnum, int secondnum, int special_case) 920 { 921 int i, j; 922 uschar *buf = 0; 923 int ret = 1; 924 int init_q = (firstnum == 0); /* first added char will be ? */ 925 int n_q_reps = secondnum-firstnum; /* m>n, so reduce until {1,m-n} left */ 926 int prefix_length = reptok - basestr; /* prefix includes first rep */ 927 int suffix_length = strlen((const char *) reptok) - reptoklen; /* string after rep specifier */ 928 int size = prefix_length + suffix_length; 929 930 if (firstnum > 1) { /* add room for reps 2 through firstnum */ 931 size += atomlen*(firstnum-1); 932 } 933 934 /* Adjust size of buffer for special cases */ 935 if (special_case == REPEAT_PLUS_APPENDED) { 936 size++; /* for the final + */ 937 } else if (special_case == REPEAT_WITH_Q) { 938 size += init_q + (atomlen+1)* (n_q_reps-init_q); 939 } else if (special_case == REPEAT_ZERO) { 940 size += 2; /* just a null ERE: () */ 941 } 942 if ((buf = (uschar *) malloc(size + 1)) == NULL) 943 FATAL("out of space in reg expr %.10s..", lastre); 944 memcpy(buf, basestr, prefix_length); /* copy prefix */ 945 j = prefix_length; 946 if (special_case == REPEAT_ZERO) { 947 j -= atomlen; 948 buf[j++] = '('; 949 buf[j++] = ')'; 950 } 951 for (i = 1; i < firstnum; i++) { /* copy x reps */ 952 memcpy(&buf[j], atom, atomlen); 953 j += atomlen; 954 } 955 if (special_case == REPEAT_PLUS_APPENDED) { 956 buf[j++] = '+'; 957 } else if (special_case == REPEAT_WITH_Q) { 958 if (init_q) 959 buf[j++] = '?'; 960 for (i = init_q; i < n_q_reps; i++) { /* copy x? reps */ 961 memcpy(&buf[j], atom, atomlen); 962 j += atomlen; 963 buf[j++] = '?'; 964 } 965 } 966 memcpy(&buf[j], reptok+reptoklen, suffix_length); 967 j += suffix_length; 968 buf[j] = '\0'; 969 /* free old basestr */ 970 if (firstbasestr != basestr) { 971 if (basestr) 972 xfree(basestr); 973 } 974 basestr = buf; 975 prestr = buf + prefix_length; 976 if (special_case == REPEAT_ZERO) { 977 prestr -= atomlen; 978 ret++; 979 } 980 return ret; 981 } 982 983 static int repeat(const uschar *reptok, int reptoklen, const uschar *atom, 984 int atomlen, int firstnum, int secondnum) 985 { 986 /* 987 In general, the repetition specifier or "bound" is replaced here 988 by an equivalent ERE string, repeating the immediately previous atom 989 and appending ? and + as needed. Note that the first copy of the 990 atom is left in place, except in the special_case of a zero-repeat 991 (i.e., {0}). 992 */ 993 if (secondnum < 0) { /* means {n,} -> repeat n-1 times followed by PLUS */ 994 if (firstnum < 2) { 995 /* 0 or 1: should be handled before you get here */ 996 FATAL("internal error"); 997 } else { 998 return replace_repeat(reptok, reptoklen, atom, atomlen, 999 firstnum, secondnum, REPEAT_PLUS_APPENDED); 1000 } 1001 } else if (firstnum == secondnum) { /* {n} or {n,n} -> simply repeat n-1 times */ 1002 if (firstnum == 0) { /* {0} or {0,0} */ 1003 /* This case is unusual because the resulting 1004 replacement string might actually be SMALLER than 1005 the original ERE */ 1006 return replace_repeat(reptok, reptoklen, atom, atomlen, 1007 firstnum, secondnum, REPEAT_ZERO); 1008 } else { /* (firstnum >= 1) */ 1009 return replace_repeat(reptok, reptoklen, atom, atomlen, 1010 firstnum, secondnum, REPEAT_SIMPLE); 1011 } 1012 } else if (firstnum < secondnum) { /* {n,m} -> repeat n-1 times then alternate */ 1013 /* x{n,m} => xx...x{1, m-n+1} => xx...x?x?x?..x? */ 1014 return replace_repeat(reptok, reptoklen, atom, atomlen, 1015 firstnum, secondnum, REPEAT_WITH_Q); 1016 } else { /* Error - shouldn't be here (n>m) */ 1017 FATAL("internal error"); 1018 } 1019 return 0; 1020 } 1021 1022 int relex(void) /* lexical analyzer for reparse */ 1023 { 1024 int c, n; 1025 int cflag; 1026 static uschar *buf = NULL; 1027 static int bufsz = 100; 1028 uschar *bp; 1029 const struct charclass *cc; 1030 int i; 1031 int num, m; 1032 bool commafound, digitfound; 1033 const uschar *startreptok; 1034 static int parens = 0; 1035 1036 rescan: 1037 starttok = prestr; 1038 1039 switch (c = *prestr++) { 1040 case '|': return OR; 1041 case '*': return STAR; 1042 case '+': return PLUS; 1043 case '?': return QUEST; 1044 case '.': return DOT; 1045 case '\0': prestr--; return '\0'; 1046 case '^': 1047 case '$': 1048 return c; 1049 case '(': 1050 parens++; 1051 return c; 1052 case ')': 1053 if (parens) { 1054 parens--; 1055 return c; 1056 } 1057 /* unmatched close parenthesis; per POSIX, treat as literal */ 1058 rlxval = c; 1059 return CHAR; 1060 case '\\': 1061 rlxval = quoted(&prestr); 1062 return CHAR; 1063 default: 1064 rlxval = c; 1065 return CHAR; 1066 case '[': 1067 if (buf == NULL && (buf = (uschar *) malloc(bufsz)) == NULL) 1068 FATAL("out of space in reg expr %.10s..", lastre); 1069 bp = buf; 1070 if (*prestr == '^') { 1071 cflag = 1; 1072 prestr++; 1073 } 1074 else 1075 cflag = 0; 1076 n = 2 * strlen((const char *) prestr)+1; 1077 if (!adjbuf((char **) &buf, &bufsz, n, n, (char **) &bp, "relex1")) 1078 FATAL("out of space for reg expr %.10s...", lastre); 1079 for (; ; ) { 1080 if ((c = *prestr++) == '\\') { 1081 *bp++ = '\\'; 1082 if ((c = *prestr++) == '\0') 1083 FATAL("nonterminated character class %.20s...", lastre); 1084 *bp++ = c; 1085 /* } else if (c == '\n') { */ 1086 /* FATAL("newline in character class %.20s...", lastre); */ 1087 } else if (c == '[' && *prestr == ':') { 1088 /* POSIX char class names, Dag-Erling Smorgrav, des@ofug.org */ 1089 for (cc = charclasses; cc->cc_name; cc++) 1090 if (strncmp((const char *) prestr + 1, (const char *) cc->cc_name, cc->cc_namelen) == 0) 1091 break; 1092 if (cc->cc_name != NULL && prestr[1 + cc->cc_namelen] == ':' && 1093 prestr[2 + cc->cc_namelen] == ']') { 1094 prestr += cc->cc_namelen + 3; 1095 /* 1096 * BUG: We begin at 1, instead of 0, since we 1097 * would otherwise prematurely terminate the 1098 * string for classes like [[:cntrl:]]. This 1099 * means that we can't match the NUL character, 1100 * not without first adapting the entire 1101 * program to track each string's length. 1102 */ 1103 for (i = 1; i <= UCHAR_MAX; i++) { 1104 if (!adjbuf((char **) &buf, &bufsz, bp-buf+1, 100, (char **) &bp, "relex2")) 1105 FATAL("out of space for reg expr %.10s...", lastre); 1106 if (cc->cc_func(i)) { 1107 /* escape backslash */ 1108 if (i == '\\') { 1109 *bp++ = '\\'; 1110 n++; 1111 } 1112 1113 *bp++ = i; 1114 n++; 1115 } 1116 } 1117 } else 1118 *bp++ = c; 1119 } else if (c == '[' && *prestr == '.') { 1120 char collate_char; 1121 prestr++; 1122 collate_char = *prestr++; 1123 if (*prestr == '.' && prestr[1] == ']') { 1124 prestr += 2; 1125 /* Found it: map via locale TBD: for 1126 now, simply return this char. This 1127 is sufficient to pass conformance 1128 test awk.ex 156 1129 */ 1130 if (*prestr == ']') { 1131 prestr++; 1132 rlxval = collate_char; 1133 return CHAR; 1134 } 1135 } 1136 } else if (c == '[' && *prestr == '=') { 1137 char equiv_char; 1138 prestr++; 1139 equiv_char = *prestr++; 1140 if (*prestr == '=' && prestr[1] == ']') { 1141 prestr += 2; 1142 /* Found it: map via locale TBD: for now 1143 simply return this char. This is 1144 sufficient to pass conformance test 1145 awk.ex 156 1146 */ 1147 if (*prestr == ']') { 1148 prestr++; 1149 rlxval = equiv_char; 1150 return CHAR; 1151 } 1152 } 1153 } else if (c == '\0') { 1154 FATAL("nonterminated character class %.20s", lastre); 1155 } else if (bp == buf) { /* 1st char is special */ 1156 *bp++ = c; 1157 } else if (c == ']') { 1158 *bp++ = 0; 1159 rlxstr = (uschar *) tostring((char *) buf); 1160 if (cflag == 0) 1161 return CCL; 1162 else 1163 return NCCL; 1164 } else 1165 *bp++ = c; 1166 } 1167 break; 1168 case '{': 1169 if (isdigit(*(prestr))) { 1170 num = 0; /* Process as a repetition */ 1171 n = -1; m = -1; 1172 commafound = false; 1173 digitfound = false; 1174 startreptok = prestr-1; 1175 /* Remember start of previous atom here ? */ 1176 } else { /* just a { char, not a repetition */ 1177 rlxval = c; 1178 return CHAR; 1179 } 1180 for (; ; ) { 1181 if ((c = *prestr++) == '}') { 1182 if (commafound) { 1183 if (digitfound) { /* {n,m} */ 1184 m = num; 1185 if (m < n) 1186 FATAL("illegal repetition expression: class %.20s", 1187 lastre); 1188 if (n == 0 && m == 1) { 1189 return QUEST; 1190 } 1191 } else { /* {n,} */ 1192 if (n == 0) 1193 return STAR; 1194 else if (n == 1) 1195 return PLUS; 1196 } 1197 } else { 1198 if (digitfound) { /* {n} same as {n,n} */ 1199 n = num; 1200 m = num; 1201 } else { /* {} */ 1202 FATAL("illegal repetition expression: class %.20s", 1203 lastre); 1204 } 1205 } 1206 if (repeat(starttok, prestr-starttok, lastatom, 1207 startreptok - lastatom, n, m) > 0) { 1208 if (n == 0 && m == 0) { 1209 return ZERO; 1210 } 1211 /* must rescan input for next token */ 1212 goto rescan; 1213 } 1214 /* Failed to replace: eat up {...} characters 1215 and treat like just PLUS */ 1216 return PLUS; 1217 } else if (c == '\0') { 1218 FATAL("nonterminated character class %.20s", 1219 lastre); 1220 } else if (isdigit(c)) { 1221 num = 10 * num + c - '0'; 1222 digitfound = true; 1223 } else if (c == ',') { 1224 if (commafound) 1225 FATAL("illegal repetition expression: class %.20s", 1226 lastre); 1227 /* looking for {n,} or {n,m} */ 1228 commafound = true; 1229 n = num; 1230 digitfound = false; /* reset */ 1231 num = 0; 1232 } else { 1233 FATAL("illegal repetition expression: class %.20s", 1234 lastre); 1235 } 1236 } 1237 break; 1238 } 1239 } 1240 1241 int cgoto(fa *f, int s, int c) 1242 { 1243 int *p, *q; 1244 int i, j, k; 1245 1246 assert(c == HAT || c < NCHARS); 1247 while (f->accept >= maxsetvec) { /* guessing here! */ 1248 resizesetvec(__func__); 1249 } 1250 for (i = 0; i <= f->accept; i++) 1251 setvec[i] = 0; 1252 setcnt = 0; 1253 resize_state(f, s); 1254 /* compute positions of gototab[s,c] into setvec */ 1255 p = f->posns[s]; 1256 for (i = 1; i <= *p; i++) { 1257 if ((k = f->re[p[i]].ltype) != FINAL) { 1258 if ((k == CHAR && c == ptoi(f->re[p[i]].lval.np)) 1259 || (k == DOT && c != 0 && c != HAT) 1260 || (k == ALL && c != 0) 1261 || (k == EMPTYRE && c != 0) 1262 || (k == CCL && member(c, (char *) f->re[p[i]].lval.up)) 1263 || (k == NCCL && !member(c, (char *) f->re[p[i]].lval.up) && c != 0 && c != HAT)) { 1264 q = f->re[p[i]].lfollow; 1265 for (j = 1; j <= *q; j++) { 1266 if (q[j] >= maxsetvec) { 1267 resizesetvec(__func__); 1268 } 1269 if (setvec[q[j]] == 0) { 1270 setcnt++; 1271 setvec[q[j]] = 1; 1272 } 1273 } 1274 } 1275 } 1276 } 1277 /* determine if setvec is a previous state */ 1278 tmpset[0] = setcnt; 1279 j = 1; 1280 for (i = f->accept; i >= 0; i--) 1281 if (setvec[i]) { 1282 tmpset[j++] = i; 1283 } 1284 resize_state(f, f->curstat > s ? f->curstat : s); 1285 /* tmpset == previous state? */ 1286 for (i = 1; i <= f->curstat; i++) { 1287 p = f->posns[i]; 1288 if ((k = tmpset[0]) != p[0]) 1289 goto different; 1290 for (j = 1; j <= k; j++) 1291 if (tmpset[j] != p[j]) 1292 goto different; 1293 /* setvec is state i */ 1294 if (c != HAT) 1295 f->gototab[s][c] = i; 1296 return i; 1297 different:; 1298 } 1299 1300 /* add tmpset to current set of states */ 1301 ++(f->curstat); 1302 resize_state(f, f->curstat); 1303 for (i = 0; i < NCHARS; i++) 1304 f->gototab[f->curstat][i] = 0; 1305 xfree(f->posns[f->curstat]); 1306 p = intalloc(setcnt + 1, __func__); 1307 1308 f->posns[f->curstat] = p; 1309 if (c != HAT) 1310 f->gototab[s][c] = f->curstat; 1311 for (i = 0; i <= setcnt; i++) 1312 p[i] = tmpset[i]; 1313 if (setvec[f->accept]) 1314 f->out[f->curstat] = 1; 1315 else 1316 f->out[f->curstat] = 0; 1317 return f->curstat; 1318 } 1319 1320 1321 void freefa(fa *f) /* free a finite automaton */ 1322 { 1323 int i; 1324 1325 if (f == NULL) 1326 return; 1327 for (i = 0; i < f->state_count; i++) 1328 xfree(f->gototab[i]) 1329 for (i = 0; i <= f->curstat; i++) 1330 xfree(f->posns[i]); 1331 for (i = 0; i <= f->accept; i++) { 1332 xfree(f->re[i].lfollow); 1333 if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL) 1334 xfree(f->re[i].lval.np); 1335 } 1336 xfree(f->restr); 1337 xfree(f->out); 1338 xfree(f->posns); 1339 xfree(f->gototab); 1340 xfree(f); 1341 } 1342