1 /****************************************************************
2 Copyright (C) Lucent Technologies 1997
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
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
23 ****************************************************************/
25 /* lasciate ogne speranza, voi ch'entrate. */
36 #define HAT (NCHARS-2) /* matches ^ in regular expr */
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
46 #define LEAF case CCL: case NCCL: case CHAR: case DOT: case FINAL: case ALL:
47 #define UNARY case STAR: case PLUS: case QUEST:
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
62 int rtok; /* next token in current re */
64 static uschar *rlxstr;
65 static uschar *prestr; /* current position in current re */
66 static uschar *lastre; /* origin of last re */
74 #define NFA 20 /* cache this many dynamic fa's */
76 int nfatab = 0; /* entries in fatab */
78 fa *makedfa(char *s, int anchor) /* returns dfa for reg expr s */
84 if (setvec == 0) { /* first time through any RE */
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");
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++;
100 pfa = mkdfa(s, anchor);
101 if (nfatab < NFA) { /* room for another */
103 fatab[nfatab]->use = now++;
107 use = fatab[0]->use; /* replace least-recently used */
109 for (i = 1; i < nfatab; i++)
110 if (fatab[i]->use < use) {
120 fa *mkdfa(char *s, int anchor) /* does the real work of making a dfa */
121 /* anchor = 1 for anchored matches, else 0 */
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. */
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 */
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");
144 f->initstat = makeinit(f, anchor);
146 f->restr = (uschar *) tostring(s);
150 int makeinit(fa *f, int anchor)
157 k = *(f->re[0].lfollow);
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];
164 if ((f->posns[2])[1] == f->accept)
166 for (i=0; i < NCHARS; i++)
167 f->gototab[2][i] = 0;
168 f->curstat = cgoto(f, 2, HAT);
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];
175 f->out[0] = f->out[2];
177 --(*f->posns[f->curstat]);
182 void penter(Node *p) /* set up parent pointers and leaf indices */
198 parent(right(p)) = p;
200 default: /* can't happen */
201 FATAL("can't happen: unknown type %d in penter", type(p));
206 void freetr(Node *p) /* free parse tree */
222 default: /* can't happen */
223 FATAL("can't happen: unknown type %d in freetr", type(p));
228 /* in the parsing of regular expressions, metacharacters like . have */
229 /* to be seen literally; \056 is not a metacharacter. */
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) */
237 for (i = 0, p = (uschar *) *pp; i < 2 && isxdigit(*p); i++, 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;
249 #define isoctdigit(c) ((c) >= '0' && (c) <= '7') /* multiple use of arg */
251 int quoted(char **pp) /* pick up next thing after a \\ */
252 /* and increment *pp */
257 if ((c = *p++) == 't')
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 */
273 if (isoctdigit(*p)) {
274 n = 8 * n + *p++ - '0';
276 n = 8 * n + *p++ - '0';
285 char *cclenter(char *argp) /* add a character class */
288 uschar *p = (uschar *) argp;
290 static uschar *buf = 0;
291 static int bufsz = 100;
294 if (buf == 0 && (buf = (uschar *) malloc(bufsz)) == NULL)
295 FATAL("out of space for character class [%.10s...] 1", p);
297 for (i = 0; (c = *p++) != 0; ) {
299 c = quoted((char **) &p);
300 } else if (c == '-' && i > 0 && bp[-1] != 0) {
305 c2 = quoted((char **) &p);
306 if (c > c2) { /* empty; ignore */
312 if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, 0))
313 FATAL("out of space for character class [%.10s...] 2", p);
320 if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, 0))
321 FATAL("out of space for character class [%.10s...] 3", p);
326 dprintf( ("cclenter: in = |%s|, out = |%s|\n", op, buf) );
328 return (char *) tostring((char *) buf);
331 void overflo(char *s)
333 FATAL("regular expression too big: %.30s...", s);
336 void cfoll(fa *f, Node *v) /* enter follow set of each leaf of vertex v into lfollow[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! */
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()");
352 for (i = 0; i <= f->accept; i++)
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;
360 for (i = f->accept; i >= 0; i--)
372 default: /* can't happen */
373 FATAL("can't happen: unknown type %d in cfoll", type(v));
377 int first(Node *p) /* collects initially active leaves of p into setvec */
378 /* returns 1 if p matches empty string */
384 lp = info(p); /* look for high-water mark of subscripts */
385 while (setcnt >= maxsetvec || lp >= maxsetvec) { /* guessing here! */
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()");
392 if (setvec[lp] != 1) {
396 if (type(p) == CCL && (*(char *) right(p)) == '\0')
397 return(0); /* empty CCL */
400 if (first(left(p)) == 0) return(0);
407 if (first(left(p)) == 0 && first(right(p)) == 0) return(0);
411 if (first(left(p)) == 0 || b == 0) return(0);
414 FATAL("can't happen: unknown type %d in first", type(p)); /* can't happen */
418 void follow(Node *v) /* collects leaves that can follow v into setvec */
422 if (type(v) == FINAL)
438 if (v == left(p)) { /* v is left child of p */
439 if (first(right(p)) == 0) {
443 } else /* v is right child */
449 int member(int c, char *sarg) /* is c in s? */
451 uschar *s = (uschar *) sarg;
459 int match(fa *f, char *p0) /* shortest match ? */
462 uschar *p = (uschar *) p0;
464 s = f->reset ? makeinit(f,0) : f->initstat;
468 if ((ns = f->gototab[s][*p]) != 0)
478 int pmatch(fa *f, char *p0) /* longest match, for sub */
481 uschar *p = (uschar *) p0;
485 s = f->reset ? makeinit(f,1) : f->initstat;
491 if (f->out[s]) /* final state */
493 if ((ns = f->gototab[s][*q]) != 0)
497 if (s == 1) { /* no transition */
503 goto nextin; /* no match */
507 patlen = q-p-1; /* don't count $ */
515 for (i = 2; i <= f->curstat; i++)
518 if ((f->posns[2] = (int *) calloc(1, (k+1)*sizeof(int))) == NULL)
519 overflo("out of space in pmatch");
520 for (i = 0; i <= k; i++)
521 (f->posns[2])[i] = (f->posns[0])[i];
522 f->initstat = f->curstat = 2;
523 f->out[2] = f->out[0];
524 for (i = 0; i < NCHARS; i++)
525 f->gototab[2][i] = 0;
531 int nematch(fa *f, char *p0) /* non-empty match, for sub */
534 uschar *p = (uschar *) p0;
538 s = f->reset ? makeinit(f,1) : f->initstat;
543 if (f->out[s]) /* final state */
545 if ((ns = f->gototab[s][*q]) != 0)
549 if (s == 1) { /* no transition */
554 goto nnextin; /* no nonempty match */
558 patlen = q-p-1; /* don't count $ */
566 for (i = 2; i <= f->curstat; i++)
569 if ((f->posns[2] = (int *) calloc(1, (k+1)*sizeof(int))) == NULL)
570 overflo("out of state space");
571 for (i = 0; i <= k; i++)
572 (f->posns[2])[i] = (f->posns[0])[i];
573 f->initstat = f->curstat = 2;
574 f->out[2] = f->out[0];
575 for (i = 0; i < NCHARS; i++)
576 f->gototab[2][i] = 0;
583 Node *reparse(char *p) /* parses regular expression pointed to by p */
584 { /* uses relex() to scan regular expression */
587 dprintf( ("reparse <%s>\n", p) );
588 lastre = prestr = (uschar *) p; /* prestr points to string to be parsed */
591 FATAL("empty regular expression");
594 FATAL("syntax error in regular expression %s at %s", lastre, prestr);
598 Node *regexp(void) /* top-level parse of reg expr */
600 return (alt(concat(primary())));
609 np = op2(CHAR, NIL, itonp(rlxval));
614 return (unary(op2(ALL, NIL, NIL)));
617 return (unary(op2(DOT, NIL, NIL)));
619 np = op2(CCL, NIL, (Node*) cclenter((char *) rlxstr));
623 np = op2(NCCL, NIL, (Node *) cclenter((char *) rlxstr));
628 return (unary(op2(CHAR, NIL, itonp(HAT))));
631 return (unary(op2(CHAR, NIL, NIL)));
634 if (rtok == ')') { /* special pleading for () */
636 return unary(op2(CCL, NIL, (Node *) tostring("")));
644 FATAL("syntax error in regular expression %s at %s", lastre, prestr);
646 FATAL("illegal primary in regular expression %s at %s", lastre, prestr);
648 return 0; /*NOTREACHED*/
651 Node *concat(Node *np)
654 case CHAR: case DOT: case ALL: case CCL: case NCCL: case '$': case '(':
655 return (concat(op2(CAT, np, primary())));
664 return (alt(op2(OR, np, concat(primary()))));
669 Node *unary(Node *np)
674 return (unary(op2(STAR, np, NIL)));
677 return (unary(op2(PLUS, np, NIL)));
680 return (unary(op2(QUEST, np, NIL)));
687 * Character class definitions conformant to the POSIX locale as
688 * defined in IEEE P1003.1 draft 7 of June 2001, assuming the source
689 * and operating character sets are both ASCII (ISO646) or supersets
692 * Note that to avoid overflowing the temporary buffer used in
693 * relex(), the expanded character class (prior to range expansion)
694 * must be less than twice the size of their full name.
699 const char *cc_expand;
701 { "alnum", 5, "0-9A-Za-z" },
702 { "alpha", 5, "A-Za-z" },
703 { "blank", 5, " \t" },
704 { "cntrl", 5, "\000-\037\177" },
705 { "digit", 5, "0-9" },
706 { "graph", 5, "\041-\176" },
707 { "lower", 5, "a-z" },
708 { "print", 5, " \041-\176" },
709 { "punct", 5, "\041-\057\072-\100\133-\140\173-\176" },
710 { "space", 5, " \f\n\r\t\v" },
711 { "upper", 5, "A-Z" },
712 { "xdigit", 6, "0-9A-Fa-f" },
717 int relex(void) /* lexical analyzer for reparse */
721 static uschar *buf = 0;
722 static int bufsz = 100;
724 struct charclass *cc;
727 switch (c = *prestr++) {
729 case '*': return STAR;
730 case '+': return PLUS;
731 case '?': return QUEST;
732 case '.': return DOT;
733 case '\0': prestr--; return '\0';
740 rlxval = quoted((char **) &prestr);
746 if (buf == 0 && (buf = (uschar *) malloc(bufsz)) == NULL)
747 FATAL("out of space in reg expr %.10s..", lastre);
749 if (*prestr == '^') {
755 n = 2 * strlen((const char *) prestr)+1;
756 if (!adjbuf((char **) &buf, &bufsz, n, n, (char **) &bp, 0))
757 FATAL("out of space for reg expr %.10s...", lastre);
759 if ((c = *prestr++) == '\\') {
761 if ((c = *prestr++) == '\0')
762 FATAL("nonterminated character class %.20s...", lastre);
764 /* } else if (c == '\n') { */
765 /* FATAL("newline in character class %.20s...", lastre); */
766 } else if (c == '[' && *prestr == ':') {
767 /* POSIX char class names, Dag-Erling Smorgrav, des@ofug.org */
768 for (cc = charclasses; cc->cc_name; cc++)
769 if (strncmp((const char *) prestr + 1, (const char *) cc->cc_name, cc->cc_namelen) == 0)
771 if (cc->cc_name != NULL && prestr[1 + cc->cc_namelen] == ':' &&
772 prestr[2 + cc->cc_namelen] == ']') {
773 prestr += cc->cc_namelen + 3;
774 for (p = (const uschar *) cc->cc_expand; *p; p++)
778 } else if (c == '\0') {
779 FATAL("nonterminated character class %.20s", lastre);
780 } else if (bp == buf) { /* 1st char is special */
782 } else if (c == ']') {
784 rlxstr = (uschar *) tostring((char *) buf);
795 int cgoto(fa *f, int s, int c)
800 if (c < 0 || c > 255)
801 FATAL("can't happen: neg char %d in cgoto", c);
802 while (f->accept >= maxsetvec) { /* guessing here! */
804 setvec = (int *) realloc(setvec, maxsetvec * sizeof(int));
805 tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(int));
806 if (setvec == 0 || tmpset == 0)
807 overflo("out of space in cgoto()");
809 for (i = 0; i <= f->accept; i++)
812 /* compute positions of gototab[s,c] into setvec */
814 for (i = 1; i <= *p; i++) {
815 if ((k = f->re[p[i]].ltype) != FINAL) {
816 if ((k == CHAR && c == ptoi(f->re[p[i]].lval.np))
817 || (k == DOT && c != 0 && c != HAT)
818 || (k == ALL && c != 0)
819 || (k == CCL && member(c, (char *) f->re[p[i]].lval.up))
820 || (k == NCCL && !member(c, (char *) f->re[p[i]].lval.up) && c != 0 && c != HAT)) {
821 q = f->re[p[i]].lfollow;
822 for (j = 1; j <= *q; j++) {
823 if (q[j] >= maxsetvec) {
825 setvec = (int *) realloc(setvec, maxsetvec * sizeof(int));
826 tmpset = (int *) realloc(setvec, maxsetvec * sizeof(int));
827 if (setvec == 0 || tmpset == 0)
828 overflo("cgoto overflow");
830 if (setvec[q[j]] == 0) {
838 /* determine if setvec is a previous state */
841 for (i = f->accept; i >= 0; i--)
845 /* tmpset == previous state? */
846 for (i = 1; i <= f->curstat; i++) {
848 if ((k = tmpset[0]) != p[0])
850 for (j = 1; j <= k; j++)
851 if (tmpset[j] != p[j])
853 /* setvec is state i */
854 f->gototab[s][c] = i;
859 /* add tmpset to current set of states */
860 if (f->curstat >= NSTATES-1) {
863 for (i = 2; i < NSTATES; i++)
867 for (i = 0; i < NCHARS; i++)
868 f->gototab[f->curstat][i] = 0;
869 xfree(f->posns[f->curstat]);
870 if ((p = (int *) calloc(1, (setcnt+1)*sizeof(int))) == NULL)
871 overflo("out of space in cgoto");
873 f->posns[f->curstat] = p;
874 f->gototab[s][c] = f->curstat;
875 for (i = 0; i <= setcnt; i++)
877 if (setvec[f->accept])
878 f->out[f->curstat] = 1;
880 f->out[f->curstat] = 0;
885 void freefa(fa *f) /* free a finite automaton */
891 for (i = 0; i <= f->curstat; i++)
893 for (i = 0; i <= f->accept; i++) {
894 xfree(f->re[i].lfollow);
895 if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL)
896 xfree((f->re[i].lval.np));