38 #define	NISERR()	VISERR(nfa->v)
39 #define	NERR(e)		(void)VERR(nfa->v, (e))
46 static struct nfa *		/* the NFA, or NULL */
50 struct nfa *parent;		/* NULL if primary NFA */
52 	struct nfa *nfa;  local
54 	nfa = (struct nfa *)MALLOC(sizeof(struct nfa));
55 	if (nfa == NULL)
58 	nfa->states = NULL;
59 	nfa->slast = NULL;
60 	nfa->free = NULL;
61 	nfa->nstates = 0;
62 	nfa->cm = cm;
63 	nfa->v = v;
64 	nfa->bos[0] = nfa->bos[1] = COLORLESS;
65 	nfa->eos[0] = nfa->eos[1] = COLORLESS;
66 	nfa->post = newfstate(nfa, '@');	/* number 0 */
67 	nfa->pre = newfstate(nfa, '>');		/* number 1 */
68 	nfa->parent = parent;
70 	nfa->init = newstate(nfa);		/* may become invalid later */
71 	nfa->final = newstate(nfa);
73 		freenfa(nfa);
76 	rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->pre, nfa->init);
77 	newarc(nfa, '^', 1, nfa->pre, nfa->init);
78 	newarc(nfa, '^', 0, nfa->pre, nfa->init);
79 	rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->final, nfa->post);
80 	newarc(nfa, '$', 1, nfa->final, nfa->post);
81 	newarc(nfa, '$', 0, nfa->final, nfa->post);
84 		freenfa(nfa);
87 	return nfa;
95 freenfa(nfa)  in freenfa()  argument
96 struct nfa *nfa;  in freenfa()
100 	while ((s = nfa->states) != NULL) {
102 		freestate(nfa, s);
104 	while ((s = nfa->free) != NULL) {
105 		nfa->free = s->next;
106 		destroystate(nfa, s);
109 	nfa->slast = NULL;
110 	nfa->nstates = -1;
111 	nfa->pre = NULL;
112 	nfa->post = NULL;
113 	FREE(nfa);
121 newstate(nfa)  in newstate()  argument
122 struct nfa *nfa;  in newstate()
126 	if (nfa->free != NULL) {
127 		s = nfa->free;
128 		nfa->free = s->next;
140 	assert(nfa->nstates >= 0);
141 	s->no = nfa->nstates++;
143 	if (nfa->states == NULL)
144 		nfa->states = s;
151 	if (nfa->slast != NULL) {
152 		assert(nfa->slast->next == NULL);
153 		nfa->slast->next = s;
155 	s->prev = nfa->slast;
156 	nfa->slast = s;
165 newfstate(nfa, flag)  in newfstate()  argument
166 struct nfa *nfa;  in newfstate()
171 	s = newstate(nfa);
182 dropstate(nfa, s)  in dropstate()  argument
183 struct nfa *nfa;  in dropstate()
189 		freearc(nfa, a);
191 		freearc(nfa, a);
192 	freestate(nfa, s);
200 freestate(nfa, s)  in freestate()  argument
201 struct nfa *nfa;  in freestate()
212 		assert(s == nfa->slast);
213 		nfa->slast = s->prev;
218 		assert(s == nfa->states);
219 		nfa->states = s->next;
222 	s->next = nfa->free;	/* don't delete it, put it on the free list */
223 	nfa->free = s;
231 destroystate(nfa, s)  in destroystate()  argument
232 struct nfa *nfa;  in destroystate()
255 newarc(nfa, t, co, from, to)  in newarc()  argument
256 struct nfa *nfa;  in newarc()
271 	a = allocarc(nfa, from);
295 	if (COLORED(a) && nfa->parent == NULL)
296 		colorchain(nfa->cm, a);
306 allocarc(nfa, s)  in allocarc()  argument
307 struct nfa *nfa;  in allocarc()
350 freearc(nfa, victim)  in freearc()  argument
351 struct nfa *nfa;  in freearc()
361 	if (COLORED(victim) && nfa->parent == NULL)
362 		uncolorchain(nfa->cm, victim);
427 cparc(nfa, oa, from, to)  in cparc()  argument
428 struct nfa *nfa;  in cparc()
433 	newarc(nfa, oa->type, oa->co, from, to);
445 moveins(nfa, old, new)  in moveins()  argument
446 struct nfa *nfa;  in moveins()
455 		cparc(nfa, a, a->from, new);
456 		freearc(nfa, a);
467 copyins(nfa, old, new)  in copyins()  argument
468 struct nfa *nfa;  in copyins()
477 		cparc(nfa, a, a->from, new);
485 moveouts(nfa, old, new)  in moveouts()  argument
486 struct nfa *nfa;  in moveouts()
495 		cparc(nfa, a, new, a->to);
496 		freearc(nfa, a);
505 copyouts(nfa, old, new)  in copyouts()  argument
506 struct nfa *nfa;  in copyouts()
515 		cparc(nfa, a, new, a->to);
524 cloneouts(nfa, old, from, to, type)  in cloneouts()  argument
525 struct nfa *nfa;  in cloneouts()
536 		newarc(nfa, type, a->co, from, to);
546 delsub(nfa, lp, rp)  in delsub()  argument
547 struct nfa *nfa;  in delsub()
555 	deltraverse(nfa, lp, lp);
569 deltraverse(nfa, leftend, s)  in deltraverse()  argument
570 struct nfa *nfa;  in deltraverse()
586 		deltraverse(nfa, leftend, to);
588 		freearc(nfa, a);
591 			freestate(nfa, to);
611 dupnfa(nfa, start, stop, from, to)  in dupnfa()  argument
612 struct nfa *nfa;  in dupnfa()
619 		newarc(nfa, EMPTY, 0, from, to);
624 	duptraverse(nfa, start, from);
628 	cleartraverse(nfa, start);
636 duptraverse(nfa, s, stmp)  in duptraverse()  argument
637 struct nfa *nfa;  in duptraverse()
646 	s->tmp = (stmp == NULL) ? newstate(nfa) : stmp;
653 		duptraverse(nfa, a->to, (struct state *)NULL);
655 		cparc(nfa, a, s->tmp, a->to->tmp);
664 cleartraverse(nfa, s)  in cleartraverse()  argument
665 struct nfa *nfa;  in cleartraverse()
675 		cleartraverse(nfa, a->to);
683 specialcolors(nfa)  in specialcolors()  argument
684 struct nfa *nfa;  in specialcolors()
687 	if (nfa->parent == NULL) {
688 		nfa->bos[0] = pseudocolor(nfa->cm);
689 		nfa->bos[1] = pseudocolor(nfa->cm);
690 		nfa->eos[0] = pseudocolor(nfa->cm);
691 		nfa->eos[1] = pseudocolor(nfa->cm);
693 		assert(nfa->parent->bos[0] != COLORLESS);
694 		nfa->bos[0] = nfa->parent->bos[0];
695 		assert(nfa->parent->bos[1] != COLORLESS);
696 		nfa->bos[1] = nfa->parent->bos[1];
697 		assert(nfa->parent->eos[0] != COLORLESS);
698 		nfa->eos[0] = nfa->parent->eos[0];
699 		assert(nfa->parent->eos[1] != COLORLESS);
700 		nfa->eos[1] = nfa->parent->eos[1];
709 optimize(nfa, f)  in optimize()  argument
710 struct nfa *nfa;  in optimize()
717 	cleanup(nfa);		/* may simplify situation */
719 		dumpnfa(nfa, f);
722 	fixempties(nfa, f);	/* get rid of EMPTY arcs */
725 	pullback(nfa, f);	/* pull back constraints backward */
726 	pushfwd(nfa, f);	/* push fwd constraints forward */
729 	cleanup(nfa);		/* final tidying */
730 	return analyze(nfa);	/* and analysis */
738 pullback(nfa, f)  in pullback()  argument
739 struct nfa *nfa;  in pullback()
751 		for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
756 					if (pull(nfa, a))
762 			dumpnfa(nfa, f);
767 	for (a = nfa->pre->outs; a != NULL; a = nexta) {
771 			newarc(nfa, PLAIN, nfa->bos[a->co], a->from, a->to);
772 			freearc(nfa, a);
785 pull(nfa, con)  in pull()  argument
786 struct nfa *nfa;  in pull()
796 		freearc(nfa, con);
802 		freearc(nfa, con);
808 		s = newstate(nfa);
812 		copyins(nfa, from, s);		/* duplicate inarcs */
813 		cparc(nfa, con, s, to);		/* move constraint arc */
814 		freearc(nfa, con);
825 			freearc(nfa, a);
830 			s = newstate(nfa);
833 			cparc(nfa, a, s, to);		/* anticipate move */
834 			cparc(nfa, con, a->from, s);
837 			freearc(nfa, a);
846 	moveins(nfa, from, to);
847 	dropstate(nfa, from);		/* will free the constraint */
856 pushfwd(nfa, f)  in pushfwd()  argument
857 struct nfa *nfa;  in pushfwd()
869 		for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
874 					if (push(nfa, a))
880 			dumpnfa(nfa, f);
885 	for (a = nfa->post->ins; a != NULL; a = nexta) {
889 			newarc(nfa, PLAIN, nfa->eos[a->co], a->from, a->to);
890 			freearc(nfa, a);
903 push(nfa, con)  in push()  argument
904 struct nfa *nfa;  in push()
914 		freearc(nfa, con);
920 		freearc(nfa, con);
926 		s = newstate(nfa);
929 		copyouts(nfa, to, s);		/* duplicate outarcs */
930 		cparc(nfa, con, from, s);	/* move constraint */
931 		freearc(nfa, con);
942 			freearc(nfa, a);
947 			s = newstate(nfa);
950 			cparc(nfa, con, s, a->to);	/* anticipate move */
951 			cparc(nfa, a, from, s);
954 			freearc(nfa, a);
963 	moveouts(nfa, to, from);
964 	dropstate(nfa, to);		/* will free the constraint */
1038 fixempties(nfa, f)  in fixempties()  argument
1039 struct nfa *nfa;  in fixempties()
1051 		for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
1055 				if (a->type == EMPTY && unempty(nfa, a))
1061 			dumpnfa(nfa, f);
1072 unempty(nfa, a)  in unempty()  argument
1073 struct nfa *nfa;  in unempty()
1081 	assert(from != nfa->pre && to != nfa->post);
1084 		freearc(nfa, a);
1098 	freearc(nfa, a);
1102 			moveins(nfa, from, to);
1103 			freestate(nfa, from);
1105 			copyins(nfa, from, to);
1109 			moveouts(nfa, to, from);
1110 			freestate(nfa, to);
1112 			copyouts(nfa, to, from);
1123 cleanup(nfa)  in cleanup()  argument
1124 struct nfa *nfa;  in cleanup()
1132 	markreachable(nfa, nfa->pre, (struct state *)NULL, nfa->pre);
1133 	markcanreach(nfa, nfa->post, nfa->pre, nfa->post);
1134 	for (s = nfa->states; s != NULL; s = nexts) {
1136 		if (s->tmp != nfa->post && !s->flag)
1137 			dropstate(nfa, s);
1139 	assert(nfa->post->nins == 0 || nfa->post->tmp == nfa->post);
1140 	cleartraverse(nfa, nfa->pre);
1141 	assert(nfa->post->nins == 0 || nfa->post->tmp == NULL);
1146 	for (s = nfa->states; s != NULL; s = s->next)
1148 	nfa->nstates = n;
1157 markreachable(nfa, s, okay, mark)  in markreachable()  argument
1158 struct nfa *nfa;  in markreachable()
1170 		markreachable(nfa, a->to, okay, mark);
1179 markcanreach(nfa, s, okay, mark)  in markcanreach()  argument
1180 struct nfa *nfa;  in markcanreach()
1192 		markcanreach(nfa, a->from, okay, mark);
1200 analyze(nfa)  in analyze()  argument
1201 struct nfa *nfa;  in analyze()
1206 	if (nfa->pre->outs == NULL)
1208 	for (a = nfa->pre->outs; a != NULL; a = a->outchain)
1210 			if (aa->to == nfa->post)
1220 compact(nfa, cnfa)  in compact()  argument
1221 struct nfa *nfa;  in compact()
1235 	for (s = nfa->states; s != NULL; s = s->next) {
1252 	cnfa->pre = nfa->pre->no;
1253 	cnfa->post = nfa->post->no;
1254 	cnfa->bos[0] = nfa->bos[0];
1255 	cnfa->bos[1] = nfa->bos[1];
1256 	cnfa->eos[0] = nfa->eos[0];
1257 	cnfa->eos[1] = nfa->eos[1];
1258 	cnfa->ncolors = maxcolor(nfa->cm) + 1;
1262 	for (s = nfa->states; s != NULL; s = s->next) {
1295 	for (a = nfa->pre->outs; a != NULL; a = a->outchain)
1297 	cnfa->states[nfa->pre->no]->co = 1;
1348 dumpnfa(nfa, f)  in dumpnfa()  argument
1349 struct nfa *nfa;  in dumpnfa()
1355 	fprintf(f, "pre %d, post %d", nfa->pre->no, nfa->post->no);
1356 	if (nfa->bos[0] != COLORLESS)
1357 		fprintf(f, ", bos [%ld]", (long)nfa->bos[0]);
1358 	if (nfa->bos[1] != COLORLESS)
1359 		fprintf(f, ", bol [%ld]", (long)nfa->bos[1]);
1360 	if (nfa->eos[0] != COLORLESS)
1361 		fprintf(f, ", eos [%ld]", (long)nfa->eos[0]);
1362 	if (nfa->eos[1] != COLORLESS)
1363 		fprintf(f, ", eol [%ld]", (long)nfa->eos[1]);
1365 	for (s = nfa->states; s != NULL; s = s->next)
1367 	if (nfa->parent == NULL)
1368 		dumpcolors(nfa->cm, f);