Age Owner Branch data TLA Line data Source code
1 : : /*
2 : : * NFA utilities.
3 : : * This file is #included by regcomp.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/regc_nfa.c
32 : : *
33 : : *
34 : : * One or two things that technically ought to be in here
35 : : * are actually in color.c, thanks to some incestuous relationships in
36 : : * the color chains.
37 : : */
38 : :
39 : : #define NISERR() VISERR(nfa->v)
40 : : #define NERR(e) VERR(nfa->v, (e))
41 : :
42 : :
43 : : /*
44 : : * newnfa - set up an NFA
45 : : */
46 : : static struct nfa * /* the NFA, or NULL */
2999 tgl@sss.pgh.pa.us 47 :CBC 9913 : newnfa(struct vars *v,
48 : : struct colormap *cm,
49 : : struct nfa *parent) /* NULL if primary NFA */
50 : : {
51 : : struct nfa *nfa;
52 : :
8069 bruce@momjian.us 53 : 9913 : nfa = (struct nfa *) MALLOC(sizeof(struct nfa));
8249 tgl@sss.pgh.pa.us 54 [ - + ]: 9913 : if (nfa == NULL)
55 : : {
3678 tgl@sss.pgh.pa.us 56 [ # # ]:UBC 0 : ERR(REG_ESPACE);
8249 57 : 0 : return NULL;
58 : : }
59 : :
60 : : /* Make the NFA minimally valid, so freenfa() will behave sanely */
8249 tgl@sss.pgh.pa.us 61 :CBC 9913 : nfa->states = NULL;
62 : 9913 : nfa->slast = NULL;
1653 63 : 9913 : nfa->freestates = NULL;
64 : 9913 : nfa->freearcs = NULL;
65 : 9913 : nfa->lastsb = NULL;
66 : 9913 : nfa->lastab = NULL;
67 : 9913 : nfa->lastsbused = 0;
68 : 9913 : nfa->lastabused = 0;
8249 69 : 9913 : nfa->nstates = 0;
70 : 9913 : nfa->cm = cm;
71 : 9913 : nfa->v = v;
72 : 9913 : nfa->bos[0] = nfa->bos[1] = COLORLESS;
73 : 9913 : nfa->eos[0] = nfa->eos[1] = COLORLESS;
1659 74 : 9913 : nfa->flags = 0;
75 : 9913 : nfa->minmatchall = nfa->maxmatchall = -1;
6456 76 : 9913 : nfa->parent = parent; /* Precedes newfstate so parent is valid. */
77 : :
78 : : /* Create required infrastructure */
8249 79 : 9913 : nfa->post = newfstate(nfa, '@'); /* number 0 */
2999 80 : 9913 : nfa->pre = newfstate(nfa, '>'); /* number 1 */
8069 bruce@momjian.us 81 : 9913 : nfa->init = newstate(nfa); /* may become invalid later */
8249 tgl@sss.pgh.pa.us 82 : 9913 : nfa->final = newstate(nfa);
8069 bruce@momjian.us 83 [ - + ]: 9913 : if (ISERR())
84 : : {
8249 tgl@sss.pgh.pa.us 85 :UBC 0 : freenfa(nfa);
86 : 0 : return NULL;
87 : : }
8249 tgl@sss.pgh.pa.us 88 :CBC 9913 : rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->pre, nfa->init);
89 : 9913 : newarc(nfa, '^', 1, nfa->pre, nfa->init);
90 : 9913 : newarc(nfa, '^', 0, nfa->pre, nfa->init);
91 : 9913 : rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->final, nfa->post);
92 : 9913 : newarc(nfa, '$', 1, nfa->final, nfa->post);
93 : 9913 : newarc(nfa, '$', 0, nfa->final, nfa->post);
94 : :
8069 bruce@momjian.us 95 [ - + ]: 9913 : if (ISERR())
96 : : {
8249 tgl@sss.pgh.pa.us 97 :UBC 0 : freenfa(nfa);
98 : 0 : return NULL;
99 : : }
8249 tgl@sss.pgh.pa.us 100 :CBC 9913 : return nfa;
101 : : }
102 : :
103 : : /*
104 : : * freenfa - free an entire NFA
105 : : */
106 : : static void
2999 107 : 9913 : freenfa(struct nfa *nfa)
108 : : {
109 : : struct statebatch *sb;
110 : : struct statebatch *sbnext;
111 : : struct arcbatch *ab;
112 : : struct arcbatch *abnext;
113 : :
1653 114 [ + + ]: 20678 : for (sb = nfa->lastsb; sb != NULL; sb = sbnext)
115 : : {
116 : 10765 : sbnext = sb->next;
117 : 10765 : nfa->v->spaceused -= STATEBATCHSIZE(sb->nstates);
118 : 10765 : FREE(sb);
119 : : }
120 : 9913 : nfa->lastsb = NULL;
121 [ + + ]: 27923 : for (ab = nfa->lastab; ab != NULL; ab = abnext)
122 : : {
123 : 18010 : abnext = ab->next;
124 : 18010 : nfa->v->spaceused -= ARCBATCHSIZE(ab->narcs);
125 : 18010 : FREE(ab);
126 : : }
127 : 9913 : nfa->lastab = NULL;
128 : :
8249 129 : 9913 : nfa->nstates = -1;
130 : 9913 : FREE(nfa);
131 : 9913 : }
132 : :
133 : : /*
134 : : * newstate - allocate an NFA state, with zero flag value
135 : : */
136 : : static struct state * /* NULL on error */
2999 137 : 260084 : newstate(struct nfa *nfa)
138 : : {
139 : : struct state *s;
140 : :
141 : : /*
142 : : * This is a handy place to check for operation cancel during regex
143 : : * compilation, since no code path will go very long without making a new
144 : : * state or arc.
145 : : */
882 tmunro@postgresql.or 146 [ - + ]: 260084 : INTERRUPT(nfa->v->re);
147 : :
148 : : /* first, recycle anything that's on the freelist */
1653 tgl@sss.pgh.pa.us 149 [ + + ]: 260084 : if (nfa->freestates != NULL)
150 : : {
151 : 16878 : s = nfa->freestates;
152 : 16878 : nfa->freestates = s->next;
153 : : }
154 : : /* otherwise, is there anything left in the last statebatch? */
155 [ + + + + ]: 243206 : else if (nfa->lastsb != NULL && nfa->lastsbused < nfa->lastsb->nstates)
156 : : {
157 : 232441 : s = &nfa->lastsb->s[nfa->lastsbused++];
158 : : }
159 : : /* otherwise, need to allocate a new statebatch */
160 : : else
161 : : {
162 : : struct statebatch *newSb;
163 : : size_t nstates;
164 : :
3613 165 [ - + ]: 10765 : if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE)
166 : : {
3613 tgl@sss.pgh.pa.us 167 [ # # ]:UBC 0 : NERR(REG_ETOOBIG);
168 : 0 : return NULL;
169 : : }
1653 tgl@sss.pgh.pa.us 170 [ + + ]:CBC 10765 : nstates = (nfa->lastsb != NULL) ? nfa->lastsb->nstates * 2 : FIRSTSBSIZE;
171 [ + + ]: 10765 : if (nstates > MAXSBSIZE)
172 : 25 : nstates = MAXSBSIZE;
173 : 10765 : newSb = (struct statebatch *) MALLOC(STATEBATCHSIZE(nstates));
174 [ - + ]: 10765 : if (newSb == NULL)
175 : : {
8249 tgl@sss.pgh.pa.us 176 [ # # ]:UBC 0 : NERR(REG_ESPACE);
177 : 0 : return NULL;
178 : : }
1653 tgl@sss.pgh.pa.us 179 :CBC 10765 : nfa->v->spaceused += STATEBATCHSIZE(nstates);
180 : 10765 : newSb->nstates = nstates;
181 : 10765 : newSb->next = nfa->lastsb;
182 : 10765 : nfa->lastsb = newSb;
183 : 10765 : nfa->lastsbused = 1;
184 : 10765 : s = &newSb->s[0];
185 : : }
186 : :
8249 187 [ - + ]: 260084 : assert(nfa->nstates >= 0);
188 : 260084 : s->no = nfa->nstates++;
189 : 260084 : s->flag = 0;
190 [ + + ]: 260084 : if (nfa->states == NULL)
191 : 9913 : nfa->states = s;
192 : 260084 : s->nins = 0;
193 : 260084 : s->ins = NULL;
194 : 260084 : s->nouts = 0;
195 : 260084 : s->outs = NULL;
196 : 260084 : s->tmp = NULL;
197 : 260084 : s->next = NULL;
8069 bruce@momjian.us 198 [ + + ]: 260084 : if (nfa->slast != NULL)
199 : : {
8249 tgl@sss.pgh.pa.us 200 [ - + ]: 250171 : assert(nfa->slast->next == NULL);
201 : 250171 : nfa->slast->next = s;
202 : : }
203 : 260084 : s->prev = nfa->slast;
204 : 260084 : nfa->slast = s;
205 : 260084 : return s;
206 : : }
207 : :
208 : : /*
209 : : * newfstate - allocate an NFA state with a specified flag value
210 : : */
211 : : static struct state * /* NULL on error */
2999 212 : 19826 : newfstate(struct nfa *nfa, int flag)
213 : : {
214 : : struct state *s;
215 : :
8249 216 : 19826 : s = newstate(nfa);
217 [ + - ]: 19826 : if (s != NULL)
8069 bruce@momjian.us 218 : 19826 : s->flag = (char) flag;
8249 tgl@sss.pgh.pa.us 219 : 19826 : return s;
220 : : }
221 : :
222 : : /*
223 : : * dropstate - delete a state's inarcs and outarcs and free it
224 : : */
225 : : static void
2999 226 : 107347 : dropstate(struct nfa *nfa,
227 : : struct state *s)
228 : : {
229 : : struct arc *a;
230 : :
8249 231 [ + + ]: 126044 : while ((a = s->ins) != NULL)
232 : 18697 : freearc(nfa, a);
233 [ + + ]: 177145 : while ((a = s->outs) != NULL)
234 : 69798 : freearc(nfa, a);
235 : 107347 : freestate(nfa, s);
236 : 107347 : }
237 : :
238 : : /*
239 : : * freestate - free a state, which has no in-arcs or out-arcs
240 : : */
241 : : static void
2999 242 : 112239 : freestate(struct nfa *nfa,
243 : : struct state *s)
244 : : {
8249 245 [ - + ]: 112239 : assert(s != NULL);
246 [ + - - + ]: 112239 : assert(s->nins == 0 && s->nouts == 0);
247 : :
248 : 112239 : s->no = FREESTATE;
249 : 112239 : s->flag = 0;
250 [ + + ]: 112239 : if (s->next != NULL)
251 : 106143 : s->next->prev = s->prev;
252 : : else
253 : : {
254 [ - + ]: 6096 : assert(s == nfa->slast);
255 : 6096 : nfa->slast = s->prev;
256 : : }
257 [ + - ]: 112239 : if (s->prev != NULL)
258 : 112239 : s->prev->next = s->next;
259 : : else
260 : : {
8249 tgl@sss.pgh.pa.us 261 [ # # ]:UBC 0 : assert(s == nfa->states);
262 : 0 : nfa->states = s->next;
263 : : }
8249 tgl@sss.pgh.pa.us 264 :CBC 112239 : s->prev = NULL;
1653 265 : 112239 : s->next = nfa->freestates; /* don't delete it, put it on the free list */
266 : 112239 : nfa->freestates = s;
8249 267 : 112239 : }
268 : :
269 : : /*
270 : : * newarc - set up a new arc within an NFA
271 : : *
272 : : * This function checks to make sure that no duplicate arcs are created.
273 : : * In general we never want duplicates.
274 : : *
275 : : * However: in principle, a RAINBOW arc is redundant with any plain arc
276 : : * (unless that arc is for a pseudocolor). But we don't try to recognize
277 : : * that redundancy, either here or in allied operations such as moveins().
278 : : * The pseudocolor consideration makes that more costly than it seems worth.
279 : : */
280 : : static void
2999 281 : 952311 : newarc(struct nfa *nfa,
282 : : int t,
283 : : color co,
284 : : struct state *from,
285 : : struct state *to)
286 : : {
287 : : struct arc *a;
288 : :
8249 289 [ + - - + ]: 952311 : assert(from != NULL && to != NULL);
290 : :
291 : : /*
292 : : * This is a handy place to check for operation cancel during regex
293 : : * compilation, since no code path will go very long without making a new
294 : : * state or arc.
295 : : */
882 tmunro@postgresql.or 296 [ - + ]: 952311 : INTERRUPT(nfa->v->re);
297 : :
298 : : /* check for duplicate arc, using whichever chain is shorter */
3613 tgl@sss.pgh.pa.us 299 [ + + ]: 952311 : if (from->nouts <= to->nins)
300 : : {
301 [ + + ]: 3016392 : for (a = from->outs; a != NULL; a = a->outchain)
302 [ + + + + : 2564998 : if (a->to == to && a->co == co && a->type == t)
+ + ]
303 : 85322 : return;
304 : : }
305 : : else
306 : : {
307 [ + + ]: 38389399 : for (a = to->ins; a != NULL; a = a->inchain)
308 [ + + + + : 38059624 : if (a->from == from && a->co == co && a->type == t)
+ + ]
309 : 85820 : return;
310 : : }
311 : :
312 : : /* no dup, so create the arc */
313 : 781169 : createarc(nfa, t, co, from, to);
314 : : }
315 : :
316 : : /*
317 : : * createarc - create a new arc within an NFA
318 : : *
319 : : * This function must *only* be used after verifying that there is no existing
320 : : * identical arc (same type/color/from/to).
321 : : */
322 : : static void
2999 323 : 8724446 : createarc(struct nfa *nfa,
324 : : int t,
325 : : color co,
326 : : struct state *from,
327 : : struct state *to)
328 : : {
329 : : struct arc *a;
330 : :
1653 331 : 8724446 : a = allocarc(nfa);
8249 332 [ + + ]: 8724446 : if (NISERR())
333 : 5709 : return;
334 [ - + ]: 8718737 : assert(a != NULL);
335 : :
336 : 8718737 : a->type = t;
3305 337 : 8718737 : a->co = co;
8249 338 : 8718737 : a->to = to;
339 : 8718737 : a->from = from;
340 : :
341 : : /*
342 : : * Put the new arc on the beginning, not the end, of the chains; it's
343 : : * simpler here, and freearc() is the same cost either way. See also the
344 : : * logic in moveins() and its cohorts, as well as fixempties().
345 : : */
346 : 8718737 : a->inchain = to->ins;
3613 347 : 8718737 : a->inchainRev = NULL;
348 [ + + ]: 8718737 : if (to->ins)
349 : 8409600 : to->ins->inchainRev = a;
8249 350 : 8718737 : to->ins = a;
351 : 8718737 : a->outchain = from->outs;
3613 352 : 8718737 : a->outchainRev = NULL;
353 [ + + ]: 8718737 : if (from->outs)
354 : 8451635 : from->outs->outchainRev = a;
8249 355 : 8718737 : from->outs = a;
356 : :
357 : 8718737 : from->nouts++;
358 : 8718737 : to->nins++;
359 : :
360 [ + + + + : 8718737 : if (COLORED(a) && nfa->parent == NULL)
+ + + + +
+ ]
361 : 799568 : colorchain(nfa->cm, a);
362 : : }
363 : :
364 : : /*
365 : : * allocarc - allocate a new arc within an NFA
366 : : */
367 : : static struct arc * /* NULL for failure */
1653 368 : 8724446 : allocarc(struct nfa *nfa)
369 : : {
370 : : struct arc *a;
371 : :
372 : : /* first, recycle anything that's on the freelist */
373 [ + + ]: 8724446 : if (nfa->freearcs != NULL)
374 : : {
375 : 692858 : a = nfa->freearcs;
376 : 692858 : nfa->freearcs = a->freechain;
377 : : }
378 : : /* otherwise, is there anything left in the last arcbatch? */
379 [ + + + + ]: 8031588 : else if (nfa->lastab != NULL && nfa->lastabused < nfa->lastab->narcs)
380 : : {
381 : 8007869 : a = &nfa->lastab->a[nfa->lastabused++];
382 : : }
383 : : /* otherwise, need to allocate a new arcbatch */
384 : : else
385 : : {
386 : : struct arcbatch *newAb;
387 : : size_t narcs;
388 : :
3613 389 [ + + ]: 23719 : if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE)
390 : : {
391 [ + + ]: 5709 : NERR(REG_ETOOBIG);
392 : 5709 : return NULL;
393 : : }
1653 394 [ + + ]: 18010 : narcs = (nfa->lastab != NULL) ? nfa->lastab->narcs * 2 : FIRSTABSIZE;
395 [ + + ]: 18010 : if (narcs > MAXABSIZE)
396 : 7529 : narcs = MAXABSIZE;
397 : 18010 : newAb = (struct arcbatch *) MALLOC(ARCBATCHSIZE(narcs));
6414 398 [ - + ]: 18010 : if (newAb == NULL)
399 : : {
8249 tgl@sss.pgh.pa.us 400 [ # # ]:UBC 0 : NERR(REG_ESPACE);
401 : 0 : return NULL;
402 : : }
1653 tgl@sss.pgh.pa.us 403 :CBC 18010 : nfa->v->spaceused += ARCBATCHSIZE(narcs);
404 : 18010 : newAb->narcs = narcs;
405 : 18010 : newAb->next = nfa->lastab;
406 : 18010 : nfa->lastab = newAb;
407 : 18010 : nfa->lastabused = 1;
408 : 18010 : a = &newAb->a[0];
409 : : }
410 : :
8249 411 : 8718737 : return a;
412 : : }
413 : :
414 : : /*
415 : : * freearc - free an arc
416 : : */
417 : : static void
2999 418 : 805630 : freearc(struct nfa *nfa,
419 : : struct arc *victim)
420 : : {
8249 421 : 805630 : struct state *from = victim->from;
422 : 805630 : struct state *to = victim->to;
423 : : struct arc *predecessor;
424 : :
425 [ - + ]: 805630 : assert(victim->type != 0);
426 : :
427 : : /* take it off color chain if necessary */
428 [ + + + + : 805630 : if (COLORED(victim) && nfa->parent == NULL)
+ + + + +
+ ]
429 : 369525 : uncolorchain(nfa->cm, victim);
430 : :
431 : : /* take it off source's out-chain */
432 [ - + ]: 805630 : assert(from != NULL);
3613 433 : 805630 : predecessor = victim->outchainRev;
434 [ + + ]: 805630 : if (predecessor == NULL)
435 : : {
436 [ - + ]: 232009 : assert(from->outs == victim);
8249 437 : 232009 : from->outs = victim->outchain;
438 : : }
439 : : else
440 : : {
3613 441 [ - + ]: 573621 : assert(predecessor->outchain == victim);
442 : 573621 : predecessor->outchain = victim->outchain;
443 : : }
444 [ + + ]: 805630 : if (victim->outchain != NULL)
445 : : {
446 [ - + ]: 511496 : assert(victim->outchain->outchainRev == victim);
447 : 511496 : victim->outchain->outchainRev = predecessor;
448 : : }
8249 449 : 805630 : from->nouts--;
450 : :
451 : : /* take it off target's in-chain */
452 [ - + ]: 805630 : assert(to != NULL);
3613 453 : 805630 : predecessor = victim->inchainRev;
454 [ + + ]: 805630 : if (predecessor == NULL)
455 : : {
456 [ - + ]: 388378 : assert(to->ins == victim);
8249 457 : 388378 : to->ins = victim->inchain;
458 : : }
459 : : else
460 : : {
3613 461 [ - + ]: 417252 : assert(predecessor->inchain == victim);
462 : 417252 : predecessor->inchain = victim->inchain;
463 : : }
464 [ + + ]: 805630 : if (victim->inchain != NULL)
465 : : {
466 [ - + ]: 527225 : assert(victim->inchain->inchainRev == victim);
467 : 527225 : victim->inchain->inchainRev = predecessor;
468 : : }
8249 469 : 805630 : to->nins--;
470 : :
471 : : /* clean up and place on NFA's free list */
472 : 805630 : victim->type = 0;
473 : 805630 : victim->from = NULL; /* precautions... */
474 : 805630 : victim->to = NULL;
475 : 805630 : victim->inchain = NULL;
3613 476 : 805630 : victim->inchainRev = NULL;
8249 477 : 805630 : victim->outchain = NULL;
3613 478 : 805630 : victim->outchainRev = NULL;
1653 479 : 805630 : victim->freechain = nfa->freearcs;
480 : 805630 : nfa->freearcs = victim;
8249 481 : 805630 : }
482 : :
483 : : /*
484 : : * changearcsource - flip an arc to have a different from state
485 : : *
486 : : * Caller must have verified that there is no pre-existing duplicate arc.
487 : : */
488 : : static void
1653 489 : 294 : changearcsource(struct arc *a, struct state *newfrom)
490 : : {
491 : 294 : struct state *oldfrom = a->from;
492 : : struct arc *predecessor;
493 : :
494 [ - + ]: 294 : assert(oldfrom != newfrom);
495 : :
496 : : /* take it off old source's out-chain */
497 [ - + ]: 294 : assert(oldfrom != NULL);
498 : 294 : predecessor = a->outchainRev;
499 [ + - ]: 294 : if (predecessor == NULL)
500 : : {
501 [ - + ]: 294 : assert(oldfrom->outs == a);
502 : 294 : oldfrom->outs = a->outchain;
503 : : }
504 : : else
505 : : {
1653 tgl@sss.pgh.pa.us 506 [ # # ]:UBC 0 : assert(predecessor->outchain == a);
507 : 0 : predecessor->outchain = a->outchain;
508 : : }
1653 tgl@sss.pgh.pa.us 509 [ + + ]:CBC 294 : if (a->outchain != NULL)
510 : : {
511 [ - + ]: 287 : assert(a->outchain->outchainRev == a);
512 : 287 : a->outchain->outchainRev = predecessor;
513 : : }
514 : 294 : oldfrom->nouts--;
515 : :
516 : 294 : a->from = newfrom;
517 : :
518 : : /* prepend it to new source's out-chain */
519 : 294 : a->outchain = newfrom->outs;
520 : 294 : a->outchainRev = NULL;
521 [ + - ]: 294 : if (newfrom->outs)
522 : 294 : newfrom->outs->outchainRev = a;
523 : 294 : newfrom->outs = a;
524 : 294 : newfrom->nouts++;
525 : 294 : }
526 : :
527 : : /*
528 : : * changearctarget - flip an arc to have a different to state
529 : : *
530 : : * Caller must have verified that there is no pre-existing duplicate arc.
531 : : */
532 : : static void
2999 533 : 160 : changearctarget(struct arc *a, struct state *newto)
534 : : {
3613 535 : 160 : struct state *oldto = a->to;
536 : : struct arc *predecessor;
537 : :
538 [ - + ]: 160 : assert(oldto != newto);
539 : :
540 : : /* take it off old target's in-chain */
541 [ - + ]: 160 : assert(oldto != NULL);
542 : 160 : predecessor = a->inchainRev;
543 [ + - ]: 160 : if (predecessor == NULL)
544 : : {
545 [ - + ]: 160 : assert(oldto->ins == a);
546 : 160 : oldto->ins = a->inchain;
547 : : }
548 : : else
549 : : {
3613 tgl@sss.pgh.pa.us 550 [ # # ]:UBC 0 : assert(predecessor->inchain == a);
551 : 0 : predecessor->inchain = a->inchain;
552 : : }
3613 tgl@sss.pgh.pa.us 553 [ + + ]:CBC 160 : if (a->inchain != NULL)
554 : : {
555 [ - + ]: 156 : assert(a->inchain->inchainRev == a);
556 : 156 : a->inchain->inchainRev = predecessor;
557 : : }
558 : 160 : oldto->nins--;
559 : :
560 : 160 : a->to = newto;
561 : :
562 : : /* prepend it to new target's in-chain */
563 : 160 : a->inchain = newto->ins;
564 : 160 : a->inchainRev = NULL;
565 [ + - ]: 160 : if (newto->ins)
566 : 160 : newto->ins->inchainRev = a;
567 : 160 : newto->ins = a;
568 : 160 : newto->nins++;
569 : 160 : }
570 : :
571 : : /*
572 : : * hasnonemptyout - Does state have a non-EMPTY out arc?
573 : : */
574 : : static int
2999 575 : 120340 : hasnonemptyout(struct state *s)
576 : : {
577 : : struct arc *a;
578 : :
4566 579 [ + + ]: 134453 : for (a = s->outs; a != NULL; a = a->outchain)
580 : : {
581 [ + + ]: 132473 : if (a->type != EMPTY)
582 : 118360 : return 1;
583 : : }
584 : 1980 : return 0;
585 : : }
586 : :
587 : : /*
588 : : * findarc - find arc, if any, from given source with given type and color
589 : : * If there is more than one such arc, the result is random.
590 : : */
591 : : static struct arc *
2999 592 : 317 : findarc(struct state *s,
593 : : int type,
594 : : color co)
595 : : {
596 : : struct arc *a;
597 : :
8249 598 [ + + ]: 958 : for (a = s->outs; a != NULL; a = a->outchain)
599 [ + - + + ]: 644 : if (a->type == type && a->co == co)
600 : 3 : return a;
601 : 314 : return NULL;
602 : : }
603 : :
604 : : /*
605 : : * cparc - allocate a new arc within an NFA, copying details from old one
606 : : */
607 : : static void
2999 608 : 750091 : cparc(struct nfa *nfa,
609 : : struct arc *oa,
610 : : struct state *from,
611 : : struct state *to)
612 : : {
8249 613 : 750091 : newarc(nfa, oa->type, oa->co, from, to);
614 : 750091 : }
615 : :
616 : : /*
617 : : * sortins - sort the in arcs of a state by from/color/type
618 : : */
619 : : static void
2999 620 : 15403 : sortins(struct nfa *nfa,
621 : : struct state *s)
622 : : {
623 : : struct arc **sortarray;
624 : : struct arc *a;
3613 625 : 15403 : int n = s->nins;
626 : : int i;
627 : :
628 [ + + ]: 15403 : if (n <= 1)
629 : 2 : return; /* nothing to do */
630 : : /* make an array of arc pointers ... */
631 : 15401 : sortarray = (struct arc **) MALLOC(n * sizeof(struct arc *));
632 [ - + ]: 15401 : if (sortarray == NULL)
633 : : {
3613 tgl@sss.pgh.pa.us 634 [ # # ]:UBC 0 : NERR(REG_ESPACE);
635 : 0 : return;
636 : : }
3613 tgl@sss.pgh.pa.us 637 :CBC 15401 : i = 0;
638 [ + + ]: 68370 : for (a = s->ins; a != NULL; a = a->inchain)
639 : 52969 : sortarray[i++] = a;
640 [ - + ]: 15401 : assert(i == n);
641 : : /* ... sort the array */
642 : 15401 : qsort(sortarray, n, sizeof(struct arc *), sortins_cmp);
643 : : /* ... and rebuild arc list in order */
644 : : /* it seems worth special-casing first and last items to simplify loop */
645 : 15401 : a = sortarray[0];
646 : 15401 : s->ins = a;
647 : 15401 : a->inchain = sortarray[1];
648 : 15401 : a->inchainRev = NULL;
649 [ + + ]: 37568 : for (i = 1; i < n - 1; i++)
650 : : {
651 : 22167 : a = sortarray[i];
652 : 22167 : a->inchain = sortarray[i + 1];
653 : 22167 : a->inchainRev = sortarray[i - 1];
654 : : }
655 : 15401 : a = sortarray[i];
656 : 15401 : a->inchain = NULL;
657 : 15401 : a->inchainRev = sortarray[i - 1];
658 : 15401 : FREE(sortarray);
659 : : }
660 : :
661 : : static int
662 : 37894154 : sortins_cmp(const void *a, const void *b)
663 : : {
2999 664 : 37894154 : const struct arc *aa = *((const struct arc *const *) a);
665 : 37894154 : const struct arc *bb = *((const struct arc *const *) b);
666 : :
667 : : /* we check the fields in the order they are most likely to be different */
3613 668 [ + + ]: 37894154 : if (aa->from->no < bb->from->no)
669 : 30138905 : return -1;
670 [ + + ]: 7755249 : if (aa->from->no > bb->from->no)
671 : 7524363 : return 1;
672 [ + + ]: 230886 : if (aa->co < bb->co)
673 : 122786 : return -1;
674 [ + + ]: 108100 : if (aa->co > bb->co)
675 : 106488 : return 1;
676 [ + + ]: 1612 : if (aa->type < bb->type)
677 : 68 : return -1;
678 [ + + ]: 1544 : if (aa->type > bb->type)
679 : 33 : return 1;
680 : 1511 : return 0;
681 : : }
682 : :
683 : : /*
684 : : * sortouts - sort the out arcs of a state by to/color/type
685 : : */
686 : : static void
2999 687 : 16 : sortouts(struct nfa *nfa,
688 : : struct state *s)
689 : : {
690 : : struct arc **sortarray;
691 : : struct arc *a;
3613 692 : 16 : int n = s->nouts;
693 : : int i;
694 : :
695 [ - + ]: 16 : if (n <= 1)
3613 tgl@sss.pgh.pa.us 696 :UBC 0 : return; /* nothing to do */
697 : : /* make an array of arc pointers ... */
3613 tgl@sss.pgh.pa.us 698 :CBC 16 : sortarray = (struct arc **) MALLOC(n * sizeof(struct arc *));
699 [ - + ]: 16 : if (sortarray == NULL)
700 : : {
3613 tgl@sss.pgh.pa.us 701 [ # # ]:UBC 0 : NERR(REG_ESPACE);
702 : 0 : return;
703 : : }
3613 tgl@sss.pgh.pa.us 704 :CBC 16 : i = 0;
705 [ + + ]: 484 : for (a = s->outs; a != NULL; a = a->outchain)
706 : 468 : sortarray[i++] = a;
707 [ - + ]: 16 : assert(i == n);
708 : : /* ... sort the array */
709 : 16 : qsort(sortarray, n, sizeof(struct arc *), sortouts_cmp);
710 : : /* ... and rebuild arc list in order */
711 : : /* it seems worth special-casing first and last items to simplify loop */
712 : 16 : a = sortarray[0];
713 : 16 : s->outs = a;
714 : 16 : a->outchain = sortarray[1];
715 : 16 : a->outchainRev = NULL;
716 [ + + ]: 452 : for (i = 1; i < n - 1; i++)
717 : : {
718 : 436 : a = sortarray[i];
719 : 436 : a->outchain = sortarray[i + 1];
720 : 436 : a->outchainRev = sortarray[i - 1];
721 : : }
722 : 16 : a = sortarray[i];
723 : 16 : a->outchain = NULL;
724 : 16 : a->outchainRev = sortarray[i - 1];
725 : 16 : FREE(sortarray);
726 : : }
727 : :
728 : : static int
729 : 2746 : sortouts_cmp(const void *a, const void *b)
730 : : {
2999 731 : 2746 : const struct arc *aa = *((const struct arc *const *) a);
732 : 2746 : const struct arc *bb = *((const struct arc *const *) b);
733 : :
734 : : /* we check the fields in the order they are most likely to be different */
3613 735 [ + + ]: 2746 : if (aa->to->no < bb->to->no)
736 : 305 : return -1;
737 [ + + ]: 2441 : if (aa->to->no > bb->to->no)
738 : 80 : return 1;
739 [ + + ]: 2361 : if (aa->co < bb->co)
740 : 1281 : return -1;
741 [ + + ]: 1080 : if (aa->co > bb->co)
742 : 1058 : return 1;
743 [ + + ]: 22 : if (aa->type < bb->type)
744 : 1 : return -1;
745 [ + + ]: 21 : if (aa->type > bb->type)
746 : 7 : return 1;
747 : 14 : return 0;
748 : : }
749 : :
750 : : /*
751 : : * Common decision logic about whether to use arc-by-arc operations or
752 : : * sort/merge. If there's just a few source arcs we cannot recoup the
753 : : * cost of sorting the destination arc list, no matter how large it is.
754 : : * Otherwise, limit the number of arc-by-arc comparisons to about 1000
755 : : * (a somewhat arbitrary choice, but the breakeven point would probably
756 : : * be machine dependent anyway).
757 : : */
758 : : #define BULK_ARC_OP_USE_SORT(nsrcarcs, ndestarcs) \
759 : : ((nsrcarcs) < 4 ? 0 : ((nsrcarcs) > 32 || (ndestarcs) > 32))
760 : :
761 : : /*
762 : : * moveins - move all in arcs of a state to another state
763 : : *
764 : : * You might think this could be done better by just updating the
765 : : * existing arcs, and you would be right if it weren't for the need
766 : : * for duplicate suppression, which makes it easier to just make new
767 : : * ones to exploit the suppression built into newarc.
768 : : *
769 : : * However, if we have a whole lot of arcs to deal with, retail duplicate
770 : : * checks become too slow. In that case we proceed by sorting and merging
771 : : * the arc lists, and then we can indeed just update the arcs in-place.
772 : : *
773 : : * On the other hand, it's also true that this is frequently called with
774 : : * a brand-new newState that has no existing in-arcs. In that case,
775 : : * de-duplication is unnecessary, so we can just blindly move all the arcs.
776 : : */
777 : : static void
2999 778 : 130594 : moveins(struct nfa *nfa,
779 : : struct state *oldState,
780 : : struct state *newState)
781 : : {
6414 782 [ - + ]: 130594 : assert(oldState != newState);
783 : :
1481 784 [ + + ]: 130594 : if (newState->nins == 0)
785 : : {
786 : : /* No need for de-duplication */
787 : : struct arc *a;
788 : :
789 [ + + ]: 108762 : while ((a = oldState->ins) != NULL)
790 : : {
791 : 55848 : createarc(nfa, a->type, a->co, a->from, newState);
792 : 55848 : freearc(nfa, a);
793 : : }
794 : : }
795 [ + + + + : 77680 : else if (!BULK_ARC_OP_USE_SORT(oldState->nins, newState->nins))
+ + ]
8069 bruce@momjian.us 796 : 77634 : {
797 : : /* With not too many arcs, just do them one at a time */
798 : : struct arc *a;
799 : :
3613 tgl@sss.pgh.pa.us 800 [ + + ]: 191234 : while ((a = oldState->ins) != NULL)
801 : : {
802 : 113600 : cparc(nfa, a, a->from, newState);
803 : 113600 : freearc(nfa, a);
804 : : }
805 : : }
806 : : else
807 : : {
808 : : /*
809 : : * With many arcs, use a sort-merge approach. Note changearctarget()
810 : : * will put the arc onto the front of newState's chain, so it does not
811 : : * break our walk through the sorted part of the chain.
812 : : */
813 : : struct arc *oa;
814 : : struct arc *na;
815 : :
816 : : /*
817 : : * Because we bypass newarc() in this code path, we'd better include a
818 : : * cancel check.
819 : : */
882 tmunro@postgresql.or 820 [ - + ]: 46 : INTERRUPT(nfa->v->re);
821 : :
3613 tgl@sss.pgh.pa.us 822 : 46 : sortins(nfa, oldState);
823 : 46 : sortins(nfa, newState);
824 [ - + ]: 46 : if (NISERR())
3613 tgl@sss.pgh.pa.us 825 :UBC 0 : return; /* might have failed to sort */
3613 tgl@sss.pgh.pa.us 826 :CBC 46 : oa = oldState->ins;
827 : 46 : na = newState->ins;
828 [ + + + + ]: 1653 : while (oa != NULL && na != NULL)
829 : : {
830 : 1607 : struct arc *a = oa;
831 : :
832 [ + + + - ]: 1607 : switch (sortins_cmp(&oa, &na))
833 : : {
834 : 83 : case -1:
835 : : /* newState does not have anything matching oa */
836 : 83 : oa = oa->inchain;
837 : :
838 : : /*
839 : : * Rather than doing createarc+freearc, we can just unlink
840 : : * and relink the existing arc struct.
841 : : */
842 : 83 : changearctarget(a, newState);
843 : 83 : break;
844 : 236 : case 0:
845 : : /* match, advance in both lists */
846 : 236 : oa = oa->inchain;
847 : 236 : na = na->inchain;
848 : : /* ... and drop duplicate arc from oldState */
849 : 236 : freearc(nfa, a);
850 : 236 : break;
851 : 1288 : case +1:
852 : : /* advance only na; oa might have a match later */
853 : 1288 : na = na->inchain;
854 : 1288 : break;
3613 tgl@sss.pgh.pa.us 855 :UBC 0 : default:
856 : 0 : assert(NOTREACHED);
857 : : }
858 : : }
3613 tgl@sss.pgh.pa.us 859 [ + + ]:CBC 123 : while (oa != NULL)
860 : : {
861 : : /* newState does not have anything matching oa */
862 : 77 : struct arc *a = oa;
863 : :
864 : 77 : oa = oa->inchain;
865 : 77 : changearctarget(a, newState);
866 : : }
867 : : }
868 : :
6414 869 [ - + ]: 130594 : assert(oldState->nins == 0);
870 [ - + ]: 130594 : assert(oldState->ins == NULL);
871 : : }
872 : :
873 : : /*
874 : : * copyins - copy in arcs of a state to another state
875 : : *
876 : : * The comments for moveins() apply here as well. However, in current
877 : : * usage, this is *only* called with brand-new target states, so that
878 : : * only the "no need for de-duplication" code path is ever reached.
879 : : * We keep the rest #ifdef'd out in case it's needed in the future.
880 : : */
881 : : static void
2999 882 : 9431 : copyins(struct nfa *nfa,
883 : : struct state *oldState,
884 : : struct state *newState)
885 : : {
6414 886 [ - + ]: 9431 : assert(oldState != newState);
1481 887 [ - + ]: 9431 : assert(newState->nins == 0); /* see comment above */
888 : :
889 [ + - ]: 9431 : if (newState->nins == 0)
890 : : {
891 : : /* No need for de-duplication */
892 : : struct arc *a;
893 : :
894 [ + + ]: 129982 : for (a = oldState->ins; a != NULL; a = a->inchain)
895 : 120551 : createarc(nfa, a->type, a->co, a->from, newState);
896 : : }
897 : : #ifdef NOT_USED /* see comment above */
898 : : else if (!BULK_ARC_OP_USE_SORT(oldState->nins, newState->nins))
899 : : {
900 : : /* With not too many arcs, just do them one at a time */
901 : : struct arc *a;
902 : :
903 : : for (a = oldState->ins; a != NULL; a = a->inchain)
904 : : cparc(nfa, a, a->from, newState);
905 : : }
906 : : else
907 : : {
908 : : /*
909 : : * With many arcs, use a sort-merge approach. Note that createarc()
910 : : * will put new arcs onto the front of newState's chain, so it does
911 : : * not break our walk through the sorted part of the chain.
912 : : */
913 : : struct arc *oa;
914 : : struct arc *na;
915 : :
916 : : /*
917 : : * Because we bypass newarc() in this code path, we'd better include a
918 : : * cancel check.
919 : : */
920 : : INTERRUPT(nfa->v->re);
921 : :
922 : : sortins(nfa, oldState);
923 : : sortins(nfa, newState);
924 : : if (NISERR())
925 : : return; /* might have failed to sort */
926 : : oa = oldState->ins;
927 : : na = newState->ins;
928 : : while (oa != NULL && na != NULL)
929 : : {
930 : : struct arc *a = oa;
931 : :
932 : : switch (sortins_cmp(&oa, &na))
933 : : {
934 : : case -1:
935 : : /* newState does not have anything matching oa */
936 : : oa = oa->inchain;
937 : : createarc(nfa, a->type, a->co, a->from, newState);
938 : : break;
939 : : case 0:
940 : : /* match, advance in both lists */
941 : : oa = oa->inchain;
942 : : na = na->inchain;
943 : : break;
944 : : case +1:
945 : : /* advance only na; oa might have a match later */
946 : : na = na->inchain;
947 : : break;
948 : : default:
949 : : assert(NOTREACHED);
950 : : }
951 : : }
952 : : while (oa != NULL)
953 : : {
954 : : /* newState does not have anything matching oa */
955 : : struct arc *a = oa;
956 : :
957 : : oa = oa->inchain;
958 : : createarc(nfa, a->type, a->co, a->from, newState);
959 : : }
960 : : }
961 : : #endif /* NOT_USED */
3613 962 : 9431 : }
963 : :
964 : : /*
965 : : * mergeins - merge a list of inarcs into a state
966 : : *
967 : : * This is much like copyins, but the source arcs are listed in an array,
968 : : * and are not guaranteed unique. It's okay to clobber the array contents.
969 : : */
970 : : static void
2999 971 : 137942 : mergeins(struct nfa *nfa,
972 : : struct state *s,
973 : : struct arc **arcarray,
974 : : int arccount)
975 : : {
976 : : struct arc *na;
977 : : int i;
978 : : int j;
979 : :
3613 980 [ + + ]: 137942 : if (arccount <= 0)
981 : 122631 : return;
982 : :
983 : : /*
984 : : * Because we bypass newarc() in this code path, we'd better include a
985 : : * cancel check.
986 : : */
882 tmunro@postgresql.or 987 [ + + ]: 15311 : INTERRUPT(nfa->v->re);
988 : :
989 : : /* Sort existing inarcs as well as proposed new ones */
3613 tgl@sss.pgh.pa.us 990 : 15311 : sortins(nfa, s);
991 [ - + ]: 15311 : if (NISERR())
3613 tgl@sss.pgh.pa.us 992 :UBC 0 : return; /* might have failed to sort */
993 : :
3613 tgl@sss.pgh.pa.us 994 :CBC 15311 : qsort(arcarray, arccount, sizeof(struct arc *), sortins_cmp);
995 : :
996 : : /*
997 : : * arcarray very likely includes dups, so we must eliminate them. (This
998 : : * could be folded into the next loop, but it's not worth the trouble.)
999 : : */
1000 : 15311 : j = 0;
1001 [ + + ]: 7515445 : for (i = 1; i < arccount; i++)
1002 : : {
1003 [ + + - ]: 7500134 : switch (sortins_cmp(&arcarray[j], &arcarray[i]))
1004 : : {
1005 : 7499528 : case -1:
1006 : : /* non-dup */
1007 : 7499528 : arcarray[++j] = arcarray[i];
1008 : 7499528 : break;
1009 : 606 : case 0:
1010 : : /* dup */
1011 : 606 : break;
3613 tgl@sss.pgh.pa.us 1012 :UBC 0 : default:
1013 : : /* trouble */
1014 : 0 : assert(NOTREACHED);
1015 : : }
1016 : : }
3613 tgl@sss.pgh.pa.us 1017 :CBC 15311 : arccount = j + 1;
1018 : :
1019 : : /*
1020 : : * Now merge into s' inchain. Note that createarc() will put new arcs
1021 : : * onto the front of s's chain, so it does not break our walk through the
1022 : : * sorted part of the chain.
1023 : : */
1024 : 15311 : i = 0;
1025 : 15311 : na = s->ins;
1026 [ + + + + ]: 7530546 : while (i < arccount && na != NULL)
1027 : : {
1028 : 7515235 : struct arc *a = arcarray[i];
1029 : :
1030 [ + + + - ]: 7515235 : switch (sortins_cmp(&a, &na))
1031 : : {
1032 : 7493629 : case -1:
1033 : : /* s does not have anything matching a */
1034 : 7493629 : createarc(nfa, a->type, a->co, a->from, s);
1035 : 7493629 : i++;
1036 : 7493629 : break;
1037 : 10 : case 0:
1038 : : /* match, advance in both lists */
1039 : 10 : i++;
1040 : 10 : na = na->inchain;
1041 : 10 : break;
1042 : 21596 : case +1:
1043 : : /* advance only na; array might have a match later */
1044 : 21596 : na = na->inchain;
1045 : 21596 : break;
3613 tgl@sss.pgh.pa.us 1046 :UBC 0 : default:
1047 : 0 : assert(NOTREACHED);
1048 : : }
1049 : : }
3613 tgl@sss.pgh.pa.us 1050 [ + + ]:CBC 36511 : while (i < arccount)
1051 : : {
1052 : : /* s does not have anything matching a */
1053 : 21200 : struct arc *a = arcarray[i];
1054 : :
1055 : 21200 : createarc(nfa, a->type, a->co, a->from, s);
1056 : 21200 : i++;
1057 : : }
1058 : : }
1059 : :
1060 : : /*
1061 : : * moveouts - move all out arcs of a state to another state
1062 : : *
1063 : : * See comments for moveins()
1064 : : */
1065 : : static void
2999 1066 : 34972 : moveouts(struct nfa *nfa,
1067 : : struct state *oldState,
1068 : : struct state *newState)
1069 : : {
6414 1070 [ - + ]: 34972 : assert(oldState != newState);
1071 : :
1481 1072 [ + + ]: 34972 : if (newState->nouts == 0)
1073 : : {
1074 : : /* No need for de-duplication */
1075 : : struct arc *a;
1076 : :
1077 [ + + ]: 27792 : while ((a = oldState->outs) != NULL)
1078 : : {
1079 : 15238 : createarc(nfa, a->type, a->co, newState, a->to);
1080 : 15238 : freearc(nfa, a);
1081 : : }
1082 : : }
1083 [ + + + + : 22418 : else if (!BULK_ARC_OP_USE_SORT(oldState->nouts, newState->nouts))
+ - ]
8069 bruce@momjian.us 1084 : 22410 : {
1085 : : /* With not too many arcs, just do them one at a time */
1086 : : struct arc *a;
1087 : :
3613 tgl@sss.pgh.pa.us 1088 [ + + ]: 54136 : while ((a = oldState->outs) != NULL)
1089 : : {
1090 : 31726 : cparc(nfa, a, newState, a->to);
1091 : 31726 : freearc(nfa, a);
1092 : : }
1093 : : }
1094 : : else
1095 : : {
1096 : : /*
1097 : : * With many arcs, use a sort-merge approach. Note changearcsource()
1098 : : * will put the arc onto the front of newState's chain, so it does not
1099 : : * break our walk through the sorted part of the chain.
1100 : : */
1101 : : struct arc *oa;
1102 : : struct arc *na;
1103 : :
1104 : : /*
1105 : : * Because we bypass newarc() in this code path, we'd better include a
1106 : : * cancel check.
1107 : : */
882 tmunro@postgresql.or 1108 [ - + ]: 8 : INTERRUPT(nfa->v->re);
1109 : :
3613 tgl@sss.pgh.pa.us 1110 : 8 : sortouts(nfa, oldState);
1111 : 8 : sortouts(nfa, newState);
1112 [ - + ]: 8 : if (NISERR())
3613 tgl@sss.pgh.pa.us 1113 :UBC 0 : return; /* might have failed to sort */
3613 tgl@sss.pgh.pa.us 1114 :CBC 8 : oa = oldState->outs;
1115 : 8 : na = newState->outs;
1116 [ + + + + ]: 288 : while (oa != NULL && na != NULL)
1117 : : {
1118 : 280 : struct arc *a = oa;
1119 : :
1120 [ + + + - ]: 280 : switch (sortouts_cmp(&oa, &na))
1121 : : {
1122 : 258 : case -1:
1123 : : /* newState does not have anything matching oa */
1124 : 258 : oa = oa->outchain;
1125 : :
1126 : : /*
1127 : : * Rather than doing createarc+freearc, we can just unlink
1128 : : * and relink the existing arc struct.
1129 : : */
1653 1130 : 258 : changearcsource(a, newState);
3613 1131 : 258 : break;
1132 : 14 : case 0:
1133 : : /* match, advance in both lists */
1134 : 14 : oa = oa->outchain;
1135 : 14 : na = na->outchain;
1136 : : /* ... and drop duplicate arc from oldState */
1137 : 14 : freearc(nfa, a);
1138 : 14 : break;
1139 : 8 : case +1:
1140 : : /* advance only na; oa might have a match later */
1141 : 8 : na = na->outchain;
1142 : 8 : break;
3613 tgl@sss.pgh.pa.us 1143 :UBC 0 : default:
1144 : 0 : assert(NOTREACHED);
1145 : : }
1146 : : }
3613 tgl@sss.pgh.pa.us 1147 [ + + ]:CBC 44 : while (oa != NULL)
1148 : : {
1149 : : /* newState does not have anything matching oa */
1150 : 36 : struct arc *a = oa;
1151 : :
1152 : 36 : oa = oa->outchain;
1653 1153 : 36 : changearcsource(a, newState);
1154 : : }
1155 : : }
1156 : :
3613 1157 [ - + ]: 34972 : assert(oldState->nouts == 0);
1158 [ - + ]: 34972 : assert(oldState->outs == NULL);
1159 : : }
1160 : :
1161 : : /*
1162 : : * copyouts - copy out arcs of a state to another state
1163 : : *
1164 : : * See comments for copyins()
1165 : : */
1166 : : static void
2999 1167 : 7128 : copyouts(struct nfa *nfa,
1168 : : struct state *oldState,
1169 : : struct state *newState)
1170 : : {
6414 1171 [ - + ]: 7128 : assert(oldState != newState);
1481 1172 [ - + ]: 7128 : assert(newState->nouts == 0); /* see comment above */
1173 : :
1174 [ + - ]: 7128 : if (newState->nouts == 0)
1175 : : {
1176 : : /* No need for de-duplication */
1177 : : struct arc *a;
1178 : :
1179 [ + + ]: 243939 : for (a = oldState->outs; a != NULL; a = a->outchain)
1180 : 236811 : createarc(nfa, a->type, a->co, newState, a->to);
1181 : : }
1182 : : #ifdef NOT_USED /* see comment above */
1183 : : else if (!BULK_ARC_OP_USE_SORT(oldState->nouts, newState->nouts))
1184 : : {
1185 : : /* With not too many arcs, just do them one at a time */
1186 : : struct arc *a;
1187 : :
1188 : : for (a = oldState->outs; a != NULL; a = a->outchain)
1189 : : cparc(nfa, a, newState, a->to);
1190 : : }
1191 : : else
1192 : : {
1193 : : /*
1194 : : * With many arcs, use a sort-merge approach. Note that createarc()
1195 : : * will put new arcs onto the front of newState's chain, so it does
1196 : : * not break our walk through the sorted part of the chain.
1197 : : */
1198 : : struct arc *oa;
1199 : : struct arc *na;
1200 : :
1201 : : /*
1202 : : * Because we bypass newarc() in this code path, we'd better include a
1203 : : * cancel check.
1204 : : */
1205 : : INTERRUPT(nfa->v->re);
1206 : :
1207 : : sortouts(nfa, oldState);
1208 : : sortouts(nfa, newState);
1209 : : if (NISERR())
1210 : : return; /* might have failed to sort */
1211 : : oa = oldState->outs;
1212 : : na = newState->outs;
1213 : : while (oa != NULL && na != NULL)
1214 : : {
1215 : : struct arc *a = oa;
1216 : :
1217 : : switch (sortouts_cmp(&oa, &na))
1218 : : {
1219 : : case -1:
1220 : : /* newState does not have anything matching oa */
1221 : : oa = oa->outchain;
1222 : : createarc(nfa, a->type, a->co, newState, a->to);
1223 : : break;
1224 : : case 0:
1225 : : /* match, advance in both lists */
1226 : : oa = oa->outchain;
1227 : : na = na->outchain;
1228 : : break;
1229 : : case +1:
1230 : : /* advance only na; oa might have a match later */
1231 : : na = na->outchain;
1232 : : break;
1233 : : default:
1234 : : assert(NOTREACHED);
1235 : : }
1236 : : }
1237 : : while (oa != NULL)
1238 : : {
1239 : : /* newState does not have anything matching oa */
1240 : : struct arc *a = oa;
1241 : :
1242 : : oa = oa->outchain;
1243 : : createarc(nfa, a->type, a->co, newState, a->to);
1244 : : }
1245 : : }
1246 : : #endif /* NOT_USED */
8249 1247 : 7128 : }
1248 : :
1249 : : /*
1250 : : * cloneouts - copy out arcs of a state to another state pair, modifying type
1251 : : *
1252 : : * This is only used to convert PLAIN arcs to AHEAD/BEHIND arcs, which share
1253 : : * the same interpretation of "co". It wouldn't be sensible with LACONs.
1254 : : */
1255 : : static void
2999 1256 : 175 : cloneouts(struct nfa *nfa,
1257 : : struct state *old,
1258 : : struct state *from,
1259 : : struct state *to,
1260 : : int type)
1261 : : {
1262 : : struct arc *a;
1263 : :
8249 1264 [ - + ]: 175 : assert(old != from);
1659 1265 [ + + - + ]: 175 : assert(type == AHEAD || type == BEHIND);
1266 : :
8249 1267 [ + + ]: 653 : for (a = old->outs; a != NULL; a = a->outchain)
1268 : : {
1659 1269 [ - + ]: 478 : assert(a->type == PLAIN);
8249 1270 : 478 : newarc(nfa, type, a->co, from, to);
1271 : : }
1272 : 175 : }
1273 : :
1274 : : /*
1275 : : * delsub - delete a sub-NFA, updating subre pointers if necessary
1276 : : *
1277 : : * This uses a recursive traversal of the sub-NFA, marking already-seen
1278 : : * states using their tmp pointer.
1279 : : */
1280 : : static void
2999 1281 : 5047 : delsub(struct nfa *nfa,
1282 : : struct state *lp, /* the sub-NFA goes from here... */
1283 : : struct state *rp) /* ...to here, *not* inclusive */
1284 : : {
8249 1285 [ - + ]: 5047 : assert(lp != rp);
1286 : :
8069 bruce@momjian.us 1287 : 5047 : rp->tmp = rp; /* mark end */
1288 : :
8249 tgl@sss.pgh.pa.us 1289 : 5047 : deltraverse(nfa, lp, lp);
3627 1290 [ - + ]: 5047 : if (NISERR())
3627 tgl@sss.pgh.pa.us 1291 :UBC 0 : return; /* asserts might not hold after failure */
8249 tgl@sss.pgh.pa.us 1292 [ + - - + ]:CBC 5047 : assert(lp->nouts == 0 && rp->nins == 0); /* did the job */
8069 bruce@momjian.us 1293 [ + - - + ]: 5047 : assert(lp->no != FREESTATE && rp->no != FREESTATE); /* no more */
1294 : :
1295 : 5047 : rp->tmp = NULL; /* unmark end */
1296 : 5047 : lp->tmp = NULL; /* and begin, marked by deltraverse */
1297 : : }
1298 : :
1299 : : /*
1300 : : * deltraverse - the recursive heart of delsub
1301 : : * This routine's basic job is to destroy all out-arcs of the state.
1302 : : */
1303 : : static void
2999 tgl@sss.pgh.pa.us 1304 : 14813 : deltraverse(struct nfa *nfa,
1305 : : struct state *leftend,
1306 : : struct state *s)
1307 : : {
1308 : : struct arc *a;
1309 : : struct state *to;
1310 : :
1311 : : /* Since this is recursive, it could be driven to stack overflow */
3627 1312 [ - + ]: 14813 : if (STACK_TOO_DEEP(nfa->v->re))
1313 : : {
3627 tgl@sss.pgh.pa.us 1314 [ # # ]:UBC 0 : NERR(REG_ETOOBIG);
1315 : 0 : return;
1316 : : }
1317 : :
8249 tgl@sss.pgh.pa.us 1318 [ + + ]:CBC 14813 : if (s->nouts == 0)
8069 bruce@momjian.us 1319 : 101 : return; /* nothing to do */
8249 tgl@sss.pgh.pa.us 1320 [ + + ]: 14712 : if (s->tmp != NULL)
8069 bruce@momjian.us 1321 : 4961 : return; /* already in progress */
1322 : :
1323 : 9751 : s->tmp = s; /* mark as in progress */
1324 : :
1325 [ + + ]: 19517 : while ((a = s->outs) != NULL)
1326 : : {
8249 tgl@sss.pgh.pa.us 1327 : 9766 : to = a->to;
1328 : 9766 : deltraverse(nfa, leftend, to);
3627 1329 [ - + ]: 9766 : if (NISERR())
3627 tgl@sss.pgh.pa.us 1330 :UBC 0 : return; /* asserts might not hold after failure */
8249 tgl@sss.pgh.pa.us 1331 [ + + - + ]:CBC 9766 : assert(to->nouts == 0 || to->tmp != NULL);
1332 : 9766 : freearc(nfa, a);
8069 bruce@momjian.us 1333 [ + + + + ]: 9766 : if (to->nins == 0 && to->tmp == NULL)
1334 : : {
8249 tgl@sss.pgh.pa.us 1335 [ - + ]: 4704 : assert(to->nouts == 0);
1336 : 4704 : freestate(nfa, to);
1337 : : }
1338 : : }
1339 : :
8069 bruce@momjian.us 1340 [ - + ]: 9751 : assert(s->no != FREESTATE); /* we're still here */
2999 tgl@sss.pgh.pa.us 1341 [ + + - + ]: 9751 : assert(s == leftend || s->nins != 0); /* and still reachable */
8249 1342 [ - + ]: 9751 : assert(s->nouts == 0); /* but have no outarcs */
1343 : :
8069 bruce@momjian.us 1344 : 9751 : s->tmp = NULL; /* we're done here */
1345 : : }
1346 : :
1347 : : /*
1348 : : * dupnfa - duplicate sub-NFA
1349 : : *
1350 : : * Another recursive traversal, this time using tmp to point to duplicates
1351 : : * as well as mark already-seen states. (You knew there was a reason why
1352 : : * it's a state pointer, didn't you? :-))
1353 : : */
1354 : : static void
2999 tgl@sss.pgh.pa.us 1355 : 7463 : dupnfa(struct nfa *nfa,
1356 : : struct state *start, /* duplicate of subNFA starting here */
1357 : : struct state *stop, /* and stopping here */
1358 : : struct state *from, /* stringing duplicate from here */
1359 : : struct state *to) /* to here */
1360 : : {
8069 bruce@momjian.us 1361 [ - + ]: 7463 : if (start == stop)
1362 : : {
8249 tgl@sss.pgh.pa.us 1363 :UBC 0 : newarc(nfa, EMPTY, 0, from, to);
1364 : 0 : return;
1365 : : }
1366 : :
8249 tgl@sss.pgh.pa.us 1367 :CBC 7463 : stop->tmp = to;
1368 : 7463 : duptraverse(nfa, start, from);
1369 : : /* done, except for clearing out the tmp pointers */
1370 : :
1371 : 7463 : stop->tmp = NULL;
1372 : 7463 : cleartraverse(nfa, start);
1373 : : }
1374 : :
1375 : : /*
1376 : : * duptraverse - recursive heart of dupnfa
1377 : : */
1378 : : static void
2999 1379 : 190951 : duptraverse(struct nfa *nfa,
1380 : : struct state *s,
1381 : : struct state *stmp) /* s's duplicate, or NULL */
1382 : : {
1383 : : struct arc *a;
1384 : :
1385 : : /* Since this is recursive, it could be driven to stack overflow */
3627 1386 [ - + ]: 190951 : if (STACK_TOO_DEEP(nfa->v->re))
1387 : : {
3627 tgl@sss.pgh.pa.us 1388 [ # # ]:UBC 0 : NERR(REG_ETOOBIG);
1389 : 0 : return;
1390 : : }
1391 : :
8249 tgl@sss.pgh.pa.us 1392 [ + + ]:CBC 190951 : if (s->tmp != NULL)
8069 bruce@momjian.us 1393 : 59267 : return; /* already done */
1394 : :
8249 tgl@sss.pgh.pa.us 1395 [ + + ]: 131684 : s->tmp = (stmp == NULL) ? newstate(nfa) : stmp;
8069 bruce@momjian.us 1396 [ - + ]: 131684 : if (s->tmp == NULL)
1397 : : {
8249 tgl@sss.pgh.pa.us 1398 [ # # ]:UBC 0 : assert(NISERR());
1399 : 0 : return;
1400 : : }
1401 : :
8069 bruce@momjian.us 1402 [ + + + - ]:CBC 315172 : for (a = s->outs; a != NULL && !NISERR(); a = a->outchain)
1403 : : {
1404 : 183488 : duptraverse(nfa, a->to, (struct state *) NULL);
6456 tgl@sss.pgh.pa.us 1405 [ - + ]: 183488 : if (NISERR())
6456 tgl@sss.pgh.pa.us 1406 :UBC 0 : break;
8249 tgl@sss.pgh.pa.us 1407 [ - + ]:CBC 183488 : assert(a->to->tmp != NULL);
1408 : 183488 : cparc(nfa, a, s->tmp, a->to->tmp);
1409 : : }
1410 : : }
1411 : :
1412 : : /*
1413 : : * removeconstraints - remove any constraints in an NFA
1414 : : *
1415 : : * Constraint arcs are replaced by empty arcs, essentially treating all
1416 : : * constraints as automatically satisfied.
1417 : : */
1418 : : static void
1649 1419 : 101 : removeconstraints(struct nfa *nfa,
1420 : : struct state *start, /* process subNFA starting here */
1421 : : struct state *stop) /* and stopping here */
1422 : : {
1423 [ - + ]: 101 : if (start == stop)
1649 tgl@sss.pgh.pa.us 1424 :UBC 0 : return;
1425 : :
1649 tgl@sss.pgh.pa.us 1426 :CBC 101 : stop->tmp = stop;
1427 : 101 : removetraverse(nfa, start);
1428 : : /* done, except for clearing out the tmp pointers */
1429 : :
1430 : 101 : stop->tmp = NULL;
1431 : 101 : cleartraverse(nfa, start);
1432 : : }
1433 : :
1434 : : /*
1435 : : * removetraverse - recursive heart of removeconstraints
1436 : : */
1437 : : static void
1438 : 281 : removetraverse(struct nfa *nfa,
1439 : : struct state *s)
1440 : : {
1441 : : struct arc *a;
1442 : : struct arc *oa;
1443 : :
1444 : : /* Since this is recursive, it could be driven to stack overflow */
1445 [ - + ]: 281 : if (STACK_TOO_DEEP(nfa->v->re))
1446 : : {
1649 tgl@sss.pgh.pa.us 1447 [ # # ]:UBC 0 : NERR(REG_ETOOBIG);
1448 : 0 : return;
1449 : : }
1450 : :
1649 tgl@sss.pgh.pa.us 1451 [ + + ]:CBC 281 : if (s->tmp != NULL)
1452 : 126 : return; /* already done */
1453 : :
1454 : 155 : s->tmp = s;
1455 [ + + + - ]: 335 : for (a = s->outs; a != NULL && !NISERR(); a = oa)
1456 : : {
1457 : 180 : removetraverse(nfa, a->to);
1458 [ - + ]: 180 : if (NISERR())
1649 tgl@sss.pgh.pa.us 1459 :UBC 0 : break;
1649 tgl@sss.pgh.pa.us 1460 :CBC 180 : oa = a->outchain;
1461 [ + + - ]: 180 : switch (a->type)
1462 : : {
1463 : 173 : case PLAIN:
1464 : : case EMPTY:
1465 : : case CANTMATCH:
1466 : : /* nothing to do */
1467 : 173 : break;
1468 : 7 : case AHEAD:
1469 : : case BEHIND:
1470 : : case '^':
1471 : : case '$':
1472 : : case LACON:
1473 : : /* replace it */
1474 : 7 : newarc(nfa, EMPTY, 0, s, a->to);
1475 : 7 : freearc(nfa, a);
1476 : 7 : break;
1649 tgl@sss.pgh.pa.us 1477 :UBC 0 : default:
1478 [ # # ]: 0 : NERR(REG_ASSERT);
1479 : 0 : break;
1480 : : }
1481 : : }
1482 : : }
1483 : :
1484 : : /*
1485 : : * cleartraverse - recursive cleanup for algorithms that leave tmp ptrs set
1486 : : */
1487 : : static void
2999 tgl@sss.pgh.pa.us 1488 :CBC 1085075 : cleartraverse(struct nfa *nfa,
1489 : : struct state *s)
1490 : : {
1491 : : struct arc *a;
1492 : :
1493 : : /* Since this is recursive, it could be driven to stack overflow */
3627 1494 [ - + ]: 1085075 : if (STACK_TOO_DEEP(nfa->v->re))
1495 : : {
3627 tgl@sss.pgh.pa.us 1496 [ # # ]:UBC 0 : NERR(REG_ETOOBIG);
1497 : 0 : return;
1498 : : }
1499 : :
8249 tgl@sss.pgh.pa.us 1500 [ + + ]:CBC 1085075 : if (s->tmp == NULL)
1501 : 618861 : return;
1502 : 466214 : s->tmp = NULL;
1503 : :
1504 [ + + ]: 1524146 : for (a = s->outs; a != NULL; a = a->outchain)
1505 : 1057932 : cleartraverse(nfa, a->to);
1506 : : }
1507 : :
1508 : : /*
1509 : : * single_color_transition - does getting from s1 to s2 cross one PLAIN arc?
1510 : : *
1511 : : * If traversing from s1 to s2 requires a single PLAIN match (possibly of any
1512 : : * of a set of colors), return a state whose outarc list contains only PLAIN
1513 : : * arcs of those color(s). Otherwise return NULL.
1514 : : *
1515 : : * This is used before optimizing the NFA, so there may be EMPTY arcs, which
1516 : : * we should ignore; the possibility of an EMPTY is why the result state could
1517 : : * be different from s1.
1518 : : *
1519 : : * It's worth troubling to handle multiple parallel PLAIN arcs here because a
1520 : : * bracket construct such as [abc] might yield either one or several parallel
1521 : : * PLAIN arcs depending on earlier atoms in the expression. We'd rather that
1522 : : * that implementation detail not create user-visible performance differences.
1523 : : */
1524 : : static struct state *
2999 1525 : 127 : single_color_transition(struct state *s1, struct state *s2)
1526 : : {
1527 : : struct arc *a;
1528 : :
1529 : : /* Ignore leading EMPTY arc, if any */
3599 1530 [ + - + - ]: 127 : if (s1->nouts == 1 && s1->outs->type == EMPTY)
1531 : 127 : s1 = s1->outs->to;
1532 : : /* Likewise for any trailing EMPTY arc */
1533 [ + - + - ]: 127 : if (s2->nins == 1 && s2->ins->type == EMPTY)
1534 : 127 : s2 = s2->ins->from;
1535 : : /* Perhaps we could have a single-state loop in between, if so reject */
1536 [ - + ]: 127 : if (s1 == s2)
3599 tgl@sss.pgh.pa.us 1537 :UBC 0 : return NULL;
1538 : : /* s1 must have at least one outarc... */
3599 tgl@sss.pgh.pa.us 1539 [ - + ]:CBC 127 : if (s1->outs == NULL)
3599 tgl@sss.pgh.pa.us 1540 :UBC 0 : return NULL;
1541 : : /* ... and they must all be PLAIN arcs to s2 */
3599 tgl@sss.pgh.pa.us 1542 [ + + ]:CBC 218 : for (a = s1->outs; a != NULL; a = a->outchain)
1543 : : {
1544 [ + + + + ]: 134 : if (a->type != PLAIN || a->to != s2)
1545 : 43 : return NULL;
1546 : : }
1547 : : /* OK, return s1 as the possessor of the relevant outarcs */
1548 : 84 : return s1;
1549 : : }
1550 : :
1551 : : /*
1552 : : * specialcolors - fill in special colors for an NFA
1553 : : */
1554 : : static void
2999 1555 : 9794 : specialcolors(struct nfa *nfa)
1556 : : {
1557 : : /* false colors for BOS, BOL, EOS, EOL */
8069 bruce@momjian.us 1558 [ + + ]: 9794 : if (nfa->parent == NULL)
1559 : : {
8249 tgl@sss.pgh.pa.us 1560 : 3928 : nfa->bos[0] = pseudocolor(nfa->cm);
1561 : 3928 : nfa->bos[1] = pseudocolor(nfa->cm);
1562 : 3928 : nfa->eos[0] = pseudocolor(nfa->cm);
1563 : 3928 : nfa->eos[1] = pseudocolor(nfa->cm);
1564 : : }
1565 : : else
1566 : : {
1567 [ - + ]: 5866 : assert(nfa->parent->bos[0] != COLORLESS);
1568 : 5866 : nfa->bos[0] = nfa->parent->bos[0];
1569 [ - + ]: 5866 : assert(nfa->parent->bos[1] != COLORLESS);
1570 : 5866 : nfa->bos[1] = nfa->parent->bos[1];
1571 [ - + ]: 5866 : assert(nfa->parent->eos[0] != COLORLESS);
1572 : 5866 : nfa->eos[0] = nfa->parent->eos[0];
1573 [ - + ]: 5866 : assert(nfa->parent->eos[1] != COLORLESS);
1574 : 5866 : nfa->eos[1] = nfa->parent->eos[1];
1575 : : }
1576 : 9794 : }
1577 : :
1578 : : /*
1579 : : * optimize - optimize an NFA
1580 : : *
1581 : : * The main goal of this function is not so much "optimization" (though it
1582 : : * does try to get rid of useless NFA states) as reducing the NFA to a form
1583 : : * the regex executor can handle. The executor, and indeed the cNFA format
1584 : : * that is its input, can only handle PLAIN and LACON arcs. The output of
1585 : : * the regex parser also includes EMPTY (do-nothing) arcs, as well as
1586 : : * ^, $, AHEAD, and BEHIND constraint arcs, which we must get rid of here.
1587 : : * We first get rid of EMPTY arcs and then deal with the constraint arcs.
1588 : : * The hardest part of either job is to get rid of circular loops of the
1589 : : * target arc type. We would have to do that in any case, though, as such a
1590 : : * loop would otherwise allow the executor to cycle through the loop endlessly
1591 : : * without making any progress in the input string.
1592 : : */
1593 : : static long /* re_info bits */
2999 1594 : 9791 : optimize(struct nfa *nfa,
1595 : : FILE *f) /* for debug output; NULL none */
1596 : : {
1597 : : #ifdef REG_DEBUG
1598 : : int verbose = (f != NULL) ? 1 : 0;
1599 : :
1600 : : if (verbose)
1601 : : fprintf(f, "\ninitial cleanup:\n");
1602 : : #endif
1603 : : /* If we have any CANTMATCH arcs, drop them; but this is uncommon */
295 1604 [ + + ]: 9791 : if (nfa->flags & HASCANTMATCH)
1605 : : {
1606 : 6 : removecantmatch(nfa);
1607 : 6 : nfa->flags &= ~HASCANTMATCH;
1608 : : }
8069 bruce@momjian.us 1609 : 9791 : cleanup(nfa); /* may simplify situation */
1610 : : #ifdef REG_DEBUG
1611 : : if (verbose)
1612 : : dumpnfa(nfa, f);
1613 : : if (verbose)
1614 : : fprintf(f, "\nempties:\n");
1615 : : #endif
1616 : 9791 : fixempties(nfa, f); /* get rid of EMPTY arcs */
1617 : : #ifdef REG_DEBUG
1618 : : if (verbose)
1619 : : fprintf(f, "\nconstraints:\n");
1620 : : #endif
3613 tgl@sss.pgh.pa.us 1621 : 9791 : fixconstraintloops(nfa, f); /* get rid of constraint loops */
8069 bruce@momjian.us 1622 : 9791 : pullback(nfa, f); /* pull back constraints backward */
1623 : 9791 : pushfwd(nfa, f); /* push fwd constraints forward */
1624 : : #ifdef REG_DEBUG
1625 : : if (verbose)
1626 : : fprintf(f, "\nfinal cleanup:\n");
1627 : : #endif
1628 : 9791 : cleanup(nfa); /* final tidying */
1629 : : #ifdef REG_DEBUG
1630 : : if (verbose)
1631 : : dumpnfa(nfa, f);
1632 : : #endif
1633 : 9791 : return analyze(nfa); /* and analysis */
1634 : : }
1635 : :
1636 : : /*
1637 : : * pullback - pull back constraints backward to eliminate them
1638 : : */
1639 : : static void
2999 tgl@sss.pgh.pa.us 1640 : 9791 : pullback(struct nfa *nfa,
1641 : : FILE *f) /* for debug output; NULL none */
1642 : : {
1643 : : struct state *s;
1644 : : struct state *nexts;
1645 : : struct arc *a;
1646 : : struct arc *nexta;
1647 : : struct state *intermediates;
1648 : : int progress;
1649 : :
1650 : : /* find and pull until there are no more */
1651 : : do
1652 : : {
8249 1653 : 15469 : progress = 0;
8069 bruce@momjian.us 1654 [ + + + + ]: 238954 : for (s = nfa->states; s != NULL && !NISERR(); s = nexts)
1655 : : {
8249 tgl@sss.pgh.pa.us 1656 : 223485 : nexts = s->next;
3613 1657 : 223485 : intermediates = NULL;
8069 bruce@momjian.us 1658 [ + + + - ]: 963544 : for (a = s->outs; a != NULL && !NISERR(); a = nexta)
1659 : : {
8249 tgl@sss.pgh.pa.us 1660 : 740059 : nexta = a->outchain;
1661 [ + + + + ]: 740059 : if (a->type == '^' || a->type == BEHIND)
3613 1662 [ + + ]: 50377 : if (pull(nfa, a, &intermediates))
8249 1663 : 19311 : progress = 1;
1664 : : }
1665 : : /* clear tmp fields of intermediate states created here */
3613 1666 [ + + ]: 224715 : while (intermediates != NULL)
1667 : : {
1668 : 1230 : struct state *ns = intermediates->tmp;
1669 : :
1670 : 1230 : intermediates->tmp = NULL;
1671 : 1230 : intermediates = ns;
1672 : : }
1673 : : /* if s is now useless, get rid of it */
1674 [ + + + + : 223485 : if ((s->nins == 0 || s->nouts == 0) && !s->flag)
+ + ]
1675 : 16707 : dropstate(nfa, s);
1676 : : }
8249 1677 [ + + - + ]: 15469 : if (progress && f != NULL)
8249 tgl@sss.pgh.pa.us 1678 :UBC 0 : dumpnfa(nfa, f);
8249 tgl@sss.pgh.pa.us 1679 [ + + + - ]:CBC 15469 : } while (progress && !NISERR());
1680 [ + + ]: 9791 : if (NISERR())
1681 : 3 : return;
1682 : :
1683 : : /*
1684 : : * Any ^ constraints we were able to pull to the start state can now be
1685 : : * replaced by PLAIN arcs referencing the BOS or BOL colors. There should
1686 : : * be no other ^ or BEHIND arcs left in the NFA, though we do not check
1687 : : * that here (compact() will fail if so).
1688 : : */
8069 bruce@momjian.us 1689 [ + + ]: 36678 : for (a = nfa->pre->outs; a != NULL; a = nexta)
1690 : : {
8249 tgl@sss.pgh.pa.us 1691 : 26890 : nexta = a->outchain;
8069 bruce@momjian.us 1692 [ + + ]: 26890 : if (a->type == '^')
1693 : : {
8249 tgl@sss.pgh.pa.us 1694 [ + + - + ]: 19398 : assert(a->co == 0 || a->co == 1);
1695 : 19398 : newarc(nfa, PLAIN, nfa->bos[a->co], a->from, a->to);
1696 : 19398 : freearc(nfa, a);
1697 : : }
1698 : : }
1699 : : }
1700 : :
1701 : : /*
1702 : : * pull - pull a back constraint backward past its source state
1703 : : *
1704 : : * Returns 1 if successful (which it always is unless the source is the
1705 : : * start state or we have an internal error), 0 if nothing happened.
1706 : : *
1707 : : * A significant property of this function is that it deletes no pre-existing
1708 : : * states, and no outarcs of the constraint's from state other than the given
1709 : : * constraint arc. This makes the loops in pullback() safe, at the cost that
1710 : : * we may leave useless states behind. Therefore, we leave it to pullback()
1711 : : * to delete such states.
1712 : : *
1713 : : * If the from state has multiple back-constraint outarcs, and/or multiple
1714 : : * compatible constraint inarcs, we only need to create one new intermediate
1715 : : * state per combination of predecessor and successor states. *intermediates
1716 : : * points to a list of such intermediate states for this from state (chained
1717 : : * through their tmp fields).
1718 : : */
1719 : : static int
2999 1720 : 50377 : pull(struct nfa *nfa,
1721 : : struct arc *con,
1722 : : struct state **intermediates)
1723 : : {
8249 1724 : 50377 : struct state *from = con->from;
1725 : 50377 : struct state *to = con->to;
1726 : : struct arc *a;
1727 : : struct arc *nexta;
1728 : : struct state *s;
1729 : :
3613 1730 [ - + ]: 50377 : assert(from != to); /* should have gotten rid of this earlier */
8069 bruce@momjian.us 1731 [ + + ]: 50377 : if (from->flag) /* can't pull back beyond start */
8249 tgl@sss.pgh.pa.us 1732 : 31066 : return 0;
8069 bruce@momjian.us 1733 [ + + ]: 19311 : if (from->nins == 0)
1734 : : { /* unreachable */
8249 tgl@sss.pgh.pa.us 1735 : 3652 : freearc(nfa, con);
1736 : 3652 : return 1;
1737 : : }
1738 : :
1739 : : /*
1740 : : * First, clone from state if necessary to avoid other outarcs. This may
1741 : : * seem wasteful, but it simplifies the logic, and we'll get rid of the
1742 : : * clone state again at the bottom.
1743 : : */
8069 bruce@momjian.us 1744 [ + + ]: 15659 : if (from->nouts > 1)
1745 : : {
8249 tgl@sss.pgh.pa.us 1746 : 9431 : s = newstate(nfa);
1747 [ - + ]: 9431 : if (NISERR())
8249 tgl@sss.pgh.pa.us 1748 :UBC 0 : return 0;
3613 tgl@sss.pgh.pa.us 1749 :CBC 9431 : copyins(nfa, from, s); /* duplicate inarcs */
8069 bruce@momjian.us 1750 : 9431 : cparc(nfa, con, s, to); /* move constraint arc */
8249 tgl@sss.pgh.pa.us 1751 : 9431 : freearc(nfa, con);
3613 1752 [ - + ]: 9431 : if (NISERR())
3613 tgl@sss.pgh.pa.us 1753 :UBC 0 : return 0;
8249 tgl@sss.pgh.pa.us 1754 :CBC 9431 : from = s;
1755 : 9431 : con = from->outs;
1756 : : }
1757 [ - + ]: 15659 : assert(from->nouts == 1);
1758 : :
1759 : : /* propagate the constraint into the from state's inarcs */
3613 1760 [ + + + - ]: 158926 : for (a = from->ins; a != NULL && !NISERR(); a = nexta)
1761 : : {
8249 1762 : 143267 : nexta = a->inchain;
1659 1763 [ + + + + : 143267 : switch (combine(nfa, con, a))
- ]
1764 : : {
8069 bruce@momjian.us 1765 : 43782 : case INCOMPATIBLE: /* destroy the arc */
1766 : 43782 : freearc(nfa, a);
1767 : 43782 : break;
1768 : 8510 : case SATISFIED: /* no action needed */
1769 : 8510 : break;
1770 : 90167 : case COMPATIBLE: /* swap the two arcs, more or less */
1771 : : /* need an intermediate state, but might have one already */
3613 tgl@sss.pgh.pa.us 1772 [ + + ]: 101960 : for (s = *intermediates; s != NULL; s = s->tmp)
1773 : : {
1774 [ + - - + ]: 100730 : assert(s->nins > 0 && s->nouts > 0);
1775 [ + + + + ]: 100730 : if (s->ins->from == a->from && s->outs->to == to)
1776 : 88937 : break;
1777 : : }
1778 [ + + ]: 90167 : if (s == NULL)
1779 : : {
1780 : 1230 : s = newstate(nfa);
1781 [ - + ]: 1230 : if (NISERR())
3613 tgl@sss.pgh.pa.us 1782 :UBC 0 : return 0;
3613 tgl@sss.pgh.pa.us 1783 :CBC 1230 : s->tmp = *intermediates;
1784 : 1230 : *intermediates = s;
1785 : : }
8069 bruce@momjian.us 1786 : 90167 : cparc(nfa, con, a->from, s);
3613 tgl@sss.pgh.pa.us 1787 : 90167 : cparc(nfa, a, s, to);
8069 bruce@momjian.us 1788 : 90167 : freearc(nfa, a);
1789 : 90167 : break;
1659 tgl@sss.pgh.pa.us 1790 : 808 : case REPLACEARC: /* replace arc's color */
1791 : 808 : newarc(nfa, a->type, con->co, a->from, to);
1792 : 808 : freearc(nfa, a);
1793 : 808 : break;
8069 bruce@momjian.us 1794 :UBC 0 : default:
1795 : 0 : assert(NOTREACHED);
1796 : : break;
1797 : : }
1798 : : }
1799 : :
1800 : : /* remaining inarcs, if any, incorporate the constraint */
8249 tgl@sss.pgh.pa.us 1801 :CBC 15659 : moveins(nfa, from, to);
3613 1802 : 15659 : freearc(nfa, con);
1803 : : /* from state is now useless, but we leave it to pullback() to clean up */
8249 1804 : 15659 : return 1;
1805 : : }
1806 : :
1807 : : /*
1808 : : * pushfwd - push forward constraints forward to eliminate them
1809 : : */
1810 : : static void
2999 1811 : 9791 : pushfwd(struct nfa *nfa,
1812 : : FILE *f) /* for debug output; NULL none */
1813 : : {
1814 : : struct state *s;
1815 : : struct state *nexts;
1816 : : struct arc *a;
1817 : : struct arc *nexta;
1818 : : struct state *intermediates;
1819 : : int progress;
1820 : :
1821 : : /* find and push until there are no more */
1822 : : do
1823 : : {
8249 1824 : 14600 : progress = 0;
8069 bruce@momjian.us 1825 [ + + + + ]: 205763 : for (s = nfa->states; s != NULL && !NISERR(); s = nexts)
1826 : : {
8249 tgl@sss.pgh.pa.us 1827 : 191163 : nexts = s->next;
3613 1828 : 191163 : intermediates = NULL;
8069 bruce@momjian.us 1829 [ + + + - ]: 851001 : for (a = s->ins; a != NULL && !NISERR(); a = nexta)
1830 : : {
8249 tgl@sss.pgh.pa.us 1831 : 659838 : nexta = a->inchain;
1832 [ + + + + ]: 659838 : if (a->type == '$' || a->type == AHEAD)
3613 1833 [ + + ]: 36129 : if (push(nfa, a, &intermediates))
8249 1834 : 11101 : progress = 1;
1835 : : }
1836 : : /* clear tmp fields of intermediate states created here */
3613 1837 [ + + ]: 191165 : while (intermediates != NULL)
1838 : : {
1839 : 2 : struct state *ns = intermediates->tmp;
1840 : :
1841 : 2 : intermediates->tmp = NULL;
1842 : 2 : intermediates = ns;
1843 : : }
1844 : : /* if s is now useless, get rid of it */
1845 [ + + + + : 191163 : if ((s->nins == 0 || s->nouts == 0) && !s->flag)
+ + ]
1846 : 11381 : dropstate(nfa, s);
1847 : : }
8249 1848 [ + + - + ]: 14600 : if (progress && f != NULL)
8249 tgl@sss.pgh.pa.us 1849 :UBC 0 : dumpnfa(nfa, f);
8249 tgl@sss.pgh.pa.us 1850 [ + + + - ]:CBC 14600 : } while (progress && !NISERR());
1851 [ + + ]: 9791 : if (NISERR())
1852 : 3 : return;
1853 : :
1854 : : /*
1855 : : * Any $ constraints we were able to push to the post state can now be
1856 : : * replaced by PLAIN arcs referencing the EOS or EOL colors. There should
1857 : : * be no other $ or AHEAD arcs left in the NFA, though we do not check
1858 : : * that here (compact() will fail if so).
1859 : : */
8069 bruce@momjian.us 1860 [ + + ]: 30801 : for (a = nfa->post->ins; a != NULL; a = nexta)
1861 : : {
8249 tgl@sss.pgh.pa.us 1862 : 21013 : nexta = a->inchain;
8069 bruce@momjian.us 1863 [ + + ]: 21013 : if (a->type == '$')
1864 : : {
8249 tgl@sss.pgh.pa.us 1865 [ + + - + ]: 15022 : assert(a->co == 0 || a->co == 1);
1866 : 15022 : newarc(nfa, PLAIN, nfa->eos[a->co], a->from, a->to);
1867 : 15022 : freearc(nfa, a);
1868 : : }
1869 : : }
1870 : : }
1871 : :
1872 : : /*
1873 : : * push - push a forward constraint forward past its destination state
1874 : : *
1875 : : * Returns 1 if successful (which it always is unless the destination is the
1876 : : * post state or we have an internal error), 0 if nothing happened.
1877 : : *
1878 : : * A significant property of this function is that it deletes no pre-existing
1879 : : * states, and no inarcs of the constraint's to state other than the given
1880 : : * constraint arc. This makes the loops in pushfwd() safe, at the cost that
1881 : : * we may leave useless states behind. Therefore, we leave it to pushfwd()
1882 : : * to delete such states.
1883 : : *
1884 : : * If the to state has multiple forward-constraint inarcs, and/or multiple
1885 : : * compatible constraint outarcs, we only need to create one new intermediate
1886 : : * state per combination of predecessor and successor states. *intermediates
1887 : : * points to a list of such intermediate states for this to state (chained
1888 : : * through their tmp fields).
1889 : : */
1890 : : static int
2999 1891 : 36129 : push(struct nfa *nfa,
1892 : : struct arc *con,
1893 : : struct state **intermediates)
1894 : : {
8249 1895 : 36129 : struct state *from = con->from;
1896 : 36129 : struct state *to = con->to;
1897 : : struct arc *a;
1898 : : struct arc *nexta;
1899 : : struct state *s;
1900 : :
3613 1901 [ - + ]: 36129 : assert(to != from); /* should have gotten rid of this earlier */
8069 bruce@momjian.us 1902 [ + + ]: 36129 : if (to->flag) /* can't push forward beyond end */
8249 tgl@sss.pgh.pa.us 1903 : 25028 : return 0;
8069 bruce@momjian.us 1904 [ + + ]: 11101 : if (to->nouts == 0)
1905 : : { /* dead end */
8249 tgl@sss.pgh.pa.us 1906 : 410 : freearc(nfa, con);
1907 : 410 : return 1;
1908 : : }
1909 : :
1910 : : /*
1911 : : * First, clone to state if necessary to avoid other inarcs. This may
1912 : : * seem wasteful, but it simplifies the logic, and we'll get rid of the
1913 : : * clone state again at the bottom.
1914 : : */
8069 bruce@momjian.us 1915 [ + + ]: 10691 : if (to->nins > 1)
1916 : : {
8249 tgl@sss.pgh.pa.us 1917 : 5641 : s = newstate(nfa);
1918 [ - + ]: 5641 : if (NISERR())
8249 tgl@sss.pgh.pa.us 1919 :UBC 0 : return 0;
3613 tgl@sss.pgh.pa.us 1920 :CBC 5641 : copyouts(nfa, to, s); /* duplicate outarcs */
2999 1921 : 5641 : cparc(nfa, con, from, s); /* move constraint arc */
8249 1922 : 5641 : freearc(nfa, con);
3613 1923 [ - + ]: 5641 : if (NISERR())
3613 tgl@sss.pgh.pa.us 1924 :UBC 0 : return 0;
8249 tgl@sss.pgh.pa.us 1925 :CBC 5641 : to = s;
1926 : 5641 : con = to->ins;
1927 : : }
1928 [ - + ]: 10691 : assert(to->nins == 1);
1929 : :
1930 : : /* propagate the constraint into the to state's outarcs */
3613 1931 [ + + + - ]: 64938 : for (a = to->outs; a != NULL && !NISERR(); a = nexta)
1932 : : {
8249 1933 : 54247 : nexta = a->outchain;
1659 1934 [ + + + + : 54247 : switch (combine(nfa, con, a))
- ]
1935 : : {
8069 bruce@momjian.us 1936 : 45780 : case INCOMPATIBLE: /* destroy the arc */
1937 : 45780 : freearc(nfa, a);
1938 : 45780 : break;
1939 : 7224 : case SATISFIED: /* no action needed */
1940 : 7224 : break;
1941 : 8 : case COMPATIBLE: /* swap the two arcs, more or less */
1942 : : /* need an intermediate state, but might have one already */
3613 tgl@sss.pgh.pa.us 1943 [ + + ]: 8 : for (s = *intermediates; s != NULL; s = s->tmp)
1944 : : {
1945 [ + - - + ]: 6 : assert(s->nins > 0 && s->nouts > 0);
1946 [ + - + - ]: 6 : if (s->ins->from == from && s->outs->to == a->to)
1947 : 6 : break;
1948 : : }
1949 [ + + ]: 8 : if (s == NULL)
1950 : : {
1951 : 2 : s = newstate(nfa);
1952 [ - + ]: 2 : if (NISERR())
3613 tgl@sss.pgh.pa.us 1953 :UBC 0 : return 0;
3613 tgl@sss.pgh.pa.us 1954 :CBC 2 : s->tmp = *intermediates;
1955 : 2 : *intermediates = s;
1956 : : }
1957 : 8 : cparc(nfa, con, s, a->to);
8069 bruce@momjian.us 1958 : 8 : cparc(nfa, a, from, s);
1959 : 8 : freearc(nfa, a);
1960 : 8 : break;
1659 tgl@sss.pgh.pa.us 1961 : 1235 : case REPLACEARC: /* replace arc's color */
1962 : 1235 : newarc(nfa, a->type, con->co, from, a->to);
1963 : 1235 : freearc(nfa, a);
1964 : 1235 : break;
8069 bruce@momjian.us 1965 :UBC 0 : default:
1966 : 0 : assert(NOTREACHED);
1967 : : break;
1968 : : }
1969 : : }
1970 : :
1971 : : /* remaining outarcs, if any, incorporate the constraint */
8249 tgl@sss.pgh.pa.us 1972 :CBC 10691 : moveouts(nfa, to, from);
3613 1973 : 10691 : freearc(nfa, con);
1974 : : /* to state is now useless, but we leave it to pushfwd() to clean up */
8249 1975 : 10691 : return 1;
1976 : : }
1977 : :
1978 : : /*
1979 : : * combine - constraint lands on an arc, what happens?
1980 : : *
1981 : : * #def INCOMPATIBLE 1 // destroys arc
1982 : : * #def SATISFIED 2 // constraint satisfied
1983 : : * #def COMPATIBLE 3 // compatible but not satisfied yet
1984 : : * #def REPLACEARC 4 // replace arc's color with constraint color
1985 : : */
1986 : : static int
1659 1987 : 197514 : combine(struct nfa *nfa,
1988 : : struct arc *con,
1989 : : struct arc *a)
1990 : : {
1991 : : #define CA(ct,at) (((ct)<<CHAR_BIT) | (at))
1992 : :
8069 bruce@momjian.us 1993 [ + + + + : 197514 : switch (CA(con->type, a->type))
+ + - ]
1994 : : {
1995 : 44834 : case CA('^', PLAIN): /* newlines are handled separately */
1996 : : case CA('$', PLAIN):
1997 : 44834 : return INCOMPATIBLE;
1998 : : break;
1999 : 18494 : case CA(AHEAD, PLAIN): /* color constraints meet colors */
2000 : : case CA(BEHIND, PLAIN):
2001 [ + + ]: 18494 : if (con->co == a->co)
2002 : 827 : return SATISFIED;
1659 tgl@sss.pgh.pa.us 2003 [ + + ]: 17667 : if (con->co == RAINBOW)
2004 : : {
2005 : : /* con is satisfied unless arc's color is a pseudocolor */
2006 [ + - ]: 2 : if (!(nfa->cm->cd[a->co].flags & PSEUDO))
2007 : 2 : return SATISFIED;
2008 : : }
2009 [ + + ]: 17665 : else if (a->co == RAINBOW)
2010 : : {
2011 : : /* con is incompatible if it's for a pseudocolor */
2012 : : /* (this is hypothetical; we make no such constraints today) */
2013 [ - + ]: 2039 : if (nfa->cm->cd[con->co].flags & PSEUDO)
1659 tgl@sss.pgh.pa.us 2014 :UBC 0 : return INCOMPATIBLE;
2015 : : /* otherwise, constraint constrains arc to be only its color */
1659 tgl@sss.pgh.pa.us 2016 :CBC 2039 : return REPLACEARC;
2017 : : }
8069 bruce@momjian.us 2018 : 15626 : return INCOMPATIBLE;
2019 : : break;
2020 : 25483 : case CA('^', '^'): /* collision, similar constraints */
2021 : : case CA('$', '$'):
1659 tgl@sss.pgh.pa.us 2022 [ + + ]: 25483 : if (con->co == a->co) /* true duplication */
2023 : 14444 : return SATISFIED;
2024 : 11039 : return INCOMPATIBLE;
2025 : : break;
2026 : 12310 : case CA(AHEAD, AHEAD): /* collision, similar constraints */
2027 : : case CA(BEHIND, BEHIND):
2999 2028 [ + + ]: 12310 : if (con->co == a->co) /* true duplication */
8069 bruce@momjian.us 2029 : 459 : return SATISFIED;
1659 tgl@sss.pgh.pa.us 2030 [ + + ]: 11851 : if (con->co == RAINBOW)
2031 : : {
2032 : : /* con is satisfied unless arc's color is a pseudocolor */
2033 [ + - ]: 2 : if (!(nfa->cm->cd[a->co].flags & PSEUDO))
2034 : 2 : return SATISFIED;
2035 : : }
2036 [ + + ]: 11849 : else if (a->co == RAINBOW)
2037 : : {
2038 : : /* con is incompatible if it's for a pseudocolor */
2039 : : /* (this is hypothetical; we make no such constraints today) */
2040 [ - + ]: 4 : if (nfa->cm->cd[con->co].flags & PSEUDO)
1659 tgl@sss.pgh.pa.us 2041 :UBC 0 : return INCOMPATIBLE;
2042 : : /* otherwise, constraint constrains arc to be only its color */
1659 tgl@sss.pgh.pa.us 2043 :CBC 4 : return REPLACEARC;
2044 : : }
8069 bruce@momjian.us 2045 : 11845 : return INCOMPATIBLE;
2046 : : break;
2047 : 6218 : case CA('^', BEHIND): /* collision, dissimilar constraints */
2048 : : case CA(BEHIND, '^'):
2049 : : case CA('$', AHEAD):
2050 : : case CA(AHEAD, '$'):
2051 : 6218 : return INCOMPATIBLE;
2052 : : break;
2053 : 90175 : case CA('^', '$'): /* constraints passing each other */
2054 : : case CA('^', AHEAD):
2055 : : case CA(BEHIND, '$'):
2056 : : case CA(BEHIND, AHEAD):
2057 : : case CA('$', '^'):
2058 : : case CA('$', BEHIND):
2059 : : case CA(AHEAD, '^'):
2060 : : case CA(AHEAD, BEHIND):
2061 : : case CA('^', LACON):
2062 : : case CA(BEHIND, LACON):
2063 : : case CA('$', LACON):
2064 : : case CA(AHEAD, LACON):
2065 : 90175 : return COMPATIBLE;
2066 : : break;
2067 : : }
8249 tgl@sss.pgh.pa.us 2068 :UBC 0 : assert(NOTREACHED);
2069 : : return INCOMPATIBLE; /* for benefit of blind compilers */
2070 : : }
2071 : :
2072 : : /*
2073 : : * fixempties - get rid of EMPTY arcs
2074 : : */
2075 : : static void
2999 tgl@sss.pgh.pa.us 2076 :CBC 9791 : fixempties(struct nfa *nfa,
2077 : : FILE *f) /* for debug output; NULL none */
2078 : : {
2079 : : struct state *s;
2080 : : struct state *s2;
2081 : : struct state *nexts;
2082 : : struct arc *a;
2083 : : struct arc *nexta;
2084 : : int totalinarcs;
2085 : : struct arc **inarcsorig;
2086 : : struct arc **arcarray;
2087 : : int arccount;
2088 : : int prevnins;
2089 : : int nskip;
2090 : :
2091 : : /*
2092 : : * First, get rid of any states whose sole out-arc is an EMPTY, since
2093 : : * they're basically just aliases for their successor. The parsing
2094 : : * algorithm creates enough of these that it's worth special-casing this.
2095 : : */
4566 2096 [ + + + - ]: 225942 : for (s = nfa->states; s != NULL && !NISERR(); s = nexts)
2097 : : {
2098 : 216151 : nexts = s->next;
2099 [ + + + + ]: 216151 : if (s->flag || s->nouts != 1)
2100 : 55704 : continue;
2101 : 160447 : a = s->outs;
2102 [ + - - + ]: 160447 : assert(a != NULL && a->outchain == NULL);
2103 [ + + ]: 160447 : if (a->type != EMPTY)
2104 : 98426 : continue;
2105 [ + - ]: 62021 : if (s != a->to)
2106 : 62021 : moveins(nfa, s, a->to);
2107 : 62021 : dropstate(nfa, s);
2108 : : }
2109 : :
2110 : : /*
2111 : : * Similarly, get rid of any state with a single EMPTY in-arc, by folding
2112 : : * it into its predecessor.
2113 : : */
2114 [ + + + - ]: 163921 : for (s = nfa->states; s != NULL && !NISERR(); s = nexts)
2115 : : {
2116 : 154130 : nexts = s->next;
2117 : : /* while we're at it, ensure tmp fields are clear for next step */
2118 [ - + ]: 154130 : assert(s->tmp == NULL);
2119 [ + + + + ]: 154130 : if (s->flag || s->nins != 1)
2120 : 52862 : continue;
2121 : 101268 : a = s->ins;
2122 [ + - - + ]: 101268 : assert(a != NULL && a->inchain == NULL);
2123 [ + + ]: 101268 : if (a->type != EMPTY)
2124 : 89541 : continue;
2125 [ + - ]: 11727 : if (s != a->from)
2126 : 11727 : moveouts(nfa, s, a->from);
2127 : 11727 : dropstate(nfa, s);
2128 : : }
2129 : :
3613 2130 [ - + ]: 9791 : if (NISERR())
3613 tgl@sss.pgh.pa.us 2131 :UBC 0 : return;
2132 : :
2133 : : /*
2134 : : * For each remaining NFA state, find all other states from which it is
2135 : : * reachable by a chain of one or more EMPTY arcs. Then generate new arcs
2136 : : * that eliminate the need for each such chain.
2137 : : *
2138 : : * We could replace a chain of EMPTY arcs that leads from a "from" state
2139 : : * to a "to" state either by pushing non-EMPTY arcs forward (linking
2140 : : * directly from "from"'s predecessors to "to") or by pulling them back
2141 : : * (linking directly from "from" to "to"'s successors). We choose to
2142 : : * always do the former; this choice is somewhat arbitrary, but the
2143 : : * approach below requires that we uniformly do one or the other.
2144 : : *
2145 : : * Suppose we have a chain of N successive EMPTY arcs (where N can easily
2146 : : * approach the size of the NFA). All of the intermediate states must
2147 : : * have additional inarcs and outarcs, else they'd have been removed by
2148 : : * the steps above. Assuming their inarcs are mostly not empties, we will
2149 : : * add O(N^2) arcs to the NFA, since a non-EMPTY inarc leading to any one
2150 : : * state in the chain must be duplicated to lead to all its successor
2151 : : * states as well. So there is no hope of doing less than O(N^2) work;
2152 : : * however, we should endeavor to keep the big-O cost from being even
2153 : : * worse than that, which it can easily become without care. In
2154 : : * particular, suppose we were to copy all S1's inarcs forward to S2, and
2155 : : * then also to S3, and then later we consider pushing S2's inarcs forward
2156 : : * to S3. If we include the arcs already copied from S1 in that, we'd be
2157 : : * doing O(N^3) work. (The duplicate-arc elimination built into newarc()
2158 : : * and its cohorts would get rid of the extra arcs, but not without cost.)
2159 : : *
2160 : : * We can avoid this cost by treating only arcs that existed at the start
2161 : : * of this phase as candidates to be pushed forward. To identify those,
2162 : : * we remember the first inarc each state had to start with. We rely on
2163 : : * the fact that newarc() and friends put new arcs on the front of their
2164 : : * to-states' inchains, and that this phase never deletes arcs, so that
2165 : : * the original arcs must be the last arcs in their to-states' inchains.
2166 : : *
2167 : : * So the process here is that, for each state in the NFA, we gather up
2168 : : * all non-EMPTY inarcs of states that can reach the target state via
2169 : : * EMPTY arcs. We then sort, de-duplicate, and merge these arcs into the
2170 : : * target state's inchain. (We can safely use sort-merge for this as long
2171 : : * as we update each state's original-arcs pointer after we add arcs to
2172 : : * it; the sort step of mergeins probably changed the order of the old
2173 : : * arcs.)
2174 : : *
2175 : : * Another refinement worth making is that, because we only add non-EMPTY
2176 : : * arcs during this phase, and all added arcs have the same from-state as
2177 : : * the non-EMPTY arc they were cloned from, we know ahead of time that any
2178 : : * states having only EMPTY outarcs will be useless for lack of outarcs
2179 : : * after we drop the EMPTY arcs. (They cannot gain non-EMPTY outarcs if
2180 : : * they had none to start with.) So we need not bother to update the
2181 : : * inchains of such states at all.
2182 : : */
2183 : :
2184 : : /* Remember the states' first original inarcs */
2185 : : /* ... and while at it, count how many old inarcs there are altogether */
3613 tgl@sss.pgh.pa.us 2186 :CBC 9791 : inarcsorig = (struct arc **) MALLOC(nfa->nstates * sizeof(struct arc *));
2187 [ - + ]: 9791 : if (inarcsorig == NULL)
2188 : : {
3613 tgl@sss.pgh.pa.us 2189 [ # # ]:UBC 0 : NERR(REG_ESPACE);
2190 : 0 : return;
2191 : : }
3613 tgl@sss.pgh.pa.us 2192 :CBC 9791 : totalinarcs = 0;
2193 [ + + ]: 152194 : for (s = nfa->states; s != NULL; s = s->next)
2194 : : {
2195 : 142403 : inarcsorig[s->no] = s->ins;
2196 : 142403 : totalinarcs += s->nins;
2197 : : }
2198 : :
2199 : : /*
2200 : : * Create a workspace for accumulating the inarcs to be added to the
2201 : : * current target state. totalinarcs is probably a considerable
2202 : : * overestimate of the space needed, but the NFA is unlikely to be large
2203 : : * enough at this point to make it worth being smarter.
2204 : : */
2205 : 9791 : arcarray = (struct arc **) MALLOC(totalinarcs * sizeof(struct arc *));
2206 [ - + ]: 9791 : if (arcarray == NULL)
2207 : : {
3613 tgl@sss.pgh.pa.us 2208 [ # # ]:UBC 0 : NERR(REG_ESPACE);
2209 : 0 : FREE(inarcsorig);
2210 : 0 : return;
2211 : : }
2212 : :
2213 : : /* And iterate over the target states */
4566 tgl@sss.pgh.pa.us 2214 [ + + + + ]:CBC 149713 : for (s = nfa->states; s != NULL && !NISERR(); s = s->next)
2215 : : {
2216 : : /* Ignore target states without non-EMPTY outarcs, per note above */
3613 2217 [ + + + + ]: 139922 : if (!s->flag && !hasnonemptyout(s))
2218 : 1980 : continue;
2219 : :
2220 : : /* Find predecessor states and accumulate their original inarcs */
2221 : 137942 : arccount = 0;
2222 [ + + ]: 7631499 : for (s2 = emptyreachable(nfa, s, s, inarcsorig); s2 != s; s2 = nexts)
2223 : : {
2224 : : /* Add s2's original inarcs to arcarray[], but ignore empties */
2225 [ + + ]: 22501509 : for (a = inarcsorig[s2->no]; a != NULL; a = a->inchain)
2226 : : {
2227 [ + + ]: 15007952 : if (a->type != EMPTY)
2228 : 7515445 : arcarray[arccount++] = a;
2229 : : }
2230 : :
2231 : : /* Reset the tmp fields as we walk back */
4566 2232 : 7493557 : nexts = s2->tmp;
2233 : 7493557 : s2->tmp = NULL;
2234 : : }
2235 : 137942 : s->tmp = NULL;
3613 2236 [ - + ]: 137942 : assert(arccount <= totalinarcs);
2237 : :
2238 : : /* Remember how many original inarcs this state has */
2239 : 137942 : prevnins = s->nins;
2240 : :
2241 : : /* Add non-duplicate inarcs to target state */
2242 : 137942 : mergeins(nfa, s, arcarray, arccount);
2243 : :
2244 : : /* Now we must update the state's inarcsorig pointer */
2245 : 137942 : nskip = s->nins - prevnins;
2246 : 137942 : a = s->ins;
2247 [ + + ]: 7647062 : while (nskip-- > 0)
2248 : 7509120 : a = a->inchain;
2249 : 137942 : inarcsorig[s->no] = a;
2250 : : }
2251 : :
2252 : 9791 : FREE(arcarray);
2253 : 9791 : FREE(inarcsorig);
2254 : :
4566 2255 [ + + ]: 9791 : if (NISERR())
2256 : 3 : return;
2257 : :
2258 : : /*
2259 : : * Now remove all the EMPTY arcs, since we don't need them anymore.
2260 : : */
2261 [ + + ]: 143185 : for (s = nfa->states; s != NULL; s = s->next)
2262 : : {
2263 [ + + ]: 761321 : for (a = s->outs; a != NULL; a = nexta)
2264 : : {
2265 : 627924 : nexta = a->outchain;
2266 [ + + ]: 627924 : if (a->type == EMPTY)
2267 : 12741 : freearc(nfa, a);
2268 : : }
2269 : : }
2270 : :
2271 : : /*
2272 : : * And remove any states that have become useless. (This cleanup is not
2273 : : * very thorough, and would be even less so if we tried to combine it with
2274 : : * the previous step; but cleanup() will take care of anything we miss.)
2275 : : */
2276 [ + + ]: 143185 : for (s = nfa->states; s != NULL; s = nexts)
2277 : : {
2278 : 133397 : nexts = s->next;
2279 [ + + + + : 133397 : if ((s->nins == 0 || s->nouts == 0) && !s->flag)
+ + ]
2280 : 1980 : dropstate(nfa, s);
2281 : : }
2282 : :
2283 [ - + ]: 9788 : if (f != NULL)
4566 tgl@sss.pgh.pa.us 2284 :UBC 0 : dumpnfa(nfa, f);
2285 : : }
2286 : :
2287 : : /*
2288 : : * emptyreachable - recursively find all states that can reach s by EMPTY arcs
2289 : : *
2290 : : * The return value is the last such state found. Its tmp field links back
2291 : : * to the next-to-last such state, and so on back to s, so that all these
2292 : : * states can be located without searching the whole NFA.
2293 : : *
2294 : : * Since this is only used in fixempties(), we pass in the inarcsorig[] array
2295 : : * maintained by that function. This lets us skip over all new inarcs, which
2296 : : * are certainly not EMPTY arcs.
2297 : : *
2298 : : * The maximum recursion depth here is equal to the length of the longest
2299 : : * loop-free chain of EMPTY arcs, which is surely no more than the size of
2300 : : * the NFA ... but that could still be enough to cause trouble.
2301 : : */
2302 : : static struct state *
2999 tgl@sss.pgh.pa.us 2303 :CBC 7631499 : emptyreachable(struct nfa *nfa,
2304 : : struct state *s,
2305 : : struct state *lastfound,
2306 : : struct arc **inarcsorig)
2307 : : {
2308 : : struct arc *a;
2309 : :
2310 : : /* Since this is recursive, it could be driven to stack overflow */
3627 2311 [ - + ]: 7631499 : if (STACK_TOO_DEEP(nfa->v->re))
2312 : : {
3627 tgl@sss.pgh.pa.us 2313 [ # # ]:UBC 0 : NERR(REG_ETOOBIG);
2314 : 0 : return lastfound;
2315 : : }
2316 : :
4566 tgl@sss.pgh.pa.us 2317 :CBC 7631499 : s->tmp = lastfound;
2318 : 7631499 : lastfound = s;
3613 2319 [ + + ]: 22860749 : for (a = inarcsorig[s->no]; a != NULL; a = a->inchain)
2320 : : {
2321 [ + + + + ]: 15229250 : if (a->type == EMPTY && a->from->tmp == NULL)
2322 : 7493557 : lastfound = emptyreachable(nfa, a->from, lastfound, inarcsorig);
2323 : : }
4566 2324 : 7631499 : return lastfound;
2325 : : }
2326 : :
2327 : : /*
2328 : : * isconstraintarc - detect whether an arc is of a constraint type
2329 : : */
2330 : : static inline int
2999 2331 : 1296571 : isconstraintarc(struct arc *a)
2332 : : {
3613 2333 [ + + ]: 1296571 : switch (a->type)
2334 : : {
2335 : 165011 : case '^':
2336 : : case '$':
2337 : : case BEHIND:
2338 : : case AHEAD:
2339 : : case LACON:
2340 : 165011 : return 1;
2341 : : }
2342 : 1131560 : return 0;
2343 : : }
2344 : :
2345 : : /*
2346 : : * hasconstraintout - does state have a constraint out arc?
2347 : : */
2348 : : static int
2999 2349 : 12631 : hasconstraintout(struct state *s)
2350 : : {
2351 : : struct arc *a;
2352 : :
3613 2353 [ + + ]: 23960 : for (a = s->outs; a != NULL; a = a->outchain)
2354 : : {
2355 [ + + ]: 19222 : if (isconstraintarc(a))
2356 : 7893 : return 1;
2357 : : }
2358 : 4738 : return 0;
2359 : : }
2360 : :
2361 : : /*
2362 : : * fixconstraintloops - get rid of loops containing only constraint arcs
2363 : : *
2364 : : * A loop of states that contains only constraint arcs is useless, since
2365 : : * passing around the loop represents no forward progress. Moreover, it
2366 : : * would cause infinite looping in pullback/pushfwd, so we need to get rid
2367 : : * of such loops before doing that.
2368 : : */
2369 : : static void
2999 2370 : 9791 : fixconstraintloops(struct nfa *nfa,
2371 : : FILE *f) /* for debug output; NULL none */
2372 : : {
2373 : : struct state *s;
2374 : : struct state *nexts;
2375 : : struct arc *a;
2376 : : struct arc *nexta;
2377 : : int hasconstraints;
2378 : :
2379 : : /*
2380 : : * In the trivial case of a state that loops to itself, we can just drop
2381 : : * the constraint arc altogether. This is worth special-casing because
2382 : : * such loops are far more common than loops containing multiple states.
2383 : : * While we're at it, note whether any constraint arcs survive.
2384 : : */
3613 2385 : 9791 : hasconstraints = 0;
2386 [ + + + + ]: 141208 : for (s = nfa->states; s != NULL && !NISERR(); s = nexts)
2387 : : {
2388 : 131417 : nexts = s->next;
2389 : : /* while we're at it, ensure tmp fields are clear for next step */
2390 [ - + ]: 131417 : assert(s->tmp == NULL);
2391 [ + + + - ]: 744621 : for (a = s->outs; a != NULL && !NISERR(); a = nexta)
2392 : : {
2393 : 613204 : nexta = a->outchain;
2394 [ + + ]: 613204 : if (isconstraintarc(a))
2395 : : {
2396 [ + + ]: 61407 : if (a->to == s)
2397 : 176 : freearc(nfa, a);
2398 : : else
2399 : 61231 : hasconstraints = 1;
2400 : : }
2401 : : }
2402 : : /* If we removed all the outarcs, the state is useless. */
2403 [ + + - + ]: 131417 : if (s->nouts == 0 && !s->flag)
3613 tgl@sss.pgh.pa.us 2404 :UBC 0 : dropstate(nfa, s);
2405 : : }
2406 : :
2407 : : /* Nothing to do if no remaining constraint arcs */
3613 tgl@sss.pgh.pa.us 2408 [ + + + + ]:CBC 9791 : if (NISERR() || !hasconstraints)
2409 : 5 : return;
2410 : :
2411 : : /*
2412 : : * Starting from each remaining NFA state, search outwards for a
2413 : : * constraint loop. If we find a loop, break the loop, then start the
2414 : : * search over. (We could possibly retain some state from the first scan,
2415 : : * but it would complicate things greatly, and multi-state constraint
2416 : : * loops are rare enough that it's not worth optimizing the case.)
2417 : : */
2418 : 9786 : restart:
2419 [ + + + - ]: 148666 : for (s = nfa->states; s != NULL && !NISERR(); s = s->next)
2420 : : {
2421 [ + + ]: 138880 : if (findconstraintloop(nfa, s))
2422 : 206 : goto restart;
2423 : : }
2424 : :
2425 [ - + ]: 9786 : if (NISERR())
3613 tgl@sss.pgh.pa.us 2426 :UBC 0 : return;
2427 : :
2428 : : /*
2429 : : * Now remove any states that have become useless. (This cleanup is not
2430 : : * very thorough, and would be even less so if we tried to combine it with
2431 : : * the previous step; but cleanup() will take care of anything we miss.)
2432 : : *
2433 : : * Because findconstraintloop intentionally doesn't reset all tmp fields,
2434 : : * we have to clear them after it's done. This is a convenient place to
2435 : : * do that, too.
2436 : : */
3613 tgl@sss.pgh.pa.us 2437 [ + + ]:CBC 142060 : for (s = nfa->states; s != NULL; s = nexts)
2438 : : {
2439 : 132274 : nexts = s->next;
2440 : 132274 : s->tmp = NULL;
2441 [ + + + + : 132274 : if ((s->nins == 0 || s->nouts == 0) && !s->flag)
+ + ]
2442 : 213 : dropstate(nfa, s);
2443 : : }
2444 : :
2445 [ - + ]: 9786 : if (f != NULL)
3613 tgl@sss.pgh.pa.us 2446 :UBC 0 : dumpnfa(nfa, f);
2447 : : }
2448 : :
2449 : : /*
2450 : : * findconstraintloop - recursively find a loop of constraint arcs
2451 : : *
2452 : : * If we find a loop, break it by calling breakconstraintloop(), then
2453 : : * return 1; otherwise return 0.
2454 : : *
2455 : : * State tmp fields are guaranteed all NULL on a success return, because
2456 : : * breakconstraintloop does that. After a failure return, any state that
2457 : : * is known not to be part of a loop is marked with s->tmp == s; this allows
2458 : : * us not to have to re-prove that fact on later calls. (This convention is
2459 : : * workable because we already eliminated single-state loops.)
2460 : : *
2461 : : * Note that the found loop doesn't necessarily include the first state we
2462 : : * are called on. Any loop reachable from that state will do.
2463 : : *
2464 : : * The maximum recursion depth here is one more than the length of the longest
2465 : : * loop-free chain of constraint arcs, which is surely no more than the size
2466 : : * of the NFA ... but that could still be enough to cause trouble.
2467 : : */
2468 : : static int
2999 tgl@sss.pgh.pa.us 2469 :CBC 220175 : findconstraintloop(struct nfa *nfa, struct state *s)
2470 : : {
2471 : : struct arc *a;
2472 : :
2473 : : /* Since this is recursive, it could be driven to stack overflow */
3613 2474 [ - + ]: 220175 : if (STACK_TOO_DEEP(nfa->v->re))
2475 : : {
3613 tgl@sss.pgh.pa.us 2476 [ # # ]:UBC 0 : NERR(REG_ETOOBIG);
2477 : 0 : return 1; /* to exit as quickly as possible */
2478 : : }
2479 : :
3613 tgl@sss.pgh.pa.us 2480 [ + + ]:CBC 220175 : if (s->tmp != NULL)
2481 : : {
2482 : : /* Already proven uninteresting? */
2483 [ + + ]: 78925 : if (s->tmp == s)
2484 : 78719 : return 0;
2485 : : /* Found a loop involving s */
2486 : 206 : breakconstraintloop(nfa, s);
2487 : : /* The tmp fields have been cleaned up by breakconstraintloop */
2488 : 206 : return 1;
2489 : : }
2490 [ + + ]: 789799 : for (a = s->outs; a != NULL; a = a->outchain)
2491 : : {
2492 [ + + ]: 649208 : if (isconstraintarc(a))
2493 : : {
2494 : 81295 : struct state *sto = a->to;
2495 : :
2496 [ - + ]: 81295 : assert(sto != s);
2497 : 81295 : s->tmp = sto;
2498 [ + + ]: 81295 : if (findconstraintloop(nfa, sto))
2499 : 659 : return 1;
2500 : : }
2501 : : }
2502 : :
2503 : : /*
2504 : : * If we get here, no constraint loop exists leading out from s. Mark it
2505 : : * with s->tmp == s so we need not rediscover that fact again later.
2506 : : */
2507 : 140591 : s->tmp = s;
2508 : 140591 : return 0;
2509 : : }
2510 : :
2511 : : /*
2512 : : * breakconstraintloop - break a loop of constraint arcs
2513 : : *
2514 : : * sinitial is any one member state of the loop. Each loop member's tmp
2515 : : * field links to its successor within the loop. (Note that this function
2516 : : * will reset all the tmp fields to NULL.)
2517 : : *
2518 : : * We can break the loop by, for any one state S1 in the loop, cloning its
2519 : : * loop successor state S2 (and possibly following states), and then moving
2520 : : * all S1->S2 constraint arcs to point to the cloned S2. The cloned S2 should
2521 : : * copy any non-constraint outarcs of S2. Constraint outarcs should be
2522 : : * dropped if they point back to S1, else they need to be copied as arcs to
2523 : : * similarly cloned states S3, S4, etc. In general, each cloned state copies
2524 : : * non-constraint outarcs, drops constraint outarcs that would lead to itself
2525 : : * or any earlier cloned state, and sends other constraint outarcs to newly
2526 : : * cloned states. No cloned state will have any inarcs that aren't constraint
2527 : : * arcs or do not lead from S1 or earlier-cloned states. It's okay to drop
2528 : : * constraint back-arcs since they would not take us to any state we've not
2529 : : * already been in; therefore, no new constraint loop is created. In this way
2530 : : * we generate a modified NFA that can still represent every useful state
2531 : : * sequence, but not sequences that represent state loops with no consumption
2532 : : * of input data. Note that the set of cloned states will certainly include
2533 : : * all of the loop member states other than S1, and it may also include
2534 : : * non-loop states that are reachable from S2 via constraint arcs. This is
2535 : : * important because there is no guarantee that findconstraintloop found a
2536 : : * maximal loop (and searching for one would be NP-hard, so don't try).
2537 : : * Frequently the "non-loop states" are actually part of a larger loop that
2538 : : * we didn't notice, and indeed there may be several overlapping loops.
2539 : : * This technique ensures convergence in such cases, while considering only
2540 : : * the originally-found loop does not.
2541 : : *
2542 : : * If there is only one S1->S2 constraint arc, then that constraint is
2543 : : * certainly satisfied when we enter any of the clone states. This means that
2544 : : * in the common case where many of the constraint arcs are identically
2545 : : * labeled, we can merge together clone states linked by a similarly-labeled
2546 : : * constraint: if we can get to the first one we can certainly get to the
2547 : : * second, so there's no need to distinguish. This greatly reduces the number
2548 : : * of new states needed, so we preferentially break the given loop at a state
2549 : : * pair where this is true.
2550 : : *
2551 : : * Furthermore, it's fairly common to find that a cloned successor state has
2552 : : * no outarcs, especially if we're a bit aggressive about removing unnecessary
2553 : : * outarcs. If that happens, then there is simply not any interesting state
2554 : : * that can be reached through the predecessor's loop arcs, which means we can
2555 : : * break the loop just by removing those loop arcs, with no new states added.
2556 : : */
2557 : : static void
2999 2558 : 206 : breakconstraintloop(struct nfa *nfa, struct state *sinitial)
2559 : : {
2560 : : struct state *s;
2561 : : struct state *shead;
2562 : : struct state *stail;
2563 : : struct state *sclone;
2564 : : struct state *nexts;
2565 : : struct arc *refarc;
2566 : : struct arc *a;
2567 : : struct arc *nexta;
2568 : :
2569 : : /*
2570 : : * Start by identifying which loop step we want to break at.
2571 : : * Preferentially this is one with only one constraint arc. (XXX are
2572 : : * there any other secondary heuristics we want to use here?) Set refarc
2573 : : * to point to the selected lone constraint arc, if there is one.
2574 : : */
3613 2575 : 206 : refarc = NULL;
2576 : 206 : s = sinitial;
2577 : : do
2578 : : {
2579 : 530 : nexts = s->tmp;
2580 [ - + ]: 530 : assert(nexts != s); /* should not see any one-element loops */
2581 [ + + ]: 530 : if (refarc == NULL)
2582 : : {
2583 : 332 : int narcs = 0;
2584 : :
2585 [ + + ]: 3800 : for (a = s->outs; a != NULL; a = a->outchain)
2586 : : {
2587 [ + + + - ]: 3468 : if (a->to == nexts && isconstraintarc(a))
2588 : : {
2589 : 1296 : refarc = a;
2590 : 1296 : narcs++;
2591 : : }
2592 : : }
2593 [ - + ]: 332 : assert(narcs > 0);
2594 [ + + ]: 332 : if (narcs > 1)
2595 : 186 : refarc = NULL; /* multiple constraint arcs here, no good */
2596 : : }
2597 : 530 : s = nexts;
2598 [ + + ]: 530 : } while (s != sinitial);
2599 : :
2600 [ + + ]: 206 : if (refarc)
2601 : : {
2602 : : /* break at the refarc */
2603 : 146 : shead = refarc->from;
2604 : 146 : stail = refarc->to;
2605 [ - + ]: 146 : assert(stail == shead->tmp);
2606 : : }
2607 : : else
2608 : : {
2609 : : /* for lack of a better idea, break after sinitial */
2610 : 60 : shead = sinitial;
2611 : 60 : stail = sinitial->tmp;
2612 : : }
2613 : :
2614 : : /*
2615 : : * Reset the tmp fields so that we can use them for local storage in
2616 : : * clonesuccessorstates. (findconstraintloop won't mind, since it's just
2617 : : * going to abandon its search anyway.)
2618 : : */
2619 [ + + ]: 17361 : for (s = nfa->states; s != NULL; s = s->next)
2620 : 17155 : s->tmp = NULL;
2621 : :
2622 : : /*
2623 : : * Recursively build clone state(s) as needed.
2624 : : */
2625 : 206 : sclone = newstate(nfa);
2626 [ - + ]: 206 : if (sclone == NULL)
2627 : : {
3613 tgl@sss.pgh.pa.us 2628 [ # # ]:UBC 0 : assert(NISERR());
2629 : 0 : return;
2630 : : }
2631 : :
3613 tgl@sss.pgh.pa.us 2632 :CBC 206 : clonesuccessorstates(nfa, stail, sclone, shead, refarc,
2633 : : NULL, NULL, nfa->nstates);
2634 : :
2635 [ - + ]: 206 : if (NISERR())
3613 tgl@sss.pgh.pa.us 2636 :UBC 0 : return;
2637 : :
2638 : : /*
2639 : : * It's possible that sclone has no outarcs at all, in which case it's
2640 : : * useless. (We don't try extremely hard to get rid of useless states
2641 : : * here, but this is an easy and fairly common case.)
2642 : : */
3613 tgl@sss.pgh.pa.us 2643 [ + + ]:CBC 206 : if (sclone->nouts == 0)
2644 : : {
2645 : 49 : freestate(nfa, sclone);
2646 : 49 : sclone = NULL;
2647 : : }
2648 : :
2649 : : /*
2650 : : * Move shead's constraint-loop arcs to point to sclone, or just drop them
2651 : : * if we discovered we don't need sclone.
2652 : : */
2653 [ + + ]: 2256 : for (a = shead->outs; a != NULL; a = nexta)
2654 : : {
2655 : 2050 : nexta = a->outchain;
2656 [ + + + - ]: 2050 : if (a->to == stail && isconstraintarc(a))
2657 : : {
2658 [ + + ]: 489 : if (sclone)
2659 : 412 : cparc(nfa, a, shead, sclone);
2660 : 489 : freearc(nfa, a);
2661 [ - + ]: 489 : if (NISERR())
3613 tgl@sss.pgh.pa.us 2662 :UBC 0 : break;
2663 : : }
2664 : : }
2665 : : }
2666 : :
2667 : : /*
2668 : : * clonesuccessorstates - create a tree of constraint-arc successor states
2669 : : *
2670 : : * ssource is the state to be cloned, and sclone is the state to copy its
2671 : : * outarcs into. sclone's inarcs, if any, should already be set up.
2672 : : *
2673 : : * spredecessor is the original predecessor state that we are trying to build
2674 : : * successors for (it may not be the immediate predecessor of ssource).
2675 : : * refarc, if not NULL, is the original constraint arc that is known to have
2676 : : * been traversed out of spredecessor to reach the successor(s).
2677 : : *
2678 : : * For each cloned successor state, we transiently create a "donemap" that is
2679 : : * a boolean array showing which source states we've already visited for this
2680 : : * clone state. This prevents infinite recursion as well as useless repeat
2681 : : * visits to the same state subtree (which can add up fast, since typical NFAs
2682 : : * have multiple redundant arc pathways). Each donemap is a char array
2683 : : * indexed by state number. The donemaps are all of the same size "nstates",
2684 : : * which is nfa->nstates as of the start of the recursion. This is enough to
2685 : : * have entries for all pre-existing states, but *not* entries for clone
2686 : : * states created during the recursion. That's okay since we have no need to
2687 : : * mark those.
2688 : : *
2689 : : * curdonemap is NULL when recursing to a new sclone state, or sclone's
2690 : : * donemap when we are recursing without having created a new state (which we
2691 : : * do when we decide we can merge a successor state into the current clone
2692 : : * state). outerdonemap is NULL at the top level and otherwise the parent
2693 : : * clone state's donemap.
2694 : : *
2695 : : * The successor states we create and fill here form a strict tree structure,
2696 : : * with each state having exactly one predecessor, except that the toplevel
2697 : : * state has no inarcs as yet (breakconstraintloop will add its inarcs from
2698 : : * spredecessor after we're done). Thus, we can examine sclone's inarcs back
2699 : : * to the root, plus refarc if any, to identify the set of constraints already
2700 : : * known valid at the current point. This allows us to avoid generating extra
2701 : : * successor states.
2702 : : */
2703 : : static void
2999 tgl@sss.pgh.pa.us 2704 :CBC 1811 : clonesuccessorstates(struct nfa *nfa,
2705 : : struct state *ssource,
2706 : : struct state *sclone,
2707 : : struct state *spredecessor,
2708 : : struct arc *refarc,
2709 : : char *curdonemap,
2710 : : char *outerdonemap,
2711 : : int nstates)
2712 : : {
2713 : : char *donemap;
2714 : : struct arc *a;
2715 : :
2716 : : /* Since this is recursive, it could be driven to stack overflow */
3613 2717 [ - + ]: 1811 : if (STACK_TOO_DEEP(nfa->v->re))
2718 : : {
3613 tgl@sss.pgh.pa.us 2719 [ # # ]:UBC 0 : NERR(REG_ETOOBIG);
2720 : 0 : return;
2721 : : }
2722 : :
2723 : : /* If this state hasn't already got a donemap, create one */
3613 tgl@sss.pgh.pa.us 2724 :CBC 1811 : donemap = curdonemap;
2725 [ + + ]: 1811 : if (donemap == NULL)
2726 : : {
2727 : 910 : donemap = (char *) MALLOC(nstates * sizeof(char));
2728 [ - + ]: 910 : if (donemap == NULL)
2729 : : {
3613 tgl@sss.pgh.pa.us 2730 [ # # ]:UBC 0 : NERR(REG_ESPACE);
2731 : 0 : return;
2732 : : }
2733 : :
3613 tgl@sss.pgh.pa.us 2734 [ + + ]:CBC 910 : if (outerdonemap != NULL)
2735 : : {
2736 : : /*
2737 : : * Not at outermost recursion level, so copy the outer level's
2738 : : * donemap; this ensures that we see states in process of being
2739 : : * visited at outer levels, or already merged into predecessor
2740 : : * states, as ones we shouldn't traverse back to.
2741 : : */
2742 : 704 : memcpy(donemap, outerdonemap, nstates * sizeof(char));
2743 : : }
2744 : : else
2745 : : {
2746 : : /* At outermost level, only spredecessor is off-limits */
2747 : 206 : memset(donemap, 0, nstates * sizeof(char));
2748 [ - + ]: 206 : assert(spredecessor->no < nstates);
2749 : 206 : donemap[spredecessor->no] = 1;
2750 : : }
2751 : : }
2752 : :
2753 : : /* Mark ssource as visited in the donemap */
2754 [ - + ]: 1811 : assert(ssource->no < nstates);
2755 [ - + ]: 1811 : assert(donemap[ssource->no] == 0);
2756 : 1811 : donemap[ssource->no] = 1;
2757 : :
2758 : : /*
2759 : : * We proceed by first cloning all of ssource's outarcs, creating new
2760 : : * clone states as needed but not doing more with them than that. Then in
2761 : : * a second pass, recurse to process the child clone states. This allows
2762 : : * us to have only one child clone state per reachable source state, even
2763 : : * when there are multiple outarcs leading to the same state. Also, when
2764 : : * we do visit a child state, its set of inarcs is known exactly, which
2765 : : * makes it safe to apply the constraint-is-already-checked optimization.
2766 : : * Also, this ensures that we've merged all the states we can into the
2767 : : * current clone before we recurse to any children, thus possibly saving
2768 : : * them from making extra images of those states.
2769 : : *
2770 : : * While this function runs, child clone states of the current state are
2771 : : * marked by setting their tmp fields to point to the original state they
2772 : : * were cloned from. This makes it possible to detect multiple outarcs
2773 : : * leading to the same state, and also makes it easy to distinguish clone
2774 : : * states from original states (which will have tmp == NULL).
2775 : : */
2776 [ + + + - ]: 14963 : for (a = ssource->outs; a != NULL && !NISERR(); a = a->outchain)
2777 : : {
2778 : 13152 : struct state *sto = a->to;
2779 : :
2780 : : /*
2781 : : * We do not consider cloning successor states that have no constraint
2782 : : * outarcs; just link to them as-is. They cannot be part of a
2783 : : * constraint loop so there is no need to make copies. In particular,
2784 : : * this rule keeps us from trying to clone the post state, which would
2785 : : * be a bad idea.
2786 : : */
2787 [ + + + + ]: 13152 : if (isconstraintarc(a) && hasconstraintout(sto))
2788 : 5485 : {
2789 : : struct state *prevclone;
2790 : : int canmerge;
2791 : : struct arc *a2;
2792 : :
2793 : : /*
2794 : : * Back-link constraint arcs must not be followed. Nor is there a
2795 : : * need to revisit states previously merged into this clone.
2796 : : */
2797 [ - + ]: 7893 : assert(sto->no < nstates);
2798 [ + + ]: 7893 : if (donemap[sto->no] != 0)
2799 : 2408 : continue;
2800 : :
2801 : : /*
2802 : : * Check whether we already have a child clone state for this
2803 : : * source state.
2804 : : */
2805 : 5485 : prevclone = NULL;
2806 [ + + ]: 18762 : for (a2 = sclone->outs; a2 != NULL; a2 = a2->outchain)
2807 : : {
2808 [ + + ]: 17157 : if (a2->to->tmp == sto)
2809 : : {
2810 : 3880 : prevclone = a2->to;
2811 : 3880 : break;
2812 : : }
2813 : : }
2814 : :
2815 : : /*
2816 : : * If this arc is labeled the same as refarc, or the same as any
2817 : : * arc we must have traversed to get to sclone, then no additional
2818 : : * constraints need to be met to get to sto, so we should just
2819 : : * merge its outarcs into sclone.
2820 : : */
2821 [ + + + + : 5485 : if (refarc && a->type == refarc->type && a->co == refarc->co)
+ - ]
2822 : 901 : canmerge = 1;
2823 : : else
2824 : : {
2825 : : struct state *s;
2826 : :
2827 : 4584 : canmerge = 0;
2828 [ + + ]: 22946 : for (s = sclone; s->ins; s = s->ins->from)
2829 : : {
2830 [ + + ]: 18362 : if (s->nins == 1 &&
2831 [ + - - + ]: 18 : a->type == s->ins->type && a->co == s->ins->co)
2832 : : {
3613 tgl@sss.pgh.pa.us 2833 :UBC 0 : canmerge = 1;
2834 : 0 : break;
2835 : : }
2836 : : }
2837 : : }
2838 : :
3613 tgl@sss.pgh.pa.us 2839 [ + + ]:CBC 5485 : if (canmerge)
2840 : : {
2841 : : /*
2842 : : * We can merge into sclone. If we previously made a child
2843 : : * clone state, drop it; there's no need to visit it. (This
2844 : : * can happen if ssource has multiple pathways to sto, and we
2845 : : * only just now found one that is provably a no-op.)
2846 : : */
2847 [ - + ]: 901 : if (prevclone)
3613 tgl@sss.pgh.pa.us 2848 :UBC 0 : dropstate(nfa, prevclone); /* kills our outarc, too */
2849 : :
2850 : : /* Recurse to merge sto's outarcs into sclone */
3613 tgl@sss.pgh.pa.us 2851 :CBC 901 : clonesuccessorstates(nfa,
2852 : : sto,
2853 : : sclone,
2854 : : spredecessor,
2855 : : refarc,
2856 : : donemap,
2857 : : outerdonemap,
2858 : : nstates);
2859 : : /* sto should now be marked as previously visited */
2860 [ + - - + ]: 901 : assert(NISERR() || donemap[sto->no] == 1);
2861 : : }
2862 [ + + ]: 4584 : else if (prevclone)
2863 : : {
2864 : : /*
2865 : : * We already have a clone state for this successor, so just
2866 : : * make another arc to it.
2867 : : */
2868 : 3880 : cparc(nfa, a, sclone, prevclone);
2869 : : }
2870 : : else
2871 : : {
2872 : : /*
2873 : : * We need to create a new successor clone state.
2874 : : */
2875 : : struct state *stoclone;
2876 : :
2877 : 704 : stoclone = newstate(nfa);
2878 [ - + ]: 704 : if (stoclone == NULL)
2879 : : {
3613 tgl@sss.pgh.pa.us 2880 [ # # ]:UBC 0 : assert(NISERR());
2881 : 0 : break;
2882 : : }
2883 : : /* Mark it as to what it's a clone of */
3613 tgl@sss.pgh.pa.us 2884 :CBC 704 : stoclone->tmp = sto;
2885 : : /* ... and add the outarc leading to it */
2886 : 704 : cparc(nfa, a, sclone, stoclone);
2887 : : }
2888 : : }
2889 : : else
2890 : : {
2891 : : /*
2892 : : * Non-constraint outarcs just get copied to sclone, as do outarcs
2893 : : * leading to states with no constraint outarc.
2894 : : */
2895 : 5259 : cparc(nfa, a, sclone, sto);
2896 : : }
2897 : : }
2898 : :
2899 : : /*
2900 : : * If we are at outer level for this clone state, recurse to all its child
2901 : : * clone states, clearing their tmp fields as we go. (If we're not
2902 : : * outermost for sclone, leave this to be done by the outer call level.)
2903 : : * Note that if we have multiple outarcs leading to the same clone state,
2904 : : * it will only be recursed-to once.
2905 : : */
2906 [ + + ]: 1811 : if (curdonemap == NULL)
2907 : : {
2908 [ + + + - ]: 8083 : for (a = sclone->outs; a != NULL && !NISERR(); a = a->outchain)
2909 : : {
2910 : 7173 : struct state *stoclone = a->to;
2911 : 7173 : struct state *sto = stoclone->tmp;
2912 : :
2913 [ + + ]: 7173 : if (sto != NULL)
2914 : : {
2915 : 704 : stoclone->tmp = NULL;
2916 : 704 : clonesuccessorstates(nfa,
2917 : : sto,
2918 : : stoclone,
2919 : : spredecessor,
2920 : : refarc,
2921 : : NULL,
2922 : : donemap,
2923 : : nstates);
2924 : : }
2925 : : }
2926 : :
2927 : : /* Don't forget to free sclone's donemap when done with it */
2928 : 910 : FREE(donemap);
2929 : : }
2930 : : }
2931 : :
2932 : : /*
2933 : : * removecantmatch - remove CANTMATCH arcs, which are no longer useful
2934 : : * once we are done with the parsing phase. (We need them only to
2935 : : * preserve connectedness of NFA subgraphs during parsing.)
2936 : : */
2937 : : static void
295 2938 : 6 : removecantmatch(struct nfa *nfa)
2939 : : {
2940 : : struct state *s;
2941 : :
2942 [ + + ]: 46 : for (s = nfa->states; s != NULL; s = s->next)
2943 : : {
2944 : : struct arc *a;
2945 : : struct arc *nexta;
2946 : :
2947 [ + + ]: 101 : for (a = s->outs; a != NULL; a = nexta)
2948 : : {
2949 : 61 : nexta = a->outchain;
2950 [ + + ]: 61 : if (a->type == CANTMATCH)
2951 : : {
2952 : 4 : freearc(nfa, a);
2953 [ - + ]: 4 : if (NISERR())
295 tgl@sss.pgh.pa.us 2954 :UBC 0 : return;
2955 : : }
2956 : : }
2957 : : }
2958 : : }
2959 : :
2960 : : /*
2961 : : * cleanup - clean up NFA after optimizations
2962 : : */
2963 : : static void
2999 tgl@sss.pgh.pa.us 2964 :CBC 19582 : cleanup(struct nfa *nfa)
2965 : : {
2966 : : struct state *s;
2967 : : struct state *nexts;
2968 : : int n;
2969 : :
3627 2970 [ + + ]: 19582 : if (NISERR())
2971 : 3 : return;
2972 : :
2973 : : /* clear out unreachable or dead-end states */
2974 : : /* use pre to mark reachable, then post to mark can-reach-post */
8069 bruce@momjian.us 2975 : 19579 : markreachable(nfa, nfa->pre, (struct state *) NULL, nfa->pre);
8249 tgl@sss.pgh.pa.us 2976 : 19579 : markcanreach(nfa, nfa->post, nfa->pre, nfa->post);
3627 2977 [ + + + - ]: 357145 : for (s = nfa->states; s != NULL && !NISERR(); s = nexts)
2978 : : {
8249 2979 : 337566 : nexts = s->next;
2980 [ + + + + ]: 337566 : if (s->tmp != nfa->post && !s->flag)
2981 : 3140 : dropstate(nfa, s);
2982 : : }
3627 2983 [ + - + + : 19579 : assert(NISERR() || nfa->post->nins == 0 || nfa->post->tmp == nfa->post);
- + ]
8249 2984 : 19579 : cleartraverse(nfa, nfa->pre);
3627 2985 [ + - + + : 19579 : assert(NISERR() || nfa->post->nins == 0 || nfa->post->tmp == NULL);
- + ]
2986 : : /* the nins==0 (final unreachable) case will be caught later */
2987 : :
2988 : : /* renumber surviving states */
8249 2989 : 19579 : n = 0;
2990 [ + + ]: 354005 : for (s = nfa->states; s != NULL; s = s->next)
2991 : 334426 : s->no = n++;
2992 : 19579 : nfa->nstates = n;
2993 : : }
2994 : :
2995 : : /*
2996 : : * markreachable - recursive marking of reachable states
2997 : : */
2998 : : static void
2999 2999 : 893977 : markreachable(struct nfa *nfa,
3000 : : struct state *s,
3001 : : struct state *okay, /* consider only states with this mark */
3002 : : struct state *mark) /* the value to mark with */
3003 : : {
3004 : : struct arc *a;
3005 : :
3006 : : /* Since this is recursive, it could be driven to stack overflow */
3627 3007 [ - + ]: 893977 : if (STACK_TOO_DEEP(nfa->v->re))
3008 : : {
3627 tgl@sss.pgh.pa.us 3009 [ # # ]:UBC 0 : NERR(REG_ETOOBIG);
3010 : 0 : return;
3011 : : }
3012 : :
8249 tgl@sss.pgh.pa.us 3013 [ + + ]:CBC 893977 : if (s->tmp != okay)
3014 : 559556 : return;
3015 : 334421 : s->tmp = mark;
3016 : :
3017 [ + + ]: 1208819 : for (a = s->outs; a != NULL; a = a->outchain)
3018 : 874398 : markreachable(nfa, a->to, okay, mark);
3019 : : }
3020 : :
3021 : : /*
3022 : : * markcanreach - recursive marking of states which can reach here
3023 : : */
3024 : : static void
2999 3025 : 894423 : markcanreach(struct nfa *nfa,
3026 : : struct state *s,
3027 : : struct state *okay, /* consider only states with this mark */
3028 : : struct state *mark) /* the value to mark with */
3029 : : {
3030 : : struct arc *a;
3031 : :
3032 : : /* Since this is recursive, it could be driven to stack overflow */
3627 3033 [ - + ]: 894423 : if (STACK_TOO_DEEP(nfa->v->re))
3034 : : {
3627 tgl@sss.pgh.pa.us 3035 [ # # ]:UBC 0 : NERR(REG_ETOOBIG);
3036 : 0 : return;
3037 : : }
3038 : :
8249 tgl@sss.pgh.pa.us 3039 [ + + ]:CBC 894423 : if (s->tmp != okay)
3040 : 560099 : return;
3041 : 334324 : s->tmp = mark;
3042 : :
3043 [ + + ]: 1209168 : for (a = s->ins; a != NULL; a = a->inchain)
3044 : 874844 : markcanreach(nfa, a->from, okay, mark);
3045 : : }
3046 : :
3047 : : /*
3048 : : * analyze - ascertain potentially-useful facts about an optimized NFA
3049 : : */
3050 : : static long /* re_info bits to be ORed in */
2999 3051 : 9791 : analyze(struct nfa *nfa)
3052 : : {
3053 : : struct arc *a;
3054 : : struct arc *aa;
3055 : :
3627 3056 [ + + ]: 9791 : if (NISERR())
3057 : 3 : return 0;
3058 : :
3059 : : /* Detect whether NFA can't match anything */
8249 3060 [ + + ]: 9788 : if (nfa->pre->outs == NULL)
3061 : 49 : return REG_UIMPOSSIBLE;
3062 : :
3063 : : /* Detect whether NFA matches all strings (possibly with length bounds) */
1659 3064 : 9739 : checkmatchall(nfa);
3065 : :
3066 : : /* Detect whether NFA can possibly match a zero-length string */
8249 3067 [ + + ]: 29375 : for (a = nfa->pre->outs; a != NULL; a = a->outchain)
3068 [ + + ]: 772781 : for (aa = a->to->outs; aa != NULL; aa = aa->outchain)
3069 [ + + ]: 753145 : if (aa->to == nfa->post)
3070 : 1098 : return REG_UEMPTYMATCH;
3071 : 8641 : return 0;
3072 : : }
3073 : :
3074 : : /*
3075 : : * checkmatchall - does the NFA represent no more than a string length test?
3076 : : *
3077 : : * If so, set nfa->minmatchall and nfa->maxmatchall correctly (they are -1
3078 : : * to begin with) and set the MATCHALL bit in nfa->flags.
3079 : : *
3080 : : * To succeed, we require all arcs to be PLAIN RAINBOW arcs, except for those
3081 : : * for pseudocolors (i.e., BOS/BOL/EOS/EOL). We must be able to reach the
3082 : : * post state via RAINBOW arcs, and if there are any loops in the graph, they
3083 : : * must be loop-to-self arcs, ensuring that each loop iteration consumes
3084 : : * exactly one character. (Longer loops are problematic because they create
3085 : : * non-consecutive possible match lengths; we have no good way to represent
3086 : : * that situation for lengths beyond the DUPINF limit.)
3087 : : *
3088 : : * Pseudocolor arcs complicate things a little. We know that they can only
3089 : : * appear as pre-state outarcs (for BOS/BOL) or post-state inarcs (for
3090 : : * EOS/EOL). There, they must exactly replicate the parallel RAINBOW arcs,
3091 : : * e.g. if the pre state has one RAINBOW outarc to state 2, it must have BOS
3092 : : * and BOL outarcs to state 2, and no others. Missing or extra pseudocolor
3093 : : * arcs can occur, meaning that the NFA involves some constraint on the
3094 : : * adjacent characters, which makes it not a matchall NFA.
3095 : : */
3096 : : static void
1659 3097 : 9739 : checkmatchall(struct nfa *nfa)
3098 : : {
3099 : : bool **haspaths;
3100 : : struct state *s;
3101 : : int i;
3102 : :
3103 : : /*
3104 : : * If there are too many states, don't bother trying to detect matchall.
3105 : : * This limit serves to bound the time and memory we could consume below.
3106 : : * Note that even if the graph is all-RAINBOW, if there are significantly
3107 : : * more than DUPINF states then it's likely that there are paths of length
3108 : : * more than DUPINF, which would force us to fail anyhow. In practice,
3109 : : * plausible ways of writing a matchall regex with maximum finite path
3110 : : * length K tend not to have very many more than K states.
3111 : : */
1587 3112 [ + + ]: 9739 : if (nfa->nstates > DUPINF * 2)
3113 : 6 : return;
3114 : :
3115 : : /*
3116 : : * First, scan all the states to verify that only RAINBOW arcs appear,
3117 : : * plus pseudocolor arcs adjacent to the pre and post states. This lets
3118 : : * us quickly eliminate most cases that aren't matchall NFAs.
3119 : : */
3120 [ + + ]: 36349 : for (s = nfa->states; s != NULL; s = s->next)
3121 : : {
3122 : : struct arc *a;
3123 : :
3124 [ + + ]: 101167 : for (a = s->outs; a != NULL; a = a->outchain)
3125 : : {
3126 [ + + ]: 74551 : if (a->type != PLAIN)
3127 : 45 : return; /* any LACONs make it non-matchall */
3128 [ + + ]: 74506 : if (a->co != RAINBOW)
3129 : : {
3130 [ + + ]: 31971 : if (nfa->cm->cd[a->co].flags & PSEUDO)
3131 : : {
3132 : : /*
3133 : : * Pseudocolor arc: verify it's in a valid place (this
3134 : : * seems quite unlikely to fail, but let's be sure).
3135 : : */
3136 [ + + ]: 23063 : if (s == nfa->pre &&
3137 [ + + + - ]: 16723 : (a->co == nfa->bos[0] || a->co == nfa->bos[1]))
3138 : : /* okay BOS/BOL arc */ ;
3139 [ + - ]: 6340 : else if (a->to == nfa->post &&
3140 [ + + + - ]: 6340 : (a->co == nfa->eos[0] || a->co == nfa->eos[1]))
3141 : : /* okay EOS/EOL arc */ ;
3142 : : else
1587 tgl@sss.pgh.pa.us 3143 :UBC 0 : return; /* unexpected pseudocolor arc */
3144 : : /* We'll check these arcs some more below. */
3145 : : }
3146 : : else
1587 tgl@sss.pgh.pa.us 3147 :CBC 8908 : return; /* any other color makes it non-matchall */
3148 : : }
3149 : : }
3150 : : /* Also, assert that the tmp fields are available for use. */
3151 [ - + ]: 26616 : assert(s->tmp == NULL);
3152 : : }
3153 : :
3154 : : /*
3155 : : * The next cheapest check we can make is to verify that the BOS/BOL
3156 : : * outarcs of the pre state reach the same states as its RAINBOW outarcs.
3157 : : * If they don't, the NFA expresses some constraints on the character
3158 : : * before the matched string, making it non-matchall. Likewise, the
3159 : : * EOS/EOL inarcs of the post state must match its RAINBOW inarcs.
3160 : : */
1659 3161 [ + + ]: 780 : if (!check_out_colors_match(nfa->pre, RAINBOW, nfa->bos[0]) ||
3162 [ + + ]: 777 : !check_out_colors_match(nfa->pre, RAINBOW, nfa->bos[1]) ||
1587 3163 [ + + ]: 605 : !check_in_colors_match(nfa->post, RAINBOW, nfa->eos[0]) ||
3164 [ + + ]: 601 : !check_in_colors_match(nfa->post, RAINBOW, nfa->eos[1]))
1659 3165 : 281 : return;
3166 : :
3167 : : /*
3168 : : * Initialize an array of path-length arrays, in which
3169 : : * checkmatchall_recurse will return per-state results. This lets us
3170 : : * memo-ize the recursive search and avoid exponential time consumption.
3171 : : */
1587 3172 : 499 : haspaths = (bool **) MALLOC(nfa->nstates * sizeof(bool *));
3173 [ - + ]: 499 : if (haspaths == NULL)
1587 tgl@sss.pgh.pa.us 3174 :UBC 0 : return; /* fail quietly */
1587 tgl@sss.pgh.pa.us 3175 :CBC 499 : memset(haspaths, 0, nfa->nstates * sizeof(bool *));
3176 : :
3177 : : /*
3178 : : * Recursively search the graph for all-RAINBOW paths to the "post" state,
3179 : : * starting at the "pre" state, and computing the lengths of the paths.
3180 : : * (Given the preceding checks, there should be at least one such path.
3181 : : * However we could get back a false result anyway, in case there are
3182 : : * multi-state loops, paths exceeding DUPINF+1 length, or non-algorithmic
3183 : : * failures such as ENOMEM.)
3184 : : */
3185 [ + + ]: 499 : if (checkmatchall_recurse(nfa, nfa->pre, haspaths))
3186 : : {
3187 : : /* The useful result is the path length array for the pre state */
3188 : 487 : bool *haspath = haspaths[nfa->pre->no];
3189 : : int minmatch,
3190 : : maxmatch,
3191 : : morematch;
3192 : :
3193 [ - + ]: 487 : assert(haspath != NULL);
3194 : :
3195 : : /*
3196 : : * haspath[] now represents the set of possible path lengths; but we
3197 : : * want to reduce that to a min and max value, because it doesn't seem
3198 : : * worth complicating regexec.c to deal with nonconsecutive possible
3199 : : * match lengths. Find min and max of first run of lengths, then
3200 : : * verify there are no nonconsecutive lengths.
3201 : : */
3202 [ + - ]: 1994 : for (minmatch = 0; minmatch <= DUPINF + 1; minmatch++)
3203 : : {
3204 [ + + ]: 1994 : if (haspath[minmatch])
3205 : 487 : break;
3206 : : }
3207 [ - + ]: 487 : assert(minmatch <= DUPINF + 1); /* else checkmatchall_recurse lied */
3208 [ + + ]: 32555 : for (maxmatch = minmatch; maxmatch < DUPINF + 1; maxmatch++)
3209 : : {
3210 [ + + ]: 32432 : if (!haspath[maxmatch + 1])
3211 : 364 : break;
3212 : : }
3213 [ + + ]: 90547 : for (morematch = maxmatch + 1; morematch <= DUPINF + 1; morematch++)
3214 : : {
3215 [ + + ]: 90066 : if (haspath[morematch])
3216 : : {
3217 : 6 : haspath = NULL; /* fail, there are nonconsecutive lengths */
3218 : 6 : break;
3219 : : }
3220 : : }
3221 : :
3222 [ + + ]: 487 : if (haspath != NULL)
3223 : : {
3224 : : /*
3225 : : * Success, so record the info. Here we have a fine point: the
3226 : : * path length from the pre state includes the pre-to-initial
3227 : : * transition, so it's one more than the actually matched string
3228 : : * length. (We avoided counting the final-to-post transition
3229 : : * within checkmatchall_recurse, but not this one.) This is why
3230 : : * checkmatchall_recurse allows one more level of path length than
3231 : : * might seem necessary. This decrement also takes care of
3232 : : * converting checkmatchall_recurse's definition of "infinity" as
3233 : : * "DUPINF+1" to our normal representation as "DUPINF".
3234 : : */
3235 [ - + ]: 481 : assert(minmatch > 0); /* else pre and post states were adjacent */
3236 : 481 : nfa->minmatchall = minmatch - 1;
3237 : 481 : nfa->maxmatchall = maxmatch - 1;
3238 : 481 : nfa->flags |= MATCHALL;
3239 : : }
3240 : : }
3241 : :
3242 : : /* Clean up */
3243 [ + + ]: 5219 : for (i = 0; i < nfa->nstates; i++)
3244 : : {
3245 [ + + ]: 4720 : if (haspaths[i] != NULL)
3246 : 4221 : FREE(haspaths[i]);
3247 : : }
3248 : 499 : FREE(haspaths);
3249 : : }
3250 : :
3251 : : /*
3252 : : * checkmatchall_recurse - recursive search for checkmatchall
3253 : : *
3254 : : * s is the state to be examined in this recursion level.
3255 : : * haspaths[] is an array of per-state exit path length arrays.
3256 : : *
3257 : : * We return true if the search was performed successfully, false if
3258 : : * we had to fail because of multi-state loops or other internal reasons.
3259 : : * (Because "dead" states that can't reach the post state have been
3260 : : * eliminated, and we already verified that only RAINBOW and matching
3261 : : * pseudocolor arcs exist, every state should have RAINBOW path(s) to
3262 : : * the post state. Hence we take a false result from recursive calls
3263 : : * as meaning that we'd better fail altogether, not just that that
3264 : : * particular state can't reach the post state.)
3265 : : *
3266 : : * On success, we store a malloc'd result array in haspaths[s->no],
3267 : : * showing the possible path lengths from s to the post state.
3268 : : * Each state's haspath[] array is of length DUPINF+2. The entries from
3269 : : * k = 0 to DUPINF are true if there is an all-RAINBOW path of length k
3270 : : * from this state to the string end. haspath[DUPINF+1] is true if all
3271 : : * path lengths >= DUPINF+1 are possible. (Situations that cannot be
3272 : : * represented under these rules cause failure.)
3273 : : *
3274 : : * checkmatchall is responsible for eventually freeing the haspath[] arrays.
3275 : : */
3276 : : static bool
3277 : 4221 : checkmatchall_recurse(struct nfa *nfa, struct state *s, bool **haspaths)
3278 : : {
1659 3279 : 4221 : bool result = false;
1587 3280 : 4221 : bool foundloop = false;
3281 : : bool *haspath;
3282 : : struct arc *a;
3283 : :
3284 : : /*
3285 : : * Since this is recursive, it could be driven to stack overflow. But we
3286 : : * need not treat that as a hard failure; just deem the NFA non-matchall.
3287 : : */
1659 3288 [ - + ]: 4221 : if (STACK_TOO_DEEP(nfa->v->re))
1659 tgl@sss.pgh.pa.us 3289 :UBC 0 : return false;
3290 : :
3291 : : /* In case the search takes a long time, check for cancel */
882 tmunro@postgresql.or 3292 [ - + ]:CBC 4221 : INTERRUPT(nfa->v->re);
3293 : :
3294 : : /* Create a haspath array for this state */
1587 tgl@sss.pgh.pa.us 3295 : 4221 : haspath = (bool *) MALLOC((DUPINF + 2) * sizeof(bool));
3296 [ - + ]: 4221 : if (haspath == NULL)
1587 tgl@sss.pgh.pa.us 3297 :UBC 0 : return false; /* again, treat as non-matchall */
1587 tgl@sss.pgh.pa.us 3298 :CBC 4221 : memset(haspath, 0, (DUPINF + 2) * sizeof(bool));
3299 : :
3300 : : /* Mark this state as being visited */
1659 3301 [ - + ]: 4221 : assert(s->tmp == NULL);
3302 : 4221 : s->tmp = s;
3303 : :
3304 [ + + ]: 41487 : for (a = s->outs; a != NULL; a = a->outchain)
3305 : : {
3306 [ + + ]: 37314 : if (a->co != RAINBOW)
3307 : 3230 : continue; /* ignore pseudocolor arcs */
3308 [ + + ]: 34084 : if (a->to == nfa->post)
3309 : : {
3310 : : /* We found an all-RAINBOW path to the post state */
3311 : 493 : result = true;
3312 : :
3313 : : /*
3314 : : * Mark this state as being zero steps away from the string end
3315 : : * (the transition to the post state isn't counted).
3316 : : */
1587 3317 : 493 : haspath[0] = true;
3318 : : }
3319 [ + + ]: 33591 : else if (a->to == s)
3320 : : {
3321 : : /* We found a cycle of length 1, which we'll deal with below. */
3322 : 126 : foundloop = true;
3323 : : }
3324 [ + + ]: 33465 : else if (a->to->tmp != NULL)
3325 : : {
3326 : : /* It's busy, so we found a cycle of length > 1, so fail. */
3327 : 6 : result = false;
3328 : 6 : break;
3329 : : }
3330 : : else
3331 : : {
3332 : : /* Consider paths forward through this to-state. */
3333 : : bool *nexthaspath;
3334 : : int i;
3335 : :
3336 : : /* If to-state was not already visited, recurse */
3337 [ + + ]: 33459 : if (haspaths[a->to->no] == NULL)
3338 : : {
3339 : 3722 : result = checkmatchall_recurse(nfa, a->to, haspaths);
3340 : : /* Fail if any recursive path fails */
3341 [ + + ]: 3722 : if (!result)
3342 : 36 : break;
3343 : : }
3344 : : else
3345 : : {
3346 : : /* The previous visit must have found path(s) to the end */
3347 : 29737 : result = true;
3348 : : }
3349 [ - + ]: 33423 : assert(a->to->tmp == NULL);
3350 : 33423 : nexthaspath = haspaths[a->to->no];
3351 [ - + ]: 33423 : assert(nexthaspath != NULL);
3352 : :
3353 : : /*
3354 : : * Now, for every path of length i from a->to to the string end,
3355 : : * there is a path of length i + 1 from s to the string end.
3356 : : */
3357 [ + + ]: 33423 : if (nexthaspath[DUPINF] != nexthaspath[DUPINF + 1])
3358 : : {
3359 : : /*
3360 : : * a->to has a path of length exactly DUPINF, but not longer;
3361 : : * or it has paths of all lengths > DUPINF but not one of
3362 : : * exactly that length. In either case, we cannot represent
3363 : : * the possible path lengths from s correctly, so fail.
3364 : : */
3365 : 6 : result = false;
3366 : 6 : break;
3367 : : }
3368 : : /* Merge knowledge of these path lengths into what we have */
3369 [ + + ]: 8588169 : for (i = 0; i < DUPINF; i++)
3370 : 8554752 : haspath[i + 1] |= nexthaspath[i];
3371 : : /* Infinity + 1 is still infinity */
3372 : 33417 : haspath[DUPINF + 1] |= nexthaspath[DUPINF + 1];
3373 : : }
3374 : : }
3375 : :
3376 [ + + + + ]: 4221 : if (result && foundloop)
3377 : : {
3378 : : /*
3379 : : * If there is a length-1 loop at this state, then find the shortest
3380 : : * known path length to the end. The loop means that every larger
3381 : : * path length is possible, too. (It doesn't matter whether any of
3382 : : * the longer lengths were already known possible.)
3383 : : */
3384 : : int i;
3385 : :
3386 [ + - ]: 160 : for (i = 0; i <= DUPINF; i++)
3387 : : {
3388 [ + + ]: 160 : if (haspath[i])
1659 3389 : 126 : break;
3390 : : }
1587 3391 [ + + ]: 32474 : for (i++; i <= DUPINF + 1; i++)
3392 : 32348 : haspath[i] = true;
3393 : : }
3394 : :
3395 : : /* Report out the completed path length map */
3396 [ - + ]: 4221 : assert(s->no < nfa->nstates);
3397 [ - + ]: 4221 : assert(haspaths[s->no] == NULL);
3398 : 4221 : haspaths[s->no] = haspath;
3399 : :
3400 : : /* Mark state no longer busy */
1659 3401 : 4221 : s->tmp = NULL;
3402 : :
3403 : 4221 : return result;
3404 : : }
3405 : :
3406 : : /*
3407 : : * check_out_colors_match - subroutine for checkmatchall
3408 : : *
3409 : : * Check whether the set of states reachable from s by arcs of color co1
3410 : : * is equivalent to the set reachable by arcs of color co2.
3411 : : * checkmatchall already verified that all of the NFA's arcs are PLAIN,
3412 : : * so we need not examine arc types here.
3413 : : */
3414 : : static bool
3415 : 1557 : check_out_colors_match(struct state *s, color co1, color co2)
3416 : : {
1587 3417 : 1557 : bool result = true;
3418 : : struct arc *a;
3419 : :
3420 : : /*
3421 : : * To do this in linear time, we assume that the NFA contains no duplicate
3422 : : * arcs. Run through the out-arcs, marking states reachable by arcs of
3423 : : * color co1. Run through again, un-marking states reachable by arcs of
3424 : : * color co2; if we see a not-marked state, we know this co2 arc is
3425 : : * unmatched. Then run through again, checking for still-marked states,
3426 : : * and in any case leaving all the tmp fields reset to NULL.
3427 : : */
3428 [ + + ]: 9493 : for (a = s->outs; a != NULL; a = a->outchain)
3429 : : {
3430 [ + + ]: 7936 : if (a->co == co1)
3431 : : {
3432 [ - + ]: 2520 : assert(a->to->tmp == NULL);
3433 : 2520 : a->to->tmp = a->to;
3434 : : }
3435 : : }
3436 [ + + ]: 9493 : for (a = s->outs; a != NULL; a = a->outchain)
3437 : : {
3438 [ + + ]: 7936 : if (a->co == co2)
3439 : : {
3440 [ + + ]: 2708 : if (a->to->tmp != NULL)
3441 : 2518 : a->to->tmp = NULL;
3442 : : else
3443 : 190 : result = false; /* unmatched co2 arc */
3444 : : }
3445 : : }
3446 [ + + ]: 9493 : for (a = s->outs; a != NULL; a = a->outchain)
3447 : : {
3448 [ + + ]: 7936 : if (a->co == co1)
3449 : : {
3450 [ + + ]: 2520 : if (a->to->tmp != NULL)
3451 : : {
3452 : 2 : result = false; /* unmatched co1 arc */
3453 : 2 : a->to->tmp = NULL;
3454 : : }
3455 : : }
3456 : : }
3457 : 1557 : return result;
3458 : : }
3459 : :
3460 : : /*
3461 : : * check_in_colors_match - subroutine for checkmatchall
3462 : : *
3463 : : * Check whether the set of states that can reach s by arcs of color co1
3464 : : * is equivalent to the set that can reach s by arcs of color co2.
3465 : : * checkmatchall already verified that all of the NFA's arcs are PLAIN,
3466 : : * so we need not examine arc types here.
3467 : : */
3468 : : static bool
1659 3469 : 1206 : check_in_colors_match(struct state *s, color co1, color co2)
3470 : : {
1587 3471 : 1206 : bool result = true;
3472 : : struct arc *a;
3473 : :
3474 : : /*
3475 : : * Identical algorithm to check_out_colors_match, except examine the
3476 : : * from-states of s' inarcs.
3477 : : */
3478 [ + + ]: 4470 : for (a = s->ins; a != NULL; a = a->inchain)
3479 : : {
3480 [ + + ]: 3264 : if (a->co == co1)
3481 : : {
3482 [ - + ]: 1014 : assert(a->from->tmp == NULL);
3483 : 1014 : a->from->tmp = a->from;
3484 : : }
3485 : : }
3486 [ + + ]: 4470 : for (a = s->ins; a != NULL; a = a->inchain)
3487 : : {
3488 [ + + ]: 3264 : if (a->co == co2)
3489 : : {
3490 [ + + ]: 1125 : if (a->from->tmp != NULL)
3491 : 1012 : a->from->tmp = NULL;
3492 : : else
3493 : 113 : result = false; /* unmatched co2 arc */
3494 : : }
3495 : : }
3496 [ + + ]: 4470 : for (a = s->ins; a != NULL; a = a->inchain)
3497 : : {
3498 [ + + ]: 3264 : if (a->co == co1)
3499 : : {
3500 [ + + ]: 1014 : if (a->from->tmp != NULL)
3501 : : {
3502 : 2 : result = false; /* unmatched co1 arc */
3503 : 2 : a->from->tmp = NULL;
3504 : : }
3505 : : }
3506 : : }
3507 : 1206 : return result;
3508 : : }
3509 : :
3510 : : /*
3511 : : * compact - construct the compact representation of an NFA
3512 : : */
3513 : : static void
2999 3514 : 9788 : compact(struct nfa *nfa,
3515 : : struct cnfa *cnfa)
3516 : : {
3517 : : struct state *s;
3518 : : struct arc *a;
3519 : : size_t nstates;
3520 : : size_t narcs;
3521 : : struct carc *ca;
3522 : : struct carc *first;
3523 : :
8069 bruce@momjian.us 3524 [ - + ]: 9788 : assert(!NISERR());
3525 : :
8249 tgl@sss.pgh.pa.us 3526 : 9788 : nstates = 0;
3527 : 9788 : narcs = 0;
8069 bruce@momjian.us 3528 [ + + ]: 129550 : for (s = nfa->states; s != NULL; s = s->next)
3529 : : {
8249 tgl@sss.pgh.pa.us 3530 : 119762 : nstates++;
4483 bruce@momjian.us 3531 : 119762 : narcs += s->nouts + 1; /* need one extra for endmarker */
3532 : : }
3533 : :
4809 tgl@sss.pgh.pa.us 3534 : 9788 : cnfa->stflags = (char *) MALLOC(nstates * sizeof(char));
8069 bruce@momjian.us 3535 : 9788 : cnfa->states = (struct carc **) MALLOC(nstates * sizeof(struct carc *));
3536 : 9788 : cnfa->arcs = (struct carc *) MALLOC(narcs * sizeof(struct carc));
4809 tgl@sss.pgh.pa.us 3537 [ + - + - : 9788 : if (cnfa->stflags == NULL || cnfa->states == NULL || cnfa->arcs == NULL)
- + ]
3538 : : {
4809 tgl@sss.pgh.pa.us 3539 [ # # ]:UBC 0 : if (cnfa->stflags != NULL)
3540 : 0 : FREE(cnfa->stflags);
8249 3541 [ # # ]: 0 : if (cnfa->states != NULL)
3542 : 0 : FREE(cnfa->states);
3543 [ # # ]: 0 : if (cnfa->arcs != NULL)
3544 : 0 : FREE(cnfa->arcs);
3545 [ # # ]: 0 : NERR(REG_ESPACE);
3546 : 0 : return;
3547 : : }
8249 tgl@sss.pgh.pa.us 3548 :CBC 9788 : cnfa->nstates = nstates;
3549 : 9788 : cnfa->pre = nfa->pre->no;
3550 : 9788 : cnfa->post = nfa->post->no;
3551 : 9788 : cnfa->bos[0] = nfa->bos[0];
3552 : 9788 : cnfa->bos[1] = nfa->bos[1];
3553 : 9788 : cnfa->eos[0] = nfa->eos[0];
3554 : 9788 : cnfa->eos[1] = nfa->eos[1];
3555 : 9788 : cnfa->ncolors = maxcolor(nfa->cm) + 1;
1659 3556 : 9788 : cnfa->flags = nfa->flags;
3557 : 9788 : cnfa->minmatchall = nfa->minmatchall;
3558 : 9788 : cnfa->maxmatchall = nfa->maxmatchall;
3559 : :
8249 3560 : 9788 : ca = cnfa->arcs;
8069 bruce@momjian.us 3561 [ + + ]: 129550 : for (s = nfa->states; s != NULL; s = s->next)
3562 : : {
3563 [ - + ]: 119762 : assert((size_t) s->no < nstates);
4809 tgl@sss.pgh.pa.us 3564 : 119762 : cnfa->stflags[s->no] = 0;
8249 3565 : 119762 : cnfa->states[s->no] = ca;
3566 : 119762 : first = ca;
3567 [ + + ]: 892998 : for (a = s->outs; a != NULL; a = a->outchain)
8069 bruce@momjian.us 3568 [ + + - ]: 773236 : switch (a->type)
3569 : : {
3570 : 773137 : case PLAIN:
3571 : 773137 : ca->co = a->co;
3572 : 773137 : ca->to = a->to->no;
3573 : 773137 : ca++;
3574 : 773137 : break;
3575 : 99 : case LACON:
3576 [ - + ]: 99 : assert(s->no != cnfa->pre);
1659 tgl@sss.pgh.pa.us 3577 [ - + ]: 99 : assert(a->co >= 0);
8069 bruce@momjian.us 3578 : 99 : ca->co = (color) (cnfa->ncolors + a->co);
3579 : 99 : ca->to = a->to->no;
3580 : 99 : ca++;
3581 : 99 : cnfa->flags |= HASLACONS;
3582 : 99 : break;
8069 bruce@momjian.us 3583 :UBC 0 : default:
3613 tgl@sss.pgh.pa.us 3584 [ # # ]: 0 : NERR(REG_ASSERT);
1662 3585 : 0 : return;
3586 : : }
3613 tgl@sss.pgh.pa.us 3587 :CBC 119762 : carcsort(first, ca - first);
8249 3588 : 119762 : ca->co = COLORLESS;
3589 : 119762 : ca->to = 0;
3590 : 119762 : ca++;
3591 : : }
3592 [ - + ]: 9788 : assert(ca == &cnfa->arcs[narcs]);
3593 [ - + ]: 9788 : assert(cnfa->nstates != 0);
3594 : :
3595 : : /* mark no-progress states */
3596 [ + + ]: 40809 : for (a = nfa->pre->outs; a != NULL; a = a->outchain)
4809 3597 : 31021 : cnfa->stflags[a->to->no] = CNFA_NOPROGRESS;
3598 : 9788 : cnfa->stflags[nfa->pre->no] = CNFA_NOPROGRESS;
3599 : : }
3600 : :
3601 : : /*
3602 : : * carcsort - sort compacted-NFA arcs by color
3603 : : */
3604 : : static void
2999 3605 : 119762 : carcsort(struct carc *first, size_t n)
3606 : : {
3613 3607 [ + + ]: 119762 : if (n > 1)
3608 : 23042 : qsort(first, n, sizeof(struct carc), carc_cmp);
3609 : 119762 : }
3610 : :
3611 : : static int
3612 : 7725002 : carc_cmp(const void *a, const void *b)
3613 : : {
3614 : 7725002 : const struct carc *aa = (const struct carc *) a;
3615 : 7725002 : const struct carc *bb = (const struct carc *) b;
3616 : :
3617 [ + + ]: 7725002 : if (aa->co < bb->co)
3618 : 69050 : return -1;
3619 [ + + ]: 7655952 : if (aa->co > bb->co)
3620 : 100678 : return +1;
3621 [ + + ]: 7555274 : if (aa->to < bb->to)
3622 : 5181673 : return -1;
3623 [ + - ]: 2373601 : if (aa->to > bb->to)
3624 : 2373601 : return +1;
3625 : : /* This is unreached, since there should be no duplicate arcs now: */
3613 tgl@sss.pgh.pa.us 3626 :UBC 0 : return 0;
3627 : : }
3628 : :
3629 : : /*
3630 : : * freecnfa - free a compacted NFA
3631 : : */
3632 : : static void
2999 tgl@sss.pgh.pa.us 3633 :CBC 2148 : freecnfa(struct cnfa *cnfa)
3634 : : {
1665 3635 [ - + ]: 2148 : assert(!NULLCNFA(*cnfa)); /* not empty already */
4809 3636 : 2148 : FREE(cnfa->stflags);
8249 3637 : 2148 : FREE(cnfa->states);
3638 : 2148 : FREE(cnfa->arcs);
1665 3639 : 2148 : ZAPCNFA(*cnfa);
8249 3640 : 2148 : }
3641 : :
3642 : : /*
3643 : : * dumpnfa - dump an NFA in human-readable form
3644 : : */
3645 : : static void
2999 tgl@sss.pgh.pa.us 3646 :UBC 0 : dumpnfa(struct nfa *nfa,
3647 : : FILE *f)
3648 : : {
3649 : : #ifdef REG_DEBUG
3650 : : struct state *s;
3651 : : int nstates = 0;
3652 : : int narcs = 0;
3653 : :
3654 : : fprintf(f, "pre %d, post %d", nfa->pre->no, nfa->post->no);
3655 : : if (nfa->bos[0] != COLORLESS)
3656 : : fprintf(f, ", bos [%ld]", (long) nfa->bos[0]);
3657 : : if (nfa->bos[1] != COLORLESS)
3658 : : fprintf(f, ", bol [%ld]", (long) nfa->bos[1]);
3659 : : if (nfa->eos[0] != COLORLESS)
3660 : : fprintf(f, ", eos [%ld]", (long) nfa->eos[0]);
3661 : : if (nfa->eos[1] != COLORLESS)
3662 : : fprintf(f, ", eol [%ld]", (long) nfa->eos[1]);
3663 : : if (nfa->flags & HASLACONS)
3664 : : fprintf(f, ", haslacons");
3665 : : if (nfa->flags & HASCANTMATCH)
3666 : : fprintf(f, ", hascantmatch");
3667 : : if (nfa->flags & MATCHALL)
3668 : : {
3669 : : fprintf(f, ", minmatchall %d", nfa->minmatchall);
3670 : : if (nfa->maxmatchall == DUPINF)
3671 : : fprintf(f, ", maxmatchall inf");
3672 : : else
3673 : : fprintf(f, ", maxmatchall %d", nfa->maxmatchall);
3674 : : }
3675 : : fprintf(f, "\n");
3676 : : for (s = nfa->states; s != NULL; s = s->next)
3677 : : {
3678 : : dumpstate(s, f);
3679 : : nstates++;
3680 : : narcs += s->nouts;
3681 : : }
3682 : : fprintf(f, "total of %d states, %d arcs\n", nstates, narcs);
3683 : : if (nfa->parent == NULL)
3684 : : dumpcolors(nfa->cm, f);
3685 : : fflush(f);
3686 : : #endif
8249 3687 : 0 : }
3688 : :
3689 : : #ifdef REG_DEBUG /* subordinates of dumpnfa */
3690 : :
3691 : : /*
3692 : : * dumpstate - dump an NFA state in human-readable form
3693 : : */
3694 : : static void
3695 : : dumpstate(struct state *s,
3696 : : FILE *f)
3697 : : {
3698 : : struct arc *a;
3699 : :
3700 : : fprintf(f, "%d%s%c", s->no, (s->tmp != NULL) ? "T" : "",
3701 : : (s->flag) ? s->flag : '.');
3702 : : if (s->prev != NULL && s->prev->next != s)
3703 : : fprintf(f, "\tstate chain bad\n");
3704 : : if (s->nouts == 0)
3705 : : fprintf(f, "\tno out arcs\n");
3706 : : else
3707 : : dumparcs(s, f);
3708 : : for (a = s->ins; a != NULL; a = a->inchain)
3709 : : {
3710 : : if (a->to != s)
3711 : : fprintf(f, "\tlink from %d to %d on %d's in-chain\n",
3712 : : a->from->no, a->to->no, s->no);
3713 : : }
3714 : : fflush(f);
3715 : : }
3716 : :
3717 : : /*
3718 : : * dumparcs - dump out-arcs in human-readable form
3719 : : */
3720 : : static void
3721 : : dumparcs(struct state *s,
3722 : : FILE *f)
3723 : : {
3724 : : int pos;
3725 : : struct arc *a;
3726 : :
3727 : : /* printing oldest arcs first is usually clearer */
3728 : : a = s->outs;
3729 : : assert(a != NULL);
3730 : : while (a->outchain != NULL)
3731 : : a = a->outchain;
3732 : : pos = 1;
3733 : : do
3734 : : {
3735 : : dumparc(a, s, f);
3736 : : if (pos == 5)
3737 : : {
3738 : : fprintf(f, "\n");
3739 : : pos = 1;
3740 : : }
3741 : : else
3742 : : pos++;
3743 : : a = a->outchainRev;
3744 : : } while (a != NULL);
3745 : : if (pos != 1)
3746 : : fprintf(f, "\n");
3747 : : }
3748 : :
3749 : : /*
3750 : : * dumparc - dump one outarc in readable form, including prefixing tab
3751 : : */
3752 : : static void
3753 : : dumparc(struct arc *a,
3754 : : struct state *s,
3755 : : FILE *f)
3756 : : {
3757 : : struct arc *aa;
3758 : :
3759 : : fprintf(f, "\t");
3760 : : switch (a->type)
3761 : : {
3762 : : case PLAIN:
3763 : : if (a->co == RAINBOW)
3764 : : fprintf(f, "[*]");
3765 : : else
3766 : : fprintf(f, "[%ld]", (long) a->co);
3767 : : break;
3768 : : case AHEAD:
3769 : : if (a->co == RAINBOW)
3770 : : fprintf(f, ">*>");
3771 : : else
3772 : : fprintf(f, ">%ld>", (long) a->co);
3773 : : break;
3774 : : case BEHIND:
3775 : : if (a->co == RAINBOW)
3776 : : fprintf(f, "<*<");
3777 : : else
3778 : : fprintf(f, "<%ld<", (long) a->co);
3779 : : break;
3780 : : case LACON:
3781 : : fprintf(f, ":%ld:", (long) a->co);
3782 : : break;
3783 : : case '^':
3784 : : case '$':
3785 : : fprintf(f, "%c%d", a->type, (int) a->co);
3786 : : break;
3787 : : case EMPTY:
3788 : : break;
3789 : : case CANTMATCH:
3790 : : fprintf(f, "X");
3791 : : break;
3792 : : default:
3793 : : fprintf(f, "0x%x/0%lo", a->type, (long) a->co);
3794 : : break;
3795 : : }
3796 : : if (a->from != s)
3797 : : fprintf(f, "?%d?", a->from->no);
3798 : : for (aa = a->from->outs; aa != NULL; aa = aa->outchain)
3799 : : if (aa == a)
3800 : : break; /* NOTE BREAK OUT */
3801 : : if (aa == NULL)
3802 : : fprintf(f, "?!?"); /* missing from out-chain */
3803 : : fprintf(f, "->");
3804 : : if (a->to == NULL)
3805 : : {
3806 : : fprintf(f, "NULL");
3807 : : return;
3808 : : }
3809 : : fprintf(f, "%d", a->to->no);
3810 : : for (aa = a->to->ins; aa != NULL; aa = aa->inchain)
3811 : : if (aa == a)
3812 : : break; /* NOTE BREAK OUT */
3813 : : if (aa == NULL)
3814 : : fprintf(f, "?!?"); /* missing from in-chain */
3815 : : }
3816 : : #endif /* REG_DEBUG */
3817 : :
3818 : : /*
3819 : : * dumpcnfa - dump a compacted NFA in human-readable form
3820 : : */
3821 : : #ifdef REG_DEBUG
3822 : : static void
3823 : : dumpcnfa(struct cnfa *cnfa,
3824 : : FILE *f)
3825 : : {
3826 : : int st;
3827 : :
3828 : : fprintf(f, "pre %d, post %d", cnfa->pre, cnfa->post);
3829 : : if (cnfa->bos[0] != COLORLESS)
3830 : : fprintf(f, ", bos [%ld]", (long) cnfa->bos[0]);
3831 : : if (cnfa->bos[1] != COLORLESS)
3832 : : fprintf(f, ", bol [%ld]", (long) cnfa->bos[1]);
3833 : : if (cnfa->eos[0] != COLORLESS)
3834 : : fprintf(f, ", eos [%ld]", (long) cnfa->eos[0]);
3835 : : if (cnfa->eos[1] != COLORLESS)
3836 : : fprintf(f, ", eol [%ld]", (long) cnfa->eos[1]);
3837 : : if (cnfa->flags & HASLACONS)
3838 : : fprintf(f, ", haslacons");
3839 : : if (cnfa->flags & MATCHALL)
3840 : : {
3841 : : fprintf(f, ", minmatchall %d", cnfa->minmatchall);
3842 : : if (cnfa->maxmatchall == DUPINF)
3843 : : fprintf(f, ", maxmatchall inf");
3844 : : else
3845 : : fprintf(f, ", maxmatchall %d", cnfa->maxmatchall);
3846 : : }
3847 : : fprintf(f, "\n");
3848 : : for (st = 0; st < cnfa->nstates; st++)
3849 : : dumpcstate(st, cnfa, f);
3850 : : fflush(f);
3851 : : }
3852 : : #endif
3853 : :
3854 : : #ifdef REG_DEBUG /* subordinates of dumpcnfa */
3855 : :
3856 : : /*
3857 : : * dumpcstate - dump a compacted-NFA state in human-readable form
3858 : : */
3859 : : static void
3860 : : dumpcstate(int st,
3861 : : struct cnfa *cnfa,
3862 : : FILE *f)
3863 : : {
3864 : : struct carc *ca;
3865 : : int pos;
3866 : :
3867 : : fprintf(f, "%d%s", st, (cnfa->stflags[st] & CNFA_NOPROGRESS) ? ":" : ".");
3868 : : pos = 1;
3869 : : for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++)
3870 : : {
3871 : : if (ca->co == RAINBOW)
3872 : : fprintf(f, "\t[*]->%d", ca->to);
3873 : : else if (ca->co < cnfa->ncolors)
3874 : : fprintf(f, "\t[%ld]->%d", (long) ca->co, ca->to);
3875 : : else
3876 : : fprintf(f, "\t:%ld:->%d", (long) (ca->co - cnfa->ncolors), ca->to);
3877 : : if (pos == 5)
3878 : : {
3879 : : fprintf(f, "\n");
3880 : : pos = 1;
3881 : : }
3882 : : else
3883 : : pos++;
3884 : : }
3885 : : if (ca == cnfa->states[st] || pos != 1)
3886 : : fprintf(f, "\n");
3887 : : fflush(f);
3888 : : }
3889 : :
3890 : : #endif /* REG_DEBUG */
|
