regc_nfa.c File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Defines
#define	NISERR()   VISERR(nfa->v)
#define	NERR(e)   VERR(nfa->v, (e))
#define	CA(ct, at)   (((ct)<<CHAR_BIT) | (at))
Functions
static struct nfa *	newnfa (struct vars *v, struct colormap *cm, struct nfa *parent)
static int	TooManyStates (struct nfa *nfa)
static void	IncrementSize (struct nfa *nfa)
static void	DecrementSize (struct nfa *nfa)
static void	freenfa (struct nfa *nfa)
static struct state *	newstate (struct nfa *nfa)
static struct state *	newfstate (struct nfa *nfa, int flag)
static void	dropstate (struct nfa *nfa, struct state *s)
static void	freestate (struct nfa *nfa, struct state *s)
static void	destroystate (struct nfa *nfa, struct state *s)
static void	newarc (struct nfa *nfa, int t, pcolor co, struct state *from, struct state *to)
static struct arc *	allocarc (struct nfa *nfa, struct state *s)
static void	freearc (struct nfa *nfa, struct arc *victim)
static int	hasnonemptyout (struct state *s)
static int	nonemptyouts (struct state *s)
static int	nonemptyins (struct state *s)
static struct arc *	findarc (struct state *s, int type, pcolor co)
static void	cparc (struct nfa *nfa, struct arc *oa, struct state *from, struct state *to)
static void	moveins (struct nfa *nfa, struct state *oldState, struct state *newState)
static void	copyins (struct nfa *nfa, struct state *oldState, struct state *newState, int all)
static void	moveouts (struct nfa *nfa, struct state *oldState, struct state *newState)
static void	copyouts (struct nfa *nfa, struct state *oldState, struct state *newState, int all)
static void	cloneouts (struct nfa *nfa, struct state *old, struct state *from, struct state *to, int type)
static void	delsub (struct nfa *nfa, struct state *lp, struct state *rp)
static void	deltraverse (struct nfa *nfa, struct state *leftend, struct state *s)
static void	dupnfa (struct nfa *nfa, struct state *start, struct state *stop, struct state *from, struct state *to)
static void	duptraverse (struct nfa *nfa, struct state *s, struct state *stmp)
static void	cleartraverse (struct nfa *nfa, struct state *s)
static void	specialcolors (struct nfa *nfa)
static long	optimize (struct nfa *nfa, FILE *f)
static void	pullback (struct nfa *nfa, FILE *f)
static int	pull (struct nfa *nfa, struct arc *con)
static void	pushfwd (struct nfa *nfa, FILE *f)
static int	push (struct nfa *nfa, struct arc *con)
static int	combine (struct arc *con, struct arc *a)
static void	fixempties (struct nfa *nfa, FILE *f)
static struct state *	emptyreachable (struct state *s, struct state *lastfound)
static void	replaceempty (struct nfa *nfa, struct state *from, struct state *to)
static void	cleanup (struct nfa *nfa)
static void	markreachable (struct nfa *nfa, struct state *s, struct state *okay, struct state *mark)
static void	markcanreach (struct nfa *nfa, struct state *s, struct state *okay, struct state *mark)
static long	analyze (struct nfa *nfa)
static void	compact (struct nfa *nfa, struct cnfa *cnfa)
static void	carcsort (struct carc *first, struct carc *last)
static void	freecnfa (struct cnfa *cnfa)
static void	dumpnfa (struct nfa *nfa, FILE *f)

---

Define Documentation

#define CA	(		ct,
			at
	)			(((ct)<<CHAR_BIT) | (at))

Referenced by combine().

#define NERR

(

e

)

VERR(nfa->v, (e))

Definition at line 40 of file regc_nfa.c.

Referenced by allocarc(), compact(), and newstate().

#define NISERR

(

)

VISERR(nfa->v)

Definition at line 39 of file regc_nfa.c.

Referenced by compact(), duptraverse(), fixempties(), newarc(), pull(), pullback(), push(), and pushfwd().

---

Function Documentation

static struct arc* allocarc	(	struct nfa *	nfa,
		struct state *	s
	)			[static, read]

Definition at line 358 of file regc_nfa.c.

References arcbatch::a, ABSIZE, assert, state::free, i, MALLOC, NERR, arcbatch::next, state::noas, NULL, state::oas, REG_ESPACE, and arc::type.

Referenced by newarc().

{
    struct arc *a;

    /* shortcut */
    if (s->free == NULL && s->noas < ABSIZE)
    {
        a = &s->oas.a[s->noas];
        s->noas++;
        return a;
    }

    /* if none at hand, get more */
    if (s->free == NULL)
    {
        struct arcbatch *newAb;
        int         i;

        newAb = (struct arcbatch *) MALLOC(sizeof(struct arcbatch));
        if (newAb == NULL)
        {
            NERR(REG_ESPACE);
            return NULL;
        }
        newAb->next = s->oas.next;
        s->oas.next = newAb;

        for (i = 0; i < ABSIZE; i++)
        {
            newAb->a[i].type = 0;
            newAb->a[i].freechain = &newAb->a[i + 1];
        }
        newAb->a[ABSIZE - 1].freechain = NULL;
        s->free = &newAb->a[0];
    }
    assert(s->free != NULL);

    a = s->free;
    s->free = a->freechain;
    return a;
}

