b.c (22878B)
1 /* $OpenBSD: b.c,v 1.17 2011/09/28 19:27:18 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(uschar **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 = (uschar *) p; 250 return n; 251 } 252 253 #define isoctdigit(c) ((c) >= '0' && (c) <= '7') /* multiple use of arg */ 254 255 int quoted(uschar **pp) /* pick up next thing after a \\ */ 256 /* and increment *pp */ 257 { 258 uschar *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(&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(&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 (xisblank)(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 #ifndef HAS_ISBLANK 752 { "blank", 5, isspace }, /* was isblank */ 753 #else 754 { "blank", 5, isblank }, 755 #endif 756 { "cntrl", 5, iscntrl }, 757 { "digit", 5, isdigit }, 758 { "graph", 5, isgraph }, 759 { "lower", 5, islower }, 760 { "print", 5, isprint }, 761 { "punct", 5, ispunct }, 762 { "space", 5, isspace }, 763 { "upper", 5, isupper }, 764 { "xdigit", 6, isxdigit }, 765 { NULL, 0, NULL }, 766 }; 767 768 769 int relex(void) /* lexical analyzer for reparse */ 770 { 771 int c, n; 772 int cflag; 773 static uschar *buf = 0; 774 static int bufsz = 100; 775 uschar *bp; 776 struct charclass *cc; 777 int i; 778 779 switch (c = *prestr++) { 780 case '|': return OR; 781 case '*': return STAR; 782 case '+': return PLUS; 783 case '?': return QUEST; 784 case '.': return DOT; 785 case '\0': prestr--; return '\0'; 786 case '^': 787 case '$': 788 case '(': 789 case ')': 790 return c; 791 case '\\': 792 rlxval = quoted(&prestr); 793 return CHAR; 794 default: 795 rlxval = c; 796 return CHAR; 797 case '[': 798 if (buf == 0 && (buf = (uschar *) malloc(bufsz)) == NULL) 799 FATAL("out of space in reg expr %.10s..", lastre); 800 bp = buf; 801 if (*prestr == '^') { 802 cflag = 1; 803 prestr++; 804 } 805 else 806 cflag = 0; 807 n = 2 * strlen((const char *) prestr)+1; 808 if (!adjbuf((char **) &buf, &bufsz, n, n, (char **) &bp, "relex1")) 809 FATAL("out of space for reg expr %.10s...", lastre); 810 for (; ; ) { 811 if ((c = *prestr++) == '\\') { 812 *bp++ = '\\'; 813 if ((c = *prestr++) == '\0') 814 FATAL("nonterminated character class %.20s...", lastre); 815 *bp++ = c; 816 /* } else if (c == '\n') { */ 817 /* FATAL("newline in character class %.20s...", lastre); */ 818 } else if (c == '[' && *prestr == ':') { 819 /* POSIX char class names, Dag-Erling Smorgrav, des@ofug.org */ 820 for (cc = charclasses; cc->cc_name; cc++) 821 if (strncmp((const char *) prestr + 1, (const char *) cc->cc_name, cc->cc_namelen) == 0) 822 break; 823 if (cc->cc_name != NULL && prestr[1 + cc->cc_namelen] == ':' && 824 prestr[2 + cc->cc_namelen] == ']') { 825 prestr += cc->cc_namelen + 3; 826 for (i = 0; i < NCHARS; i++) { 827 if (!adjbuf((char **) &buf, &bufsz, bp-buf+1, 100, (char **) &bp, "relex2")) 828 FATAL("out of space for reg expr %.10s...", lastre); 829 if (cc->cc_func(i)) { 830 *bp++ = i; 831 n++; 832 } 833 } 834 } else 835 *bp++ = c; 836 } else if (c == '\0') { 837 FATAL("nonterminated character class %.20s", lastre); 838 } else if (bp == buf) { /* 1st char is special */ 839 *bp++ = c; 840 } else if (c == ']') { 841 *bp++ = 0; 842 rlxstr = (uschar *) tostring((char *) buf); 843 if (cflag == 0) 844 return CCL; 845 else 846 return NCCL; 847 } else 848 *bp++ = c; 849 } 850 } 851 } 852 853 int cgoto(fa *f, int s, int c) 854 { 855 int i, j, k; 856 int *p, *q; 857 858 assert(c == HAT || c < NCHARS); 859 while (f->accept >= maxsetvec) { /* guessing here! */ 860 maxsetvec *= 4; 861 setvec = (int *) realloc(setvec, maxsetvec * sizeof(int)); 862 tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int)); 863 if (setvec == 0 || tmpset == 0) 864 overflo("out of space in cgoto()"); 865 } 866 for (i = 0; i <= f->accept; i++) 867 setvec[i] = 0; 868 setcnt = 0; 869 /* compute positions of gototab[s,c] into setvec */ 870 p = f->posns[s]; 871 for (i = 1; i <= *p; i++) { 872 if ((k = f->re[p[i]].ltype) != FINAL) { 873 if ((k == CHAR && c == ptoi(f->re[p[i]].lval.np)) 874 || (k == DOT && c != 0 && c != HAT) 875 || (k == ALL && c != 0) 876 || (k == EMPTYRE && c != 0) 877 || (k == CCL && member(c, (char *) f->re[p[i]].lval.up)) 878 || (k == NCCL && !member(c, (char *) f->re[p[i]].lval.up) && c != 0 && c != HAT)) { 879 q = f->re[p[i]].lfollow; 880 for (j = 1; j <= *q; j++) { 881 if (q[j] >= maxsetvec) { 882 maxsetvec *= 4; 883 setvec = (int *) realloc(setvec, maxsetvec * sizeof(int)); 884 tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int)); 885 if (setvec == 0 || tmpset == 0) 886 overflo("cgoto overflow"); 887 } 888 if (setvec[q[j]] == 0) { 889 setcnt++; 890 setvec[q[j]] = 1; 891 } 892 } 893 } 894 } 895 } 896 /* determine if setvec is a previous state */ 897 tmpset[0] = setcnt; 898 j = 1; 899 for (i = f->accept; i >= 0; i--) 900 if (setvec[i]) { 901 tmpset[j++] = i; 902 } 903 /* tmpset == previous state? */ 904 for (i = 1; i <= f->curstat; i++) { 905 p = f->posns[i]; 906 if ((k = tmpset[0]) != p[0]) 907 goto different; 908 for (j = 1; j <= k; j++) 909 if (tmpset[j] != p[j]) 910 goto different; 911 /* setvec is state i */ 912 f->gototab[s][c] = i; 913 return i; 914 different:; 915 } 916 917 /* add tmpset to current set of states */ 918 if (f->curstat >= NSTATES-1) { 919 f->curstat = 2; 920 f->reset = 1; 921 for (i = 2; i < NSTATES; i++) 922 xfree(f->posns[i]); 923 } else 924 ++(f->curstat); 925 for (i = 0; i < NCHARS; i++) 926 f->gototab[f->curstat][i] = 0; 927 xfree(f->posns[f->curstat]); 928 if ((p = (int *) calloc(setcnt+1, sizeof(int))) == NULL) 929 overflo("out of space in cgoto"); 930 931 f->posns[f->curstat] = p; 932 f->gototab[s][c] = f->curstat; 933 for (i = 0; i <= setcnt; i++) 934 p[i] = tmpset[i]; 935 if (setvec[f->accept]) 936 f->out[f->curstat] = 1; 937 else 938 f->out[f->curstat] = 0; 939 return f->curstat; 940 } 941 942 943 void freefa(fa *f) /* free a finite automaton */ 944 { 945 int i; 946 947 if (f == NULL) 948 return; 949 for (i = 0; i <= f->curstat; i++) 950 xfree(f->posns[i]); 951 for (i = 0; i <= f->accept; i++) { 952 xfree(f->re[i].lfollow); 953 if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL) 954 xfree((f->re[i].lval.np)); 955 } 956 xfree(f->restr); 957 xfree(f); 958 }