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(const 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(const 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(const 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(const 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
, const char *sarg
) /* is c in s? */
451 uschar
*s
= (uschar
*) sarg
;
459 int match(fa
*f
, const 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
, const char *p0
) /* longest match, for sub */
481 uschar
*p
= (uschar
*) p0
;
485 /* s = f->reset ? makeinit(f,1) : f->initstat; */
487 f
->initstat
= s
= makeinit(f
,1);
496 if (f
->out
[s
]) /* final state */
498 if ((ns
= f
->gototab
[s
][*q
]) != 0)
502 if (s
== 1) { /* no transition */
508 goto nextin
; /* no match */
512 patlen
= q
-p
-1; /* don't count $ */
520 for (i
= 2; i
<= f
->curstat
; i
++)
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;
536 int nematch(fa
*f
, const char *p0
) /* non-empty match, for sub */
539 uschar
*p
= (uschar
*) p0
;
543 /* s = f->reset ? makeinit(f,1) : f->initstat; */
545 f
->initstat
= s
= makeinit(f
,1);
553 if (f
->out
[s
]) /* final state */
555 if ((ns
= f
->gototab
[s
][*q
]) != 0)
559 if (s
== 1) { /* no transition */
564 goto nnextin
; /* no nonempty match */
568 patlen
= q
-p
-1; /* don't count $ */
576 for (i
= 2; i
<= f
->curstat
; i
++)
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;
593 Node
*reparse(const char *p
) /* parses regular expression pointed to by p */
594 { /* uses relex() to scan regular expression */
597 dprintf( ("reparse <%s>\n", p
) );
598 lastre
= prestr
= (uschar
*) p
; /* prestr points to string to be parsed */
600 /* GNU compatibility: an empty regexp matches anything */
602 /* FATAL("empty regular expression"); previous */
603 return(op2(ALL
, NIL
, NIL
));
606 FATAL("syntax error in regular expression %s at %s", lastre
, prestr
);
610 Node
*regexp(void) /* top-level parse of reg expr */
612 return (alt(concat(primary())));
621 np
= op2(CHAR
, NIL
, itonp(rlxval
));
626 return (unary(op2(ALL
, NIL
, NIL
)));
629 return (unary(op2(DOT
, NIL
, NIL
)));
631 np
= op2(CCL
, NIL
, (Node
*) cclenter((char *) rlxstr
));
635 np
= op2(NCCL
, NIL
, (Node
*) cclenter((char *) rlxstr
));
640 return (unary(op2(CHAR
, NIL
, itonp(HAT
))));
643 return (unary(op2(CHAR
, NIL
, NIL
)));
646 if (rtok
== ')') { /* special pleading for () */
648 return unary(op2(CCL
, NIL
, (Node
*) tostring("")));
656 FATAL("syntax error in regular expression %s at %s", lastre
, prestr
);
658 FATAL("illegal primary in regular expression %s at %s", lastre
, prestr
);
660 return 0; /*NOTREACHED*/
663 Node
*concat(Node
*np
)
666 case CHAR
: case DOT
: case ALL
: case CCL
: case NCCL
: case '$': case '(':
667 return (concat(op2(CAT
, np
, primary())));
676 return (alt(op2(OR
, np
, concat(primary()))));
681 Node
*unary(Node
*np
)
686 return (unary(op2(STAR
, np
, NIL
)));
689 return (unary(op2(PLUS
, np
, NIL
)));
692 return (unary(op2(QUEST
, np
, NIL
)));
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
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.
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
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.
722 return c
==' ' || c
=='\t';
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
},
748 int relex(void) /* lexical analyzer for reparse */
752 static uschar
*buf
= 0;
753 static int bufsz
= 100;
755 struct charclass
*cc
;
758 switch (c
= *prestr
++) {
760 case '*': return STAR
;
761 case '+': return PLUS
;
762 case '?': return QUEST
;
763 case '.': return DOT
;
764 case '\0': prestr
--; return '\0';
771 rlxval
= quoted((char **) &prestr
);
777 if (buf
== 0 && (buf
= (uschar
*) malloc(bufsz
)) == NULL
)
778 FATAL("out of space in reg expr %.10s..", lastre
);
780 if (*prestr
== '^') {
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
);
790 if ((c
= *prestr
++) == '\\') {
792 if ((c
= *prestr
++) == '\0')
793 FATAL("nonterminated character class %.20s...", lastre
);
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)
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
)) {
815 } else if (c
== '\0') {
816 FATAL("nonterminated character class %.20s", lastre
);
817 } else if (bp
== buf
) { /* 1st char is special */
819 } else if (c
== ']') {
821 rlxstr
= (uschar
*) tostring((char *) buf
);
832 int cgoto(fa
*f
, int s
, int c
)
837 while (f
->accept
>= maxsetvec
) { /* guessing here! */
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()");
844 for (i
= 0; i
<= f
->accept
; i
++)
847 /* compute positions of gototab[s,c] into setvec */
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
) {
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");
865 if (setvec
[q
[j
]] == 0) {
873 /* determine if setvec is a previous state */
876 for (i
= f
->accept
; i
>= 0; i
--)
880 /* tmpset == previous state? */
881 for (i
= 1; i
<= f
->curstat
; i
++) {
883 if ((k
= tmpset
[0]) != p
[0])
885 for (j
= 1; j
<= k
; j
++)
886 if (tmpset
[j
] != p
[j
])
888 /* setvec is state i */
889 f
->gototab
[s
][c
] = i
;
894 /* add tmpset to current set of states */
895 if (f
->curstat
>= NSTATES
-1) {
898 for (i
= 2; i
< NSTATES
; i
++)
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");
908 f
->posns
[f
->curstat
] = p
;
909 f
->gototab
[s
][c
] = f
->curstat
;
910 for (i
= 0; i
<= setcnt
; i
++)
912 if (setvec
[f
->accept
])
913 f
->out
[f
->curstat
] = 1;
915 f
->out
[f
->curstat
] = 0;
920 void freefa(fa
*f
) /* free a finite automaton */
926 for (i
= 0; i
<= f
->curstat
; 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
));