static long analyze

(

struct nfa *

nfa

)

[static]

Definition at line 1474 of file regc_nfa.c.

References NULL, arc::outchain, state::outs, nfa::post, nfa::pre, and arc::to.

Referenced by GetCommandLogLevel(), and optimize().

{
    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 carcsort	(	struct carc *	first,
		struct carc *	last
	)			[static]

Definition at line 1583 of file regc_nfa.c.

References assert, carc::co, and carc::to.

Referenced by compact().

{
    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 cleanup

(

struct nfa *

nfa

)

[static]

Definition at line 1404 of file regc_nfa.c.

References assert, cleartraverse(), dropstate(), state::flag, markcanreach(), markreachable(), state::next, state::nins, state::no, nfa::nstates, NULL, nfa::post, nfa::pre, nfa::states, and state::tmp.

Referenced by optimize().

{
    struct state *s;
    struct state *nexts;
    int         n;

    /* clear out unreachable or dead-end states */
    /* use pre to mark reachable, then post to mark can-reach-post */
    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);
    /* the nins==0 (final unreachable) case will be caught later */

    /* renumber surviving states */
    n = 0;
    for (s = nfa->states; s != NULL; s = s->next)
        s->no = n++;
    nfa->nstates = n;
}

static void cleartraverse	(	struct nfa *	nfa,
		struct state *	s
	)			[static]

Definition at line 768 of file regc_nfa.c.

References NULL, arc::outchain, state::outs, state::tmp, and arc::to.

Referenced by cleanup(), and dupnfa().

{
    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 cloneouts	(	struct nfa *	nfa,
		struct state *	old,
		struct state *	from,
		struct state *	to,
		int	type
	)			[static]

Definition at line 630 of file regc_nfa.c.

References assert, arc::co, newarc(), NULL, arc::outchain, and state::outs.

{
    struct arc *a;

    assert(old != from);

    for (a = old->outs; a != NULL; a = a->outchain)
        newarc(nfa, type, a->co, from, to);
}

static int combine	(	struct arc *	con,
		struct arc *	a
	)			[static]

Definition at line 1141 of file regc_nfa.c.

References AHEAD, assert, BEHIND, CA, arc::co, LACON, NOTREACHED, PLAIN, and arc::type.

Referenced by pull(), and push().

{
#define  CA(ct,at)   (((ct)<<CHAR_BIT) | (at))

    switch (CA(con->type, a->type))
    {
        case CA('^', PLAIN):    /* newlines are handled separately */
        case CA('$', PLAIN):
            return INCOMPATIBLE;
            break;
        case CA(AHEAD, PLAIN):  /* color constraints meet colors */
        case CA(BEHIND, PLAIN):
            if (con->co == a->co)
                return SATISFIED;
            return INCOMPATIBLE;
            break;
        case CA('^', '^'):      /* collision, similar constraints */
        case CA('$', '$'):
        case CA(AHEAD, AHEAD):
        case CA(BEHIND, BEHIND):
            if (con->co == a->co)       /* true duplication */
                return SATISFIED;
            return INCOMPATIBLE;
            break;
        case CA('^', BEHIND):   /* collision, dissimilar constraints */
        case CA(BEHIND, '^'):
        case CA('$', AHEAD):
        case CA(AHEAD, '$'):
            return INCOMPATIBLE;
            break;
        case CA('^', '$'):      /* constraints passing each other */
        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;        /* for benefit of blind compilers */
}

static void compact	(	struct nfa *	nfa,
		struct cnfa *	cnfa
	)			[static]

Definition at line 1492 of file regc_nfa.c.

References cnfa::arcs, assert, nfa::bos, cnfa::bos, carcsort(), nfa::cm, arc::co, carc::co, nfa::eos, cnfa::eos, cnfa::flags, FREE, LACON, MALLOC, maxcolor(), cnfa::ncolors, NERR, state::next, NISERR, state::no, NOTREACHED, state::nouts, cnfa::nstates, NULL, arc::outchain, state::outs, PLAIN, nfa::post, cnfa::post, nfa::pre, cnfa::pre, REG_ESPACE, cnfa::states, nfa::states, cnfa::stflags, arc::to, carc::to, and arc::type.

{
    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 += 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->stflags == NULL || cnfa->states == NULL || cnfa->arcs == NULL)
    {
        if (cnfa->stflags != NULL)
            FREE(cnfa->stflags);
        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->stflags[s->no] = 0;
        cnfa->states[s->no] = 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);

    /* mark no-progress states */
    for (a = nfa->pre->outs; a != NULL; a = a->outchain)
        cnfa->stflags[a->to->no] = CNFA_NOPROGRESS;
    cnfa->stflags[nfa->pre->no] = CNFA_NOPROGRESS;
}

static void copyins	(	struct nfa *	nfa,
		struct state *	oldState,
		struct state *	newState,
		int	all
	)			[static]

Definition at line 569 of file regc_nfa.c.

References assert, cparc(), EMPTY, arc::from, arc::inchain, state::ins, NULL, and arc::type.

Referenced by pull(), and replaceempty().

{
    struct arc *a;

    assert(oldState != newState);

    for (a = oldState->ins; a != NULL; a = a->inchain)
    {
        if (all || a->type != EMPTY)
            cparc(nfa, a, a->from, newState);
    }
}

static void copyouts	(	struct nfa *	nfa,
		struct state *	oldState,
		struct state *	newState,
		int	all
	)			[static]

Definition at line 610 of file regc_nfa.c.

References assert, cparc(), EMPTY, NULL, arc::outchain, state::outs, arc::to, and arc::type.

Referenced by push(), and replaceempty().

{
    struct arc *a;

    assert(oldState != newState);

    for (a = oldState->outs; a != NULL; a = a->outchain)
    {
        if (all || a->type != EMPTY)
            cparc(nfa, a, newState, a->to);
    }
}

static void cparc	(	struct nfa *	nfa,
		struct arc *	oa,
		struct state *	from,
		struct state *	to
	)			[static]

Definition at line 529 of file regc_nfa.c.

References arc::co, newarc(), and arc::type.

Referenced by copyins(), copyouts(), duptraverse(), moveins(), moveouts(), pull(), and push().

{
    newarc(nfa, oa->type, oa->co, from, to);
}

static void DecrementSize

(

struct nfa *

nfa

)

[static]

Definition at line 131 of file regc_nfa.c.

References NULL, nfa::parent, and nfa::size.

Referenced by freestate().

{
    struct nfa *parent = nfa->parent;

    nfa->size--;
    while (parent != NULL)
    {
        parent->size--;
        parent = parent->parent;
    }
}

static void delsub	(	struct nfa *	nfa,
		struct state *	lp,
		struct state *	rp
	)			[static]

Definition at line 651 of file regc_nfa.c.

References assert, deltraverse(), FREESTATE, state::nins, state::no, state::nouts, and state::tmp.

{
    assert(lp != rp);

    rp->tmp = rp;               /* mark end */

    deltraverse(nfa, lp, lp);
    assert(lp->nouts == 0 && rp->nins == 0);    /* did the job */
    assert(lp->no != FREESTATE && rp->no != FREESTATE); /* no more */

    rp->tmp = NULL;             /* unmark end */
    lp->tmp = NULL;             /* and begin, marked by deltraverse */
}

static void deltraverse	(	struct nfa *	nfa,
		struct state *	leftend,
		struct state *	s
	)			[static]

Definition at line 672 of file regc_nfa.c.

References assert, freearc(), FREESTATE, freestate(), state::nins, state::no, state::nouts, NULL, state::outs, state::tmp, and arc::to.

Referenced by delsub().

{
    struct arc *a;
    struct state *to;

    if (s->nouts == 0)
        return;                 /* nothing to do */
    if (s->tmp != NULL)
        return;                 /* already in progress */

    s->tmp = s;                 /* mark as in progress */

    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); /* we're still here */
    assert(s == leftend || s->nins != 0);       /* and still reachable */
    assert(s->nouts == 0);      /* but have no outarcs */

    s->tmp = NULL;              /* we're done here */
}

static void destroystate	(	struct nfa *	nfa,
		struct state *	s
	)			[static]

Definition at line 289 of file regc_nfa.c.

References assert, FREE, FREESTATE, state::ins, state::next, arcbatch::next, state::no, NULL, state::oas, and state::outs.

Referenced by freenfa().

{
    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 dropstate	(	struct nfa *	nfa,
		struct state *	s
	)			[static]

Definition at line 241 of file regc_nfa.c.

References freearc(), freestate(), state::ins, NULL, and state::outs.

Referenced by cleanup(), fixempties(), pull(), and push().

{
    struct arc *a;

    while ((a = s->ins) != NULL)
        freearc(nfa, a);
    while ((a = s->outs) != NULL)
        freearc(nfa, a);
    freestate(nfa, s);
}

static void dumpnfa	(	struct nfa *	nfa,
		FILE *	f
	)			[static]

Definition at line 1622 of file regc_nfa.c.

References nfa::bos, nfa::cm, COLORLESS, nfa::eos, state::next, state::no, NULL, nfa::parent, nfa::post, nfa::pre, and nfa::states.

Referenced by fixempties(), optimize(), pullback(), and pushfwd().

{
#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
}

static void dupnfa	(	struct nfa *	nfa,
		struct state *	start,
		struct state *	stop,
		struct state *	from,
		struct state *	to
	)			[static]

Definition at line 714 of file regc_nfa.c.

References cleartraverse(), duptraverse(), EMPTY, newarc(), and state::tmp.

{
    if (start == stop)
    {
        newarc(nfa, EMPTY, 0, from, to);
        return;
    }

    stop->tmp = to;
    duptraverse(nfa, start, from);
    /* done, except for clearing out the tmp pointers */

    stop->tmp = NULL;
    cleartraverse(nfa, start);
}

static void duptraverse	(	struct nfa *	nfa,
		struct state *	s,
		struct state *	stmp
	)			[static]

Definition at line 738 of file regc_nfa.c.

References assert, cparc(), newstate(), NISERR, NULL, arc::outchain, state::outs, state::tmp, and arc::to.

Referenced by dupnfa().

{
    struct arc *a;

    if (s->tmp != NULL)
        return;                 /* already done */

    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);
        if (NISERR())
            break;
        assert(a->to->tmp != NULL);
        cparc(nfa, a, s->tmp, a->to->tmp);
    }
}

