]> git.saurik.com Git - wxWidgets.git/blame - src/regex/regc_nfa.c
added wxStringOutputStream::TellO(); fixed bugs in OnSysWrite()
[wxWidgets.git] / src / regex / regc_nfa.c
CommitLineData
48bf5def
RN
1/*
2 * NFA utilities.
3 * This file is #included by regcomp.c.
4 *
3ca4086b
VS
5 * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved.
6 *
48bf5def
RN
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
3ca4086b
VS
10 * thanks all of them.
11 *
48bf5def
RN
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.
3ca4086b 16 *
48bf5def
RN
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.
3ca4086b 19 *
48bf5def
RN
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 *
48bf5def
RN
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
3ca4086b
VS
38#define NISERR() VISERR(nfa->v)
39#define NERR(e) VERR(nfa->v, (e))
48bf5def
RN
40
41
42/*
3ca4086b
VS
43 - newnfa - set up an NFA
44 ^ static struct nfa *newnfa(struct vars *, struct colormap *, struct nfa *);
48bf5def 45 */
3ca4086b
VS
46static struct nfa * /* the NFA, or NULL */
47newnfa(v, cm, parent)
48struct vars *v;
49struct colormap *cm;
50struct nfa *parent; /* NULL if primary NFA */
48bf5def
RN
51{
52 struct nfa *nfa;
53
3ca4086b 54 nfa = (struct nfa *)MALLOC(sizeof(struct nfa));
48bf5def
RN
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
3ca4086b 70 nfa->init = newstate(nfa); /* may become invalid later */
48bf5def 71 nfa->final = newstate(nfa);
3ca4086b 72 if (ISERR()) {
48bf5def
RN
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
3ca4086b 83 if (ISERR()) {
48bf5def
RN
84 freenfa(nfa);
85 return NULL;
86 }
87 return nfa;
88}
89
90/*
3ca4086b
VS
91 - freenfa - free an entire NFA
92 ^ static VOID freenfa(struct nfa *);
48bf5def 93 */
3ca4086b
VS
94static VOID
95freenfa(nfa)
96struct nfa *nfa;
48bf5def
RN
97{
98 struct state *s;
99
3ca4086b
VS
100 while ((s = nfa->states) != NULL) {
101 s->nins = s->nouts = 0; /* don't worry about arcs */
48bf5def
RN
102 freestate(nfa, s);
103 }
3ca4086b 104 while ((s = nfa->free) != NULL) {
48bf5def
RN
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/*
3ca4086b
VS
117 - newstate - allocate an NFA state, with zero flag value
118 ^ static struct state *newstate(struct nfa *);
48bf5def 119 */
3ca4086b
VS
120static struct state * /* NULL on error */
121newstate(nfa)
122struct nfa *nfa;
48bf5def
RN
123{
124 struct state *s;
125
3ca4086b 126 if (nfa->free != NULL) {
48bf5def
RN
127 s = nfa->free;
128 nfa->free = s->next;
3ca4086b
VS
129 } else {
130 s = (struct state *)MALLOC(sizeof(struct state));
131 if (s == NULL) {
48bf5def
RN
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;
3ca4086b 151 if (nfa->slast != NULL) {
48bf5def
RN
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/*
3ca4086b
VS
161 - newfstate - allocate an NFA state with a specified flag value
162 ^ static struct state *newfstate(struct nfa *, int flag);
48bf5def 163 */
3ca4086b
VS
164static struct state * /* NULL on error */
165newfstate(nfa, flag)
166struct nfa *nfa;
167int flag;
48bf5def
RN
168{
169 struct state *s;
170
171 s = newstate(nfa);
172 if (s != NULL)
3ca4086b 173 s->flag = (char)flag;
48bf5def
RN
174 return s;
175}
176
177/*
3ca4086b
VS
178 - dropstate - delete a state's inarcs and outarcs and free it
179 ^ static VOID dropstate(struct nfa *, struct state *);
48bf5def 180 */
3ca4086b
VS
181static VOID
182dropstate(nfa, s)
183struct nfa *nfa;
184struct state *s;
48bf5def
RN
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/*
3ca4086b
VS
196 - freestate - free a state, which has no in-arcs or out-arcs
197 ^ static VOID freestate(struct nfa *, struct state *);
48bf5def 198 */
3ca4086b
VS
199static VOID
200freestate(nfa, s)
201struct nfa *nfa;
202struct state *s;
48bf5def
RN
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;
3ca4086b 211 else {
48bf5def
RN
212 assert(s == nfa->slast);
213 nfa->slast = s->prev;
214 }
215 if (s->prev != NULL)
216 s->prev->next = s->next;
3ca4086b 217 else {
48bf5def
RN
218 assert(s == nfa->states);
219 nfa->states = s->next;
220 }
221 s->prev = NULL;
3ca4086b 222 s->next = nfa->free; /* don't delete it, put it on the free list */
48bf5def
RN
223 nfa->free = s;
224}
225
226/*
3ca4086b
VS
227 - destroystate - really get rid of an already-freed state
228 ^ static VOID destroystate(struct nfa *, struct state *);
48bf5def 229 */
3ca4086b
VS
230static VOID
231destroystate(nfa, s)
232struct nfa *nfa;
233struct state *s;
48bf5def
RN
234{
235 struct arcbatch *ab;
236 struct arcbatch *abnext;
237
238 assert(s->no == FREESTATE);
3ca4086b 239 for (ab = s->oas.next; ab != NULL; ab = abnext) {
48bf5def
RN
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/*
3ca4086b
VS
250 - newarc - set up a new arc within an NFA
251 ^ static VOID newarc(struct nfa *, int, pcolor, struct state *,
252 ^ struct state *);
48bf5def 253 */
3ca4086b
VS
254static VOID
255newarc(nfa, t, co, from, to)
256struct nfa *nfa;
257int t;
258pcolor co;
259struct state *from;
260struct state *to;
48bf5def
RN
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;
3ca4086b 277 a->co = (color)co;
48bf5def
RN
278 a->to = to;
279 a->from = from;
280
281 /*
3ca4086b
VS
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
48bf5def
RN
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/*
3ca4086b
VS
302 - allocarc - allocate a new out-arc within a state
303 ^ static struct arc *allocarc(struct nfa *, struct state *);
48bf5def 304 */
3ca4086b
VS
305static struct arc * /* NULL for failure */
306allocarc(nfa, s)
307struct nfa *nfa;
308struct state *s;
48bf5def
RN
309{
310 struct arc *a;
311 struct arcbatch *new;
3ca4086b 312 int i;
48bf5def
RN
313
314 /* shortcut */
3ca4086b 315 if (s->free == NULL && s->noas < ABSIZE) {
48bf5def
RN
316 a = &s->oas.a[s->noas];
317 s->noas++;
318 return a;
319 }
320
321 /* if none at hand, get more */
3ca4086b
VS
322 if (s->free == NULL) {
323 new = (struct arcbatch *)MALLOC(sizeof(struct arcbatch));
324 if (new == NULL) {
48bf5def
RN
325 NERR(REG_ESPACE);
326 return NULL;
327 }
328 new->next = s->oas.next;
329 s->oas.next = new;
330
3ca4086b 331 for (i = 0; i < ABSIZE; i++) {
48bf5def 332 new->a[i].type = 0;
3ca4086b 333 new->a[i].freechain = &new->a[i+1];
48bf5def 334 }
3ca4086b 335 new->a[ABSIZE-1].freechain = NULL;
48bf5def
RN
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/*
3ca4086b
VS
346 - freearc - free an arc
347 ^ static VOID freearc(struct nfa *, struct arc *);
48bf5def 348 */
3ca4086b
VS
349static VOID
350freearc(nfa, victim)
351struct nfa *nfa;
352struct arc *victim;
48bf5def
RN
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;
3ca4086b 368 if (a == victim) /* simple case: first in chain */
48bf5def 369 from->outs = victim->outchain;
3ca4086b 370 else {
48bf5def
RN
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;
3ca4086b 382 if (a == victim) /* simple case: first in chain */
48bf5def 383 to->ins = victim->inchain;
3ca4086b 384 else {
48bf5def
RN
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/*
3ca4086b 403 - findarc - find arc, if any, from given source with given type and color
48bf5def 404 * If there is more than one such arc, the result is random.
3ca4086b 405 ^ static struct arc *findarc(struct state *, int, pcolor);
48bf5def
RN
406 */
407static struct arc *
3ca4086b
VS
408findarc(s, type, co)
409struct state *s;
410int type;
411pcolor co;
48bf5def
RN
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/*
3ca4086b
VS
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 *);
48bf5def 425 */
3ca4086b
VS
426static VOID
427cparc(nfa, oa, from, to)
428struct nfa *nfa;
429struct arc *oa;
430struct state *from;
431struct state *to;
48bf5def
RN
432{
433 newarc(nfa, oa->type, oa->co, from, to);
434}
435
436/*
3ca4086b 437 - moveins - move all in arcs of a state to another state
48bf5def
RN
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.
3ca4086b 442 ^ static VOID moveins(struct nfa *, struct state *, struct state *);
48bf5def 443 */
3ca4086b
VS
444static VOID
445moveins(nfa, old, new)
446struct nfa *nfa;
447struct state *old;
448struct state *new;
48bf5def
RN
449{
450 struct arc *a;
451
452 assert(old != new);
453
3ca4086b 454 while ((a = old->ins) != NULL) {
48bf5def
RN
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/*
3ca4086b
VS
463 - copyins - copy all in arcs of a state to another state
464 ^ static VOID copyins(struct nfa *, struct state *, struct state *);
48bf5def 465 */
3ca4086b
VS
466static VOID
467copyins(nfa, old, new)
468struct nfa *nfa;
469struct state *old;
470struct state *new;
48bf5def
RN
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/*
3ca4086b
VS
481 - moveouts - move all out arcs of a state to another state
482 ^ static VOID moveouts(struct nfa *, struct state *, struct state *);
48bf5def 483 */
3ca4086b
VS
484static VOID
485moveouts(nfa, old, new)
486struct nfa *nfa;
487struct state *old;
488struct state *new;
48bf5def
RN
489{
490 struct arc *a;
491
492 assert(old != new);
493
3ca4086b 494 while ((a = old->outs) != NULL) {
48bf5def
RN
495 cparc(nfa, a, new, a->to);
496 freearc(nfa, a);
497 }
498}
499
500/*
3ca4086b
VS
501 - copyouts - copy all out arcs of a state to another state
502 ^ static VOID copyouts(struct nfa *, struct state *, struct state *);
48bf5def 503 */
3ca4086b
VS
504static VOID
505copyouts(nfa, old, new)
506struct nfa *nfa;
507struct state *old;
508struct state *new;
48bf5def
RN
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/*
3ca4086b
VS
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);
48bf5def 522 */
3ca4086b
VS
523static VOID
524cloneouts(nfa, old, from, to, type)
525struct nfa *nfa;
526struct state *old;
527struct state *from;
528struct state *to;
529int type;
48bf5def
RN
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/*
3ca4086b 540 - delsub - delete a sub-NFA, updating subre pointers if necessary
48bf5def
RN
541 * This uses a recursive traversal of the sub-NFA, marking already-seen
542 * states using their tmp pointer.
3ca4086b 543 ^ static VOID delsub(struct nfa *, struct state *, struct state *);
48bf5def 544 */
3ca4086b
VS
545static VOID
546delsub(nfa, lp, rp)
547struct nfa *nfa;
548struct state *lp; /* the sub-NFA goes from here... */
549struct state *rp; /* ...to here, *not* inclusive */
48bf5def
RN
550{
551 assert(lp != rp);
552
3ca4086b 553 rp->tmp = rp; /* mark end */
48bf5def
RN
554
555 deltraverse(nfa, lp, lp);
556 assert(lp->nouts == 0 && rp->nins == 0); /* did the job */
3ca4086b 557 assert(lp->no != FREESTATE && rp->no != FREESTATE); /* no more */
48bf5def 558
3ca4086b
VS
559 rp->tmp = NULL; /* unmark end */
560 lp->tmp = NULL; /* and begin, marked by deltraverse */
48bf5def
RN
561}
562
563/*
3ca4086b 564 - deltraverse - the recursive heart of delsub
48bf5def 565 * This routine's basic job is to destroy all out-arcs of the state.
3ca4086b 566 ^ static VOID deltraverse(struct nfa *, struct state *, struct state *);
48bf5def 567 */
3ca4086b
VS
568static VOID
569deltraverse(nfa, leftend, s)
570struct nfa *nfa;
571struct state *leftend;
572struct state *s;
48bf5def
RN
573{
574 struct arc *a;
575 struct state *to;
576
577 if (s->nouts == 0)
3ca4086b 578 return; /* nothing to do */
48bf5def 579 if (s->tmp != NULL)
3ca4086b 580 return; /* already in progress */
48bf5def 581
3ca4086b 582 s->tmp = s; /* mark as in progress */
48bf5def 583
3ca4086b 584 while ((a = s->outs) != NULL) {
48bf5def
RN
585 to = a->to;
586 deltraverse(nfa, leftend, to);
587 assert(to->nouts == 0 || to->tmp != NULL);
588 freearc(nfa, a);
3ca4086b 589 if (to->nins == 0 && to->tmp == NULL) {
48bf5def
RN
590 assert(to->nouts == 0);
591 freestate(nfa, to);
592 }
593 }
594
3ca4086b
VS
595 assert(s->no != FREESTATE); /* we're still here */
596 assert(s == leftend || s->nins != 0); /* and still reachable */
48bf5def
RN
597 assert(s->nouts == 0); /* but have no outarcs */
598
3ca4086b 599 s->tmp = NULL; /* we're done here */
48bf5def
RN
600}
601
602/*
3ca4086b 603 - dupnfa - duplicate sub-NFA
48bf5def
RN
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? :-))
3ca4086b
VS
607 ^ static VOID dupnfa(struct nfa *, struct state *, struct state *,
608 ^ struct state *, struct state *);
48bf5def 609 */
3ca4086b
VS
610static VOID
611dupnfa(nfa, start, stop, from, to)
612struct nfa *nfa;
613struct state *start; /* duplicate of subNFA starting here */
614struct state *stop; /* and stopping here */
615struct state *from; /* stringing duplicate from here */
616struct state *to; /* to here */
48bf5def 617{
3ca4086b 618 if (start == stop) {
48bf5def
RN
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/*
3ca4086b
VS
632 - duptraverse - recursive heart of dupnfa
633 ^ static VOID duptraverse(struct nfa *, struct state *, struct state *);
48bf5def 634 */
3ca4086b
VS
635static VOID
636duptraverse(nfa, s, stmp)
637struct nfa *nfa;
638struct state *s;
639struct state *stmp; /* s's duplicate, or NULL */
48bf5def
RN
640{
641 struct arc *a;
642
643 if (s->tmp != NULL)
3ca4086b 644 return; /* already done */
48bf5def
RN
645
646 s->tmp = (stmp == NULL) ? newstate(nfa) : stmp;
3ca4086b 647 if (s->tmp == NULL) {
48bf5def
RN
648 assert(NISERR());
649 return;
650 }
651
3ca4086b
VS
652 for (a = s->outs; a != NULL && !NISERR(); a = a->outchain) {
653 duptraverse(nfa, a->to, (struct state *)NULL);
48bf5def
RN
654 assert(a->to->tmp != NULL);
655 cparc(nfa, a, s->tmp, a->to->tmp);
656 }
657}
658
659/*
3ca4086b
VS
660 - cleartraverse - recursive cleanup for algorithms that leave tmp ptrs set
661 ^ static VOID cleartraverse(struct nfa *, struct state *);
48bf5def 662 */
3ca4086b
VS
663static VOID
664cleartraverse(nfa, s)
665struct nfa *nfa;
666struct state *s;
48bf5def
RN
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/*
3ca4086b
VS
679 - specialcolors - fill in special colors for an NFA
680 ^ static VOID specialcolors(struct nfa *);
48bf5def 681 */
3ca4086b
VS
682static VOID
683specialcolors(nfa)
684struct nfa *nfa;
48bf5def
RN
685{
686 /* false colors for BOS, BOL, EOS, EOL */
3ca4086b 687 if (nfa->parent == NULL) {
48bf5def
RN
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);
3ca4086b 692 } else {
48bf5def
RN
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/*
3ca4086b
VS
705 - optimize - optimize an NFA
706 ^ static long optimize(struct nfa *, FILE *);
48bf5def 707 */
3ca4086b
VS
708static long /* re_info bits */
709optimize(nfa, f)
710struct nfa *nfa;
711FILE *f; /* for debug output; NULL none */
48bf5def 712{
3ca4086b 713 int verbose = (f != NULL) ? 1 : 0;
48bf5def
RN
714
715 if (verbose)
716 fprintf(f, "\ninitial cleanup:\n");
3ca4086b 717 cleanup(nfa); /* may simplify situation */
48bf5def
RN
718 if (verbose)
719 dumpnfa(nfa, f);
720 if (verbose)
721 fprintf(f, "\nempties:\n");
3ca4086b 722 fixempties(nfa, f); /* get rid of EMPTY arcs */
48bf5def
RN
723 if (verbose)
724 fprintf(f, "\nconstraints:\n");
3ca4086b
VS
725 pullback(nfa, f); /* pull back constraints backward */
726 pushfwd(nfa, f); /* push fwd constraints forward */
48bf5def
RN
727 if (verbose)
728 fprintf(f, "\nfinal cleanup:\n");
3ca4086b
VS
729 cleanup(nfa); /* final tidying */
730 return analyze(nfa); /* and analysis */
48bf5def
RN
731}
732
733/*
3ca4086b
VS
734 - pullback - pull back constraints backward to (with luck) eliminate them
735 ^ static VOID pullback(struct nfa *, FILE *);
48bf5def 736 */
3ca4086b
VS
737static VOID
738pullback(nfa, f)
739struct nfa *nfa;
740FILE *f; /* for debug output; NULL none */
48bf5def
RN
741{
742 struct state *s;
743 struct state *nexts;
744 struct arc *a;
745 struct arc *nexta;
3ca4086b 746 int progress;
48bf5def
RN
747
748 /* find and pull until there are no more */
3ca4086b 749 do {
48bf5def 750 progress = 0;
3ca4086b 751 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
48bf5def 752 nexts = s->next;
3ca4086b 753 for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
48bf5def
RN
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
3ca4086b 767 for (a = nfa->pre->outs; a != NULL; a = nexta) {
48bf5def 768 nexta = a->outchain;
3ca4086b 769 if (a->type == '^') {
48bf5def
RN
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/*
3ca4086b 778 - pull - pull a back constraint backward past its source state
48bf5def
RN
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.
3ca4086b 782 ^ static int pull(struct nfa *, struct arc *);
48bf5def 783 */
3ca4086b
VS
784static int /* 0 couldn't, 1 could */
785pull(nfa, con)
786struct nfa *nfa;
787struct arc *con;
48bf5def
RN
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
3ca4086b 795 if (from == to) { /* circular constraint is pointless */
48bf5def
RN
796 freearc(nfa, con);
797 return 1;
798 }
3ca4086b 799 if (from->flag) /* can't pull back beyond start */
48bf5def 800 return 0;
3ca4086b 801 if (from->nins == 0) { /* unreachable */
48bf5def
RN
802 freearc(nfa, con);
803 return 1;
804 }
805
806 /* first, clone from state if necessary to avoid other outarcs */
3ca4086b 807 if (from->nouts > 1) {
48bf5def
RN
808 s = newstate(nfa);
809 if (NISERR())
810 return 0;
811 assert(to != from); /* con is not an inarc */
3ca4086b
VS
812 copyins(nfa, from, s); /* duplicate inarcs */
813 cparc(nfa, con, s, to); /* move constraint arc */
48bf5def
RN
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 */
3ca4086b 821 for (a = from->ins; a != NULL; a = nexta) {
48bf5def 822 nexta = a->inchain;
3ca4086b
VS
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;
48bf5def
RN
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/*
3ca4086b
VS
852 - pushfwd - push forward constraints forward to (with luck) eliminate them
853 ^ static VOID pushfwd(struct nfa *, FILE *);
48bf5def 854 */
3ca4086b
VS
855static VOID
856pushfwd(nfa, f)
857struct nfa *nfa;
858FILE *f; /* for debug output; NULL none */
48bf5def
RN
859{
860 struct state *s;
861 struct state *nexts;
862 struct arc *a;
863 struct arc *nexta;
3ca4086b 864 int progress;
48bf5def
RN
865
866 /* find and push until there are no more */
3ca4086b 867 do {
48bf5def 868 progress = 0;
3ca4086b 869 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
48bf5def 870 nexts = s->next;
3ca4086b 871 for (a = s->ins; a != NULL && !NISERR(); a = nexta) {
48bf5def
RN
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
3ca4086b 885 for (a = nfa->post->ins; a != NULL; a = nexta) {
48bf5def 886 nexta = a->inchain;
3ca4086b 887 if (a->type == '$') {
48bf5def
RN
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/*
3ca4086b 896 - push - push a forward constraint forward past its destination state
48bf5def
RN
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.
3ca4086b 900 ^ static int push(struct nfa *, struct arc *);
48bf5def 901 */
3ca4086b
VS
902static int /* 0 couldn't, 1 could */
903push(nfa, con)
904struct nfa *nfa;
905struct arc *con;
48bf5def
RN
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
3ca4086b 913 if (to == from) { /* circular constraint is pointless */
48bf5def
RN
914 freearc(nfa, con);
915 return 1;
916 }
3ca4086b 917 if (to->flag) /* can't push forward beyond end */
48bf5def 918 return 0;
3ca4086b 919 if (to->nouts == 0) { /* dead end */
48bf5def
RN
920 freearc(nfa, con);
921 return 1;
922 }
923
924 /* first, clone to state if necessary to avoid other inarcs */
3ca4086b 925 if (to->nins > 1) {
48bf5def
RN
926 s = newstate(nfa);
927 if (NISERR())
928 return 0;
3ca4086b
VS
929 copyouts(nfa, to, s); /* duplicate outarcs */
930 cparc(nfa, con, from, s); /* move constraint */
48bf5def
RN
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 */
3ca4086b 938 for (a = to->outs; a != NULL; a = nexta) {
48bf5def 939 nexta = a->outchain;
3ca4086b
VS
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;
48bf5def
RN
959 }
960 }
961
962 /* remaining outarcs, if any, incorporate the constraint */
963 moveouts(nfa, to, from);
3ca4086b 964 dropstate(nfa, to); /* will free the constraint */
48bf5def
RN
965 return 1;
966}
967
968/*
3ca4086b
VS
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 *);
48bf5def 974 */
0f0fd26d
JS
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
48bf5def 982static int
3ca4086b
VS
983combine(con, a)
984struct arc *con;
985struct arc *a;
48bf5def 986{
3ca4086b
VS
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;
48bf5def
RN
1028 }
1029 assert(NOTREACHED);
1030 return INCOMPATIBLE; /* for benefit of blind compilers */
1031}
1032
1033/*
3ca4086b
VS
1034 - fixempties - get rid of EMPTY arcs
1035 ^ static VOID fixempties(struct nfa *, FILE *);
48bf5def 1036 */
3ca4086b
VS
1037static VOID
1038fixempties(nfa, f)
1039struct nfa *nfa;
1040FILE *f; /* for debug output; NULL none */
48bf5def
RN
1041{
1042 struct state *s;
1043 struct state *nexts;
1044 struct arc *a;
1045 struct arc *nexta;
3ca4086b 1046 int progress;
48bf5def
RN
1047
1048 /* find and eliminate empties until there are no more */
3ca4086b 1049 do {
48bf5def 1050 progress = 0;
3ca4086b 1051 for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
48bf5def 1052 nexts = s->next;
3ca4086b 1053 for (a = s->outs; a != NULL && !NISERR(); a = nexta) {
48bf5def
RN
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/*
3ca4086b 1066 - unempty - optimize out an EMPTY arc, if possible
48bf5def
RN
1067 * Actually, as it stands this function always succeeds, but the return
1068 * value is kept with an eye on possible future changes.
3ca4086b 1069 ^ static int unempty(struct nfa *, struct arc *);
48bf5def 1070 */
3ca4086b
VS
1071static int /* 0 couldn't, 1 could */
1072unempty(nfa, a)
1073struct nfa *nfa;
1074struct arc *a;
48bf5def
RN
1075{
1076 struct state *from = a->from;
1077 struct state *to = a->to;
3ca4086b 1078 int usefrom; /* work on from, as opposed to to? */
48bf5def
RN
1079
1080 assert(a->type == EMPTY);
1081 assert(from != nfa->pre && to != nfa->post);
1082
3ca4086b 1083 if (from == to) { /* vacuous loop */
48bf5def
RN
1084 freearc(nfa, a);
1085 return 1;
1086 }
1087
1088 /* decide which end to work on */
3ca4086b 1089 usefrom = 1; /* default: attack from */
48bf5def
RN
1090 if (from->nouts > to->nins)
1091 usefrom = 0;
3ca4086b 1092 else if (from->nouts == to->nins) {
48bf5def
RN
1093 /* decide on secondary issue: move/copy fewest arcs */
1094 if (from->nins > to->nouts)
1095 usefrom = 0;
1096 }
3ca4086b 1097
48bf5def 1098 freearc(nfa, a);
3ca4086b
VS
1099 if (usefrom) {
1100 if (from->nouts == 0) {
48bf5def
RN
1101 /* was the state's only outarc */
1102 moveins(nfa, from, to);
1103 freestate(nfa, from);
3ca4086b 1104 } else
48bf5def 1105 copyins(nfa, from, to);
3ca4086b
VS
1106 } else {
1107 if (to->nins == 0) {
48bf5def
RN
1108 /* was the state's only inarc */
1109 moveouts(nfa, to, from);
1110 freestate(nfa, to);
3ca4086b 1111 } else
48bf5def
RN
1112 copyouts(nfa, to, from);
1113 }
1114
1115 return 1;
1116}
1117
1118/*
3ca4086b
VS
1119 - cleanup - clean up NFA after optimizations
1120 ^ static VOID cleanup(struct nfa *);
48bf5def 1121 */
3ca4086b
VS
1122static VOID
1123cleanup(nfa)
1124struct nfa *nfa;
48bf5def
RN
1125{
1126 struct state *s;
1127 struct state *nexts;
3ca4086b 1128 int n;
48bf5def
RN
1129
1130 /* clear out unreachable or dead-end states */
1131 /* use pre to mark reachable, then post to mark can-reach-post */
3ca4086b 1132 markreachable(nfa, nfa->pre, (struct state *)NULL, nfa->pre);
48bf5def 1133 markcanreach(nfa, nfa->post, nfa->pre, nfa->post);
3ca4086b 1134 for (s = nfa->states; s != NULL; s = nexts) {
48bf5def
RN
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/*
3ca4086b
VS
1152 - markreachable - recursive marking of reachable states
1153 ^ static VOID markreachable(struct nfa *, struct state *, struct state *,
1154 ^ struct state *);
48bf5def 1155 */
3ca4086b
VS
1156static VOID
1157markreachable(nfa, s, okay, mark)
1158struct nfa *nfa;
1159struct state *s;
1160struct state *okay; /* consider only states with this mark */
1161struct state *mark; /* the value to mark with */
48bf5def
RN
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/*
3ca4086b
VS
1174 - markcanreach - recursive marking of states which can reach here
1175 ^ static VOID markcanreach(struct nfa *, struct state *, struct state *,
1176 ^ struct state *);
48bf5def 1177 */
3ca4086b
VS
1178static VOID
1179markcanreach(nfa, s, okay, mark)
1180struct nfa *nfa;
1181struct state *s;
1182struct state *okay; /* consider only states with this mark */
1183struct state *mark; /* the value to mark with */
48bf5def
RN
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/*
3ca4086b
VS
1196 - analyze - ascertain potentially-useful facts about an optimized NFA
1197 ^ static long analyze(struct nfa *);
48bf5def 1198 */
3ca4086b
VS
1199static long /* re_info bits to be ORed in */
1200analyze(nfa)
1201struct nfa *nfa;
48bf5def
RN
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/*
3ca4086b
VS
1216 - compact - compact an NFA
1217 ^ static VOID compact(struct nfa *, struct cnfa *);
48bf5def 1218 */
3ca4086b
VS
1219static VOID
1220compact(nfa, cnfa)
1221struct nfa *nfa;
1222struct cnfa *cnfa;
48bf5def
RN
1223{
1224 struct state *s;
1225 struct arc *a;
3ca4086b
VS
1226 size_t nstates;
1227 size_t narcs;
48bf5def
RN
1228 struct carc *ca;
1229 struct carc *first;
1230
3ca4086b 1231 assert (!NISERR());
48bf5def
RN
1232
1233 nstates = 0;
1234 narcs = 0;
3ca4086b 1235 for (s = nfa->states; s != NULL; s = s->next) {
48bf5def
RN
1236 nstates++;
1237 narcs += 1 + s->nouts + 1;
1238 /* 1 as a fake for flags, nouts for arcs, 1 as endmarker */
1239 }
1240
3ca4086b
VS
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) {
48bf5def
RN
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;
3ca4086b
VS
1262 for (s = nfa->states; s != NULL; s = s->next) {
1263 assert((size_t)s->no < nstates);
48bf5def 1264 cnfa->states[s->no] = ca;
3ca4086b 1265 ca->co = 0; /* clear and skip flags "arc" */
48bf5def
RN
1266 ca++;
1267 first = ca;
1268 for (a = s->outs; a != NULL; a = a->outchain)
3ca4086b
VS
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;
48bf5def 1285 }
3ca4086b 1286 carcsort(first, ca-1);
48bf5def
RN
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/*
3ca4086b 1301 - carcsort - sort compacted-NFA arcs by color
48bf5def
RN
1302 * Really dumb algorithm, but if the list is long enough for that to matter,
1303 * you're in real trouble anyway.
3ca4086b 1304 ^ static VOID carcsort(struct carc *, struct carc *);
48bf5def 1305 */
3ca4086b
VS
1306static VOID
1307carcsort(first, last)
1308struct carc *first;
1309struct carc *last;
48bf5def
RN
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 ||
3ca4086b 1321 (p->co == q->co && p->to > q->to)) {
48bf5def
RN
1322 assert(p != q);
1323 tmp = *p;
1324 *p = *q;
1325 *q = tmp;
1326 }
1327}
1328
1329/*
3ca4086b
VS
1330 - freecnfa - free a compacted NFA
1331 ^ static VOID freecnfa(struct cnfa *);
48bf5def 1332 */
3ca4086b
VS
1333static VOID
1334freecnfa(cnfa)
1335struct cnfa *cnfa;
48bf5def 1336{
3ca4086b 1337 assert(cnfa->nstates != 0); /* not empty already */
48bf5def
RN
1338 cnfa->nstates = 0;
1339 FREE(cnfa->states);
1340 FREE(cnfa->arcs);
1341}
1342
1343/*
3ca4086b
VS
1344 - dumpnfa - dump an NFA in human-readable form
1345 ^ static VOID dumpnfa(struct nfa *, FILE *);
48bf5def 1346 */
3ca4086b
VS
1347static VOID
1348dumpnfa(nfa, f)
1349struct nfa *nfa;
1350FILE *f;
48bf5def
RN
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)
3ca4086b 1357 fprintf(f, ", bos [%ld]", (long)nfa->bos[0]);
48bf5def 1358 if (nfa->bos[1] != COLORLESS)
3ca4086b 1359 fprintf(f, ", bol [%ld]", (long)nfa->bos[1]);
48bf5def 1360 if (nfa->eos[0] != COLORLESS)
3ca4086b 1361 fprintf(f, ", eos [%ld]", (long)nfa->eos[0]);
48bf5def 1362 if (nfa->eos[1] != COLORLESS)
3ca4086b 1363 fprintf(f, ", eol [%ld]", (long)nfa->eos[1]);
48bf5def
RN
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
3ca4086b
VS
1373#ifdef REG_DEBUG /* subordinates of dumpnfa */
1374/*
1375 ^ #ifdef REG_DEBUG
1376 */
48bf5def
RN
1377
1378/*
3ca4086b
VS
1379 - dumpstate - dump an NFA state in human-readable form
1380 ^ static VOID dumpstate(struct state *, FILE *);
48bf5def 1381 */
3ca4086b
VS
1382static VOID
1383dumpstate(s, f)
1384struct state *s;
1385FILE *f;
48bf5def
RN
1386{
1387 struct arc *a;
1388
1389 fprintf(f, "%d%s%c", s->no, (s->tmp != NULL) ? "T" : "",
3ca4086b 1390 (s->flag) ? s->flag : '.');
48bf5def
RN
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);
3ca4086b 1398 for (a = s->ins; a != NULL; a = a->inchain) {
48bf5def
RN
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/*
3ca4086b
VS
1406 - dumparcs - dump out-arcs in human-readable form
1407 ^ static VOID dumparcs(struct state *, FILE *);
48bf5def 1408 */
3ca4086b
VS
1409static VOID
1410dumparcs(s, f)
1411struct state *s;
1412FILE *f;
48bf5def 1413{
3ca4086b 1414 int pos;
48bf5def
RN
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/*
3ca4086b
VS
1424 - dumprarcs - dump remaining outarcs, recursively, in reverse order
1425 ^ static int dumprarcs(struct arc *, struct state *, FILE *, int);
48bf5def 1426 */
3ca4086b
VS
1427static int /* resulting print position */
1428dumprarcs(a, s, f, pos)
1429struct arc *a;
1430struct state *s;
1431FILE *f;
1432int pos; /* initial print position */
48bf5def
RN
1433{
1434 if (a->outchain != NULL)
1435 pos = dumprarcs(a->outchain, s, f, pos);
1436 dumparc(a, s, f);
3ca4086b 1437 if (pos == 5) {
48bf5def
RN
1438 fprintf(f, "\n");
1439 pos = 1;
3ca4086b 1440 } else
48bf5def
RN
1441 pos++;
1442 return pos;
1443}
1444
1445/*
3ca4086b
VS
1446 - dumparc - dump one outarc in readable form, including prefixing tab
1447 ^ static VOID dumparc(struct arc *, struct state *, FILE *);
48bf5def 1448 */
3ca4086b
VS
1449static VOID
1450dumparc(a, s, f)
1451struct arc *a;
1452struct state *s;
1453FILE *f;
48bf5def
RN
1454{
1455 struct arc *aa;
1456 struct arcbatch *ab;
1457
1458 fprintf(f, "\t");
3ca4086b
VS
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;
48bf5def
RN
1481 }
1482 if (a->from != s)
1483 fprintf(f, "?%d?", a->from->no);
3ca4086b 1484 for (ab = &a->from->oas; ab != NULL; ab = ab->next) {
48bf5def
RN
1485 for (aa = &ab->a[0]; aa < &ab->a[ABSIZE]; aa++)
1486 if (aa == a)
3ca4086b 1487 break; /* NOTE BREAK OUT */
48bf5def 1488 if (aa < &ab->a[ABSIZE]) /* propagate break */
3ca4086b 1489 break; /* NOTE BREAK OUT */
48bf5def
RN
1490 }
1491 if (ab == NULL)
3ca4086b 1492 fprintf(f, "?!?"); /* not in allocated space */
48bf5def 1493 fprintf(f, "->");
3ca4086b 1494 if (a->to == NULL) {
48bf5def
RN
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)
3ca4086b 1501 break; /* NOTE BREAK OUT */
48bf5def 1502 if (aa == NULL)
3ca4086b 1503 fprintf(f, "?!?"); /* missing from in-chain */
48bf5def 1504}
48bf5def
RN
1505
1506/*
3ca4086b 1507 ^ #endif
48bf5def 1508 */
3ca4086b
VS
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 */
1515static VOID
1516dumpcnfa(cnfa, f)
1517struct cnfa *cnfa;
1518FILE *f;
48bf5def 1519{
3ca4086b
VS
1520#ifdef REG_DEBUG
1521 int st;
48bf5def
RN
1522
1523 fprintf(f, "pre %d, post %d", cnfa->pre, cnfa->post);
1524 if (cnfa->bos[0] != COLORLESS)
3ca4086b 1525 fprintf(f, ", bos [%ld]", (long)cnfa->bos[0]);
48bf5def 1526 if (cnfa->bos[1] != COLORLESS)
3ca4086b 1527 fprintf(f, ", bol [%ld]", (long)cnfa->bos[1]);
48bf5def 1528 if (cnfa->eos[0] != COLORLESS)
3ca4086b 1529 fprintf(f, ", eos [%ld]", (long)cnfa->eos[0]);
48bf5def 1530 if (cnfa->eos[1] != COLORLESS)
3ca4086b
VS
1531 fprintf(f, ", eol [%ld]", (long)cnfa->eos[1]);
1532 if (cnfa->flags&HASLACONS)
48bf5def
RN
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);
48bf5def 1538#endif
3ca4086b 1539}
48bf5def 1540
3ca4086b
VS
1541#ifdef REG_DEBUG /* subordinates of dumpcnfa */
1542/*
1543 ^ #ifdef REG_DEBUG
1544 */
48bf5def
RN
1545
1546/*
3ca4086b
VS
1547 - dumpcstate - dump a compacted-NFA state in human-readable form
1548 ^ static VOID dumpcstate(int, struct carc *, struct cnfa *, FILE *);
48bf5def 1549 */
3ca4086b
VS
1550static VOID
1551dumpcstate(st, ca, cnfa, f)
1552int st;
1553struct carc *ca;
1554struct cnfa *cnfa;
1555FILE *f;
48bf5def 1556{
3ca4086b
VS
1557 int i;
1558 int pos;
48bf5def
RN
1559
1560 fprintf(f, "%d%s", st, (ca[0].co) ? ":" : ".");
1561 pos = 1;
3ca4086b 1562 for (i = 1; ca[i].co != COLORLESS; i++) {
48bf5def 1563 if (ca[i].co < cnfa->ncolors)
3ca4086b 1564 fprintf(f, "\t[%ld]->%d", (long)ca[i].co, ca[i].to);
48bf5def 1565 else
3ca4086b
VS
1566 fprintf(f, "\t:%ld:->%d", (long)ca[i].co-cnfa->ncolors,
1567 ca[i].to);
1568 if (pos == 5) {
48bf5def
RN
1569 fprintf(f, "\n");
1570 pos = 1;
3ca4086b 1571 } else
48bf5def
RN
1572 pos++;
1573 }
1574 if (i == 1 || pos != 1)
1575 fprintf(f, "\n");
1576 fflush(f);
1577}
1578
3ca4086b
VS
1579/*
1580 ^ #endif
1581 */
1582#endif /* ifdef REG_DEBUG */