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

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

Parent Directory Parent Directory | Revision Log Revision Log

Revision 71 - (hide annotations) (download)
Sat Nov 5 11:07:06 2016 UTC (7 years, 6 months ago) by dashley
File MIME type: text/plain
File size: 59531 byte(s) 
Set EOL properties appropriately to facilitate simultaneous Linux and Windows development.
1 dashley 71 /* $Header$ */
2     /*
3     * re_*comp and friends - compile REs
4     * This file #includes several others (see the bottom).
5     *
6     * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved.
7     *
8     * Development of this software was funded, in part, by Cray Research Inc.,
9     * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
10     * Corporation, none of whom are responsible for the results. The author
11     * thanks all of them.
12     *
13     * Redistribution and use in source and binary forms -- with or without
14     * modification -- are permitted for any purpose, provided that
15     * redistributions in source form retain this entire copyright notice and
16     * indicate the origin and nature of any modifications.
17     *
18     * I'd appreciate being given credit for this package in the documentation
19     * 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,
22     * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
23     * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
24     * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25     * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26     * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
27     * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
28     * 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
30     * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31     *
32     */
33    
34     #include "regguts.h"
35    
36     /*
37     * forward declarations, up here so forward datatypes etc. are defined early
38     */
39     /* =====^!^===== begin forwards =====^!^===== */
40     /* automatically gathered by fwd; do not hand-edit */
41     /* === regcomp.c === */
42     int compile _ANSI_ARGS_((regex_t *, CONST chr *, size_t, int));
43     static VOID moresubs _ANSI_ARGS_((struct vars *, int));
44     static int freev _ANSI_ARGS_((struct vars *, int));
45     static VOID makesearch _ANSI_ARGS_((struct vars *, struct nfa *));
46     static struct subre *parse _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *));
47     static struct subre *parsebranch _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *, int));
48     static VOID parseqatom _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *, struct subre *));
49     static VOID nonword _ANSI_ARGS_((struct vars *, int, struct state *, struct state *));
50     static VOID word _ANSI_ARGS_((struct vars *, int, struct state *, struct state *));
51     static int scannum _ANSI_ARGS_((struct vars *));
52     static VOID repeat _ANSI_ARGS_((struct vars *, struct state *, struct state *, int, int));
53     static VOID bracket _ANSI_ARGS_((struct vars *, struct state *, struct state *));
54     static VOID cbracket _ANSI_ARGS_((struct vars *, struct state *, struct state *));
55     static VOID brackpart _ANSI_ARGS_((struct vars *, struct state *, struct state *));
56     static chr *scanplain _ANSI_ARGS_((struct vars *));
57     static VOID leaders _ANSI_ARGS_((struct vars *, struct cvec *));
58     static VOID onechr _ANSI_ARGS_((struct vars *, pchr, struct state *, struct state *));
59     static VOID dovec _ANSI_ARGS_((struct vars *, struct cvec *, struct state *, struct state *));
60     static celt nextleader _ANSI_ARGS_((struct vars *, pchr, pchr));
61     static VOID wordchrs _ANSI_ARGS_((struct vars *));
62     static struct subre *subre _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *));
63     static VOID freesubre _ANSI_ARGS_((struct vars *, struct subre *));
64     static VOID freesrnode _ANSI_ARGS_((struct vars *, struct subre *));
65     static VOID optst _ANSI_ARGS_((struct vars *, struct subre *));
66     static int numst _ANSI_ARGS_((struct subre *, int));
67     static VOID markst _ANSI_ARGS_((struct subre *));
68     static VOID cleanst _ANSI_ARGS_((struct vars *));
69     static long nfatree _ANSI_ARGS_((struct vars *, struct subre *, FILE *));
70     static long nfanode _ANSI_ARGS_((struct vars *, struct subre *, FILE *));
71     static int newlacon _ANSI_ARGS_((struct vars *, struct state *, struct state *, int));
72     static VOID freelacons _ANSI_ARGS_((struct subre *, int));
73     static VOID rfree _ANSI_ARGS_((regex_t *));
74     static VOID dump _ANSI_ARGS_((regex_t *, FILE *));
75     static VOID dumpst _ANSI_ARGS_((struct subre *, FILE *, int));
76     static VOID stdump _ANSI_ARGS_((struct subre *, FILE *, int));
77     static char *stid _ANSI_ARGS_((struct subre *, char *, size_t));
78     /* === regc_lex.c === */
79     static VOID lexstart _ANSI_ARGS_((struct vars *));
80     static VOID prefixes _ANSI_ARGS_((struct vars *));
81     static VOID lexnest _ANSI_ARGS_((struct vars *, chr *, chr *));
82     static VOID lexword _ANSI_ARGS_((struct vars *));
83     static int next _ANSI_ARGS_((struct vars *));
84     static int lexescape _ANSI_ARGS_((struct vars *));
85     static chr lexdigits _ANSI_ARGS_((struct vars *, int, int, int));
86     static int brenext _ANSI_ARGS_((struct vars *, pchr));
87     static VOID skip _ANSI_ARGS_((struct vars *));
88     static chr newline _ANSI_ARGS_((NOPARMS));
89     #ifdef REG_DEBUG
90     static chr *ch _ANSI_ARGS_((NOPARMS));
91     #endif
92     static chr chrnamed _ANSI_ARGS_((struct vars *, chr *, chr *, pchr));
93     /* === regc_color.c === */
94     static VOID initcm _ANSI_ARGS_((struct vars *, struct colormap *));
95     static VOID freecm _ANSI_ARGS_((struct colormap *));
96     static VOID cmtreefree _ANSI_ARGS_((struct colormap *, union tree *, int));
97     static color setcolor _ANSI_ARGS_((struct colormap *, pchr, pcolor));
98     static color maxcolor _ANSI_ARGS_((struct colormap *));
99     static color newcolor _ANSI_ARGS_((struct colormap *));
100     static VOID freecolor _ANSI_ARGS_((struct colormap *, pcolor));
101     static color pseudocolor _ANSI_ARGS_((struct colormap *));
102     static color subcolor _ANSI_ARGS_((struct colormap *, pchr c));
103     static color newsub _ANSI_ARGS_((struct colormap *, pcolor));
104     static VOID subrange _ANSI_ARGS_((struct vars *, pchr, pchr, struct state *, struct state *));
105     static VOID subblock _ANSI_ARGS_((struct vars *, pchr, struct state *, struct state *));
106     static VOID okcolors _ANSI_ARGS_((struct nfa *, struct colormap *));
107     static VOID colorchain _ANSI_ARGS_((struct colormap *, struct arc *));
108     static VOID uncolorchain _ANSI_ARGS_((struct colormap *, struct arc *));
109     static int singleton _ANSI_ARGS_((struct colormap *, pchr c));
110     static VOID rainbow _ANSI_ARGS_((struct nfa *, struct colormap *, int, pcolor, struct state *, struct state *));
111     static VOID colorcomplement _ANSI_ARGS_((struct nfa *, struct colormap *, int, struct state *, struct state *, struct state *));
112     #ifdef REG_DEBUG
113     static VOID dumpcolors _ANSI_ARGS_((struct colormap *, FILE *));
114     static VOID fillcheck _ANSI_ARGS_((struct colormap *, union tree *, int, FILE *));
115     static VOID dumpchr _ANSI_ARGS_((pchr, FILE *));
116     #endif
117     /* === regc_nfa.c === */
118     static struct nfa *newnfa _ANSI_ARGS_((struct vars *, struct colormap *, struct nfa *));
119     static VOID freenfa _ANSI_ARGS_((struct nfa *));
120     static struct state *newstate _ANSI_ARGS_((struct nfa *));
121     static struct state *newfstate _ANSI_ARGS_((struct nfa *, int flag));
122     static VOID dropstate _ANSI_ARGS_((struct nfa *, struct state *));
123     static VOID freestate _ANSI_ARGS_((struct nfa *, struct state *));
124     static VOID destroystate _ANSI_ARGS_((struct nfa *, struct state *));
125     static VOID newarc _ANSI_ARGS_((struct nfa *, int, pcolor, struct state *, struct state *));
126     static struct arc *allocarc _ANSI_ARGS_((struct nfa *, struct state *));
127     static VOID freearc _ANSI_ARGS_((struct nfa *, struct arc *));
128     static struct arc *findarc _ANSI_ARGS_((struct state *, int, pcolor));
129     static VOID cparc _ANSI_ARGS_((struct nfa *, struct arc *, struct state *, struct state *));
130     static VOID moveins _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
131     static VOID copyins _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
132     static VOID moveouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
133     static VOID copyouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
134     static VOID cloneouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *, int));
135     static VOID delsub _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
136     static VOID deltraverse _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
137     static VOID dupnfa _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *, struct state *));
138     static VOID duptraverse _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
139     static VOID cleartraverse _ANSI_ARGS_((struct nfa *, struct state *));
140     static VOID specialcolors _ANSI_ARGS_((struct nfa *));
141     static long optimize _ANSI_ARGS_((struct nfa *, FILE *));
142     static VOID pullback _ANSI_ARGS_((struct nfa *, FILE *));
143     static int pull _ANSI_ARGS_((struct nfa *, struct arc *));
144     static VOID pushfwd _ANSI_ARGS_((struct nfa *, FILE *));
145     static int push _ANSI_ARGS_((struct nfa *, struct arc *));
146     #define INCOMPATIBLE 1 /* destroys arc */
147     #define SATISFIED 2 /* constraint satisfied */
148     #define COMPATIBLE 3 /* compatible but not satisfied yet */
149     static int combine _ANSI_ARGS_((struct arc *, struct arc *));
150     static VOID fixempties _ANSI_ARGS_((struct nfa *, FILE *));
151     static int unempty _ANSI_ARGS_((struct nfa *, struct arc *));
152     static VOID cleanup _ANSI_ARGS_((struct nfa *));
153     static VOID markreachable _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *));
154     static VOID markcanreach _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *));
155     static long analyze _ANSI_ARGS_((struct nfa *));
156     static VOID compact _ANSI_ARGS_((struct nfa *, struct cnfa *));
157     static VOID carcsort _ANSI_ARGS_((struct carc *, struct carc *));
158     static VOID freecnfa _ANSI_ARGS_((struct cnfa *));
159     static VOID dumpnfa _ANSI_ARGS_((struct nfa *, FILE *));
160     #ifdef REG_DEBUG
161     static VOID dumpstate _ANSI_ARGS_((struct state *, FILE *));
162     static VOID dumparcs _ANSI_ARGS_((struct state *, FILE *));
163     static int dumprarcs _ANSI_ARGS_((struct arc *, struct state *, FILE *, int));
164     static VOID dumparc _ANSI_ARGS_((struct arc *, struct state *, FILE *));
165     #endif
166     static VOID dumpcnfa _ANSI_ARGS_((struct cnfa *, FILE *));
167     #ifdef REG_DEBUG
168     static VOID dumpcstate _ANSI_ARGS_((int, struct carc *, struct cnfa *, FILE *));
169     #endif
170     /* === regc_cvec.c === */
171     static struct cvec *newcvec _ANSI_ARGS_((int, int, int));
172     static struct cvec *clearcvec _ANSI_ARGS_((struct cvec *));
173     static VOID addchr _ANSI_ARGS_((struct cvec *, pchr));
174     static VOID addrange _ANSI_ARGS_((struct cvec *, pchr, pchr));
175     static VOID addmcce _ANSI_ARGS_((struct cvec *, chr *, chr *));
176     static int haschr _ANSI_ARGS_((struct cvec *, pchr));
177     static struct cvec *getcvec _ANSI_ARGS_((struct vars *, int, int, int));
178     static VOID freecvec _ANSI_ARGS_((struct cvec *));
179     /* === regc_locale.c === */
180     static int nmcces _ANSI_ARGS_((struct vars *));
181     static int nleaders _ANSI_ARGS_((struct vars *));
182     static struct cvec *allmcces _ANSI_ARGS_((struct vars *, struct cvec *));
183     static celt element _ANSI_ARGS_((struct vars *, chr *, chr *));
184     static struct cvec *range _ANSI_ARGS_((struct vars *, celt, celt, int));
185     static int before _ANSI_ARGS_((celt, celt));
186     static struct cvec *eclass _ANSI_ARGS_((struct vars *, celt, int));
187     static struct cvec *cclass _ANSI_ARGS_((struct vars *, chr *, chr *, int));
188     static struct cvec *allcases _ANSI_ARGS_((struct vars *, pchr));
189     static int cmp _ANSI_ARGS_((CONST chr *, CONST chr *, size_t));
190     static int casecmp _ANSI_ARGS_((CONST chr *, CONST chr *, size_t));
191     /* automatically gathered by fwd; do not hand-edit */
192     /* =====^!^===== end forwards =====^!^===== */
193    
194    
195    
196     /* internal variables, bundled for easy passing around */
197     struct vars {
198     regex_t *re;
199     chr *now; /* scan pointer into string */
200     chr *stop; /* end of string */
201     chr *savenow; /* saved now and stop for "subroutine call" */
202     chr *savestop;
203     int err; /* error code (0 if none) */
204     int cflags; /* copy of compile flags */
205     int lasttype; /* type of previous token */
206     int nexttype; /* type of next token */
207     chr nextvalue; /* value (if any) of next token */
208     int lexcon; /* lexical context type (see lex.c) */
209     int nsubexp; /* subexpression count */
210     struct subre **subs; /* subRE pointer vector */
211     size_t nsubs; /* length of vector */
212     struct subre *sub10[10]; /* initial vector, enough for most */
213     struct nfa *nfa; /* the NFA */
214     struct colormap *cm; /* character color map */
215     color nlcolor; /* color of newline */
216     struct state *wordchrs; /* state in nfa holding word-char outarcs */
217     struct subre *tree; /* subexpression tree */
218     struct subre *treechain; /* all tree nodes allocated */
219     struct subre *treefree; /* any free tree nodes */
220     int ntree; /* number of tree nodes */
221     struct cvec *cv; /* interface cvec */
222     struct cvec *cv2; /* utility cvec */
223     struct cvec *mcces; /* collating-element information */
224     # define ISCELEADER(v,c) (v->mcces != NULL && haschr(v->mcces, (c)))
225     struct state *mccepbegin; /* in nfa, start of MCCE prototypes */
226     struct state *mccepend; /* in nfa, end of MCCE prototypes */
227     struct subre *lacons; /* lookahead-constraint vector */
228     int nlacons; /* size of lacons */
229     };
230    
231     /* parsing macros; most know that `v' is the struct vars pointer */
232     #define NEXT() (next(v)) /* advance by one token */
233     #define SEE(t) (v->nexttype == (t)) /* is next token this? */
234     #define EAT(t) (SEE(t) && next(v)) /* if next is this, swallow it */
235     #define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */
236     #define ISERR() VISERR(v)
237     #define VERR(vv,e) ((vv)->nexttype = EOS, ((vv)->err) ? (vv)->err :\
238     ((vv)->err = (e)))
239     #define ERR(e) VERR(v, e) /* record an error */
240     #define NOERR() {if (ISERR()) return;} /* if error seen, return */
241     #define NOERRN() {if (ISERR()) return NULL;} /* NOERR with retval */
242     #define NOERRZ() {if (ISERR()) return 0;} /* NOERR with retval */
243     #define INSIST(c, e) ((c) ? 0 : ERR(e)) /* if condition false, error */
244     #define NOTE(b) (v->re->re_info |= (b)) /* note visible condition */
245     #define EMPTYARC(x, y) newarc(v->nfa, EMPTY, 0, x, y)
246    
247     /* token type codes, some also used as NFA arc types */
248     #define EMPTY 'n' /* no token present */
249     #define EOS 'e' /* end of string */
250     #define PLAIN 'p' /* ordinary character */
251     #define DIGIT 'd' /* digit (in bound) */
252     #define BACKREF 'b' /* back reference */
253     #define COLLEL 'I' /* start of [. */
254     #define ECLASS 'E' /* start of [= */
255     #define CCLASS 'C' /* start of [: */
256     #define END 'X' /* end of [. [= [: */
257     #define RANGE 'R' /* - within [] which might be range delim. */
258     #define LACON 'L' /* lookahead constraint subRE */
259     #define AHEAD 'a' /* color-lookahead arc */
260     #define BEHIND 'r' /* color-lookbehind arc */
261     #define WBDRY 'w' /* word boundary constraint */
262     #define NWBDRY 'W' /* non-word-boundary constraint */
263     #define SBEGIN 'A' /* beginning of string (even if not BOL) */
264     #define SEND 'Z' /* end of string (even if not EOL) */
265     #define PREFER 'P' /* length preference */
266    
267     /* is an arc colored, and hence on a color chain? */
268     #define COLORED(a) ((a)->type == PLAIN || (a)->type == AHEAD || \
269     (a)->type == BEHIND)
270    
271    
272    
273     /* static function list */
274     static struct fns functions = {
275     rfree, /* regfree insides */
276     };
277    
278    
279    
280     /*
281     - compile - compile regular expression
282     ^ int compile(regex_t *, CONST chr *, size_t, int);
283     */
284     int
285     compile(re, string, len, flags)
286     regex_t *re;
287     CONST chr *string;
288     size_t len;
289     int flags;
290     {
291     struct vars var;
292     struct vars *v = &var;
293     struct guts *g;
294     int i;
295     size_t j;
296     FILE *debug = (flags&REG_PROGRESS) ? stdout : (FILE *)NULL;
297     # define CNOERR() { if (ISERR()) return freev(v, v->err); }
298    
299     /* sanity checks */
300    
301     if (re == NULL || string == NULL)
302     return REG_INVARG;
303     if ((flags&REG_QUOTE) &&
304     (flags&(REG_ADVANCED|REG_EXPANDED|REG_NEWLINE)))
305     return REG_INVARG;
306     if (!(flags&REG_EXTENDED) && (flags&REG_ADVF))
307     return REG_INVARG;
308    
309     /* initial setup (after which freev() is callable) */
310     v->re = re;
311     v->now = (chr *)string;
312     v->stop = v->now + len;
313     v->savenow = v->savestop = NULL;
314     v->err = 0;
315     v->cflags = flags;
316     v->nsubexp = 0;
317     v->subs = v->sub10;
318     v->nsubs = 10;
319     for (j = 0; j < v->nsubs; j++)
320     v->subs[j] = NULL;
321     v->nfa = NULL;
322     v->cm = NULL;
323     v->nlcolor = COLORLESS;
324     v->wordchrs = NULL;
325     v->tree = NULL;
326     v->treechain = NULL;
327     v->treefree = NULL;
328     v->cv = NULL;
329     v->cv2 = NULL;
330     v->mcces = NULL;
331     v->lacons = NULL;
332     v->nlacons = 0;
333     re->re_magic = REMAGIC;
334     re->re_info = 0; /* bits get set during parse */
335     re->re_csize = sizeof(chr);
336     re->re_guts = NULL;
337     re->re_fns = VS(&functions);
338    
339     /* more complex setup, malloced things */
340     re->re_guts = VS(MALLOC(sizeof(struct guts)));
341     if (re->re_guts == NULL)
342     return freev(v, REG_ESPACE);
343     g = (struct guts *)re->re_guts;
344     g->tree = NULL;
345     initcm(v, &g->cmap);
346     v->cm = &g->cmap;
347     g->lacons = NULL;
348     g->nlacons = 0;
349     ZAPCNFA(g->search);
350     v->nfa = newnfa(v, v->cm, (struct nfa *)NULL);
351     CNOERR();
352     v->cv = newcvec(100, 20, 10);
353     if (v->cv == NULL)
354     return freev(v, REG_ESPACE);
355     i = nmcces(v);
356     if (i > 0) {
357     v->mcces = newcvec(nleaders(v), 0, i);
358     CNOERR();
359     v->mcces = allmcces(v, v->mcces);
360     leaders(v, v->mcces);
361     addmcce(v->mcces, (chr *)NULL, (chr *)NULL); /* dummy */
362     }
363     CNOERR();
364    
365     /* parsing */
366     lexstart(v); /* also handles prefixes */
367     if ((v->cflags&REG_NLSTOP) || (v->cflags&REG_NLANCH)) {
368     /* assign newline a unique color */
369     v->nlcolor = subcolor(v->cm, newline());
370     okcolors(v->nfa, v->cm);
371     }
372     CNOERR();
373     v->tree = parse(v, EOS, PLAIN, v->nfa->init, v->nfa->final);
374     assert(SEE(EOS)); /* even if error; ISERR() => SEE(EOS) */
375     CNOERR();
376     assert(v->tree != NULL);
377    
378     /* finish setup of nfa and its subre tree */
379     specialcolors(v->nfa);
380     CNOERR();
381     if (debug != NULL) {
382     fprintf(debug, "\n\n\n========= RAW ==========\n");
383     dumpnfa(v->nfa, debug);
384     dumpst(v->tree, debug, 1);
385     }
386     optst(v, v->tree);
387     v->ntree = numst(v->tree, 1);
388     markst(v->tree);
389     cleanst(v);
390     if (debug != NULL) {
391     fprintf(debug, "\n\n\n========= TREE FIXED ==========\n");
392     dumpst(v->tree, debug, 1);
393     }
394    
395     /* build compacted NFAs for tree and lacons */
396     re->re_info |= nfatree(v, v->tree, debug);
397     CNOERR();
398     assert(v->nlacons == 0 || v->lacons != NULL);
399     for (i = 1; i < v->nlacons; i++) {
400     if (debug != NULL)
401     fprintf(debug, "\n\n\n========= LA%d ==========\n", i);
402     nfanode(v, &v->lacons[i], debug);
403     }
404     CNOERR();
405     if (v->tree->flags&SHORTER)
406     NOTE(REG_USHORTEST);
407    
408     /* build compacted NFAs for tree, lacons, fast search */
409     if (debug != NULL)
410     fprintf(debug, "\n\n\n========= SEARCH ==========\n");
411     /* can sacrifice main NFA now, so use it as work area */
412     (DISCARD)optimize(v->nfa, debug);
413     CNOERR();
414     makesearch(v, v->nfa);
415     CNOERR();
416     compact(v->nfa, &g->search);
417     CNOERR();
418    
419     /* looks okay, package it up */
420     re->re_nsub = v->nsubexp;
421     v->re = NULL; /* freev no longer frees re */
422     g->magic = GUTSMAGIC;
423     g->cflags = v->cflags;
424     g->info = re->re_info;
425     g->nsub = re->re_nsub;
426     g->tree = v->tree;
427     v->tree = NULL;
428     g->ntree = v->ntree;
429     g->compare = (v->cflags&REG_ICASE) ? casecmp : cmp;
430     g->lacons = v->lacons;
431     v->lacons = NULL;
432     g->nlacons = v->nlacons;
433    
434     if (flags&REG_DUMP)
435     dump(re, stdout);
436    
437     assert(v->err == 0);
438     return freev(v, 0);
439     }
440    
441     /*
442     - moresubs - enlarge subRE vector
443     ^ static VOID moresubs(struct vars *, int);
444     */
445     static VOID
446     moresubs(v, wanted)
447     struct vars *v;
448     int wanted; /* want enough room for this one */
449     {
450     struct subre **p;
451     size_t n;
452    
453     assert(wanted > 0 && (size_t)wanted >= v->nsubs);
454     n = (size_t)wanted * 3 / 2 + 1;
455     if (v->subs == v->sub10) {
456     p = (struct subre **)MALLOC(n * sizeof(struct subre *));
457     if (p != NULL)
458     memcpy(VS(p), VS(v->subs),
459     v->nsubs * sizeof(struct subre *));
460     } else
461     p = (struct subre **)REALLOC(v->subs, n*sizeof(struct subre *));
462     if (p == NULL) {
463     ERR(REG_ESPACE);
464     return;
465     }
466     v->subs = p;
467     for (p = &v->subs[v->nsubs]; v->nsubs < n; p++, v->nsubs++)
468     *p = NULL;
469     assert(v->nsubs == n);
470     assert((size_t)wanted < v->nsubs);
471     }
472    
473     /*
474     - freev - free vars struct's substructures where necessary
475     * Optionally does error-number setting, and always returns error code
476     * (if any), to make error-handling code terser.
477     ^ static int freev(struct vars *, int);
478     */
479     static int
480     freev(v, err)
481     struct vars *v;
482     int err;
483     {
484     if (v->re != NULL)
485     rfree(v->re);
486     if (v->subs != v->sub10)
487     FREE(v->subs);
488     if (v->nfa != NULL)
489     freenfa(v->nfa);
490     if (v->tree != NULL)
491     freesubre(v, v->tree);
492     if (v->treechain != NULL)
493     cleanst(v);
494     if (v->cv != NULL)
495     freecvec(v->cv);
496     if (v->cv2 != NULL)
497     freecvec(v->cv2);
498     if (v->mcces != NULL)
499     freecvec(v->mcces);
500     if (v->lacons != NULL)
501     freelacons(v->lacons, v->nlacons);
502     ERR(err); /* nop if err==0 */
503    
504     return v->err;
505     }
506    
507     /*
508     - makesearch - turn an NFA into a search NFA (implicit prepend of .*?)
509     * NFA must have been optimize()d already.
510     ^ static VOID makesearch(struct vars *, struct nfa *);
511     */
512     static VOID
513     makesearch(v, nfa)
514     struct vars *v;
515     struct nfa *nfa;
516     {
517     struct arc *a;
518     struct arc *b;
519     struct state *pre = nfa->pre;
520     struct state *s;
521     struct state *s2;
522     struct state *slist;
523    
524     /* no loops are needed if it's anchored */
525     for (a = pre->outs; a != NULL; a = a->outchain) {
526     assert(a->type == PLAIN);
527     if (a->co != nfa->bos[0] && a->co != nfa->bos[1])
528     break;
529     }
530     if (a != NULL) {
531     /* add implicit .* in front */
532     rainbow(nfa, v->cm, PLAIN, COLORLESS, pre, pre);
533    
534     /* and ^* and \A* too -- not always necessary, but harmless */
535     newarc(nfa, PLAIN, nfa->bos[0], pre, pre);
536     newarc(nfa, PLAIN, nfa->bos[1], pre, pre);
537     }
538    
539     /*
540     * Now here's the subtle part. Because many REs have no lookback
541     * constraints, often knowing when you were in the pre state tells
542     * you little; it's the next state(s) that are informative. But
543     * some of them may have other inarcs, i.e. it may be possible to
544     * make actual progress and then return to one of them. We must
545     * de-optimize such cases, splitting each such state into progress
546     * and no-progress states.
547     */
548    
549     /* first, make a list of the states */
550     slist = NULL;
551     for (a = pre->outs; a != NULL; a = a->outchain) {
552     s = a->to;
553     for (b = s->ins; b != NULL; b = b->inchain)
554     if (b->from != pre)
555     break;
556     if (b != NULL) { /* must be split */
557     s->tmp = slist;
558     slist = s;
559     }
560     }
561    
562     /* do the splits */
563     for (s = slist; s != NULL; s = s2) {
564     s2 = newstate(nfa);
565     copyouts(nfa, s, s2);
566     for (a = s->ins; a != NULL; a = b) {
567     b = a->inchain;
568     if (a->from != pre) {
569     cparc(nfa, a, a->from, s2);
570     freearc(nfa, a);
571     }
572     }
573     s2 = s->tmp;
574     s->tmp = NULL; /* clean up while we're at it */
575     }
576     }
577    
578     /*
579     - parse - parse an RE
580     * This is actually just the top level, which parses a bunch of branches
581     * tied together with '|'. They appear in the tree as the left children
582     * of a chain of '|' subres.
583     ^ static struct subre *parse(struct vars *, int, int, struct state *,
584     ^ struct state *);
585     */
586     static struct subre *
587     parse(v, stopper, type, init, final)
588     struct vars *v;
589     int stopper; /* EOS or ')' */
590     int type; /* LACON (lookahead subRE) or PLAIN */
591     struct state *init; /* initial state */
592     struct state *final; /* final state */
593     {
594     struct state *left; /* scaffolding for branch */
595     struct state *right;
596     struct subre *branches; /* top level */
597     struct subre *branch; /* current branch */
598     struct subre *t; /* temporary */
599     int firstbranch; /* is this the first branch? */
600    
601     assert(stopper == ')' || stopper == EOS);
602    
603     branches = subre(v, '|', LONGER, init, final);
604     NOERRN();
605     branch = branches;
606     firstbranch = 1;
607     do { /* a branch */
608     if (!firstbranch) {
609     /* need a place to hang it */
610     branch->right = subre(v, '|', LONGER, init, final);
611     NOERRN();
612     branch = branch->right;
613     }
614     firstbranch = 0;
615     left = newstate(v->nfa);
616     right = newstate(v->nfa);
617     NOERRN();
618     EMPTYARC(init, left);
619     EMPTYARC(right, final);
620     NOERRN();
621     branch->left = parsebranch(v, stopper, type, left, right, 0);
622     NOERRN();
623     branch->flags |= UP(branch->flags | branch->left->flags);
624     if ((branch->flags &~ branches->flags) != 0) /* new flags */
625     for (t = branches; t != branch; t = t->right)
626     t->flags |= branch->flags;
627     } while (EAT('|'));
628     assert(SEE(stopper) || SEE(EOS));
629    
630     if (!SEE(stopper)) {
631     assert(stopper == ')' && SEE(EOS));
632     ERR(REG_EPAREN);
633     }
634    
635     /* optimize out simple cases */
636     if (branch == branches) { /* only one branch */
637     assert(branch->right == NULL);
638     t = branch->left;
639     branch->left = NULL;
640     freesubre(v, branches);
641     branches = t;
642     } else if (!MESSY(branches->flags)) { /* no interesting innards */
643     freesubre(v, branches->left);
644     branches->left = NULL;
645     freesubre(v, branches->right);
646     branches->right = NULL;
647     branches->op = '=';
648     }
649    
650     return branches;
651     }
652    
653     /*
654     - parsebranch - parse one branch of an RE
655     * This mostly manages concatenation, working closely with parseqatom().
656     * Concatenated things are bundled up as much as possible, with separate
657     * ',' nodes introduced only when necessary due to substructure.
658     ^ static struct subre *parsebranch(struct vars *, int, int, struct state *,
659     ^ struct state *, int);
660     */
661     static struct subre *
662     parsebranch(v, stopper, type, left, right, partial)
663     struct vars *v;
664     int stopper; /* EOS or ')' */
665     int type; /* LACON (lookahead subRE) or PLAIN */
666     struct state *left; /* leftmost state */
667     struct state *right; /* rightmost state */
668     int partial; /* is this only part of a branch? */
669     {
670     struct state *lp; /* left end of current construct */
671     int seencontent; /* is there anything in this branch yet? */
672     struct subre *t;
673    
674     lp = left;
675     seencontent = 0;
676     t = subre(v, '=', 0, left, right); /* op '=' is tentative */
677     NOERRN();
678     while (!SEE('|') && !SEE(stopper) && !SEE(EOS)) {
679     if (seencontent) { /* implicit concat operator */
680     lp = newstate(v->nfa);
681     NOERRN();
682     moveins(v->nfa, right, lp);
683     }
684     seencontent = 1;
685    
686     /* NB, recursion in parseqatom() may swallow rest of branch */
687     parseqatom(v, stopper, type, lp, right, t);
688     }
689    
690     if (!seencontent) { /* empty branch */
691     if (!partial)
692     NOTE(REG_UUNSPEC);
693     assert(lp == left);
694     EMPTYARC(left, right);
695     }
696    
697     return t;
698     }
699    
700     /*
701     - parseqatom - parse one quantified atom or constraint of an RE
702     * The bookkeeping near the end cooperates very closely with parsebranch();
703     * in particular, it contains a recursion that can involve parsing the rest
704     * of the branch, making this function's name somewhat inaccurate.
705     ^ static VOID parseqatom(struct vars *, int, int, struct state *,
706     ^ struct state *, struct subre *);
707     */
708     static VOID
709     parseqatom(v, stopper, type, lp, rp, top)
710     struct vars *v;
711     int stopper; /* EOS or ')' */
712     int type; /* LACON (lookahead subRE) or PLAIN */
713     struct state *lp; /* left state to hang it on */
714     struct state *rp; /* right state to hang it on */
715     struct subre *top; /* subtree top */
716     {
717     struct state *s; /* temporaries for new states */
718     struct state *s2;
719     # define ARCV(t, val) newarc(v->nfa, t, val, lp, rp)
720     int m, n;
721     struct subre *atom; /* atom's subtree */
722     struct subre *t;
723     int cap; /* capturing parens? */
724     int pos; /* positive lookahead? */
725     int subno; /* capturing-parens or backref number */
726     int atomtype;
727     int qprefer; /* quantifier short/long preference */
728     int f;
729     struct subre **atomp; /* where the pointer to atom is */
730    
731     /* initial bookkeeping */
732     atom = NULL;
733     assert(lp->nouts == 0); /* must string new code */
734     assert(rp->nins == 0); /* between lp and rp */
735     subno = 0; /* just to shut lint up */
736    
737     /* an atom or constraint... */
738     atomtype = v->nexttype;
739     switch (atomtype) {
740     /* first, constraints, which end by returning */
741     case '^':
742     ARCV('^', 1);
743     if (v->cflags&REG_NLANCH)
744     ARCV(BEHIND, v->nlcolor);
745     NEXT();
746     return;
747     break;
748     case '$':
749     ARCV('$', 1);
750     if (v->cflags&REG_NLANCH)
751     ARCV(AHEAD, v->nlcolor);
752     NEXT();
753     return;
754     break;
755     case SBEGIN:
756     ARCV('^', 1); /* BOL */
757     ARCV('^', 0); /* or BOS */
758     NEXT();
759     return;
760     break;
761     case SEND:
762     ARCV('$', 1); /* EOL */
763     ARCV('$', 0); /* or EOS */
764     NEXT();
765     return;
766     break;
767     case '<':
768     wordchrs(v); /* does NEXT() */
769     s = newstate(v->nfa);
770     NOERR();
771     nonword(v, BEHIND, lp, s);
772     word(v, AHEAD, s, rp);
773     return;
774     break;
775     case '>':
776     wordchrs(v); /* does NEXT() */
777     s = newstate(v->nfa);
778     NOERR();
779     word(v, BEHIND, lp, s);
780     nonword(v, AHEAD, s, rp);
781     return;
782     break;
783     case WBDRY:
784     wordchrs(v); /* does NEXT() */
785     s = newstate(v->nfa);
786     NOERR();
787     nonword(v, BEHIND, lp, s);
788     word(v, AHEAD, s, rp);
789     s = newstate(v->nfa);
790     NOERR();
791     word(v, BEHIND, lp, s);
792     nonword(v, AHEAD, s, rp);
793     return;
794     break;
795     case NWBDRY:
796     wordchrs(v); /* does NEXT() */
797     s = newstate(v->nfa);
798     NOERR();
799     word(v, BEHIND, lp, s);
800     word(v, AHEAD, s, rp);
801     s = newstate(v->nfa);
802     NOERR();
803     nonword(v, BEHIND, lp, s);
804     nonword(v, AHEAD, s, rp);
805     return;
806     break;
807     case LACON: /* lookahead constraint */
808     pos = v->nextvalue;
809     NEXT();
810     s = newstate(v->nfa);
811     s2 = newstate(v->nfa);
812     NOERR();
813     t = parse(v, ')', LACON, s, s2);
814     freesubre(v, t); /* internal structure irrelevant */
815     assert(SEE(')') || ISERR());
816     NEXT();
817     n = newlacon(v, s, s2, pos);
818     NOERR();
819     ARCV(LACON, n);
820     return;
821     break;
822     /* then errors, to get them out of the way */
823     case '*':
824     case '+':
825     case '?':
826     case '{':
827     ERR(REG_BADRPT);
828     return;
829     break;
830     default:
831     ERR(REG_ASSERT);
832     return;
833     break;
834     /* then plain characters, and minor variants on that theme */
835     case ')': /* unbalanced paren */
836     if ((v->cflags&REG_ADVANCED) != REG_EXTENDED) {
837     ERR(REG_EPAREN);
838     return;
839     }
840     /* legal in EREs due to specification botch */
841     NOTE(REG_UPBOTCH);
842     /* fallthrough into case PLAIN */
843     case PLAIN:
844     onechr(v, v->nextvalue, lp, rp);
845     okcolors(v->nfa, v->cm);
846     NOERR();
847     NEXT();
848     break;
849     case '[':
850     if (v->nextvalue == 1)
851     bracket(v, lp, rp);
852     else
853     cbracket(v, lp, rp);
854     assert(SEE(']') || ISERR());
855     NEXT();
856     break;
857     case '.':
858     rainbow(v->nfa, v->cm, PLAIN,
859     (v->cflags&REG_NLSTOP) ? v->nlcolor : COLORLESS,
860     lp, rp);
861     NEXT();
862     break;
863     /* and finally the ugly stuff */
864     case '(': /* value flags as capturing or non */
865     cap = (type == LACON) ? 0 : v->nextvalue;
866     if (cap) {
867     v->nsubexp++;
868     subno = v->nsubexp;
869     if ((size_t)subno >= v->nsubs)
870     moresubs(v, subno);
871     assert((size_t)subno < v->nsubs);
872     } else
873     atomtype = PLAIN; /* something that's not '(' */
874     NEXT();
875     /* need new endpoints because tree will contain pointers */
876     s = newstate(v->nfa);
877     s2 = newstate(v->nfa);
878     NOERR();
879     EMPTYARC(lp, s);
880     EMPTYARC(s2, rp);
881     NOERR();
882     atom = parse(v, ')', PLAIN, s, s2);
883     assert(SEE(')') || ISERR());
884     NEXT();
885     NOERR();
886     if (cap) {
887     v->subs[subno] = atom;
888     t = subre(v, '(', atom->flags|CAP, lp, rp);
889     NOERR();
890     t->subno = subno;
891     t->left = atom;
892     atom = t;
893     }
894     /* postpone everything else pending possible {0} */
895     break;
896     case BACKREF: /* the Feature From The Black Lagoon */
897     INSIST(type != LACON, REG_ESUBREG);
898     INSIST(v->nextvalue < v->nsubs, REG_ESUBREG);
899     INSIST(v->subs[v->nextvalue] != NULL, REG_ESUBREG);
900     NOERR();
901     assert(v->nextvalue > 0);
902     atom = subre(v, 'b', BACKR, lp, rp);
903     subno = v->nextvalue;
904     atom->subno = subno;
905     EMPTYARC(lp, rp); /* temporarily, so there's something */
906     NEXT();
907     break;
908     }
909    
910     /* ...and an atom may be followed by a quantifier */
911     switch (v->nexttype) {
912     case '*':
913     m = 0;
914     n = INFINITY;
915     qprefer = (v->nextvalue) ? LONGER : SHORTER;
916     NEXT();
917     break;
918     case '+':
919     m = 1;
920     n = INFINITY;
921     qprefer = (v->nextvalue) ? LONGER : SHORTER;
922     NEXT();
923     break;
924     case '?':
925     m = 0;
926     n = 1;
927     qprefer = (v->nextvalue) ? LONGER : SHORTER;
928     NEXT();
929     break;
930     case '{':
931     NEXT();
932     m = scannum(v);
933     if (EAT(',')) {
934     if (SEE(DIGIT))
935     n = scannum(v);
936     else
937     n = INFINITY;
938     if (m > n) {
939     ERR(REG_BADBR);
940     return;
941     }
942     /* {m,n} exercises preference, even if it's {m,m} */
943     qprefer = (v->nextvalue) ? LONGER : SHORTER;
944     } else {
945     n = m;
946     /* {m} passes operand's preference through */
947     qprefer = 0;
948     }
949     if (!SEE('}')) { /* catches errors too */
950     ERR(REG_BADBR);
951     return;
952     }
953     NEXT();
954     break;
955     default: /* no quantifier */
956     m = n = 1;
957     qprefer = 0;
958     break;
959     }
960    
961     /* annoying special case: {0} or {0,0} cancels everything */
962     if (m == 0 && n == 0) {
963     if (atom != NULL)
964     freesubre(v, atom);
965     if (atomtype == '(')
966     v->subs[subno] = NULL;
967     delsub(v->nfa, lp, rp);
968     EMPTYARC(lp, rp);
969     return;
970     }
971    
972     /* if not a messy case, avoid hard part */
973     assert(!MESSY(top->flags));
974     f = top->flags | qprefer | ((atom != NULL) ? atom->flags : 0);
975     if (atomtype != '(' && atomtype != BACKREF && !MESSY(UP(f))) {
976     if (!(m == 1 && n == 1))
977     repeat(v, lp, rp, m, n);
978     if (atom != NULL)
979     freesubre(v, atom);
980     top->flags = f;
981     return;
982     }
983    
984     /*
985     * hard part: something messy
986     * That is, capturing parens, back reference, short/long clash, or
987     * an atom with substructure containing one of those.
988     */
989    
990     /* now we'll need a subre for the contents even if they're boring */
991     if (atom == NULL) {
992     atom = subre(v, '=', 0, lp, rp);
993     NOERR();
994     }
995    
996     /*
997     * prepare a general-purpose state skeleton
998     *
999     * ---> [s] ---prefix---> [begin] ---atom---> [end] ----rest---> [rp]
1000     * / /
1001     * [lp] ----> [s2] ----bypass---------------------
1002     *
1003     * where bypass is an empty, and prefix is some repetitions of atom
1004     */
1005     s = newstate(v->nfa); /* first, new endpoints for the atom */
1006     s2 = newstate(v->nfa);
1007     NOERR();
1008     moveouts(v->nfa, lp, s);
1009     moveins(v->nfa, rp, s2);
1010     NOERR();
1011     atom->begin = s;
1012     atom->end = s2;
1013     s = newstate(v->nfa); /* and spots for prefix and bypass */
1014     s2 = newstate(v->nfa);
1015     NOERR();
1016     EMPTYARC(lp, s);
1017     EMPTYARC(lp, s2);
1018     NOERR();
1019    
1020     /* break remaining subRE into x{...} and what follows */
1021     t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp);
1022     t->left = atom;
1023     atomp = &t->left;
1024     /* here we should recurse... but we must postpone that to the end */
1025    
1026     /* split top into prefix and remaining */
1027     assert(top->op == '=' && top->left == NULL && top->right == NULL);
1028     top->left = subre(v, '=', top->flags, top->begin, lp);
1029     top->op = '.';
1030     top->right = t;
1031    
1032     /* if it's a backref, now is the time to replicate the subNFA */
1033     if (atomtype == BACKREF) {
1034     assert(atom->begin->nouts == 1); /* just the EMPTY */
1035     delsub(v->nfa, atom->begin, atom->end);
1036     assert(v->subs[subno] != NULL);
1037     /* and here's why the recursion got postponed: it must */
1038     /* wait until the skeleton is filled in, because it may */
1039     /* hit a backref that wants to copy the filled-in skeleton */
1040     dupnfa(v->nfa, v->subs[subno]->begin, v->subs[subno]->end,
1041     atom->begin, atom->end);
1042     NOERR();
1043     }
1044    
1045     /* it's quantifier time; first, turn x{0,...} into x{1,...}|empty */
1046     if (m == 0) {
1047     EMPTYARC(s2, atom->end); /* the bypass */
1048     assert(PREF(qprefer) != 0);
1049     f = COMBINE(qprefer, atom->flags);
1050     t = subre(v, '|', f, lp, atom->end);
1051     NOERR();
1052     t->left = atom;
1053     t->right = subre(v, '|', PREF(f), s2, atom->end);
1054     NOERR();
1055     t->right->left = subre(v, '=', 0, s2, atom->end);
1056     NOERR();
1057     *atomp = t;
1058     atomp = &t->left;
1059     m = 1;
1060     }
1061    
1062     /* deal with the rest of the quantifier */
1063     if (atomtype == BACKREF) {
1064     /* special case: backrefs have internal quantifiers */
1065     EMPTYARC(s, atom->begin); /* empty prefix */
1066     /* just stuff everything into atom */
1067     repeat(v, atom->begin, atom->end, m, n);
1068     atom->min = (short)m;
1069     atom->max = (short)n;
1070     atom->flags |= COMBINE(qprefer, atom->flags);
1071     } else if (m == 1 && n == 1) {
1072     /* no/vacuous quantifier: done */
1073     EMPTYARC(s, atom->begin); /* empty prefix */
1074     } else {
1075     /* turn x{m,n} into x{m-1,n-1}x, with capturing */
1076     /* parens in only second x */
1077     dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin);
1078     assert(m >= 1 && m != INFINITY && n >= 1);
1079     repeat(v, s, atom->begin, m-1, (n == INFINITY) ? n : n-1);
1080     f = COMBINE(qprefer, atom->flags);
1081     t = subre(v, '.', f, s, atom->end); /* prefix and atom */
1082     NOERR();
1083     t->left = subre(v, '=', PREF(f), s, atom->begin);
1084     NOERR();
1085     t->right = atom;
1086     *atomp = t;
1087     }
1088    
1089     /* and finally, look after that postponed recursion */
1090     t = top->right;
1091     if (!(SEE('|') || SEE(stopper) || SEE(EOS)))
1092     t->right = parsebranch(v, stopper, type, atom->end, rp, 1);
1093     else {
1094     EMPTYARC(atom->end, rp);
1095     t->right = subre(v, '=', 0, atom->end, rp);
1096     }
1097     assert(SEE('|') || SEE(stopper) || SEE(EOS));
1098     t->flags |= COMBINE(t->flags, t->right->flags);
1099     top->flags |= COMBINE(top->flags, t->flags);
1100     }
1101    
1102     /*
1103     - nonword - generate arcs for non-word-character ahead or behind
1104     ^ static VOID nonword(struct vars *, int, struct state *, struct state *);
1105     */
1106     static VOID
1107     nonword(v, dir, lp, rp)
1108     struct vars *v;
1109     int dir; /* AHEAD or BEHIND */
1110     struct state *lp;
1111     struct state *rp;
1112     {
1113     int anchor = (dir == AHEAD) ? '$' : '^';
1114    
1115     assert(dir == AHEAD || dir == BEHIND);
1116     newarc(v->nfa, anchor, 1, lp, rp);
1117     newarc(v->nfa, anchor, 0, lp, rp);
1118     colorcomplement(v->nfa, v->cm, dir, v->wordchrs, lp, rp);
1119     /* (no need for special attention to \n) */
1120     }
1121    
1122     /*
1123     - word - generate arcs for word character ahead or behind
1124     ^ static VOID word(struct vars *, int, struct state *, struct state *);
1125     */
1126     static VOID
1127     word(v, dir, lp, rp)
1128     struct vars *v;
1129     int dir; /* AHEAD or BEHIND */
1130     struct state *lp;
1131     struct state *rp;
1132     {
1133     assert(dir == AHEAD || dir == BEHIND);
1134     cloneouts(v->nfa, v->wordchrs, lp, rp, dir);
1135     /* (no need for special attention to \n) */
1136     }
1137    
1138     /*
1139     - scannum - scan a number
1140     ^ static int scannum(struct vars *);
1141     */
1142     static int /* value, <= DUPMAX */
1143     scannum(v)
1144     struct vars *v;
1145     {
1146     int n = 0;
1147    
1148     while (SEE(DIGIT) && n < DUPMAX) {
1149     n = n*10 + v->nextvalue;
1150     NEXT();
1151     }
1152     if (SEE(DIGIT) || n > DUPMAX) {
1153     ERR(REG_BADBR);
1154     return 0;
1155     }
1156     return n;
1157     }
1158    
1159     /*
1160     - repeat - replicate subNFA for quantifiers
1161     * The duplication sequences used here are chosen carefully so that any
1162     * pointers starting out pointing into the subexpression end up pointing into
1163     * the last occurrence. (Note that it may not be strung between the same
1164     * left and right end states, however!) This used to be important for the
1165     * subRE tree, although the important bits are now handled by the in-line
1166     * code in parse(), and when this is called, it doesn't matter any more.
1167     ^ static VOID repeat(struct vars *, struct state *, struct state *, int, int);
1168     */
1169     static VOID
1170     repeat(v, lp, rp, m, n)
1171     struct vars *v;
1172     struct state *lp;
1173     struct state *rp;
1174     int m;
1175     int n;
1176     {
1177     # define SOME 2
1178     # define INF 3
1179     # define PAIR(x, y) ((x)*4 + (y))
1180     # define REDUCE(x) ( ((x) == INFINITY) ? INF : (((x) > 1) ? SOME : (x)) )
1181     CONST int rm = REDUCE(m);
1182     CONST int rn = REDUCE(n);
1183     struct state *s;
1184     struct state *s2;
1185    
1186     switch (PAIR(rm, rn)) {
1187     case PAIR(0, 0): /* empty string */
1188     delsub(v->nfa, lp, rp);
1189     EMPTYARC(lp, rp);
1190     break;
1191     case PAIR(0, 1): /* do as x| */
1192     EMPTYARC(lp, rp);
1193     break;
1194     case PAIR(0, SOME): /* do as x{1,n}| */
1195     repeat(v, lp, rp, 1, n);
1196     NOERR();
1197     EMPTYARC(lp, rp);
1198     break;
1199     case PAIR(0, INF): /* loop x around */
1200     s = newstate(v->nfa);
1201     NOERR();
1202     moveouts(v->nfa, lp, s);
1203     moveins(v->nfa, rp, s);
1204     EMPTYARC(lp, s);
1205     EMPTYARC(s, rp);
1206     break;
1207     case PAIR(1, 1): /* no action required */
1208     break;
1209     case PAIR(1, SOME): /* do as x{0,n-1}x = (x{1,n-1}|)x */
1210     s = newstate(v->nfa);
1211     NOERR();
1212     moveouts(v->nfa, lp, s);
1213     dupnfa(v->nfa, s, rp, lp, s);
1214     NOERR();
1215     repeat(v, lp, s, 1, n-1);
1216     NOERR();
1217     EMPTYARC(lp, s);
1218     break;
1219     case PAIR(1, INF): /* add loopback arc */
1220     s = newstate(v->nfa);
1221     s2 = newstate(v->nfa);
1222     NOERR();
1223     moveouts(v->nfa, lp, s);
1224     moveins(v->nfa, rp, s2);
1225     EMPTYARC(lp, s);
1226     EMPTYARC(s2, rp);
1227     EMPTYARC(s2, s);
1228     break;
1229     case PAIR(SOME, SOME): /* do as x{m-1,n-1}x */
1230     s = newstate(v->nfa);
1231     NOERR();
1232     moveouts(v->nfa, lp, s);
1233     dupnfa(v->nfa, s, rp, lp, s);
1234     NOERR();
1235     repeat(v, lp, s, m-1, n-1);
1236     break;
1237     case PAIR(SOME, INF): /* do as x{m-1,}x */
1238     s = newstate(v->nfa);
1239     NOERR();
1240     moveouts(v->nfa, lp, s);
1241     dupnfa(v->nfa, s, rp, lp, s);
1242     NOERR();
1243     repeat(v, lp, s, m-1, n);
1244     break;
1245     default:
1246     ERR(REG_ASSERT);
1247     break;
1248     }
1249     }
1250    
1251     /*
1252     - bracket - handle non-complemented bracket expression
1253     * Also called from cbracket for complemented bracket expressions.
1254     ^ static VOID bracket(struct vars *, struct state *, struct state *);
1255     */
1256     static VOID
1257     bracket(v, lp, rp)
1258     struct vars *v;
1259     struct state *lp;
1260     struct state *rp;
1261     {
1262     assert(SEE('['));
1263     NEXT();
1264     while (!SEE(']') && !SEE(EOS))
1265     brackpart(v, lp, rp);
1266     assert(SEE(']') || ISERR());
1267     okcolors(v->nfa, v->cm);
1268     }
1269    
1270     /*
1271     - cbracket - handle complemented bracket expression
1272     * We do it by calling bracket() with dummy endpoints, and then complementing
1273     * the result. The alternative would be to invoke rainbow(), and then delete
1274     * arcs as the b.e. is seen... but that gets messy.
1275     ^ static VOID cbracket(struct vars *, struct state *, struct state *);
1276     */
1277     static VOID
1278     cbracket(v, lp, rp)
1279     struct vars *v;
1280     struct state *lp;
1281     struct state *rp;
1282     {
1283     struct state *left = newstate(v->nfa);
1284     struct state *right = newstate(v->nfa);
1285     struct state *s;
1286     struct arc *a; /* arc from lp */
1287     struct arc *ba; /* arc from left, from bracket() */
1288     struct arc *pa; /* MCCE-prototype arc */
1289     color co;
1290     chr *p;
1291     int i;
1292    
1293     NOERR();
1294     bracket(v, left, right);
1295     if (v->cflags&REG_NLSTOP)
1296     newarc(v->nfa, PLAIN, v->nlcolor, left, right);
1297     NOERR();
1298    
1299     assert(lp->nouts == 0); /* all outarcs will be ours */
1300    
1301     /* easy part of complementing */
1302     colorcomplement(v->nfa, v->cm, PLAIN, left, lp, rp);
1303     NOERR();
1304     if (v->mcces == NULL) { /* no MCCEs -- we're done */
1305     dropstate(v->nfa, left);
1306     assert(right->nins == 0);
1307     freestate(v->nfa, right);
1308     return;
1309     }
1310    
1311     /* but complementing gets messy in the presence of MCCEs... */
1312     NOTE(REG_ULOCALE);
1313     for (p = v->mcces->chrs, i = v->mcces->nchrs; i > 0; p++, i--) {
1314     co = GETCOLOR(v->cm, *p);
1315     a = findarc(lp, PLAIN, co);
1316     ba = findarc(left, PLAIN, co);
1317     if (ba == NULL) {
1318     assert(a != NULL);
1319     freearc(v->nfa, a);
1320     } else {
1321     assert(a == NULL);
1322     }
1323     s = newstate(v->nfa);
1324     NOERR();
1325     newarc(v->nfa, PLAIN, co, lp, s);
1326     NOERR();
1327     pa = findarc(v->mccepbegin, PLAIN, co);
1328     assert(pa != NULL);
1329     if (ba == NULL) { /* easy case, need all of them */
1330     cloneouts(v->nfa, pa->to, s, rp, PLAIN);
1331     newarc(v->nfa, '$', 1, s, rp);
1332     newarc(v->nfa, '$', 0, s, rp);
1333     colorcomplement(v->nfa, v->cm, AHEAD, pa->to, s, rp);
1334     } else { /* must be selective */
1335     if (findarc(ba->to, '$', 1) == NULL) {
1336     newarc(v->nfa, '$', 1, s, rp);
1337     newarc(v->nfa, '$', 0, s, rp);
1338     colorcomplement(v->nfa, v->cm, AHEAD, pa->to,
1339     s, rp);
1340     }
1341     for (pa = pa->to->outs; pa != NULL; pa = pa->outchain)
1342     if (findarc(ba->to, PLAIN, pa->co) == NULL)
1343     newarc(v->nfa, PLAIN, pa->co, s, rp);
1344     if (s->nouts == 0) /* limit of selectivity: none */
1345     dropstate(v->nfa, s); /* frees arc too */
1346     }
1347     NOERR();
1348     }
1349    
1350     delsub(v->nfa, left, right);
1351     assert(left->nouts == 0);
1352     freestate(v->nfa, left);
1353     assert(right->nins == 0);
1354     freestate(v->nfa, right);
1355     }
1356    
1357     /*
1358     - brackpart - handle one item (or range) within a bracket expression
1359     ^ static VOID brackpart(struct vars *, struct state *, struct state *);
1360     */
1361     static VOID
1362     brackpart(v, lp, rp)
1363     struct vars *v;
1364     struct state *lp;
1365     struct state *rp;
1366     {
1367     celt startc;
1368     celt endc;
1369     struct cvec *cv;
1370     chr *startp;
1371     chr *endp;
1372     chr c[1];
1373    
1374     /* parse something, get rid of special cases, take shortcuts */
1375     switch (v->nexttype) {
1376     case RANGE: /* a-b-c or other botch */
1377     ERR(REG_ERANGE);
1378     return;
1379     break;
1380     case PLAIN:
1381     c[0] = v->nextvalue;
1382     NEXT();
1383     /* shortcut for ordinary chr (not range, not MCCE leader) */
1384     if (!SEE(RANGE) && !ISCELEADER(v, c[0])) {
1385     onechr(v, c[0], lp, rp);
1386     return;
1387     }
1388     startc = element(v, c, c+1);
1389     NOERR();
1390     break;
1391     case COLLEL:
1392     startp = v->now;
1393     endp = scanplain(v);
1394     INSIST(startp < endp, REG_ECOLLATE);
1395     NOERR();
1396     startc = element(v, startp, endp);
1397     NOERR();
1398     break;
1399     case ECLASS:
1400     startp = v->now;
1401     endp = scanplain(v);
1402     INSIST(startp < endp, REG_ECOLLATE);
1403     NOERR();
1404     startc = element(v, startp, endp);
1405     NOERR();
1406     cv = eclass(v, startc, (v->cflags&REG_ICASE));
1407     NOERR();
1408     dovec(v, cv, lp, rp);
1409     return;
1410     break;
1411     case CCLASS:
1412     startp = v->now;
1413     endp = scanplain(v);
1414     INSIST(startp < endp, REG_ECTYPE);
1415     NOERR();
1416     cv = cclass(v, startp, endp, (v->cflags&REG_ICASE));
1417     NOERR();
1418     dovec(v, cv, lp, rp);
1419     return;
1420     break;
1421     default:
1422     ERR(REG_ASSERT);
1423     return;
1424     break;
1425     }
1426    
1427     if (SEE(RANGE)) {
1428     NEXT();
1429     switch (v->nexttype) {
1430     case PLAIN:
1431     case RANGE:
1432     c[0] = v->nextvalue;
1433     NEXT();
1434     endc = element(v, c, c+1);
1435     NOERR();
1436     break;
1437     case COLLEL:
1438     startp = v->now;
1439     endp = scanplain(v);
1440     INSIST(startp < endp, REG_ECOLLATE);
1441     NOERR();
1442     endc = element(v, startp, endp);
1443     NOERR();
1444     break;
1445     default:
1446     ERR(REG_ERANGE);
1447     return;
1448     break;
1449     }
1450     } else
1451     endc = startc;
1452    
1453     /*
1454     * Ranges are unportable. Actually, standard C does
1455     * guarantee that digits are contiguous, but making
1456     * that an exception is just too complicated.
1457     */
1458     if (startc != endc)
1459     NOTE(REG_UUNPORT);
1460     cv = range(v, startc, endc, (v->cflags&REG_ICASE));
1461     NOERR();
1462     dovec(v, cv, lp, rp);
1463     }
1464    
1465     /*
1466     - scanplain - scan PLAIN contents of [. etc.
1467     * Certain bits of trickery in lex.c know that this code does not try
1468     * to look past the final bracket of the [. etc.
1469     ^ static chr *scanplain(struct vars *);
1470     */
1471     static chr * /* just after end of sequence */
1472     scanplain(v)
1473     struct vars *v;
1474     {
1475     chr *endp;
1476    
1477     assert(SEE(COLLEL) || SEE(ECLASS) || SEE(CCLASS));
1478     NEXT();
1479    
1480     endp = v->now;
1481     while (SEE(PLAIN)) {
1482     endp = v->now;
1483     NEXT();
1484     }
1485    
1486     assert(SEE(END) || ISERR());
1487     NEXT();
1488    
1489     return endp;
1490     }
1491    
1492     /*
1493     - leaders - process a cvec of collating elements to also include leaders
1494     * Also gives all characters involved their own colors, which is almost
1495     * certainly necessary, and sets up little disconnected subNFA.
1496     ^ static VOID leaders(struct vars *, struct cvec *);
1497     */
1498     static VOID
1499     leaders(v, cv)
1500     struct vars *v;
1501     struct cvec *cv;
1502     {
1503     int mcce;
1504     chr *p;
1505     chr leader;
1506     struct state *s;
1507     struct arc *a;
1508    
1509     v->mccepbegin = newstate(v->nfa);
1510     v->mccepend = newstate(v->nfa);
1511     NOERR();
1512    
1513     for (mcce = 0; mcce < cv->nmcces; mcce++) {
1514     p = cv->mcces[mcce];
1515     leader = *p;
1516     if (!haschr(cv, leader)) {
1517     addchr(cv, leader);
1518     s = newstate(v->nfa);
1519     newarc(v->nfa, PLAIN, subcolor(v->cm, leader),
1520     v->mccepbegin, s);
1521     okcolors(v->nfa, v->cm);
1522     } else {
1523     a = findarc(v->mccepbegin, PLAIN,
1524     GETCOLOR(v->cm, leader));
1525     assert(a != NULL);
1526     s = a->to;
1527     assert(s != v->mccepend);
1528     }
1529     p++;
1530     assert(*p != 0 && *(p+1) == 0); /* only 2-char MCCEs for now */
1531     newarc(v->nfa, PLAIN, subcolor(v->cm, *p), s, v->mccepend);
1532     okcolors(v->nfa, v->cm);
1533     }
1534     }
1535    
1536     /*
1537     - onechr - fill in arcs for a plain character, and possible case complements
1538     * This is mostly a shortcut for efficient handling of the common case.
1539     ^ static VOID onechr(struct vars *, pchr, struct state *, struct state *);
1540     */
1541     static VOID
1542     onechr(v, c, lp, rp)
1543     struct vars *v;
1544     pchr c;
1545     struct state *lp;
1546     struct state *rp;
1547     {
1548     if (!(v->cflags&REG_ICASE)) {
1549     newarc(v->nfa, PLAIN, subcolor(v->cm, c), lp, rp);
1550     return;
1551     }
1552    
1553     /* rats, need general case anyway... */
1554     dovec(v, allcases(v, c), lp, rp);
1555     }
1556    
1557     /*
1558     - dovec - fill in arcs for each element of a cvec
1559     * This one has to handle the messy cases, like MCCEs and MCCE leaders.
1560     ^ static VOID dovec(struct vars *, struct cvec *, struct state *,
1561     ^ struct state *);
1562     */
1563     static VOID
1564     dovec(v, cv, lp, rp)
1565     struct vars *v;
1566     struct cvec *cv;
1567     struct state *lp;
1568     struct state *rp;
1569     {
1570     chr ch, from, to;
1571     celt ce;
1572     chr *p;
1573     int i;
1574     color co;
1575     struct cvec *leads;
1576     struct arc *a;
1577     struct arc *pa; /* arc in prototype */
1578     struct state *s;
1579     struct state *ps; /* state in prototype */
1580    
1581     /* need a place to store leaders, if any */
1582     if (nmcces(v) > 0) {
1583     assert(v->mcces != NULL);
1584     if (v->cv2 == NULL || v->cv2->nchrs < v->mcces->nchrs) {
1585     if (v->cv2 != NULL)
1586     free(v->cv2);
1587     v->cv2 = newcvec(v->mcces->nchrs, 0, v->mcces->nmcces);
1588     NOERR();
1589     leads = v->cv2;
1590     } else
1591     leads = clearcvec(v->cv2);
1592     } else
1593     leads = NULL;
1594    
1595     /* first, get the ordinary characters out of the way */
1596     for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--) {
1597     ch = *p;
1598     if (!ISCELEADER(v, ch))
1599     newarc(v->nfa, PLAIN, subcolor(v->cm, ch), lp, rp);
1600     else {
1601     assert(singleton(v->cm, ch));
1602     assert(leads != NULL);
1603     if (!haschr(leads, ch))
1604     addchr(leads, ch);
1605     }
1606     }
1607    
1608     /* and the ranges */
1609     for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--) {
1610     from = *p;
1611     to = *(p+1);
1612     while (from <= to && (ce = nextleader(v, from, to)) != NOCELT) {
1613     if (from < ce)
1614     subrange(v, from, ce - 1, lp, rp);
1615     assert(singleton(v->cm, ce));
1616     assert(leads != NULL);
1617     if (!haschr(leads, ce))
1618     addchr(leads, ce);
1619     from = ce + 1;
1620     }
1621     if (from <= to)
1622     subrange(v, from, to, lp, rp);
1623     }
1624    
1625     if ((leads == NULL || leads->nchrs == 0) && cv->nmcces == 0)
1626     return;
1627    
1628     /* deal with the MCCE leaders */
1629     NOTE(REG_ULOCALE);
1630     for (p = leads->chrs, i = leads->nchrs; i > 0; p++, i--) {
1631     co = GETCOLOR(v->cm, *p);
1632     a = findarc(lp, PLAIN, co);
1633     if (a != NULL)
1634     s = a->to;
1635     else {
1636     s = newstate(v->nfa);
1637     NOERR();
1638     newarc(v->nfa, PLAIN, co, lp, s);
1639     NOERR();
1640     }
1641     pa = findarc(v->mccepbegin, PLAIN, co);
1642     assert(pa != NULL);
1643     ps = pa->to;
1644     newarc(v->nfa, '$', 1, s, rp);
1645     newarc(v->nfa, '$', 0, s, rp);
1646     colorcomplement(v->nfa, v->cm, AHEAD, ps, s, rp);
1647     NOERR();
1648     }
1649    
1650     /* and the MCCEs */
1651     for (i = 0; i < cv->nmcces; i++) {
1652     p = cv->mcces[i];
1653     assert(singleton(v->cm, *p));
1654     if (!singleton(v->cm, *p)) {
1655     ERR(REG_ASSERT);
1656     return;
1657     }
1658     ch = *p++;
1659     co = GETCOLOR(v->cm, ch);
1660     a = findarc(lp, PLAIN, co);
1661     if (a != NULL)
1662     s = a->to;
1663     else {
1664     s = newstate(v->nfa);
1665     NOERR();
1666     newarc(v->nfa, PLAIN, co, lp, s);
1667     NOERR();
1668     }
1669     assert(*p != 0); /* at least two chars */
1670     assert(singleton(v->cm, *p));
1671     ch = *p++;
1672     co = GETCOLOR(v->cm, ch);
1673     assert(*p == 0); /* and only two, for now */
1674     newarc(v->nfa, PLAIN, co, s, rp);
1675     NOERR();
1676     }
1677     }
1678    
1679     /*
1680     - nextleader - find next MCCE leader within range
1681     ^ static celt nextleader(struct vars *, pchr, pchr);
1682     */
1683     static celt /* NOCELT means none */
1684     nextleader(v, from, to)
1685     struct vars *v;
1686     pchr from;
1687     pchr to;
1688     {
1689     int i;
1690     chr *p;
1691     chr ch;
1692     celt it = NOCELT;
1693    
1694     if (v->mcces == NULL)
1695     return it;
1696    
1697     for (i = v->mcces->nchrs, p = v->mcces->chrs; i > 0; i--, p++) {
1698     ch = *p;
1699     if (from <= ch && ch <= to)
1700     if (it == NOCELT || ch < it)
1701     it = ch;
1702     }
1703     return it;
1704     }
1705    
1706     /*
1707     - wordchrs - set up word-chr list for word-boundary stuff, if needed
1708     * The list is kept as a bunch of arcs between two dummy states; it's
1709     * disposed of by the unreachable-states sweep in NFA optimization.
1710     * Does NEXT(). Must not be called from any unusual lexical context.
1711     * This should be reconciled with the \w etc. handling in lex.c, and
1712     * should be cleaned up to reduce dependencies on input scanning.
1713     ^ static VOID wordchrs(struct vars *);
1714     */
1715     static VOID
1716     wordchrs(v)
1717     struct vars *v;
1718     {
1719     struct state *left;
1720     struct state *right;
1721    
1722     if (v->wordchrs != NULL) {
1723     NEXT(); /* for consistency */
1724     return;
1725     }
1726    
1727     left = newstate(v->nfa);
1728     right = newstate(v->nfa);
1729     NOERR();
1730     /* fine point: implemented with [::], and lexer will set REG_ULOCALE */
1731     lexword(v);
1732     NEXT();
1733     assert(v->savenow != NULL && SEE('['));
1734     bracket(v, left, right);
1735     assert((v->savenow != NULL && SEE(']')) || ISERR());
1736     NEXT();
1737     NOERR();
1738     v->wordchrs = left;
1739     }
1740    
1741     /*
1742     - subre - allocate a subre
1743     ^ static struct subre *subre(struct vars *, int, int, struct state *,
1744     ^ struct state *);
1745     */
1746     static struct subre *
1747     subre(v, op, flags, begin, end)
1748     struct vars *v;
1749     int op;
1750     int flags;
1751     struct state *begin;
1752     struct state *end;
1753     {
1754     struct subre *ret;
1755    
1756     ret = v->treefree;
1757     if (ret != NULL)
1758     v->treefree = ret->left;
1759     else {
1760     ret = (struct subre *)MALLOC(sizeof(struct subre));
1761     if (ret == NULL) {
1762     ERR(REG_ESPACE);
1763     return NULL;
1764     }
1765     ret->chain = v->treechain;
1766     v->treechain = ret;
1767     }
1768    
1769     assert(strchr("|.b(=", op) != NULL);
1770    
1771     ret->op = op;
1772     ret->flags = flags;
1773     ret->retry = 0;
1774     ret->subno = 0;
1775     ret->min = ret->max = 1;
1776     ret->left = NULL;
1777     ret->right = NULL;
1778     ret->begin = begin;
1779     ret->end = end;
1780     ZAPCNFA(ret->cnfa);
1781    
1782     return ret;
1783     }
1784    
1785     /*
1786     - freesubre - free a subRE subtree
1787     ^ static VOID freesubre(struct vars *, struct subre *);
1788     */
1789     static VOID
1790     freesubre(v, sr)
1791     struct vars *v; /* might be NULL */
1792     struct subre *sr;
1793     {
1794     if (sr == NULL)
1795     return;
1796    
1797     if (sr->left != NULL)
1798     freesubre(v, sr->left);
1799     if (sr->right != NULL)
1800     freesubre(v, sr->right);
1801    
1802     freesrnode(v, sr);
1803     }
1804    
1805     /*
1806     - freesrnode - free one node in a subRE subtree
1807     ^ static VOID freesrnode(struct vars *, struct subre *);
1808     */
1809     static VOID
1810     freesrnode(v, sr)
1811     struct vars *v; /* might be NULL */
1812     struct subre *sr;
1813     {
1814     if (sr == NULL)
1815     return;
1816    
1817     if (!NULLCNFA(sr->cnfa))
1818     freecnfa(&sr->cnfa);
1819     sr->flags = 0;
1820    
1821     if (v != NULL) {
1822     sr->left = v->treefree;
1823     v->treefree = sr;
1824     } else
1825     FREE(sr);
1826     }
1827    
1828     /*
1829     - optst - optimize a subRE subtree
1830     ^ static VOID optst(struct vars *, struct subre *);
1831     */
1832     static VOID
1833     optst(v, t)
1834     struct vars *v;
1835     struct subre *t;
1836     {
1837     if (t == NULL)
1838     return;
1839    
1840     /* recurse through children */
1841     if (t->left != NULL)
1842     optst(v, t->left);
1843     if (t->right != NULL)
1844     optst(v, t->right);
1845     }
1846    
1847     /*
1848     - numst - number tree nodes (assigning retry indexes)
1849     ^ static int numst(struct subre *, int);
1850     */
1851     static int /* next number */
1852     numst(t, start)
1853     struct subre *t;
1854     int start; /* starting point for subtree numbers */
1855     {
1856     int i;
1857    
1858     assert(t != NULL);
1859    
1860     i = start;
1861     t->retry = (short)i++;
1862     if (t->left != NULL)
1863     i = numst(t->left, i);
1864     if (t->right != NULL)
1865     i = numst(t->right, i);
1866     return i;
1867     }
1868    
1869     /*
1870     - markst - mark tree nodes as INUSE
1871     ^ static VOID markst(struct subre *);
1872     */
1873     static VOID
1874     markst(t)
1875     struct subre *t;
1876     {
1877     assert(t != NULL);
1878    
1879     t->flags |= INUSE;
1880     if (t->left != NULL)
1881     markst(t->left);
1882     if (t->right != NULL)
1883     markst(t->right);
1884     }
1885    
1886     /*
1887     - cleanst - free any tree nodes not marked INUSE
1888     ^ static VOID cleanst(struct vars *);
1889     */
1890     static VOID
1891     cleanst(v)
1892     struct vars *v;
1893     {
1894     struct subre *t;
1895     struct subre *next;
1896    
1897     for (t = v->treechain; t != NULL; t = next) {
1898     next = t->chain;
1899     if (!(t->flags&INUSE))
1900     FREE(t);
1901     }
1902     v->treechain = NULL;
1903     v->treefree = NULL; /* just on general principles */
1904     }
1905    
1906     /*
1907     - nfatree - turn a subRE subtree into a tree of compacted NFAs
1908     ^ static long nfatree(struct vars *, struct subre *, FILE *);
1909     */
1910     static long /* optimize results from top node */
1911     nfatree(v, t, f)
1912     struct vars *v;
1913     struct subre *t;
1914     FILE *f; /* for debug output */
1915     {
1916     assert(t != NULL && t->begin != NULL);
1917    
1918     if (t->left != NULL)
1919     (DISCARD)nfatree(v, t->left, f);
1920     if (t->right != NULL)
1921     (DISCARD)nfatree(v, t->right, f);
1922    
1923     return nfanode(v, t, f);
1924     }
1925    
1926     /*
1927     - nfanode - do one NFA for nfatree
1928     ^ static long nfanode(struct vars *, struct subre *, FILE *);
1929     */
1930     static long /* optimize results */
1931     nfanode(v, t, f)
1932     struct vars *v;
1933     struct subre *t;
1934     FILE *f; /* for debug output */
1935     {
1936     struct nfa *nfa;
1937     long ret = 0;
1938     char idbuf[50];
1939    
1940     assert(t->begin != NULL);
1941    
1942     if (f != NULL)
1943     fprintf(f, "\n\n\n========= TREE NODE %s ==========\n",
1944     stid(t, idbuf, sizeof(idbuf)));
1945     nfa = newnfa(v, v->cm, v->nfa);
1946     NOERRZ();
1947     dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final);
1948     if (!ISERR()) {
1949     specialcolors(nfa);
1950     ret = optimize(nfa, f);
1951     }
1952     if (!ISERR())
1953     compact(nfa, &t->cnfa);
1954    
1955     freenfa(nfa);
1956     return ret;
1957     }
1958    
1959     /*
1960     - newlacon - allocate a lookahead-constraint subRE
1961     ^ static int newlacon(struct vars *, struct state *, struct state *, int);
1962     */
1963     static int /* lacon number */
1964     newlacon(v, begin, end, pos)
1965     struct vars *v;
1966     struct state *begin;
1967     struct state *end;
1968     int pos;
1969     {
1970     int n;
1971     struct subre *sub;
1972    
1973     if (v->nlacons == 0) {
1974     v->lacons = (struct subre *)MALLOC(2 * sizeof(struct subre));
1975     n = 1; /* skip 0th */
1976     v->nlacons = 2;
1977     } else {
1978     v->lacons = (struct subre *)REALLOC(v->lacons,
1979     (v->nlacons+1)*sizeof(struct subre));
1980     n = v->nlacons++;
1981     }
1982     if (v->lacons == NULL) {
1983     ERR(REG_ESPACE);
1984     return 0;
1985     }
1986     sub = &v->lacons[n];
1987     sub->begin = begin;
1988     sub->end = end;
1989     sub->subno = pos;
1990     ZAPCNFA(sub->cnfa);
1991     return n;
1992     }
1993    
1994     /*
1995     - freelacons - free lookahead-constraint subRE vector
1996     ^ static VOID freelacons(struct subre *, int);
1997     */
1998     static VOID
1999     freelacons(subs, n)
2000     struct subre *subs;
2001     int n;
2002     {
2003     struct subre *sub;
2004     int i;
2005    
2006     assert(n > 0);
2007     for (sub = subs + 1, i = n - 1; i > 0; sub++, i--) /* no 0th */
2008     if (!NULLCNFA(sub->cnfa))
2009     freecnfa(&sub->cnfa);
2010     FREE(subs);
2011     }
2012    
2013     /*
2014     - rfree - free a whole RE (insides of regfree)
2015     ^ static VOID rfree(regex_t *);
2016     */
2017     static VOID
2018     rfree(re)
2019     regex_t *re;
2020     {
2021     struct guts *g;
2022    
2023     if (re == NULL || re->re_magic != REMAGIC)
2024     return;
2025    
2026     re->re_magic = 0; /* invalidate RE */
2027     g = (struct guts *)re->re_guts;
2028     re->re_guts = NULL;
2029     re->re_fns = NULL;
2030     g->magic = 0;
2031     freecm(&g->cmap);
2032     if (g->tree != NULL)
2033     freesubre((struct vars *)NULL, g->tree);
2034     if (g->lacons != NULL)
2035     freelacons(g->lacons, g->nlacons);
2036     if (!NULLCNFA(g->search))
2037     freecnfa(&g->search);
2038     FREE(g);
2039     }
2040    
2041     /*
2042     - dump - dump an RE in human-readable form
2043     ^ static VOID dump(regex_t *, FILE *);
2044     */
2045     static VOID
2046     dump(re, f)
2047     regex_t *re;
2048     FILE *f;
2049     {
2050     #ifdef REG_DEBUG
2051     struct guts *g;
2052     int i;
2053    
2054     if (re->re_magic != REMAGIC)
2055     fprintf(f, "bad magic number (0x%x not 0x%x)\n", re->re_magic,
2056     REMAGIC);
2057     if (re->re_guts == NULL) {
2058     fprintf(f, "NULL guts!!!\n");
2059     return;
2060     }
2061     g = (struct guts *)re->re_guts;
2062     if (g->magic != GUTSMAGIC)
2063     fprintf(f, "bad guts magic number (0x%x not 0x%x)\n", g->magic,
2064     GUTSMAGIC);
2065    
2066     fprintf(f, "\n\n\n========= DUMP ==========\n");
2067     fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n",
2068     re->re_nsub, re->re_info, re->re_csize, g->ntree);
2069    
2070     dumpcolors(&g->cmap, f);
2071     if (!NULLCNFA(g->search)) {
2072     printf("\nsearch:\n");
2073     dumpcnfa(&g->search, f);
2074     }
2075     for (i = 1; i < g->nlacons; i++) {
2076     fprintf(f, "\nla%d (%s):\n", i,
2077     (g->lacons[i].subno) ? "positive" : "negative");
2078     dumpcnfa(&g->lacons[i].cnfa, f);
2079     }
2080     fprintf(f, "\n");
2081     dumpst(g->tree, f, 0);
2082     #endif
2083     }
2084    
2085     /*
2086     - dumpst - dump a subRE tree
2087     ^ static VOID dumpst(struct subre *, FILE *, int);
2088     */
2089     static VOID
2090     dumpst(t, f, nfapresent)
2091     struct subre *t;
2092     FILE *f;
2093     int nfapresent; /* is the original NFA still around? */
2094     {
2095     if (t == NULL)
2096     fprintf(f, "null tree\n");
2097     else
2098     stdump(t, f, nfapresent);
2099     fflush(f);
2100     }
2101    
2102     /*
2103     - stdump - recursive guts of dumpst
2104     ^ static VOID stdump(struct subre *, FILE *, int);
2105     */
2106     static VOID
2107     stdump(t, f, nfapresent)
2108     struct subre *t;
2109     FILE *f;
2110     int nfapresent; /* is the original NFA still around? */
2111     {
2112     char idbuf[50];
2113    
2114     fprintf(f, "%s. `%c'", stid(t, idbuf, sizeof(idbuf)), t->op);
2115     if (t->flags&LONGER)
2116     fprintf(f, " longest");
2117     if (t->flags&SHORTER)
2118     fprintf(f, " shortest");
2119     if (t->flags&MIXED)
2120     fprintf(f, " hasmixed");
2121     if (t->flags&CAP)
2122     fprintf(f, " hascapture");
2123     if (t->flags&BACKR)
2124     fprintf(f, " hasbackref");
2125     if (!(t->flags&INUSE))
2126     fprintf(f, " UNUSED");
2127     if (t->subno != 0)
2128     fprintf(f, " (#%d)", t->subno);
2129     if (t->min != 1 || t->max != 1) {
2130     fprintf(f, " {%d,", t->min);
2131     if (t->max != INFINITY)
2132     fprintf(f, "%d", t->max);
2133     fprintf(f, "}");
2134     }
2135     if (nfapresent)
2136     fprintf(f, " %ld-%ld", (long)t->begin->no, (long)t->end->no);
2137     if (t->left != NULL)
2138     fprintf(f, " L:%s", stid(t->left, idbuf, sizeof(idbuf)));
2139     if (t->right != NULL)
2140     fprintf(f, " R:%s", stid(t->right, idbuf, sizeof(idbuf)));
2141     if (!NULLCNFA(t->cnfa)) {
2142     fprintf(f, "\n");
2143     dumpcnfa(&t->cnfa, f);
2144     fprintf(f, "\n");
2145     }
2146     if (t->left != NULL)
2147     stdump(t->left, f, nfapresent);
2148     if (t->right != NULL)
2149     stdump(t->right, f, nfapresent);
2150     }
2151    
2152     /*
2153     - stid - identify a subtree node for dumping
2154     ^ static char *stid(struct subre *, char *, size_t);
2155     */
2156     static char * /* points to buf or constant string */
2157     stid(t, buf, bufsize)
2158     struct subre *t;
2159     char *buf;
2160     size_t bufsize;
2161     {
2162     /* big enough for hex int or decimal t->retry? */
2163     if (bufsize < sizeof(int)*2 + 3 || bufsize < sizeof(t->retry)*3 + 1)
2164     return "unable";
2165     if (t->retry != 0)
2166     sprintf(buf, "%d", t->retry);
2167     else
2168     sprintf(buf, "0x%x", (int)t); /* may lose bits, that's okay */
2169     return buf;
2170     }
2171    
2172     #include "regc_lex.c"
2173     #include "regc_color.c"
2174     #include "regc_nfa.c"
2175     #include "regc_cvec.c"
2176     #include "regc_locale.c"
2177    
2178     /* End of regcomp.c */

Properties

Name Value
svn:eol-style native
svn:keywords Header
dashley@gmail.com
 ViewVC Help
Powered by ViewVC 1.1.25