/[dtapublic]/projs/trunk/shared_source/c_tcl_base_7_5_w_mods/regc_nfa.c
ViewVC logotype

Annotation of /projs/trunk/shared_source/c_tcl_base_7_5_w_mods/regc_nfa.c

Parent Directory Parent Directory | Revision Log Revision Log


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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25