1 /* $OpenBSD: b.c,v 1.16 2010/06/13 17:58:19 millert Exp $ */ 2 /**************************************************************** 3 Copyright (C) Lucent Technologies 1997 4 All Rights Reserved 5 6 Permission to use, copy, modify, and distribute this software and 7 its documentation for any purpose and without fee is hereby 8 granted, provided that the above copyright notice appear in all 9 copies and that both that the copyright notice and this 10 permission notice and warranty disclaimer appear in supporting 11 documentation, and that the name Lucent Technologies or any of 12 its entities not be used in advertising or publicity pertaining 13 to distribution of the software without specific, written prior 14 permission. 15 16 LUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, 17 INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 18 IN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY 19 SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 20 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER 21 IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 22 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF 23 THIS SOFTWARE. 24 ****************************************************************/ 25 26 /* lasciate ogne speranza, voi ch'intrate. */ 27 28 #define DEBUG 29 30 #include <ctype.h> 31 #include <stdio.h> 32 #include <string.h> 33 #include <stdlib.h> 34 #include "awk.h" 35 #include "ytab.h" 36 37 #define HAT (NCHARS+2) /* matches ^ in regular expr */ 38 /* NCHARS is 2**n */ 39 #define MAXLIN 22 40 41 #define type(v) (v)->nobj /* badly overloaded here */ 42 #define info(v) (v)->ntype /* badly overloaded here */ 43 #define left(v) (v)->narg[0] 44 #define right(v) (v)->narg[1] 45 #define parent(v) (v)->nnext 46 47 #define LEAF case CCL: case NCCL: case CHAR: case DOT: case FINAL: case ALL: 48 #define ELEAF case EMPTYRE: /* empty string in regexp */ 49 #define UNARY case STAR: case PLUS: case QUEST: 50 51 /* encoding in tree Nodes: 52 leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL, EMPTYRE): 53 left is index, right contains value or pointer to value 54 unary (STAR, PLUS, QUEST): left is child, right is null 55 binary (CAT, OR): left and right are children 56 parent contains pointer to parent 57 */ 58 59 60 int *setvec; 61 int *tmpset; 62 int maxsetvec = 0; 63 64 int rtok; /* next token in current re */ 65 int rlxval; 66 static uschar *rlxstr; 67 static uschar *prestr; /* current position in current re */ 68 static uschar *lastre; /* origin of last re */ 69 70 static int setcnt; 71 static int poscnt; 72 73 char *patbeg; 74 int patlen; 75 76 #define NFA 20 /* cache this many dynamic fa's */ 77 fa *fatab[NFA]; 78 int nfatab = 0; /* entries in fatab */ 79 80 fa *makedfa(const char *s, int anchor) /* returns dfa for reg expr s */ 81 { 82 int i, use, nuse; 83 fa *pfa; 84 static int now = 1; 85 86 if (setvec == 0) { /* first time through any RE */ 87 maxsetvec = MAXLIN; 88 setvec = (int *) calloc(maxsetvec, sizeof(int)); 89 tmpset = (int *) calloc(maxsetvec, sizeof(int)); 90 if (setvec == 0 || tmpset == 0) 91 overflo("out of space initializing makedfa"); 92 } 93 94 if (compile_time) /* a constant for sure */ 95 return mkdfa(s, anchor); 96 for (i = 0; i < nfatab; i++) /* is it there already? */ 97 if (fatab[i]->anchor == anchor 98 && strcmp((const char *) fatab[i]->restr, s) == 0) { 99 fatab[i]->use = now++; 100 return fatab[i]; 101 } 102 pfa = mkdfa(s, anchor); 103 if (nfatab < NFA) { /* room for another */ 104 fatab[nfatab] = pfa; 105 fatab[nfatab]->use = now++; 106 nfatab++; 107 return pfa; 108 } 109 use = fatab[0]->use; /* replace least-recently used */ 110 nuse = 0; 111 for (i = 1; i < nfatab; i++) 112 if (fatab[i]->use < use) { 113 use = fatab[i]->use; 114 nuse = i; 115 } 116 freefa(fatab[nuse]); 117 fatab[nuse] = pfa; 118 pfa->use = now++; 119 return pfa; 120 } 121 122 fa *mkdfa(const char *s, int anchor) /* does the real work of making a dfa */ 123 /* anchor = 1 for anchored matches, else 0 */ 124 { 125 Node *p, *p1; 126 fa *f; 127 128 p = reparse(s); 129 p1 = op2(CAT, op2(STAR, op2(ALL, NIL, NIL), NIL), p); 130 /* put ALL STAR in front of reg. exp. */ 131 p1 = op2(CAT, p1, op2(FINAL, NIL, NIL)); 132 /* put FINAL after reg. exp. */ 133 134 poscnt = 0; 135 penter(p1); /* enter parent pointers and leaf indices */ 136 if ((f = (fa *) calloc(1, sizeof(fa) + poscnt*sizeof(rrow))) == NULL) 137 overflo("out of space for fa"); 138 f->accept = poscnt-1; /* penter has computed number of positions in re */ 139 cfoll(f, p1); /* set up follow sets */ 140 freetr(p1); 141 if ((f->posns[0] = (int *) calloc(*(f->re[0].lfollow), sizeof(int))) == NULL) 142 overflo("out of space in makedfa"); 143 if ((f->posns[1] = (int *) calloc(1, sizeof(int))) == NULL) 144 overflo("out of space in makedfa"); 145 *f->posns[1] = 0; 146 f->initstat = makeinit(f, anchor); 147 f->anchor = anchor; 148 f->restr = (uschar *) tostring(s); 149 return f; 150 } 151 152 int makeinit(fa *f, int anchor) 153 { 154 int i, k; 155 156 f->curstat = 2; 157 f->out[2] = 0; 158 f->reset = 0; 159 k = *(f->re[0].lfollow); 160 xfree(f->posns[2]); 161 if ((f->posns[2] = (int *) calloc(k+1, sizeof(int))) == NULL) 162 overflo("out of space in makeinit"); 163 for (i=0; i <= k; i++) { 164 (f->posns[2])[i] = (f->re[0].lfollow)[i]; 165 } 166 if ((f->posns[2])[1] == f->accept) 167 f->out[2] = 1; 168 for (i=0; i < NCHARS; i++) 169 f->gototab[2][i] = 0; 170 f->curstat = cgoto(f, 2, HAT); 171 if (anchor) { 172 *f->posns[2] = k-1; /* leave out position 0 */ 173 for (i=0; i < k; i++) { 174 (f->posns[0])[i] = (f->posns[2])[i]; 175 } 176 177 f->out[0] = f->out[2]; 178 if (f->curstat != 2) 179 --(*f->posns[f->curstat]); 180 } 181 return f->curstat; 182 } 183 184 void penter(Node *p) /* set up parent pointers and leaf indices */ 185 { 186 switch (type(p)) { 187 ELEAF 188 LEAF 189 info(p) = poscnt; 190 poscnt++; 191 break; 192 UNARY 193 penter(left(p)); 194 parent(left(p)) = p; 195 break; 196 case CAT: 197 case OR: 198 penter(left(p)); 199 penter(right(p)); 200 parent(left(p)) = p; 201 parent(right(p)) = p; 202 break; 203 default: /* can't happen */ 204 FATAL("can't happen: unknown type %d in penter", type(p)); 205 break; 206 } 207 } 208 209 void freetr(Node *p) /* free parse tree */ 210 { 211 switch (type(p)) { 212 ELEAF 213 LEAF 214 xfree(p); 215 break; 216 UNARY 217 freetr(left(p)); 218 xfree(p); 219 break; 220 case CAT: 221 case OR: 222 freetr(left(p)); 223 freetr(right(p)); 224 xfree(p); 225 break; 226 default: /* can't happen */ 227 FATAL("can't happen: unknown type %d in freetr", type(p)); 228 break; 229 } 230 } 231 232 /* in the parsing of regular expressions, metacharacters like . have */ 233 /* to be seen literally; \056 is not a metacharacter. */ 234 235 int hexstr(char **pp) /* find and eval hex string at pp, return new p */ 236 { /* only pick up one 8-bit byte (2 chars) */ 237 uschar *p; 238 int n = 0; 239 int i; 240 241 for (i = 0, p = (uschar *) *pp; i < 2 && isxdigit(*p); i++, p++) { 242 if (isdigit(*p)) 243 n = 16 * n + *p - '0'; 244 else if (*p >= 'a' && *p <= 'f') 245 n = 16 * n + *p - 'a' + 10; 246 else if (*p >= 'A' && *p <= 'F') 247 n = 16 * n + *p - 'A' + 10; 248 } 249 *pp = (char *) p; 250 return n; 251 } 252 253 #define isoctdigit(c) ((c) >= '0' && (c) <= '7') /* multiple use of arg */ 254 255 int quoted(char **pp) /* pick up next thing after a \\ */ 256 /* and increment *pp */ 257 { 258 char *p = *pp; 259 int c; 260 261 if ((c = *p++) == 't') 262 c = '\t'; 263 else if (c == 'n') 264 c = '\n'; 265 else if (c == 'f') 266 c = '\f'; 267 else if (c == 'r') 268 c = '\r'; 269 else if (c == 'b') 270 c = '\b'; 271 else if (c == '\\') 272 c = '\\'; 273 else if (c == 'x') { /* hexadecimal goo follows */ 274 c = hexstr(&p); /* this adds a null if number is invalid */ 275 } else if (isoctdigit(c)) { /* \d \dd \ddd */ 276 int n = c - '0'; 277 if (isoctdigit(*p)) { 278 n = 8 * n + *p++ - '0'; 279 if (isoctdigit(*p)) 280 n = 8 * n + *p++ - '0'; 281 } 282 c = n; 283 } /* else */ 284 /* c = c; */ 285 *pp = p; 286 return c; 287 } 288 289 char *cclenter(const char *argp) /* add a character class */ 290 { 291 int i, c, c2; 292 uschar *p = (uschar *) argp; 293 uschar *op, *bp; 294 static uschar *buf = 0; 295 static int bufsz = 100; 296 297 op = p; 298 if (buf == 0 && (buf = (uschar *) malloc(bufsz)) == NULL) 299 FATAL("out of space for character class [%.10s...] 1", p); 300 bp = buf; 301 for (i = 0; (c = *p++) != 0; ) { 302 if (c == '\\') { 303 c = quoted((char **) &p); 304 } else if (c == '-' && i > 0 && bp[-1] != 0) { 305 if (*p != 0) { 306 c = bp[-1]; 307 c2 = *p++; 308 if (c2 == '\\') 309 c2 = quoted((char **) &p); 310 if (c > c2) { /* empty; ignore */ 311 bp--; 312 i--; 313 continue; 314 } 315 while (c < c2) { 316 if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, "cclenter1")) 317 FATAL("out of space for character class [%.10s...] 2", p); 318 *bp++ = ++c; 319 i++; 320 } 321 continue; 322 } 323 } 324 if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, "cclenter2")) 325 FATAL("out of space for character class [%.10s...] 3", p); 326 *bp++ = c; 327 i++; 328 } 329 *bp = 0; 330 dprintf( ("cclenter: in = |%s|, out = |%s|\n", op, buf) ); 331 xfree(op); 332 return (char *) tostring((char *) buf); 333 } 334 335 void overflo(const char *s) 336 { 337 FATAL("regular expression too big: %.30s...", s); 338 } 339 340 void cfoll(fa *f, Node *v) /* enter follow set of each leaf of vertex v into lfollow[leaf] */ 341 { 342 int i; 343 int *p; 344 345 switch (type(v)) { 346 ELEAF 347 LEAF 348 f->re[info(v)].ltype = type(v); 349 f->re[info(v)].lval.np = right(v); 350 while (f->accept >= maxsetvec) { /* guessing here! */ 351 maxsetvec *= 4; 352 setvec = (int *) realloc(setvec, maxsetvec * sizeof(int)); 353 tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int)); 354 if (setvec == 0 || tmpset == 0) 355 overflo("out of space in cfoll()"); 356 } 357 for (i = 0; i <= f->accept; i++) 358 setvec[i] = 0; 359 setcnt = 0; 360 follow(v); /* computes setvec and setcnt */ 361 if ((p = (int *) calloc(setcnt+1, sizeof(int))) == NULL) 362 overflo("out of space building follow set"); 363 f->re[info(v)].lfollow = p; 364 *p = setcnt; 365 for (i = f->accept; i >= 0; i--) 366 if (setvec[i] == 1) 367 *++p = i; 368 break; 369 UNARY 370 cfoll(f,left(v)); 371 break; 372 case CAT: 373 case OR: 374 cfoll(f,left(v)); 375 cfoll(f,right(v)); 376 break; 377 default: /* can't happen */ 378 FATAL("can't happen: unknown type %d in cfoll", type(v)); 379 } 380 } 381 382 int first(Node *p) /* collects initially active leaves of p into setvec */ 383 /* returns 0 if p matches empty string */ 384 { 385 int b, lp; 386 387 switch (type(p)) { 388 ELEAF 389 LEAF 390 lp = info(p); /* look for high-water mark of subscripts */ 391 while (setcnt >= maxsetvec || lp >= maxsetvec) { /* guessing here! */ 392 maxsetvec *= 4; 393 setvec = (int *) realloc(setvec, maxsetvec * sizeof(int)); 394 tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int)); 395 if (setvec == 0 || tmpset == 0) 396 overflo("out of space in first()"); 397 } 398 if (type(p) == EMPTYRE) { 399 setvec[lp] = 0; 400 return(0); 401 } 402 if (setvec[lp] != 1) { 403 setvec[lp] = 1; 404 setcnt++; 405 } 406 if (type(p) == CCL && (*(char *) right(p)) == '\0') 407 return(0); /* empty CCL */ 408 else return(1); 409 case PLUS: 410 if (first(left(p)) == 0) return(0); 411 return(1); 412 case STAR: 413 case QUEST: 414 first(left(p)); 415 return(0); 416 case CAT: 417 if (first(left(p)) == 0 && first(right(p)) == 0) return(0); 418 return(1); 419 case OR: 420 b = first(right(p)); 421 if (first(left(p)) == 0 || b == 0) return(0); 422 return(1); 423 } 424 FATAL("can't happen: unknown type %d in first", type(p)); /* can't happen */ 425 return(-1); 426 } 427 428 void follow(Node *v) /* collects leaves that can follow v into setvec */ 429 { 430 Node *p; 431 432 if (type(v) == FINAL) 433 return; 434 p = parent(v); 435 switch (type(p)) { 436 case STAR: 437 case PLUS: 438 first(v); 439 follow(p); 440 return; 441 442 case OR: 443 case QUEST: 444 follow(p); 445 return; 446 447 case CAT: 448 if (v == left(p)) { /* v is left child of p */ 449 if (first(right(p)) == 0) { 450 follow(p); 451 return; 452 } 453 } else /* v is right child */ 454 follow(p); 455 return; 456 } 457 } 458 459 int member(int c, const char *sarg) /* is c in s? */ 460 { 461 uschar *s = (uschar *) sarg; 462 463 while (*s) 464 if (c == *s++) 465 return(1); 466 return(0); 467 } 468 469 int match(fa *f, const char *p0) /* shortest match ? */ 470 { 471 int s, ns; 472 uschar *p = (uschar *) p0; 473 474 s = f->reset ? makeinit(f,0) : f->initstat; 475 if (f->out[s]) 476 return(1); 477 do { 478 /* assert(*p < NCHARS); */ 479 if ((ns = f->gototab[s][*p]) != 0) 480 s = ns; 481 else 482 s = cgoto(f, s, *p); 483 if (f->out[s]) 484 return(1); 485 } while (*p++ != 0); 486 return(0); 487 } 488 489 int pmatch(fa *f, const char *p0) /* longest match, for sub */ 490 { 491 int s, ns; 492 uschar *p = (uschar *) p0; 493 uschar *q; 494 int i, k; 495 496 /* s = f->reset ? makeinit(f,1) : f->initstat; */ 497 if (f->reset) { 498 f->initstat = s = makeinit(f,1); 499 } else { 500 s = f->initstat; 501 } 502 patbeg = (char *) p; 503 patlen = -1; 504 do { 505 q = p; 506 do { 507 if (f->out[s]) /* final state */ 508 patlen = q-p; 509 /* assert(*q < NCHARS); */ 510 if ((ns = f->gototab[s][*q]) != 0) 511 s = ns; 512 else 513 s = cgoto(f, s, *q); 514 if (s == 1) { /* no transition */ 515 if (patlen >= 0) { 516 patbeg = (char *) p; 517 return(1); 518 } 519 else 520 goto nextin; /* no match */ 521 } 522 } while (*q++ != 0); 523 if (f->out[s]) 524 patlen = q-p-1; /* don't count $ */ 525 if (patlen >= 0) { 526 patbeg = (char *) p; 527 return(1); 528 } 529 nextin: 530 s = 2; 531 if (f->reset) { 532 for (i = 2; i <= f->curstat; i++) 533 xfree(f->posns[i]); 534 k = *f->posns[0]; 535 if ((f->posns[2] = (int *) calloc(k+1, sizeof(int))) == NULL) 536 overflo("out of space in pmatch"); 537 for (i = 0; i <= k; i++) 538 (f->posns[2])[i] = (f->posns[0])[i]; 539 f->initstat = f->curstat = 2; 540 f->out[2] = f->out[0]; 541 for (i = 0; i < NCHARS; i++) 542 f->gototab[2][i] = 0; 543 } 544 } while (*p++ != 0); 545 return (0); 546 } 547 548 int nematch(fa *f, const char *p0) /* non-empty match, for sub */ 549 { 550 int s, ns; 551 uschar *p = (uschar *) p0; 552 uschar *q; 553 int i, k; 554 555 /* s = f->reset ? makeinit(f,1) : f->initstat; */ 556 if (f->reset) { 557 f->initstat = s = makeinit(f,1); 558 } else { 559 s = f->initstat; 560 } 561 patlen = -1; 562 while (*p) { 563 q = p; 564 do { 565 if (f->out[s]) /* final state */ 566 patlen = q-p; 567 /* assert(*q < NCHARS); */ 568 if ((ns = f->gototab[s][*q]) != 0) 569 s = ns; 570 else 571 s = cgoto(f, s, *q); 572 if (s == 1) { /* no transition */ 573 if (patlen > 0) { 574 patbeg = (char *) p; 575 return(1); 576 } else 577 goto nnextin; /* no nonempty match */ 578 } 579 } while (*q++ != 0); 580 if (f->out[s]) 581 patlen = q-p-1; /* don't count $ */ 582 if (patlen > 0 ) { 583 patbeg = (char *) p; 584 return(1); 585 } 586 nnextin: 587 s = 2; 588 if (f->reset) { 589 for (i = 2; i <= f->curstat; i++) 590 xfree(f->posns[i]); 591 k = *f->posns[0]; 592 if ((f->posns[2] = (int *) calloc(k+1, sizeof(int))) == NULL) 593 overflo("out of state space"); 594 for (i = 0; i <= k; i++) 595 (f->posns[2])[i] = (f->posns[0])[i]; 596 f->initstat = f->curstat = 2; 597 f->out[2] = f->out[0]; 598 for (i = 0; i < NCHARS; i++) 599 f->gototab[2][i] = 0; 600 } 601 p++; 602 } 603 return (0); 604 } 605 606 Node *reparse(const char *p) /* parses regular expression pointed to by p */ 607 { /* uses relex() to scan regular expression */ 608 Node *np; 609 610 dprintf( ("reparse <%s>\n", p) ); 611 lastre = prestr = (uschar *) p; /* prestr points to string to be parsed */ 612 rtok = relex(); 613 /* GNU compatibility: an empty regexp matches anything */ 614 if (rtok == '\0') { 615 /* FATAL("empty regular expression"); previous */ 616 return(op2(EMPTYRE, NIL, NIL)); 617 } 618 np = regexp(); 619 if (rtok != '\0') 620 FATAL("syntax error in regular expression %s at %s", lastre, prestr); 621 return(np); 622 } 623 624 Node *regexp(void) /* top-level parse of reg expr */ 625 { 626 return (alt(concat(primary()))); 627 } 628 629 Node *primary(void) 630 { 631 Node *np; 632 633 switch (rtok) { 634 case CHAR: 635 np = op2(CHAR, NIL, itonp(rlxval)); 636 rtok = relex(); 637 return (unary(np)); 638 case ALL: 639 rtok = relex(); 640 return (unary(op2(ALL, NIL, NIL))); 641 case EMPTYRE: 642 rtok = relex(); 643 return (unary(op2(ALL, NIL, NIL))); 644 case DOT: 645 rtok = relex(); 646 return (unary(op2(DOT, NIL, NIL))); 647 case CCL: 648 np = op2(CCL, NIL, (Node*) cclenter((char *) rlxstr)); 649 rtok = relex(); 650 return (unary(np)); 651 case NCCL: 652 np = op2(NCCL, NIL, (Node *) cclenter((char *) rlxstr)); 653 rtok = relex(); 654 return (unary(np)); 655 case '^': 656 rtok = relex(); 657 return (unary(op2(CHAR, NIL, itonp(HAT)))); 658 case '$': 659 rtok = relex(); 660 return (unary(op2(CHAR, NIL, NIL))); 661 case '(': 662 rtok = relex(); 663 if (rtok == ')') { /* special pleading for () */ 664 rtok = relex(); 665 return unary(op2(CCL, NIL, (Node *) tostring(""))); 666 } 667 np = regexp(); 668 if (rtok == ')') { 669 rtok = relex(); 670 return (unary(np)); 671 } 672 else 673 FATAL("syntax error in regular expression %s at %s", lastre, prestr); 674 default: 675 FATAL("illegal primary in regular expression %s at %s", lastre, prestr); 676 } 677 return 0; /*NOTREACHED*/ 678 } 679 680 Node *concat(Node *np) 681 { 682 switch (rtok) { 683 case CHAR: case DOT: case ALL: case EMPTYRE: case CCL: case NCCL: case '$': case '(': 684 return (concat(op2(CAT, np, primary()))); 685 } 686 return (np); 687 } 688 689 Node *alt(Node *np) 690 { 691 if (rtok == OR) { 692 rtok = relex(); 693 return (alt(op2(OR, np, concat(primary())))); 694 } 695 return (np); 696 } 697 698 Node *unary(Node *np) 699 { 700 switch (rtok) { 701 case STAR: 702 rtok = relex(); 703 return (unary(op2(STAR, np, NIL))); 704 case PLUS: 705 rtok = relex(); 706 return (unary(op2(PLUS, np, NIL))); 707 case QUEST: 708 rtok = relex(); 709 return (unary(op2(QUEST, np, NIL))); 710 default: 711 return (np); 712 } 713 } 714 715 /* 716 * Character class definitions conformant to the POSIX locale as 717 * defined in IEEE P1003.1 draft 7 of June 2001, assuming the source 718 * and operating character sets are both ASCII (ISO646) or supersets 719 * thereof. 720 * 721 * Note that to avoid overflowing the temporary buffer used in 722 * relex(), the expanded character class (prior to range expansion) 723 * must be less than twice the size of their full name. 724 */ 725 726 /* Because isblank doesn't show up in any of the header files on any 727 * system i use, it's defined here. if some other locale has a richer 728 * definition of "blank", define HAS_ISBLANK and provide your own 729 * version. 730 * the parentheses here are an attempt to find a path through the maze 731 * of macro definition and/or function and/or version provided. thanks 732 * to nelson beebe for the suggestion; let's see if it works everywhere. 733 */ 734 735 #ifndef HAS_ISBLANK 736 737 int (isblank)(int c) 738 { 739 return c==' ' || c=='\t'; 740 } 741 742 #endif 743 744 struct charclass { 745 const char *cc_name; 746 int cc_namelen; 747 int (*cc_func)(int); 748 } charclasses[] = { 749 { "alnum", 5, isalnum }, 750 { "alpha", 5, isalpha }, 751 { "blank", 5, isblank }, 752 { "cntrl", 5, iscntrl }, 753 { "digit", 5, isdigit }, 754 { "graph", 5, isgraph }, 755 { "lower", 5, islower }, 756 { "print", 5, isprint }, 757 { "punct", 5, ispunct }, 758 { "space", 5, isspace }, 759 { "upper", 5, isupper }, 760 { "xdigit", 6, isxdigit }, 761 { NULL, 0, NULL }, 762 }; 763 764 765 int relex(void) /* lexical analyzer for reparse */ 766 { 767 int c, n; 768 int cflag; 769 static uschar *buf = 0; 770 static int bufsz = 100; 771 uschar *bp; 772 struct charclass *cc; 773 int i; 774 775 switch (c = *prestr++) { 776 case '|': return OR; 777 case '*': return STAR; 778 case '+': return PLUS; 779 case '?': return QUEST; 780 case '.': return DOT; 781 case '\0': prestr--; return '\0'; 782 case '^': 783 case '$': 784 case '(': 785 case ')': 786 return c; 787 case '\\': 788 rlxval = quoted((char **) &prestr); 789 return CHAR; 790 default: 791 rlxval = c; 792 return CHAR; 793 case '[': 794 if (buf == 0 && (buf = (uschar *) malloc(bufsz)) == NULL) 795 FATAL("out of space in reg expr %.10s..", lastre); 796 bp = buf; 797 if (*prestr == '^') { 798 cflag = 1; 799 prestr++; 800 } 801 else 802 cflag = 0; 803 n = 2 * strlen((const char *) prestr)+1; 804 if (!adjbuf((char **) &buf, &bufsz, n, n, (char **) &bp, "relex1")) 805 FATAL("out of space for reg expr %.10s...", lastre); 806 for (; ; ) { 807 if ((c = *prestr++) == '\\') { 808 *bp++ = '\\'; 809 if ((c = *prestr++) == '\0') 810 FATAL("nonterminated character class %.20s...", lastre); 811 *bp++ = c; 812 /* } else if (c == '\n') { */ 813 /* FATAL("newline in character class %.20s...", lastre); */ 814 } else if (c == '[' && *prestr == ':') { 815 /* POSIX char class names, Dag-Erling Smorgrav, des@ofug.org */ 816 for (cc = charclasses; cc->cc_name; cc++) 817 if (strncmp((const char *) prestr + 1, (const char *) cc->cc_name, cc->cc_namelen) == 0) 818 break; 819 if (cc->cc_name != NULL && prestr[1 + cc->cc_namelen] == ':' && 820 prestr[2 + cc->cc_namelen] == ']') { 821 prestr += cc->cc_namelen + 3; 822 for (i = 0; i < NCHARS; i++) { 823 if (!adjbuf((char **) &buf, &bufsz, bp-buf+1, 100, (char **) &bp, "relex2")) 824 FATAL("out of space for reg expr %.10s...", lastre); 825 if (cc->cc_func(i)) { 826 *bp++ = i; 827 n++; 828 } 829 } 830 } else 831 *bp++ = c; 832 } else if (c == '\0') { 833 FATAL("nonterminated character class %.20s", lastre); 834 } else if (bp == buf) { /* 1st char is special */ 835 *bp++ = c; 836 } else if (c == ']') { 837 *bp++ = 0; 838 rlxstr = (uschar *) tostring((char *) buf); 839 if (cflag == 0) 840 return CCL; 841 else 842 return NCCL; 843 } else 844 *bp++ = c; 845 } 846 } 847 } 848 849 int cgoto(fa *f, int s, int c) 850 { 851 int i, j, k; 852 int *p, *q; 853 854 assert(c == HAT || c < NCHARS); 855 while (f->accept >= maxsetvec) { /* guessing here! */ 856 maxsetvec *= 4; 857 setvec = (int *) realloc(setvec, maxsetvec * sizeof(int)); 858 tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int)); 859 if (setvec == 0 || tmpset == 0) 860 overflo("out of space in cgoto()"); 861 } 862 for (i = 0; i <= f->accept; i++) 863 setvec[i] = 0; 864 setcnt = 0; 865 /* compute positions of gototab[s,c] into setvec */ 866 p = f->posns[s]; 867 for (i = 1; i <= *p; i++) { 868 if ((k = f->re[p[i]].ltype) != FINAL) { 869 if ((k == CHAR && c == ptoi(f->re[p[i]].lval.np)) 870 || (k == DOT && c != 0 && c != HAT) 871 || (k == ALL && c != 0) 872 || (k == EMPTYRE && c != 0) 873 || (k == CCL && member(c, (char *) f->re[p[i]].lval.up)) 874 || (k == NCCL && !member(c, (char *) f->re[p[i]].lval.up) && c != 0 && c != HAT)) { 875 q = f->re[p[i]].lfollow; 876 for (j = 1; j <= *q; j++) { 877 if (q[j] >= maxsetvec) { 878 maxsetvec *= 4; 879 setvec = (int *) realloc(setvec, maxsetvec * sizeof(int)); 880 tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int)); 881 if (setvec == 0 || tmpset == 0) 882 overflo("cgoto overflow"); 883 } 884 if (setvec[q[j]] == 0) { 885 setcnt++; 886 setvec[q[j]] = 1; 887 } 888 } 889 } 890 } 891 } 892 /* determine if setvec is a previous state */ 893 tmpset[0] = setcnt; 894 j = 1; 895 for (i = f->accept; i >= 0; i--) 896 if (setvec[i]) { 897 tmpset[j++] = i; 898 } 899 /* tmpset == previous state? */ 900 for (i = 1; i <= f->curstat; i++) { 901 p = f->posns[i]; 902 if ((k = tmpset[0]) != p[0]) 903 goto different; 904 for (j = 1; j <= k; j++) 905 if (tmpset[j] != p[j]) 906 goto different; 907 /* setvec is state i */ 908 f->gototab[s][c] = i; 909 return i; 910 different:; 911 } 912 913 /* add tmpset to current set of states */ 914 if (f->curstat >= NSTATES-1) { 915 f->curstat = 2; 916 f->reset = 1; 917 for (i = 2; i < NSTATES; i++) 918 xfree(f->posns[i]); 919 } else 920 ++(f->curstat); 921 for (i = 0; i < NCHARS; i++) 922 f->gototab[f->curstat][i] = 0; 923 xfree(f->posns[f->curstat]); 924 if ((p = (int *) calloc(setcnt+1, sizeof(int))) == NULL) 925 overflo("out of space in cgoto"); 926 927 f->posns[f->curstat] = p; 928 f->gototab[s][c] = f->curstat; 929 for (i = 0; i <= setcnt; i++) 930 p[i] = tmpset[i]; 931 if (setvec[f->accept]) 932 f->out[f->curstat] = 1; 933 else 934 f->out[f->curstat] = 0; 935 return f->curstat; 936 } 937 938 939 void freefa(fa *f) /* free a finite automaton */ 940 { 941 int i; 942 943 if (f == NULL) 944 return; 945 for (i = 0; i <= f->curstat; i++) 946 xfree(f->posns[i]); 947 for (i = 0; i <= f->accept; i++) { 948 xfree(f->re[i].lfollow); 949 if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL) 950 xfree((f->re[i].lval.np)); 951 } 952 xfree(f->restr); 953 xfree(f); 954 } 955