static struct state* emptyreachable	(	struct state *	s,
		struct state *	lastfound
	)			[static, read]

Definition at line 1322 of file regc_nfa.c.

References EMPTY, NULL, arc::outchain, state::outs, state::tmp, arc::to, and arc::type.

Referenced by fixempties().

{
    struct arc *a;

    s->tmp = lastfound;
    lastfound = s;
    for (a = s->outs; a != NULL; a = a->outchain)
    {
        if (a->type == EMPTY && a->to->tmp == NULL)
            lastfound = emptyreachable(a->to, lastfound);
    }
    return lastfound;
}

static struct arc* findarc	(	struct state *	s,
		int	type,
		pcolor	co
	)			[static, read]

Definition at line 513 of file regc_nfa.c.

References arc::co, NULL, arc::outchain, state::outs, and arc::type.

Referenced by colorcomplement().

{
    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 fixempties	(	struct nfa *	nfa,
		FILE *	f
	)			[static]

Definition at line 1195 of file regc_nfa.c.

References assert, dropstate(), dumpnfa(), EMPTY, emptyreachable(), state::flag, freearc(), arc::from, hasnonemptyout(), arc::inchain, state::ins, moveins(), moveouts(), state::next, state::nins, NISERR, state::nouts, NULL, arc::outchain, state::outs, replaceempty(), s2, nfa::states, state::tmp, arc::to, and arc::type.

Referenced by optimize().

{
    struct state *s;
    struct state *s2;
    struct state *nexts;
    struct arc *a;
    struct arc *nexta;

    /*
     * First, get rid of any states whose sole out-arc is an EMPTY, since
     * they're basically just aliases for their successor.  The parsing
     * algorithm creates enough of these that it's worth special-casing this.
     */
    for (s = nfa->states; s != NULL && !NISERR(); s = nexts)
    {
        nexts = s->next;
        if (s->flag || s->nouts != 1)
            continue;
        a = s->outs;
        assert(a != NULL && a->outchain == NULL);
        if (a->type != EMPTY)
            continue;
        if (s != a->to)
            moveins(nfa, s, a->to);
        dropstate(nfa, s);
    }

    /*
     * Similarly, get rid of any state with a single EMPTY in-arc, by folding
     * it into its predecessor.
     */
    for (s = nfa->states; s != NULL && !NISERR(); s = nexts)
    {
        nexts = s->next;
        /* while we're at it, ensure tmp fields are clear for next step */
        assert(s->tmp == NULL);
        if (s->flag || s->nins != 1)
            continue;
        a = s->ins;
        assert(a != NULL && a->inchain == NULL);
        if (a->type != EMPTY)
            continue;
        if (s != a->from)
            moveouts(nfa, s, a->from);
        dropstate(nfa, s);
    }

    /*
     * For each remaining NFA state, find all other states that are reachable
     * from it by a chain of one or more EMPTY arcs.  Then generate new arcs
     * that eliminate the need for each such chain.
     *
     * If we just do this straightforwardly, the algorithm gets slow in
     * complex graphs, because the same arcs get copied to all intermediate
     * states of an EMPTY chain, and then uselessly pushed repeatedly to the
     * chain's final state; we waste a lot of time in newarc's duplicate
     * checking.  To improve matters, we decree that any state with only EMPTY
     * out-arcs is "doomed" and will not be part of the final NFA. That can be
     * ensured by not adding any new out-arcs to such a state. Having ensured
     * that, we need not update the state's in-arcs list either; all arcs that
     * might have gotten pushed forward to it will just get pushed directly to
     * successor states.  This eliminates most of the useless duplicate arcs.
     */
    for (s = nfa->states; s != NULL && !NISERR(); s = s->next)
    {
        for (s2 = emptyreachable(s, s); s2 != s && !NISERR(); s2 = nexts)
        {
            /*
             * If s2 is doomed, we decide that (1) we will always push arcs
             * forward to it, not pull them back to s; and (2) we can optimize
             * away the push-forward, per comment above.  So do nothing.
             */
            if (s2->flag || hasnonemptyout(s2))
                replaceempty(nfa, s, s2);

            /* Reset the tmp fields as we walk back */
            nexts = s2->tmp;
            s2->tmp = NULL;
        }
        s->tmp = NULL;
    }

    if (NISERR())
        return;

    /*
     * Now remove all the EMPTY arcs, since we don't need them anymore.
     */
    for (s = nfa->states; s != NULL; s = s->next)
    {
        for (a = s->outs; a != NULL; a = nexta)
        {
            nexta = a->outchain;
            if (a->type == EMPTY)
                freearc(nfa, a);
        }
    }

    /*
     * And remove any states that have become useless.  (This cleanup is not
     * very thorough, and would be even less so if we tried to combine it with
     * the previous step; but cleanup() will take care of anything we miss.)
     */
    for (s = nfa->states; s != NULL; s = nexts)
    {
        nexts = s->next;
        if ((s->nins == 0 || s->nouts == 0) && !s->flag)
            dropstate(nfa, s);
    }

    if (f != NULL)
        dumpnfa(nfa, f);
}

static void freearc	(	struct nfa *	nfa,
		struct arc *	victim
	)			[static]

Definition at line 405 of file regc_nfa.c.

References assert, nfa::cm, COLORED, state::free, arc::from, arc::inchain, state::ins, state::nins, state::nouts, NULL, arc::outchain, state::outs, nfa::parent, arc::to, arc::type, and uncolorchain().

Referenced by deltraverse(), dropstate(), fixempties(), moveins(), moveouts(), pull(), pullback(), push(), and pushfwd().

{
    struct state *from = victim->from;
    struct state *to = victim->to;
    struct arc *a;

    assert(victim->type != 0);

    /* take it off color chain if necessary */
    if (COLORED(victim) && nfa->parent == NULL)
        uncolorchain(nfa->cm, victim);

    /* take it off source's out-chain */
    assert(from != NULL);
    assert(from->outs != NULL);
    a = from->outs;
    if (a == victim)            /* simple case:  first in chain */
        from->outs = victim->outchain;
    else
    {
        for (; a != NULL && a->outchain != victim; a = a->outchain)
            continue;
        assert(a != NULL);
        a->outchain = victim->outchain;
    }
    from->nouts--;

    /* take it off target's in-chain */
    assert(to != NULL);
    assert(to->ins != NULL);
    a = to->ins;
    if (a == victim)            /* simple case:  first in chain */
        to->ins = victim->inchain;
    else
    {
        for (; a != NULL && a->inchain != victim; a = a->inchain)
            continue;
        assert(a != NULL);
        a->inchain = victim->inchain;
    }
    to->nins--;

    /* clean up and place on free list */
    victim->type = 0;
    victim->from = NULL;        /* precautions... */
    victim->to = NULL;
    victim->inchain = NULL;
    victim->outchain = NULL;
    victim->freechain = from->free;
    from->free = victim;
}

static void freecnfa

(

struct cnfa *

cnfa

)

[static]

Definition at line 1609 of file regc_nfa.c.

References cnfa::arcs, assert, FREE, cnfa::nstates, cnfa::states, and cnfa::stflags.

{
    assert(cnfa->nstates != 0); /* not empty already */
    cnfa->nstates = 0;
    FREE(cnfa->stflags);
    FREE(cnfa->states);
    FREE(cnfa->arcs);
}

static void freenfa

(

struct nfa *

nfa

)

[static]

Definition at line 147 of file regc_nfa.c.

References destroystate(), FREE, nfa::free, freestate(), state::next, state::nins, state::nouts, nfa::nstates, NULL, nfa::post, nfa::pre, nfa::slast, and nfa::states.

Referenced by newnfa().

{
    struct state *s;

    while ((s = nfa->states) != NULL)
    {
        s->nins = s->nouts = 0; /* don't worry about arcs */
        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 void freestate	(	struct nfa *	nfa,
		struct state *	s
	)			[static]

Definition at line 257 of file regc_nfa.c.

References assert, DecrementSize(), state::flag, nfa::free, state::next, state::nins, state::no, state::nouts, NULL, state::prev, nfa::slast, and nfa::states.

Referenced by deltraverse(), dropstate(), and freenfa().

{
    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;        /* don't delete it, put it on the free list */
    nfa->free = s;
    DecrementSize(nfa);
}

static int hasnonemptyout

(

struct state *

s

)

[static]

Definition at line 462 of file regc_nfa.c.

References EMPTY, NULL, arc::outchain, state::outs, and arc::type.

Referenced by fixempties().

{
    struct arc *a;

    for (a = s->outs; a != NULL; a = a->outchain)
    {
        if (a->type != EMPTY)
            return 1;
    }
    return 0;
}

static void IncrementSize

(

struct nfa *

nfa

)

[static]

Definition at line 115 of file regc_nfa.c.

References NULL, nfa::parent, and nfa::size.

Referenced by newstate().

{
    struct nfa *parent = nfa->parent;

    nfa->size++;
    while (parent != NULL)
    {
        parent->size++;
        parent = parent->parent;
    }
}

static void markcanreach	(	struct nfa *	nfa,
		struct state *	s,
		struct state *	okay,
		struct state *	mark
	)			[static]

Definition at line 1455 of file regc_nfa.c.

References arc::from, arc::inchain, state::ins, NULL, and state::tmp.

Referenced by cleanup().

{
    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 void markreachable	(	struct nfa *	nfa,
		struct state *	s,
		struct state *	okay,
		struct state *	mark
	)			[static]

Definition at line 1436 of file regc_nfa.c.

References NULL, arc::outchain, state::outs, state::tmp, and arc::to.

Referenced by cleanup().

{
    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 moveins	(	struct nfa *	nfa,
		struct state *	oldState,
		struct state *	newState
	)			[static]

Definition at line 546 of file regc_nfa.c.

References assert, cparc(), freearc(), arc::from, state::ins, state::nins, and NULL.

Referenced by fixempties(), and pull().

{
    struct arc *a;

    assert(oldState != newState);

    while ((a = oldState->ins) != NULL)
    {
        cparc(nfa, a, a->from, newState);
        freearc(nfa, a);
    }
    assert(oldState->nins == 0);
    assert(oldState->ins == NULL);
}

static void moveouts	(	struct nfa *	nfa,
		struct state *	oldState,
		struct state *	newState
	)			[static]

Definition at line 589 of file regc_nfa.c.

References assert, cparc(), freearc(), NULL, state::outs, and arc::to.

Referenced by fixempties(), and push().

{
    struct arc *a;

    assert(oldState != newState);

    while ((a = oldState->outs) != NULL)
    {
        cparc(nfa, a, newState, a->to);
        freearc(nfa, a);
    }
}

static void newarc	(	struct nfa *	nfa,
		int	t,
		pcolor	co,
		struct state *	from,
		struct state *	to
	)			[static]

Definition at line 311 of file regc_nfa.c.

References allocarc(), assert, nfa::cm, arc::co, colorchain(), COLORED, arc::from, arc::inchain, state::ins, state::nins, NISERR, state::nouts, NULL, arc::outchain, state::outs, nfa::parent, arc::to, and arc::type.

Referenced by cloneouts(), colorcomplement(), cparc(), dupnfa(), newnfa(), okcolors(), pullback(), pushfwd(), rainbow(), subblock(), and subrange().

{
    struct arc *a;

    assert(from != NULL && to != NULL);

    /* check for duplicates */
    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;

    /*
     * Put the new arc on the beginning, not the end, of the chains. Not only
     * is this easier, it has the very useful side effect that deleting the
     * most-recently-added arc is the cheapest case rather than the most
     * expensive one.
     */
    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);
}

static struct state* newfstate	(	struct nfa *	nfa,
		int	flag
	)			[static, read]

Definition at line 227 of file regc_nfa.c.

References state::flag, newstate(), and NULL.

Referenced by newnfa().

{
    struct state *s;

    s = newstate(nfa);
    if (s != NULL)
        s->flag = (char) flag;
    return s;
}

static struct nfa* newnfa	(	struct vars *	v,
		struct colormap *	cm,
		struct nfa *	parent
	)			[static, read]

Definition at line 47 of file regc_nfa.c.

References nfa::bos, nfa::cm, COLORLESS, nfa::eos, nfa::final, nfa::free, freenfa(), nfa::init, ISERR, MALLOC, newarc(), newfstate(), newstate(), nfa::nstates, NULL, nfa::parent, PLAIN, nfa::post, nfa::pre, rainbow(), nfa::size, nfa::slast, nfa::states, and nfa::v.

{
    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->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. */
    nfa->post = newfstate(nfa, '@');    /* number 0 */
    nfa->pre = newfstate(nfa, '>');     /* number 1 */

    nfa->init = newstate(nfa);  /* may become invalid later */
    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 struct state* newstate

(

struct nfa *

nfa

)

[static, read]

Definition at line 173 of file regc_nfa.c.

References assert, state::flag, state::free, nfa::free, IncrementSize(), state::ins, MALLOC, NERR, arcbatch::next, state::next, state::nins, state::no, state::noas, state::nouts, nfa::nstates, NULL, state::oas, state::outs, state::prev, REG_ESPACE, REG_ETOOBIG, nfa::slast, nfa::states, state::tmp, and TooManyStates().

Referenced by duptraverse(), newfstate(), newnfa(), pull(), and push().

{
    struct state *s;

    if (TooManyStates(nfa))
    {
        NERR(REG_ETOOBIG);
        return NULL;
    }
    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;
    /* track the current size and the parent size */
    IncrementSize(nfa);
    return s;
}

static int nonemptyins

(

struct state *

s

)

[static]

Definition at line 495 of file regc_nfa.c.

References EMPTY, arc::inchain, state::ins, NULL, and arc::type.

Referenced by replaceempty().

{
    int         n = 0;
    struct arc *a;

    for (a = s->ins; a != NULL; a = a->inchain)
    {
        if (a->type != EMPTY)
            n++;
    }
    return n;
}

static int nonemptyouts

(

struct state *

s

)

[static]

Definition at line 478 of file regc_nfa.c.

References EMPTY, NULL, arc::outchain, state::outs, and arc::type.

Referenced by replaceempty().

{
    int         n = 0;
    struct arc *a;

    for (a = s->outs; a != NULL; a = a->outchain)
    {
        if (a->type != EMPTY)
            n++;
    }
    return n;
}

static long optimize	(	struct nfa *	nfa,
		FILE *	f
	)			[static]

Definition at line 812 of file regc_nfa.c.

References analyze(), cleanup(), dumpnfa(), fixempties(), pullback(), pushfwd(), and verbose.

{
#ifdef REG_DEBUG
    int         verbose = (f != NULL) ? 1 : 0;

    if (verbose)
        fprintf(f, "\ninitial cleanup:\n");
#endif
    cleanup(nfa);               /* may simplify situation */
#ifdef REG_DEBUG
    if (verbose)
        dumpnfa(nfa, f);
    if (verbose)
        fprintf(f, "\nempties:\n");
#endif
    fixempties(nfa, f);         /* get rid of EMPTY arcs */
#ifdef REG_DEBUG
    if (verbose)
        fprintf(f, "\nconstraints:\n");
#endif
    pullback(nfa, f);           /* pull back constraints backward */
    pushfwd(nfa, f);            /* push fwd constraints forward */
#ifdef REG_DEBUG
    if (verbose)
        fprintf(f, "\nfinal cleanup:\n");
#endif
    cleanup(nfa);               /* final tidying */
    return analyze(nfa);        /* and analysis */
}

static int pull	(	struct nfa *	nfa,
		struct arc *	con
	)			[static]

Definition at line 897 of file regc_nfa.c.

References AHEAD, assert, BEHIND, combine(), COMPATIBLE, copyins(), cparc(), dropstate(), state::flag, freearc(), arc::from, arc::inchain, INCOMPATIBLE, state::ins, moveins(), newstate(), state::nins, NISERR, NOTREACHED, state::nouts, NULL, arc::outchain, state::outs, SATISFIED, arc::to, and arc::type.

Referenced by pullback().

{
    struct state *from = con->from;
    struct state *to = con->to;
    struct arc *a;
    struct arc *nexta;
    struct state *s;

    if (from == to)
    {                           /* circular constraint is pointless */
        freearc(nfa, con);
        return 1;
    }
    if (from->flag)             /* can't pull back beyond start */
        return 0;
    if (from->nins == 0)
    {                           /* unreachable */
        freearc(nfa, con);
        return 1;
    }

    /*
     * DGP 2007-11-15: Cloning a state with a circular constraint on its list
     * of outs can lead to trouble [Tcl Bug 1810038], so get rid of them
     * first.
     */
    for (a = from->outs; a != NULL; a = nexta)
    {
        nexta = a->outchain;
        switch (a->type)
        {
            case '^':
            case '$':
            case BEHIND:
            case AHEAD:
                if (from == a->to)
                    freearc(nfa, a);
                break;
        }
    }

    /* first, clone from state if necessary to avoid other outarcs */
    if (from->nouts > 1)
    {
        s = newstate(nfa);
        if (NISERR())
            return 0;
        assert(to != from);     /* con is not an inarc */
        copyins(nfa, from, s, 1);       /* duplicate inarcs */
        cparc(nfa, con, s, to); /* move constraint arc */
        freearc(nfa, con);
        from = s;
        con = from->outs;
    }
    assert(from->nouts == 1);

    /* propagate the constraint into the from state's inarcs */
    for (a = from->ins; a != NULL; a = nexta)
    {
        nexta = a->inchain;
        switch (combine(con, a))
        {
            case INCOMPATIBLE:  /* destroy the arc */
                freearc(nfa, a);
                break;
            case SATISFIED:     /* no action needed */
                break;
            case COMPATIBLE:    /* swap the two arcs, more or less */
                s = newstate(nfa);
                if (NISERR())
                    return 0;
                cparc(nfa, a, s, to);   /* anticipate move */
                cparc(nfa, con, a->from, s);
                if (NISERR())
                    return 0;
                freearc(nfa, a);
                break;
            default:
                assert(NOTREACHED);
                break;
        }
    }

    /* remaining inarcs, if any, incorporate the constraint */
    moveins(nfa, from, to);
    dropstate(nfa, from);       /* will free the constraint */
    return 1;
}

static void pullback	(	struct nfa *	nfa,
		FILE *	f
	)			[static]

Definition at line 847 of file regc_nfa.c.

References assert, BEHIND, nfa::bos, arc::co, dumpnfa(), freearc(), FREESTATE, arc::from, newarc(), state::next, NISERR, state::no, NULL, arc::outchain, state::outs, PLAIN, nfa::pre, pull(), nfa::states, arc::to, and arc::type.

Referenced by optimize().

{
    struct state *s;
    struct state *nexts;
    struct arc *a;
    struct arc *nexta;
    int         progress;

    /* find and pull until there are no more */
    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 push	(	struct nfa *	nfa,
		struct arc *	con
	)			[static]

Definition at line 1041 of file regc_nfa.c.

References AHEAD, assert, BEHIND, combine(), COMPATIBLE, copyouts(), cparc(), dropstate(), state::flag, freearc(), arc::from, arc::inchain, INCOMPATIBLE, state::ins, moveouts(), newstate(), state::nins, NISERR, NOTREACHED, state::nouts, NULL, arc::outchain, state::outs, SATISFIED, arc::to, and arc::type.

Referenced by pushfwd().

{
    struct state *from = con->from;
    struct state *to = con->to;
    struct arc *a;
    struct arc *nexta;
    struct state *s;

    if (to == from)
    {                           /* circular constraint is pointless */
        freearc(nfa, con);
        return 1;
    }
    if (to->flag)               /* can't push forward beyond end */
        return 0;
    if (to->nouts == 0)
    {                           /* dead end */
        freearc(nfa, con);
        return 1;
    }

    /*
     * DGP 2007-11-15: Here we duplicate the same protections as appear in
     * pull() above to avoid troubles with cloning a state with a circular
     * constraint on its list of ins.  It is not clear whether this is
     * necessary, or is protecting against a "can't happen". Any test case
     * that actually leads to a freearc() call here would be a welcome
     * addition to the test suite.
     */
    for (a = to->ins; a != NULL; a = nexta)
    {
        nexta = a->inchain;
        switch (a->type)
        {
            case '^':
            case '$':
            case BEHIND:
            case AHEAD:
                if (a->from == to)
                    freearc(nfa, a);
                break;
        }
    }

    /* first, clone to state if necessary to avoid other inarcs */
    if (to->nins > 1)
    {
        s = newstate(nfa);
        if (NISERR())
            return 0;
        copyouts(nfa, to, s, 1);    /* duplicate outarcs */
        cparc(nfa, con, from, s);       /* move constraint */
        freearc(nfa, con);
        to = s;
        con = to->ins;
    }
    assert(to->nins == 1);

    /* propagate the constraint into the to state's outarcs */
    for (a = to->outs; a != NULL; a = nexta)
    {
        nexta = a->outchain;
        switch (combine(con, a))
        {
            case INCOMPATIBLE:  /* destroy the arc */
                freearc(nfa, a);
                break;
            case SATISFIED:     /* no action needed */
                break;
            case COMPATIBLE:    /* swap the two arcs, more or less */
                s = newstate(nfa);
                if (NISERR())
                    return 0;
                cparc(nfa, con, s, a->to);      /* anticipate move */
                cparc(nfa, a, from, s);
                if (NISERR())
                    return 0;
                freearc(nfa, a);
                break;
            default:
                assert(NOTREACHED);
                break;
        }
    }

    /* remaining outarcs, if any, incorporate the constraint */
    moveouts(nfa, to, from);
    dropstate(nfa, to);         /* will free the constraint */
    return 1;
}

static void pushfwd	(	struct nfa *	nfa,
		FILE *	f
	)			[static]

Definition at line 991 of file regc_nfa.c.

References AHEAD, assert, arc::co, dumpnfa(), nfa::eos, freearc(), FREESTATE, arc::from, arc::inchain, state::ins, newarc(), state::next, NISERR, state::no, NULL, PLAIN, nfa::post, push(), nfa::states, arc::to, and arc::type.

Referenced by optimize().

{
    struct state *s;
    struct state *nexts;
    struct arc *a;
    struct arc *nexta;
    int         progress;

    /* find and push until there are no more */
    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 void replaceempty	(	struct nfa *	nfa,
		struct state *	from,
		struct state *	to
	)			[static]

Definition at line 1343 of file regc_nfa.c.

References assert, copyins(), copyouts(), state::nins, nonemptyins(), nonemptyouts(), and state::nouts.

Referenced by fixempties().

{
    int         fromouts;
    int         toins;

    assert(from != to);

    /*
     * Create replacement arcs that bypass the need for the EMPTY chain.  We
     * can do this either by pushing arcs forward (linking directly from
     * "from"'s predecessors to "to") or by pulling them back (linking
     * directly from "from" to "to"'s successors).  In general, we choose
     * whichever way creates greater fan-out or fan-in, so as to improve the
     * odds of reducing the other state to zero in-arcs or out-arcs and
     * thereby being able to delete it.  However, if "from" is doomed (has no
     * non-EMPTY out-arcs), we must keep it so, so always push forward in that
     * case.
     *
     * The fan-out/fan-in comparison should count only non-EMPTY arcs.  If
     * "from" is doomed, we can skip counting "to"'s arcs, since we want to
     * force taking the copyins path in that case.
     */
    fromouts = nonemptyouts(from);
    toins = (fromouts == 0) ? 1 : nonemptyins(to);

    if (fromouts > toins)
    {
        copyouts(nfa, to, from, 0);
        return;
    }
    if (fromouts < toins)
    {
        copyins(nfa, from, to, 0);
        return;
    }

    /*
     * fromouts == toins.  Decide on secondary issue: copy fewest arcs.
     *
     * Doesn't seem to be worth the trouble to exclude empties from these
     * comparisons; that takes extra time and doesn't seem to improve the
     * resulting graph much.
     */
    if (from->nins > to->nouts)
    {
        copyouts(nfa, to, from, 0);
        return;
    }
    else
    {
        copyins(nfa, from, to, 0);
        return;
    }
}

static void specialcolors

(

struct nfa *

nfa

)

[static]

Definition at line 785 of file regc_nfa.c.

References assert, nfa::bos, nfa::cm, COLORLESS, nfa::eos, NULL, nfa::parent, and pseudocolor().

{
    /* false colors for BOS, BOL, EOS, EOL */
    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 int TooManyStates

(

struct nfa *

nfa

)

[static]

Definition at line 96 of file regc_nfa.c.

References NULL, nfa::parent, and nfa::size.

Referenced by newstate().

{
    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;
}