shared_source/tcl_base/rege_dfa.c

/* $Header: /cvsroot/esrg/sfesrg/esrgpcpj/shared/tcl_base/rege_dfa.c,v 1.1.1.1 2001/06/13 04:32:30 dtashley Exp $ */

/*
 * DFA routines
 * This file is #included by regexec.c.
 *
 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
 * 
 * Development of this software was funded, in part, by Cray Research Inc.,
 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
 * Corporation, none of whom are responsible for the results.  The author
 * thanks all of them. 
 * 
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 * 
 * I'd appreciate being given credit for this package in the documentation
 * of software which uses it, but that is not a requirement.
 * 
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

/*
 - longest - longest-preferred matching engine
 ^ static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *);
 */
static chr *                    /* endpoint, or NULL */
longest(v, d, start, stop, hitstopp)
struct vars *v;                 /* used only for debug and exec flags */
struct dfa *d;
chr *start;                     /* where the match should start */
chr *stop;                      /* match must end at or before here */
int *hitstopp;                  /* record whether hit v->stop, if non-NULL */
{
        chr *cp;
        chr *realstop = (stop == v->stop) ? stop : stop + 1;
        color co;
        struct sset *css;
        struct sset *ss;
        chr *post;
        int i;
        struct colormap *cm = d->cm;

        /* initialize */
        css = initialize(v, d, start);
        cp = start;
        if (hitstopp != NULL)
                *hitstopp = 0;

        /* startup */
        FDEBUG(("+++ startup +++\n"));
        if (cp == v->start) {
                co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];
                FDEBUG(("color %ld\n", (long)co));
        } else {
                co = GETCOLOR(cm, *(cp - 1));
                FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));
        }
        css = miss(v, d, css, co, cp, start);
        if (css == NULL)
                return NULL;
        css->lastseen = cp;

        /* main loop */
        if (v->eflags&REG_FTRACE)
                while (cp < realstop) {
                        FDEBUG(("+++ at c%d +++\n", css - d->ssets));
                        co = GETCOLOR(cm, *cp);
                        FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
                        ss = css->outs[co];
                        if (ss == NULL) {
                                ss = miss(v, d, css, co, cp+1, start);
                                if (ss == NULL)
                                        break;  /* NOTE BREAK OUT */
                        }
                        cp++;
                        ss->lastseen = cp;
                        css = ss;
                }
        else
                while (cp < realstop) {
                        co = GETCOLOR(cm, *cp);
                        ss = css->outs[co];
                        if (ss == NULL) {
                                ss = miss(v, d, css, co, cp+1, start);
                                if (ss == NULL)
                                        break;  /* NOTE BREAK OUT */
                        }
                        cp++;
                        ss->lastseen = cp;
                        css = ss;
                }

        /* shutdown */
        FDEBUG(("+++ shutdown at c%d +++\n", css - d->ssets));
        if (cp == v->stop && stop == v->stop) {
                if (hitstopp != NULL)
                        *hitstopp = 1;
                co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];
                FDEBUG(("color %ld\n", (long)co));
                ss = miss(v, d, css, co, cp, start);
                /* special case:  match ended at eol? */
                if (ss != NULL && (ss->flags&POSTSTATE))
                        return cp;
                else if (ss != NULL)
                        ss->lastseen = cp;      /* to be tidy */
        }

        /* find last match, if any */
        post = d->lastpost;
        for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)
                if ((ss->flags&POSTSTATE) && post != ss->lastseen &&
                                        (post == NULL || post < ss->lastseen))
                        post = ss->lastseen;
        if (post != NULL)               /* found one */
                return post - 1;

        return NULL;
}

/*
 - shortest - shortest-preferred matching engine
 ^ static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *,
 ^      chr **, int *);
 */
static chr *                    /* endpoint, or NULL */
shortest(v, d, start, min, max, coldp, hitstopp)
struct vars *v;
struct dfa *d;
chr *start;                     /* where the match should start */
chr *min;                       /* match must end at or after here */
chr *max;                       /* match must end at or before here */
chr **coldp;                    /* store coldstart pointer here, if nonNULL */
int *hitstopp;                  /* record whether hit v->stop, if non-NULL */
{
        chr *cp;
        chr *realmin = (min == v->stop) ? min : min + 1;
        chr *realmax = (max == v->stop) ? max : max + 1;
        color co;
        struct sset *css;
        struct sset *ss;
        struct colormap *cm = d->cm;

        /* initialize */
        css = initialize(v, d, start);
        cp = start;
        if (hitstopp != NULL)
                *hitstopp = 0;

        /* startup */
        FDEBUG(("--- startup ---\n"));
        if (cp == v->start) {
                co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];
                FDEBUG(("color %ld\n", (long)co));
        } else {
                co = GETCOLOR(cm, *(cp - 1));
                FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));
        }
        css = miss(v, d, css, co, cp, start);
        if (css == NULL)
                return NULL;
        css->lastseen = cp;
        ss = css;

        /* main loop */
        if (v->eflags&REG_FTRACE)
                while (cp < realmax) {
                        FDEBUG(("--- at c%d ---\n", css - d->ssets));
                        co = GETCOLOR(cm, *cp);
                        FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
                        ss = css->outs[co];
                        if (ss == NULL) {
                                ss = miss(v, d, css, co, cp+1, start);
                                if (ss == NULL)
                                        break;  /* NOTE BREAK OUT */
                        }
                        cp++;
                        ss->lastseen = cp;
                        css = ss;
                        if ((ss->flags&POSTSTATE) && cp >= realmin)
                                break;          /* NOTE BREAK OUT */
                }
        else
                while (cp < realmax) {
                        co = GETCOLOR(cm, *cp);
                        ss = css->outs[co];
                        if (ss == NULL) {
                                ss = miss(v, d, css, co, cp+1, start);
                                if (ss == NULL)
                                        break;  /* NOTE BREAK OUT */
                        }
                        cp++;
                        ss->lastseen = cp;
                        css = ss;
                        if ((ss->flags&POSTSTATE) && cp >= realmin)
                                break;          /* NOTE BREAK OUT */
                }

        if (ss == NULL)
                return NULL;

        if (coldp != NULL)      /* report last no-progress state set, if any */
                *coldp = lastcold(v, d);

        if ((ss->flags&POSTSTATE) && cp > min) {
                assert(cp >= realmin);
                cp--;
        } else if (cp == v->stop && max == v->stop) {
                co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];
                FDEBUG(("color %ld\n", (long)co));
                ss = miss(v, d, css, co, cp, start);
                /* match might have ended at eol */
                if ((ss == NULL || !(ss->flags&POSTSTATE)) && hitstopp != NULL)
                        *hitstopp = 1;
        }

        if (ss == NULL || !(ss->flags&POSTSTATE))
                return NULL;

        return cp;
}

