summaryrefslogtreecommitdiffstats
path: root/generic/regc_nfa.c
diff options
context:
space:
mode:
Diffstat (limited to 'generic/regc_nfa.c')
-rw-r--r--generic/regc_nfa.c115
1 files changed, 65 insertions, 50 deletions
diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c
index 6280e5e..0e0343e 100644
--- a/generic/regc_nfa.c
+++ b/generic/regc_nfa.c
@@ -90,7 +90,7 @@ newnfa(
/*
- freenfa - free an entire NFA
- ^ static VOID freenfa(struct nfa *);
+ ^ static void freenfa(struct nfa *);
*/
static void
freenfa(
@@ -184,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(
@@ -204,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(
@@ -235,7 +235,7 @@ freestate(
/*
- 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(
@@ -260,7 +260,7 @@ destroystate(
/*
- 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 *);
*/
/*
@@ -410,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(
@@ -569,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
@@ -756,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(
@@ -1016,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(
@@ -1176,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
@@ -1200,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(
@@ -1223,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(
@@ -1266,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
@@ -1283,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;
@@ -1292,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;
@@ -1312,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;
}
@@ -1324,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(
@@ -1345,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(
@@ -1428,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(
@@ -1608,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(
@@ -1847,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(
@@ -2670,7 +2683,7 @@ clonesuccessorstates(
/*
- cleanup - clean up NFA after optimizations
- ^ static VOID cleanup(struct nfa *);
+ ^ static void cleanup(struct nfa *);
*/
static void
cleanup(
@@ -2711,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
@@ -2735,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
@@ -2783,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(
@@ -2803,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);
}
@@ -2832,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) {
@@ -2868,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(
@@ -2912,7 +2927,7 @@ carc_cmp(
/*
- freecnfa - free a compacted NFA
- ^ static VOID freecnfa(struct cnfa *);
+ ^ static void freecnfa(struct cnfa *);
*/
static void
freecnfa(
@@ -2920,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(
@@ -2972,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(
@@ -3002,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(
@@ -3036,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(
@@ -3110,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(
@@ -3138,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
@@ -3151,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");
@@ -3178,7 +3193,7 @@ dumpcstate(
pos++;
}
}
- if (i == 1 || pos != 1) {
+ if (ca == cnfa->states[st] || pos != 1) {
fprintf(f, "\n");
}
fflush(f);