#define NISERR() VISERR(nfa->v)
#define NERR(e) VERR(nfa->v, (e))
static struct nfa *
newnfa(v, cm, parent)
struct vars *v;
struct colormap *cm;
struct nfa *parent;
{
struct nfa *nfa;
nfa = (struct nfa *)MALLOC(sizeof(struct nfa));
if (nfa == NULL)
return NULL;
nfa->states = NULL;
nfa->slast = NULL;
nfa->free = NULL;
nfa->nstates = 0;
nfa->cm = cm;
nfa->v = v;
nfa->bos[0] = nfa->bos[1] = COLORLESS;
nfa->eos[0] = nfa->eos[1] = COLORLESS;
nfa->post = newfstate(nfa, '@');
nfa->pre = newfstate(nfa, '>');
nfa->parent = parent;
nfa->init = newstate(nfa);
nfa->final = newstate(nfa);
if (ISERR()) {
freenfa(nfa);
return NULL;
}
rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->pre, nfa->init);
newarc(nfa, '^', 1, nfa->pre, nfa->init);
newarc(nfa, '^', 0, nfa->pre, nfa->init);
rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->final, nfa->post);
newarc(nfa, '$', 1, nfa->final, nfa->post);
newarc(nfa, '$', 0, nfa->final, nfa->post);
if (ISERR()) {
freenfa(nfa);
return NULL;
}
return nfa;
}
static VOID
freenfa(nfa)
struct nfa *nfa;
{
struct state *s;
while ((s = nfa->states) != NULL) {
s->nins = s->nouts = 0;
freestate(nfa, s);
}
while ((s = nfa->free) != NULL) {
nfa->free = s->next;
destroystate(nfa, s);
}
nfa->slast = NULL;
nfa->nstates = -1;
nfa->pre = NULL;
nfa->post = NULL;
FREE(nfa);
}
static struct state *
newstate(nfa)
struct nfa *nfa;
{
struct state *s;
if (nfa->free != NULL) {
s = nfa->free;
nfa->free = s->next;
} else {
s = (struct state *)MALLOC(sizeof(struct state));
if (s == NULL) {
NERR(REG_ESPACE);
return NULL;
}
s->oas.next = NULL;
s->free = NULL;
s->noas = 0;
}
assert(nfa->nstates >= 0);
s->no = nfa->nstates++;
s->flag = 0;
if (nfa->states == NULL)
nfa->states = s;
s->nins = 0;
s->ins = NULL;
s->nouts = 0;
s->outs = NULL;
s->tmp = NULL;
s->next = NULL;
if (nfa->slast != NULL) {
assert(nfa->slast->next == NULL);
nfa->slast->next = s;
}
s->prev = nfa->slast;
nfa->slast = s;
return s;
}
static struct state *
newfstate(nfa, flag)
struct nfa *nfa;
int flag;
{
struct state *s;
s = newstate(nfa);
if (s != NULL)
s->flag = (char)flag;
return s;
}
static VOID
dropstate(nfa, s)
struct nfa *nfa;
struct state *s;
{
struct arc *a;
while ((a = s->ins) != NULL)
freearc(nfa, a);
while ((a = s->outs) != NULL)
freearc(nfa, a);
freestate(nfa, s);
}
static VOID
freestate(nfa, s)
struct nfa *nfa;
struct state *s;
{
assert(s != NULL);
assert(s->nins == 0 && s->nouts == 0);
s->no = FREESTATE;
s->flag = 0;
if (s->next != NULL)
s->next->prev = s->prev;
else {
assert(s == nfa->slast);
nfa->slast = s->prev;
}
if (s->prev != NULL)
s->prev->next = s->next;
else {
assert(s == nfa->states);
nfa->states = s->next;
}
s->prev = NULL;
s->next = nfa->free;
nfa->free = s;
}
static VOID
destroystate(nfa, s)
struct nfa *nfa;
struct state *s;
{
struct arcbatch *ab;
struct arcbatch *abnext;
assert(s->no == FREESTATE);
for (ab = s->oas.next; ab != NULL; ab = abnext) {
abnext = ab->next;
FREE(ab);
}
s->ins = NULL;
s->outs = NULL;
s->next = NULL;
FREE(s);
}
static VOID
newarc(nfa, t, co, from, to)
struct nfa *nfa;
int t;
pcolor co;
struct state *from;
struct state *to;
{
struct arc *a;
assert(from != NULL && to != NULL);
for (a = from->outs; a != NULL; a = a->outchain)
if (a->to == to && a->co == co && a->type == t)
return;
a = allocarc(nfa, from);
if (NISERR())
return;
assert(a != NULL);
a->type = t;
a->co = (color)co;
a->to = to;
a->from = from;
a->inchain = to->ins;
to->ins = a;
a->outchain = from->outs;
from->outs = a;
from->nouts++;
to->nins++;
if (COLORED(a) && nfa->parent == NULL)
colorchain(nfa->cm, a);
return;
}
static struct arc *
allocarc(nfa, s)
struct nfa *nfa;
struct state *s;
{
struct arc *a;
struct arcbatch *new;
int i;
if (s->free == NULL && s->noas < ABSIZE) {
a = &s->oas.a[s->noas];
s->noas++;
return a;
}
if (s->free == NULL) {
new = (struct arcbatch *)MALLOC(sizeof(struct arcbatch));
if (new == NULL) {
NERR(REG_ESPACE);
return NULL;
}
new->next = s->oas.next;
s->oas.next = new;
for (i = 0; i < ABSIZE; i++) {
new->a[i].type = 0;
new->a[i].freechain = &new->a[i+1];
}
new->a[ABSIZE-1].freechain = NULL;
s->free = &new->a[0];
}
assert(s->free != NULL);
a = s->free;
s->free = a->freechain;
return a;
}
static VOID
freearc(nfa, victim)
struct nfa *nfa;
struct arc *victim;
{
struct state *from = victim->from;
struct state *to = victim->to;
struct arc *a;
assert(victim->type != 0);
if (COLORED(victim) && nfa->parent == NULL)
uncolorchain(nfa->cm, victim);
assert(from != NULL);
assert(from->outs != NULL);
a = from->outs;
if (a == victim)
from->outs = victim->outchain;
else {
for (; a != NULL && a->outchain != victim; a = a->outchain)
continue;
assert(a != NULL);
a->outchain = victim->outchain;
}
from->nouts--;
assert(to != NULL);
assert(to->ins != NULL);
a = to->ins;
if (a == victim)
to->ins = victim->inchain;
else {
for (; a != NULL && a->inchain != victim; a = a->inchain)
continue;
assert(a != NULL);
a->inchain = victim->inchain;
}
to->nins--;
victim->type = 0;
victim->from = NULL;
victim->to = NULL;
victim->inchain = NULL;
victim->outchain = NULL;
victim->freechain = from->free;
from->free = victim;
}
static struct arc *
findarc(s, type, co)
struct state *s;
int type;
pcolor co;
{
struct arc *a;
for (a = s->outs; a != NULL; a = a->outchain)
if (a->type == type && a->co == co)
return a;
return NULL;
}
static VOID
cparc(nfa, oa, from, to)
struct nfa *nfa;
struct arc *oa;
struct state *from;
struct state *to;
{
newarc(nfa, oa->type, oa->co, from, to);
}
static VOID
moveins(nfa, old, new)
struct nfa *nfa;
struct state *old;
struct state *new;
{
struct arc *a;
assert(old != new);
while ((a = old->ins) != NULL) {
cparc(nfa, a, a->from, new);
freearc(nfa, a);
}
assert(old->nins == 0);
assert(old->ins == NULL);
}
static VOID
copyins(nfa, old, new)
struct nfa *nfa;
struct state *old;
struct state *new;
{
struct arc *a;
assert(old != new);
for (a = old->ins; a != NULL; a = a->inchain)
cparc(nfa, a, a->from, new);
}
static VOID
moveouts(nfa, old, new)
struct nfa *nfa;
struct state *old;
struct state *new;
{
struct arc *a;
assert(old != new);
while ((a = old->outs) != NULL) {
cparc(nfa, a, new, a->to);
freearc(nfa, a);
}
}
static VOID
copyouts(nfa, old, new)
struct nfa *nfa;
struct state *old;
struct state *new;
{
struct arc *a;
assert(old != new);
for (a = old->outs; a != NULL; a = a->outchain)
cparc(nfa, a, new, a->to);
}
static VOID
cloneouts(nfa, old, from, to, type)
struct nfa *nfa;
struct state *old;
struct state *from;
struct state *to;
int type;
{
struct arc *a;
assert(old != from);
for (a = old->outs; a != NULL; a = a->outchain)
newarc(nfa, type, a->co, from, to);
}
static VOID
delsub(nfa, lp, rp)
struct nfa *nfa;
struct state *lp;
struct state *rp;
{
assert(lp != rp);
rp->tmp = rp;
deltraverse(nfa, lp, lp);
assert(lp->nouts == 0 && rp->nins == 0);
assert(lp->no != FREESTATE && rp->no != FREESTATE);
rp->tmp = NULL;
lp->tmp = NULL;
}
static VOID
deltraverse(nfa, leftend, s)
struct nfa *nfa;
struct state *leftend;
struct state *s;
{
struct arc *a;
struct state *to;
if (s->nouts == 0)
return;
if (s->tmp != NULL)
return;
s->tmp = s;
while ((a = s->outs) != NULL) {
to = a->to;
deltraverse(nfa, leftend, to);
assert(to->nouts == 0 || to->tmp != NULL);
freearc(nfa, a);
if (to->nins == 0 && to->tmp == NULL) {
assert(to->nouts == 0);
freestate(nfa, to);
}
}
assert(s->no != FREESTATE);
assert(s == leftend || s->nins != 0);
assert(s->nouts == 0);
s->tmp = NULL;
}
static VOID
dupnfa(nfa, start, stop, from, to)
struct nfa *nfa;
struct state *start;
struct state *stop;
struct state *from;
struct state *to;
{
if (start == stop) {
newarc(nfa, EMPTY, 0, from, to);
return;
}
stop->tmp = to;
duptraverse(nfa, start, from);
stop->tmp = NULL;
cleartraverse(nfa, start);
}
static VOID
duptraverse(nfa, s, stmp)
struct nfa *nfa;
struct state *s;
struct state *stmp;
{
struct arc *a;
if (s->tmp != NULL)
return;
s->tmp = (stmp == NULL) ? newstate(nfa) : stmp;
if (s->tmp == NULL) {
assert(NISERR());
return;
}
for (a = s->outs; a != NULL && !NISERR(); a = a->outchain) {
duptraverse(nfa, a->to, (struct state *)NULL);
assert(a->to->tmp != NULL);
cparc(nfa, a, s->tmp, a->to->tmp);
}
}
static VOID
cleartraverse(nfa, s)
struct nfa *nfa;
struct state *s;
{
struct arc *a;
if (s->tmp == NULL)
return;
s->tmp = NULL;
for (a = s->outs; a != NULL; a = a->outchain)
cleartraverse(nfa, a->to);
}
static VOID
specialcolors(nfa)
struct nfa *nfa;
{
if (nfa->parent == NULL) {
nfa->bos[0] = pseudocolor(nfa->cm);
nfa->bos[1] = pseudocolor(nfa->cm);
nfa->eos[0] = pseudocolor(nfa->cm);
nfa->eos[1] = pseudocolor(nfa->cm);
} else {
assert(nfa->parent->bos[0] != COLORLESS);
nfa->bos[0] = nfa->parent->bos[0];
assert(nfa->parent->bos[1] != COLORLESS);
nfa->bos[1] = nfa->parent->bos[1];
assert(nfa->parent->eos[0] != COLORLESS);
nfa->eos[0] = nfa->parent->eos[0];
assert(nfa->parent->eos[1] != COLORLESS);
nfa->eos[1] = nfa->parent->eos[1];
}
}
static long
optimize(nfa, f)
struct nfa *nfa;
FILE *f;
{
int verbose = (f != NULL) ? 1 : 0;
if (verbose)
fprintf(f, "\ninitial cleanup:\n");
cleanup(nfa);
if (verbose)
dumpnfa(nfa, f);
if (verbose)
fprintf(f, "\nempties:\n");
fixempties(nfa, f);
if (verbose)
fprintf(f, "\nconstraints:\n");
pullback(nfa, f);
pushfwd(nfa, f);
if (verbose)
fprintf(f, "\nfinal cleanup:\n");
cleanup(nfa);
return analyze(nfa);
}
static VOID
pullback(nfa, f)
struct nfa *nfa;
FILE *f;
{
struct state *s;
struct state *nexts;
struct arc *a;
struct arc *nexta;
int progress;
do {
progress = 0;
for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
nexts = s->next;
for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
nexta = a->outchain;
if (a->type == '^' || a->type == BEHIND)
if (pull(nfa, a))
progress = 1;
assert(nexta == NULL || s->no != FREESTATE);
}
}
if (progress && f != NULL)
dumpnfa(nfa, f);
} while (progress && !NISERR());
if (NISERR())
return;
for (a = nfa->pre->outs; a != NULL; a = nexta) {
nexta = a->outchain;
if (a->type == '^') {
assert(a->co == 0 || a->co == 1);
newarc(nfa, PLAIN, nfa->bos[a->co], a->from, a->to);
freearc(nfa, a);
}
}
}
static int
pull(nfa, con)
struct nfa *nfa;
struct arc *con;
{
struct state *from = con->from;
struct state *to = con->to;
struct arc *a;
struct arc *nexta;
struct state *s;
if (from == to) {
freearc(nfa, con);
return 1;
}
if (from->flag)
return 0;
if (from->nins == 0) {
freearc(nfa, con);
return 1;
}
if (from->nouts > 1) {
s = newstate(nfa);
if (NISERR())
return 0;
assert(to != from);
copyins(nfa, from, s);
cparc(nfa, con, s, to);
freearc(nfa, con);
from = s;
con = from->outs;
}
assert(from->nouts == 1);
for (a = from->ins; a != NULL; a = nexta) {
nexta = a->inchain;
switch (combine(con, a)) {
case INCOMPATIBLE:
freearc(nfa, a);
break;
case SATISFIED:
break;
case COMPATIBLE:
s = newstate(nfa);
if (NISERR())
return 0;
cparc(nfa, a, s, to);
cparc(nfa, con, a->from, s);
if (NISERR())
return 0;
freearc(nfa, a);
break;
default:
assert(NOTREACHED);
break;
}
}
moveins(nfa, from, to);
dropstate(nfa, from);
return 1;
}
static VOID
pushfwd(nfa, f)
struct nfa *nfa;
FILE *f;
{
struct state *s;
struct state *nexts;
struct arc *a;
struct arc *nexta;
int progress;
do {
progress = 0;
for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
nexts = s->next;
for (a = s->ins; a != NULL && !NISERR(); a = nexta) {
nexta = a->inchain;
if (a->type == '$' || a->type == AHEAD)
if (push(nfa, a))
progress = 1;
assert(nexta == NULL || s->no != FREESTATE);
}
}
if (progress && f != NULL)
dumpnfa(nfa, f);
} while (progress && !NISERR());
if (NISERR())
return;
for (a = nfa->post->ins; a != NULL; a = nexta) {
nexta = a->inchain;
if (a->type == '$') {
assert(a->co == 0 || a->co == 1);
newarc(nfa, PLAIN, nfa->eos[a->co], a->from, a->to);
freearc(nfa, a);
}
}
}
static int
push(nfa, con)
struct nfa *nfa;
struct arc *con;
{
struct state *from = con->from;
struct state *to = con->to;
struct arc *a;
struct arc *nexta;
struct state *s;
if (to == from) {
freearc(nfa, con);
return 1;
}
if (to->flag)
return 0;
if (to->nouts == 0) {
freearc(nfa, con);
return 1;
}
if (to->nins > 1) {
s = newstate(nfa);
if (NISERR())
return 0;
copyouts(nfa, to, s);
cparc(nfa, con, from, s);
freearc(nfa, con);
to = s;
con = to->ins;
}
assert(to->nins == 1);
for (a = to->outs; a != NULL; a = nexta) {
nexta = a->outchain;
switch (combine(con, a)) {
case INCOMPATIBLE:
freearc(nfa, a);
break;
case SATISFIED:
break;
case COMPATIBLE:
s = newstate(nfa);
if (NISERR())
return 0;
cparc(nfa, con, s, a->to);
cparc(nfa, a, from, s);
if (NISERR())
return 0;
freearc(nfa, a);
break;
default:
assert(NOTREACHED);
break;
}
}
moveouts(nfa, to, from);
dropstate(nfa, to);
return 1;
}
static int
combine(con, a)
struct arc *con;
struct arc *a;
{
# define CA(ct,at) (((ct)<<CHAR_BIT) | (at))
switch (CA(con->type, a->type)) {
case CA('^', PLAIN):
case CA('$', PLAIN):
return INCOMPATIBLE;
break;
case CA(AHEAD, PLAIN):
case CA(BEHIND, PLAIN):
if (con->co == a->co)
return SATISFIED;
return INCOMPATIBLE;
break;
case CA('^', '^'):
case CA('$', '$'):
case CA(AHEAD, AHEAD):
case CA(BEHIND, BEHIND):
if (con->co == a->co)
return SATISFIED;
return INCOMPATIBLE;
break;
case CA('^', BEHIND):
case CA(BEHIND, '^'):
case CA('$', AHEAD):
case CA(AHEAD, '$'):
return INCOMPATIBLE;
break;
case CA('^', '$'):
case CA('^', AHEAD):
case CA(BEHIND, '$'):
case CA(BEHIND, AHEAD):
case CA('$', '^'):
case CA('$', BEHIND):
case CA(AHEAD, '^'):
case CA(AHEAD, BEHIND):
case CA('^', LACON):
case CA(BEHIND, LACON):
case CA('$', LACON):
case CA(AHEAD, LACON):
return COMPATIBLE;
break;
}
assert(NOTREACHED);
return INCOMPATIBLE;
}
static VOID
fixempties(nfa, f)
struct nfa *nfa;
FILE *f;
{
struct state *s;
struct state *nexts;
struct arc *a;
struct arc *nexta;
int progress;
do {
progress = 0;
for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
nexts = s->next;
for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
nexta = a->outchain;
if (a->type == EMPTY && unempty(nfa, a))
progress = 1;
assert(nexta == NULL || s->no != FREESTATE);
}
}
if (progress && f != NULL)
dumpnfa(nfa, f);
} while (progress && !NISERR());
}
static int
unempty(nfa, a)
struct nfa *nfa;
struct arc *a;
{
struct state *from = a->from;
struct state *to = a->to;
int usefrom;
assert(a->type == EMPTY);
assert(from != nfa->pre && to != nfa->post);
if (from == to) {
freearc(nfa, a);
return 1;
}
usefrom = 1;
if (from->nouts > to->nins)
usefrom = 0;
else if (from->nouts == to->nins) {
if (from->nins > to->nouts)
usefrom = 0;
}
freearc(nfa, a);
if (usefrom) {
if (from->nouts == 0) {
moveins(nfa, from, to);
freestate(nfa, from);
} else
copyins(nfa, from, to);
} else {
if (to->nins == 0) {
moveouts(nfa, to, from);
freestate(nfa, to);
} else
copyouts(nfa, to, from);
}
return 1;
}
static VOID
cleanup(nfa)
struct nfa *nfa;
{
struct state *s;
struct state *nexts;
int n;
markreachable(nfa, nfa->pre, (struct state *)NULL, nfa->pre);
markcanreach(nfa, nfa->post, nfa->pre, nfa->post);
for (s = nfa->states; s != NULL; s = nexts) {
nexts = s->next;
if (s->tmp != nfa->post && !s->flag)
dropstate(nfa, s);
}
assert(nfa->post->nins == 0 || nfa->post->tmp == nfa->post);
cleartraverse(nfa, nfa->pre);
assert(nfa->post->nins == 0 || nfa->post->tmp == NULL);
n = 0;
for (s = nfa->states; s != NULL; s = s->next)
s->no = n++;
nfa->nstates = n;
}
static VOID
markreachable(nfa, s, okay, mark)
struct nfa *nfa;
struct state *s;
struct state *okay;
struct state *mark;
{
struct arc *a;
if (s->tmp != okay)
return;
s->tmp = mark;
for (a = s->outs; a != NULL; a = a->outchain)
markreachable(nfa, a->to, okay, mark);
}
static VOID
markcanreach(nfa, s, okay, mark)
struct nfa *nfa;
struct state *s;
struct state *okay;
struct state *mark;
{
struct arc *a;
if (s->tmp != okay)
return;
s->tmp = mark;
for (a = s->ins; a != NULL; a = a->inchain)
markcanreach(nfa, a->from, okay, mark);
}
static long
analyze(nfa)
struct nfa *nfa;
{
struct arc *a;
struct arc *aa;
if (nfa->pre->outs == NULL)
return REG_UIMPOSSIBLE;
for (a = nfa->pre->outs; a != NULL; a = a->outchain)
for (aa = a->to->outs; aa != NULL; aa = aa->outchain)
if (aa->to == nfa->post)
return REG_UEMPTYMATCH;
return 0;
}
static VOID
compact(nfa, cnfa)
struct nfa *nfa;
struct cnfa *cnfa;
{
struct state *s;
struct arc *a;
size_t nstates;
size_t narcs;
struct carc *ca;
struct carc *first;
assert (!NISERR());
nstates = 0;
narcs = 0;
for (s = nfa->states; s != NULL; s = s->next) {
nstates++;
narcs += 1 + s->nouts + 1;
}
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->states != NULL)
FREE(cnfa->states);
if (cnfa->arcs != NULL)
FREE(cnfa->arcs);
NERR(REG_ESPACE);
return;
}
cnfa->nstates = nstates;
cnfa->pre = nfa->pre->no;
cnfa->post = nfa->post->no;
cnfa->bos[0] = nfa->bos[0];
cnfa->bos[1] = nfa->bos[1];
cnfa->eos[0] = nfa->eos[0];
cnfa->eos[1] = nfa->eos[1];
cnfa->ncolors = maxcolor(nfa->cm) + 1;
cnfa->flags = 0;
ca = cnfa->arcs;
for (s = nfa->states; s != NULL; s = s->next) {
assert((size_t)s->no < nstates);
cnfa->states[s->no] = ca;
ca->co = 0;
ca++;
first = ca;
for (a = s->outs; a != NULL; a = a->outchain)
switch (a->type) {
case PLAIN:
ca->co = a->co;
ca->to = a->to->no;
ca++;
break;
case LACON:
assert(s->no != cnfa->pre);
ca->co = (color)(cnfa->ncolors + a->co);
ca->to = a->to->no;
ca++;
cnfa->flags |= HASLACONS;
break;
default:
assert(NOTREACHED);
break;
}
carcsort(first, ca-1);
ca->co = COLORLESS;
ca->to = 0;
ca++;
}
assert(ca == &cnfa->arcs[narcs]);
assert(cnfa->nstates != 0);
for (a = nfa->pre->outs; a != NULL; a = a->outchain)
cnfa->states[a->to->no]->co = 1;
cnfa->states[nfa->pre->no]->co = 1;
}
static VOID
carcsort(first, last)
struct carc *first;
struct carc *last;
{
struct carc *p;
struct carc *q;
struct carc tmp;
if (last - first <= 1)
return;
for (p = first; p <= last; p++)
for (q = p; q <= last; q++)
if (p->co > q->co ||
(p->co == q->co && p->to > q->to)) {
assert(p != q);
tmp = *p;
*p = *q;
*q = tmp;
}
}
static VOID
freecnfa(cnfa)
struct cnfa *cnfa;
{
assert(cnfa->nstates != 0);
cnfa->nstates = 0;
FREE(cnfa->states);
FREE(cnfa->arcs);
}
static VOID
dumpnfa(nfa, f)
struct nfa *nfa;
FILE *f;
{
#ifdef REG_DEBUG
struct state *s;
fprintf(f, "pre %d, post %d", nfa->pre->no, nfa->post->no);
if (nfa->bos[0] != COLORLESS)
fprintf(f, ", bos [%ld]", (long)nfa->bos[0]);
if (nfa->bos[1] != COLORLESS)
fprintf(f, ", bol [%ld]", (long)nfa->bos[1]);
if (nfa->eos[0] != COLORLESS)
fprintf(f, ", eos [%ld]", (long)nfa->eos[0]);
if (nfa->eos[1] != COLORLESS)
fprintf(f, ", eol [%ld]", (long)nfa->eos[1]);
fprintf(f, "\n");
for (s = nfa->states; s != NULL; s = s->next)
dumpstate(s, f);
if (nfa->parent == NULL)
dumpcolors(nfa->cm, f);
fflush(f);
#endif
}
#ifdef REG_DEBUG
static VOID
dumpstate(s, f)
struct state *s;
FILE *f;
{
struct arc *a;
fprintf(f, "%d%s%c", s->no, (s->tmp != NULL) ? "T" : "",
(s->flag) ? s->flag : '.');
if (s->prev != NULL && s->prev->next != s)
fprintf(f, "\tstate chain bad\n");
if (s->nouts == 0)
fprintf(f, "\tno out arcs\n");
else
dumparcs(s, f);
fflush(f);
for (a = s->ins; a != NULL; a = a->inchain) {
if (a->to != s)
fprintf(f, "\tlink from %d to %d on %d's in-chain\n",
a->from->no, a->to->no, s->no);
}
}
static VOID
dumparcs(s, f)
struct state *s;
FILE *f;
{
int pos;
assert(s->nouts > 0);
pos = dumprarcs(s->outs, s, f, 1);
if (pos != 1)
fprintf(f, "\n");
}
static int
dumprarcs(a, s, f, pos)
struct arc *a;
struct state *s;
FILE *f;
int pos;
{
if (a->outchain != NULL)
pos = dumprarcs(a->outchain, s, f, pos);
dumparc(a, s, f);
if (pos == 5) {
fprintf(f, "\n");
pos = 1;
} else
pos++;
return pos;
}
static VOID
dumparc(a, s, f)
struct arc *a;
struct state *s;
FILE *f;
{
struct arc *aa;
struct arcbatch *ab;
fprintf(f, "\t");
switch (a->type) {
case PLAIN:
fprintf(f, "[%ld]", (long)a->co);
break;
case AHEAD:
fprintf(f, ">%ld>", (long)a->co);
break;
case BEHIND:
fprintf(f, "<%ld<", (long)a->co);
break;
case LACON:
fprintf(f, ":%ld:", (long)a->co);
break;
case '^':
case '$':
fprintf(f, "%c%d", a->type, (int)a->co);
break;
case EMPTY:
break;
default:
fprintf(f, "0x%x/0%lo", a->type, (long)a->co);
break;
}
if (a->from != s)
fprintf(f, "?%d?", a->from->no);
for (ab = &a->from->oas; ab != NULL; ab = ab->next) {
for (aa = &ab->a[0]; aa < &ab->a[ABSIZE]; aa++)
if (aa == a)
break;
if (aa < &ab->a[ABSIZE])
break;
}
if (ab == NULL)
fprintf(f, "?!?");
fprintf(f, "->");
if (a->to == NULL) {
fprintf(f, "NULL");
return;
}
fprintf(f, "%d", a->to->no);
for (aa = a->to->ins; aa != NULL; aa = aa->inchain)
if (aa == a)
break;
if (aa == NULL)
fprintf(f, "?!?");
}
#endif
static VOID
dumpcnfa(cnfa, f)
struct cnfa *cnfa;
FILE *f;
{
#ifdef REG_DEBUG
int st;
fprintf(f, "pre %d, post %d", cnfa->pre, cnfa->post);
if (cnfa->bos[0] != COLORLESS)
fprintf(f, ", bos [%ld]", (long)cnfa->bos[0]);
if (cnfa->bos[1] != COLORLESS)
fprintf(f, ", bol [%ld]", (long)cnfa->bos[1]);
if (cnfa->eos[0] != COLORLESS)
fprintf(f, ", eos [%ld]", (long)cnfa->eos[0]);
if (cnfa->eos[1] != COLORLESS)
fprintf(f, ", eol [%ld]", (long)cnfa->eos[1]);
if (cnfa->flags&HASLACONS)
fprintf(f, ", haslacons");
fprintf(f, "\n");
for (st = 0; st < cnfa->nstates; st++)
dumpcstate(st, cnfa->states[st], cnfa, f);
fflush(f);
#endif
}
#ifdef REG_DEBUG
static VOID
dumpcstate(st, ca, cnfa, f)
int st;
struct carc *ca;
struct cnfa *cnfa;
FILE *f;
{
int i;
int pos;
fprintf(f, "%d%s", st, (ca[0].co) ? ":" : ".");
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);
else
fprintf(f, "\t:%ld:->%d", (long)ca[i].co-cnfa->ncolors,
ca[i].to);
if (pos == 5) {
fprintf(f, "\n");
pos = 1;
} else
pos++;
}
if (i == 1 || pos != 1)
fprintf(f, "\n");
fflush(f);
}
#endif