/*
 - lastcold - determine last point at which no progress had been made
 ^ static chr *lastcold(struct vars *, struct dfa *);
 */
static chr *                    /* endpoint, or NULL */
lastcold(v, d)
struct vars *v;
struct dfa *d;
{
        struct sset *ss;
        chr *nopr;
        int i;

        nopr = d->lastnopr;
        if (nopr == NULL)
                nopr = v->start;
        for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)
                if ((ss->flags&NOPROGRESS) && nopr < ss->lastseen)
                        nopr = ss->lastseen;
        return nopr;
}

/*
 - newdfa - set up a fresh DFA
 ^ static struct dfa *newdfa(struct vars *, struct cnfa *,
 ^      struct colormap *, struct smalldfa *);
 */
static struct dfa *
newdfa(v, cnfa, cm, small)
struct vars *v;
struct cnfa *cnfa;
struct colormap *cm;
struct smalldfa *small;         /* preallocated space, may be NULL */
{
        struct dfa *d;
        size_t nss = cnfa->nstates * 2;
        int wordsper = (cnfa->nstates + UBITS - 1) / UBITS;
        struct smalldfa *smallwas = small;

        assert(cnfa != NULL && cnfa->nstates != 0);

        if (nss <= FEWSTATES && cnfa->ncolors <= FEWCOLORS) {
                assert(wordsper == 1);
                if (small == NULL) {
                        small = (struct smalldfa *)MALLOC(
                                                sizeof(struct smalldfa));
                        if (small == NULL) {
                                ERR(REG_ESPACE);
                                return NULL;
                        }
                }
                d = &small->dfa;
                d->ssets = small->ssets;
                d->statesarea = small->statesarea;
                d->work = &d->statesarea[nss];
                d->outsarea = small->outsarea;
                d->incarea = small->incarea;
                d->cptsmalloced = 0;
                d->mallocarea = (smallwas == NULL) ? (char *)small : NULL;
        } else {
                d = (struct dfa *)MALLOC(sizeof(struct dfa));
                if (d == NULL) {
                        ERR(REG_ESPACE);
                        return NULL;
                }
                d->ssets = (struct sset *)MALLOC(nss * sizeof(struct sset));
                d->statesarea = (unsigned *)MALLOC((nss+WORK) * wordsper *
                                                        sizeof(unsigned));
                d->work = &d->statesarea[nss * wordsper];
                d->outsarea = (struct sset **)MALLOC(nss * cnfa->ncolors *
                                                        sizeof(struct sset *));
                d->incarea = (struct arcp *)MALLOC(nss * cnfa->ncolors *
                                                        sizeof(struct arcp));
                d->cptsmalloced = 1;
                d->mallocarea = (char *)d;
                if (d->ssets == NULL || d->statesarea == NULL ||
                                d->outsarea == NULL || d->incarea == NULL) {
                        freedfa(d);
                        ERR(REG_ESPACE);
                        return NULL;
                }
        }

        d->nssets = (v->eflags&REG_SMALL) ? 7 : nss;
        d->nssused = 0;
        d->nstates = cnfa->nstates;
        d->ncolors = cnfa->ncolors;
        d->wordsper = wordsper;
        d->cnfa = cnfa;
        d->cm = cm;
        d->lastpost = NULL;
        d->lastnopr = NULL;
        d->search = d->ssets;

        /* initialization of sset fields is done as needed */

        return d;
}

/*
 - freedfa - free a DFA
 ^ static VOID freedfa(struct dfa *);
 */
static VOID
freedfa(d)
struct dfa *d;
{
        if (d->cptsmalloced) {
                if (d->ssets != NULL)
                        FREE(d->ssets);
                if (d->statesarea != NULL)
                        FREE(d->statesarea);
                if (d->outsarea != NULL)
                        FREE(d->outsarea);
                if (d->incarea != NULL)
                        FREE(d->incarea);
        }

        if (d->mallocarea != NULL)
                FREE(d->mallocarea);
}

/*
 - hash - construct a hash code for a bitvector
 * There are probably better ways, but they're more expensive.
 ^ static unsigned hash(unsigned *, int);
 */
static unsigned
hash(uv, n)
unsigned *uv;
int n;
{
        int i;
        unsigned h;

        h = 0;
        for (i = 0; i < n; i++)
                h ^= uv[i];
        return h;
}

/*
 - initialize - hand-craft a cache entry for startup, otherwise get ready
 ^ static struct sset *initialize(struct vars *, struct dfa *, chr *);
 */
