62 #define	HAT	(NCHARS-1)	/* matches ^ in regular expr */
69 #define	right(v)	(v)->narg[1]
123 	static int now = 1;  in makedfa()
151 	for (i = 1; i < nfatab; i++)  in makedfa()
164  * anchor = 1 for anchored matches, else 0
170 	fa *f;  in mkdfa()  local
180 	if ((f = (fa *)calloc(1, sizeof (fa) + poscnt * sizeof (rrow))) == NULL)  in mkdfa()
183 	f->accept = poscnt-1;  in mkdfa()
184 	cfoll(f, p1);	/* set up follow sets */  in mkdfa()
186 	if ((f->posns[0] =  in mkdfa()
187 	    (int *)calloc(1, *(f->re[0].lfollow) * sizeof (int))) == NULL) {  in mkdfa()
190 	if ((f->posns[1] = (int *)calloc(1, sizeof (int))) == NULL)  in mkdfa()
192 	*f->posns[1] = 0;  in mkdfa()
193 	f->initstat = makeinit(f, anchor);  in mkdfa()
194 	f->anchor = anchor;  in mkdfa()
195 	f->restr = (uschar *)tostring(s);  in mkdfa()
196 	return (f);  in mkdfa()
200 makeinit(fa *f, int anchor)  in makeinit()  argument
204 	f->curstat = 2;  in makeinit()
205 	f->out[2] = 0;  in makeinit()
206 	f->reset = 0;  in makeinit()
207 	k = *(f->re[0].lfollow);  in makeinit()
208 	xfree(f->posns[2]);  in makeinit()
209 	if ((f->posns[2] = (int *)calloc(1, (k+1) * sizeof (int))) == NULL)  in makeinit()
212 		(f->posns[2])[i] = (f->re[0].lfollow)[i];  in makeinit()
214 	if ((f->posns[2])[1] == f->accept)  in makeinit()
215 		f->out[2] = 1;  in makeinit()
217 		f->gototab[2][i] = 0;  in makeinit()
218 	f->curstat = cgoto(f, 2, HAT);  in makeinit()
220 		*f->posns[2] = k-1;	/* leave out position 0 */  in makeinit()
222 			(f->posns[0])[i] = (f->posns[2])[i];  in makeinit()
225 		f->out[0] = f->out[2];  in makeinit()
226 		if (f->curstat != 2)  in makeinit()
227 			--(*f->posns[f->curstat]);  in makeinit()
229 	return (f->curstat);  in makeinit()
311 		else if (*p >= 'a' && *p <= 'f')  in hexstr()
313 		else if (*p >= 'A' && *p <= 'F')  in hexstr()
333 	else if (c == 'f')  in quoted()
334 		c = '\f';  in quoted()
368 		FATAL("out of space for character class [%.10s...] 1", p);  in cclenter()
373 		} else if (c == '-' && i > 0 && bp[-1] != 0) {  in cclenter()
375 				c = bp[-1];  in cclenter()
418 cfoll(fa *f, Node *v)  in cfoll()  argument
426 		f->re[info(v)].ltype = type(v);  in cfoll()
427 		f->re[info(v)].lval.np = right(v);  in cfoll()
428 		while (f->accept >= maxsetvec) {	/* guessing here! */  in cfoll()
431 		for (i = 0; i <= f->accept; i++)  in cfoll()
435 		if ((p = (int *)calloc(1, (setcnt+1) * sizeof (int))) == NULL)  in cfoll()
437 		f->re[info(v)].lfollow = p;  in cfoll()
439 		for (i = f->accept; i >= 0; i--) {  in cfoll()
440 			if (setvec[i] == 1)  in cfoll()
445 		cfoll(f, left(v));  in cfoll()
449 		cfoll(f, left(v));  in cfoll()
450 		cfoll(f, right(v));  in cfoll()
459  * returns 0 or 1 depending on whether p matches empty string
478 		if (setvec[lp] != 1) {  in first()
479 			setvec[lp] = 1;  in first()
485 			return (1);  in first()
489 		return (1);  in first()
497 		return (1);  in first()
502 		return (1);  in first()
550 			return (1);  in member()
556 match(fa *f, const char *p0)	/* shortest match ? */  in match()  argument
561 	s = f->reset ? makeinit(f, 0) : f->initstat;  in match()
562 	if (f->out[s])  in match()
563 		return (1);  in match()
565 		if ((ns = f->gototab[s][*p]) != 0)  in match()
568 			s = cgoto(f, s, *p);  in match()
569 		if (f->out[s])  in match()
570 			return (1);  in match()
576 pmatch(fa *f, const char *p0)	/* longest match, for sub */  in pmatch()  argument
583 	if (f->reset) {  in pmatch()
584 		f->initstat = s = makeinit(f, 1);  in pmatch()
586 		s = f->initstat;  in pmatch()
589 	patlen = -1;  in pmatch()
593 			if (f->out[s])		/* final state */  in pmatch()
595 			if ((ns = f->gototab[s][*q]) != 0)  in pmatch()
598 				s = cgoto(f, s, *q);  in pmatch()
599 			if (s == 1) {	/* no transition */  in pmatch()
602 					return (1);  in pmatch()
608 		if (f->out[s])  in pmatch()
609 			patlen = q - p - 1;	/* don't count $ */  in pmatch()
612 			return (1);  in pmatch()
616 		if (f->reset) {  in pmatch()
617 			for (i = 2; i <= f->curstat; i++)  in pmatch()
618 				xfree(f->posns[i]);  in pmatch()
619 			k = *f->posns[0];  in pmatch()
620 			if ((f->posns[2] =  in pmatch()
621 			    (int *)calloc(k + 1, sizeof (int))) == NULL) {  in pmatch()
625 				(f->posns[2])[i] = (f->posns[0])[i];  in pmatch()
626 			f->initstat = f->curstat = 2;  in pmatch()
627 			f->out[2] = f->out[0];  in pmatch()
629 				f->gototab[2][i] = 0;  in pmatch()
636 nematch(fa *f, const char *p0)	/* non-empty match, for sub */  in nematch()  argument
643 	if (f->reset) {  in nematch()
644 		f->initstat = s = makeinit(f, 1);  in nematch()
646 		s = f->initstat;  in nematch()
648 	patlen = -1;  in nematch()
652 			if (f->out[s])		/* final state */  in nematch()
654 			if ((ns = f->gototab[s][*q]) != 0)  in nematch()
657 				s = cgoto(f, s, *q);  in nematch()
658 			if (s == 1) {	/* no transition */  in nematch()
661 					return (1);  in nematch()
666 		if (f->out[s])  in nematch()
667 			patlen = q - p - 1;	/* don't count $ */  in nematch()
670 			return (1);  in nematch()
674 		if (f->reset) {  in nematch()
675 			for (i = 2; i <= f->curstat; i++)  in nematch()
676 				xfree(f->posns[i]);  in nematch()
677 			k = *f->posns[0];  in nematch()
678 			if ((f->posns[2] =  in nematch()
679 			    (int *)calloc(k + 1, sizeof (int))) == NULL) {  in nematch()
683 				(f->posns[2])[i] = (f->posns[0])[i];  in nematch()
684 			f->initstat = f->curstat = 2;  in nematch()
685 			f->out[2] = f->out[0];  in nematch()
687 				f->gototab[2][i] = 0;  in nematch()
834  * defined in IEEE P1003.1 draft 7 of June 2001, assuming the source
898 			cflag = 1;  in relex()
902 		n = 2 * strlen((const char *)prestr) + 1;  in relex()
920 					if (strncmp((const char *)prestr + 1,  in relex()
926 				    prestr[1 + cc->cc_namelen] != ':' ||  in relex()
934 				 * BUG: We begin at 1, instead of 0, since we  in relex()
941 				for (i = 1; i < NCHARS; i++) {  in relex()
943 					    bp - buf + 1, 100, (char **)&bp,  in relex()
953 			} else if (bp == buf) {	/* 1st char is special */  in relex()
971 cgoto(fa *f, int s, int c)  in cgoto()  argument
977 	while (f->accept >= maxsetvec) {	/* guessing here! */  in cgoto()
980 	for (i = 0; i <= f->accept; i++)  in cgoto()
984 	p = f->posns[s];  in cgoto()
985 	for (i = 1; i <= *p; i++) {  in cgoto()
986 		if ((k = f->re[p[i]].ltype) != FINAL) {  in cgoto()
987 			if ((k == CHAR && c == ptoi(f->re[p[i]].lval.np)) ||  in cgoto()
992 			    member(c, (char *)f->re[p[i]].lval.up)) ||  in cgoto()
994 			    !member(c, (char *)f->re[p[i]].lval.up) &&  in cgoto()
996 				q = f->re[p[i]].lfollow;  in cgoto()
997 				for (j = 1; j <= *q; j++) {  in cgoto()
1003 						setvec[q[j]] = 1;  in cgoto()
1011 	j = 1;  in cgoto()
1012 	for (i = f->accept; i >= 0; i--)  in cgoto()
1017 	for (i = 1; i <= f->curstat; i++) {  in cgoto()
1018 		p = f->posns[i];  in cgoto()
1021 		for (j = 1; j <= k; j++)  in cgoto()
1025 		f->gototab[s][c] = i;  in cgoto()
1031 	if (f->curstat >= NSTATES-1) {  in cgoto()
1032 		f->curstat = 2;  in cgoto()
1033 		f->reset = 1;  in cgoto()
1035 			xfree(f->posns[i]);  in cgoto()
1037 		++(f->curstat);  in cgoto()
1039 		f->gototab[f->curstat][i] = 0;  in cgoto()
1040 	xfree(f->posns[f->curstat]);  in cgoto()
1041 	if ((p = (int *)calloc(1, (setcnt + 1) * sizeof (int))) == NULL)  in cgoto()
1044 	f->posns[f->curstat] = p;  in cgoto()
1045 	f->gototab[s][c] = f->curstat;  in cgoto()
1048 	if (setvec[f->accept])  in cgoto()
1049 		f->out[f->curstat] = 1;  in cgoto()
1051 		f->out[f->curstat] = 0;  in cgoto()
1052 	return (f->curstat);  in cgoto()
1056 freefa(fa *f)	/* free a finite automaton */  in freefa()  argument
1060 	if (f == NULL)  in freefa()
1062 	for (i = 0; i <= f->curstat; i++)  in freefa()
1063 		xfree(f->posns[i]);  in freefa()
1064 	for (i = 0; i <= f->accept; i++) {  in freefa()
1065 		xfree(f->re[i].lfollow);  in freefa()
1066 		if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL)  in freefa()
1067 			xfree((f->re[i].lval.np));  in freefa()
1069 	xfree(f->restr);  in freefa()
1070 	xfree(f);  in freefa()