Lines Matching refs:nfa
39 #define NISERR() VISERR(nfa->v)
40 #define NERR(e) VERR(nfa->v, (e))
46 static struct nfa * /* the NFA, or NULL */
49 struct nfa *parent) /* NULL if primary NFA */ in newnfa()
51 struct nfa *nfa; in newnfa() local
53 nfa = (struct nfa *) MALLOC(sizeof(struct nfa)); in newnfa()
54 if (nfa == NULL) in newnfa()
60 nfa->states = NULL; in newnfa()
61 nfa->slast = NULL; in newnfa()
62 nfa->free = NULL; in newnfa()
63 nfa->nstates = 0; in newnfa()
64 nfa->cm = cm; in newnfa()
65 nfa->v = v; in newnfa()
66 nfa->bos[0] = nfa->bos[1] = COLORLESS; in newnfa()
67 nfa->eos[0] = nfa->eos[1] = COLORLESS; in newnfa()
68 nfa->parent = parent; /* Precedes newfstate so parent is valid. */ in newnfa()
69 nfa->post = newfstate(nfa, '@'); /* number 0 */ in newnfa()
70 nfa->pre = newfstate(nfa, '>'); /* number 1 */ in newnfa()
72 nfa->init = newstate(nfa); /* may become invalid later */ in newnfa()
73 nfa->final = newstate(nfa); in newnfa()
76 freenfa(nfa); in newnfa()
79 rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->pre, nfa->init); in newnfa()
80 newarc(nfa, '^', 1, nfa->pre, nfa->init); in newnfa()
81 newarc(nfa, '^', 0, nfa->pre, nfa->init); in newnfa()
82 rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->final, nfa->post); in newnfa()
83 newarc(nfa, '$', 1, nfa->final, nfa->post); in newnfa()
84 newarc(nfa, '$', 0, nfa->final, nfa->post); in newnfa()
88 freenfa(nfa); in newnfa()
91 return nfa; in newnfa()
98 freenfa(struct nfa *nfa) in freenfa() argument
102 while ((s = nfa->states) != NULL) in freenfa()
105 freestate(nfa, s); in freenfa()
107 while ((s = nfa->free) != NULL) in freenfa()
109 nfa->free = s->next; in freenfa()
110 destroystate(nfa, s); in freenfa()
113 nfa->slast = NULL; in freenfa()
114 nfa->nstates = -1; in freenfa()
115 nfa->pre = NULL; in freenfa()
116 nfa->post = NULL; in freenfa()
117 FREE(nfa); in freenfa()
124 newstate(struct nfa *nfa) in newstate() argument
133 if (CANCEL_REQUESTED(nfa->v->re)) in newstate()
139 if (nfa->free != NULL) in newstate()
141 s = nfa->free; in newstate()
142 nfa->free = s->next; in newstate()
146 if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE) in newstate()
157 nfa->v->spaceused += sizeof(struct state); in newstate()
163 assert(nfa->nstates >= 0); in newstate()
164 s->no = nfa->nstates++; in newstate()
166 if (nfa->states == NULL) in newstate()
167 nfa->states = s; in newstate()
174 if (nfa->slast != NULL) in newstate()
176 assert(nfa->slast->next == NULL); in newstate()
177 nfa->slast->next = s; in newstate()
179 s->prev = nfa->slast; in newstate()
180 nfa->slast = s; in newstate()
188 newfstate(struct nfa *nfa, int flag) in newfstate() argument
192 s = newstate(nfa); in newfstate()
202 dropstate(struct nfa *nfa, in dropstate() argument
208 freearc(nfa, a); in dropstate()
210 freearc(nfa, a); in dropstate()
211 freestate(nfa, s); in dropstate()
218 freestate(struct nfa *nfa, in freestate() argument
230 assert(s == nfa->slast); in freestate()
231 nfa->slast = s->prev; in freestate()
237 assert(s == nfa->states); in freestate()
238 nfa->states = s->next; in freestate()
241 s->next = nfa->free; /* don't delete it, put it on the free list */ in freestate()
242 nfa->free = s; in freestate()
249 destroystate(struct nfa *nfa, in destroystate() argument
260 nfa->v->spaceused -= sizeof(struct arcbatch); in destroystate()
266 nfa->v->spaceused -= sizeof(struct state); in destroystate()
276 newarc(struct nfa *nfa, in newarc() argument
291 if (CANCEL_REQUESTED(nfa->v->re)) in newarc()
312 createarc(nfa, t, co, from, to); in newarc()
322 createarc(struct nfa *nfa, in createarc() argument
331 a = allocarc(nfa, from); in createarc()
360 if (COLORED(a) && nfa->parent == NULL) in createarc()
361 colorchain(nfa->cm, a); in createarc()
368 allocarc(struct nfa *nfa, in allocarc() argument
387 if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE) in allocarc()
398 nfa->v->spaceused += sizeof(struct arcbatch); in allocarc()
421 freearc(struct nfa *nfa, in freearc() argument
431 if (COLORED(victim) && nfa->parent == NULL) in freearc()
432 uncolorchain(nfa->cm, victim); in freearc()
570 cparc(struct nfa *nfa, in cparc() argument
575 newarc(nfa, oa->type, oa->co, from, to); in cparc()
582 sortins(struct nfa *nfa, in sortins() argument
649 sortouts(struct nfa *nfa, in sortouts() argument
736 moveins(struct nfa *nfa, in moveins() argument
749 cparc(nfa, a, a->from, newState); in moveins()
750 freearc(nfa, a); in moveins()
767 if (CANCEL_REQUESTED(nfa->v->re)) in moveins()
773 sortins(nfa, oldState); in moveins()
774 sortins(nfa, newState); in moveins()
800 freearc(nfa, a); in moveins()
828 copyins(struct nfa *nfa, in copyins() argument
840 cparc(nfa, a, a->from, newState); in copyins()
856 if (CANCEL_REQUESTED(nfa->v->re)) in copyins()
862 sortins(nfa, oldState); in copyins()
863 sortins(nfa, newState); in copyins()
877 createarc(nfa, a->type, a->co, a->from, newState); in copyins()
898 createarc(nfa, a->type, a->co, a->from, newState); in copyins()
910 mergeins(struct nfa *nfa, in mergeins() argument
926 if (CANCEL_REQUESTED(nfa->v->re)) in mergeins()
933 sortins(nfa, s); in mergeins()
977 createarc(nfa, a->type, a->co, a->from, s); in mergeins()
998 createarc(nfa, a->type, a->co, a->from, s); in mergeins()
1007 moveouts(struct nfa *nfa, in moveouts() argument
1020 cparc(nfa, a, newState, a->to); in moveouts()
1021 freearc(nfa, a); in moveouts()
1038 if (CANCEL_REQUESTED(nfa->v->re)) in moveouts()
1044 sortouts(nfa, oldState); in moveouts()
1045 sortouts(nfa, newState); in moveouts()
1059 createarc(nfa, a->type, a->co, newState, a->to); in moveouts()
1060 freearc(nfa, a); in moveouts()
1067 freearc(nfa, a); in moveouts()
1083 createarc(nfa, a->type, a->co, newState, a->to); in moveouts()
1084 freearc(nfa, a); in moveouts()
1096 copyouts(struct nfa *nfa, in copyouts() argument
1108 cparc(nfa, a, newState, a->to); in copyouts()
1124 if (CANCEL_REQUESTED(nfa->v->re)) in copyouts()
1130 sortouts(nfa, oldState); in copyouts()
1131 sortouts(nfa, newState); in copyouts()
1145 createarc(nfa, a->type, a->co, newState, a->to); in copyouts()
1166 createarc(nfa, a->type, a->co, newState, a->to); in copyouts()
1175 cloneouts(struct nfa *nfa, in cloneouts() argument
1186 newarc(nfa, type, a->co, from, to); in cloneouts()
1196 delsub(struct nfa *nfa, in delsub() argument
1204 deltraverse(nfa, lp, lp); in delsub()
1219 deltraverse(struct nfa *nfa, in deltraverse() argument
1227 if (STACK_TOO_DEEP(nfa->v->re)) in deltraverse()
1243 deltraverse(nfa, leftend, to); in deltraverse()
1247 freearc(nfa, a); in deltraverse()
1251 freestate(nfa, to); in deltraverse()
1270 dupnfa(struct nfa *nfa, in dupnfa() argument
1278 newarc(nfa, EMPTY, 0, from, to); in dupnfa()
1283 duptraverse(nfa, start, from); in dupnfa()
1287 cleartraverse(nfa, start); in dupnfa()
1294 duptraverse(struct nfa *nfa, in duptraverse() argument
1301 if (STACK_TOO_DEEP(nfa->v->re)) in duptraverse()
1310 s->tmp = (stmp == NULL) ? newstate(nfa) : stmp; in duptraverse()
1319 duptraverse(nfa, a->to, (struct state *) NULL); in duptraverse()
1323 cparc(nfa, a, s->tmp, a->to->tmp); in duptraverse()
1331 cleartraverse(struct nfa *nfa, in cleartraverse() argument
1337 if (STACK_TOO_DEEP(nfa->v->re)) in cleartraverse()
1348 cleartraverse(nfa, a->to); in cleartraverse()
1398 specialcolors(struct nfa *nfa) in specialcolors() argument
1401 if (nfa->parent == NULL) in specialcolors()
1403 nfa->bos[0] = pseudocolor(nfa->cm); in specialcolors()
1404 nfa->bos[1] = pseudocolor(nfa->cm); in specialcolors()
1405 nfa->eos[0] = pseudocolor(nfa->cm); in specialcolors()
1406 nfa->eos[1] = pseudocolor(nfa->cm); in specialcolors()
1410 assert(nfa->parent->bos[0] != COLORLESS); in specialcolors()
1411 nfa->bos[0] = nfa->parent->bos[0]; in specialcolors()
1412 assert(nfa->parent->bos[1] != COLORLESS); in specialcolors()
1413 nfa->bos[1] = nfa->parent->bos[1]; in specialcolors()
1414 assert(nfa->parent->eos[0] != COLORLESS); in specialcolors()
1415 nfa->eos[0] = nfa->parent->eos[0]; in specialcolors()
1416 assert(nfa->parent->eos[1] != COLORLESS); in specialcolors()
1417 nfa->eos[1] = nfa->parent->eos[1]; in specialcolors()
1437 optimize(struct nfa *nfa, in optimize() argument
1446 cleanup(nfa); /* may simplify situation */ in optimize()
1449 dumpnfa(nfa, f); in optimize()
1453 fixempties(nfa, f); /* get rid of EMPTY arcs */ in optimize()
1458 fixconstraintloops(nfa, f); /* get rid of constraint loops */ in optimize()
1459 pullback(nfa, f); /* pull back constraints backward */ in optimize()
1460 pushfwd(nfa, f); /* push fwd constraints forward */ in optimize()
1465 cleanup(nfa); /* final tidying */ in optimize()
1468 dumpnfa(nfa, f); in optimize()
1470 return analyze(nfa); /* and analysis */ in optimize()
1477 pullback(struct nfa *nfa, in pullback() argument
1491 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) in pullback()
1499 if (pull(nfa, a, &intermediates)) in pullback()
1512 dropstate(nfa, s); in pullback()
1515 dumpnfa(nfa, f); in pullback()
1526 for (a = nfa->pre->outs; a != NULL; a = nexta) in pullback()
1532 newarc(nfa, PLAIN, nfa->bos[a->co], a->from, a->to); in pullback()
1533 freearc(nfa, a); in pullback()
1557 pull(struct nfa *nfa, in pull() argument
1572 freearc(nfa, con); in pull()
1583 s = newstate(nfa); in pull()
1586 copyins(nfa, from, s); /* duplicate inarcs */ in pull()
1587 cparc(nfa, con, s, to); /* move constraint arc */ in pull()
1588 freearc(nfa, con); in pull()
1603 freearc(nfa, a); in pull()
1617 s = newstate(nfa); in pull()
1623 cparc(nfa, con, a->from, s); in pull()
1624 cparc(nfa, a, s, to); in pull()
1625 freearc(nfa, a); in pull()
1634 moveins(nfa, from, to); in pull()
1635 freearc(nfa, con); in pull()
1644 pushfwd(struct nfa *nfa, in pushfwd() argument
1658 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) in pushfwd()
1666 if (push(nfa, a, &intermediates)) in pushfwd()
1679 dropstate(nfa, s); in pushfwd()
1682 dumpnfa(nfa, f); in pushfwd()
1693 for (a = nfa->post->ins; a != NULL; a = nexta) in pushfwd()
1699 newarc(nfa, PLAIN, nfa->eos[a->co], a->from, a->to); in pushfwd()
1700 freearc(nfa, a); in pushfwd()
1724 push(struct nfa *nfa, in push() argument
1739 freearc(nfa, con); in push()
1750 s = newstate(nfa); in push()
1753 copyouts(nfa, to, s); /* duplicate outarcs */ in push()
1754 cparc(nfa, con, from, s); /* move constraint arc */ in push()
1755 freearc(nfa, con); in push()
1770 freearc(nfa, a); in push()
1784 s = newstate(nfa); in push()
1790 cparc(nfa, con, s, a->to); in push()
1791 cparc(nfa, a, from, s); in push()
1792 freearc(nfa, a); in push()
1801 moveouts(nfa, to, from); in push()
1802 freearc(nfa, con); in push()
1869 fixempties(struct nfa *nfa, in fixempties() argument
1889 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) in fixempties()
1899 moveins(nfa, s, a->to); in fixempties()
1900 dropstate(nfa, s); in fixempties()
1907 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) in fixempties()
1919 moveouts(nfa, s, a->from); in fixempties()
1920 dropstate(nfa, s); in fixempties()
1979 inarcsorig = (struct arc **) MALLOC(nfa->nstates * sizeof(struct arc *)); in fixempties()
1986 for (s = nfa->states; s != NULL; s = s->next) in fixempties()
2007 for (s = nfa->states; s != NULL && !NISERR(); s = s->next) in fixempties()
2015 for (s2 = emptyreachable(nfa, s, s, inarcsorig); s2 != s; s2 = nexts) in fixempties()
2035 mergeins(nfa, s, arcarray, arccount); in fixempties()
2054 for (s = nfa->states; s != NULL; s = s->next) in fixempties()
2060 freearc(nfa, a); in fixempties()
2069 for (s = nfa->states; s != NULL; s = nexts) in fixempties()
2073 dropstate(nfa, s); in fixempties()
2077 dumpnfa(nfa, f); in fixempties()
2096 emptyreachable(struct nfa *nfa, in emptyreachable() argument
2104 if (STACK_TOO_DEEP(nfa->v->re)) in emptyreachable()
2115 lastfound = emptyreachable(nfa, a->from, lastfound, inarcsorig); in emptyreachable()
2163 fixconstraintloops(struct nfa *nfa, in fixconstraintloops() argument
2179 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) in fixconstraintloops()
2190 freearc(nfa, a); in fixconstraintloops()
2197 dropstate(nfa, s); in fixconstraintloops()
2212 for (s = nfa->states; s != NULL && !NISERR(); s = s->next) in fixconstraintloops()
2214 if (findconstraintloop(nfa, s)) in fixconstraintloops()
2230 for (s = nfa->states; s != NULL; s = nexts) in fixconstraintloops()
2235 dropstate(nfa, s); in fixconstraintloops()
2239 dumpnfa(nfa, f); in fixconstraintloops()
2262 findconstraintloop(struct nfa *nfa, struct state *s) in findconstraintloop() argument
2267 if (STACK_TOO_DEEP(nfa->v->re)) in findconstraintloop()
2279 breakconstraintloop(nfa, s); in findconstraintloop()
2291 if (findconstraintloop(nfa, sto)) in findconstraintloop()
2351 breakconstraintloop(struct nfa *nfa, struct state *sinitial) in breakconstraintloop() argument
2412 for (s = nfa->states; s != NULL; s = s->next) in breakconstraintloop()
2418 sclone = newstate(nfa); in breakconstraintloop()
2425 clonesuccessorstates(nfa, stail, sclone, shead, refarc, in breakconstraintloop()
2426 NULL, NULL, nfa->nstates); in breakconstraintloop()
2438 freestate(nfa, sclone); in breakconstraintloop()
2452 cparc(nfa, a, shead, sclone); in breakconstraintloop()
2453 freearc(nfa, a); in breakconstraintloop()
2497 clonesuccessorstates(struct nfa *nfa, in clonesuccessorstates() argument
2510 if (STACK_TOO_DEEP(nfa->v->re)) in clonesuccessorstates()
2641 dropstate(nfa, prevclone); /* kills our outarc, too */ in clonesuccessorstates()
2644 clonesuccessorstates(nfa, in clonesuccessorstates()
2661 cparc(nfa, a, sclone, prevclone); in clonesuccessorstates()
2670 stoclone = newstate(nfa); in clonesuccessorstates()
2679 cparc(nfa, a, sclone, stoclone); in clonesuccessorstates()
2688 cparc(nfa, a, sclone, sto); in clonesuccessorstates()
2709 clonesuccessorstates(nfa, in clonesuccessorstates()
2729 cleanup(struct nfa *nfa) in cleanup() argument
2740 markreachable(nfa, nfa->pre, (struct state *) NULL, nfa->pre); in cleanup()
2741 markcanreach(nfa, nfa->post, nfa->pre, nfa->post); in cleanup()
2742 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) in cleanup()
2745 if (s->tmp != nfa->post && !s->flag) in cleanup()
2746 dropstate(nfa, s); in cleanup()
2748 assert(NISERR() || nfa->post->nins == 0 || nfa->post->tmp == nfa->post); in cleanup()
2749 cleartraverse(nfa, nfa->pre); in cleanup()
2750 assert(NISERR() || nfa->post->nins == 0 || nfa->post->tmp == NULL); in cleanup()
2755 for (s = nfa->states; s != NULL; s = s->next) in cleanup()
2757 nfa->nstates = n; in cleanup()
2764 markreachable(struct nfa *nfa, in markreachable() argument
2772 if (STACK_TOO_DEEP(nfa->v->re)) in markreachable()
2783 markreachable(nfa, a->to, okay, mark); in markreachable()
2790 markcanreach(struct nfa *nfa, in markcanreach() argument
2798 if (STACK_TOO_DEEP(nfa->v->re)) in markcanreach()
2809 markcanreach(nfa, a->from, okay, mark); in markcanreach()
2816 analyze(struct nfa *nfa) in analyze() argument
2824 if (nfa->pre->outs == NULL) in analyze()
2826 for (a = nfa->pre->outs; a != NULL; a = a->outchain) in analyze()
2828 if (aa->to == nfa->post) in analyze()
2837 compact(struct nfa *nfa, in compact() argument
2851 for (s = nfa->states; s != NULL; s = s->next) in compact()
2872 cnfa->pre = nfa->pre->no; in compact()
2873 cnfa->post = nfa->post->no; in compact()
2874 cnfa->bos[0] = nfa->bos[0]; in compact()
2875 cnfa->bos[1] = nfa->bos[1]; in compact()
2876 cnfa->eos[0] = nfa->eos[0]; in compact()
2877 cnfa->eos[1] = nfa->eos[1]; in compact()
2878 cnfa->ncolors = maxcolor(nfa->cm) + 1; in compact()
2882 for (s = nfa->states; s != NULL; s = s->next) in compact()
2916 for (a = nfa->pre->outs; a != NULL; a = a->outchain) in compact()
2918 cnfa->stflags[nfa->pre->no] = CNFA_NOPROGRESS; in compact()
2965 dumpnfa(struct nfa *nfa, in dumpnfa() argument
2973 fprintf(f, "pre %d, post %d", nfa->pre->no, nfa->post->no); in dumpnfa()
2974 if (nfa->bos[0] != COLORLESS) in dumpnfa()
2975 fprintf(f, ", bos [%ld]", (long) nfa->bos[0]); in dumpnfa()
2976 if (nfa->bos[1] != COLORLESS) in dumpnfa()
2977 fprintf(f, ", bol [%ld]", (long) nfa->bos[1]); in dumpnfa()
2978 if (nfa->eos[0] != COLORLESS) in dumpnfa()
2979 fprintf(f, ", eos [%ld]", (long) nfa->eos[0]); in dumpnfa()
2980 if (nfa->eos[1] != COLORLESS) in dumpnfa()
2981 fprintf(f, ", eol [%ld]", (long) nfa->eos[1]); in dumpnfa()
2983 for (s = nfa->states; s != NULL; s = s->next) in dumpnfa()
2990 if (nfa->parent == NULL) in dumpnfa()
2991 dumpcolors(nfa->cm, f); in dumpnfa()