static struct sset *
initialize(v, d, start)
struct vars *v;                 /* used only for debug flags */
struct dfa *d;
chr *start;
{
        struct sset *ss;
        int i;

        /* is previous one still there? */
        if (d->nssused > 0 && (d->ssets[0].flags&STARTER))
                ss = &d->ssets[0];
        else {                          /* no, must (re)build it */
                ss = getvacant(v, d, start, start);
                for (i = 0; i < d->wordsper; i++)
                        ss->states[i] = 0;
                BSET(ss->states, d->cnfa->pre);
                ss->hash = HASH(ss->states, d->wordsper);
                assert(d->cnfa->pre != d->cnfa->post);
                ss->flags = STARTER|LOCKED|NOPROGRESS;
                /* lastseen dealt with below */
        }

        for (i = 0; i < d->nssused; i++)
                d->ssets[i].lastseen = NULL;
        ss->lastseen = start;           /* maybe untrue, but harmless */
        d->lastpost = NULL;
        d->lastnopr = NULL;
        return ss;
}

/*
 - miss - handle a cache miss
 ^ static struct sset *miss(struct vars *, struct dfa *, struct sset *,
 ^      pcolor, chr *, chr *);
 */
static struct sset *            /* NULL if goes to empty set */
miss(v, d, css, co, cp, start)
struct vars *v;                 /* used only for debug flags */
struct dfa *d;
struct sset *css;
pcolor co;
chr *cp;                        /* next chr */
chr *start;                     /* where the attempt got started */
{
        struct cnfa *cnfa = d->cnfa;
        int i;
        unsigned h;
        struct carc *ca;
        struct sset *p;
        int ispost;
        int noprogress;
        int gotstate;
        int dolacons;
        int sawlacons;

        /* for convenience, we can be called even if it might not be a miss */
        if (css->outs[co] != NULL) {
                FDEBUG(("hit\n"));
                return css->outs[co];
        }
        FDEBUG(("miss\n"));

        /* first, what set of states would we end up in? */
        for (i = 0; i < d->wordsper; i++)
                d->work[i] = 0;
        ispost = 0;
        noprogress = 1;
        gotstate = 0;
        for (i = 0; i < d->nstates; i++)
                if (ISBSET(css->states, i))
                        for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++)
                                if (ca->co == co) {
                                        BSET(d->work, ca->to);
                                        gotstate = 1;
                                        if (ca->to == cnfa->post)
                                                ispost = 1;
                                        if (!cnfa->states[ca->to]->co)
                                                noprogress = 0;
                                        FDEBUG(("%d -> %d\n", i, ca->to));
                                }
        dolacons = (gotstate) ? (cnfa->flags&HASLACONS) : 0;
        sawlacons = 0;
        while (dolacons) {              /* transitive closure */
                dolacons = 0;
                for (i = 0; i < d->nstates; i++)
                        if (ISBSET(d->work, i))
                                for (ca = cnfa->states[i]+1; ca->co != COLORLESS;
                                                                        ca++) {
                                        if (ca->co <= cnfa->ncolors)
                                                continue; /* NOTE CONTINUE */
                                        sawlacons = 1;
                                        if (ISBSET(d->work, ca->to))
                                                continue; /* NOTE CONTINUE */
                                        if (!lacon(v, cnfa, cp, ca->co))
                                                continue; /* NOTE CONTINUE */
                                        BSET(d->work, ca->to);
                                        dolacons = 1;
                                        if (ca->to == cnfa->post)
                                                ispost = 1;
                                        if (!cnfa->states[ca->to]->co)
                                                noprogress = 0;
                                        FDEBUG(("%d :> %d\n", i, ca->to));
                                }
        }
        if (!gotstate)
                return NULL;
        h = HASH(d->work, d->wordsper);

        /* next, is that in the cache? */
        for (p = d->ssets, i = d->nssused; i > 0; p++, i--)
                if (HIT(h, d->work, p, d->wordsper)) {
                        FDEBUG(("cached c%d\n", p - d->ssets));
                        break;                  /* NOTE BREAK OUT */
                }
        if (i == 0) {           /* nope, need a new cache entry */
                p = getvacant(v, d, cp, start);
                assert(p != css);
                for (i = 0; i < d->wordsper; i++)
                        p->states[i] = d->work[i];
                p->hash = h;
                p->flags = (ispost) ? POSTSTATE : 0;
                if (noprogress)
                        p->flags |= NOPROGRESS;
                /* lastseen to be dealt with by caller */
        }

        if (!sawlacons) {               /* lookahead conds. always cache miss */
                FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, p - d->ssets));
                css->outs[co] = p;
                css->inchain[co] = p->ins;
                p->ins.ss = css;
                p->ins.co = (color)co;
        }
        return p;
}

/*
 - lacon - lookahead-constraint checker for miss()
 ^ static int lacon(struct vars *, struct cnfa *, chr *, pcolor);
 */
static int                      /* predicate:  constraint satisfied? */
lacon(v, pcnfa, cp, co)
struct vars *v;
struct cnfa *pcnfa;             /* parent cnfa */
chr *cp;
pcolor co;                      /* "color" of the lookahead constraint */
{
        int n;
        struct subre *sub;
        struct dfa *d;
        struct smalldfa sd;
        chr *end;

        n = co - pcnfa->ncolors;
        assert(n < v->g->nlacons && v->g->lacons != NULL);
        FDEBUG(("=== testing lacon %d\n", n));
        sub = &v->g->lacons[n];
        d = newdfa(v, &sub->cnfa, &v->g->cmap, &sd);
        if (d == NULL) {
                ERR(REG_ESPACE);
                return 0;
        }
        end = longest(v, d, cp, v->stop, (int *)NULL);
        freedfa(d);
        FDEBUG(("=== lacon %d match %d\n", n, (end != NULL)));
        return (sub->subno) ? (end != NULL) : (end == NULL);
}

/*
 - getvacant - get a vacant state set
 * This routine clears out the inarcs and outarcs, but does not otherwise
 * clear the innards of the state set -- that's up to the caller.
 ^ static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);
 */
