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

Diff of /projs/trunk/shared_source/c_tcl_base_7_5_w_mods/rege_dfa.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   * DFA routines   * DFA routines
4   * This file is #included by regexec.c.   * This file is #included by regexec.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  /*  /*
35   - longest - longest-preferred matching engine   - longest - longest-preferred matching engine
36   ^ static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *);   ^ static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *);
37   */   */
38  static chr *                    /* endpoint, or NULL */  static chr *                    /* endpoint, or NULL */
39  longest(v, d, start, stop, hitstopp)  longest(v, d, start, stop, hitstopp)
40  struct vars *v;                 /* used only for debug and exec flags */  struct vars *v;                 /* used only for debug and exec flags */
41  struct dfa *d;  struct dfa *d;
42  chr *start;                     /* where the match should start */  chr *start;                     /* where the match should start */
43  chr *stop;                      /* match must end at or before here */  chr *stop;                      /* match must end at or before here */
44  int *hitstopp;                  /* record whether hit v->stop, if non-NULL */  int *hitstopp;                  /* record whether hit v->stop, if non-NULL */
45  {  {
46          chr *cp;          chr *cp;
47          chr *realstop = (stop == v->stop) ? stop : stop + 1;          chr *realstop = (stop == v->stop) ? stop : stop + 1;
48          color co;          color co;
49          struct sset *css;          struct sset *css;
50          struct sset *ss;          struct sset *ss;
51          chr *post;          chr *post;
52          int i;          int i;
53          struct colormap *cm = d->cm;          struct colormap *cm = d->cm;
54    
55          /* initialize */          /* initialize */
56          css = initialize(v, d, start);          css = initialize(v, d, start);
57          cp = start;          cp = start;
58          if (hitstopp != NULL)          if (hitstopp != NULL)
59                  *hitstopp = 0;                  *hitstopp = 0;
60    
61          /* startup */          /* startup */
62          FDEBUG(("+++ startup +++\n"));          FDEBUG(("+++ startup +++\n"));
63          if (cp == v->start) {          if (cp == v->start) {
64                  co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];                  co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];
65                  FDEBUG(("color %ld\n", (long)co));                  FDEBUG(("color %ld\n", (long)co));
66          } else {          } else {
67                  co = GETCOLOR(cm, *(cp - 1));                  co = GETCOLOR(cm, *(cp - 1));
68                  FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));                  FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));
69          }          }
70          css = miss(v, d, css, co, cp, start);          css = miss(v, d, css, co, cp, start);
71          if (css == NULL)          if (css == NULL)
72                  return NULL;                  return NULL;
73          css->lastseen = cp;          css->lastseen = cp;
74    
75          /* main loop */          /* main loop */
76          if (v->eflags&REG_FTRACE)          if (v->eflags&REG_FTRACE)
77                  while (cp < realstop) {                  while (cp < realstop) {
78                          FDEBUG(("+++ at c%d +++\n", css - d->ssets));                          FDEBUG(("+++ at c%d +++\n", css - d->ssets));
79                          co = GETCOLOR(cm, *cp);                          co = GETCOLOR(cm, *cp);
80                          FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));                          FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
81                          ss = css->outs[co];                          ss = css->outs[co];
82                          if (ss == NULL) {                          if (ss == NULL) {
83                                  ss = miss(v, d, css, co, cp+1, start);                                  ss = miss(v, d, css, co, cp+1, start);
84                                  if (ss == NULL)                                  if (ss == NULL)
85                                          break;  /* NOTE BREAK OUT */                                          break;  /* NOTE BREAK OUT */
86                          }                          }
87                          cp++;                          cp++;
88                          ss->lastseen = cp;                          ss->lastseen = cp;
89                          css = ss;                          css = ss;
90                  }                  }
91          else          else
92                  while (cp < realstop) {                  while (cp < realstop) {
93                          co = GETCOLOR(cm, *cp);                          co = GETCOLOR(cm, *cp);
94                          ss = css->outs[co];                          ss = css->outs[co];
95                          if (ss == NULL) {                          if (ss == NULL) {
96                                  ss = miss(v, d, css, co, cp+1, start);                                  ss = miss(v, d, css, co, cp+1, start);
97                                  if (ss == NULL)                                  if (ss == NULL)
98                                          break;  /* NOTE BREAK OUT */                                          break;  /* NOTE BREAK OUT */
99                          }                          }
100                          cp++;                          cp++;
101                          ss->lastseen = cp;                          ss->lastseen = cp;
102                          css = ss;                          css = ss;
103                  }                  }
104    
105          /* shutdown */          /* shutdown */
106          FDEBUG(("+++ shutdown at c%d +++\n", css - d->ssets));          FDEBUG(("+++ shutdown at c%d +++\n", css - d->ssets));
107          if (cp == v->stop && stop == v->stop) {          if (cp == v->stop && stop == v->stop) {
108                  if (hitstopp != NULL)                  if (hitstopp != NULL)
109                          *hitstopp = 1;                          *hitstopp = 1;
110                  co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];                  co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];
111                  FDEBUG(("color %ld\n", (long)co));                  FDEBUG(("color %ld\n", (long)co));
112                  ss = miss(v, d, css, co, cp, start);                  ss = miss(v, d, css, co, cp, start);
113                  /* special case:  match ended at eol? */                  /* special case:  match ended at eol? */
114                  if (ss != NULL && (ss->flags&POSTSTATE))                  if (ss != NULL && (ss->flags&POSTSTATE))
115                          return cp;                          return cp;
116                  else if (ss != NULL)                  else if (ss != NULL)
117                          ss->lastseen = cp;      /* to be tidy */                          ss->lastseen = cp;      /* to be tidy */
118          }          }
119    
120          /* find last match, if any */          /* find last match, if any */
121          post = d->lastpost;          post = d->lastpost;
122          for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)          for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)
123                  if ((ss->flags&POSTSTATE) && post != ss->lastseen &&                  if ((ss->flags&POSTSTATE) && post != ss->lastseen &&
124                                          (post == NULL || post < ss->lastseen))                                          (post == NULL || post < ss->lastseen))
125                          post = ss->lastseen;                          post = ss->lastseen;
126          if (post != NULL)               /* found one */          if (post != NULL)               /* found one */
127                  return post - 1;                  return post - 1;
128    
129          return NULL;          return NULL;
130  }  }
131    
132  /*  /*
133   - shortest - shortest-preferred matching engine   - shortest - shortest-preferred matching engine
134   ^ static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *,   ^ static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *,
135   ^      chr **, int *);   ^      chr **, int *);
136   */   */
137  static chr *                    /* endpoint, or NULL */  static chr *                    /* endpoint, or NULL */
138  shortest(v, d, start, min, max, coldp, hitstopp)  shortest(v, d, start, min, max, coldp, hitstopp)
139  struct vars *v;  struct vars *v;
140  struct dfa *d;  struct dfa *d;
141  chr *start;                     /* where the match should start */  chr *start;                     /* where the match should start */
142  chr *min;                       /* match must end at or after here */  chr *min;                       /* match must end at or after here */
143  chr *max;                       /* match must end at or before here */  chr *max;                       /* match must end at or before here */
144  chr **coldp;                    /* store coldstart pointer here, if nonNULL */  chr **coldp;                    /* store coldstart pointer here, if nonNULL */
145  int *hitstopp;                  /* record whether hit v->stop, if non-NULL */  int *hitstopp;                  /* record whether hit v->stop, if non-NULL */
146  {  {
147          chr *cp;          chr *cp;
148          chr *realmin = (min == v->stop) ? min : min + 1;          chr *realmin = (min == v->stop) ? min : min + 1;
149          chr *realmax = (max == v->stop) ? max : max + 1;          chr *realmax = (max == v->stop) ? max : max + 1;
150          color co;          color co;
151          struct sset *css;          struct sset *css;
152          struct sset *ss;          struct sset *ss;
153          struct colormap *cm = d->cm;          struct colormap *cm = d->cm;
154    
155          /* initialize */          /* initialize */
156          css = initialize(v, d, start);          css = initialize(v, d, start);
157          cp = start;          cp = start;
158          if (hitstopp != NULL)          if (hitstopp != NULL)
159                  *hitstopp = 0;                  *hitstopp = 0;
160    
161          /* startup */          /* startup */
162          FDEBUG(("--- startup ---\n"));          FDEBUG(("--- startup ---\n"));
163          if (cp == v->start) {          if (cp == v->start) {
164                  co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];                  co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];
165                  FDEBUG(("color %ld\n", (long)co));                  FDEBUG(("color %ld\n", (long)co));
166          } else {          } else {
167                  co = GETCOLOR(cm, *(cp - 1));                  co = GETCOLOR(cm, *(cp - 1));
168                  FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));                  FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));
169          }          }
170          css = miss(v, d, css, co, cp, start);          css = miss(v, d, css, co, cp, start);
171          if (css == NULL)          if (css == NULL)
172                  return NULL;                  return NULL;
173          css->lastseen = cp;          css->lastseen = cp;
174          ss = css;          ss = css;
175    
176          /* main loop */          /* main loop */
177          if (v->eflags&REG_FTRACE)          if (v->eflags&REG_FTRACE)
178                  while (cp < realmax) {                  while (cp < realmax) {
179                          FDEBUG(("--- at c%d ---\n", css - d->ssets));                          FDEBUG(("--- at c%d ---\n", css - d->ssets));
180                          co = GETCOLOR(cm, *cp);                          co = GETCOLOR(cm, *cp);
181                          FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));                          FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
182                          ss = css->outs[co];                          ss = css->outs[co];
183                          if (ss == NULL) {                          if (ss == NULL) {
184                                  ss = miss(v, d, css, co, cp+1, start);                                  ss = miss(v, d, css, co, cp+1, start);
185                                  if (ss == NULL)                                  if (ss == NULL)
186                                          break;  /* NOTE BREAK OUT */                                          break;  /* NOTE BREAK OUT */
187                          }                          }
188                          cp++;                          cp++;
189                          ss->lastseen = cp;                          ss->lastseen = cp;
190                          css = ss;                          css = ss;
191                          if ((ss->flags&POSTSTATE) && cp >= realmin)                          if ((ss->flags&POSTSTATE) && cp >= realmin)
192                                  break;          /* NOTE BREAK OUT */                                  break;          /* NOTE BREAK OUT */
193                  }                  }
194          else          else
195                  while (cp < realmax) {                  while (cp < realmax) {
196                          co = GETCOLOR(cm, *cp);                          co = GETCOLOR(cm, *cp);
197                          ss = css->outs[co];                          ss = css->outs[co];
198                          if (ss == NULL) {                          if (ss == NULL) {
199                                  ss = miss(v, d, css, co, cp+1, start);                                  ss = miss(v, d, css, co, cp+1, start);
200                                  if (ss == NULL)                                  if (ss == NULL)
201                                          break;  /* NOTE BREAK OUT */                                          break;  /* NOTE BREAK OUT */
202                          }                          }
203                          cp++;                          cp++;
204                          ss->lastseen = cp;                          ss->lastseen = cp;
205                          css = ss;                          css = ss;
206                          if ((ss->flags&POSTSTATE) && cp >= realmin)                          if ((ss->flags&POSTSTATE) && cp >= realmin)
207                                  break;          /* NOTE BREAK OUT */                                  break;          /* NOTE BREAK OUT */
208                  }                  }
209    
210          if (ss == NULL)          if (ss == NULL)
211                  return NULL;                  return NULL;
212    
213          if (coldp != NULL)      /* report last no-progress state set, if any */          if (coldp != NULL)      /* report last no-progress state set, if any */
214                  *coldp = lastcold(v, d);                  *coldp = lastcold(v, d);
215    
216          if ((ss->flags&POSTSTATE) && cp > min) {          if ((ss->flags&POSTSTATE) && cp > min) {
217                  assert(cp >= realmin);                  assert(cp >= realmin);
218                  cp--;                  cp--;
219          } else if (cp == v->stop && max == v->stop) {          } else if (cp == v->stop && max == v->stop) {
220                  co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];                  co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];
221                  FDEBUG(("color %ld\n", (long)co));                  FDEBUG(("color %ld\n", (long)co));
222                  ss = miss(v, d, css, co, cp, start);                  ss = miss(v, d, css, co, cp, start);
223                  /* match might have ended at eol */                  /* match might have ended at eol */
224                  if ((ss == NULL || !(ss->flags&POSTSTATE)) && hitstopp != NULL)                  if ((ss == NULL || !(ss->flags&POSTSTATE)) && hitstopp != NULL)
225                          *hitstopp = 1;                          *hitstopp = 1;
226          }          }
227    
228          if (ss == NULL || !(ss->flags&POSTSTATE))          if (ss == NULL || !(ss->flags&POSTSTATE))
229                  return NULL;                  return NULL;
230    
231          return cp;          return cp;
232  }  }
233    
234  /*  /*
235   - lastcold - determine last point at which no progress had been made   - lastcold - determine last point at which no progress had been made
236   ^ static chr *lastcold(struct vars *, struct dfa *);   ^ static chr *lastcold(struct vars *, struct dfa *);
237   */   */
238  static chr *                    /* endpoint, or NULL */  static chr *                    /* endpoint, or NULL */
239  lastcold(v, d)  lastcold(v, d)
240  struct vars *v;  struct vars *v;
241  struct dfa *d;  struct dfa *d;
242  {  {
243          struct sset *ss;          struct sset *ss;
244          chr *nopr;          chr *nopr;
245          int i;          int i;
246    
247          nopr = d->lastnopr;          nopr = d->lastnopr;
248          if (nopr == NULL)          if (nopr == NULL)
249                  nopr = v->start;                  nopr = v->start;
250          for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)          for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)
251                  if ((ss->flags&NOPROGRESS) && nopr < ss->lastseen)                  if ((ss->flags&NOPROGRESS) && nopr < ss->lastseen)
252                          nopr = ss->lastseen;                          nopr = ss->lastseen;
253          return nopr;          return nopr;
254  }  }
255    
256  /*  /*
257   - newdfa - set up a fresh DFA   - newdfa - set up a fresh DFA
258   ^ static struct dfa *newdfa(struct vars *, struct cnfa *,   ^ static struct dfa *newdfa(struct vars *, struct cnfa *,
259   ^      struct colormap *, struct smalldfa *);   ^      struct colormap *, struct smalldfa *);
260   */   */
261  static struct dfa *  static struct dfa *
262  newdfa(v, cnfa, cm, small)  newdfa(v, cnfa, cm, small)
263  struct vars *v;  struct vars *v;
264  struct cnfa *cnfa;  struct cnfa *cnfa;
265  struct colormap *cm;  struct colormap *cm;
266  struct smalldfa *small;         /* preallocated space, may be NULL */  struct smalldfa *small;         /* preallocated space, may be NULL */
267  {  {
268          struct dfa *d;          struct dfa *d;
269          size_t nss = cnfa->nstates * 2;          size_t nss = cnfa->nstates * 2;
270          int wordsper = (cnfa->nstates + UBITS - 1) / UBITS;          int wordsper = (cnfa->nstates + UBITS - 1) / UBITS;
271          struct smalldfa *smallwas = small;          struct smalldfa *smallwas = small;
272    
273          assert(cnfa != NULL && cnfa->nstates != 0);          assert(cnfa != NULL && cnfa->nstates != 0);
274    
275          if (nss <= FEWSTATES && cnfa->ncolors <= FEWCOLORS) {          if (nss <= FEWSTATES && cnfa->ncolors <= FEWCOLORS) {
276                  assert(wordsper == 1);                  assert(wordsper == 1);
277                  if (small == NULL) {                  if (small == NULL) {
278                          small = (struct smalldfa *)MALLOC(                          small = (struct smalldfa *)MALLOC(
279                                                  sizeof(struct smalldfa));                                                  sizeof(struct smalldfa));
280                          if (small == NULL) {                          if (small == NULL) {
281                                  ERR(REG_ESPACE);                                  ERR(REG_ESPACE);
282                                  return NULL;                                  return NULL;
283                          }                          }
284                  }                  }
285                  d = &small->dfa;                  d = &small->dfa;
286                  d->ssets = small->ssets;                  d->ssets = small->ssets;
287                  d->statesarea = small->statesarea;                  d->statesarea = small->statesarea;
288                  d->work = &d->statesarea[nss];                  d->work = &d->statesarea[nss];
289                  d->outsarea = small->outsarea;                  d->outsarea = small->outsarea;
290                  d->incarea = small->incarea;                  d->incarea = small->incarea;
291                  d->cptsmalloced = 0;                  d->cptsmalloced = 0;
292                  d->mallocarea = (smallwas == NULL) ? (char *)small : NULL;                  d->mallocarea = (smallwas == NULL) ? (char *)small : NULL;
293          } else {          } else {
294                  d = (struct dfa *)MALLOC(sizeof(struct dfa));                  d = (struct dfa *)MALLOC(sizeof(struct dfa));
295                  if (d == NULL) {                  if (d == NULL) {
296                          ERR(REG_ESPACE);                          ERR(REG_ESPACE);
297                          return NULL;                          return NULL;
298                  }                  }
299                  d->ssets = (struct sset *)MALLOC(nss * sizeof(struct sset));                  d->ssets = (struct sset *)MALLOC(nss * sizeof(struct sset));
300                  d->statesarea = (unsigned *)MALLOC((nss+WORK) * wordsper *                  d->statesarea = (unsigned *)MALLOC((nss+WORK) * wordsper *
301                                                          sizeof(unsigned));                                                          sizeof(unsigned));
302                  d->work = &d->statesarea[nss * wordsper];                  d->work = &d->statesarea[nss * wordsper];
303                  d->outsarea = (struct sset **)MALLOC(nss * cnfa->ncolors *                  d->outsarea = (struct sset **)MALLOC(nss * cnfa->ncolors *
304                                                          sizeof(struct sset *));                                                          sizeof(struct sset *));
305                  d->incarea = (struct arcp *)MALLOC(nss * cnfa->ncolors *                  d->incarea = (struct arcp *)MALLOC(nss * cnfa->ncolors *
306                                                          sizeof(struct arcp));                                                          sizeof(struct arcp));
307                  d->cptsmalloced = 1;                  d->cptsmalloced = 1;
308                  d->mallocarea = (char *)d;                  d->mallocarea = (char *)d;
309                  if (d->ssets == NULL || d->statesarea == NULL ||                  if (d->ssets == NULL || d->statesarea == NULL ||
310                                  d->outsarea == NULL || d->incarea == NULL) {                                  d->outsarea == NULL || d->incarea == NULL) {
311                          freedfa(d);                          freedfa(d);
312                          ERR(REG_ESPACE);                          ERR(REG_ESPACE);
313                          return NULL;                          return NULL;
314                  }                  }
315          }          }
316    
317          d->nssets = (v->eflags&REG_SMALL) ? 7 : nss;          d->nssets = (v->eflags&REG_SMALL) ? 7 : nss;
318          d->nssused = 0;          d->nssused = 0;
319          d->nstates = cnfa->nstates;          d->nstates = cnfa->nstates;
320          d->ncolors = cnfa->ncolors;          d->ncolors = cnfa->ncolors;
321          d->wordsper = wordsper;          d->wordsper = wordsper;
322          d->cnfa = cnfa;          d->cnfa = cnfa;
323          d->cm = cm;          d->cm = cm;
324          d->lastpost = NULL;          d->lastpost = NULL;
325          d->lastnopr = NULL;          d->lastnopr = NULL;
326          d->search = d->ssets;          d->search = d->ssets;
327    
328          /* initialization of sset fields is done as needed */          /* initialization of sset fields is done as needed */
329    
330          return d;          return d;
331  }  }
332    
333  /*  /*
334   - freedfa - free a DFA   - freedfa - free a DFA
335   ^ static VOID freedfa(struct dfa *);   ^ static VOID freedfa(struct dfa *);
336   */   */
337  static VOID  static VOID
338  freedfa(d)  freedfa(d)
339  struct dfa *d;  struct dfa *d;
340  {  {
341          if (d->cptsmalloced) {          if (d->cptsmalloced) {
342                  if (d->ssets != NULL)                  if (d->ssets != NULL)
343                          FREE(d->ssets);                          FREE(d->ssets);
344                  if (d->statesarea != NULL)                  if (d->statesarea != NULL)
345                          FREE(d->statesarea);                          FREE(d->statesarea);
346                  if (d->outsarea != NULL)                  if (d->outsarea != NULL)
347                          FREE(d->outsarea);                          FREE(d->outsarea);
348                  if (d->incarea != NULL)                  if (d->incarea != NULL)
349                          FREE(d->incarea);                          FREE(d->incarea);
350          }          }
351    
352          if (d->mallocarea != NULL)          if (d->mallocarea != NULL)
353                  FREE(d->mallocarea);                  FREE(d->mallocarea);
354  }  }
355    
356  /*  /*
357   - hash - construct a hash code for a bitvector   - hash - construct a hash code for a bitvector
358   * There are probably better ways, but they're more expensive.   * There are probably better ways, but they're more expensive.
359   ^ static unsigned hash(unsigned *, int);   ^ static unsigned hash(unsigned *, int);
360   */   */
361  static unsigned  static unsigned
362  hash(uv, n)  hash(uv, n)
363  unsigned *uv;  unsigned *uv;
364  int n;  int n;
365  {  {
366          int i;          int i;
367          unsigned h;          unsigned h;
368    
369          h = 0;          h = 0;
370          for (i = 0; i < n; i++)          for (i = 0; i < n; i++)
371                  h ^= uv[i];                  h ^= uv[i];
372          return h;          return h;
373  }  }
374    
375  /*  /*
376   - initialize - hand-craft a cache entry for startup, otherwise get ready   - initialize - hand-craft a cache entry for startup, otherwise get ready
377   ^ static struct sset *initialize(struct vars *, struct dfa *, chr *);   ^ static struct sset *initialize(struct vars *, struct dfa *, chr *);
378   */   */
379  static struct sset *  static struct sset *
380  initialize(v, d, start)  initialize(v, d, start)
381  struct vars *v;                 /* used only for debug flags */  struct vars *v;                 /* used only for debug flags */
382  struct dfa *d;  struct dfa *d;
383  chr *start;  chr *start;
384  {  {
385          struct sset *ss;          struct sset *ss;
386          int i;          int i;
387    
388          /* is previous one still there? */          /* is previous one still there? */
389          if (d->nssused > 0 && (d->ssets[0].flags&STARTER))          if (d->nssused > 0 && (d->ssets[0].flags&STARTER))
390                  ss = &d->ssets[0];                  ss = &d->ssets[0];
391          else {                          /* no, must (re)build it */          else {                          /* no, must (re)build it */
392                  ss = getvacant(v, d, start, start);                  ss = getvacant(v, d, start, start);
393                  for (i = 0; i < d->wordsper; i++)                  for (i = 0; i < d->wordsper; i++)
394                          ss->states[i] = 0;                          ss->states[i] = 0;
395                  BSET(ss->states, d->cnfa->pre);                  BSET(ss->states, d->cnfa->pre);
396                  ss->hash = HASH(ss->states, d->wordsper);                  ss->hash = HASH(ss->states, d->wordsper);
397                  assert(d->cnfa->pre != d->cnfa->post);                  assert(d->cnfa->pre != d->cnfa->post);
398                  ss->flags = STARTER|LOCKED|NOPROGRESS;                  ss->flags = STARTER|LOCKED|NOPROGRESS;
399                  /* lastseen dealt with below */                  /* lastseen dealt with below */
400          }          }
401    
402          for (i = 0; i < d->nssused; i++)          for (i = 0; i < d->nssused; i++)
403                  d->ssets[i].lastseen = NULL;                  d->ssets[i].lastseen = NULL;
404          ss->lastseen = start;           /* maybe untrue, but harmless */          ss->lastseen = start;           /* maybe untrue, but harmless */
405          d->lastpost = NULL;          d->lastpost = NULL;
406          d->lastnopr = NULL;          d->lastnopr = NULL;
407          return ss;          return ss;
408  }  }
409    
410  /*  /*
411   - miss - handle a cache miss   - miss - handle a cache miss
412   ^ static struct sset *miss(struct vars *, struct dfa *, struct sset *,   ^ static struct sset *miss(struct vars *, struct dfa *, struct sset *,
413   ^      pcolor, chr *, chr *);   ^      pcolor, chr *, chr *);
414   */   */
415  static struct sset *            /* NULL if goes to empty set */  static struct sset *            /* NULL if goes to empty set */
416  miss(v, d, css, co, cp, start)  miss(v, d, css, co, cp, start)
417  struct vars *v;                 /* used only for debug flags */  struct vars *v;                 /* used only for debug flags */
418  struct dfa *d;  struct dfa *d;
419  struct sset *css;  struct sset *css;
420  pcolor co;  pcolor co;
421  chr *cp;                        /* next chr */  chr *cp;                        /* next chr */
422  chr *start;                     /* where the attempt got started */  chr *start;                     /* where the attempt got started */
423  {  {
424          struct cnfa *cnfa = d->cnfa;          struct cnfa *cnfa = d->cnfa;
425          int i;          int i;
426          unsigned h;          unsigned h;
427          struct carc *ca;          struct carc *ca;
428          struct sset *p;          struct sset *p;
429          int ispost;          int ispost;
430          int noprogress;          int noprogress;
431          int gotstate;          int gotstate;
432          int dolacons;          int dolacons;
433          int sawlacons;          int sawlacons;
434    
435          /* for convenience, we can be called even if it might not be a miss */          /* for convenience, we can be called even if it might not be a miss */
436          if (css->outs[co] != NULL) {          if (css->outs[co] != NULL) {
437                  FDEBUG(("hit\n"));                  FDEBUG(("hit\n"));
438                  return css->outs[co];                  return css->outs[co];
439          }          }
440          FDEBUG(("miss\n"));          FDEBUG(("miss\n"));
441    
442          /* first, what set of states would we end up in? */          /* first, what set of states would we end up in? */
443          for (i = 0; i < d->wordsper; i++)          for (i = 0; i < d->wordsper; i++)
444                  d->work[i] = 0;                  d->work[i] = 0;
445          ispost = 0;          ispost = 0;
446          noprogress = 1;          noprogress = 1;
447          gotstate = 0;          gotstate = 0;
448          for (i = 0; i < d->nstates; i++)          for (i = 0; i < d->nstates; i++)
449                  if (ISBSET(css->states, i))                  if (ISBSET(css->states, i))
450                          for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++)                          for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++)
451                                  if (ca->co == co) {                                  if (ca->co == co) {
452                                          BSET(d->work, ca->to);                                          BSET(d->work, ca->to);
453                                          gotstate = 1;                                          gotstate = 1;
454                                          if (ca->to == cnfa->post)                                          if (ca->to == cnfa->post)
455                                                  ispost = 1;                                                  ispost = 1;
456                                          if (!cnfa->states[ca->to]->co)                                          if (!cnfa->states[ca->to]->co)
457                                                  noprogress = 0;                                                  noprogress = 0;
458                                          FDEBUG(("%d -> %d\n", i, ca->to));                                          FDEBUG(("%d -> %d\n", i, ca->to));
459                                  }                                  }
460          dolacons = (gotstate) ? (cnfa->flags&HASLACONS) : 0;          dolacons = (gotstate) ? (cnfa->flags&HASLACONS) : 0;
461          sawlacons = 0;          sawlacons = 0;
462          while (dolacons) {              /* transitive closure */          while (dolacons) {              /* transitive closure */
463                  dolacons = 0;                  dolacons = 0;
464                  for (i = 0; i < d->nstates; i++)                  for (i = 0; i < d->nstates; i++)
465                          if (ISBSET(d->work, i))                          if (ISBSET(d->work, i))
466                                  for (ca = cnfa->states[i]+1; ca->co != COLORLESS;                                  for (ca = cnfa->states[i]+1; ca->co != COLORLESS;
467                                                                          ca++) {                                                                          ca++) {
468                                          if (ca->co <= cnfa->ncolors)                                          if (ca->co <= cnfa->ncolors)
469                                                  continue; /* NOTE CONTINUE */                                                  continue; /* NOTE CONTINUE */
470                                          sawlacons = 1;                                          sawlacons = 1;
471                                          if (ISBSET(d->work, ca->to))                                          if (ISBSET(d->work, ca->to))
472                                                  continue; /* NOTE CONTINUE */                                                  continue; /* NOTE CONTINUE */
473                                          if (!lacon(v, cnfa, cp, ca->co))                                          if (!lacon(v, cnfa, cp, ca->co))
474                                                  continue; /* NOTE CONTINUE */                                                  continue; /* NOTE CONTINUE */
475                                          BSET(d->work, ca->to);                                          BSET(d->work, ca->to);
476                                          dolacons = 1;                                          dolacons = 1;
477                                          if (ca->to == cnfa->post)                                          if (ca->to == cnfa->post)
478                                                  ispost = 1;                                                  ispost = 1;
479                                          if (!cnfa->states[ca->to]->co)                                          if (!cnfa->states[ca->to]->co)
480                                                  noprogress = 0;                                                  noprogress = 0;
481                                          FDEBUG(("%d :> %d\n", i, ca->to));                                          FDEBUG(("%d :> %d\n", i, ca->to));
482                                  }                                  }
483          }          }
484          if (!gotstate)          if (!gotstate)
485                  return NULL;                  return NULL;
486          h = HASH(d->work, d->wordsper);          h = HASH(d->work, d->wordsper);
487    
488          /* next, is that in the cache? */          /* next, is that in the cache? */
489          for (p = d->ssets, i = d->nssused; i > 0; p++, i--)          for (p = d->ssets, i = d->nssused; i > 0; p++, i--)
490                  if (HIT(h, d->work, p, d->wordsper)) {                  if (HIT(h, d->work, p, d->wordsper)) {
491                          FDEBUG(("cached c%d\n", p - d->ssets));                          FDEBUG(("cached c%d\n", p - d->ssets));
492                          break;                  /* NOTE BREAK OUT */                          break;                  /* NOTE BREAK OUT */
493                  }                  }
494          if (i == 0) {           /* nope, need a new cache entry */          if (i == 0) {           /* nope, need a new cache entry */
495                  p = getvacant(v, d, cp, start);                  p = getvacant(v, d, cp, start);
496                  assert(p != css);                  assert(p != css);
497                  for (i = 0; i < d->wordsper; i++)                  for (i = 0; i < d->wordsper; i++)
498                          p->states[i] = d->work[i];                          p->states[i] = d->work[i];
499                  p->hash = h;                  p->hash = h;
500                  p->flags = (ispost) ? POSTSTATE : 0;                  p->flags = (ispost) ? POSTSTATE : 0;
501                  if (noprogress)                  if (noprogress)
502                          p->flags |= NOPROGRESS;                          p->flags |= NOPROGRESS;
503                  /* lastseen to be dealt with by caller */                  /* lastseen to be dealt with by caller */
504          }          }
505    
506          if (!sawlacons) {               /* lookahead conds. always cache miss */          if (!sawlacons) {               /* lookahead conds. always cache miss */
507                  FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, p - d->ssets));                  FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, p - d->ssets));
508                  css->outs[co] = p;                  css->outs[co] = p;
509                  css->inchain[co] = p->ins;                  css->inchain[co] = p->ins;
510                  p->ins.ss = css;                  p->ins.ss = css;
511                  p->ins.co = (color)co;                  p->ins.co = (color)co;
512          }          }
513          return p;          return p;
514  }  }
515    
516  /*  /*
517   - lacon - lookahead-constraint checker for miss()   - lacon - lookahead-constraint checker for miss()
518   ^ static int lacon(struct vars *, struct cnfa *, chr *, pcolor);   ^ static int lacon(struct vars *, struct cnfa *, chr *, pcolor);
519   */   */
520  static int                      /* predicate:  constraint satisfied? */  static int                      /* predicate:  constraint satisfied? */
521  lacon(v, pcnfa, cp, co)  lacon(v, pcnfa, cp, co)
522  struct vars *v;  struct vars *v;
523  struct cnfa *pcnfa;             /* parent cnfa */  struct cnfa *pcnfa;             /* parent cnfa */
524  chr *cp;  chr *cp;
525  pcolor co;                      /* "color" of the lookahead constraint */  pcolor co;                      /* "color" of the lookahead constraint */
526  {  {
527          int n;          int n;
528          struct subre *sub;          struct subre *sub;
529          struct dfa *d;          struct dfa *d;
530          struct smalldfa sd;          struct smalldfa sd;
531          chr *end;          chr *end;
532    
533          n = co - pcnfa->ncolors;          n = co - pcnfa->ncolors;
534          assert(n < v->g->nlacons && v->g->lacons != NULL);          assert(n < v->g->nlacons && v->g->lacons != NULL);
535          FDEBUG(("=== testing lacon %d\n", n));          FDEBUG(("=== testing lacon %d\n", n));
536          sub = &v->g->lacons[n];          sub = &v->g->lacons[n];
537          d = newdfa(v, &sub->cnfa, &v->g->cmap, &sd);          d = newdfa(v, &sub->cnfa, &v->g->cmap, &sd);
538          if (d == NULL) {          if (d == NULL) {
539                  ERR(REG_ESPACE);                  ERR(REG_ESPACE);
540                  return 0;                  return 0;
541          }          }
542          end = longest(v, d, cp, v->stop, (int *)NULL);          end = longest(v, d, cp, v->stop, (int *)NULL);
543          freedfa(d);          freedfa(d);
544          FDEBUG(("=== lacon %d match %d\n", n, (end != NULL)));          FDEBUG(("=== lacon %d match %d\n", n, (end != NULL)));
545          return (sub->subno) ? (end != NULL) : (end == NULL);          return (sub->subno) ? (end != NULL) : (end == NULL);
546  }  }
547    
548  /*  /*
549   - getvacant - get a vacant state set   - getvacant - get a vacant state set
550   * This routine clears out the inarcs and outarcs, but does not otherwise   * This routine clears out the inarcs and outarcs, but does not otherwise
551   * clear the innards of the state set -- that's up to the caller.   * clear the innards of the state set -- that's up to the caller.
552   ^ static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);   ^ static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);
553   */   */
554  static struct sset *  static struct sset *
555  getvacant(v, d, cp, start)  getvacant(v, d, cp, start)
556  struct vars *v;                 /* used only for debug flags */  struct vars *v;                 /* used only for debug flags */
557  struct dfa *d;  struct dfa *d;
558  chr *cp;  chr *cp;
559  chr *start;  chr *start;
560  {  {
561          int i;          int i;
562          struct sset *ss;          struct sset *ss;
563          struct sset *p;          struct sset *p;
564          struct arcp ap;          struct arcp ap;
565          struct arcp lastap;          struct arcp lastap;
566          color co;          color co;
567    
568          ss = pickss(v, d, cp, start);          ss = pickss(v, d, cp, start);
569          assert(!(ss->flags&LOCKED));          assert(!(ss->flags&LOCKED));
570    
571          /* clear out its inarcs, including self-referential ones */          /* clear out its inarcs, including self-referential ones */
572          ap = ss->ins;          ap = ss->ins;
573          while ((p = ap.ss) != NULL) {          while ((p = ap.ss) != NULL) {
574                  co = ap.co;                  co = ap.co;
575                  FDEBUG(("zapping c%d's %ld outarc\n", p - d->ssets, (long)co));                  FDEBUG(("zapping c%d's %ld outarc\n", p - d->ssets, (long)co));
576                  p->outs[co] = NULL;                  p->outs[co] = NULL;
577                  ap = p->inchain[co];                  ap = p->inchain[co];
578                  p->inchain[co].ss = NULL;       /* paranoia */                  p->inchain[co].ss = NULL;       /* paranoia */
579          }          }
580          ss->ins.ss = NULL;          ss->ins.ss = NULL;
581    
582          /* take it off the inarc chains of the ssets reached by its outarcs */          /* take it off the inarc chains of the ssets reached by its outarcs */
583          for (i = 0; i < d->ncolors; i++) {          for (i = 0; i < d->ncolors; i++) {
584                  p = ss->outs[i];                  p = ss->outs[i];
585                  assert(p != ss);                /* not self-referential */                  assert(p != ss);                /* not self-referential */
586                  if (p == NULL)                  if (p == NULL)
587                          continue;               /* NOTE CONTINUE */                          continue;               /* NOTE CONTINUE */
588                  FDEBUG(("del outarc %d from c%d's in chn\n", i, p - d->ssets));                  FDEBUG(("del outarc %d from c%d's in chn\n", i, p - d->ssets));
589                  if (p->ins.ss == ss && p->ins.co == i)                  if (p->ins.ss == ss && p->ins.co == i)
590                          p->ins = ss->inchain[i];                          p->ins = ss->inchain[i];
591                  else {                  else {
592                          assert(p->ins.ss != NULL);                          assert(p->ins.ss != NULL);
593                          for (ap = p->ins; ap.ss != NULL &&                          for (ap = p->ins; ap.ss != NULL &&
594                                                  !(ap.ss == ss && ap.co == i);                                                  !(ap.ss == ss && ap.co == i);
595                                                  ap = ap.ss->inchain[ap.co])                                                  ap = ap.ss->inchain[ap.co])
596                                  lastap = ap;                                  lastap = ap;
597                          assert(ap.ss != NULL);                          assert(ap.ss != NULL);
598                          lastap.ss->inchain[lastap.co] = ss->inchain[i];                          lastap.ss->inchain[lastap.co] = ss->inchain[i];
599                  }                  }
600                  ss->outs[i] = NULL;                  ss->outs[i] = NULL;
601                  ss->inchain[i].ss = NULL;                  ss->inchain[i].ss = NULL;
602          }          }
603    
604          /* if ss was a success state, may need to remember location */          /* if ss was a success state, may need to remember location */
605          if ((ss->flags&POSTSTATE) && ss->lastseen != d->lastpost &&          if ((ss->flags&POSTSTATE) && ss->lastseen != d->lastpost &&
606                          (d->lastpost == NULL || d->lastpost < ss->lastseen))                          (d->lastpost == NULL || d->lastpost < ss->lastseen))
607                  d->lastpost = ss->lastseen;                  d->lastpost = ss->lastseen;
608    
609          /* likewise for a no-progress state */          /* likewise for a no-progress state */
610          if ((ss->flags&NOPROGRESS) && ss->lastseen != d->lastnopr &&          if ((ss->flags&NOPROGRESS) && ss->lastseen != d->lastnopr &&
611                          (d->lastnopr == NULL || d->lastnopr < ss->lastseen))                          (d->lastnopr == NULL || d->lastnopr < ss->lastseen))
612                  d->lastnopr = ss->lastseen;                  d->lastnopr = ss->lastseen;
613    
614          return ss;          return ss;
615  }  }
616    
617  /*  /*
618   - pickss - pick the next stateset to be used   - pickss - pick the next stateset to be used
619   ^ static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);   ^ static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);
620   */   */
621  static struct sset *  static struct sset *
622  pickss(v, d, cp, start)  pickss(v, d, cp, start)
623  struct vars *v;                 /* used only for debug flags */  struct vars *v;                 /* used only for debug flags */
624  struct dfa *d;  struct dfa *d;
625  chr *cp;  chr *cp;
626  chr *start;  chr *start;
627  {  {
628          int i;          int i;
629          struct sset *ss;          struct sset *ss;
630          struct sset *end;          struct sset *end;
631          chr *ancient;          chr *ancient;
632    
633          /* shortcut for cases where cache isn't full */          /* shortcut for cases where cache isn't full */
634          if (d->nssused < d->nssets) {          if (d->nssused < d->nssets) {
635                  i = d->nssused;                  i = d->nssused;
636                  d->nssused++;                  d->nssused++;
637                  ss = &d->ssets[i];                  ss = &d->ssets[i];
638                  FDEBUG(("new c%d\n", i));                  FDEBUG(("new c%d\n", i));
639                  /* set up innards */                  /* set up innards */
640                  ss->states = &d->statesarea[i * d->wordsper];                  ss->states = &d->statesarea[i * d->wordsper];
641                  ss->flags = 0;                  ss->flags = 0;
642                  ss->ins.ss = NULL;                  ss->ins.ss = NULL;
643                  ss->ins.co = WHITE;             /* give it some value */                  ss->ins.co = WHITE;             /* give it some value */
644                  ss->outs = &d->outsarea[i * d->ncolors];                  ss->outs = &d->outsarea[i * d->ncolors];
645                  ss->inchain = &d->incarea[i * d->ncolors];                  ss->inchain = &d->incarea[i * d->ncolors];
646                  for (i = 0; i < d->ncolors; i++) {                  for (i = 0; i < d->ncolors; i++) {
647                          ss->outs[i] = NULL;                          ss->outs[i] = NULL;
648                          ss->inchain[i].ss = NULL;                          ss->inchain[i].ss = NULL;
649                  }                  }
650                  return ss;                  return ss;
651          }          }
652    
653          /* look for oldest, or old enough anyway */          /* look for oldest, or old enough anyway */
654          if (cp - start > d->nssets*2/3)         /* oldest 33% are expendable */          if (cp - start > d->nssets*2/3)         /* oldest 33% are expendable */
655                  ancient = cp - d->nssets*2/3;                  ancient = cp - d->nssets*2/3;
656          else          else
657                  ancient = start;                  ancient = start;
658          for (ss = d->search, end = &d->ssets[d->nssets]; ss < end; ss++)          for (ss = d->search, end = &d->ssets[d->nssets]; ss < end; ss++)
659                  if ((ss->lastseen == NULL || ss->lastseen < ancient) &&                  if ((ss->lastseen == NULL || ss->lastseen < ancient) &&
660                                                          !(ss->flags&LOCKED)) {                                                          !(ss->flags&LOCKED)) {
661                          d->search = ss + 1;                          d->search = ss + 1;
662                          FDEBUG(("replacing c%d\n", ss - d->ssets));                          FDEBUG(("replacing c%d\n", ss - d->ssets));
663                          return ss;                          return ss;
664                  }                  }
665          for (ss = d->ssets, end = d->search; ss < end; ss++)          for (ss = d->ssets, end = d->search; ss < end; ss++)
666                  if ((ss->lastseen == NULL || ss->lastseen < ancient) &&                  if ((ss->lastseen == NULL || ss->lastseen < ancient) &&
667                                                          !(ss->flags&LOCKED)) {                                                          !(ss->flags&LOCKED)) {
668                          d->search = ss + 1;                          d->search = ss + 1;
669                          FDEBUG(("replacing c%d\n", ss - d->ssets));                          FDEBUG(("replacing c%d\n", ss - d->ssets));
670                          return ss;                          return ss;
671                  }                  }
672    
673          /* nobody's old enough?!? -- something's really wrong */          /* nobody's old enough?!? -- something's really wrong */
674          FDEBUG(("can't find victim to replace!\n"));          FDEBUG(("can't find victim to replace!\n"));
675          assert(NOTREACHED);          assert(NOTREACHED);
676          ERR(REG_ASSERT);          ERR(REG_ASSERT);
677          return d->ssets;          return d->ssets;
678  }  }
679    
680  /* End of rege_dfa.c */  /* End of rege_dfa.c */
Legend:
Removed from v.67  
changed lines
  Added in v.71
dashley@gmail.com
 ViewVC Help
Powered by ViewVC 1.1.25