]> git.saurik.com Git - wxWidgets.git/blob - src/regex/regcomp.c
projects / wxWidgets.git / blob
? search:


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