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