Return to b.c CVS log

Up to [local] / rpl / rplawk

Quelques patches pour rplawk et ncurses.

    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 <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 ELEAF   case EMPTYRE:       /* empty string in regexp */
   48: #define UNARY   case STAR: case PLUS: case QUEST:
   49: 
   50: /* encoding in tree Nodes:
   51:     leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL, EMPTYRE):
   52:         left is index, right contains value or pointer to value
   53:     unary (STAR, PLUS, QUEST): left is child, right is null
   54:     binary (CAT, OR): left and right are children
   55:     parent contains pointer to parent
   56: */
   57: 
   58: 
   59: int *setvec;
   60: int *tmpset;
   61: int maxsetvec = 0;
   62: 
   63: int rtok;       /* next token in current re */
   64: int rlxval;
   65: static uschar   *rlxstr;
   66: static uschar   *prestr;    /* current position in current re */
   67: static uschar   *lastre;    /* origin of last re */
   68: 
   69: static  int setcnt;
   70: static  int poscnt;
   71: 
   72: char    *patbeg;
   73: int patlen;
   74: 
   75: #define NFA 20  /* cache this many dynamic fa's */
   76: fa  *fatab[NFA];
   77: int nfatab  = 0;    /* entries in fatab */
   78: 
   79: fa *makedfa(const char *s, int anchor)  /* returns dfa for reg expr s */
   80: {
   81:     int i, use, nuse;
   82:     fa *pfa;
   83:     static int now = 1;
   84: 
   85:     if (setvec == 0) {  /* first time through any RE */
   86:         maxsetvec = MAXLIN;
   87:         setvec = (int *) malloc(maxsetvec * sizeof(int));
   88:         tmpset = (int *) malloc(maxsetvec * sizeof(int));
   89:         if (setvec == 0 || tmpset == 0)
   90:             overflo("out of space initializing makedfa");
   91:     }
   92: 
   93:     if (compile_time)   /* a constant for sure */
   94:         return mkdfa(s, anchor);
   95:     for (i = 0; i < nfatab; i++)    /* is it there already? */
   96:         if (fatab[i]->anchor == anchor
   97:           && strcmp((const char *) fatab[i]->restr, s) == 0) {
   98:             fatab[i]->use = now++;
   99:             return fatab[i];
  100:         }
  101:     pfa = mkdfa(s, anchor);
  102:     if (nfatab < NFA) { /* room for another */
  103:         fatab[nfatab] = pfa;
  104:         fatab[nfatab]->use = now++;
  105:         nfatab++;
  106:         return pfa;
  107:     }
  108:     use = fatab[0]->use;    /* replace least-recently used */
  109:     nuse = 0;
  110:     for (i = 1; i < nfatab; i++)
  111:         if (fatab[i]->use < use) {
  112:             use = fatab[i]->use;
  113:             nuse = i;
  114:         }
  115:     freefa(fatab[nuse]);
  116:     fatab[nuse] = pfa;
  117:     pfa->use = now++;
  118:     return pfa;
  119: }
  120: 
  121: fa *mkdfa(const char *s, int anchor)    /* does the real work of making a dfa */
  122:                 /* anchor = 1 for anchored matches, else 0 */
  123: {
  124:     Node *p, *p1;
  125:     fa *f;
  126: 
  127:     p = reparse(s);
  128:     p1 = op2(CAT, op2(STAR, op2(ALL, NIL, NIL), NIL), p);
  129:         /* put ALL STAR in front of reg.  exp. */
  130:     p1 = op2(CAT, p1, op2(FINAL, NIL, NIL));
  131:         /* put FINAL after reg.  exp. */
  132: 
  133:     poscnt = 0;
  134:     penter(p1); /* enter parent pointers and leaf indices */
  135:     if ((f = (fa *) calloc(1, sizeof(fa) + poscnt*sizeof(rrow))) == NULL)
  136:         overflo("out of space for fa");
  137:     f->accept = poscnt-1;   /* penter has computed number of positions in re */
  138:     cfoll(f, p1);   /* set up follow sets */
  139:     freetr(p1);
  140:     if ((f->posns[0] = (int *) calloc(1, *(f->re[0].lfollow)*sizeof(int))) == NULL)
  141:             overflo("out of space in makedfa");
  142:     if ((f->posns[1] = (int *) calloc(1, sizeof(int))) == NULL)
  143:         overflo("out of space in makedfa");
  144:     *f->posns[1] = 0;
  145:     f->initstat = makeinit(f, anchor);
  146:     f->anchor = anchor;
  147:     f->restr = (uschar *) tostring(s);
  148:     return f;
  149: }
  150: 
  151: int makeinit(fa *f, int anchor)
  152: {
  153:     int i, k;
  154: 
  155:     f->curstat = 2;
  156:     f->out[2] = 0;
  157:     f->reset = 0;
  158:     k = *(f->re[0].lfollow);
  159:     xfree(f->posns[2]);         
  160:     if ((f->posns[2] = (int *) calloc(1, (k+1)*sizeof(int))) == NULL)
  161:         overflo("out of space in makeinit");
  162:     for (i=0; i <= k; i++) {
  163:         (f->posns[2])[i] = (f->re[0].lfollow)[i];
  164:     }
  165:     if ((f->posns[2])[1] == f->accept)
  166:         f->out[2] = 1;
  167:     for (i=0; i < NCHARS; i++)
  168:         f->gototab[2][i] = 0;
  169:     f->curstat = cgoto(f, 2, HAT);
  170:     if (anchor) {
  171:         *f->posns[2] = k-1; /* leave out position 0 */
  172:         for (i=0; i < k; i++) {
  173:             (f->posns[0])[i] = (f->posns[2])[i];
  174:         }
  175: 
  176:         f->out[0] = f->out[2];
  177:         if (f->curstat != 2)
  178:             --(*f->posns[f->curstat]);
  179:     }
  180:     return f->curstat;
  181: }
  182: 
  183: void penter(Node *p)    /* set up parent pointers and leaf indices */
  184: {
  185:     switch (type(p)) {
  186:     ELEAF
  187:     LEAF
  188:         info(p) = poscnt;
  189:         poscnt++;
  190:         break;
  191:     UNARY
  192:         penter(left(p));
  193:         parent(left(p)) = p;
  194:         break;
  195:     case CAT:
  196:     case OR:
  197:         penter(left(p));
  198:         penter(right(p));
  199:         parent(left(p)) = p;
  200:         parent(right(p)) = p;
  201:         break;
  202:     default:    /* can't happen */
  203:         FATAL("can't happen: unknown type %d in penter", type(p));
  204:         break;
  205:     }
  206: }
  207: 
  208: void freetr(Node *p)    /* free parse tree */
  209: {
  210:     switch (type(p)) {
  211:     ELEAF
  212:     LEAF
  213:         xfree(p);
  214:         break;
  215:     UNARY
  216:         freetr(left(p));
  217:         xfree(p);
  218:         break;
  219:     case CAT:
  220:     case OR:
  221:         freetr(left(p));
  222:         freetr(right(p));
  223:         xfree(p);
  224:         break;
  225:     default:    /* can't happen */
  226:         FATAL("can't happen: unknown type %d in freetr", type(p));
  227:         break;
  228:     }
  229: }
  230: 
  231: /* in the parsing of regular expressions, metacharacters like . have */
  232: /* to be seen literally;  \056 is not a metacharacter. */
  233: 
  234: int hexstr(uschar **pp) /* find and eval hex string at pp, return new p */
  235: {           /* only pick up one 8-bit byte (2 chars) */
  236:     uschar *p;
  237:     int n = 0;
  238:     int i;
  239: 
  240:     for (i = 0, p = (uschar *) *pp; i < 2 && isxdigit(*p); i++, p++) {
  241:         if (isdigit(*p))
  242:             n = 16 * n + *p - '0';
  243:         else if (*p >= 'a' && *p <= 'f')
  244:             n = 16 * n + *p - 'a' + 10;
  245:         else if (*p >= 'A' && *p <= 'F')
  246:             n = 16 * n + *p - 'A' + 10;
  247:     }
  248:     *pp = (uschar *) p;
  249:     return n;
  250: }
  251: 
  252: #define isoctdigit(c) ((c) >= '0' && (c) <= '7')    /* multiple use of arg */
  253: 
  254: int quoted(uschar **pp) /* pick up next thing after a \\ */
  255:             /* and increment *pp */
  256: {
  257:     uschar *p = *pp;
  258:     int c;
  259: 
  260:     if ((c = *p++) == 't')
  261:         c = '\t';
  262:     else if (c == 'n')
  263:         c = '\n';
  264:     else if (c == 'f')
  265:         c = '\f';
  266:     else if (c == 'r')
  267:         c = '\r';
  268:     else if (c == 'b')
  269:         c = '\b';
  270:     else if (c == '\\')
  271:         c = '\\';
  272:     else if (c == 'x') {    /* hexadecimal goo follows */
  273:         c = hexstr(&p); /* this adds a null if number is invalid */
  274:     } else if (isoctdigit(c)) { /* \d \dd \ddd */
  275:         int n = c - '0';
  276:         if (isoctdigit(*p)) {
  277:             n = 8 * n + *p++ - '0';
  278:             if (isoctdigit(*p))
  279:                 n = 8 * n + *p++ - '0';
  280:         }
  281:         c = n;
  282:     } /* else */
  283:         /* c = c; */
  284:     *pp = p;
  285:     return c;
  286: }
  287: 
  288: char *cclenter(const char *argp)    /* add a character class */
  289: {
  290:     int i, c, c2;
  291:     uschar *p = (uschar *) argp;
  292:     uschar *op, *bp;
  293:     static uschar *buf = 0;
  294:     static int bufsz = 100;
  295: 
  296:     op = p;
  297:     if (buf == 0 && (buf = (uschar *) malloc(bufsz)) == NULL)
  298:         FATAL("out of space for character class [%.10s...] 1", p);
  299:     bp = buf;
  300:     for (i = 0; (c = *p++) != 0; ) {
  301:         if (c == '\\') {
  302:             c = quoted(&p);
  303:         } else if (c == '-' && i > 0 && bp[-1] != 0) {
  304:             if (*p != 0) {
  305:                 c = bp[-1];
  306:                 c2 = *p++;
  307:                 if (c2 == '\\')
  308:                     c2 = quoted(&p);
  309:                 if (c > c2) {   /* empty; ignore */
  310:                     bp--;
  311:                     i--;
  312:                     continue;
  313:                 }
  314:                 while (c < c2) {
  315:                     if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, "cclenter1"))
  316:                         FATAL("out of space for character class [%.10s...] 2", p);
  317:                     *bp++ = ++c;
  318:                     i++;
  319:                 }
  320:                 continue;
  321:             }
  322:         }
  323:         if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, "cclenter2"))
  324:             FATAL("out of space for character class [%.10s...] 3", p);
  325:         *bp++ = c;
  326:         i++;
  327:     }
  328:     *bp = 0;
  329:     dprintf( ("cclenter: in = |%s|, out = |%s|\n", op, buf) );
  330:     xfree(op);
  331:     return (char *) tostring((char *) buf);
  332: }
  333: 
  334: void overflo(const char *s)
  335: {
  336:     FATAL("regular expression too big: %.30s...", s);
  337: }
  338: 
  339: void cfoll(fa *f, Node *v)  /* enter follow set of each leaf of vertex v into lfollow[leaf] */
  340: {
  341:     int i;
  342:     int *p;
  343: 
  344:     switch (type(v)) {
  345:     ELEAF
  346:     LEAF
  347:         f->re[info(v)].ltype = type(v);
  348:         f->re[info(v)].lval.np = right(v);
  349:         while (f->accept >= maxsetvec) {    /* guessing here! */
  350:             maxsetvec *= 4;
  351:             setvec = (int *) realloc(setvec, maxsetvec * sizeof(int));
  352:             tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int));
  353:             if (setvec == 0 || tmpset == 0)
  354:                 overflo("out of space in cfoll()");
  355:         }
  356:         for (i = 0; i <= f->accept; i++)
  357:             setvec[i] = 0;
  358:         setcnt = 0;
  359:         follow(v);  /* computes setvec and setcnt */
  360:         if ((p = (int *) calloc(1, (setcnt+1)*sizeof(int))) == NULL)
  361:             overflo("out of space building follow set");
  362:         f->re[info(v)].lfollow = p;
  363:         *p = setcnt;
  364:         for (i = f->accept; i >= 0; i--)
  365:             if (setvec[i] == 1)
  366:                 *++p = i;
  367:         break;
  368:     UNARY
  369:         cfoll(f,left(v));
  370:         break;
  371:     case CAT:
  372:     case OR:
  373:         cfoll(f,left(v));
  374:         cfoll(f,right(v));
  375:         break;
  376:     default:    /* can't happen */
  377:         FATAL("can't happen: unknown type %d in cfoll", type(v));
  378:     }
  379: }
  380: 
  381: int first(Node *p)  /* collects initially active leaves of p into setvec */
  382:             /* returns 0 if p matches empty string */
  383: {
  384:     int b, lp;
  385: 
  386:     switch (type(p)) {
  387:     ELEAF
  388:     LEAF
  389:         lp = info(p);   /* look for high-water mark of subscripts */
  390:         while (setcnt >= maxsetvec || lp >= maxsetvec) {    /* guessing here! */
  391:             maxsetvec *= 4;
  392:             setvec = (int *) realloc(setvec, maxsetvec * sizeof(int));
  393:             tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int));
  394:             if (setvec == 0 || tmpset == 0)
  395:                 overflo("out of space in first()");
  396:         }
  397:         if (type(p) == EMPTYRE) {
  398:             setvec[lp] = 0;
  399:             return(0);
  400:         }
  401:         if (setvec[lp] != 1) {
  402:             setvec[lp] = 1;
  403:             setcnt++;
  404:         }
  405:         if (type(p) == CCL && (*(char *) right(p)) == '\0')
  406:             return(0);      /* empty CCL */
  407:         else return(1);
  408:     case PLUS:
  409:         if (first(left(p)) == 0) return(0);
  410:         return(1);
  411:     case STAR:
  412:     case QUEST:
  413:         first(left(p));
  414:         return(0);
  415:     case CAT:
  416:         if (first(left(p)) == 0 && first(right(p)) == 0) return(0);
  417:         return(1);
  418:     case OR:
  419:         b = first(right(p));
  420:         if (first(left(p)) == 0 || b == 0) return(0);
  421:         return(1);
  422:     }
  423:     FATAL("can't happen: unknown type %d in first", type(p));   /* can't happen */
  424:     return(-1);
  425: }
  426: 
  427: void follow(Node *v)    /* collects leaves that can follow v into setvec */
  428: {
  429:     Node *p;
  430: 
  431:     if (type(v) == FINAL)
  432:         return;
  433:     p = parent(v);
  434:     switch (type(p)) {
  435:     case STAR:
  436:     case PLUS:
  437:         first(v);
  438:         follow(p);
  439:         return;
  440: 
  441:     case OR:
  442:     case QUEST:
  443:         follow(p);
  444:         return;
  445: 
  446:     case CAT:
  447:         if (v == left(p)) { /* v is left child of p */
  448:             if (first(right(p)) == 0) {
  449:                 follow(p);
  450:                 return;
  451:             }
  452:         } else      /* v is right child */
  453:             follow(p);
  454:         return;
  455:     }
  456: }
  457: 
  458: int member(int c, const char *sarg) /* is c in s? */
  459: {
  460:     uschar *s = (uschar *) sarg;
  461: 
  462:     while (*s)
  463:         if (c == *s++)
  464:             return(1);
  465:     return(0);
  466: }
  467: 
  468: int match(fa *f, const char *p0)    /* shortest match ? */
  469: {
  470:     int s, ns;
  471:     uschar *p = (uschar *) p0;
  472: 
  473:     s = f->reset ? makeinit(f,0) : f->initstat;
  474:     if (f->out[s])
  475:         return(1);
  476:     do {
  477:         /* assert(*p < NCHARS); */
  478:         if ((ns = f->gototab[s][*p]) != 0)
  479:             s = ns;
  480:         else
  481:             s = cgoto(f, s, *p);
  482:         if (f->out[s])
  483:             return(1);
  484:     } while (*p++ != 0);
  485:     return(0);
  486: }
  487: 
  488: int pmatch(fa *f, const char *p0)   /* longest match, for sub */
  489: {
  490:     int s, ns;
  491:     uschar *p = (uschar *) p0;
  492:     uschar *q;
  493:     int i, k;
  494: 
  495:     /* s = f->reset ? makeinit(f,1) : f->initstat; */
  496:     if (f->reset) {
  497:         f->initstat = s = makeinit(f,1);
  498:     } else {
  499:         s = f->initstat;
  500:     }
  501:     patbeg = (char *) p;
  502:     patlen = -1;
  503:     do {
  504:         q = p;
  505:         do {
  506:             if (f->out[s])      /* final state */
  507:                 patlen = q-p;
  508:             /* assert(*q < NCHARS); */
  509:             if ((ns = f->gototab[s][*q]) != 0)
  510:                 s = ns;
  511:             else
  512:                 s = cgoto(f, s, *q);
  513:             if (s == 1) {   /* no transition */
  514:                 if (patlen >= 0) {
  515:                     patbeg = (char *) p;
  516:                     return(1);
  517:                 }
  518:                 else
  519:                     goto nextin;    /* no match */
  520:             }
  521:         } while (*q++ != 0);
  522:         if (f->out[s])
  523:             patlen = q-p-1; /* don't count $ */
  524:         if (patlen >= 0) {
  525:             patbeg = (char *) p;
  526:             return(1);
  527:         }
  528:     nextin:
  529:         s = 2;
  530:         if (f->reset) {
  531:             for (i = 2; i <= f->curstat; i++)
  532:                 xfree(f->posns[i]);
  533:             k = *f->posns[0];           
  534:             if ((f->posns[2] = (int *) calloc(1, (k+1)*sizeof(int))) == NULL)
  535:                 overflo("out of space in pmatch");
  536:             for (i = 0; i <= k; i++)
  537:                 (f->posns[2])[i] = (f->posns[0])[i];
  538:             f->initstat = f->curstat = 2;
  539:             f->out[2] = f->out[0];
  540:             for (i = 0; i < NCHARS; i++)
  541:                 f->gototab[2][i] = 0;
  542:         }
  543:     } while (*p++ != 0);
  544:     return (0);
  545: }
  546: 
  547: int nematch(fa *f, const char *p0)  /* non-empty match, for sub */
  548: {
  549:     int s, ns;
  550:     uschar *p = (uschar *) p0;
  551:     uschar *q;
  552:     int i, k;
  553: 
  554:     /* s = f->reset ? makeinit(f,1) : f->initstat; */
  555:     if (f->reset) {
  556:         f->initstat = s = makeinit(f,1);
  557:     } else {
  558:         s = f->initstat;
  559:     }
  560:     patlen = -1;
  561:     while (*p) {
  562:         q = p;
  563:         do {
  564:             if (f->out[s])      /* final state */
  565:                 patlen = q-p;
  566:             /* assert(*q < NCHARS); */
  567:             if ((ns = f->gototab[s][*q]) != 0)
  568:                 s = ns;
  569:             else
  570:                 s = cgoto(f, s, *q);
  571:             if (s == 1) {   /* no transition */
  572:                 if (patlen > 0) {
  573:                     patbeg = (char *) p;
  574:                     return(1);
  575:                 } else
  576:                     goto nnextin;   /* no nonempty match */
  577:             }
  578:         } while (*q++ != 0);
  579:         if (f->out[s])
  580:             patlen = q-p-1; /* don't count $ */
  581:         if (patlen > 0 ) {
  582:             patbeg = (char *) p;
  583:             return(1);
  584:         }
  585:     nnextin:
  586:         s = 2;
  587:         if (f->reset) {
  588:             for (i = 2; i <= f->curstat; i++)
  589:                 xfree(f->posns[i]);
  590:             k = *f->posns[0];           
  591:             if ((f->posns[2] = (int *) calloc(1, (k+1)*sizeof(int))) == NULL)
  592:                 overflo("out of state space");
  593:             for (i = 0; i <= k; i++)
  594:                 (f->posns[2])[i] = (f->posns[0])[i];
  595:             f->initstat = f->curstat = 2;
  596:             f->out[2] = f->out[0];
  597:             for (i = 0; i < NCHARS; i++)
  598:                 f->gototab[2][i] = 0;
  599:         }
  600:         p++;
  601:     }
  602:     return (0);
  603: }
  604: 
  605: Node *reparse(const char *p)    /* parses regular expression pointed to by p */
  606: {           /* uses relex() to scan regular expression */
  607:     Node *np;
  608: 
  609:     dprintf( ("reparse <%s>\n", p) );
  610:     lastre = prestr = (uschar *) p; /* prestr points to string to be parsed */
  611:     rtok = relex();
  612:     /* GNU compatibility: an empty regexp matches anything */
  613:     if (rtok == '\0') {
  614:         /* FATAL("empty regular expression"); previous */
  615:         return(op2(EMPTYRE, NIL, NIL));
  616:     }
  617:     np = regexp();
  618:     if (rtok != '\0')
  619:         FATAL("syntax error in regular expression %s at %s", lastre, prestr);
  620:     return(np);
  621: }
  622: 
  623: Node *regexp(void)  /* top-level parse of reg expr */
  624: {
  625:     return (alt(concat(primary())));
  626: }
  627: 
  628: Node *primary(void)
  629: {
  630:     Node *np;
  631: 
  632:     switch (rtok) {
  633:     case CHAR:
  634:         np = op2(CHAR, NIL, itonp(rlxval));
  635:         rtok = relex();
  636:         return (unary(np));
  637:     case ALL:
  638:         rtok = relex();
  639:         return (unary(op2(ALL, NIL, NIL)));
  640:     case EMPTYRE:
  641:         rtok = relex();
  642:         return (unary(op2(ALL, NIL, NIL)));
  643:     case DOT:
  644:         rtok = relex();
  645:         return (unary(op2(DOT, NIL, NIL)));
  646:     case CCL:
  647:         np = op2(CCL, NIL, (Node*) cclenter((char *) rlxstr));
  648:         rtok = relex();
  649:         return (unary(np));
  650:     case NCCL:
  651:         np = op2(NCCL, NIL, (Node *) cclenter((char *) rlxstr));
  652:         rtok = relex();
  653:         return (unary(np));
  654:     case '^':
  655:         rtok = relex();
  656:         return (unary(op2(CHAR, NIL, itonp(HAT))));
  657:     case '$':
  658:         rtok = relex();
  659:         return (unary(op2(CHAR, NIL, NIL)));
  660:     case '(':
  661:         rtok = relex();
  662:         if (rtok == ')') {  /* special pleading for () */
  663:             rtok = relex();
  664:             return unary(op2(CCL, NIL, (Node *) tostring("")));
  665:         }
  666:         np = regexp();
  667:         if (rtok == ')') {
  668:             rtok = relex();
  669:             return (unary(np));
  670:         }
  671:         else
  672:             FATAL("syntax error in regular expression %s at %s", lastre, prestr);
  673:     default:
  674:         FATAL("illegal primary in regular expression %s at %s", lastre, prestr);
  675:     }
  676:     return 0;   /*NOTREACHED*/
  677: }
  678: 
  679: Node *concat(Node *np)
  680: {
  681:     switch (rtok) {
  682:     case CHAR: case DOT: case ALL: case EMPTYRE: case CCL: case NCCL: case '$': case '(':
  683:         return (concat(op2(CAT, np, primary())));
  684:     }
  685:     return (np);
  686: }
  687: 
  688: Node *alt(Node *np)
  689: {
  690:     if (rtok == OR) {
  691:         rtok = relex();
  692:         return (alt(op2(OR, np, concat(primary()))));
  693:     }
  694:     return (np);
  695: }
  696: 
  697: Node *unary(Node *np)
  698: {
  699:     switch (rtok) {
  700:     case STAR:
  701:         rtok = relex();
  702:         return (unary(op2(STAR, np, NIL)));
  703:     case PLUS:
  704:         rtok = relex();
  705:         return (unary(op2(PLUS, np, NIL)));
  706:     case QUEST:
  707:         rtok = relex();
  708:         return (unary(op2(QUEST, np, NIL)));
  709:     default:
  710:         return (np);
  711:     }
  712: }
  713: 
  714: /*
  715:  * Character class definitions conformant to the POSIX locale as
  716:  * defined in IEEE P1003.1 draft 7 of June 2001, assuming the source
  717:  * and operating character sets are both ASCII (ISO646) or supersets
  718:  * thereof.
  719:  *
  720:  * Note that to avoid overflowing the temporary buffer used in
  721:  * relex(), the expanded character class (prior to range expansion)
  722:  * must be less than twice the size of their full name.
  723:  */
  724: 
  725: /* Because isblank doesn't show up in any of the header files on any
  726:  * system i use, it's defined here.  if some other locale has a richer
  727:  * definition of "blank", define HAS_ISBLANK and provide your own
  728:  * version.
  729:  * the parentheses here are an attempt to find a path through the maze
  730:  * of macro definition and/or function and/or version provided.  thanks
  731:  * to nelson beebe for the suggestion; let's see if it works everywhere.
  732:  */
  733: 
  734: /* #define HAS_ISBLANK */
  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(1, (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: }