static struct sset *
getvacant(v, d, cp, start)
struct vars *v;                 /* used only for debug flags */
struct dfa *d;
chr *cp;
chr *start;
{
        int i;
        struct sset *ss;
        struct sset *p;
        struct arcp ap;
        struct arcp lastap;
        color co;

        ss = pickss(v, d, cp, start);
        assert(!(ss->flags&LOCKED));

        /* clear out its inarcs, including self-referential ones */
        ap = ss->ins;
        while ((p = ap.ss) != NULL) {
                co = ap.co;
                FDEBUG(("zapping c%d's %ld outarc\n", p - d->ssets, (long)co));
                p->outs[co] = NULL;
                ap = p->inchain[co];
                p->inchain[co].ss = NULL;       /* paranoia */
        }
        ss->ins.ss = NULL;

        /* take it off the inarc chains of the ssets reached by its outarcs */
        for (i = 0; i < d->ncolors; i++) {
                p = ss->outs[i];
                assert(p != ss);                /* not self-referential */
                if (p == NULL)
                        continue;               /* NOTE CONTINUE */
                FDEBUG(("del outarc %d from c%d's in chn\n", i, p - d->ssets));
                if (p->ins.ss == ss && p->ins.co == i)
                        p->ins = ss->inchain[i];
                else {
                        assert(p->ins.ss != NULL);
                        for (ap = p->ins; ap.ss != NULL &&
                                                !(ap.ss == ss && ap.co == i);
                                                ap = ap.ss->inchain[ap.co])
                                lastap = ap;
                        assert(ap.ss != NULL);
                        lastap.ss->inchain[lastap.co] = ss->inchain[i];
                }
                ss->outs[i] = NULL;
                ss->inchain[i].ss = NULL;
        }

        /* if ss was a success state, may need to remember location */
        if ((ss->flags&POSTSTATE) && ss->lastseen != d->lastpost &&
                        (d->lastpost == NULL || d->lastpost < ss->lastseen))
                d->lastpost = ss->lastseen;

        /* likewise for a no-progress state */
        if ((ss->flags&NOPROGRESS) && ss->lastseen != d->lastnopr &&
                        (d->lastnopr == NULL || d->lastnopr < ss->lastseen))
                d->lastnopr = ss->lastseen;

        return ss;
}

/*
 - pickss - pick the next stateset to be used
 ^ static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);
 */
static struct sset *
pickss(v, d, cp, start)
struct vars *v;                 /* used only for debug flags */
struct dfa *d;
chr *cp;
chr *start;
{
        int i;
        struct sset *ss;
        struct sset *end;
        chr *ancient;

        /* shortcut for cases where cache isn't full */
        if (d->nssused < d->nssets) {
                i = d->nssused;
                d->nssused++;
                ss = &d->ssets[i];
                FDEBUG(("new c%d\n", i));
                /* set up innards */
                ss->states = &d->statesarea[i * d->wordsper];
                ss->flags = 0;
                ss->ins.ss = NULL;
                ss->ins.co = WHITE;             /* give it some value */
                ss->outs = &d->outsarea[i * d->ncolors];
                ss->inchain = &d->incarea[i * d->ncolors];
                for (i = 0; i < d->ncolors; i++) {
                        ss->outs[i] = NULL;
                        ss->inchain[i].ss = NULL;
                }
                return ss;
        }

        /* look for oldest, or old enough anyway */
        if (cp - start > d->nssets*2/3)         /* oldest 33% are expendable */
                ancient = cp - d->nssets*2/3;
        else
                ancient = start;
        for (ss = d->search, end = &d->ssets[d->nssets]; ss < end; ss++)
                if ((ss->lastseen == NULL || ss->lastseen < ancient) &&
                                                        !(ss->flags&LOCKED)) {
                        d->search = ss + 1;
                        FDEBUG(("replacing c%d\n", ss - d->ssets));
                        return ss;
                }
        for (ss = d->ssets, end = d->search; ss < end; ss++)
                if ((ss->lastseen == NULL || ss->lastseen < ancient) &&
                                                        !(ss->flags&LOCKED)) {
                        d->search = ss + 1;
                        FDEBUG(("replacing c%d\n", ss - d->ssets));
                        return ss;
                }

        /* nobody's old enough?!? -- something's really wrong */
        FDEBUG(("can't find victim to replace!\n"));
        assert(NOTREACHED);
        ERR(REG_ASSERT);
        return d->ssets;
}

/* $History: rege_dfa.c $
 * 
 * *****************  Version 1  *****************
 * User: Dtashley     Date: 1/02/01    Time: 12:10a
 * Created in $/IjuScripter, IjuConsole/Source/Tcl Base
 * Initial check-in.
 */ 

