diff options
Diffstat (limited to 'generic/regc_nfa.c')
-rw-r--r-- | generic/regc_nfa.c | 211 |
1 files changed, 85 insertions, 126 deletions
diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c index d155b23..088c6c0 100644 --- a/generic/regc_nfa.c +++ b/generic/regc_nfa.c @@ -62,7 +62,6 @@ newnfa( nfa->nstates = 0; nfa->cm = cm; nfa->v = v; - nfa->size = 0; nfa->bos[0] = nfa->bos[1] = COLORLESS; nfa->eos[0] = nfa->eos[1] = COLORLESS; nfa->parent = parent; /* Precedes newfstate so parent is valid. */ @@ -90,63 +89,8 @@ newnfa( } /* - - TooManyStates - checks if the max states exceeds the compile-time value - ^ static int TooManyStates(struct nfa *); - */ -static int -TooManyStates( - struct nfa *nfa) -{ - struct nfa *parent = nfa->parent; - size_t sz = nfa->size; - - while (parent != NULL) { - sz = parent->size; - parent = parent->parent; - } - if (sz > REG_MAX_STATES) { - return 1; - } - return 0; -} - -/* - - IncrementSize - increases the tracked size of the NFA and its parents. - ^ static void IncrementSize(struct nfa *); - */ -static void -IncrementSize( - struct nfa *nfa) -{ - struct nfa *parent = nfa->parent; - - nfa->size++; - while (parent != NULL) { - parent->size++; - parent = parent->parent; - } -} - -/* - - DecrementSize - increases the tracked size of the NFA and its parents. - ^ static void DecrementSize(struct nfa *); - */ -static void -DecrementSize( - struct nfa *nfa) -{ - struct nfa *parent = nfa->parent; - - nfa->size--; - while (parent != NULL) { - parent->size--; - parent = parent->parent; - } -} - -/* - freenfa - free an entire NFA - ^ static VOID freenfa(struct nfa *); + ^ static void freenfa(struct nfa *); */ static void freenfa( @@ -180,20 +124,20 @@ newstate( { struct state *s; - if (TooManyStates(nfa)) { - /* XXX: add specific error for this */ - NERR(REG_ETOOBIG); - return NULL; - } if (nfa->free != NULL) { s = nfa->free; nfa->free = s->next; } else { + if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE) { + NERR(REG_ETOOBIG); + return NULL; + } s = (struct state *) MALLOC(sizeof(struct state)); if (s == NULL) { NERR(REG_ESPACE); return NULL; } + nfa->v->spaceused += sizeof(struct state); s->oas.next = NULL; s->free = NULL; s->noas = 0; @@ -217,12 +161,6 @@ newstate( } s->prev = nfa->slast; nfa->slast = s; - - /* - * Track the current size and the parent size. - */ - - IncrementSize(nfa); return s; } @@ -246,7 +184,7 @@ newfstate( /* - dropstate - delete a state's inarcs and outarcs and free it - ^ static VOID dropstate(struct nfa *, struct state *); + ^ static void dropstate(struct nfa *, struct state *); */ static void dropstate( @@ -266,7 +204,7 @@ dropstate( /* - freestate - free a state, which has no in-arcs or out-arcs - ^ static VOID freestate(struct nfa *, struct state *); + ^ static void freestate(struct nfa *, struct state *); */ static void freestate( @@ -293,12 +231,11 @@ freestate( s->prev = NULL; s->next = nfa->free; /* don't delete it, put it on the free list */ nfa->free = s; - DecrementSize(nfa); } /* - destroystate - really get rid of an already-freed state - ^ static VOID destroystate(struct nfa *, struct state *); + ^ static void destroystate(struct nfa *, struct state *); */ static void destroystate( @@ -312,16 +249,18 @@ destroystate( for (ab=s->oas.next ; ab!=NULL ; ab=abnext) { abnext = ab->next; FREE(ab); + nfa->v->spaceused -= sizeof(struct arcbatch); } s->ins = NULL; s->outs = NULL; s->next = NULL; FREE(s); + nfa->v->spaceused -= sizeof(struct state); } /* - newarc - set up a new arc within an NFA - ^ static VOID newarc(struct nfa *, int, pcolor, struct state *, + ^ static void newarc(struct nfa *, int, pcolor, struct state *, ^ struct state *); */ /* @@ -354,7 +293,7 @@ newarc( } } } - + /* no dup, so create the arc */ createarc(nfa, t, co, from, to); } @@ -439,14 +378,19 @@ allocarc( */ if (s->free == NULL) { - struct arcbatch *newAb = (struct arcbatch *) - MALLOC(sizeof(struct arcbatch)); + struct arcbatch *newAb; int i; + if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE) { + NERR(REG_ETOOBIG); + return NULL; + } + newAb = (struct arcbatch *) MALLOC(sizeof(struct arcbatch)); if (newAb == NULL) { NERR(REG_ESPACE); return NULL; } + nfa->v->spaceused += sizeof(struct arcbatch); newAb->next = s->oas.next; s->oas.next = newAb; @@ -466,7 +410,7 @@ allocarc( /* - freearc - free an arc - ^ static VOID freearc(struct nfa *, struct arc *); + ^ static void freearc(struct nfa *, struct arc *); */ static void freearc( @@ -625,7 +569,7 @@ findarc( /* - cparc - allocate a new arc within an NFA, copying details from old one - ^ static VOID cparc(struct nfa *, struct arc *, struct state *, + ^ static void cparc(struct nfa *, struct arc *, struct state *, ^ struct state *); */ static void @@ -713,7 +657,7 @@ sortins_cmp( } return 0; } - + /* * sortouts - sort the out arcs of a state by to/color/type */ @@ -812,7 +756,7 @@ sortouts_cmp( * checks become too slow. In that case we proceed by sorting and merging * the arc lists, and then we can indeed just update the arcs in-place. * - ^ static VOID moveins(struct nfa *, struct state *, struct state *); + ^ static void moveins(struct nfa *, struct state *, struct state *); */ static void moveins( @@ -1072,7 +1016,7 @@ mergeins( /* - moveouts - move all out arcs of a state to another state - ^ static VOID moveouts(struct nfa *, struct state *, struct state *); + ^ static void moveouts(struct nfa *, struct state *, struct state *); */ static void moveouts( @@ -1232,7 +1176,7 @@ copyouts( /* - cloneouts - copy out arcs of a state to another state pair, modifying type - ^ static VOID cloneouts(struct nfa *, struct state *, struct state *, + ^ static void cloneouts(struct nfa *, struct state *, struct state *, ^ struct state *, int); */ static void @@ -1256,7 +1200,7 @@ cloneouts( - delsub - delete a sub-NFA, updating subre pointers if necessary * This uses a recursive traversal of the sub-NFA, marking already-seen * states using their tmp pointer. - ^ static VOID delsub(struct nfa *, struct state *, struct state *); + ^ static void delsub(struct nfa *, struct state *, struct state *); */ static void delsub( @@ -1279,7 +1223,7 @@ delsub( /* - deltraverse - the recursive heart of delsub * This routine's basic job is to destroy all out-arcs of the state. - ^ static VOID deltraverse(struct nfa *, struct state *, struct state *); + ^ static void deltraverse(struct nfa *, struct state *, struct state *); */ static void deltraverse( @@ -1322,7 +1266,7 @@ deltraverse( * Another recursive traversal, this time using tmp to point to duplicates as * well as mark already-seen states. (You knew there was a reason why it's a * state pointer, didn't you? :-)) - ^ static VOID dupnfa(struct nfa *, struct state *, struct state *, + ^ static void dupnfa(struct nfa *, struct state *, struct state *, ^ struct state *, struct state *); */ static void @@ -1339,7 +1283,7 @@ dupnfa( } stop->tmp = to; - duptraverse(nfa, start, from); + duptraverse(nfa, start, from, 0); /* done, except for clearing out the tmp pointers */ stop->tmp = NULL; @@ -1348,13 +1292,14 @@ dupnfa( /* - duptraverse - recursive heart of dupnfa - ^ static VOID duptraverse(struct nfa *, struct state *, struct state *); + ^ static void duptraverse(struct nfa *, struct state *, struct state *); */ static void duptraverse( struct nfa *nfa, struct state *s, - struct state *stmp) /* s's duplicate, or NULL */ + struct state *stmp, /* s's duplicate, or NULL */ + int depth) { struct arc *a; @@ -1368,8 +1313,20 @@ duptraverse( return; } + /* + * Arbitrary depth limit. Needs tuning, but this value is sufficient to + * make all normal tests (not reg-33.14) pass. + */ +#ifndef DUPTRAVERSE_MAX_DEPTH +#define DUPTRAVERSE_MAX_DEPTH 15000 +#endif + + if (depth++ > DUPTRAVERSE_MAX_DEPTH) { + NERR(REG_ESPACE); + } + for (a=s->outs ; a!=NULL && !NISERR() ; a=a->outchain) { - duptraverse(nfa, a->to, NULL); + duptraverse(nfa, a->to, NULL, depth); if (NISERR()) { break; } @@ -1380,7 +1337,7 @@ duptraverse( /* - cleartraverse - recursive cleanup for algorithms that leave tmp ptrs set - ^ static VOID cleartraverse(struct nfa *, struct state *); + ^ static void cleartraverse(struct nfa *, struct state *); */ static void cleartraverse( @@ -1401,7 +1358,7 @@ cleartraverse( /* - specialcolors - fill in special colors for an NFA - ^ static VOID specialcolors(struct nfa *); + ^ static void specialcolors(struct nfa *); */ static void specialcolors( @@ -1484,7 +1441,7 @@ optimize( /* - pullback - pull back constraints backward to eliminate them - ^ static VOID pullback(struct nfa *, FILE *); + ^ static void pullback(struct nfa *, FILE *); */ static void pullback( @@ -1664,7 +1621,7 @@ pull( /* - pushfwd - push forward constraints forward to eliminate them - ^ static VOID pushfwd(struct nfa *, FILE *); + ^ static void pushfwd(struct nfa *, FILE *); */ static void pushfwd( @@ -1903,7 +1860,7 @@ combine( /* - fixempties - get rid of EMPTY arcs - ^ static VOID fixempties(struct nfa *, FILE *); + ^ static void fixempties(struct nfa *, FILE *); */ static void fixempties( @@ -2063,7 +2020,7 @@ fixempties( arcarray[arccount++] = a; } } - + /* Reset the tmp fields as we walk back */ nexts = s2->tmp; s2->tmp = NULL; @@ -2085,7 +2042,7 @@ fixempties( } inarcsorig[s->no] = a; } - + FREE(arcarray); FREE(inarcsorig); @@ -2236,7 +2193,7 @@ fixconstraintloops( dropstate(nfa, s); } } - + /* Nothing to do if no remaining constraint arcs */ if (NISERR() || !hasconstraints) { return; @@ -2726,7 +2683,7 @@ clonesuccessorstates( /* - cleanup - clean up NFA after optimizations - ^ static VOID cleanup(struct nfa *); + ^ static void cleanup(struct nfa *); */ static void cleanup( @@ -2767,7 +2724,7 @@ cleanup( /* - markreachable - recursive marking of reachable states - ^ static VOID markreachable(struct nfa *, struct state *, struct state *, + ^ static void markreachable(struct nfa *, struct state *, struct state *, ^ struct state *); */ static void @@ -2791,7 +2748,7 @@ markreachable( /* - markcanreach - recursive marking of states which can reach here - ^ static VOID markcanreach(struct nfa *, struct state *, struct state *, + ^ static void markcanreach(struct nfa *, struct state *, struct state *, ^ struct state *); */ static void @@ -2839,7 +2796,7 @@ analyze( /* - compact - construct the compact representation of an NFA - ^ static VOID compact(struct nfa *, struct cnfa *); + ^ static void compact(struct nfa *, struct cnfa *); */ static void compact( @@ -2859,13 +2816,16 @@ compact( narcs = 0; for (s = nfa->states; s != NULL; s = s->next) { nstates++; - narcs += 1 + s->nouts + 1; - /* 1 as a fake for flags, nouts for arcs, 1 as endmarker */ + narcs += s->nouts + 1; /* need one extra for endmarker */ } + cnfa->stflags = (char *) MALLOC(nstates * sizeof(char)); cnfa->states = (struct carc **) MALLOC(nstates * sizeof(struct carc *)); cnfa->arcs = (struct carc *) MALLOC(narcs * sizeof(struct carc)); - if (cnfa->states == NULL || cnfa->arcs == NULL) { + if (cnfa->stflags == NULL || cnfa->states == NULL || cnfa->arcs == NULL) { + if (cnfa->stflags != NULL) { + FREE(cnfa->stflags); + } if (cnfa->states != NULL) { FREE(cnfa->states); } @@ -2888,9 +2848,8 @@ compact( ca = cnfa->arcs; for (s = nfa->states; s != NULL; s = s->next) { assert((size_t) s->no < nstates); + cnfa->stflags[s->no] = 0; cnfa->states[s->no] = ca; - ca->co = 0; /* clear and skip flags "arc" */ - ca++; first = ca; for (a = s->outs; a != NULL; a = a->outchain) { switch (a->type) { @@ -2924,14 +2883,14 @@ compact( */ for (a = nfa->pre->outs; a != NULL; a = a->outchain) { - cnfa->states[a->to->no]->co = 1; + cnfa->stflags[a->to->no] = CNFA_NOPROGRESS; } - cnfa->states[nfa->pre->no]->co = 1; + cnfa->stflags[nfa->pre->no] = CNFA_NOPROGRESS; } /* - carcsort - sort compacted-NFA arcs by color - ^ static VOID carcsort(struct carc *, struct carc *); + ^ static void carcsort(struct carc *, struct carc *); */ static void carcsort( @@ -2950,7 +2909,7 @@ carc_cmp( { const struct carc *aa = (const struct carc *) a; const struct carc *bb = (const struct carc *) b; - + if (aa->co < bb->co) { return -1; } @@ -2968,7 +2927,7 @@ carc_cmp( /* - freecnfa - free a compacted NFA - ^ static VOID freecnfa(struct cnfa *); + ^ static void freecnfa(struct cnfa *); */ static void freecnfa( @@ -2976,13 +2935,14 @@ freecnfa( { assert(cnfa->nstates != 0); /* not empty already */ cnfa->nstates = 0; + FREE(cnfa->stflags); FREE(cnfa->states); FREE(cnfa->arcs); } /* - dumpnfa - dump an NFA in human-readable form - ^ static VOID dumpnfa(struct nfa *, FILE *); + ^ static void dumpnfa(struct nfa *, FILE *); */ static void dumpnfa( @@ -3028,7 +2988,7 @@ dumpnfa( /* - dumpstate - dump an NFA state in human-readable form - ^ static VOID dumpstate(struct state *, FILE *); + ^ static void dumpstate(struct state *, FILE *); */ static void dumpstate( @@ -3058,7 +3018,7 @@ dumpstate( /* - dumparcs - dump out-arcs in human-readable form - ^ static VOID dumparcs(struct state *, FILE *); + ^ static void dumparcs(struct state *, FILE *); */ static void dumparcs( @@ -3092,7 +3052,7 @@ dumparcs( /* - dumparc - dump one outarc in readable form, including prefixing tab - ^ static VOID dumparc(struct arc *, struct state *, FILE *); + ^ static void dumparc(struct arc *, struct state *, FILE *); */ static void dumparc( @@ -3166,7 +3126,7 @@ dumparc( /* - dumpcnfa - dump a compacted NFA in human-readable form - ^ static VOID dumpcnfa(struct cnfa *, FILE *); + ^ static void dumpcnfa(struct cnfa *, FILE *); */ static void dumpcnfa( @@ -3194,7 +3154,7 @@ dumpcnfa( } fprintf(f, "\n"); for (st = 0; st < cnfa->nstates; st++) { - dumpcstate(st, cnfa->states[st], cnfa, f); + dumpcstate(st, cnfa, f); } fflush(f); #endif @@ -3207,25 +3167,24 @@ dumpcnfa( /* - dumpcstate - dump a compacted-NFA state in human-readable form - ^ static VOID dumpcstate(int, struct carc *, struct cnfa *, FILE *); + ^ static void dumpcstate(int, struct cnfa *, FILE *); */ static void dumpcstate( int st, - struct carc *ca, struct cnfa *cnfa, FILE *f) { - int i; + struct carc *ca; int pos; - fprintf(f, "%d%s", st, (ca[0].co) ? ":" : "."); + fprintf(f, "%d%s", st, (cnfa->stflags[st] & CNFA_NOPROGRESS) ? ":" : "."); pos = 1; - for (i = 1; ca[i].co != COLORLESS; i++) { - if (ca[i].co < cnfa->ncolors) { - fprintf(f, "\t[%ld]->%d", (long) ca[i].co, ca[i].to); + for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++) { + if (ca->co < cnfa->ncolors) { + fprintf(f, "\t[%ld]->%d", (long) ca->co, ca->to); } else { - fprintf(f, "\t:%ld:->%d", (long) ca[i].co-cnfa->ncolors,ca[i].to); + fprintf(f, "\t:%ld:->%d", (long) (ca->co - cnfa->ncolors), ca->to); } if (pos == 5) { fprintf(f, "\n"); @@ -3234,7 +3193,7 @@ dumpcstate( pos++; } } - if (i == 1 || pos != 1) { + if (ca == cnfa->states[st] || pos != 1) { fprintf(f, "\n"); } fflush(f); |