Merge from vendor branch AWK:
[dragonfly.git] / contrib / awk20050424 / 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                 assert(*p < NCHARS);
469                 if ((ns = f->gototab[s][*p]) != 0)
470                         s = ns;
471                 else
472                         s = cgoto(f, s, *p);
473                 if (f->out[s])
474                         return(1);
475         } while (*p++ != 0);
476         return(0);
477 }
478
479 int pmatch(fa *f, const char *p0)       /* longest match, for sub */
480 {
481         int s, ns;
482         uschar *p = (uschar *) p0;
483         uschar *q;
484         int i, k;
485
486         /* s = f->reset ? makeinit(f,1) : f->initstat; */
487         if (f->reset) {
488                 f->initstat = s = makeinit(f,1);
489         } else {
490                 s = f->initstat;
491         }
492         patbeg = (char *) p;
493         patlen = -1;
494         do {
495                 q = p;
496                 do {
497                         if (f->out[s])          /* final state */
498                                 patlen = q-p;
499                         assert(*q < NCHARS);
500                         if ((ns = f->gototab[s][*q]) != 0)
501                                 s = ns;
502                         else
503                                 s = cgoto(f, s, *q);
504                         if (s == 1) {   /* no transition */
505                                 if (patlen >= 0) {
506                                         patbeg = (char *) p;
507                                         return(1);
508                                 }
509                                 else
510                                         goto nextin;    /* no match */
511                         }
512                 } while (*q++ != 0);
513                 if (f->out[s])
514                         patlen = q-p-1; /* don't count $ */
515                 if (patlen >= 0) {
516                         patbeg = (char *) p;
517                         return(1);
518                 }
519         nextin:
520                 s = 2;
521                 if (f->reset) {
522                         for (i = 2; i <= f->curstat; i++)
523                                 xfree(f->posns[i]);
524                         k = *f->posns[0];                       
525                         if ((f->posns[2] = (int *) calloc(1, (k+1)*sizeof(int))) == NULL)
526                                 overflo("out of space in pmatch");
527                         for (i = 0; i <= k; i++)
528                                 (f->posns[2])[i] = (f->posns[0])[i];
529                         f->initstat = f->curstat = 2;
530                         f->out[2] = f->out[0];
531                         for (i = 0; i < NCHARS; i++)
532                                 f->gototab[2][i] = 0;
533                 }
534         } while (*p++ != 0);
535         return (0);
536 }
537
538 int nematch(fa *f, const char *p0)      /* non-empty match, for sub */
539 {
540         int s, ns;
541         uschar *p = (uschar *) p0;
542         uschar *q;
543         int i, k;
544
545         /* s = f->reset ? makeinit(f,1) : f->initstat; */
546         if (f->reset) {
547                 f->initstat = s = makeinit(f,1);
548         } else {
549                 s = f->initstat;
550         }
551         patlen = -1;
552         while (*p) {
553                 q = p;
554                 do {
555                         if (f->out[s])          /* final state */
556                                 patlen = q-p;
557                         assert(*q < NCHARS);
558                         if ((ns = f->gototab[s][*q]) != 0)
559                                 s = ns;
560                         else
561                                 s = cgoto(f, s, *q);
562                         if (s == 1) {   /* no transition */
563                                 if (patlen > 0) {
564                                         patbeg = (char *) p;
565                                         return(1);
566                                 } else
567                                         goto nnextin;   /* no nonempty match */
568                         }
569                 } while (*q++ != 0);
570                 if (f->out[s])
571                         patlen = q-p-1; /* don't count $ */
572                 if (patlen > 0 ) {
573                         patbeg = (char *) p;
574                         return(1);
575                 }
576         nnextin:
577                 s = 2;
578                 if (f->reset) {
579                         for (i = 2; i <= f->curstat; i++)
580                                 xfree(f->posns[i]);
581                         k = *f->posns[0];                       
582                         if ((f->posns[2] = (int *) calloc(1, (k+1)*sizeof(int))) == NULL)
583                                 overflo("out of state space");
584                         for (i = 0; i <= k; i++)
585                                 (f->posns[2])[i] = (f->posns[0])[i];
586                         f->initstat = f->curstat = 2;
587                         f->out[2] = f->out[0];
588                         for (i = 0; i < NCHARS; i++)
589                                 f->gototab[2][i] = 0;
590                 }
591                 p++;
592         }
593         return (0);
594 }
595
596 Node *reparse(const char *p)    /* parses regular expression pointed to by p */
597 {                       /* uses relex() to scan regular expression */
598         Node *np;
599
600         dprintf( ("reparse <%s>\n", p) );
601         lastre = prestr = (uschar *) p; /* prestr points to string to be parsed */
602         rtok = relex();
603         /* GNU compatibility: an empty regexp matches anything */
604         if (rtok == '\0')
605                 /* FATAL("empty regular expression"); previous */
606                 return(op2(ALL, NIL, NIL));
607         np = regexp();
608         if (rtok != '\0')
609                 FATAL("syntax error in regular expression %s at %s", lastre, prestr);
610         return(np);
611 }
612
613 Node *regexp(void)      /* top-level parse of reg expr */
614 {
615         return (alt(concat(primary())));
616 }
617
618 Node *primary(void)
619 {
620         Node *np;
621
622         switch (rtok) {
623         case CHAR:
624                 np = op2(CHAR, NIL, itonp(rlxval));
625                 rtok = relex();
626                 return (unary(np));
627         case ALL:
628                 rtok = relex();
629                 return (unary(op2(ALL, NIL, NIL)));
630         case DOT:
631                 rtok = relex();
632                 return (unary(op2(DOT, NIL, NIL)));
633         case CCL:
634                 np = op2(CCL, NIL, (Node*) cclenter((char *) rlxstr));
635                 rtok = relex();
636                 return (unary(np));
637         case NCCL:
638                 np = op2(NCCL, NIL, (Node *) cclenter((char *) rlxstr));
639                 rtok = relex();
640                 return (unary(np));
641         case '^':
642                 rtok = relex();
643                 return (unary(op2(CHAR, NIL, itonp(HAT))));
644         case '$':
645                 rtok = relex();
646                 return (unary(op2(CHAR, NIL, NIL)));
647         case '(':
648                 rtok = relex();
649                 if (rtok == ')') {      /* special pleading for () */
650                         rtok = relex();
651                         return unary(op2(CCL, NIL, (Node *) tostring("")));
652                 }
653                 np = regexp();
654                 if (rtok == ')') {
655                         rtok = relex();
656                         return (unary(np));
657                 }
658                 else
659                         FATAL("syntax error in regular expression %s at %s", lastre, prestr);
660         default:
661                 FATAL("illegal primary in regular expression %s at %s", lastre, prestr);
662         }
663         return 0;       /*NOTREACHED*/
664 }
665
666 Node *concat(Node *np)
667 {
668         switch (rtok) {
669         case CHAR: case DOT: case ALL: case CCL: case NCCL: case '$': case '(':
670                 return (concat(op2(CAT, np, primary())));
671         }
672         return (np);
673 }
674
675 Node *alt(Node *np)
676 {
677         if (rtok == OR) {
678                 rtok = relex();
679                 return (alt(op2(OR, np, concat(primary()))));
680         }
681         return (np);
682 }
683
684 Node *unary(Node *np)
685 {
686         switch (rtok) {
687         case STAR:
688                 rtok = relex();
689                 return (unary(op2(STAR, np, NIL)));
690         case PLUS:
691                 rtok = relex();
692                 return (unary(op2(PLUS, np, NIL)));
693         case QUEST:
694                 rtok = relex();
695                 return (unary(op2(QUEST, np, NIL)));
696         default:
697                 return (np);
698         }
699 }
700
701 /*
702  * Character class definitions conformant to the POSIX locale as
703  * defined in IEEE P1003.1 draft 7 of June 2001, assuming the source
704  * and operating character sets are both ASCII (ISO646) or supersets
705  * thereof.
706  *
707  * Note that to avoid overflowing the temporary buffer used in
708  * relex(), the expanded character class (prior to range expansion)
709  * must be less than twice the size of their full name.
710  */
711
712 /* Because isblank doesn't show up in any of the header files on any
713  * system i use, it's defined here.  if some other locale has a richer
714  * definition of "blank", define HAS_ISBLANK and provide your own
715  * version.
716  * the parentheses here are an attempt to find a path through the maze
717  * of macro definition and/or function and/or version provided.  thanks
718  * to nelson beebe for the suggestion; let's see if it works everywhere.
719  */
720
721 #ifndef HAS_ISBLANK
722
723 int (isblank)(int c)
724 {
725         return c==' ' || c=='\t';
726 }
727
728 #endif
729
730 struct charclass {
731         const char *cc_name;
732         int cc_namelen;
733         int (*cc_func)(int);
734 } charclasses[] = {
735         { "alnum",      5,      isalnum },
736         { "alpha",      5,      isalpha },
737         { "blank",      5,      isblank },
738         { "cntrl",      5,      iscntrl },
739         { "digit",      5,      isdigit },
740         { "graph",      5,      isgraph },
741         { "lower",      5,      islower },
742         { "print",      5,      isprint },
743         { "punct",      5,      ispunct },
744         { "space",      5,      isspace },
745         { "upper",      5,      isupper },
746         { "xdigit",     6,      isxdigit },
747         { NULL,         0,      NULL },
748 };
749
750
751 int relex(void)         /* lexical analyzer for reparse */
752 {
753         int c, n;
754         int cflag;
755         static uschar *buf = 0;
756         static int bufsz = 100;
757         uschar *bp;
758         struct charclass *cc;
759         int i;
760
761         switch (c = *prestr++) {
762         case '|': return OR;
763         case '*': return STAR;
764         case '+': return PLUS;
765         case '?': return QUEST;
766         case '.': return DOT;
767         case '\0': prestr--; return '\0';
768         case '^':
769         case '$':
770         case '(':
771         case ')':
772                 return c;
773         case '\\':
774                 rlxval = quoted((char **) &prestr);
775                 return CHAR;
776         default:
777                 rlxval = c;
778                 return CHAR;
779         case '[': 
780                 if (buf == 0 && (buf = (uschar *) malloc(bufsz)) == NULL)
781                         FATAL("out of space in reg expr %.10s..", lastre);
782                 bp = buf;
783                 if (*prestr == '^') {
784                         cflag = 1;
785                         prestr++;
786                 }
787                 else
788                         cflag = 0;
789                 n = 2 * strlen((const char *) prestr)+1;
790                 if (!adjbuf((char **) &buf, &bufsz, n, n, (char **) &bp, 0))
791                         FATAL("out of space for reg expr %.10s...", lastre);
792                 for (; ; ) {
793                         if ((c = *prestr++) == '\\') {
794                                 *bp++ = '\\';
795                                 if ((c = *prestr++) == '\0')
796                                         FATAL("nonterminated character class %.20s...", lastre);
797                                 *bp++ = c;
798                         /* } else if (c == '\n') { */
799                         /*      FATAL("newline in character class %.20s...", lastre); */
800                         } else if (c == '[' && *prestr == ':') {
801                                 /* POSIX char class names, Dag-Erling Smorgrav, des@ofug.org */
802                                 for (cc = charclasses; cc->cc_name; cc++)
803                                         if (strncmp((const char *) prestr + 1, (const char *) cc->cc_name, cc->cc_namelen) == 0)
804                                                 break;
805                                 if (cc->cc_name != NULL && prestr[1 + cc->cc_namelen] == ':' &&
806                                     prestr[2 + cc->cc_namelen] == ']') {
807                                         prestr += cc->cc_namelen + 3;
808                                         for (i = 0; i < NCHARS; i++) {
809                                                 if (!adjbuf((char **) &buf, &bufsz, bp-buf+1, 100, (char **) &bp, 0))
810                                                     FATAL("out of space for reg expr %.10s...", lastre);
811                                                 if (cc->cc_func(i)) {
812                                                         *bp++ = i;
813                                                         n++;
814                                                 }
815                                         }
816                                 } else
817                                         *bp++ = c;
818                         } else if (c == '\0') {
819                                 FATAL("nonterminated character class %.20s", lastre);
820                         } else if (bp == buf) { /* 1st char is special */
821                                 *bp++ = c;
822                         } else if (c == ']') {
823                                 *bp++ = 0;
824                                 rlxstr = (uschar *) tostring((char *) buf);
825                                 if (cflag == 0)
826                                         return CCL;
827                                 else
828                                         return NCCL;
829                         } else
830                                 *bp++ = c;
831                 }
832         }
833 }
834
835 int cgoto(fa *f, int s, int c)
836 {
837         int i, j, k;
838         int *p, *q;
839
840         assert(c == HAT || c < NCHARS);
841         while (f->accept >= maxsetvec) {        /* guessing here! */
842                 maxsetvec *= 4;
843                 setvec = (int *) realloc(setvec, maxsetvec * sizeof(int));
844                 tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int));
845                 if (setvec == 0 || tmpset == 0)
846                         overflo("out of space in cgoto()");
847         }
848         for (i = 0; i <= f->accept; i++)
849                 setvec[i] = 0;
850         setcnt = 0;
851         /* compute positions of gototab[s,c] into setvec */
852         p = f->posns[s];
853         for (i = 1; i <= *p; i++) {
854                 if ((k = f->re[p[i]].ltype) != FINAL) {
855                         if ((k == CHAR && c == ptoi(f->re[p[i]].lval.np))
856                          || (k == DOT && c != 0 && c != HAT)
857                          || (k == ALL && c != 0)
858                          || (k == CCL && member(c, (char *) f->re[p[i]].lval.up))
859                          || (k == NCCL && !member(c, (char *) f->re[p[i]].lval.up) && c != 0 && c != HAT)) {
860                                 q = f->re[p[i]].lfollow;
861                                 for (j = 1; j <= *q; j++) {
862                                         if (q[j] >= maxsetvec) {
863                                                 maxsetvec *= 4;
864                                                 setvec = (int *) realloc(setvec, maxsetvec * sizeof(int));
865                                                 tmpset = (int *) realloc(setvec, maxsetvec * sizeof(int));
866                                                 if (setvec == 0 || tmpset == 0)
867                                                         overflo("cgoto overflow");
868                                         }
869                                         if (setvec[q[j]] == 0) {
870                                                 setcnt++;
871                                                 setvec[q[j]] = 1;
872                                         }
873                                 }
874                         }
875                 }
876         }
877         /* determine if setvec is a previous state */
878         tmpset[0] = setcnt;
879         j = 1;
880         for (i = f->accept; i >= 0; i--)
881                 if (setvec[i]) {
882                         tmpset[j++] = i;
883                 }
884         /* tmpset == previous state? */
885         for (i = 1; i <= f->curstat; i++) {
886                 p = f->posns[i];
887                 if ((k = tmpset[0]) != p[0])
888                         goto different;
889                 for (j = 1; j <= k; j++)
890                         if (tmpset[j] != p[j])
891                                 goto different;
892                 /* setvec is state i */
893                 f->gototab[s][c] = i;
894                 return i;
895           different:;
896         }
897
898         /* add tmpset to current set of states */
899         if (f->curstat >= NSTATES-1) {
900                 f->curstat = 2;
901                 f->reset = 1;
902                 for (i = 2; i < NSTATES; i++)
903                         xfree(f->posns[i]);
904         } else
905                 ++(f->curstat);
906         for (i = 0; i < NCHARS; i++)
907                 f->gototab[f->curstat][i] = 0;
908         xfree(f->posns[f->curstat]);
909         if ((p = (int *) calloc(1, (setcnt+1)*sizeof(int))) == NULL)
910                 overflo("out of space in cgoto");
911
912         f->posns[f->curstat] = p;
913         f->gototab[s][c] = f->curstat;
914         for (i = 0; i <= setcnt; i++)
915                 p[i] = tmpset[i];
916         if (setvec[f->accept])
917                 f->out[f->curstat] = 1;
918         else
919                 f->out[f->curstat] = 0;
920         return f->curstat;
921 }
922
923
924 void freefa(fa *f)      /* free a finite automaton */
925 {
926         int i;
927
928         if (f == NULL)
929                 return;
930         for (i = 0; i <= f->curstat; i++)
931                 xfree(f->posns[i]);
932         for (i = 0; i <= f->accept; i++) {
933                 xfree(f->re[i].lfollow);
934                 if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL)
935                         xfree((f->re[i].lval.np));
936         }
937         xfree(f->restr);
938         xfree(f);
939 }