contrib/awk20040207/b.c

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