| 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