Age Owner Branch data TLA Line data Source code
1 : : /*
2 : : * DFA routines
3 : : * This file is #included by regexec.c.
4 : : *
5 : : * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved.
6 : : *
7 : : * Development of this software was funded, in part, by Cray Research Inc.,
8 : : * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
9 : : * Corporation, none of whom are responsible for the results. The author
10 : : * thanks all of them.
11 : : *
12 : : * Redistribution and use in source and binary forms -- with or without
13 : : * modification -- are permitted for any purpose, provided that
14 : : * redistributions in source form retain this entire copyright notice and
15 : : * indicate the origin and nature of any modifications.
16 : : *
17 : : * I'd appreciate being given credit for this package in the documentation
18 : : * of software which uses it, but that is not a requirement.
19 : : *
20 : : * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
21 : : * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
22 : : * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
23 : : * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 : : * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 : : * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
26 : : * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 : : * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 : : * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29 : : * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 : : *
31 : : * src/backend/regex/rege_dfa.c
32 : : *
33 : : */
34 : :
35 : : /*
36 : : * longest - longest-preferred matching engine
37 : : *
38 : : * On success, returns match endpoint address. Returns NULL on no match.
39 : : * Internal errors also return NULL, with v->err set.
40 : : */
41 : : static chr *
3265 tgl@sss.pgh.pa.us 42 :CBC 494614 : longest(struct vars *v,
43 : : struct dfa *d,
44 : : chr *start, /* where the match should start */
45 : : chr *stop, /* match must end at or before here */
46 : : int *hitstopp) /* record whether hit v->stop, if non-NULL */
47 : : {
48 : : chr *cp;
8335 bruce@momjian.us 49 [ + + ]: 494614 : chr *realstop = (stop == v->stop) ? stop : stop + 1;
50 : : color co;
51 : : struct sset *css;
52 : : struct sset *ss;
53 : : chr *post;
54 : : int i;
8515 tgl@sss.pgh.pa.us 55 : 494614 : struct colormap *cm = d->cm;
56 : :
57 : : /* prevent "uninitialized variable" warnings */
3893 58 [ + + ]: 494614 : if (hitstopp != NULL)
59 : 471436 : *hitstopp = 0;
60 : :
61 : : /* if this is a backref to a known string, just match against that */
1915 62 [ + + ]: 494614 : if (d->backno >= 0)
63 : : {
64 [ - + ]: 1120 : assert((size_t) d->backno < v->nmatch);
65 [ + + ]: 1120 : if (v->pmatch[d->backno].rm_so >= 0)
66 : : {
67 : 861 : cp = dfa_backref(v, d, start, start, stop, false);
68 [ + + + - : 861 : if (cp == v->stop && stop == v->stop && hitstopp != NULL)
- + ]
1915 tgl@sss.pgh.pa.us 69 :UBC 0 : *hitstopp = 1;
1915 tgl@sss.pgh.pa.us 70 :CBC 861 : return cp;
71 : : }
72 : : }
73 : :
74 : : /* fast path for matchall NFAs */
1925 75 [ + + ]: 493753 : if (d->cnfa->flags & MATCHALL)
76 : : {
77 : 3437 : size_t nchr = stop - start;
78 : 3437 : size_t maxmatchall = d->cnfa->maxmatchall;
79 : :
80 [ + + ]: 3437 : if (nchr < d->cnfa->minmatchall)
81 : 246 : return NULL;
82 [ + + ]: 3191 : if (maxmatchall == DUPINF)
83 : : {
84 [ + + + + ]: 1937 : if (stop == v->stop && hitstopp != NULL)
85 : 7 : *hitstopp = 1;
86 : : }
87 : : else
88 : : {
89 [ + + + + : 1254 : if (stop == v->stop && nchr <= maxmatchall + 1 && hitstopp != NULL)
+ + ]
90 : 128 : *hitstopp = 1;
91 [ + + ]: 1254 : if (nchr > maxmatchall)
92 : 855 : return start + maxmatchall;
93 : : }
94 : 2336 : return stop;
95 : : }
96 : :
97 : : /* initialize */
8515 98 : 490316 : css = initialize(v, d, start);
3893 99 [ - + ]: 490316 : if (css == NULL)
3893 tgl@sss.pgh.pa.us 100 :UBC 0 : return NULL;
8515 tgl@sss.pgh.pa.us 101 :CBC 490316 : cp = start;
102 : :
103 : : /* startup */
104 : : FDEBUG(("+++ startup +++\n"));
8335 bruce@momjian.us 105 [ + + ]: 490316 : if (cp == v->start)
106 : : {
107 : 2285 : co = d->cnfa->bos[(v->eflags & REG_NOTBOL) ? 0 : 1];
108 : : FDEBUG(("color %ld\n", (long) co));
109 : : }
110 : : else
111 : : {
8515 tgl@sss.pgh.pa.us 112 [ + - ]: 488031 : co = GETCOLOR(cm, *(cp - 1));
113 : : FDEBUG(("char %c, color %ld\n", (char) *(cp - 1), (long) co));
114 : : }
115 : 490316 : css = miss(v, d, css, co, cp, start);
116 [ + + ]: 490316 : if (css == NULL)
117 : 324 : return NULL;
118 : 489992 : css->lastseen = cp;
119 : :
120 : : /*
121 : : * This is the main text-scanning loop. It seems worth having two copies
122 : : * to avoid the overhead of REG_FTRACE tests here, even in REG_DEBUG
123 : : * builds, when you're not actively tracing.
124 : : */
125 : : #ifdef REG_DEBUG
126 : : if (v->eflags & REG_FTRACE)
127 : : {
128 : : while (cp < realstop)
129 : : {
130 : : FDEBUG(("+++ at c%d +++\n", (int) (css - d->ssets)));
131 : : co = GETCOLOR(cm, *cp);
132 : : FDEBUG(("char %c, color %ld\n", (char) *cp, (long) co));
133 : : ss = css->outs[co];
134 : : if (ss == NULL)
135 : : {
136 : : ss = miss(v, d, css, co, cp + 1, start);
137 : : if (ss == NULL)
138 : : break; /* NOTE BREAK OUT */
139 : : }
140 : : cp++;
141 : : ss->lastseen = cp;
142 : : css = ss;
143 : : }
144 : : }
145 : : else
146 : : #endif
147 : : {
8335 bruce@momjian.us 148 [ + + ]: 6128771 : while (cp < realstop)
149 : : {
8515 tgl@sss.pgh.pa.us 150 [ + + ]: 6111196 : co = GETCOLOR(cm, *cp);
151 : 6111196 : ss = css->outs[co];
8335 bruce@momjian.us 152 [ + + ]: 6111196 : if (ss == NULL)
153 : : {
154 : 1598480 : ss = miss(v, d, css, co, cp + 1, start);
8515 tgl@sss.pgh.pa.us 155 [ + + ]: 1598480 : if (ss == NULL)
8335 bruce@momjian.us 156 : 472417 : break; /* NOTE BREAK OUT */
157 : : }
8515 tgl@sss.pgh.pa.us 158 : 5638779 : cp++;
159 : 5638779 : ss->lastseen = cp;
160 : 5638779 : css = ss;
161 : : }
162 : : }
163 : :
3893 164 [ - + ]: 489992 : if (ISERR())
3893 tgl@sss.pgh.pa.us 165 :UBC 0 : return NULL;
166 : :
167 : : /* shutdown */
168 : : FDEBUG(("+++ shutdown at c%d +++\n", (int) (css - d->ssets)));
8335 bruce@momjian.us 169 [ + + + + ]:CBC 489992 : if (cp == v->stop && stop == v->stop)
170 : : {
8515 tgl@sss.pgh.pa.us 171 [ + + ]: 9359 : if (hitstopp != NULL)
172 : 4852 : *hitstopp = 1;
8335 bruce@momjian.us 173 : 9359 : co = d->cnfa->eos[(v->eflags & REG_NOTEOL) ? 0 : 1];
174 : : FDEBUG(("color %ld\n", (long) co));
8515 tgl@sss.pgh.pa.us 175 : 9359 : ss = miss(v, d, css, co, cp, start);
3893 176 [ - + ]: 9359 : if (ISERR())
3893 tgl@sss.pgh.pa.us 177 :UBC 0 : return NULL;
178 : : /* special case: match ended at eol? */
8335 bruce@momjian.us 179 [ + + + - ]:CBC 9359 : if (ss != NULL && (ss->flags & POSTSTATE))
8515 tgl@sss.pgh.pa.us 180 : 5179 : return cp;
181 [ - + ]: 4180 : else if (ss != NULL)
8515 tgl@sss.pgh.pa.us 182 :UBC 0 : ss->lastseen = cp; /* to be tidy */
183 : : }
184 : :
185 : : /* find last match, if any */
8515 tgl@sss.pgh.pa.us 186 :CBC 484813 : post = d->lastpost;
187 [ + + ]: 2531856 : for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)
8335 bruce@momjian.us 188 [ + + + + : 2047043 : if ((ss->flags & POSTSTATE) && post != ss->lastseen &&
+ + ]
189 [ + + ]: 9611 : (post == NULL || post < ss->lastseen))
8515 tgl@sss.pgh.pa.us 190 : 491169 : post = ss->lastseen;
8335 bruce@momjian.us 191 [ + + ]: 484813 : if (post != NULL) /* found one */
8515 tgl@sss.pgh.pa.us 192 : 482104 : return post - 1;
193 : :
194 : 2709 : return NULL;
195 : : }
196 : :
197 : : /*
198 : : * shortest - shortest-preferred matching engine
199 : : *
200 : : * On success, returns match endpoint address. Returns NULL on no match.
201 : : * Internal errors also return NULL, with v->err set.
202 : : */
203 : : static chr *
3265 204 : 5787417 : shortest(struct vars *v,
205 : : struct dfa *d,
206 : : chr *start, /* where the match should start */
207 : : chr *min, /* match must end at or after here */
208 : : chr *max, /* match must end at or before here */
209 : : chr **coldp, /* store coldstart pointer here, if non-NULL */
210 : : int *hitstopp) /* record whether hit v->stop, if non-NULL */
211 : : {
212 : : chr *cp;
8335 bruce@momjian.us 213 [ + + ]: 5787417 : chr *realmin = (min == v->stop) ? min : min + 1;
214 [ + + ]: 5787417 : chr *realmax = (max == v->stop) ? max : max + 1;
215 : : color co;
216 : : struct sset *css;
217 : : struct sset *ss;
8515 tgl@sss.pgh.pa.us 218 : 5787417 : struct colormap *cm = d->cm;
219 : :
220 : : /* prevent "uninitialized variable" warnings */
3893 221 [ + + ]: 5787417 : if (coldp != NULL)
222 : 5786246 : *coldp = NULL;
223 [ + + ]: 5787417 : if (hitstopp != NULL)
224 : 227 : *hitstopp = 0;
225 : :
226 : : /* if this is a backref to a known string, just match against that */
1915 227 [ - + ]: 5787417 : if (d->backno >= 0)
228 : : {
1915 tgl@sss.pgh.pa.us 229 [ # # ]:UBC 0 : assert((size_t) d->backno < v->nmatch);
230 [ # # ]: 0 : if (v->pmatch[d->backno].rm_so >= 0)
231 : : {
232 : 0 : cp = dfa_backref(v, d, start, min, max, true);
233 [ # # # # ]: 0 : if (cp != NULL && coldp != NULL)
234 : 0 : *coldp = start;
235 : : /* there is no case where we should set *hitstopp */
236 : 0 : return cp;
237 : : }
238 : : }
239 : :
240 : : /* fast path for matchall NFAs */
1925 tgl@sss.pgh.pa.us 241 [ + + ]:CBC 5787417 : if (d->cnfa->flags & MATCHALL)
242 : : {
243 : 1440 : size_t nchr = min - start;
244 : :
245 [ + + ]: 1440 : if (d->cnfa->maxmatchall != DUPINF &&
246 [ - + ]: 16 : nchr > d->cnfa->maxmatchall)
1925 tgl@sss.pgh.pa.us 247 :UBC 0 : return NULL;
1925 tgl@sss.pgh.pa.us 248 [ + + ]:CBC 1440 : if ((max - start) < d->cnfa->minmatchall)
249 : 15 : return NULL;
250 [ + + ]: 1425 : if (nchr < d->cnfa->minmatchall)
251 : 99 : min = start + d->cnfa->minmatchall;
252 [ + + ]: 1425 : if (coldp != NULL)
253 : 676 : *coldp = start;
254 : : /* there is no case where we should set *hitstopp */
255 : 1425 : return min;
256 : : }
257 : :
258 : : /* initialize */
8515 259 : 5785977 : css = initialize(v, d, start);
3893 260 [ - + ]: 5785977 : if (css == NULL)
3893 tgl@sss.pgh.pa.us 261 :UBC 0 : return NULL;
8515 tgl@sss.pgh.pa.us 262 :CBC 5785977 : cp = start;
263 : :
264 : : /* startup */
265 : : FDEBUG(("--- startup ---\n"));
8335 bruce@momjian.us 266 [ + + ]: 5785977 : if (cp == v->start)
267 : : {
268 : 5320612 : co = d->cnfa->bos[(v->eflags & REG_NOTBOL) ? 0 : 1];
269 : : FDEBUG(("color %ld\n", (long) co));
270 : : }
271 : : else
272 : : {
8515 tgl@sss.pgh.pa.us 273 [ + - ]: 465365 : co = GETCOLOR(cm, *(cp - 1));
274 : : FDEBUG(("char %c, color %ld\n", (char) *(cp - 1), (long) co));
275 : : }
276 : 5785977 : css = miss(v, d, css, co, cp, start);
277 [ + + ]: 5785977 : if (css == NULL)
278 : 8 : return NULL;
279 : 5785969 : css->lastseen = cp;
280 : 5785969 : ss = css;
281 : :
282 : : /*
283 : : * This is the main text-scanning loop. It seems worth having two copies
284 : : * to avoid the overhead of REG_FTRACE tests here, even in REG_DEBUG
285 : : * builds, when you're not actively tracing.
286 : : */
287 : : #ifdef REG_DEBUG
288 : : if (v->eflags & REG_FTRACE)
289 : : {
290 : : while (cp < realmax)
291 : : {
292 : : FDEBUG(("--- at c%d ---\n", (int) (css - d->ssets)));
293 : : co = GETCOLOR(cm, *cp);
294 : : FDEBUG(("char %c, color %ld\n", (char) *cp, (long) co));
295 : : ss = css->outs[co];
296 : : if (ss == NULL)
297 : : {
298 : : ss = miss(v, d, css, co, cp + 1, start);
299 : : if (ss == NULL)
300 : : break; /* NOTE BREAK OUT */
301 : : }
302 : : cp++;
303 : : ss->lastseen = cp;
304 : : css = ss;
305 : : if ((ss->flags & POSTSTATE) && cp >= realmin)
306 : : break; /* NOTE BREAK OUT */
307 : : }
308 : : }
309 : : else
310 : : #endif
311 : : {
8335 bruce@momjian.us 312 [ + + ]: 26061506 : while (cp < realmax)
313 : : {
8515 tgl@sss.pgh.pa.us 314 [ + + ]: 25735321 : co = GETCOLOR(cm, *cp);
315 : 25735321 : ss = css->outs[co];
8335 bruce@momjian.us 316 [ + + ]: 25735321 : if (ss == NULL)
317 : : {
318 : 9193493 : ss = miss(v, d, css, co, cp + 1, start);
8515 tgl@sss.pgh.pa.us 319 [ + + ]: 9193493 : if (ss == NULL)
8335 bruce@momjian.us 320 : 4869405 : break; /* NOTE BREAK OUT */
321 : : }
8515 tgl@sss.pgh.pa.us 322 : 20865916 : cp++;
323 : 20865916 : ss->lastseen = cp;
324 : 20865916 : css = ss;
8335 bruce@momjian.us 325 [ + + + + ]: 20865916 : if ((ss->flags & POSTSTATE) && cp >= realmin)
326 : 590379 : break; /* NOTE BREAK OUT */
327 : : }
328 : : }
329 : :
8515 tgl@sss.pgh.pa.us 330 [ + + ]: 5785969 : if (ss == NULL)
331 : 4869405 : return NULL;
332 : :
7532 bruce@momjian.us 333 [ + + ]: 916564 : if (coldp != NULL) /* report last no-progress state set, if any */
8515 tgl@sss.pgh.pa.us 334 : 916186 : *coldp = lastcold(v, d);
335 : :
8335 bruce@momjian.us 336 [ + + + + ]: 916564 : if ((ss->flags & POSTSTATE) && cp > min)
337 : : {
8515 tgl@sss.pgh.pa.us 338 [ - + ]: 590358 : assert(cp >= realmin);
339 : 590358 : cp--;
340 : : }
8335 bruce@momjian.us 341 [ + - + - ]: 326206 : else if (cp == v->stop && max == v->stop)
342 : : {
343 : 326206 : co = d->cnfa->eos[(v->eflags & REG_NOTEOL) ? 0 : 1];
344 : : FDEBUG(("color %ld\n", (long) co));
8515 tgl@sss.pgh.pa.us 345 : 326206 : ss = miss(v, d, css, co, cp, start);
346 : : /* match might have ended at eol */
8335 bruce@momjian.us 347 [ + + - + : 326206 : if ((ss == NULL || !(ss->flags & POSTSTATE)) && hitstopp != NULL)
+ + ]
8515 tgl@sss.pgh.pa.us 348 : 8 : *hitstopp = 1;
349 : : }
350 : :
8335 bruce@momjian.us 351 [ + + - + ]: 916564 : if (ss == NULL || !(ss->flags & POSTSTATE))
8515 tgl@sss.pgh.pa.us 352 : 312913 : return NULL;
353 : :
354 : 603651 : return cp;
355 : : }
356 : :
357 : : /*
358 : : * matchuntil - incremental matching engine
359 : : *
360 : : * This is meant for use with a search-style NFA (that is, the pattern is
361 : : * known to act as though it had a leading .*). We determine whether a
362 : : * match exists starting at v->start and ending at probe. Multiple calls
363 : : * require only O(N) time not O(N^2) so long as the probe values are
364 : : * nondecreasing. *lastcss and *lastcp must be initialized to NULL before
365 : : * starting a series of calls.
366 : : *
367 : : * Returns 1 if a match exists, 0 if not.
368 : : * Internal errors also return 0, with v->err set.
369 : : */
370 : : static int
3265 371 : 74 : matchuntil(struct vars *v,
372 : : struct dfa *d,
373 : : chr *probe, /* we want to know if a match ends here */
374 : : struct sset **lastcss, /* state storage across calls */
375 : : chr **lastcp) /* state storage across calls */
376 : : {
3865 377 : 74 : chr *cp = *lastcp;
378 : : color co;
379 : 74 : struct sset *css = *lastcss;
380 : : struct sset *ss;
381 : 74 : struct colormap *cm = d->cm;
382 : :
383 : : /* fast path for matchall NFAs */
1925 384 [ + + ]: 74 : if (d->cnfa->flags & MATCHALL)
385 : : {
386 : 18 : size_t nchr = probe - v->start;
387 : :
388 [ + + ]: 18 : if (nchr < d->cnfa->minmatchall)
389 : 9 : return 0;
390 : : /* maxmatchall will always be infinity, cf. makesearch() */
1737 391 [ - + ]: 9 : assert(d->cnfa->maxmatchall == DUPINF);
1925 392 : 9 : return 1;
393 : : }
394 : :
395 : : /* initialize and startup, or restart, if necessary */
3865 396 [ + + + + ]: 56 : if (cp == NULL || cp > probe)
397 : : {
398 : 16 : cp = v->start;
399 : 16 : css = initialize(v, d, cp);
400 [ - + ]: 16 : if (css == NULL)
3865 tgl@sss.pgh.pa.us 401 :UBC 0 : return 0;
402 : :
403 : : FDEBUG((">>> startup >>>\n"));
3865 tgl@sss.pgh.pa.us 404 :CBC 16 : co = d->cnfa->bos[(v->eflags & REG_NOTBOL) ? 0 : 1];
405 : : FDEBUG(("color %ld\n", (long) co));
406 : :
407 : 16 : css = miss(v, d, css, co, cp, v->start);
408 [ - + ]: 16 : if (css == NULL)
3865 tgl@sss.pgh.pa.us 409 :UBC 0 : return 0;
3865 tgl@sss.pgh.pa.us 410 :CBC 16 : css->lastseen = cp;
411 : : }
412 [ - + ]: 40 : else if (css == NULL)
413 : : {
414 : : /* we previously found that no match is possible beyond *lastcp */
3865 tgl@sss.pgh.pa.us 415 :UBC 0 : return 0;
416 : : }
3865 tgl@sss.pgh.pa.us 417 :CBC 56 : ss = css;
418 : :
419 : : /*
420 : : * This is the main text-scanning loop. It seems worth having two copies
421 : : * to avoid the overhead of REG_FTRACE tests here, even in REG_DEBUG
422 : : * builds, when you're not actively tracing.
423 : : */
424 : : #ifdef REG_DEBUG
425 : : if (v->eflags & REG_FTRACE)
426 : : {
427 : : while (cp < probe)
428 : : {
429 : : FDEBUG((">>> at c%d >>>\n", (int) (css - d->ssets)));
430 : : co = GETCOLOR(cm, *cp);
431 : : FDEBUG(("char %c, color %ld\n", (char) *cp, (long) co));
432 : : ss = css->outs[co];
433 : : if (ss == NULL)
434 : : {
435 : : ss = miss(v, d, css, co, cp + 1, v->start);
436 : : if (ss == NULL)
437 : : break; /* NOTE BREAK OUT */
438 : : }
439 : : cp++;
440 : : ss->lastseen = cp;
441 : : css = ss;
442 : : }
443 : : }
444 : : else
445 : : #endif
446 : : {
447 [ + + ]: 120 : while (cp < probe)
448 : : {
449 [ + - ]: 64 : co = GETCOLOR(cm, *cp);
450 : 64 : ss = css->outs[co];
451 [ + + ]: 64 : if (ss == NULL)
452 : : {
453 : 8 : ss = miss(v, d, css, co, cp + 1, v->start);
454 [ - + ]: 8 : if (ss == NULL)
3865 tgl@sss.pgh.pa.us 455 :UBC 0 : break; /* NOTE BREAK OUT */
456 : : }
3865 tgl@sss.pgh.pa.us 457 :CBC 64 : cp++;
458 : 64 : ss->lastseen = cp;
459 : 64 : css = ss;
460 : : }
461 : : }
462 : :
463 : 56 : *lastcss = ss;
464 : 56 : *lastcp = cp;
465 : :
466 [ - + ]: 56 : if (ss == NULL)
3865 tgl@sss.pgh.pa.us 467 :UBC 0 : return 0; /* impossible match, or internal error */
468 : :
469 : : /* We need to process one more chr, or the EOS symbol, to check match */
3865 tgl@sss.pgh.pa.us 470 [ + - ]:CBC 56 : if (cp < v->stop)
471 : : {
472 : : FDEBUG((">>> at c%d >>>\n", (int) (css - d->ssets)));
473 [ + - ]: 56 : co = GETCOLOR(cm, *cp);
474 : : FDEBUG(("char %c, color %ld\n", (char) *cp, (long) co));
475 : 56 : ss = css->outs[co];
476 [ + + ]: 56 : if (ss == NULL)
477 : 36 : ss = miss(v, d, css, co, cp + 1, v->start);
478 : : }
479 : : else
480 : : {
3865 tgl@sss.pgh.pa.us 481 [ # # ]:UBC 0 : assert(cp == v->stop);
482 : 0 : co = d->cnfa->eos[(v->eflags & REG_NOTEOL) ? 0 : 1];
483 : : FDEBUG(("color %ld\n", (long) co));
484 : 0 : ss = miss(v, d, css, co, cp, v->start);
485 : : }
486 : :
3865 tgl@sss.pgh.pa.us 487 [ + - + + ]:CBC 56 : if (ss == NULL || !(ss->flags & POSTSTATE))
488 : 40 : return 0;
489 : :
490 : 16 : return 1;
491 : : }
492 : :
493 : : /*
494 : : * dfa_backref - find best match length for a known backref string
495 : : *
496 : : * When the backref's referent is already available, we can deliver an exact
497 : : * answer with considerably less work than running the backref node's NFA.
498 : : *
499 : : * Return match endpoint for longest or shortest valid repeated match,
500 : : * or NULL if there is no valid match.
501 : : *
502 : : * Should be in sync with cbrdissect(), although that has the different task
503 : : * of checking a match to a predetermined section of the string.
504 : : */
505 : : static chr *
1915 506 : 861 : dfa_backref(struct vars *v,
507 : : struct dfa *d,
508 : : chr *start, /* where the match should start */
509 : : chr *min, /* match must end at or after here */
510 : : chr *max, /* match must end at or before here */
511 : : bool shortest)
512 : : {
513 : 861 : int n = d->backno;
514 : 861 : int backmin = d->backmin;
515 : 861 : int backmax = d->backmax;
516 : : size_t numreps;
517 : : size_t minreps;
518 : : size_t maxreps;
519 : : size_t brlen;
520 : : chr *brstring;
521 : : chr *p;
522 : :
523 : : /* get the backreferenced string (caller should have checked this) */
524 [ - + ]: 861 : if (v->pmatch[n].rm_so == -1)
1915 tgl@sss.pgh.pa.us 525 :UBC 0 : return NULL;
1915 tgl@sss.pgh.pa.us 526 :CBC 861 : brstring = v->start + v->pmatch[n].rm_so;
527 : 861 : brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
528 : :
529 : : /* special-case zero-length backreference to avoid divide by zero */
530 [ + + ]: 861 : if (brlen == 0)
531 : : {
532 : : /*
533 : : * matches only a zero-length string, but any number of repetitions
534 : : * can be considered to be present
535 : : */
536 [ + - + - ]: 1 : if (min == start && backmin <= backmax)
537 : 1 : return start;
1915 tgl@sss.pgh.pa.us 538 :UBC 0 : return NULL;
539 : : }
540 : :
541 : : /*
542 : : * convert min and max into numbers of possible repetitions of the backref
543 : : * string, rounding appropriately
544 : : */
1915 tgl@sss.pgh.pa.us 545 [ + - ]:CBC 860 : if (min <= start)
546 : 860 : minreps = 0;
547 : : else
1915 tgl@sss.pgh.pa.us 548 :UBC 0 : minreps = (min - start - 1) / brlen + 1;
1915 tgl@sss.pgh.pa.us 549 :CBC 860 : maxreps = (max - start) / brlen;
550 : :
551 : : /* apply bounds, then see if there is any allowed match length */
552 [ + + ]: 860 : if (minreps < backmin)
553 : 832 : minreps = backmin;
554 [ + + + + ]: 860 : if (backmax != DUPINF && maxreps > backmax)
555 : 426 : maxreps = backmax;
556 [ + + ]: 860 : if (maxreps < minreps)
557 : 178 : return NULL;
558 : :
559 : : /* quick exit if zero-repetitions match is valid and preferred */
560 [ - + - - ]: 682 : if (shortest && minreps == 0)
1915 tgl@sss.pgh.pa.us 561 :UBC 0 : return start;
562 : :
563 : : /* okay, compare the actual string contents */
1915 tgl@sss.pgh.pa.us 564 :CBC 682 : p = start;
565 : 682 : numreps = 0;
566 [ + + ]: 805 : while (numreps < maxreps)
567 : : {
568 [ + + ]: 699 : if ((*v->g->compare) (brstring, p, brlen) != 0)
569 : 576 : break;
570 : 123 : p += brlen;
571 : 123 : numreps++;
572 [ - + - - ]: 123 : if (shortest && numreps >= minreps)
1915 tgl@sss.pgh.pa.us 573 :UBC 0 : break;
574 : : }
575 : :
1915 tgl@sss.pgh.pa.us 576 [ + + ]:CBC 682 : if (numreps >= minreps)
577 : 112 : return p;
578 : 570 : return NULL;
579 : : }
580 : :
581 : : /*
582 : : * lastcold - determine last point at which no progress had been made
583 : : */
584 : : static chr * /* endpoint, or NULL */
3265 585 : 916186 : lastcold(struct vars *v,
586 : : struct dfa *d)
587 : : {
588 : : struct sset *ss;
589 : : chr *nopr;
590 : : int i;
591 : :
8515 592 : 916186 : nopr = d->lastnopr;
593 [ + + ]: 916186 : if (nopr == NULL)
594 : 916184 : nopr = v->start;
595 [ + + ]: 4874604 : for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)
8335 bruce@momjian.us 596 [ + + + + ]: 3958418 : if ((ss->flags & NOPROGRESS) && nopr < ss->lastseen)
8515 tgl@sss.pgh.pa.us 597 : 1253899 : nopr = ss->lastseen;
598 : 916186 : return nopr;
599 : : }
600 : :
601 : : /*
602 : : * newdfa - set up a fresh DFA
603 : : *
604 : : * Returns NULL (and sets v->err) on failure.
605 : : */
606 : : static struct dfa *
3265 607 : 6274207 : newdfa(struct vars *v,
608 : : struct cnfa *cnfa,
609 : : struct colormap *cm,
610 : : struct smalldfa *sml) /* preallocated space, may be NULL */
611 : : {
612 : : struct dfa *d;
8335 bruce@momjian.us 613 : 6274207 : size_t nss = cnfa->nstates * 2;
614 : 6274207 : int wordsper = (cnfa->nstates + UBITS - 1) / UBITS;
1924 tgl@sss.pgh.pa.us 615 : 6274207 : bool ismalloced = false;
616 : :
8515 617 [ + - - + ]: 6274207 : assert(cnfa != NULL && cnfa->nstates != 0);
618 : :
8335 bruce@momjian.us 619 [ + + + + ]: 6274207 : if (nss <= FEWSTATES && cnfa->ncolors <= FEWCOLORS)
620 : : {
8515 tgl@sss.pgh.pa.us 621 [ - + ]: 2878823 : assert(wordsper == 1);
5216 622 [ + + ]: 2878823 : if (sml == NULL)
623 : : {
624 : 15976 : sml = (struct smalldfa *) MALLOC(sizeof(struct smalldfa));
625 [ - + ]: 15976 : if (sml == NULL)
626 : : {
8515 tgl@sss.pgh.pa.us 627 [ # # ]:UBC 0 : ERR(REG_ESPACE);
628 : 0 : return NULL;
629 : : }
1924 tgl@sss.pgh.pa.us 630 :CBC 15976 : ismalloced = true;
631 : : }
5216 632 : 2878823 : d = &sml->dfa;
633 : 2878823 : d->ssets = sml->ssets;
634 : 2878823 : d->statesarea = sml->statesarea;
8515 635 : 2878823 : d->work = &d->statesarea[nss];
5216 636 : 2878823 : d->outsarea = sml->outsarea;
637 : 2878823 : d->incarea = sml->incarea;
1924 638 : 2878823 : d->ismalloced = ismalloced;
639 : 2878823 : d->arraysmalloced = false; /* not separately allocated, anyway */
640 : : }
641 : : else
642 : : {
643 : : /*
644 : : * Restrict the ranges of nstates and ncolors enough that the arrays
645 : : * we allocate here have no more than INT_MAX members. This protects
646 : : * not only the allocation calculations just below, but later indexing
647 : : * into these arrays.
648 : : */
19 649 [ + - ]: 3395384 : if (wordsper >= INT_MAX / (nss + WORK) ||
650 [ - + ]: 3395384 : cnfa->ncolors >= INT_MAX / nss)
651 : : {
19 tgl@sss.pgh.pa.us 652 [ # # ]:UBC 0 : ERR(REG_ETOOBIG);
653 : 0 : return NULL;
654 : : }
8335 bruce@momjian.us 655 :CBC 3395384 : d = (struct dfa *) MALLOC(sizeof(struct dfa));
656 [ - + ]: 3395384 : if (d == NULL)
657 : : {
8515 tgl@sss.pgh.pa.us 658 [ # # ]:UBC 0 : ERR(REG_ESPACE);
659 : 0 : return NULL;
660 : : }
19 tgl@sss.pgh.pa.us 661 :CBC 3395384 : d->ssets = MALLOC_ARRAY(struct sset, nss);
662 : 3395384 : d->statesarea = MALLOC_ARRAY(unsigned, (nss + WORK) * wordsper);
8515 663 : 3395384 : d->work = &d->statesarea[nss * wordsper];
19 664 : 3395384 : d->outsarea = MALLOC_ARRAY(struct sset *, nss * cnfa->ncolors);
665 : 3395384 : d->incarea = MALLOC_ARRAY(struct arcp, nss * cnfa->ncolors);
1924 666 : 3395384 : d->ismalloced = true;
667 : 3395384 : d->arraysmalloced = true;
668 : : /* now freedfa() will behave sanely */
8515 669 [ + - + - ]: 3395384 : if (d->ssets == NULL || d->statesarea == NULL ||
8335 bruce@momjian.us 670 [ + - - + ]: 3395384 : d->outsarea == NULL || d->incarea == NULL)
671 : : {
8515 tgl@sss.pgh.pa.us 672 :UBC 0 : freedfa(d);
673 [ # # ]: 0 : ERR(REG_ESPACE);
674 : 0 : return NULL;
675 : : }
676 : : }
677 : :
8335 bruce@momjian.us 678 [ + + ]:CBC 6274207 : d->nssets = (v->eflags & REG_SMALL) ? 7 : nss;
8515 tgl@sss.pgh.pa.us 679 : 6274207 : d->nssused = 0;
680 : 6274207 : d->nstates = cnfa->nstates;
681 : 6274207 : d->ncolors = cnfa->ncolors;
682 : 6274207 : d->wordsper = wordsper;
683 : 6274207 : d->cnfa = cnfa;
684 : 6274207 : d->cm = cm;
685 : 6274207 : d->lastpost = NULL;
686 : 6274207 : d->lastnopr = NULL;
687 : 6274207 : d->search = d->ssets;
1915 688 : 6274207 : d->backno = -1; /* may be set by caller */
689 : 6274207 : d->backmin = d->backmax = 0;
690 : :
691 : : /* initialization of sset fields is done as needed */
692 : :
8515 693 : 6274207 : return d;
694 : : }
695 : :
696 : : /*
697 : : * freedfa - free a DFA
698 : : */
699 : : static void
3265 700 : 6274207 : freedfa(struct dfa *d)
701 : : {
1924 702 [ + + ]: 6274207 : if (d->arraysmalloced)
703 : : {
8515 704 [ + - ]: 3395384 : if (d->ssets != NULL)
705 : 3395384 : FREE(d->ssets);
706 [ + - ]: 3395384 : if (d->statesarea != NULL)
707 : 3395384 : FREE(d->statesarea);
708 [ + - ]: 3395384 : if (d->outsarea != NULL)
709 : 3395384 : FREE(d->outsarea);
710 [ + - ]: 3395384 : if (d->incarea != NULL)
711 : 3395384 : FREE(d->incarea);
712 : : }
713 : :
1924 714 [ + + ]: 6274207 : if (d->ismalloced)
715 : 3411360 : FREE(d);
8515 716 : 6274207 : }
717 : :
718 : : /*
719 : : * hash - construct a hash code for a bitvector
720 : : *
721 : : * There are probably better ways, but they're more expensive.
722 : : */
723 : : static unsigned
724 : 22896 : hash(unsigned *uv,
725 : : int n)
726 : : {
727 : : int i;
728 : : unsigned h;
729 : :
730 : 22896 : h = 0;
731 [ + + ]: 96973 : for (i = 0; i < n; i++)
732 : 74077 : h ^= uv[i];
733 : 22896 : return h;
734 : : }
735 : :
736 : : /*
737 : : * initialize - hand-craft a cache entry for startup, otherwise get ready
738 : : */
739 : : static struct sset *
3265 740 : 6276309 : initialize(struct vars *v,
741 : : struct dfa *d,
742 : : chr *start)
743 : : {
744 : : struct sset *ss;
745 : : int i;
746 : :
747 : : /* is previous one still there? */
8335 bruce@momjian.us 748 [ + + + - ]: 6276309 : if (d->nssused > 0 && (d->ssets[0].flags & STARTER))
8515 tgl@sss.pgh.pa.us 749 : 4035 : ss = &d->ssets[0];
750 : : else
751 : : { /* no, must (re)build it */
752 : 6272274 : ss = getvacant(v, d, start, start);
3893 753 [ - + ]: 6272274 : if (ss == NULL)
3893 tgl@sss.pgh.pa.us 754 :UBC 0 : return NULL;
8515 tgl@sss.pgh.pa.us 755 [ + + ]:CBC 12546658 : for (i = 0; i < d->wordsper; i++)
756 : 6274384 : ss->states[i] = 0;
757 : 6272274 : BSET(ss->states, d->cnfa->pre);
758 [ + + ]: 6272274 : ss->hash = HASH(ss->states, d->wordsper);
759 [ - + ]: 6272274 : assert(d->cnfa->pre != d->cnfa->post);
8335 bruce@momjian.us 760 : 6272274 : ss->flags = STARTER | LOCKED | NOPROGRESS;
761 : : /* lastseen dealt with below */
762 : : }
763 : :
8515 tgl@sss.pgh.pa.us 764 [ + + ]: 12593609 : for (i = 0; i < d->nssused; i++)
765 : 6317300 : d->ssets[i].lastseen = NULL;
766 : 6276309 : ss->lastseen = start; /* maybe untrue, but harmless */
767 : 6276309 : d->lastpost = NULL;
768 : 6276309 : d->lastnopr = NULL;
769 : 6276309 : return ss;
770 : : }
771 : :
772 : : /*
773 : : * miss - handle a stateset cache miss
774 : : *
775 : : * css is the current stateset, co is the color of the current input character,
776 : : * cp points to the character after that (which is where we may need to test
777 : : * LACONs). start does not affect matching behavior but is needed for pickss'
778 : : * heuristics about which stateset cache entry to replace.
779 : : *
780 : : * Ordinarily, returns the address of the next stateset (the one that is
781 : : * valid after consuming the input character). Returns NULL if no valid
782 : : * NFA states remain, ie we have a certain match failure.
783 : : * Internal errors also return NULL, with v->err set.
784 : : */
785 : : static struct sset *
3265 786 : 17403891 : miss(struct vars *v,
787 : : struct dfa *d,
788 : : struct sset *css,
789 : : color co,
790 : : chr *cp, /* next chr */
791 : : chr *start) /* where the attempt got started */
792 : : {
8515 793 : 17403891 : struct cnfa *cnfa = d->cnfa;
794 : : int i;
795 : : unsigned h;
796 : : struct carc *ca;
797 : : struct sset *p;
798 : : int ispseudocolor;
799 : : int ispost;
800 : : int noprogress;
801 : : int gotstate;
802 : : int dolacons;
803 : : int sawlacons;
804 : :
805 : : /* for convenience, we can be called even if it might not be a miss */
8335 bruce@momjian.us 806 [ + + ]: 17403891 : if (css->outs[co] != NULL)
807 : : {
808 : : FDEBUG(("hit\n"));
8515 tgl@sss.pgh.pa.us 809 : 3031 : return css->outs[co];
810 : : }
811 : : FDEBUG(("miss\n"));
812 : :
813 : : /*
814 : : * Checking for operation cancel in the inner text search loop seems
815 : : * unduly expensive. As a compromise, check during cache misses.
816 : : */
1148 tmunro@postgresql.or 817 [ - + ]: 17400860 : INTERRUPT(v->re);
818 : :
819 : : /*
820 : : * What set of states would we end up in after consuming the co character?
821 : : * We first consider PLAIN arcs that consume the character, and then look
822 : : * to see what LACON arcs could be traversed after consuming it.
823 : : */
8515 tgl@sss.pgh.pa.us 824 [ + + ]: 34854367 : for (i = 0; i < d->wordsper; i++)
3893 825 : 17453507 : d->work[i] = 0; /* build new stateset bitmap in d->work */
1925 826 : 17400860 : ispseudocolor = d->cm->cd[co].flags & PSEUDO;
8515 827 : 17400860 : ispost = 0;
828 : 17400860 : noprogress = 1;
829 : 17400860 : gotstate = 0;
830 [ + + ]: 215916863 : for (i = 0; i < d->nstates; i++)
831 [ + + ]: 198516003 : if (ISBSET(css->states, i))
5075 832 [ + + ]: 70510021 : for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++)
1925 833 [ + + ]: 47838315 : if (ca->co == co ||
834 [ + + + + ]: 39106098 : (ca->co == RAINBOW && !ispseudocolor))
835 : : {
8515 836 : 18356327 : BSET(d->work, ca->to);
837 : 18356327 : gotstate = 1;
838 [ + + ]: 18356327 : if (ca->to == cnfa->post)
839 : 1109359 : ispost = 1;
5075 840 [ + + ]: 18356327 : if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS))
8515 841 : 5009398 : noprogress = 0;
842 : : FDEBUG(("%d -> %d\n", i, ca->to));
843 : : }
3893 844 [ + + ]: 17400860 : if (!gotstate)
845 : 5659247 : return NULL; /* character cannot reach any new state */
846 : 11741613 : dolacons = (cnfa->flags & HASLACONS);
8515 847 : 11741613 : sawlacons = 0;
848 : : /* outer loop handles transitive closure of reachable-by-LACON states */
8335 bruce@momjian.us 849 [ + + ]: 11742878 : while (dolacons)
850 : : {
8515 tgl@sss.pgh.pa.us 851 : 1265 : dolacons = 0;
852 [ + + ]: 11822 : for (i = 0; i < d->nstates; i++)
853 [ + + ]: 10557 : if (ISBSET(d->work, i))
5075 854 [ + + ]: 3718 : for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++)
855 : : {
856 [ + + ]: 2163 : if (ca->co < cnfa->ncolors)
3265 857 : 1921 : continue; /* not a LACON arc */
8515 858 [ + + ]: 242 : if (ISBSET(d->work, ca->to))
3265 859 : 84 : continue; /* arc would be a no-op anyway */
860 : 158 : sawlacons = 1; /* this LACON affects our result */
8515 861 [ + + ]: 158 : if (!lacon(v, cnfa, cp, ca->co))
862 : : {
3893 863 [ - + ]: 85 : if (ISERR())
3893 tgl@sss.pgh.pa.us 864 :UBC 0 : return NULL;
3265 tgl@sss.pgh.pa.us 865 :CBC 85 : continue; /* LACON arc cannot be traversed */
866 : : }
3893 867 [ - + ]: 73 : if (ISERR())
3893 tgl@sss.pgh.pa.us 868 :UBC 0 : return NULL;
8515 tgl@sss.pgh.pa.us 869 :CBC 73 : BSET(d->work, ca->to);
870 : 73 : dolacons = 1;
871 [ - + ]: 73 : if (ca->to == cnfa->post)
8515 tgl@sss.pgh.pa.us 872 :UBC 0 : ispost = 1;
5075 tgl@sss.pgh.pa.us 873 [ + - ]:CBC 73 : if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS))
8515 874 : 73 : noprogress = 0;
875 : : FDEBUG(("%d :> %d\n", i, ca->to));
876 : : }
877 : : }
878 [ + + ]: 11741613 : h = HASH(d->work, d->wordsper);
879 : :
880 : : /* Is this stateset already in the cache? */
881 [ + + ]: 34886848 : for (p = d->ssets, i = d->nssused; i > 0; p++, i--)
8335 bruce@momjian.us 882 [ + + + + : 24691429 : if (HIT(h, d->work, p, d->wordsper))
+ + ]
883 : : {
884 : : FDEBUG(("cached c%d\n", (int) (p - d->ssets)));
885 : : break; /* NOTE BREAK OUT */
886 : : }
887 [ + + ]: 11741613 : if (i == 0)
888 : : { /* nope, need a new cache entry */
8515 tgl@sss.pgh.pa.us 889 : 10195419 : p = getvacant(v, d, cp, start);
3893 890 [ - + ]: 10195419 : if (p == NULL)
3893 tgl@sss.pgh.pa.us 891 :UBC 0 : return NULL;
8515 tgl@sss.pgh.pa.us 892 [ - + ]:CBC 10195419 : assert(p != css);
893 [ + + ]: 20433731 : for (i = 0; i < d->wordsper; i++)
894 : 10238312 : p->states[i] = d->work[i];
895 : 10195419 : p->hash = h;
896 [ + + ]: 10195419 : p->flags = (ispost) ? POSTSTATE : 0;
897 [ + + ]: 10195419 : if (noprogress)
898 : 6275205 : p->flags |= NOPROGRESS;
899 : : /* lastseen to be dealt with by caller */
900 : : }
901 : :
902 : : /*
903 : : * Link new stateset to old, unless a LACON affected the result, in which
904 : : * case we don't create the link. That forces future transitions across
905 : : * this same arc (same prior stateset and character color) to come through
906 : : * miss() again, so that we can recheck the LACON(s), which might or might
907 : : * not pass since context will be different.
908 : : */
8335 bruce@momjian.us 909 [ + + ]: 11741613 : if (!sawlacons)
910 : : {
911 : : FDEBUG(("c%d[%d]->c%d\n",
912 : : (int) (css - d->ssets), co, (int) (p - d->ssets)));
8515 tgl@sss.pgh.pa.us 913 : 11741501 : css->outs[co] = p;
914 : 11741501 : css->inchain[co] = p->ins;
915 : 11741501 : p->ins.ss = css;
3571 916 : 11741501 : p->ins.co = co;
917 : : }
8515 918 : 11741613 : return p;
919 : : }
920 : :
921 : : /*
922 : : * lacon - lookaround-constraint checker for miss()
923 : : */
924 : : static int /* predicate: constraint satisfied? */
3265 925 : 158 : lacon(struct vars *v,
926 : : struct cnfa *pcnfa, /* parent cnfa */
927 : : chr *cp,
928 : : color co) /* "color" of the lookaround constraint */
929 : : {
930 : : int n;
931 : : struct subre *sub;
932 : : struct dfa *d;
933 : : chr *end;
934 : : int satisfied;
935 : :
936 : : /* Since this is recursive, it could be driven to stack overflow */
3893 937 [ - + ]: 158 : if (STACK_TOO_DEEP(v->re))
938 : : {
3893 tgl@sss.pgh.pa.us 939 [ # # ]:UBC 0 : ERR(REG_ETOOBIG);
940 : 0 : return 0;
941 : : }
942 : :
8515 tgl@sss.pgh.pa.us 943 :CBC 158 : n = co - pcnfa->ncolors;
3865 944 [ + - + - : 158 : assert(n > 0 && n < v->g->nlacons && v->g->lacons != NULL);
- + ]
945 : : FDEBUG(("=== testing lacon %d\n", n));
8515 946 : 158 : sub = &v->g->lacons[n];
3865 947 : 158 : d = getladfa(v, n);
8335 bruce@momjian.us 948 [ - + ]: 158 : if (d == NULL)
8515 tgl@sss.pgh.pa.us 949 :UBC 0 : return 0;
1925 tgl@sss.pgh.pa.us 950 [ + + ]:CBC 158 : if (LATYPE_IS_AHEAD(sub->latype))
951 : : {
952 : : /* used to use longest() here, but shortest() could be much cheaper */
3865 953 : 84 : end = shortest(v, d, cp, cp, v->stop,
954 : : (chr **) NULL, (int *) NULL);
1925 955 [ + + ]: 84 : satisfied = LATYPE_IS_POS(sub->latype) ? (end != NULL) : (end == NULL);
956 : : }
957 : : else
958 : : {
959 : : /*
960 : : * To avoid doing O(N^2) work when repeatedly testing a lookbehind
961 : : * constraint in an N-character string, we use matchuntil() which can
962 : : * cache the DFA state across calls. We only need to restart if the
963 : : * probe point decreases, which is not common. The NFA we're using is
964 : : * a search NFA, so it doesn't mind scanning over stuff before the
965 : : * nominal match.
966 : : */
3865 967 : 74 : satisfied = matchuntil(v, d, cp, &v->lblastcss[n], &v->lblastcp[n]);
1925 968 [ - + ]: 74 : if (!LATYPE_IS_POS(sub->latype))
3865 tgl@sss.pgh.pa.us 969 :UBC 0 : satisfied = !satisfied;
970 : : }
971 : : FDEBUG(("=== lacon %d satisfied %d\n", n, satisfied));
3865 tgl@sss.pgh.pa.us 972 :CBC 158 : return satisfied;
973 : : }
974 : :
975 : : /*
976 : : * getvacant - get a vacant state set
977 : : *
978 : : * This routine clears out the inarcs and outarcs, but does not otherwise
979 : : * clear the innards of the state set -- that's up to the caller.
980 : : */
981 : : static struct sset *
3265 982 : 16467693 : getvacant(struct vars *v,
983 : : struct dfa *d,
984 : : chr *cp,
985 : : chr *start)
986 : : {
987 : : int i;
988 : : struct sset *ss;
989 : : struct sset *p;
990 : : struct arcp ap;
991 : : color co;
992 : :
8515 993 : 16467693 : ss = pickss(v, d, cp, start);
3893 994 [ - + ]: 16467693 : if (ss == NULL)
3893 tgl@sss.pgh.pa.us 995 :UBC 0 : return NULL;
8335 bruce@momjian.us 996 [ - + ]:CBC 16467693 : assert(!(ss->flags & LOCKED));
997 : :
998 : : /* clear out its inarcs, including self-referential ones */
8515 tgl@sss.pgh.pa.us 999 : 16467693 : ap = ss->ins;
8335 bruce@momjian.us 1000 [ + + ]: 16467705 : while ((p = ap.ss) != NULL)
1001 : : {
8515 tgl@sss.pgh.pa.us 1002 : 12 : co = ap.co;
1003 : : FDEBUG(("zapping c%d's %ld outarc\n", (int) (p - d->ssets), (long) co));
1004 : 12 : p->outs[co] = NULL;
1005 : 12 : ap = p->inchain[co];
3265 1006 : 12 : p->inchain[co].ss = NULL; /* paranoia */
1007 : : }
8515 1008 : 16467693 : ss->ins.ss = NULL;
1009 : :
1010 : : /* take it off the inarc chains of the ssets reached by its outarcs */
8335 bruce@momjian.us 1011 [ + + ]: 201369029 : for (i = 0; i < d->ncolors; i++)
1012 : : {
8515 tgl@sss.pgh.pa.us 1013 : 184901336 : p = ss->outs[i];
1014 [ - + ]: 184901336 : assert(p != ss); /* not self-referential */
1015 [ + + ]: 184901336 : if (p == NULL)
8335 bruce@momjian.us 1016 : 184901270 : continue; /* NOTE CONTINUE */
1017 : : FDEBUG(("del outarc %d from c%d's in chn\n", i, (int) (p - d->ssets)));
8515 tgl@sss.pgh.pa.us 1018 [ + + + - ]: 66 : if (p->ins.ss == ss && p->ins.co == i)
1019 : 60 : p->ins = ss->inchain[i];
1020 : : else
1021 : : {
7553 1022 : 6 : struct arcp lastap = {NULL, 0};
1023 : :
8515 1024 [ - + ]: 6 : assert(p->ins.ss != NULL);
1025 [ + - ]: 12 : for (ap = p->ins; ap.ss != NULL &&
8335 bruce@momjian.us 1026 [ + + - + ]: 12 : !(ap.ss == ss && ap.co == i);
1027 : 6 : ap = ap.ss->inchain[ap.co])
8515 tgl@sss.pgh.pa.us 1028 : 6 : lastap = ap;
1029 [ - + ]: 6 : assert(ap.ss != NULL);
1030 : 6 : lastap.ss->inchain[lastap.co] = ss->inchain[i];
1031 : : }
1032 : 66 : ss->outs[i] = NULL;
1033 : 66 : ss->inchain[i].ss = NULL;
1034 : : }
1035 : :
1036 : : /* if ss was a success state, may need to remember location */
8335 bruce@momjian.us 1037 [ + + + - ]: 16467693 : if ((ss->flags & POSTSTATE) && ss->lastseen != d->lastpost &&
1038 [ + + + - ]: 18 : (d->lastpost == NULL || d->lastpost < ss->lastseen))
8515 tgl@sss.pgh.pa.us 1039 : 18 : d->lastpost = ss->lastseen;
1040 : :
1041 : : /* likewise for a no-progress state */
8335 bruce@momjian.us 1042 [ + + + - ]: 16467693 : if ((ss->flags & NOPROGRESS) && ss->lastseen != d->lastnopr &&
1043 [ - + - - ]: 6 : (d->lastnopr == NULL || d->lastnopr < ss->lastseen))
8515 tgl@sss.pgh.pa.us 1044 : 6 : d->lastnopr = ss->lastseen;
1045 : :
1046 : 16467693 : return ss;
1047 : : }
1048 : :
1049 : : /*
1050 : : * pickss - pick the next stateset to be used
1051 : : */
1052 : : static struct sset *
3265 1053 : 16467693 : pickss(struct vars *v,
1054 : : struct dfa *d,
1055 : : chr *cp,
1056 : : chr *start)
1057 : : {
1058 : : int i;
1059 : : struct sset *ss;
1060 : : struct sset *end;
1061 : : chr *ancient;
1062 : :
1063 : : /* shortcut for cases where cache isn't full */
8335 bruce@momjian.us 1064 [ + + ]: 16467693 : if (d->nssused < d->nssets)
1065 : : {
8515 tgl@sss.pgh.pa.us 1066 : 16467627 : i = d->nssused;
1067 : 16467627 : d->nssused++;
1068 : 16467627 : ss = &d->ssets[i];
1069 : : FDEBUG(("new c%d\n", i));
1070 : : /* set up innards */
1071 : 16467627 : ss->states = &d->statesarea[i * d->wordsper];
1072 : 16467627 : ss->flags = 0;
1073 : 16467627 : ss->ins.ss = NULL;
1074 : 16467627 : ss->ins.co = WHITE; /* give it some value */
1075 : 16467627 : ss->outs = &d->outsarea[i * d->ncolors];
1076 : 16467627 : ss->inchain = &d->incarea[i * d->ncolors];
8335 bruce@momjian.us 1077 [ + + ]: 201367427 : for (i = 0; i < d->ncolors; i++)
1078 : : {
8515 tgl@sss.pgh.pa.us 1079 : 184899800 : ss->outs[i] = NULL;
1080 : 184899800 : ss->inchain[i].ss = NULL;
1081 : : }
1082 : 16467627 : return ss;
1083 : : }
1084 : :
1085 : : /* look for oldest, or old enough anyway */
8335 bruce@momjian.us 1086 [ + - ]: 66 : if (cp - start > d->nssets * 2 / 3) /* oldest 33% are expendable */
1087 : 66 : ancient = cp - d->nssets * 2 / 3;
1088 : : else
8515 tgl@sss.pgh.pa.us 1089 :UBC 0 : ancient = start;
8515 tgl@sss.pgh.pa.us 1090 [ + + ]:CBC 72 : for (ss = d->search, end = &d->ssets[d->nssets]; ss < end; ss++)
1091 [ + - + - ]: 66 : if ((ss->lastseen == NULL || ss->lastseen < ancient) &&
8335 bruce@momjian.us 1092 [ + + ]: 66 : !(ss->flags & LOCKED))
1093 : : {
8515 tgl@sss.pgh.pa.us 1094 : 60 : d->search = ss + 1;
1095 : : FDEBUG(("replacing c%d\n", (int) (ss - d->ssets)));
1096 : 60 : return ss;
1097 : : }
1098 [ + - ]: 12 : for (ss = d->ssets, end = d->search; ss < end; ss++)
1099 [ + - + - ]: 12 : if ((ss->lastseen == NULL || ss->lastseen < ancient) &&
8335 bruce@momjian.us 1100 [ + + ]: 12 : !(ss->flags & LOCKED))
1101 : : {
8515 tgl@sss.pgh.pa.us 1102 : 6 : d->search = ss + 1;
1103 : : FDEBUG(("replacing c%d\n", (int) (ss - d->ssets)));
1104 : 6 : return ss;
1105 : : }
1106 : :
1107 : : /* nobody's old enough?!? -- something's really wrong */
1108 : : FDEBUG(("cannot find victim to replace!\n"));
8515 tgl@sss.pgh.pa.us 1109 [ # # ]:UBC 0 : ERR(REG_ASSERT);
3893 1110 : 0 : return NULL;
1111 : : }
|
