]> git.saurik.com Git - wxWidgets.git/blob - src/regex/regc_nfa.c
remove extraneous semicolons (patch 1299687)
[wxWidgets.git] / src / regex / regc_nfa.c
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 *
32 *
33 * One or two things that technically ought to be in here
34 * are actually in color.c, thanks to some incestuous relationships in
35 * the color chains.
36 */
37
38 #define NISERR() VISERR(nfa->v)
39 #define NERR(e) VERR(nfa->v, (e))
40
41
42 /*
43 - newnfa - set up an NFA
44 ^ static struct nfa *newnfa(struct vars *, struct colormap *, struct nfa *);
45 */
46 static struct nfa * /* the NFA, or NULL */
47 newnfa(v, cm, parent)
48 struct vars *v;
49 struct colormap *cm;
50 struct nfa *parent; /* NULL if primary NFA */
51 {
52 struct nfa *nfa;
53
54 nfa = (struct nfa *)MALLOC(sizeof(struct nfa));
55 if (nfa == NULL)
56 return NULL;
57
58 nfa->states = NULL;
59 nfa->slast = NULL;
60 nfa->free = NULL;
61 nfa->nstates = 0;
62 nfa->cm = cm;
63 nfa->v = v;
64 nfa->bos[0] = nfa->bos[1] = COLORLESS;
65 nfa->eos[0] = nfa->eos[1] = COLORLESS;
66 nfa->post = newfstate(nfa, '@'); /* number 0 */
67 nfa->pre = newfstate(nfa, '>'); /* number 1 */
68 nfa->parent = parent;
69
70 nfa->init = newstate(nfa); /* may become invalid later */
71 nfa->final = newstate(nfa);
72 if (ISERR()) {
73 freenfa(nfa);
74 return NULL;
75 }
76 rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->pre, nfa->init);
77 newarc(nfa, '^', 1, nfa->pre, nfa->init);
78 newarc(nfa, '^', 0, nfa->pre, nfa->init);
79 rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->final, nfa->post);
80 newarc(nfa, '$', 1, nfa->final, nfa->post);
81 newarc(nfa, '$', 0, nfa->final, nfa->post);
82
83 if (ISERR()) {
84 freenfa(nfa);
85 return NULL;
86 }
87 return nfa;
88 }
89
90 /*
91 - freenfa - free an entire NFA
92 ^ static VOID freenfa(struct nfa *);
93 */
94 static VOID
95 freenfa(nfa)
96 struct nfa *nfa;
97 {
98 struct state *s;
99
100 while ((s = nfa->states) != NULL) {
101 s->nins = s->nouts = 0; /* don't worry about arcs */
102 freestate(nfa, s);
103 }
104 while ((s = nfa->free) != NULL) {
105 nfa->free = s->next;
106 destroystate(nfa, s);
107 }
108
109 nfa->slast = NULL;
110 nfa->nstates = -1;
111 nfa->pre = NULL;
112 nfa->post = NULL;
113 FREE(nfa);
114 }
115
116 /*
117 - newstate - allocate an NFA state, with zero flag value
118 ^ static struct state *newstate(struct nfa *);
119 */
120 static struct state * /* NULL on error */
121 newstate(nfa)
122 struct nfa *nfa;
123 {
124 struct state *s;
125
126 if (nfa->free != NULL) {
127 s = nfa->free;
128 nfa->free = s->next;
129 } else {
130 s = (struct state *)MALLOC(sizeof(struct state));
131 if (s == NULL) {
132 NERR(REG_ESPACE);
133 return NULL;
134 }
135 s->oas.next = NULL;
136 s->free = NULL;
137 s->noas = 0;
138 }
139
140 assert(nfa->nstates >= 0);
141 s->no = nfa->nstates++;
142 s->flag = 0;
143 if (nfa->states == NULL)
144 nfa->states = s;
145 s->nins = 0;
146 s->ins = NULL;
147 s->nouts = 0;
148 s->outs = NULL;
149 s->tmp = NULL;
150 s->next = NULL;
151 if (nfa->slast != NULL) {
152 assert(nfa->slast->next == NULL);
153 nfa->slast->next = s;
154 }
155 s->prev = nfa->slast;
156 nfa->slast = s;
157 return s;
158 }
159
160 /*
161 - newfstate - allocate an NFA state with a specified flag value
162 ^ static struct state *newfstate(struct nfa *, int flag);
163 */
164 static struct state * /* NULL on error */
165 newfstate(nfa, flag)
166 struct nfa *nfa;
167 int flag;
168 {
169 struct state *s;
170
171 s = newstate(nfa);
172 if (s != NULL)
173 s->flag = (char)flag;
174 return s;
175 }
176
177 /*
178 - dropstate - delete a state's inarcs and outarcs and free it
179 ^ static VOID dropstate(struct nfa *, struct state *);
180 */
181 static VOID
182 dropstate(nfa, s)
183 struct nfa *nfa;
184 struct state *s;
185 {
186 struct arc *a;
187
188 while ((a = s->ins) != NULL)
189 freearc(nfa, a);
190 while ((a = s->outs) != NULL)
191 freearc(nfa, a);
192 freestate(nfa, s);
193 }
194
195 /*
196 - freestate - free a state, which has no in-arcs or out-arcs
197 ^ static VOID freestate(struct nfa *, struct state *);
198 */
199 static VOID
200 freestate(nfa, s)
201 struct nfa *nfa;
202 struct state *s;
203 {
204 assert(s != NULL);
205 assert(s->nins == 0 && s->nouts == 0);
206
207 s->no = FREESTATE;
208 s->flag = 0;
209 if (s->next != NULL)
210 s->next->prev = s->prev;
211 else {
212 assert(s == nfa->slast);
213 nfa->slast = s->prev;
214 }
215 if (s->prev != NULL)
216 s->prev->next = s->next;
217 else {
218 assert(s == nfa->states);
219 nfa->states = s->next;
220 }
221 s->prev = NULL;
222 s->next = nfa->free; /* don't delete it, put it on the free list */
223 nfa->free = s;
224 }
225
226 /*
227 - destroystate - really get rid of an already-freed state
228 ^ static VOID destroystate(struct nfa *, struct state *);
229 */
230 static VOID
231 destroystate(nfa, s)
232 struct nfa *nfa;
233 struct state *s;
234 {
235 struct arcbatch *ab;
236 struct arcbatch *abnext;
237
238 assert(s->no == FREESTATE);
239 for (ab = s->oas.next; ab != NULL; ab = abnext) {
240 abnext = ab->next;
241 FREE(ab);
242 }
243 s->ins = NULL;
244 s->outs = NULL;
245 s->next = NULL;
246 FREE(s);
247 }
248
249 /*
250 - newarc - set up a new arc within an NFA
251 ^ static VOID newarc(struct nfa *, int, pcolor, struct state *,
252 ^ struct state *);
253 */
254 static VOID
255 newarc(nfa, t, co, from, to)
256 struct nfa *nfa;
257 int t;
258 pcolor co;
259 struct state *from;
260 struct state *to;
261 {
262 struct arc *a;
263
264 assert(from != NULL && to != NULL);
265
266 /* check for duplicates */
267 for (a = from->outs; a != NULL; a = a->outchain)
268 if (a->to == to && a->co == co && a->type == t)
269 return;
270
271 a = allocarc(nfa, from);
272 if (NISERR())
273 return;
274 assert(a != NULL);
275
276 a->type = t;
277 a->co = (color)co;
278 a->to = to;
279 a->from = from;
280
281 /*
282 * Put the new arc on the beginning, not the end, of the chains.
283 * Not only is this easier, it has the very useful side effect that
284 * deleting the most-recently-added arc is the cheapest case rather
285 * than the most expensive one.
286 */
287 a->inchain = to->ins;
288 to->ins = a;
289 a->outchain = from->outs;
290 from->outs = a;
291
292 from->nouts++;
293 to->nins++;
294
295 if (COLORED(a) && nfa->parent == NULL)
296 colorchain(nfa->cm, a);
297
298 return;
299 }
300
301 /*
302 - allocarc - allocate a new out-arc within a state
303 ^ static struct arc *allocarc(struct nfa *, struct state *);
304 */
305 static struct arc * /* NULL for failure */
306 allocarc(nfa, s)
307 struct nfa *nfa;
308 struct state *s;
309 {
310 struct arc *a;
311 struct arcbatch *new;
312 int i;
313
314 /* shortcut */
315 if (s->free == NULL && s->noas < ABSIZE) {
316 a = &s->oas.a[s->noas];
317 s->noas++;
318 return a;
319 }
320
321 /* if none at hand, get more */
322 if (s->free == NULL) {
323 new = (struct arcbatch *)MALLOC(sizeof(struct arcbatch));
324 if (new == NULL) {
325 NERR(REG_ESPACE);
326 return NULL;
327 }
328 new->next = s->oas.next;
329 s->oas.next = new;
330
331 for (i = 0; i < ABSIZE; i++) {
332 new->a[i].type = 0;
333 new->a[i].freechain = &new->a[i+1];
334 }
335 new->a[ABSIZE-1].freechain = NULL;
336 s->free = &new->a[0];
337 }
338 assert(s->free != NULL);
339
340 a = s->free;
341 s->free = a->freechain;
342 return a;
343 }
344
345 /*
346 - freearc - free an arc
347 ^ static VOID freearc(struct nfa *, struct arc *);
348 */
349 static VOID
350 freearc(nfa, victim)
351 struct nfa *nfa;
352 struct arc *victim;
353 {
354 struct state *from = victim->from;
355 struct state *to = victim->to;
356 struct arc *a;
357
358 assert(victim->type != 0);
359
360 /* take it off color chain if necessary */
361 if (COLORED(victim) && nfa->parent == NULL)
362 uncolorchain(nfa->cm, victim);
363
364 /* take it off source's out-chain */
365 assert(from != NULL);
366 assert(from->outs != NULL);
367 a = from->outs;
368 if (a == victim) /* simple case: first in chain */
369 from->outs = victim->outchain;
370 else {
371 for (; a != NULL && a->outchain != victim; a = a->outchain)
372 continue;
373 assert(a != NULL);
374 a->outchain = victim->outchain;
375 }
376 from->nouts--;
377
378 /* take it off target's in-chain */
379 assert(to != NULL);
380 assert(to->ins != NULL);
381 a = to->ins;
382 if (a == victim) /* simple case: first in chain */
383 to->ins = victim->inchain;
384 else {
385 for (; a != NULL && a->inchain != victim; a = a->inchain)
386 continue;
387 assert(a != NULL);
388 a->inchain = victim->inchain;
389 }
390 to->nins--;
391
392 /* clean up and place on free list */
393 victim->type = 0;
394 victim->from = NULL; /* precautions... */
395 victim->to = NULL;
396 victim->inchain = NULL;
397 victim->outchain = NULL;
398 victim->freechain = from->free;
399 from->free = victim;
400 }
401
402 /*
403 - findarc - find arc, if any, from given source with given type and color
404 * If there is more than one such arc, the result is random.
405 ^ static struct arc *findarc(struct state *, int, pcolor);
406 */
407 static struct arc *
408 findarc(s, type, co)
409 struct state *s;
410 int type;
411 pcolor co;
412 {
413 struct arc *a;
414
415 for (a = s->outs; a != NULL; a = a->outchain)
416 if (a->type == type && a->co == co)
417 return a;
418 return NULL;
419 }
420
421 /*
422 - cparc - allocate a new arc within an NFA, copying details from old one
423 ^ static VOID cparc(struct nfa *, struct arc *, struct state *,
424 ^ struct state *);
425 */
426 static VOID
427 cparc(nfa, oa, from, to)
428 struct nfa *nfa;
429 struct arc *oa;
430 struct state *from;
431 struct state *to;
432 {
433 newarc(nfa, oa->type, oa->co, from, to);
434 }
435
436 /*
437 - moveins - move all in arcs of a state to another state
438 * You might think this could be done better by just updating the
439 * existing arcs, and you would be right if it weren't for the desire
440 * for duplicate suppression, which makes it easier to just make new
441 * ones to exploit the suppression built into newarc.
442 ^ static VOID moveins(struct nfa *, struct state *, struct state *);
443 */
444 static VOID
445 moveins(nfa, old, new)
446 struct nfa *nfa;
447 struct state *old;
448 struct state *new;
449 {
450 struct arc *a;
451
452 assert(old != new);
453
454 while ((a = old->ins) != NULL) {
455 cparc(nfa, a, a->from, new);
456 freearc(nfa, a);
457 }
458 assert(old->nins == 0);
459 assert(old->ins == NULL);
460 }
461
462 /*
463 - copyins - copy all in arcs of a state to another state
464 ^ static VOID copyins(struct nfa *, struct state *, struct state *);
465 */
466 static VOID
467 copyins(nfa, old, new)
468 struct nfa *nfa;
469 struct state *old;
470 struct state *new;
471 {
472 struct arc *a;
473
474 assert(old != new);
475
476 for (a = old->ins; a != NULL; a = a->inchain)
477 cparc(nfa, a, a->from, new);
478 }
479
480 /*
481 - moveouts - move all out arcs of a state to another state
482 ^ static VOID moveouts(struct nfa *, struct state *, struct state *);
483 */
484 static VOID
485 moveouts(nfa, old, new)
486 struct nfa *nfa;
487 struct state *old;
488 struct state *new;
489 {
490 struct arc *a;
491
492 assert(old != new);
493
494 while ((a = old->outs) != NULL) {
495 cparc(nfa, a, new, a->to);
496 freearc(nfa, a);
497 }
498 }
499
500 /*
501 - copyouts - copy all out arcs of a state to another state
502 ^ static VOID copyouts(struct nfa *, struct state *, struct state *);
503 */
504 static VOID
505 copyouts(nfa, old, new)
506 struct nfa *nfa;
507 struct state *old;
508 struct state *new;
509 {
510 struct arc *a;
511
512 assert(old != new);
513
514 for (a = old->outs; a != NULL; a = a->outchain)
515 cparc(nfa, a, new, a->to);
516 }
517
518 /*
519 - cloneouts - copy out arcs of a state to another state pair, modifying type
520 ^ static VOID cloneouts(struct nfa *, struct state *, struct state *,
521 ^ struct state *, int);
522 */
523 static VOID
524 cloneouts(nfa, old, from, to, type)
525 struct nfa *nfa;
526 struct state *old;
527 struct state *from;
528 struct state *to;
529 int type;
530 {
531 struct arc *a;
532
533 assert(old != from);
534
535 for (a = old->outs; a != NULL; a = a->outchain)
536 newarc(nfa, type, a->co, from, to);
537 }
538
539 /*
540 - delsub - delete a sub-NFA, updating subre pointers if necessary
541 * This uses a recursive traversal of the sub-NFA, marking already-seen
542 * states using their tmp pointer.
543 ^ static VOID delsub(struct nfa *, struct state *, struct state *);
544 */
545 static VOID
546 delsub(nfa, lp, rp)
547 struct nfa *nfa;
548 struct state *lp; /* the sub-NFA goes from here... */
549 struct state *rp; /* ...to here, *not* inclusive */
550 {
551 assert(lp != rp);
552
553 rp->tmp = rp; /* mark end */
554
555 deltraverse(nfa, lp, lp);
556 assert(lp->nouts == 0 && rp->nins == 0); /* did the job */
557 assert(lp->no != FREESTATE && rp->no != FREESTATE); /* no more */
558
559 rp->tmp = NULL; /* unmark end */
560 lp->tmp = NULL; /* and begin, marked by deltraverse */
561 }
562
563 /*
564 - deltraverse - the recursive heart of delsub
565 * This routine's basic job is to destroy all out-arcs of the state.
566 ^ static VOID deltraverse(struct nfa *, struct state *, struct state *);
567 */
568 static VOID
569 deltraverse(nfa, leftend, s)
570 struct nfa *nfa;
571 struct state *leftend;
572 struct state *s;
573 {
574 struct arc *a;
575 struct state *to;
576
577 if (s->nouts == 0)
578 return; /* nothing to do */
579 if (s->tmp != NULL)
580 return; /* already in progress */
581
582 s->tmp = s; /* mark as in progress */
583
584 while ((a = s->outs) != NULL) {
585 to = a->to;
586 deltraverse(nfa, leftend, to);
587 assert(to->nouts == 0 || to->tmp != NULL);
588 freearc(nfa, a);
589 if (to->nins == 0 && to->tmp == NULL) {
590 assert(to->nouts == 0);
591 freestate(nfa, to);
592 }
593 }
594
595 assert(s->no != FREESTATE); /* we're still here */
596 assert(s == leftend || s->nins != 0); /* and still reachable */
597 assert(s->nouts == 0); /* but have no outarcs */
598
599 s->tmp = NULL; /* we're done here */
600 }
601
602 /*
603 - dupnfa - duplicate sub-NFA
604 * Another recursive traversal, this time using tmp to point to duplicates
605 * as well as mark already-seen states. (You knew there was a reason why
606 * it's a state pointer, didn't you? :-))
607 ^ static VOID dupnfa(struct nfa *, struct state *, struct state *,
608 ^ struct state *, struct state *);
609 */
610 static VOID
611 dupnfa(nfa, start, stop, from, to)
612 struct nfa *nfa;
613 struct state *start; /* duplicate of subNFA starting here */
614 struct state *stop; /* and stopping here */
615 struct state *from; /* stringing duplicate from here */
616 struct state *to; /* to here */
617 {
618 if (start == stop) {
619 newarc(nfa, EMPTY, 0, from, to);
620 return;
621 }
622
623 stop->tmp = to;
624 duptraverse(nfa, start, from);
625 /* done, except for clearing out the tmp pointers */
626
627 stop->tmp = NULL;
628 cleartraverse(nfa, start);
629 }
630
631 /*
632 - duptraverse - recursive heart of dupnfa
633 ^ static VOID duptraverse(struct nfa *, struct state *, struct state *);
634 */
635 static VOID
636 duptraverse(nfa, s, stmp)
637 struct nfa *nfa;
638 struct state *s;
639 struct state *stmp; /* s's duplicate, or NULL */
640 {
641 struct arc *a;
642
643 if (s->tmp != NULL)
644 return; /* already done */
645
646 s->tmp = (stmp == NULL) ? newstate(nfa) : stmp;
647 if (s->tmp == NULL) {
648 assert(NISERR());
649 return;
650 }
651
652 for (a = s->outs; a != NULL && !NISERR(); a = a->outchain) {
653 duptraverse(nfa, a->to, (struct state *)NULL);
654 assert(a->to->tmp != NULL);
655 cparc(nfa, a, s->tmp, a->to->tmp);
656 }
657 }
658
659 /*
660 - cleartraverse - recursive cleanup for algorithms that leave tmp ptrs set
661 ^ static VOID cleartraverse(struct nfa *, struct state *);
662 */
663 static VOID
664 cleartraverse(nfa, s)
665 struct nfa *nfa;
666 struct state *s;
667 {
668 struct arc *a;
669
670 if (s->tmp == NULL)
671 return;
672 s->tmp = NULL;
673
674 for (a = s->outs; a != NULL; a = a->outchain)
675 cleartraverse(nfa, a->to);
676 }
677
678 /*
679 - specialcolors - fill in special colors for an NFA
680 ^ static VOID specialcolors(struct nfa *);
681 */
682 static VOID
683 specialcolors(nfa)
684 struct nfa *nfa;
685 {
686 /* false colors for BOS, BOL, EOS, EOL */
687 if (nfa->parent == NULL) {
688 nfa->bos[0] = pseudocolor(nfa->cm);
689 nfa->bos[1] = pseudocolor(nfa->cm);
690 nfa->eos[0] = pseudocolor(nfa->cm);
691 nfa->eos[1] = pseudocolor(nfa->cm);
692 } else {
693 assert(nfa->parent->bos[0] != COLORLESS);
694 nfa->bos[0] = nfa->parent->bos[0];
695 assert(nfa->parent->bos[1] != COLORLESS);
696 nfa->bos[1] = nfa->parent->bos[1];
697 assert(nfa->parent->eos[0] != COLORLESS);
698 nfa->eos[0] = nfa->parent->eos[0];
699 assert(nfa->parent->eos[1] != COLORLESS);
700 nfa->eos[1] = nfa->parent->eos[1];
701 }
702 }
703
704 /*
705 - optimize - optimize an NFA
706 ^ static long optimize(struct nfa *, FILE *);
707 */
708 static long /* re_info bits */
709 optimize(nfa, f)
710 struct nfa *nfa;
711 FILE *f; /* for debug output; NULL none */
712 {
713 int verbose = (f != NULL) ? 1 : 0;
714
715 if (verbose)
716 fprintf(f, "\ninitial cleanup:\n");
717 cleanup(nfa); /* may simplify situation */
718 if (verbose)
719 dumpnfa(nfa, f);
720 if (verbose)
721 fprintf(f, "\nempties:\n");
722 fixempties(nfa, f); /* get rid of EMPTY arcs */
723 if (verbose)
724 fprintf(f, "\nconstraints:\n");
725 pullback(nfa, f); /* pull back constraints backward */
726 pushfwd(nfa, f); /* push fwd constraints forward */
727 if (verbose)
728 fprintf(f, "\nfinal cleanup:\n");
729 cleanup(nfa); /* final tidying */
730 return analyze(nfa); /* and analysis */
731 }
732
733 /*
734 - pullback - pull back constraints backward to (with luck) eliminate them
735 ^ static VOID pullback(struct nfa *, FILE *);
736 */
737 static VOID
738 pullback(nfa, f)
739 struct nfa *nfa;
740 FILE *f; /* for debug output; NULL none */
741 {
742 struct state *s;
743 struct state *nexts;
744 struct arc *a;
745 struct arc *nexta;
746 int progress;
747
748 /* find and pull until there are no more */
749 do {
750 progress = 0;
751 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
752 nexts = s->next;
753 for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
754 nexta = a->outchain;
755 if (a->type == '^' || a->type == BEHIND)
756 if (pull(nfa, a))
757 progress = 1;
758 assert(nexta == NULL || s->no != FREESTATE);
759 }
760 }
761 if (progress && f != NULL)
762 dumpnfa(nfa, f);
763 } while (progress && !NISERR());
764 if (NISERR())
765 return;
766
767 for (a = nfa->pre->outs; a != NULL; a = nexta) {
768 nexta = a->outchain;
769 if (a->type == '^') {
770 assert(a->co == 0 || a->co == 1);
771 newarc(nfa, PLAIN, nfa->bos[a->co], a->from, a->to);
772 freearc(nfa, a);
773 }
774 }
775 }
776
777 /*
778 - pull - pull a back constraint backward past its source state
779 * A significant property of this function is that it deletes at most
780 * one state -- the constraint's from state -- and only if the constraint
781 * was that state's last outarc.
782 ^ static int pull(struct nfa *, struct arc *);
783 */
784 static int /* 0 couldn't, 1 could */
785 pull(nfa, con)
786 struct nfa *nfa;
787 struct arc *con;
788 {
789 struct state *from = con->from;
790 struct state *to = con->to;
791 struct arc *a;
792 struct arc *nexta;
793 struct state *s;
794
795 if (from == to) { /* circular constraint is pointless */
796 freearc(nfa, con);
797 return 1;
798 }
799 if (from->flag) /* can't pull back beyond start */
800 return 0;
801 if (from->nins == 0) { /* unreachable */
802 freearc(nfa, con);
803 return 1;
804 }
805
806 /* first, clone from state if necessary to avoid other outarcs */
807 if (from->nouts > 1) {
808 s = newstate(nfa);
809 if (NISERR())
810 return 0;
811 assert(to != from); /* con is not an inarc */
812 copyins(nfa, from, s); /* duplicate inarcs */
813 cparc(nfa, con, s, to); /* move constraint arc */
814 freearc(nfa, con);
815 from = s;
816 con = from->outs;
817 }
818 assert(from->nouts == 1);
819
820 /* propagate the constraint into the from state's inarcs */
821 for (a = from->ins; a != NULL; a = nexta) {
822 nexta = a->inchain;
823 switch (combine(con, a)) {
824 case INCOMPATIBLE: /* destroy the arc */
825 freearc(nfa, a);
826 break;
827 case SATISFIED: /* no action needed */
828 break;
829 case COMPATIBLE: /* swap the two arcs, more or less */
830 s = newstate(nfa);
831 if (NISERR())
832 return 0;
833 cparc(nfa, a, s, to); /* anticipate move */
834 cparc(nfa, con, a->from, s);
835 if (NISERR())
836 return 0;
837 freearc(nfa, a);
838 break;
839 default:
840 assert(NOTREACHED);
841 break;
842 }
843 }
844
845 /* remaining inarcs, if any, incorporate the constraint */
846 moveins(nfa, from, to);
847 dropstate(nfa, from); /* will free the constraint */
848 return 1;
849 }
850
851 /*
852 - pushfwd - push forward constraints forward to (with luck) eliminate them
853 ^ static VOID pushfwd(struct nfa *, FILE *);
854 */
855 static VOID
856 pushfwd(nfa, f)
857 struct nfa *nfa;
858 FILE *f; /* for debug output; NULL none */
859 {
860 struct state *s;
861 struct state *nexts;
862 struct arc *a;
863 struct arc *nexta;
864 int progress;
865
866 /* find and push until there are no more */
867 do {
868 progress = 0;
869 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
870 nexts = s->next;
871 for (a = s->ins; a != NULL && !NISERR(); a = nexta) {
872 nexta = a->inchain;
873 if (a->type == '$' || a->type == AHEAD)
874 if (push(nfa, a))
875 progress = 1;
876 assert(nexta == NULL || s->no != FREESTATE);
877 }
878 }
879 if (progress && f != NULL)
880 dumpnfa(nfa, f);
881 } while (progress && !NISERR());
882 if (NISERR())
883 return;
884
885 for (a = nfa->post->ins; a != NULL; a = nexta) {
886 nexta = a->inchain;
887 if (a->type == '$') {
888 assert(a->co == 0 || a->co == 1);
889 newarc(nfa, PLAIN, nfa->eos[a->co], a->from, a->to);
890 freearc(nfa, a);
891 }
892 }
893 }
894
895 /*
896 - push - push a forward constraint forward past its destination state
897 * A significant property of this function is that it deletes at most
898 * one state -- the constraint's to state -- and only if the constraint
899 * was that state's last inarc.
900 ^ static int push(struct nfa *, struct arc *);
901 */
902 static int /* 0 couldn't, 1 could */
903 push(nfa, con)
904 struct nfa *nfa;
905 struct arc *con;
906 {
907 struct state *from = con->from;
908 struct state *to = con->to;
909 struct arc *a;
910 struct arc *nexta;
911 struct state *s;
912
913 if (to == from) { /* circular constraint is pointless */
914 freearc(nfa, con);
915 return 1;
916 }
917 if (to->flag) /* can't push forward beyond end */
918 return 0;
919 if (to->nouts == 0) { /* dead end */
920 freearc(nfa, con);
921 return 1;
922 }
923
924 /* first, clone to state if necessary to avoid other inarcs */
925 if (to->nins > 1) {
926 s = newstate(nfa);
927 if (NISERR())
928 return 0;
929 copyouts(nfa, to, s); /* duplicate outarcs */
930 cparc(nfa, con, from, s); /* move constraint */
931 freearc(nfa, con);
932 to = s;
933 con = to->ins;
934 }
935 assert(to->nins == 1);
936
937 /* propagate the constraint into the to state's outarcs */
938 for (a = to->outs; a != NULL; a = nexta) {
939 nexta = a->outchain;
940 switch (combine(con, a)) {
941 case INCOMPATIBLE: /* destroy the arc */
942 freearc(nfa, a);
943 break;
944 case SATISFIED: /* no action needed */
945 break;
946 case COMPATIBLE: /* swap the two arcs, more or less */
947 s = newstate(nfa);
948 if (NISERR())
949 return 0;
950 cparc(nfa, con, s, a->to); /* anticipate move */
951 cparc(nfa, a, from, s);
952 if (NISERR())
953 return 0;
954 freearc(nfa, a);
955 break;
956 default:
957 assert(NOTREACHED);
958 break;
959 }
960 }
961
962 /* remaining outarcs, if any, incorporate the constraint */
963 moveouts(nfa, to, from);
964 dropstate(nfa, to); /* will free the constraint */
965 return 1;
966 }
967
968 /*
969 - combine - constraint lands on an arc, what happens?
970 ^ #def INCOMPATIBLE 1 // destroys arc
971 ^ #def SATISFIED 2 // constraint satisfied
972 ^ #def COMPATIBLE 3 // compatible but not satisfied yet
973 ^ static int combine(struct arc *, struct arc *);
974 */
975
976 /* FIXME Required for CW 8 on Mac since it's not in limits.h */
977 #ifndef __CHAR_BIT__
978 #define __CHAR_BIT__ 8
979 #endif
980
981
982 static int
983 combine(con, a)
984 struct arc *con;
985 struct arc *a;
986 {
987 # define CA(ct,at) (((ct)<<CHAR_BIT) | (at))
988
989 switch (CA(con->type, a->type)) {
990 case CA('^', PLAIN): /* newlines are handled separately */
991 case CA('$', PLAIN):
992 return INCOMPATIBLE;
993 break;
994 case CA(AHEAD, PLAIN): /* color constraints meet colors */
995 case CA(BEHIND, PLAIN):
996 if (con->co == a->co)
997 return SATISFIED;
998 return INCOMPATIBLE;
999 break;
1000 case CA('^', '^'): /* collision, similar constraints */
1001 case CA('$', '$'):
1002 case CA(AHEAD, AHEAD):
1003 case CA(BEHIND, BEHIND):
1004 if (con->co == a->co) /* true duplication */
1005 return SATISFIED;
1006 return INCOMPATIBLE;
1007 break;
1008 case CA('^', BEHIND): /* collision, dissimilar constraints */
1009 case CA(BEHIND, '^'):
1010 case CA('$', AHEAD):
1011 case CA(AHEAD, '$'):
1012 return INCOMPATIBLE;
1013 break;
1014 case CA('^', '$'): /* constraints passing each other */
1015 case CA('^', AHEAD):
1016 case CA(BEHIND, '$'):
1017 case CA(BEHIND, AHEAD):
1018 case CA('$', '^'):
1019 case CA('$', BEHIND):
1020 case CA(AHEAD, '^'):
1021 case CA(AHEAD, BEHIND):
1022 case CA('^', LACON):
1023 case CA(BEHIND, LACON):
1024 case CA('$', LACON):
1025 case CA(AHEAD, LACON):
1026 return COMPATIBLE;
1027 break;
1028 }
1029 assert(NOTREACHED);
1030 return INCOMPATIBLE; /* for benefit of blind compilers */
1031 }
1032
1033 /*
1034 - fixempties - get rid of EMPTY arcs
1035 ^ static VOID fixempties(struct nfa *, FILE *);
1036 */
1037 static VOID
1038 fixempties(nfa, f)
1039 struct nfa *nfa;
1040 FILE *f; /* for debug output; NULL none */
1041 {
1042 struct state *s;
1043 struct state *nexts;
1044 struct arc *a;
1045 struct arc *nexta;
1046 int progress;
1047
1048 /* find and eliminate empties until there are no more */
1049 do {
1050 progress = 0;
1051 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
1052 nexts = s->next;
1053 for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
1054 nexta = a->outchain;
1055 if (a->type == EMPTY && unempty(nfa, a))
1056 progress = 1;
1057 assert(nexta == NULL || s->no != FREESTATE);
1058 }
1059 }
1060 if (progress && f != NULL)
1061 dumpnfa(nfa, f);
1062 } while (progress && !NISERR());
1063 }
1064
1065 /*
1066 - unempty - optimize out an EMPTY arc, if possible
1067 * Actually, as it stands this function always succeeds, but the return
1068 * value is kept with an eye on possible future changes.
1069 ^ static int unempty(struct nfa *, struct arc *);
1070 */
1071 static int /* 0 couldn't, 1 could */
1072 unempty(nfa, a)
1073 struct nfa *nfa;
1074 struct arc *a;
1075 {
1076 struct state *from = a->from;
1077 struct state *to = a->to;
1078 int usefrom; /* work on from, as opposed to to? */
1079
1080 assert(a->type == EMPTY);
1081 assert(from != nfa->pre && to != nfa->post);
1082
1083 if (from == to) { /* vacuous loop */
1084 freearc(nfa, a);
1085 return 1;
1086 }
1087
1088 /* decide which end to work on */
1089 usefrom = 1; /* default: attack from */
1090 if (from->nouts > to->nins)
1091 usefrom = 0;
1092 else if (from->nouts == to->nins) {
1093 /* decide on secondary issue: move/copy fewest arcs */
1094 if (from->nins > to->nouts)
1095 usefrom = 0;
1096 }
1097
1098 freearc(nfa, a);
1099 if (usefrom) {
1100 if (from->nouts == 0) {
1101 /* was the state's only outarc */
1102 moveins(nfa, from, to);
1103 freestate(nfa, from);
1104 } else
1105 copyins(nfa, from, to);
1106 } else {
1107 if (to->nins == 0) {
1108 /* was the state's only inarc */
1109 moveouts(nfa, to, from);
1110 freestate(nfa, to);
1111 } else
1112 copyouts(nfa, to, from);
1113 }
1114
1115 return 1;
1116 }
1117
1118 /*
1119 - cleanup - clean up NFA after optimizations
1120 ^ static VOID cleanup(struct nfa *);
1121 */
1122 static VOID
1123 cleanup(nfa)
1124 struct nfa *nfa;
1125 {
1126 struct state *s;
1127 struct state *nexts;
1128 int n;
1129
1130 /* clear out unreachable or dead-end states */
1131 /* use pre to mark reachable, then post to mark can-reach-post */
1132 markreachable(nfa, nfa->pre, (struct state *)NULL, nfa->pre);
1133 markcanreach(nfa, nfa->post, nfa->pre, nfa->post);
1134 for (s = nfa->states; s != NULL; s = nexts) {
1135 nexts = s->next;
1136 if (s->tmp != nfa->post && !s->flag)
1137 dropstate(nfa, s);
1138 }
1139 assert(nfa->post->nins == 0 || nfa->post->tmp == nfa->post);
1140 cleartraverse(nfa, nfa->pre);
1141 assert(nfa->post->nins == 0 || nfa->post->tmp == NULL);
1142 /* the nins==0 (final unreachable) case will be caught later */
1143
1144 /* renumber surviving states */
1145 n = 0;
1146 for (s = nfa->states; s != NULL; s = s->next)
1147 s->no = n++;
1148 nfa->nstates = n;
1149 }
1150
1151 /*
1152 - markreachable - recursive marking of reachable states
1153 ^ static VOID markreachable(struct nfa *, struct state *, struct state *,
1154 ^ struct state *);
1155 */
1156 static VOID
1157 markreachable(nfa, s, okay, mark)
1158 struct nfa *nfa;
1159 struct state *s;
1160 struct state *okay; /* consider only states with this mark */
1161 struct state *mark; /* the value to mark with */
1162 {
1163 struct arc *a;
1164
1165 if (s->tmp != okay)
1166 return;
1167 s->tmp = mark;
1168
1169 for (a = s->outs; a != NULL; a = a->outchain)
1170 markreachable(nfa, a->to, okay, mark);
1171 }
1172
1173 /*
1174 - markcanreach - recursive marking of states which can reach here
1175 ^ static VOID markcanreach(struct nfa *, struct state *, struct state *,
1176 ^ struct state *);
1177 */
1178 static VOID
1179 markcanreach(nfa, s, okay, mark)
1180 struct nfa *nfa;
1181 struct state *s;
1182 struct state *okay; /* consider only states with this mark */
1183 struct state *mark; /* the value to mark with */
1184 {
1185 struct arc *a;
1186
1187 if (s->tmp != okay)
1188 return;
1189 s->tmp = mark;
1190
1191 for (a = s->ins; a != NULL; a = a->inchain)
1192 markcanreach(nfa, a->from, okay, mark);
1193 }
1194
1195 /*
1196 - analyze - ascertain potentially-useful facts about an optimized NFA
1197 ^ static long analyze(struct nfa *);
1198 */
1199 static long /* re_info bits to be ORed in */
1200 analyze(nfa)
1201 struct nfa *nfa;
1202 {
1203 struct arc *a;
1204 struct arc *aa;
1205
1206 if (nfa->pre->outs == NULL)
1207 return REG_UIMPOSSIBLE;
1208 for (a = nfa->pre->outs; a != NULL; a = a->outchain)
1209 for (aa = a->to->outs; aa != NULL; aa = aa->outchain)
1210 if (aa->to == nfa->post)
1211 return REG_UEMPTYMATCH;
1212 return 0;
1213 }
1214
1215 /*
1216 - compact - compact an NFA
1217 ^ static VOID compact(struct nfa *, struct cnfa *);
1218 */
1219 static VOID
1220 compact(nfa, cnfa)
1221 struct nfa *nfa;
1222 struct cnfa *cnfa;
1223 {
1224 struct state *s;
1225 struct arc *a;
1226 size_t nstates;
1227 size_t narcs;
1228 struct carc *ca;
1229 struct carc *first;
1230
1231 assert (!NISERR());
1232
1233 nstates = 0;
1234 narcs = 0;
1235 for (s = nfa->states; s != NULL; s = s->next) {
1236 nstates++;
1237 narcs += 1 + s->nouts + 1;
1238 /* 1 as a fake for flags, nouts for arcs, 1 as endmarker */
1239 }
1240
1241 cnfa->states = (struct carc **)MALLOC(nstates * sizeof(struct carc *));
1242 cnfa->arcs = (struct carc *)MALLOC(narcs * sizeof(struct carc));
1243 if (cnfa->states == NULL || cnfa->arcs == NULL) {
1244 if (cnfa->states != NULL)
1245 FREE(cnfa->states);
1246 if (cnfa->arcs != NULL)
1247 FREE(cnfa->arcs);
1248 NERR(REG_ESPACE);
1249 return;
1250 }
1251 cnfa->nstates = nstates;
1252 cnfa->pre = nfa->pre->no;
1253 cnfa->post = nfa->post->no;
1254 cnfa->bos[0] = nfa->bos[0];
1255 cnfa->bos[1] = nfa->bos[1];
1256 cnfa->eos[0] = nfa->eos[0];
1257 cnfa->eos[1] = nfa->eos[1];
1258 cnfa->ncolors = maxcolor(nfa->cm) + 1;
1259 cnfa->flags = 0;
1260
1261 ca = cnfa->arcs;
1262 for (s = nfa->states; s != NULL; s = s->next) {
1263 assert((size_t)s->no < nstates);
1264 cnfa->states[s->no] = ca;
1265 ca->co = 0; /* clear and skip flags "arc" */
1266 ca++;
1267 first = ca;
1268 for (a = s->outs; a != NULL; a = a->outchain)
1269 switch (a->type) {
1270 case PLAIN:
1271 ca->co = a->co;
1272 ca->to = a->to->no;
1273 ca++;
1274 break;
1275 case LACON:
1276 assert(s->no != cnfa->pre);
1277 ca->co = (color)(cnfa->ncolors + a->co);
1278 ca->to = a->to->no;
1279 ca++;
1280 cnfa->flags |= HASLACONS;
1281 break;
1282 default:
1283 assert(NOTREACHED);
1284 break;
1285 }
1286 carcsort(first, ca-1);
1287 ca->co = COLORLESS;
1288 ca->to = 0;
1289 ca++;
1290 }
1291 assert(ca == &cnfa->arcs[narcs]);
1292 assert(cnfa->nstates != 0);
1293
1294 /* mark no-progress states */
1295 for (a = nfa->pre->outs; a != NULL; a = a->outchain)
1296 cnfa->states[a->to->no]->co = 1;
1297 cnfa->states[nfa->pre->no]->co = 1;
1298 }
1299
1300 /*
1301 - carcsort - sort compacted-NFA arcs by color
1302 * Really dumb algorithm, but if the list is long enough for that to matter,
1303 * you're in real trouble anyway.
1304 ^ static VOID carcsort(struct carc *, struct carc *);
1305 */
1306 static VOID
1307 carcsort(first, last)
1308 struct carc *first;
1309 struct carc *last;
1310 {
1311 struct carc *p;
1312 struct carc *q;
1313 struct carc tmp;
1314
1315 if (last - first <= 1)
1316 return;
1317
1318 for (p = first; p <= last; p++)
1319 for (q = p; q <= last; q++)
1320 if (p->co > q->co ||
1321 (p->co == q->co && p->to > q->to)) {
1322 assert(p != q);
1323 tmp = *p;
1324 *p = *q;
1325 *q = tmp;
1326 }
1327 }
1328
1329 /*
1330 - freecnfa - free a compacted NFA
1331 ^ static VOID freecnfa(struct cnfa *);
1332 */
1333 static VOID
1334 freecnfa(cnfa)
1335 struct cnfa *cnfa;
1336 {
1337 assert(cnfa->nstates != 0); /* not empty already */
1338 cnfa->nstates = 0;
1339 FREE(cnfa->states);
1340 FREE(cnfa->arcs);
1341 }
1342
1343 /*
1344 - dumpnfa - dump an NFA in human-readable form
1345 ^ static VOID dumpnfa(struct nfa *, FILE *);
1346 */
1347 static VOID
1348 dumpnfa(nfa, f)
1349 struct nfa *nfa;
1350 FILE *f;
1351 {
1352 #ifdef REG_DEBUG
1353 struct state *s;
1354
1355 fprintf(f, "pre %d, post %d", nfa->pre->no, nfa->post->no);
1356 if (nfa->bos[0] != COLORLESS)
1357 fprintf(f, ", bos [%ld]", (long)nfa->bos[0]);
1358 if (nfa->bos[1] != COLORLESS)
1359 fprintf(f, ", bol [%ld]", (long)nfa->bos[1]);
1360 if (nfa->eos[0] != COLORLESS)
1361 fprintf(f, ", eos [%ld]", (long)nfa->eos[0]);
1362 if (nfa->eos[1] != COLORLESS)
1363 fprintf(f, ", eol [%ld]", (long)nfa->eos[1]);
1364 fprintf(f, "\n");
1365 for (s = nfa->states; s != NULL; s = s->next)
1366 dumpstate(s, f);
1367 if (nfa->parent == NULL)
1368 dumpcolors(nfa->cm, f);
1369 fflush(f);
1370 #endif
1371 }
1372
1373 #ifdef REG_DEBUG /* subordinates of dumpnfa */
1374 /*
1375 ^ #ifdef REG_DEBUG
1376 */
1377
1378 /*
1379 - dumpstate - dump an NFA state in human-readable form
1380 ^ static VOID dumpstate(struct state *, FILE *);
1381 */
1382 static VOID
1383 dumpstate(s, f)
1384 struct state *s;
1385 FILE *f;
1386 {
1387 struct arc *a;
1388
1389 fprintf(f, "%d%s%c", s->no, (s->tmp != NULL) ? "T" : "",
1390 (s->flag) ? s->flag : '.');
1391 if (s->prev != NULL && s->prev->next != s)
1392 fprintf(f, "\tstate chain bad\n");
1393 if (s->nouts == 0)
1394 fprintf(f, "\tno out arcs\n");
1395 else
1396 dumparcs(s, f);
1397 fflush(f);
1398 for (a = s->ins; a != NULL; a = a->inchain) {
1399 if (a->to != s)
1400 fprintf(f, "\tlink from %d to %d on %d's in-chain\n",
1401 a->from->no, a->to->no, s->no);
1402 }
1403 }
1404
1405 /*
1406 - dumparcs - dump out-arcs in human-readable form
1407 ^ static VOID dumparcs(struct state *, FILE *);
1408 */
1409 static VOID
1410 dumparcs(s, f)
1411 struct state *s;
1412 FILE *f;
1413 {
1414 int pos;
1415
1416 assert(s->nouts > 0);
1417 /* printing arcs in reverse order is usually clearer */
1418 pos = dumprarcs(s->outs, s, f, 1);
1419 if (pos != 1)
1420 fprintf(f, "\n");
1421 }
1422
1423 /*
1424 - dumprarcs - dump remaining outarcs, recursively, in reverse order
1425 ^ static int dumprarcs(struct arc *, struct state *, FILE *, int);
1426 */
1427 static int /* resulting print position */
1428 dumprarcs(a, s, f, pos)
1429 struct arc *a;
1430 struct state *s;
1431 FILE *f;
1432 int pos; /* initial print position */
1433 {
1434 if (a->outchain != NULL)
1435 pos = dumprarcs(a->outchain, s, f, pos);
1436 dumparc(a, s, f);
1437 if (pos == 5) {
1438 fprintf(f, "\n");
1439 pos = 1;
1440 } else
1441 pos++;
1442 return pos;
1443 }
1444
1445 /*
1446 - dumparc - dump one outarc in readable form, including prefixing tab
1447 ^ static VOID dumparc(struct arc *, struct state *, FILE *);
1448 */
1449 static VOID
1450 dumparc(a, s, f)
1451 struct arc *a;
1452 struct state *s;
1453 FILE *f;
1454 {
1455 struct arc *aa;
1456 struct arcbatch *ab;
1457
1458 fprintf(f, "\t");
1459 switch (a->type) {
1460 case PLAIN:
1461 fprintf(f, "[%ld]", (long)a->co);
1462 break;
1463 case AHEAD:
1464 fprintf(f, ">%ld>", (long)a->co);
1465 break;
1466 case BEHIND:
1467 fprintf(f, "<%ld<", (long)a->co);
1468 break;
1469 case LACON:
1470 fprintf(f, ":%ld:", (long)a->co);
1471 break;
1472 case '^':
1473 case '$':
1474 fprintf(f, "%c%d", a->type, (int)a->co);
1475 break;
1476 case EMPTY:
1477 break;
1478 default:
1479 fprintf(f, "0x%x/0%lo", a->type, (long)a->co);
1480 break;
1481 }
1482 if (a->from != s)
1483 fprintf(f, "?%d?", a->from->no);
1484 for (ab = &a->from->oas; ab != NULL; ab = ab->next) {
1485 for (aa = &ab->a[0]; aa < &ab->a[ABSIZE]; aa++)
1486 if (aa == a)
1487 break; /* NOTE BREAK OUT */
1488 if (aa < &ab->a[ABSIZE]) /* propagate break */
1489 break; /* NOTE BREAK OUT */
1490 }
1491 if (ab == NULL)
1492 fprintf(f, "?!?"); /* not in allocated space */
1493 fprintf(f, "->");
1494 if (a->to == NULL) {
1495 fprintf(f, "NULL");
1496 return;
1497 }
1498 fprintf(f, "%d", a->to->no);
1499 for (aa = a->to->ins; aa != NULL; aa = aa->inchain)
1500 if (aa == a)
1501 break; /* NOTE BREAK OUT */
1502 if (aa == NULL)
1503 fprintf(f, "?!?"); /* missing from in-chain */
1504 }
1505
1506 /*
1507 ^ #endif
1508 */
1509 #endif /* ifdef REG_DEBUG */
1510
1511 /*
1512 - dumpcnfa - dump a compacted NFA in human-readable form
1513 ^ static VOID dumpcnfa(struct cnfa *, FILE *);
1514 */
1515 static VOID
1516 dumpcnfa(cnfa, f)
1517 struct cnfa *cnfa;
1518 FILE *f;
1519 {
1520 #ifdef REG_DEBUG
1521 int st;
1522
1523 fprintf(f, "pre %d, post %d", cnfa->pre, cnfa->post);
1524 if (cnfa->bos[0] != COLORLESS)
1525 fprintf(f, ", bos [%ld]", (long)cnfa->bos[0]);
1526 if (cnfa->bos[1] != COLORLESS)
1527 fprintf(f, ", bol [%ld]", (long)cnfa->bos[1]);
1528 if (cnfa->eos[0] != COLORLESS)
1529 fprintf(f, ", eos [%ld]", (long)cnfa->eos[0]);
1530 if (cnfa->eos[1] != COLORLESS)
1531 fprintf(f, ", eol [%ld]", (long)cnfa->eos[1]);
1532 if (cnfa->flags&HASLACONS)
1533 fprintf(f, ", haslacons");
1534 fprintf(f, "\n");
1535 for (st = 0; st < cnfa->nstates; st++)
1536 dumpcstate(st, cnfa->states[st], cnfa, f);
1537 fflush(f);
1538 #endif
1539 }
1540
1541 #ifdef REG_DEBUG /* subordinates of dumpcnfa */
1542 /*
1543 ^ #ifdef REG_DEBUG
1544 */
1545
1546 /*
1547 - dumpcstate - dump a compacted-NFA state in human-readable form
1548 ^ static VOID dumpcstate(int, struct carc *, struct cnfa *, FILE *);
1549 */
1550 static VOID
1551 dumpcstate(st, ca, cnfa, f)
1552 int st;
1553 struct carc *ca;
1554 struct cnfa *cnfa;
1555 FILE *f;
1556 {
1557 int i;
1558 int pos;
1559
1560 fprintf(f, "%d%s", st, (ca[0].co) ? ":" : ".");
1561 pos = 1;
1562 for (i = 1; ca[i].co != COLORLESS; i++) {
1563 if (ca[i].co < cnfa->ncolors)
1564 fprintf(f, "\t[%ld]->%d", (long)ca[i].co, ca[i].to);
1565 else
1566 fprintf(f, "\t:%ld:->%d", (long)ca[i].co-cnfa->ncolors,
1567 ca[i].to);
1568 if (pos == 5) {
1569 fprintf(f, "\n");
1570 pos = 1;
1571 } else
1572 pos++;
1573 }
1574 if (i == 1 || pos != 1)
1575 fprintf(f, "\n");
1576 fflush(f);
1577 }
1578
1579 /*
1580 ^ #endif
1581 */
1582 #endif /* ifdef REG_DEBUG */