/* End of REGE_DFA.C */
1	dashley	25	/* $Header: /cvsroot/esrg/sfesrg/esrgpcpj/shared/tcl_base/rege_dfa.c,v 1.1.1.1 2001/06/13 04:32:30 dtashley Exp $ */
2
3			/*
4			* DFA routines
5			* This file is #included by regexec.c.
6			*
7			* Copyright (c) 1998, 1999 Henry Spencer. All rights reserved.
8			*
9			* Development of this software was funded, in part, by Cray Research Inc.,
10			* UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
11			* Corporation, none of whom are responsible for the results. The author
12			* thanks all of them.
13			*
14			* Redistribution and use in source and binary forms -- with or without
15			* modification -- are permitted for any purpose, provided that
16			* redistributions in source form retain this entire copyright notice and
17			* indicate the origin and nature of any modifications.
18			*
19			* I'd appreciate being given credit for this package in the documentation
20			* of software which uses it, but that is not a requirement.
21			*
22			* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
23			* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
24			* AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
25			* HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26			* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27			* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
28			* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
29			* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
30			* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
31			* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32			*
33			*/
34
35			/*
36			- longest - longest-preferred matching engine
37			^ static chr longest(struct vars , struct dfa , chr , chr , int );
38			*/
39			static chr * /* endpoint, or NULL */
40			longest(v, d, start, stop, hitstopp)
41			struct vars v; / used only for debug and exec flags */
42			struct dfa *d;
43			chr start; / where the match should start */
44			chr stop; / match must end at or before here */
45			int hitstopp; / record whether hit v->stop, if non-NULL */
46			{
47			chr *cp;
48			chr *realstop = (stop == v->stop) ? stop : stop + 1;
49			color co;
50			struct sset *css;
51			struct sset *ss;
52			chr *post;
53			int i;
54			struct colormap *cm = d->cm;
55
56			/* initialize */
57			css = initialize(v, d, start);
58			cp = start;
59			if (hitstopp != NULL)
60			*hitstopp = 0;
61
62			/* startup */
63			FDEBUG(("+++ startup +++\n"));
64			if (cp == v->start) {
65			co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];
66			FDEBUG(("color %ld\n", (long)co));
67			} else {
68			co = GETCOLOR(cm, *(cp - 1));
69			FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));
70			}
71			css = miss(v, d, css, co, cp, start);
72			if (css == NULL)
73			return NULL;
74			css->lastseen = cp;
75
76			/* main loop */
77			if (v->eflags&REG_FTRACE)
78			while (cp < realstop) {
79			FDEBUG(("+++ at c%d +++\n", css - d->ssets));
80			co = GETCOLOR(cm, *cp);
81			FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
82			ss = css->outs[co];
83			if (ss == NULL) {
84			ss = miss(v, d, css, co, cp+1, start);
85			if (ss == NULL)
86			break; /* NOTE BREAK OUT */
87			}
88			cp++;
89			ss->lastseen = cp;
90			css = ss;
91			}
92			else
93			while (cp < realstop) {
94			co = GETCOLOR(cm, *cp);
95			ss = css->outs[co];
96			if (ss == NULL) {
97			ss = miss(v, d, css, co, cp+1, start);
98			if (ss == NULL)
99			break; /* NOTE BREAK OUT */
100			}
101			cp++;
102			ss->lastseen = cp;
103			css = ss;
104			}
105
106			/* shutdown */
107			FDEBUG(("+++ shutdown at c%d +++\n", css - d->ssets));
108			if (cp == v->stop && stop == v->stop) {
109			if (hitstopp != NULL)
110			*hitstopp = 1;
111			co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];
112			FDEBUG(("color %ld\n", (long)co));
113			ss = miss(v, d, css, co, cp, start);
114			/* special case: match ended at eol? */
115			if (ss != NULL && (ss->flags&POSTSTATE))
116			return cp;
117			else if (ss != NULL)
118			ss->lastseen = cp; /* to be tidy */
119			}
120
121			/* find last match, if any */
122			post = d->lastpost;
123			for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)
124			if ((ss->flags&POSTSTATE) && post != ss->lastseen &&
125			(post == NULL \|\| post < ss->lastseen))
126			post = ss->lastseen;
127			if (post != NULL) /* found one */
128			return post - 1;
129
130			return NULL;
131			}
132
133			/*
134			- shortest - shortest-preferred matching engine
135			^ static chr shortest(struct vars , struct dfa , chr , chr , chr ,
136			^ chr *, int );
137			*/
138			static chr * /* endpoint, or NULL */
139			shortest(v, d, start, min, max, coldp, hitstopp)
140			struct vars *v;
141			struct dfa *d;
142			chr start; / where the match should start */
143			chr min; / match must end at or after here */
144			chr max; / match must end at or before here */
145			chr *coldp; / store coldstart pointer here, if nonNULL */
146			int hitstopp; / record whether hit v->stop, if non-NULL */
147			{
148			chr *cp;
149			chr *realmin = (min == v->stop) ? min : min + 1;
150			chr *realmax = (max == v->stop) ? max : max + 1;
151			color co;
152			struct sset *css;
153			struct sset *ss;
154			struct colormap *cm = d->cm;
155
156			/* initialize */
157			css = initialize(v, d, start);
158			cp = start;
159			if (hitstopp != NULL)
160			*hitstopp = 0;
161
162			/* startup */
163			FDEBUG(("--- startup ---\n"));
164			if (cp == v->start) {
165			co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];
166			FDEBUG(("color %ld\n", (long)co));
167			} else {
168			co = GETCOLOR(cm, *(cp - 1));
169			FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));
170			}
171			css = miss(v, d, css, co, cp, start);
172			if (css == NULL)
173			return NULL;
174			css->lastseen = cp;
175			ss = css;
176
177			/* main loop */
178			if (v->eflags&REG_FTRACE)
179			while (cp < realmax) {
180			FDEBUG(("--- at c%d ---\n", css - d->ssets));
181			co = GETCOLOR(cm, *cp);
182			FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
183			ss = css->outs[co];
184			if (ss == NULL) {
185			ss = miss(v, d, css, co, cp+1, start);
186			if (ss == NULL)
187			break; /* NOTE BREAK OUT */
188			}
189			cp++;
190			ss->lastseen = cp;
191			css = ss;
192			if ((ss->flags&POSTSTATE) && cp >= realmin)
193			break; /* NOTE BREAK OUT */
194			}
195			else
196			while (cp < realmax) {
197			co = GETCOLOR(cm, *cp);
198			ss = css->outs[co];
199			if (ss == NULL) {
200			ss = miss(v, d, css, co, cp+1, start);
201			if (ss == NULL)
202			break; /* NOTE BREAK OUT */
203			}
204			cp++;
205			ss->lastseen = cp;
206			css = ss;
207			if ((ss->flags&POSTSTATE) && cp >= realmin)
208			break; /* NOTE BREAK OUT */
209			}
210
211			if (ss == NULL)
212			return NULL;
213
214			if (coldp != NULL) /* report last no-progress state set, if any */
215			*coldp = lastcold(v, d);
216
217			if ((ss->flags&POSTSTATE) && cp > min) {
218			assert(cp >= realmin);
219			cp--;
220			} else if (cp == v->stop && max == v->stop) {
221			co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];
222			FDEBUG(("color %ld\n", (long)co));
223			ss = miss(v, d, css, co, cp, start);
224			/* match might have ended at eol */
225			if ((ss == NULL \|\| !(ss->flags&POSTSTATE)) && hitstopp != NULL)
226			*hitstopp = 1;
227			}
228
229			if (ss == NULL \|\| !(ss->flags&POSTSTATE))
230			return NULL;
231
232			return cp;
233			}
234
235			/*
236			- lastcold - determine last point at which no progress had been made
237			^ static chr lastcold(struct vars , struct dfa *);
238			*/
239			static chr * /* endpoint, or NULL */
240			lastcold(v, d)
241			struct vars *v;
242			struct dfa *d;
243			{
244			struct sset *ss;
245			chr *nopr;
246			int i;
247
248			nopr = d->lastnopr;
249			if (nopr == NULL)
250			nopr = v->start;
251			for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)
252			if ((ss->flags&NOPROGRESS) && nopr < ss->lastseen)
253			nopr = ss->lastseen;
254			return nopr;
255			}
256
257			/*
258			- newdfa - set up a fresh DFA
259			^ static struct dfa newdfa(struct vars , struct cnfa *,
260			^ struct colormap , struct smalldfa );
261			*/
262			static struct dfa *
263			newdfa(v, cnfa, cm, small)
264			struct vars *v;
265			struct cnfa *cnfa;
266			struct colormap *cm;
267			struct smalldfa small; / preallocated space, may be NULL */
268			{
269			struct dfa *d;
270			size_t nss = cnfa->nstates * 2;
271			int wordsper = (cnfa->nstates + UBITS - 1) / UBITS;
272			struct smalldfa *smallwas = small;
273
274			assert(cnfa != NULL && cnfa->nstates != 0);
275
276			if (nss <= FEWSTATES && cnfa->ncolors <= FEWCOLORS) {
277			assert(wordsper == 1);
278			if (small == NULL) {
279			small = (struct smalldfa *)MALLOC(
280			sizeof(struct smalldfa));
281			if (small == NULL) {
282			ERR(REG_ESPACE);
283			return NULL;
284			}
285			}
286			d = &small->dfa;
287			d->ssets = small->ssets;
288			d->statesarea = small->statesarea;
289			d->work = &d->statesarea[nss];
290			d->outsarea = small->outsarea;
291			d->incarea = small->incarea;
292			d->cptsmalloced = 0;
293			d->mallocarea = (smallwas == NULL) ? (char *)small : NULL;
294			} else {
295			d = (struct dfa *)MALLOC(sizeof(struct dfa));
296			if (d == NULL) {
297			ERR(REG_ESPACE);
298			return NULL;
299			}
300			d->ssets = (struct sset )MALLOC(nss sizeof(struct sset));
301			d->statesarea = (unsigned )MALLOC((nss+WORK) wordsper *
302			sizeof(unsigned));
303			d->work = &d->statesarea[nss * wordsper];
304			d->outsarea = (struct sset *)MALLOC(nss cnfa->ncolors *
305			sizeof(struct sset *));
306			d->incarea = (struct arcp )MALLOC(nss cnfa->ncolors *
307			sizeof(struct arcp));
308			d->cptsmalloced = 1;
309			d->mallocarea = (char *)d;
310			if (d->ssets == NULL \|\| d->statesarea == NULL \|\|
311			d->outsarea == NULL \|\| d->incarea == NULL) {
312			freedfa(d);
313			ERR(REG_ESPACE);
314			return NULL;
315			}
316			}
317
318			d->nssets = (v->eflags&REG_SMALL) ? 7 : nss;
319			d->nssused = 0;
320			d->nstates = cnfa->nstates;
321			d->ncolors = cnfa->ncolors;
322			d->wordsper = wordsper;
323			d->cnfa = cnfa;
324			d->cm = cm;
325			d->lastpost = NULL;
326			d->lastnopr = NULL;
327			d->search = d->ssets;
328
329			/* initialization of sset fields is done as needed */
330
331			return d;
332			}
333
334			/*
335			- freedfa - free a DFA
336			^ static VOID freedfa(struct dfa *);
337			*/
338			static VOID
339			freedfa(d)
340			struct dfa *d;
341			{
342			if (d->cptsmalloced) {
343			if (d->ssets != NULL)
344			FREE(d->ssets);
345			if (d->statesarea != NULL)
346			FREE(d->statesarea);
347			if (d->outsarea != NULL)
348			FREE(d->outsarea);
349			if (d->incarea != NULL)
350			FREE(d->incarea);
351			}
352
353			if (d->mallocarea != NULL)
354			FREE(d->mallocarea);
355			}
356
357			/*
358			- hash - construct a hash code for a bitvector
359			* There are probably better ways, but they're more expensive.
360			^ static unsigned hash(unsigned *, int);
361			*/
362			static unsigned
363			hash(uv, n)
364			unsigned *uv;
365			int n;
366			{
367			int i;
368			unsigned h;
369
370			h = 0;
371			for (i = 0; i < n; i++)
372			h ^= uv[i];
373			return h;
374			}
375
376			/*
377			- initialize - hand-craft a cache entry for startup, otherwise get ready
378			^ static struct sset initialize(struct vars , struct dfa , chr );
379			*/
380			static struct sset *
381			initialize(v, d, start)
382			struct vars v; / used only for debug flags */
383			struct dfa *d;
384			chr *start;
385			{
386			struct sset *ss;
387			int i;
388
389			/* is previous one still there? */
390			if (d->nssused > 0 && (d->ssets[0].flags&STARTER))
391			ss = &d->ssets[0];
392			else { /* no, must (re)build it */
393			ss = getvacant(v, d, start, start);
394			for (i = 0; i < d->wordsper; i++)
395			ss->states[i] = 0;
396			BSET(ss->states, d->cnfa->pre);
397			ss->hash = HASH(ss->states, d->wordsper);
398			assert(d->cnfa->pre != d->cnfa->post);
399			ss->flags = STARTER\|LOCKED\|NOPROGRESS;
400			/* lastseen dealt with below */
401			}
402
403			for (i = 0; i < d->nssused; i++)
404			d->ssets[i].lastseen = NULL;
405			ss->lastseen = start; /* maybe untrue, but harmless */
406			d->lastpost = NULL;
407			d->lastnopr = NULL;
408			return ss;
409			}
410
411			/*
412			- miss - handle a cache miss
413			^ static struct sset miss(struct vars , struct dfa , struct sset ,
414			^ pcolor, chr , chr );
415			*/
416			static struct sset * /* NULL if goes to empty set */
417			miss(v, d, css, co, cp, start)
418			struct vars v; / used only for debug flags */
419			struct dfa *d;
420			struct sset *css;
421			pcolor co;
422			chr cp; / next chr */
423			chr start; / where the attempt got started */
424			{
425			struct cnfa *cnfa = d->cnfa;
426			int i;
427			unsigned h;
428			struct carc *ca;
429			struct sset *p;
430			int ispost;
431			int noprogress;
432			int gotstate;
433			int dolacons;
434			int sawlacons;
435
436			/* for convenience, we can be called even if it might not be a miss */
437			if (css->outs[co] != NULL) {
438			FDEBUG(("hit\n"));
439			return css->outs[co];
440			}
441			FDEBUG(("miss\n"));
442
443			/* first, what set of states would we end up in? */
444			for (i = 0; i < d->wordsper; i++)
445			d->work[i] = 0;
446			ispost = 0;
447			noprogress = 1;
448			gotstate = 0;
449			for (i = 0; i < d->nstates; i++)
450			if (ISBSET(css->states, i))
451			for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++)
452			if (ca->co == co) {
453			BSET(d->work, ca->to);
454			gotstate = 1;
455			if (ca->to == cnfa->post)
456			ispost = 1;
457			if (!cnfa->states[ca->to]->co)
458			noprogress = 0;
459			FDEBUG(("%d -> %d\n", i, ca->to));
460			}
461			dolacons = (gotstate) ? (cnfa->flags&HASLACONS) : 0;
462			sawlacons = 0;
463			while (dolacons) { /* transitive closure */
464			dolacons = 0;
465			for (i = 0; i < d->nstates; i++)
466			if (ISBSET(d->work, i))
467			for (ca = cnfa->states[i]+1; ca->co != COLORLESS;
468			ca++) {
469			if (ca->co <= cnfa->ncolors)
470			continue; /* NOTE CONTINUE */
471			sawlacons = 1;
472			if (ISBSET(d->work, ca->to))
473			continue; /* NOTE CONTINUE */
474			if (!lacon(v, cnfa, cp, ca->co))
475			continue; /* NOTE CONTINUE */
476			BSET(d->work, ca->to);
477			dolacons = 1;
478			if (ca->to == cnfa->post)
479			ispost = 1;
480			if (!cnfa->states[ca->to]->co)
481			noprogress = 0;
482			FDEBUG(("%d :> %d\n", i, ca->to));
483			}
484			}
485			if (!gotstate)
486			return NULL;
487			h = HASH(d->work, d->wordsper);
488
489			/* next, is that in the cache? */
490			for (p = d->ssets, i = d->nssused; i > 0; p++, i--)
491			if (HIT(h, d->work, p, d->wordsper)) {
492			FDEBUG(("cached c%d\n", p - d->ssets));
493			break; /* NOTE BREAK OUT */
494			}
495			if (i == 0) { /* nope, need a new cache entry */
496			p = getvacant(v, d, cp, start);
497			assert(p != css);
498			for (i = 0; i < d->wordsper; i++)
499			p->states[i] = d->work[i];
500			p->hash = h;
501			p->flags = (ispost) ? POSTSTATE : 0;
502			if (noprogress)
503			p->flags \|= NOPROGRESS;
504			/* lastseen to be dealt with by caller */
505			}
506
507			if (!sawlacons) { /* lookahead conds. always cache miss */
508			FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, p - d->ssets));
509			css->outs[co] = p;
510			css->inchain[co] = p->ins;
511			p->ins.ss = css;
512			p->ins.co = (color)co;
513			}
514			return p;
515			}
516
517			/*
518			- lacon - lookahead-constraint checker for miss()
519			^ static int lacon(struct vars , struct cnfa , chr *, pcolor);
520			*/
521			static int /* predicate: constraint satisfied? */
522			lacon(v, pcnfa, cp, co)
523			struct vars *v;
524			struct cnfa pcnfa; / parent cnfa */
525			chr *cp;
526			pcolor co; /* "color" of the lookahead constraint */
527			{
528			int n;
529			struct subre *sub;
530			struct dfa *d;
531			struct smalldfa sd;
532			chr *end;
533
534			n = co - pcnfa->ncolors;
535			assert(n < v->g->nlacons && v->g->lacons != NULL);
536			FDEBUG(("=== testing lacon %d\n", n));
537			sub = &v->g->lacons[n];
538			d = newdfa(v, &sub->cnfa, &v->g->cmap, &sd);
539			if (d == NULL) {
540			ERR(REG_ESPACE);
541			return 0;
542			}
543			end = longest(v, d, cp, v->stop, (int *)NULL);
544			freedfa(d);
545			FDEBUG(("=== lacon %d match %d\n", n, (end != NULL)));
546			return (sub->subno) ? (end != NULL) : (end == NULL);
547			}
548
549			/*
550			- getvacant - get a vacant state set
551			* This routine clears out the inarcs and outarcs, but does not otherwise
552			* clear the innards of the state set -- that's up to the caller.
553			^ static struct sset getvacant(struct vars , struct dfa , chr , chr *);
554			*/
555			static struct sset *
556			getvacant(v, d, cp, start)
557			struct vars v; / used only for debug flags */
558			struct dfa *d;
559			chr *cp;
560			chr *start;
561			{
562			int i;
563			struct sset *ss;
564			struct sset *p;
565			struct arcp ap;
566			struct arcp lastap;
567			color co;
568
569			ss = pickss(v, d, cp, start);
570			assert(!(ss->flags&LOCKED));
571
572			/* clear out its inarcs, including self-referential ones */
573			ap = ss->ins;
574			while ((p = ap.ss) != NULL) {
575			co = ap.co;
576			FDEBUG(("zapping c%d's %ld outarc\n", p - d->ssets, (long)co));
577			p->outs[co] = NULL;
578			ap = p->inchain[co];
579			p->inchain[co].ss = NULL; /* paranoia */
580			}
581			ss->ins.ss = NULL;
582
583			/* take it off the inarc chains of the ssets reached by its outarcs */
584			for (i = 0; i < d->ncolors; i++) {
585			p = ss->outs[i];
586			assert(p != ss); /* not self-referential */
587			if (p == NULL)
588			continue; /* NOTE CONTINUE */
589			FDEBUG(("del outarc %d from c%d's in chn\n", i, p - d->ssets));
590			if (p->ins.ss == ss && p->ins.co == i)
591			p->ins = ss->inchain[i];
592			else {
593			assert(p->ins.ss != NULL);
594			for (ap = p->ins; ap.ss != NULL &&
595			!(ap.ss == ss && ap.co == i);
596			ap = ap.ss->inchain[ap.co])
597			lastap = ap;
598			assert(ap.ss != NULL);
599			lastap.ss->inchain[lastap.co] = ss->inchain[i];
600			}
601			ss->outs[i] = NULL;
602			ss->inchain[i].ss = NULL;
603			}
604
605			/* if ss was a success state, may need to remember location */
606			if ((ss->flags&POSTSTATE) && ss->lastseen != d->lastpost &&
607			(d->lastpost == NULL \|\| d->lastpost < ss->lastseen))
608			d->lastpost = ss->lastseen;
609
610			/* likewise for a no-progress state */
611			if ((ss->flags&NOPROGRESS) && ss->lastseen != d->lastnopr &&
612			(d->lastnopr == NULL \|\| d->lastnopr < ss->lastseen))
613			d->lastnopr = ss->lastseen;
614
615			return ss;
616			}
617
618			/*
619			- pickss - pick the next stateset to be used
620			^ static struct sset pickss(struct vars , struct dfa , chr , chr *);
621			*/
622			static struct sset *
623			pickss(v, d, cp, start)
624			struct vars v; / used only for debug flags */
625			struct dfa *d;
626			chr *cp;
627			chr *start;
628			{
629			int i;
630			struct sset *ss;
631			struct sset *end;
632			chr *ancient;
633
634			/* shortcut for cases where cache isn't full */
635			if (d->nssused < d->nssets) {
636			i = d->nssused;
637			d->nssused++;
638			ss = &d->ssets[i];
639			FDEBUG(("new c%d\n", i));
640			/* set up innards */
641			ss->states = &d->statesarea[i * d->wordsper];
642			ss->flags = 0;
643			ss->ins.ss = NULL;
644			ss->ins.co = WHITE; /* give it some value */
645			ss->outs = &d->outsarea[i * d->ncolors];
646			ss->inchain = &d->incarea[i * d->ncolors];
647			for (i = 0; i < d->ncolors; i++) {
648			ss->outs[i] = NULL;
649			ss->inchain[i].ss = NULL;
650			}
651			return ss;
652			}
653
654			/* look for oldest, or old enough anyway */
655			if (cp - start > d->nssets2/3) / oldest 33% are expendable */
656			ancient = cp - d->nssets*2/3;
657			else
658			ancient = start;
659			for (ss = d->search, end = &d->ssets[d->nssets]; ss < end; ss++)
660			if ((ss->lastseen == NULL \|\| ss->lastseen < ancient) &&
661			!(ss->flags&LOCKED)) {
662			d->search = ss + 1;
663			FDEBUG(("replacing c%d\n", ss - d->ssets));
664			return ss;
665			}
666			for (ss = d->ssets, end = d->search; ss < end; ss++)
667			if ((ss->lastseen == NULL \|\| ss->lastseen < ancient) &&
668			!(ss->flags&LOCKED)) {
669			d->search = ss + 1;
670			FDEBUG(("replacing c%d\n", ss - d->ssets));
671			return ss;
672			}
673
674			/* nobody's old enough?!? -- something's really wrong */
675			FDEBUG(("can't find victim to replace!\n"));
676			assert(NOTREACHED);
677			ERR(REG_ASSERT);
678			return d->ssets;
679			}
680
681			/* $History: rege_dfa.c $
682			*
683			* *************** Version 1 ***************
684			* User: Dtashley Date: 1/02/01 Time: 12:10a
685			* Created in $/IjuScripter, IjuConsole/Source/Tcl Base
686			* Initial check-in.
687			*/
688
689			/* End of REGE_DFA.C */