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

Diff of /projs/dtats/trunk/shared_source/c_tcl_base_7_5_w_mods/regc_nfa.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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