PostgreSQL Source Code  git master
regcomp.c
Go to the documentation of this file.
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  * src/backend/regex/regcomp.c
32  *
33  */
34 
35 #include "regex/regguts.h"
36 
37 /*
38  * forward declarations, up here so forward datatypes etc. are defined early
39  */
40 /* === regcomp.c === */
41 static void moresubs(struct vars *v, int wanted);
42 static int freev(struct vars *v, int err);
43 static void makesearch(struct vars *v, struct nfa *nfa);
44 static struct subre *parse(struct vars *v, int stopper, int type,
45  struct state *init, struct state *final);
46 static struct subre *parsebranch(struct vars *v, int stopper, int type,
47  struct state *left, struct state *right,
48  int partial);
49 static struct subre *parseqatom(struct vars *v, int stopper, int type,
50  struct state *lp, struct state *rp,
51  struct subre *top);
52 static void nonword(struct vars *v, int dir, struct state *lp,
53  struct state *rp);
54 static void word(struct vars *v, int dir, struct state *lp, struct state *rp);
55 static void charclass(struct vars *v, enum char_classes cls, struct state *lp,
56  struct state *rp);
57 static void charclasscomplement(struct vars *v, enum char_classes cls,
58  struct state *lp, struct state *rp);
59 static int scannum(struct vars *v);
60 static void repeat(struct vars *v, struct state *lp, struct state *rp,
61  int m, int n);
62 static void bracket(struct vars *v, struct state *lp, struct state *rp);
63 static void cbracket(struct vars *v, struct state *lp, struct state *rp);
64 static void brackpart(struct vars *v, struct state *lp, struct state *rp,
65  bool *have_cclassc);
66 static const chr *scanplain(struct vars *v);
67 static void onechr(struct vars *v, chr c, struct state *lp, struct state *rp);
68 static void optimizebracket(struct vars *v, struct state *lp, struct state *rp);
69 static void wordchrs(struct vars *v);
70 static void processlacon(struct vars *v, struct state *begin,
71  struct state *end, int latype,
72  struct state *lp, struct state *rp);
73 static struct subre *subre(struct vars *v, int op, int flags,
74  struct state *begin, struct state *end);
75 static void freesubre(struct vars *v, struct subre *sr);
76 static void freesubreandsiblings(struct vars *v, struct subre *sr);
77 static void freesrnode(struct vars *v, struct subre *sr);
78 static void removecaptures(struct vars *v, struct subre *t);
79 static int numst(struct subre *t, int start);
80 static void markst(struct subre *t);
81 static void cleanst(struct vars *v);
82 static long nfatree(struct vars *v, struct subre *t, FILE *f);
83 static long nfanode(struct vars *v, struct subre *t,
84  int converttosearch, FILE *f);
85 static int newlacon(struct vars *v, struct state *begin, struct state *end,
86  int latype);
87 static void freelacons(struct subre *subs, int n);
88 static void rfree(regex_t *re);
89 static int rstacktoodeep(void);
90 
91 #ifdef REG_DEBUG
92 static void dump(regex_t *re, FILE *f);
93 static void dumpst(struct subre *t, FILE *f, int nfapresent);
94 static void stdump(struct subre *t, FILE *f, int nfapresent);
95 static const char *stid(struct subre *t, char *buf, size_t bufsize);
96 #endif
97 /* === regc_lex.c === */
98 static void lexstart(struct vars *v);
99 static void prefixes(struct vars *v);
100 static int next(struct vars *v);
101 static int lexescape(struct vars *v);
102 static chr lexdigits(struct vars *v, int base, int minlen, int maxlen);
103 static int brenext(struct vars *v, chr c);
104 static void skip(struct vars *v);
105 static chr newline(void);
106 static chr chrnamed(struct vars *v, const chr *startp, const chr *endp,
107  chr lastresort);
108 
109 /* === regc_color.c === */
110 static void initcm(struct vars *v, struct colormap *cm);
111 static void freecm(struct colormap *cm);
112 static color maxcolor(struct colormap *cm);
113 static color newcolor(struct colormap *cm);
114 static void freecolor(struct colormap *cm, color co);
115 static color pseudocolor(struct colormap *cm);
116 static color subcolor(struct colormap *cm, chr c);
117 static color subcolorhi(struct colormap *cm, color *pco);
118 static color newsub(struct colormap *cm, color co);
119 static int newhicolorrow(struct colormap *cm, int oldrow);
120 static void newhicolorcols(struct colormap *cm);
121 static void subcolorcvec(struct vars *v, struct cvec *cv, struct state *lp,
122  struct state *rp);
123 static void subcoloronechr(struct vars *v, chr ch, struct state *lp,
124  struct state *rp, color *lastsubcolor);
125 static void subcoloronerange(struct vars *v, chr from, chr to,
126  struct state *lp, struct state *rp,
127  color *lastsubcolor);
128 static void subcoloronerow(struct vars *v, int rownum, struct state *lp,
129  struct state *rp, color *lastsubcolor);
130 static void okcolors(struct nfa *nfa, struct colormap *cm);
131 static void colorchain(struct colormap *cm, struct arc *a);
132 static void uncolorchain(struct colormap *cm, struct arc *a);
133 static void rainbow(struct nfa *nfa, struct colormap *cm, int type, color but,
134  struct state *from, struct state *to);
135 static void colorcomplement(struct nfa *nfa, struct colormap *cm, int type,
136  struct state *of, struct state *from,
137  struct state *to);
138 
139 #ifdef REG_DEBUG
140 static void dumpcolors(struct colormap *cm, FILE *f);
141 static void dumpchr(chr c, FILE *f);
142 #endif
143 /* === regc_nfa.c === */
144 static struct nfa *newnfa(struct vars *v, struct colormap *cm,
145  struct nfa *parent);
146 static void freenfa(struct nfa *nfa);
147 static struct state *newstate(struct nfa *nfa);
148 static struct state *newfstate(struct nfa *nfa, int flag);
149 static void dropstate(struct nfa *nfa, struct state *s);
150 static void freestate(struct nfa *nfa, struct state *s);
151 static void newarc(struct nfa *nfa, int t, color co,
152  struct state *from, struct state *to);
153 static void createarc(struct nfa *nfa, int t, color co,
154  struct state *from, struct state *to);
155 static struct arc *allocarc(struct nfa *nfa);
156 static void freearc(struct nfa *nfa, struct arc *victim);
157 static void changearcsource(struct arc *a, struct state *newfrom);
158 static void changearctarget(struct arc *a, struct state *newto);
159 static int hasnonemptyout(struct state *s);
160 static struct arc *findarc(struct state *s, int type, color co);
161 static void cparc(struct nfa *nfa, struct arc *oa,
162  struct state *from, struct state *to);
163 static void sortins(struct nfa *nfa, struct state *s);
164 static int sortins_cmp(const void *a, const void *b);
165 static void sortouts(struct nfa *nfa, struct state *s);
166 static int sortouts_cmp(const void *a, const void *b);
167 static void moveins(struct nfa *nfa, struct state *oldState,
168  struct state *newState);
169 static void copyins(struct nfa *nfa, struct state *oldState,
170  struct state *newState);
171 static void mergeins(struct nfa *nfa, struct state *s,
172  struct arc **arcarray, int arccount);
173 static void moveouts(struct nfa *nfa, struct state *oldState,
174  struct state *newState);
175 static void copyouts(struct nfa *nfa, struct state *oldState,
176  struct state *newState);
177 static void cloneouts(struct nfa *nfa, struct state *old, struct state *from,
178  struct state *to, int type);
179 static void delsub(struct nfa *nfa, struct state *lp, struct state *rp);
180 static void deltraverse(struct nfa *nfa, struct state *leftend,
181  struct state *s);
182 static void dupnfa(struct nfa *nfa, struct state *start, struct state *stop,
183  struct state *from, struct state *to);
184 static void duptraverse(struct nfa *nfa, struct state *s, struct state *stmp);
185 static void removeconstraints(struct nfa *nfa, struct state *start, struct state *stop);
186 static void removetraverse(struct nfa *nfa, struct state *s);
187 static void cleartraverse(struct nfa *nfa, struct state *s);
188 static struct state *single_color_transition(struct state *s1,
189  struct state *s2);
190 static void specialcolors(struct nfa *nfa);
191 static long optimize(struct nfa *nfa, FILE *f);
192 static void pullback(struct nfa *nfa, FILE *f);
193 static int pull(struct nfa *nfa, struct arc *con,
194  struct state **intermediates);
195 static void pushfwd(struct nfa *nfa, FILE *f);
196 static int push(struct nfa *nfa, struct arc *con,
197  struct state **intermediates);
198 
199 #define INCOMPATIBLE 1 /* destroys arc */
200 #define SATISFIED 2 /* constraint satisfied */
201 #define COMPATIBLE 3 /* compatible but not satisfied yet */
202 #define REPLACEARC 4 /* replace arc's color with constraint color */
203 static int combine(struct nfa *nfa, struct arc *con, struct arc *a);
204 static void fixempties(struct nfa *nfa, FILE *f);
205 static struct state *emptyreachable(struct nfa *nfa, struct state *s,
206  struct state *lastfound,
207  struct arc **inarcsorig);
208 static int isconstraintarc(struct arc *a);
209 static int hasconstraintout(struct state *s);
210 static void fixconstraintloops(struct nfa *nfa, FILE *f);
211 static int findconstraintloop(struct nfa *nfa, struct state *s);
212 static void breakconstraintloop(struct nfa *nfa, struct state *sinitial);
213 static void clonesuccessorstates(struct nfa *nfa, struct state *ssource,
214  struct state *sclone,
215  struct state *spredecessor,
216  struct arc *refarc, char *curdonemap,
217  char *outerdonemap, int nstates);
218 static void cleanup(struct nfa *nfa);
219 static void markreachable(struct nfa *nfa, struct state *s,
220  struct state *okay, struct state *mark);
221 static void markcanreach(struct nfa *nfa, struct state *s, struct state *okay,
222  struct state *mark);
223 static long analyze(struct nfa *nfa);
224 static void checkmatchall(struct nfa *nfa);
225 static bool checkmatchall_recurse(struct nfa *nfa, struct state *s,
226  bool **haspaths);
227 static bool check_out_colors_match(struct state *s, color co1, color co2);
228 static bool check_in_colors_match(struct state *s, color co1, color co2);
229 static void compact(struct nfa *nfa, struct cnfa *cnfa);
230 static void carcsort(struct carc *first, size_t n);
231 static int carc_cmp(const void *a, const void *b);
232 static void freecnfa(struct cnfa *cnfa);
233 static void dumpnfa(struct nfa *nfa, FILE *f);
234 
235 #ifdef REG_DEBUG
236 static void dumpstate(struct state *s, FILE *f);
237 static void dumparcs(struct state *s, FILE *f);
238 static void dumparc(struct arc *a, struct state *s, FILE *f);
239 static void dumpcnfa(struct cnfa *cnfa, FILE *f);
240 static void dumpcstate(int st, struct cnfa *cnfa, FILE *f);
241 #endif
242 /* === regc_cvec.c === */
243 static struct cvec *newcvec(int nchrs, int nranges);
244 static struct cvec *clearcvec(struct cvec *cv);
245 static void addchr(struct cvec *cv, chr c);
246 static void addrange(struct cvec *cv, chr from, chr to);
247 static struct cvec *getcvec(struct vars *v, int nchrs, int nranges);
248 static void freecvec(struct cvec *cv);
249 
250 /* === regc_pg_locale.c === */
251 static int pg_wc_isdigit(pg_wchar c);
252 static int pg_wc_isalpha(pg_wchar c);
253 static int pg_wc_isalnum(pg_wchar c);
254 static int pg_wc_isword(pg_wchar c);
255 static int pg_wc_isupper(pg_wchar c);
256 static int pg_wc_islower(pg_wchar c);
257 static int pg_wc_isgraph(pg_wchar c);
258 static int pg_wc_isprint(pg_wchar c);
259 static int pg_wc_ispunct(pg_wchar c);
260 static int pg_wc_isspace(pg_wchar c);
261 static pg_wchar pg_wc_toupper(pg_wchar c);
262 static pg_wchar pg_wc_tolower(pg_wchar c);
263 
264 /* === regc_locale.c === */
265 static chr element(struct vars *v, const chr *startp, const chr *endp);
266 static struct cvec *range(struct vars *v, chr a, chr b, int cases);
267 static int before(chr x, chr y);
268 static struct cvec *eclass(struct vars *v, chr c, int cases);
269 static enum char_classes lookupcclass(struct vars *v, const chr *startp,
270  const chr *endp);
271 static struct cvec *cclasscvec(struct vars *v, enum char_classes cclasscode,
272  int cases);
273 static int cclass_column_index(struct colormap *cm, chr c);
274 static struct cvec *allcases(struct vars *v, chr c);
275 static int cmp(const chr *x, const chr *y, size_t len);
276 static int casecmp(const chr *x, const chr *y, size_t len);
277 
278 
279 /* internal variables, bundled for easy passing around */
280 struct vars
281 {
282  regex_t *re;
283  const chr *now; /* scan pointer into string */
284  const chr *stop; /* end of string */
285  int err; /* error code (0 if none) */
286  int cflags; /* copy of compile flags */
287  int lasttype; /* type of previous token */
288  int nexttype; /* type of next token */
289  chr nextvalue; /* value (if any) of next token */
290  int lexcon; /* lexical context type (see regc_lex.c) */
291  int nsubexp; /* subexpression count */
292  struct subre **subs; /* subRE pointer vector */
293  size_t nsubs; /* length of vector */
294  struct subre *sub10[10]; /* initial vector, enough for most */
295  struct nfa *nfa; /* the NFA */
296  struct colormap *cm; /* character color map */
297  color nlcolor; /* color of newline */
298  struct state *wordchrs; /* state in nfa holding word-char outarcs */
299  struct subre *tree; /* subexpression tree */
300  struct subre *treechain; /* all tree nodes allocated */
301  struct subre *treefree; /* any free tree nodes */
302  int ntree; /* number of tree nodes, plus one */
303  struct cvec *cv; /* interface cvec */
304  struct cvec *cv2; /* utility cvec */
305  struct subre *lacons; /* lookaround-constraint vector */
306  int nlacons; /* size of lacons[]; note that only slots
307  * numbered 1 .. nlacons-1 are used */
308  size_t spaceused; /* approx. space used for compilation */
309 };
310 
311 /* parsing macros; most know that `v' is the struct vars pointer */
312 #define NEXT() (next(v)) /* advance by one token */
313 #define SEE(t) (v->nexttype == (t)) /* is next token this? */
314 #define EAT(t) (SEE(t) && next(v)) /* if next is this, swallow it */
315 #define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */
316 #define ISERR() VISERR(v)
317 #define VERR(vv,e) ((vv)->nexttype = EOS, \
318  (vv)->err = ((vv)->err ? (vv)->err : (e)))
319 #define ERR(e) VERR(v, e) /* record an error */
320 #define NOERR() {if (ISERR()) return;} /* if error seen, return */
321 #define NOERRN() {if (ISERR()) return NULL;} /* NOERR with retval */
322 #define NOERRZ() {if (ISERR()) return 0;} /* NOERR with retval */
323 #define INSIST(c, e) do { if (!(c)) ERR(e); } while (0) /* error if c false */
324 #define NOTE(b) (v->re->re_info |= (b)) /* note visible condition */
325 #define EMPTYARC(x, y) newarc(v->nfa, EMPTY, 0, x, y)
326 
327 /* token type codes, some also used as NFA arc types */
328 #define EMPTY 'n' /* no token present */
329 #define EOS 'e' /* end of string */
330 #define PLAIN 'p' /* ordinary character */
331 #define DIGIT 'd' /* digit (in bound) */
332 #define BACKREF 'b' /* back reference */
333 #define COLLEL 'I' /* start of [. */
334 #define ECLASS 'E' /* start of [= */
335 #define CCLASS 'C' /* start of [: */
336 #define END 'X' /* end of [. [= [: */
337 #define CCLASSS 's' /* char class shorthand escape */
338 #define CCLASSC 'c' /* complement char class shorthand escape */
339 #define RANGE 'R' /* - within [] which might be range delim. */
340 #define LACON 'L' /* lookaround constraint subRE */
341 #define AHEAD 'a' /* color-lookahead arc */
342 #define BEHIND 'r' /* color-lookbehind arc */
343 #define WBDRY 'w' /* word boundary constraint */
344 #define NWBDRY 'W' /* non-word-boundary constraint */
345 #define SBEGIN 'A' /* beginning of string (even if not BOL) */
346 #define SEND 'Z' /* end of string (even if not EOL) */
347 
348 /* is an arc colored, and hence should belong to a color chain? */
349 /* the test on "co" eliminates RAINBOW arcs, which we don't bother to chain */
350 #define COLORED(a) \
351  ((a)->co >= 0 && \
352  ((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND))
353 
354 
355 /* static function list */
356 static const struct fns functions = {
357  rfree, /* regfree insides */
358  rstacktoodeep /* check for stack getting dangerously deep */
359 };
360 
361 
362 
363 /*
364  * pg_regcomp - compile regular expression
365  *
366  * Note: on failure, no resources remain allocated, so pg_regfree()
367  * need not be applied to re.
368  */
369 int
370 pg_regcomp(regex_t *re,
371  const chr *string,
372  size_t len,
373  int flags,
374  Oid collation)
375 {
376  struct vars var;
377  struct vars *v = &var;
378  struct guts *g;
379  int i;
380  size_t j;
381 
382 #ifdef REG_DEBUG
383  FILE *debug = (flags & REG_PROGRESS) ? stdout : (FILE *) NULL;
384 #else
385  FILE *debug = (FILE *) NULL;
386 #endif
387 
388 #define CNOERR() { if (ISERR()) return freev(v, v->err); }
389 
390  /* sanity checks */
391 
392  if (re == NULL || string == NULL)
393  return REG_INVARG;
394  if ((flags & REG_QUOTE) &&
395  (flags & (REG_ADVANCED | REG_EXPANDED | REG_NEWLINE)))
396  return REG_INVARG;
397  if (!(flags & REG_EXTENDED) && (flags & REG_ADVF))
398  return REG_INVARG;
399 
400  /* Initialize locale-dependent support */
401  pg_set_regex_collation(collation);
402 
403  /* initial setup (after which freev() is callable) */
404  v->re = re;
405  v->now = string;
406  v->stop = v->now + len;
407  v->err = 0;
408  v->cflags = flags;
409  v->nsubexp = 0;
410  v->subs = v->sub10;
411  v->nsubs = 10;
412  for (j = 0; j < v->nsubs; j++)
413  v->subs[j] = NULL;
414  v->nfa = NULL;
415  v->cm = NULL;
416  v->nlcolor = COLORLESS;
417  v->wordchrs = NULL;
418  v->tree = NULL;
419  v->treechain = NULL;
420  v->treefree = NULL;
421  v->cv = NULL;
422  v->cv2 = NULL;
423  v->lacons = NULL;
424  v->nlacons = 0;
425  v->spaceused = 0;
426  re->re_magic = REMAGIC;
427  re->re_info = 0; /* bits get set during parse */
428  re->re_csize = sizeof(chr);
429  re->re_collation = collation;
430  re->re_guts = NULL;
431  re->re_fns = VS(&functions);
432 
433  /* more complex setup, malloced things */
434  re->re_guts = VS(MALLOC(sizeof(struct guts)));
435  if (re->re_guts == NULL)
436  return freev(v, REG_ESPACE);
437  g = (struct guts *) re->re_guts;
438  g->tree = NULL;
439  initcm(v, &g->cmap);
440  v->cm = &g->cmap;
441  g->lacons = NULL;
442  g->nlacons = 0;
443  ZAPCNFA(g->search);
444  v->nfa = newnfa(v, v->cm, (struct nfa *) NULL);
445  CNOERR();
446  /* set up a reasonably-sized transient cvec for getcvec usage */
447  v->cv = newcvec(100, 20);
448  if (v->cv == NULL)
449  return freev(v, REG_ESPACE);
450 
451  /* parsing */
452  lexstart(v); /* also handles prefixes */
453  if ((v->cflags & REG_NLSTOP) || (v->cflags & REG_NLANCH))
454  {
455  /* assign newline a unique color */
456  v->nlcolor = subcolor(v->cm, newline());
457  okcolors(v->nfa, v->cm);
458  }
459  CNOERR();
460  v->tree = parse(v, EOS, PLAIN, v->nfa->init, v->nfa->final);
461  assert(SEE(EOS)); /* even if error; ISERR() => SEE(EOS) */
462  CNOERR();
463  assert(v->tree != NULL);
464 
465  /* finish setup of nfa and its subre tree */
466  specialcolors(v->nfa);
467  CNOERR();
468 #ifdef REG_DEBUG
469  if (debug != NULL)
470  {
471  fprintf(debug, "\n\n\n========= RAW ==========\n");
472  dumpnfa(v->nfa, debug);
473  dumpst(v->tree, debug, 1);
474  }
475 #endif
476  if (v->cflags & REG_NOSUB)
477  removecaptures(v, v->tree);
478  v->ntree = numst(v->tree, 1);
479  markst(v->tree);
480  cleanst(v);
481 #ifdef REG_DEBUG
482  if (debug != NULL)
483  {
484  fprintf(debug, "\n\n\n========= TREE FIXED ==========\n");
485  dumpst(v->tree, debug, 1);
486  }
487 #endif
488 
489  /* build compacted NFAs for tree and lacons */
490  re->re_info |= nfatree(v, v->tree, debug);
491  CNOERR();
492  assert(v->nlacons == 0 || v->lacons != NULL);
493  for (i = 1; i < v->nlacons; i++)
494  {
495  struct subre *lasub = &v->lacons[i];
496 
497 #ifdef REG_DEBUG
498  if (debug != NULL)
499  fprintf(debug, "\n\n\n========= LA%d ==========\n", i);
500 #endif
501 
502  /* Prepend .* to pattern if it's a lookbehind LACON */
503  nfanode(v, lasub, !LATYPE_IS_AHEAD(lasub->latype), debug);
504  }
505  CNOERR();
506  if (v->tree->flags & SHORTER)
507  NOTE(REG_USHORTEST);
508 
509  /* build compacted NFAs for tree, lacons, fast search */
510 #ifdef REG_DEBUG
511  if (debug != NULL)
512  fprintf(debug, "\n\n\n========= SEARCH ==========\n");
513 #endif
514  /* can sacrifice main NFA now, so use it as work area */
515  (DISCARD) optimize(v->nfa, debug);
516  CNOERR();
517  makesearch(v, v->nfa);
518  CNOERR();
519  compact(v->nfa, &g->search);
520  CNOERR();
521 
522  /* looks okay, package it up */
523  re->re_nsub = v->nsubexp;
524  v->re = NULL; /* freev no longer frees re */
525  g->magic = GUTSMAGIC;
526  g->cflags = v->cflags;
527  g->info = re->re_info;
528  g->nsub = re->re_nsub;
529  g->tree = v->tree;
530  v->tree = NULL;
531  g->ntree = v->ntree;
532  g->compare = (v->cflags & REG_ICASE) ? casecmp : cmp;
533  g->lacons = v->lacons;
534  v->lacons = NULL;
535  g->nlacons = v->nlacons;
536 
537 #ifdef REG_DEBUG
538  if (flags & REG_DUMP)
539  {
540  dump(re, stdout);
541  fflush(stdout);
542  }
543 #endif
544 
545  assert(v->err == 0);
546  return freev(v, 0);
547 }
548 
549 /*
550  * moresubs - enlarge subRE vector
551  */
552 static void
553 moresubs(struct vars *v,
554  int wanted) /* want enough room for this one */
555 {
556  struct subre **p;
557  size_t n;
558 
559  assert(wanted > 0 && (size_t) wanted >= v->nsubs);
560  n = (size_t) wanted * 3 / 2 + 1;
561 
562  if (v->subs == v->sub10)
563  {
564  p = (struct subre **) MALLOC(n * sizeof(struct subre *));
565  if (p != NULL)
566  memcpy(VS(p), VS(v->subs),
567  v->nsubs * sizeof(struct subre *));
568  }
569  else
570  p = (struct subre **) REALLOC(v->subs, n * sizeof(struct subre *));
571  if (p == NULL)
572  {
573  ERR(REG_ESPACE);
574  return;
575  }
576  v->subs = p;
577  for (p = &v->subs[v->nsubs]; v->nsubs < n; p++, v->nsubs++)
578  *p = NULL;
579  assert(v->nsubs == n);
580  assert((size_t) wanted < v->nsubs);
581 }
582 
583 /*
584  * freev - free vars struct's substructures where necessary
585  *
586  * Optionally does error-number setting, and always returns error code
587  * (if any), to make error-handling code terser.
588  */
589 static int
590 freev(struct vars *v,
591  int err)
592 {
593  if (v->re != NULL)
594  rfree(v->re);
595  if (v->subs != v->sub10)
596  FREE(v->subs);
597  if (v->nfa != NULL)
598  freenfa(v->nfa);
599  if (v->tree != NULL)
600  freesubre(v, v->tree);
601  if (v->treechain != NULL)
602  cleanst(v);
603  if (v->cv != NULL)
604  freecvec(v->cv);
605  if (v->cv2 != NULL)
606  freecvec(v->cv2);
607  if (v->lacons != NULL)
608  freelacons(v->lacons, v->nlacons);
609  ERR(err); /* nop if err==0 */
610 
611  return v->err;
612 }
613 
614 /*
615  * makesearch - turn an NFA into a search NFA (implicit prepend of .*?)
616  * NFA must have been optimize()d already.
617  */
618 static void
619 makesearch(struct vars *v,
620  struct nfa *nfa)
621 {
622  struct arc *a;
623  struct arc *b;
624  struct state *pre = nfa->pre;
625  struct state *s;
626  struct state *s2;
627  struct state *slist;
628 
629  /* no loops are needed if it's anchored */
630  for (a = pre->outs; a != NULL; a = a->outchain)
631  {
632  assert(a->type == PLAIN);
633  if (a->co != nfa->bos[0] && a->co != nfa->bos[1])
634  break;
635  }
636  if (a != NULL)
637  {
638  /* add implicit .* in front */
639  rainbow(nfa, v->cm, PLAIN, COLORLESS, pre, pre);
640 
641  /* and ^* and \A* too -- not always necessary, but harmless */
642  newarc(nfa, PLAIN, nfa->bos[0], pre, pre);
643  newarc(nfa, PLAIN, nfa->bos[1], pre, pre);
644 
645  /*
646  * The pattern is still MATCHALL if it was before, but the max match
647  * length is now infinity.
648  */
649  if (nfa->flags & MATCHALL)
650  nfa->maxmatchall = DUPINF;
651  }
652 
653  /*
654  * Now here's the subtle part. Because many REs have no lookback
655  * constraints, often knowing when you were in the pre state tells you
656  * little; it's the next state(s) that are informative. But some of them
657  * may have other inarcs, i.e. it may be possible to make actual progress
658  * and then return to one of them. We must de-optimize such cases,
659  * splitting each such state into progress and no-progress states.
660  */
661 
662  /* first, make a list of the states reachable from pre and elsewhere */
663  slist = NULL;
664  for (a = pre->outs; a != NULL; a = a->outchain)
665  {
666  s = a->to;
667  for (b = s->ins; b != NULL; b = b->inchain)
668  {
669  if (b->from != pre)
670  break;
671  }
672 
673  /*
674  * We want to mark states as being in the list already by having non
675  * NULL tmp fields, but we can't just store the old slist value in tmp
676  * because that doesn't work for the first such state. Instead, the
677  * first list entry gets its own address in tmp.
678  */
679  if (b != NULL && s->tmp == NULL)
680  {
681  s->tmp = (slist != NULL) ? slist : s;
682  slist = s;
683  }
684  }
685 
686  /* do the splits */
687  for (s = slist; s != NULL; s = s2)
688  {
689  s2 = newstate(nfa);
690  NOERR();
691  copyouts(nfa, s, s2);
692  NOERR();
693  for (a = s->ins; a != NULL; a = b)
694  {
695  b = a->inchain;
696  if (a->from != pre)
697  {
698  cparc(nfa, a, a->from, s2);
699  freearc(nfa, a);
700  }
701  }
702  s2 = (s->tmp != s) ? s->tmp : NULL;
703  s->tmp = NULL; /* clean up while we're at it */
704  }
705 }
706 
707 /*
708  * parse - parse an RE
709  *
710  * This is actually just the top level, which parses a bunch of branches
711  * tied together with '|'. If there's more than one, they appear in the
712  * tree as the children of a '|' subre.
713  */
714 static struct subre *
715 parse(struct vars *v,
716  int stopper, /* EOS or ')' */
717  int type, /* LACON (lookaround subRE) or PLAIN */
718  struct state *init, /* initial state */
719  struct state *final) /* final state */
720 {
721  struct subre *branches; /* top level */
722  struct subre *lastbranch; /* latest branch */
723 
724  assert(stopper == ')' || stopper == EOS);
725 
726  branches = subre(v, '|', LONGER, init, final);
727  NOERRN();
728  lastbranch = NULL;
729  do
730  { /* a branch */
731  struct subre *branch;
732  struct state *left; /* scaffolding for branch */
733  struct state *right;
734 
735  left = newstate(v->nfa);
736  right = newstate(v->nfa);
737  NOERRN();
738  EMPTYARC(init, left);
739  EMPTYARC(right, final);
740  NOERRN();
741  branch = parsebranch(v, stopper, type, left, right, 0);
742  NOERRN();
743  if (lastbranch)
744  lastbranch->sibling = branch;
745  else
746  branches->child = branch;
747  branches->flags |= UP(branches->flags | branch->flags);
748  lastbranch = branch;
749  } while (EAT('|'));
750  assert(SEE(stopper) || SEE(EOS));
751 
752  if (!SEE(stopper))
753  {
754  assert(stopper == ')' && SEE(EOS));
755  ERR(REG_EPAREN);
756  }
757 
758  /* optimize out simple cases */
759  if (lastbranch == branches->child)
760  { /* only one branch */
761  assert(lastbranch->sibling == NULL);
762  freesrnode(v, branches);
763  branches = lastbranch;
764  }
765  else if (!MESSY(branches->flags))
766  { /* no interesting innards */
767  freesubreandsiblings(v, branches->child);
768  branches->child = NULL;
769  branches->op = '=';
770  }
771 
772  return branches;
773 }
774 
775 /*
776  * parsebranch - parse one branch of an RE
777  *
778  * This mostly manages concatenation, working closely with parseqatom().
779  * Concatenated things are bundled up as much as possible, with separate
780  * '.' nodes introduced only when necessary due to substructure.
781  */
782 static struct subre *
783 parsebranch(struct vars *v,
784  int stopper, /* EOS or ')' */
785  int type, /* LACON (lookaround subRE) or PLAIN */
786  struct state *left, /* leftmost state */
787  struct state *right, /* rightmost state */
788  int partial) /* is this only part of a branch? */
789 {
790  struct state *lp; /* left end of current construct */
791  int seencontent; /* is there anything in this branch yet? */
792  struct subre *t;
793 
794  lp = left;
795  seencontent = 0;
796  t = subre(v, '=', 0, left, right); /* op '=' is tentative */
797  NOERRN();
798  while (!SEE('|') && !SEE(stopper) && !SEE(EOS))
799  {
800  if (seencontent)
801  { /* implicit concat operator */
802  lp = newstate(v->nfa);
803  NOERRN();
804  moveins(v->nfa, right, lp);
805  }
806  seencontent = 1;
807 
808  /* NB, recursion in parseqatom() may swallow rest of branch */
809  t = parseqatom(v, stopper, type, lp, right, t);
810  NOERRN();
811  }
812 
813  if (!seencontent)
814  { /* empty branch */
815  if (!partial)
816  NOTE(REG_UUNSPEC);
817  assert(lp == left);
818  EMPTYARC(left, right);
819  }
820 
821  return t;
822 }
823 
824 /*
825  * parseqatom - parse one quantified atom or constraint of an RE
826  *
827  * The bookkeeping near the end cooperates very closely with parsebranch();
828  * in particular, it contains a recursion that can involve parsing the rest
829  * of the branch, making this function's name somewhat inaccurate.
830  *
831  * Usually, the return value is just "top", but in some cases where we
832  * have parsed the rest of the branch, we may deem "top" redundant and
833  * free it, returning some child subre instead.
834  */
835 static struct subre *
836 parseqatom(struct vars *v,
837  int stopper, /* EOS or ')' */
838  int type, /* LACON (lookaround subRE) or PLAIN */
839  struct state *lp, /* left state to hang it on */
840  struct state *rp, /* right state to hang it on */
841  struct subre *top) /* subtree top */
842 {
843  struct state *s; /* temporaries for new states */
844  struct state *s2;
845 
846 #define ARCV(t, val) newarc(v->nfa, t, val, lp, rp)
847  int m,
848  n;
849  struct subre *atom; /* atom's subtree */
850  struct subre *t;
851  int cap; /* capturing parens? */
852  int latype; /* lookaround constraint type */
853  int subno; /* capturing-parens or backref number */
854  int atomtype;
855  int qprefer; /* quantifier short/long preference */
856  int f;
857  struct subre **atomp; /* where the pointer to atom is */
858 
859  /* initial bookkeeping */
860  atom = NULL;
861  assert(lp->nouts == 0); /* must string new code */
862  assert(rp->nins == 0); /* between lp and rp */
863  subno = 0; /* just to shut lint up */
864 
865  /* an atom or constraint... */
866  atomtype = v->nexttype;
867  switch (atomtype)
868  {
869  /* first, constraints, which end by returning */
870  case '^':
871  ARCV('^', 1);
872  if (v->cflags & REG_NLANCH)
873  ARCV(BEHIND, v->nlcolor);
874  NEXT();
875  return top;
876  break;
877  case '$':
878  ARCV('$', 1);
879  if (v->cflags & REG_NLANCH)
880  ARCV(AHEAD, v->nlcolor);
881  NEXT();
882  return top;
883  break;
884  case SBEGIN:
885  ARCV('^', 1); /* BOL */
886  ARCV('^', 0); /* or BOS */
887  NEXT();
888  return top;
889  break;
890  case SEND:
891  ARCV('$', 1); /* EOL */
892  ARCV('$', 0); /* or EOS */
893  NEXT();
894  return top;
895  break;
896  case '<':
897  wordchrs(v);
898  s = newstate(v->nfa);
899  NOERRN();
900  nonword(v, BEHIND, lp, s);
901  word(v, AHEAD, s, rp);
902  NEXT();
903  return top;
904  break;
905  case '>':
906  wordchrs(v);
907  s = newstate(v->nfa);
908  NOERRN();
909  word(v, BEHIND, lp, s);
910  nonword(v, AHEAD, s, rp);
911  NEXT();
912  return top;
913  break;
914  case WBDRY:
915  wordchrs(v);
916  s = newstate(v->nfa);
917  NOERRN();
918  nonword(v, BEHIND, lp, s);
919  word(v, AHEAD, s, rp);
920  s = newstate(v->nfa);
921  NOERRN();
922  word(v, BEHIND, lp, s);
923  nonword(v, AHEAD, s, rp);
924  NEXT();
925  return top;
926  break;
927  case NWBDRY:
928  wordchrs(v);
929  s = newstate(v->nfa);
930  NOERRN();
931  word(v, BEHIND, lp, s);
932  word(v, AHEAD, s, rp);
933  s = newstate(v->nfa);
934  NOERRN();
935  nonword(v, BEHIND, lp, s);
936  nonword(v, AHEAD, s, rp);
937  NEXT();
938  return top;
939  break;
940  case LACON: /* lookaround constraint */
941  latype = v->nextvalue;
942  NEXT();
943  s = newstate(v->nfa);
944  s2 = newstate(v->nfa);
945  NOERRN();
946  t = parse(v, ')', LACON, s, s2);
947  freesubre(v, t); /* internal structure irrelevant */
948  NOERRN();
949  assert(SEE(')'));
950  NEXT();
951  processlacon(v, s, s2, latype, lp, rp);
952  return top;
953  break;
954  /* then errors, to get them out of the way */
955  case '*':
956  case '+':
957  case '?':
958  case '{':
959  ERR(REG_BADRPT);
960  return top;
961  break;
962  default:
963  ERR(REG_ASSERT);
964  return top;
965  break;
966  /* then plain characters, and minor variants on that theme */
967  case ')': /* unbalanced paren */
968  if ((v->cflags & REG_ADVANCED) != REG_EXTENDED)
969  {
970  ERR(REG_EPAREN);
971  return top;
972  }
973  /* legal in EREs due to specification botch */
974  NOTE(REG_UPBOTCH);
975  /* fall through into case PLAIN */
976  /* FALLTHROUGH */
977  case PLAIN:
978  onechr(v, v->nextvalue, lp, rp);
979  okcolors(v->nfa, v->cm);
980  NOERRN();
981  NEXT();
982  break;
983  case '[':
984  if (v->nextvalue == 1)
985  bracket(v, lp, rp);
986  else
987  cbracket(v, lp, rp);
988  assert(SEE(']') || ISERR());
989  NEXT();
990  break;
991  case CCLASSS:
992  charclass(v, (enum char_classes) v->nextvalue, lp, rp);
993  okcolors(v->nfa, v->cm);
994  NEXT();
995  break;
996  case CCLASSC:
997  charclasscomplement(v, (enum char_classes) v->nextvalue, lp, rp);
998  /* charclasscomplement() did okcolors() internally */
999  NEXT();
1000  break;
1001  case '.':
1002  rainbow(v->nfa, v->cm, PLAIN,
1003  (v->cflags & REG_NLSTOP) ? v->nlcolor : COLORLESS,
1004  lp, rp);
1005  NEXT();
1006  break;
1007  /* and finally the ugly stuff */
1008  case '(': /* value flags as capturing or non */
1009  cap = (type == LACON) ? 0 : v->nextvalue;
1010  if (cap)
1011  {
1012  v->nsubexp++;
1013  subno = v->nsubexp;
1014  if ((size_t) subno >= v->nsubs)
1015  moresubs(v, subno);
1016  }
1017  else
1018  atomtype = PLAIN; /* something that's not '(' */
1019  NEXT();
1020 
1021  /*
1022  * Make separate endpoint states to keep this sub-NFA distinct
1023  * from what surrounds it. We need to be sure that when we
1024  * duplicate the sub-NFA for a backref, we get the right
1025  * states/arcs and no others. In particular, letting a backref
1026  * duplicate the sub-NFA from lp to rp would be quite wrong,
1027  * because we may add quantification superstructure around this
1028  * atom below. (Perhaps we could skip the extra states for
1029  * non-capturing parens, but it seems not worth the trouble.)
1030  */
1031  s = newstate(v->nfa);
1032  s2 = newstate(v->nfa);
1033  NOERRN();
1034  /* We may not need these arcs, but keep things connected for now */
1035  EMPTYARC(lp, s);
1036  EMPTYARC(s2, rp);
1037  NOERRN();
1038  atom = parse(v, ')', type, s, s2);
1039  assert(SEE(')') || ISERR());
1040  NEXT();
1041  NOERRN();
1042  if (cap)
1043  {
1044  if (atom->capno == 0)
1045  {
1046  /* normal case: just mark the atom as capturing */
1047  atom->flags |= CAP;
1048  atom->capno = subno;
1049  }
1050  else
1051  {
1052  /* generate no-op wrapper node to handle "((x))" */
1053  t = subre(v, '(', atom->flags | CAP, s, s2);
1054  NOERRN();
1055  t->capno = subno;
1056  t->child = atom;
1057  atom = t;
1058  }
1059  assert(v->subs[subno] == NULL);
1060  v->subs[subno] = atom;
1061  }
1062  /* postpone everything else pending possible {0} */
1063  break;
1064  case BACKREF: /* the Feature From The Black Lagoon */
1065  INSIST(type != LACON, REG_ESUBREG);
1066  subno = v->nextvalue;
1067  assert(subno > 0);
1068  INSIST(subno < v->nsubs, REG_ESUBREG);
1069  NOERRN();
1070  INSIST(v->subs[subno] != NULL, REG_ESUBREG);
1071  NOERRN();
1072  atom = subre(v, 'b', BACKR, lp, rp);
1073  NOERRN();
1074  atom->backno = subno;
1075  v->subs[subno]->flags |= BRUSE;
1076  EMPTYARC(lp, rp); /* temporarily, so there's something */
1077  NEXT();
1078  break;
1079  }
1080 
1081  /* ...and an atom may be followed by a quantifier */
1082  switch (v->nexttype)
1083  {
1084  case '*':
1085  m = 0;
1086  n = DUPINF;
1087  qprefer = (v->nextvalue) ? LONGER : SHORTER;
1088  NEXT();
1089  break;
1090  case '+':
1091  m = 1;
1092  n = DUPINF;
1093  qprefer = (v->nextvalue) ? LONGER : SHORTER;
1094  NEXT();
1095  break;
1096  case '?':
1097  m = 0;
1098  n = 1;
1099  qprefer = (v->nextvalue) ? LONGER : SHORTER;
1100  NEXT();
1101  break;
1102  case '{':
1103  NEXT();
1104  m = scannum(v);
1105  if (EAT(','))
1106  {
1107  if (SEE(DIGIT))
1108  n = scannum(v);
1109  else
1110  n = DUPINF;
1111  if (m > n)
1112  {
1113  ERR(REG_BADBR);
1114  return top;
1115  }
1116  /* {m,n} exercises preference, even if it's {m,m} */
1117  qprefer = (v->nextvalue) ? LONGER : SHORTER;
1118  }
1119  else
1120  {
1121  n = m;
1122  /* {m} passes operand's preference through */
1123  qprefer = 0;
1124  }
1125  if (!SEE('}'))
1126  { /* catches errors too */
1127  ERR(REG_BADBR);
1128  return top;
1129  }
1130  NEXT();
1131  break;
1132  default: /* no quantifier */
1133  m = n = 1;
1134  qprefer = 0;
1135  break;
1136  }
1137 
1138  /* annoying special case: {0} or {0,0} cancels everything */
1139  if (m == 0 && n == 0)
1140  {
1141  /*
1142  * If we had capturing subexpression(s) within the atom, we don't want
1143  * to destroy them, because it's legal (if useless) to back-ref them
1144  * later. Hence, just unlink the atom from lp/rp and then ignore it.
1145  */
1146  if (atom != NULL && (atom->flags & CAP))
1147  {
1148  delsub(v->nfa, lp, atom->begin);
1149  delsub(v->nfa, atom->end, rp);
1150  }
1151  else
1152  {
1153  /* Otherwise, we can clean up any subre infrastructure we made */
1154  if (atom != NULL)
1155  freesubre(v, atom);
1156  delsub(v->nfa, lp, rp);
1157  }
1158  EMPTYARC(lp, rp);
1159  return top;
1160  }
1161 
1162  /* if not a messy case, avoid hard part */
1163  assert(!MESSY(top->flags));
1164  f = top->flags | qprefer | ((atom != NULL) ? atom->flags : 0);
1165  if (atomtype != '(' && atomtype != BACKREF && !MESSY(UP(f)))
1166  {
1167  if (!(m == 1 && n == 1))
1168  repeat(v, lp, rp, m, n);
1169  if (atom != NULL)
1170  freesubre(v, atom);
1171  top->flags = f;
1172  return top;
1173  }
1174 
1175  /*
1176  * hard part: something messy
1177  *
1178  * That is, capturing parens, back reference, short/long clash, or an atom
1179  * with substructure containing one of those.
1180  */
1181 
1182  /* now we'll need a subre for the contents even if they're boring */
1183  if (atom == NULL)
1184  {
1185  atom = subre(v, '=', 0, lp, rp);
1186  NOERRN();
1187  }
1188 
1189  /*
1190  * For what follows, we need the atom to have its own begin/end states
1191  * that are distinct from lp/rp, so that we can wrap iteration structure
1192  * around it. The parenthesized-atom case above already made suitable
1193  * states (and we don't want to modify a capturing subre, since it's
1194  * already recorded in v->subs[]). Otherwise, we need more states.
1195  */
1196  if (atom->begin == lp || atom->end == rp)
1197  {
1198  s = newstate(v->nfa);
1199  s2 = newstate(v->nfa);
1200  NOERRN();
1201  moveouts(v->nfa, lp, s);
1202  moveins(v->nfa, rp, s2);
1203  atom->begin = s;
1204  atom->end = s2;
1205  }
1206  else
1207  {
1208  /* The atom's OK, but we must temporarily disconnect it from lp/rp */
1209  /* (this removes the EMPTY arcs we made above) */
1210  delsub(v->nfa, lp, atom->begin);
1211  delsub(v->nfa, atom->end, rp);
1212  }
1213 
1214  /*----------
1215  * Prepare a general-purpose state skeleton.
1216  *
1217  * In the no-backrefs case, we want this:
1218  *
1219  * [lp] ---> [s] ---prefix---> ---atom---> ---rest---> [rp]
1220  *
1221  * where prefix is some repetitions of atom, and "rest" is the remainder
1222  * of the branch. In the general case we need:
1223  *
1224  * [lp] ---> [s] ---iterator---> [s2] ---rest---> [rp]
1225  *
1226  * where the iterator wraps around the atom.
1227  *
1228  * We make the s state here for both cases; s2 is made below if needed
1229  *----------
1230  */
1231  s = newstate(v->nfa); /* set up starting state */
1232  NOERRN();
1233  EMPTYARC(lp, s);
1234  NOERRN();
1235 
1236  /* break remaining subRE into x{...} and what follows */
1237  t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp);
1238  NOERRN();
1239  t->child = atom;
1240  atomp = &t->child;
1241 
1242  /*
1243  * Here we should recurse to fill t->child->sibling ... but we must
1244  * postpone that to the end. One reason is that t->child may be replaced
1245  * below, and we don't want to worry about its sibling link.
1246  */
1247 
1248  /*
1249  * Convert top node to a concatenation of the prefix (top->child, covering
1250  * whatever we parsed previously) and remaining (t). Note that the prefix
1251  * could be empty, in which case this concatenation node is unnecessary.
1252  * To keep things simple, we operate in a general way for now, and get rid
1253  * of unnecessary subres below.
1254  */
1255  assert(top->op == '=' && top->child == NULL);
1256  top->child = subre(v, '=', top->flags, top->begin, lp);
1257  NOERRN();
1258  top->op = '.';
1259  top->child->sibling = t;
1260  /* top->flags will get updated later */
1261 
1262  /* if it's a backref, now is the time to replicate the subNFA */
1263  if (atomtype == BACKREF)
1264  {
1265  assert(atom->begin->nouts == 1); /* just the EMPTY */
1266  delsub(v->nfa, atom->begin, atom->end);
1267  assert(v->subs[subno] != NULL);
1268 
1269  /*
1270  * And here's why the recursion got postponed: it must wait until the
1271  * skeleton is filled in, because it may hit a backref that wants to
1272  * copy the filled-in skeleton.
1273  */
1274  dupnfa(v->nfa, v->subs[subno]->begin, v->subs[subno]->end,
1275  atom->begin, atom->end);
1276  NOERRN();
1277 
1278  /* The backref node's NFA should not enforce any constraints */
1279  removeconstraints(v->nfa, atom->begin, atom->end);
1280  NOERRN();
1281  }
1282 
1283  /*
1284  * It's quantifier time. If the atom is just a backref, we'll let it deal
1285  * with quantifiers internally.
1286  */
1287  if (atomtype == BACKREF)
1288  {
1289  /* special case: backrefs have internal quantifiers */
1290  EMPTYARC(s, atom->begin); /* empty prefix */
1291  /* just stuff everything into atom */
1292  repeat(v, atom->begin, atom->end, m, n);
1293  atom->min = (short) m;
1294  atom->max = (short) n;
1295  atom->flags |= COMBINE(qprefer, atom->flags);
1296  /* rest of branch can be strung starting from atom->end */
1297  s2 = atom->end;
1298  }
1299  else if (m == 1 && n == 1 &&
1300  (qprefer == 0 ||
1301  (atom->flags & (LONGER | SHORTER | MIXED)) == 0 ||
1302  qprefer == (atom->flags & (LONGER | SHORTER | MIXED))))
1303  {
1304  /* no/vacuous quantifier: done */
1305  EMPTYARC(s, atom->begin); /* empty prefix */
1306  /* rest of branch can be strung starting from atom->end */
1307  s2 = atom->end;
1308  }
1309  else if (!(atom->flags & (CAP | BACKR)))
1310  {
1311  /*
1312  * If there's no captures nor backrefs in the atom being repeated, we
1313  * don't really care where the submatches of the iteration are, so we
1314  * don't need an iteration node. Make a plain DFA node instead.
1315  */
1316  EMPTYARC(s, atom->begin); /* empty prefix */
1317  repeat(v, atom->begin, atom->end, m, n);
1318  f = COMBINE(qprefer, atom->flags);
1319  t = subre(v, '=', f, atom->begin, atom->end);
1320  NOERRN();
1321  freesubre(v, atom);
1322  *atomp = t;
1323  /* rest of branch can be strung starting from t->end */
1324  s2 = t->end;
1325  }
1326  else if (m > 0 && !(atom->flags & BACKR))
1327  {
1328  /*
1329  * If there's no backrefs involved, we can turn x{m,n} into
1330  * x{m-1,n-1}x, with capturing parens in only the second x. This is
1331  * valid because we only care about capturing matches from the final
1332  * iteration of the quantifier. It's a win because we can implement
1333  * the backref-free left side as a plain DFA node, since we don't
1334  * really care where its submatches are.
1335  */
1336  dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin);
1337  assert(m >= 1 && m != DUPINF && n >= 1);
1338  repeat(v, s, atom->begin, m - 1, (n == DUPINF) ? n : n - 1);
1339  f = COMBINE(qprefer, atom->flags);
1340  t = subre(v, '.', f, s, atom->end); /* prefix and atom */
1341  NOERRN();
1342  t->child = subre(v, '=', PREF(f), s, atom->begin);
1343  NOERRN();
1344  t->child->sibling = atom;
1345  *atomp = t;
1346  /* rest of branch can be strung starting from atom->end */
1347  s2 = atom->end;
1348  }
1349  else
1350  {
1351  /* general case: need an iteration node */
1352  s2 = newstate(v->nfa);
1353  NOERRN();
1354  moveouts(v->nfa, atom->end, s2);
1355  NOERRN();
1356  dupnfa(v->nfa, atom->begin, atom->end, s, s2);
1357  repeat(v, s, s2, m, n);
1358  f = COMBINE(qprefer, atom->flags);
1359  t = subre(v, '*', f, s, s2);
1360  NOERRN();
1361  t->min = (short) m;
1362  t->max = (short) n;
1363  t->child = atom;
1364  *atomp = t;
1365  /* rest of branch is to be strung from iteration's end state */
1366  }
1367 
1368  /* and finally, look after that postponed recursion */
1369  t = top->child->sibling;
1370  if (!(SEE('|') || SEE(stopper) || SEE(EOS)))
1371  {
1372  /* parse all the rest of the branch, and insert in t->child->sibling */
1373  t->child->sibling = parsebranch(v, stopper, type, s2, rp, 1);
1374  NOERRN();
1375  assert(SEE('|') || SEE(stopper) || SEE(EOS));
1376 
1377  /* here's the promised update of the flags */
1378  t->flags |= COMBINE(t->flags, t->child->sibling->flags);
1379  top->flags |= COMBINE(top->flags, t->flags);
1380 
1381  /* neither t nor top could be directly marked for capture as yet */
1382  assert(t->capno == 0);
1383  assert(top->capno == 0);
1384 
1385  /*
1386  * At this point both top and t are concatenation (op == '.') subres,
1387  * and we have top->child = prefix of branch, top->child->sibling = t,
1388  * t->child = messy atom (with quantification superstructure if
1389  * needed), t->child->sibling = rest of branch.
1390  *
1391  * If the messy atom was the first thing in the branch, then
1392  * top->child is vacuous and we can get rid of one level of
1393  * concatenation.
1394  */
1395  assert(top->child->op == '=');
1396  if (top->child->begin == top->child->end)
1397  {
1398  assert(!MESSY(top->child->flags));
1399  freesubre(v, top->child);
1400  top->child = t->child;
1401  freesrnode(v, t);
1402  }
1403 
1404  /*
1405  * Otherwise, it's possible that t->child is not messy in itself, but
1406  * we considered it messy because its greediness conflicts with what
1407  * preceded it. Then it could be that the combination of t->child and
1408  * the rest of the branch is also not messy, in which case we can get
1409  * rid of the child concatenation by merging t->child and the rest of
1410  * the branch into one plain DFA node.
1411  */
1412  else if (t->child->op == '=' &&
1413  t->child->sibling->op == '=' &&
1414  !MESSY(UP(t->child->flags | t->child->sibling->flags)))
1415  {
1416  t->op = '=';
1417  t->flags = COMBINE(t->child->flags, t->child->sibling->flags);
1418  freesubreandsiblings(v, t->child);
1419  t->child = NULL;
1420  }
1421  }
1422  else
1423  {
1424  /*
1425  * There's nothing left in the branch, so we don't need the second
1426  * concatenation node 't'. Just link s2 straight to rp.
1427  */
1428  EMPTYARC(s2, rp);
1429  top->child->sibling = t->child;
1430  top->flags |= COMBINE(top->flags, top->child->sibling->flags);
1431  freesrnode(v, t);
1432 
1433  /*
1434  * Again, it could be that top->child is vacuous (if the messy atom
1435  * was in fact the only thing in the branch). In that case we need no
1436  * concatenation at all; just replace top with top->child->sibling.
1437  */
1438  assert(top->child->op == '=');
1439  if (top->child->begin == top->child->end)
1440  {
1441  assert(!MESSY(top->child->flags));
1442  t = top->child->sibling;
1443  top->child->sibling = NULL;
1444  freesubre(v, top);
1445  top = t;
1446  }
1447  }
1448 
1449  return top;
1450 }
1451 
1452 /*
1453  * nonword - generate arcs for non-word-character ahead or behind
1454  */
1455 static void
1456 nonword(struct vars *v,
1457  int dir, /* AHEAD or BEHIND */
1458  struct state *lp,
1459  struct state *rp)
1460 {
1461  int anchor = (dir == AHEAD) ? '$' : '^';
1462 
1463  assert(dir == AHEAD || dir == BEHIND);
1464  newarc(v->nfa, anchor, 1, lp, rp);
1465  newarc(v->nfa, anchor, 0, lp, rp);
1466  colorcomplement(v->nfa, v->cm, dir, v->wordchrs, lp, rp);
1467  /* (no need for special attention to \n) */
1468 }
1469 
1470 /*
1471  * word - generate arcs for word character ahead or behind
1472  */
1473 static void
1474 word(struct vars *v,
1475  int dir, /* AHEAD or BEHIND */
1476  struct state *lp,
1477  struct state *rp)
1478 {
1479  assert(dir == AHEAD || dir == BEHIND);
1480  cloneouts(v->nfa, v->wordchrs, lp, rp, dir);
1481  /* (no need for special attention to \n) */
1482 }
1483 
1484 /*
1485  * charclass - generate arcs for a character class
1486  *
1487  * This is used for both atoms (\w and sibling escapes) and for elements
1488  * of bracket expressions. The caller is responsible for calling okcolors()
1489  * at the end of processing the atom or bracket.
1490  */
1491 static void
1492 charclass(struct vars *v,
1493  enum char_classes cls,
1494  struct state *lp,
1495  struct state *rp)
1496 {
1497  struct cvec *cv;
1498 
1499  /* obtain possibly-cached cvec for char class */
1500  NOTE(REG_ULOCALE);
1501  cv = cclasscvec(v, cls, (v->cflags & REG_ICASE));
1502  NOERR();
1503 
1504  /* build the arcs; this may cause color splitting */
1505  subcolorcvec(v, cv, lp, rp);
1506 }
1507 
1508 /*
1509  * charclasscomplement - generate arcs for a complemented character class
1510  *
1511  * This is used for both atoms (\W and sibling escapes) and for elements
1512  * of bracket expressions. In bracket expressions, it is the caller's
1513  * responsibility that there not be any open subcolors when this is called.
1514  */
1515 static void
1516 charclasscomplement(struct vars *v,
1517  enum char_classes cls,
1518  struct state *lp,
1519  struct state *rp)
1520 {
1521  struct state *cstate;
1522  struct cvec *cv;
1523 
1524  /* make dummy state to hang temporary arcs on */
1525  cstate = newstate(v->nfa);
1526  NOERR();
1527 
1528  /* obtain possibly-cached cvec for char class */
1529  NOTE(REG_ULOCALE);
1530  cv = cclasscvec(v, cls, (v->cflags & REG_ICASE));
1531  NOERR();
1532 
1533  /* build arcs for char class; this may cause color splitting */
1534  subcolorcvec(v, cv, cstate, cstate);
1535  NOERR();
1536 
1537  /* clean up any subcolors in the arc set */
1538  okcolors(v->nfa, v->cm);
1539  NOERR();
1540 
1541  /* now build output arcs for the complement of the char class */
1542  colorcomplement(v->nfa, v->cm, PLAIN, cstate, lp, rp);
1543  NOERR();
1544 
1545  /* clean up dummy state */
1546  dropstate(v->nfa, cstate);
1547 }
1548 
1549 /*
1550  * scannum - scan a number
1551  */
1552 static int /* value, <= DUPMAX */
1553 scannum(struct vars *v)
1554 {
1555  int n = 0;
1556 
1557  while (SEE(DIGIT) && n < DUPMAX)
1558  {
1559  n = n * 10 + v->nextvalue;
1560  NEXT();
1561  }
1562  if (SEE(DIGIT) || n > DUPMAX)
1563  {
1564  ERR(REG_BADBR);
1565  return 0;
1566  }
1567  return n;
1568 }
1569 
1570 /*
1571  * repeat - replicate subNFA for quantifiers
1572  *
1573  * The sub-NFA strung from lp to rp is modified to represent m to n
1574  * repetitions of its initial contents.
1575  *
1576  * The duplication sequences used here are chosen carefully so that any
1577  * pointers starting out pointing into the subexpression end up pointing into
1578  * the last occurrence. (Note that it may not be strung between the same
1579  * left and right end states, however!) This used to be important for the
1580  * subRE tree, although the important bits are now handled by the in-line
1581  * code in parse(), and when this is called, it doesn't matter any more.
1582  */
1583 static void
1584 repeat(struct vars *v,
1585  struct state *lp,
1586  struct state *rp,
1587  int m,
1588  int n)
1589 {
1590 #define SOME 2
1591 #define INF 3
1592 #define PAIR(x, y) ((x)*4 + (y))
1593 #define REDUCE(x) ( ((x) == DUPINF) ? INF : (((x) > 1) ? SOME : (x)) )
1594  const int rm = REDUCE(m);
1595  const int rn = REDUCE(n);
1596  struct state *s;
1597  struct state *s2;
1598 
1599  switch (PAIR(rm, rn))
1600  {
1601  case PAIR(0, 0): /* empty string */
1602  delsub(v->nfa, lp, rp);
1603  EMPTYARC(lp, rp);
1604  break;
1605  case PAIR(0, 1): /* do as x| */
1606  EMPTYARC(lp, rp);
1607  break;
1608  case PAIR(0, SOME): /* do as x{1,n}| */
1609  repeat(v, lp, rp, 1, n);
1610  NOERR();
1611  EMPTYARC(lp, rp);
1612  break;
1613  case PAIR(0, INF): /* loop x around */
1614  s = newstate(v->nfa);
1615  NOERR();
1616  moveouts(v->nfa, lp, s);
1617  moveins(v->nfa, rp, s);
1618  EMPTYARC(lp, s);
1619  EMPTYARC(s, rp);
1620  break;
1621  case PAIR(1, 1): /* no action required */
1622  break;
1623  case PAIR(1, SOME): /* do as x{0,n-1}x = (x{1,n-1}|)x */
1624  s = newstate(v->nfa);
1625  NOERR();
1626  moveouts(v->nfa, lp, s);
1627  dupnfa(v->nfa, s, rp, lp, s);
1628  NOERR();
1629  repeat(v, lp, s, 1, n - 1);
1630  NOERR();
1631  EMPTYARC(lp, s);
1632  break;
1633  case PAIR(1, INF): /* add loopback arc */
1634  s = newstate(v->nfa);
1635  s2 = newstate(v->nfa);
1636  NOERR();
1637  moveouts(v->nfa, lp, s);
1638  moveins(v->nfa, rp, s2);
1639  EMPTYARC(lp, s);
1640  EMPTYARC(s2, rp);
1641  EMPTYARC(s2, s);
1642  break;
1643  case PAIR(SOME, SOME): /* do as x{m-1,n-1}x */
1644  s = newstate(v->nfa);
1645  NOERR();
1646  moveouts(v->nfa, lp, s);
1647  dupnfa(v->nfa, s, rp, lp, s);
1648  NOERR();
1649  repeat(v, lp, s, m - 1, n - 1);
1650  break;
1651  case PAIR(SOME, INF): /* do as x{m-1,}x */
1652  s = newstate(v->nfa);
1653  NOERR();
1654  moveouts(v->nfa, lp, s);
1655  dupnfa(v->nfa, s, rp, lp, s);
1656  NOERR();
1657  repeat(v, lp, s, m - 1, n);
1658  break;
1659  default:
1660  ERR(REG_ASSERT);
1661  break;
1662  }
1663 }
1664 
1665 /*
1666  * bracket - handle non-complemented bracket expression
1667  *
1668  * Also called from cbracket for complemented bracket expressions.
1669  */
1670 static void
1671 bracket(struct vars *v,
1672  struct state *lp,
1673  struct state *rp)
1674 {
1675  /*
1676  * We can't process complemented char classes (e.g. \W) immediately while
1677  * scanning the bracket expression, else color bookkeeping gets confused.
1678  * Instead, remember whether we saw any in have_cclassc[], and process
1679  * them at the end.
1680  */
1681  bool have_cclassc[NUM_CCLASSES];
1682  bool any_cclassc;
1683  int i;
1684 
1685  memset(have_cclassc, false, sizeof(have_cclassc));
1686 
1687  assert(SEE('['));
1688  NEXT();
1689  while (!SEE(']') && !SEE(EOS))
1690  brackpart(v, lp, rp, have_cclassc);
1691  assert(SEE(']') || ISERR());
1692 
1693  /* close up open subcolors from the positive bracket elements */
1694  okcolors(v->nfa, v->cm);
1695  NOERR();
1696 
1697  /* now handle any complemented elements */
1698  any_cclassc = false;
1699  for (i = 0; i < NUM_CCLASSES; i++)
1700  {
1701  if (have_cclassc[i])
1702  {
1703  charclasscomplement(v, (enum char_classes) i, lp, rp);
1704  NOERR();
1705  any_cclassc = true;
1706  }
1707  }
1708 
1709  /*
1710  * If we had any complemented elements, see if we can optimize the bracket
1711  * into a rainbow. Since a complemented element is the only way a WHITE
1712  * arc could get into the result, there's no point in checking otherwise.
1713  */
1714  if (any_cclassc)
1715  optimizebracket(v, lp, rp);
1716 }
1717 
1718 /*
1719  * cbracket - handle complemented bracket expression
1720  *
1721  * We do it by calling bracket() with dummy endpoints, and then complementing
1722  * the result. The alternative would be to invoke rainbow(), and then delete
1723  * arcs as the b.e. is seen... but that gets messy, and is really quite
1724  * infeasible now that rainbow() just puts out one RAINBOW arc.
1725  */
1726 static void
1727 cbracket(struct vars *v,
1728  struct state *lp,
1729  struct state *rp)
1730 {
1731  struct state *left = newstate(v->nfa);
1732  struct state *right = newstate(v->nfa);
1733 
1734  NOERR();
1735  bracket(v, left, right);
1736 
1737  /* in NLSTOP mode, ensure newline is not part of the result set */
1738  if (v->cflags & REG_NLSTOP)
1739  newarc(v->nfa, PLAIN, v->nlcolor, left, right);
1740  NOERR();
1741 
1742  assert(lp->nouts == 0); /* all outarcs will be ours */
1743 
1744  /*
1745  * Easy part of complementing, and all there is to do since the MCCE code
1746  * was removed. Note that the result of colorcomplement() cannot be a
1747  * rainbow, since we don't allow empty brackets; so there's no point in
1748  * calling optimizebracket() again.
1749  */
1750  colorcomplement(v->nfa, v->cm, PLAIN, left, lp, rp);
1751  NOERR();
1752  dropstate(v->nfa, left);
1753  assert(right->nins == 0);
1754  freestate(v->nfa, right);
1755 }
1756 
1757 /*
1758  * brackpart - handle one item (or range) within a bracket expression
1759  */
1760 static void
1761 brackpart(struct vars *v,
1762  struct state *lp,
1763  struct state *rp,
1764  bool *have_cclassc)
1765 {
1766  chr startc;
1767  chr endc;
1768  struct cvec *cv;
1769  enum char_classes cls;
1770  const chr *startp;
1771  const chr *endp;
1772 
1773  /* parse something, get rid of special cases, take shortcuts */
1774  switch (v->nexttype)
1775  {
1776  case RANGE: /* a-b-c or other botch */
1777  ERR(REG_ERANGE);
1778  return;
1779  break;
1780  case PLAIN:
1781  startc = v->nextvalue;
1782  NEXT();
1783  /* shortcut for ordinary chr (not range) */
1784  if (!SEE(RANGE))
1785  {
1786  onechr(v, startc, lp, rp);
1787  return;
1788  }
1789  NOERR();
1790  break;
1791  case COLLEL:
1792  startp = v->now;
1793  endp = scanplain(v);
1794  INSIST(startp < endp, REG_ECOLLATE);
1795  NOERR();
1796  startc = element(v, startp, endp);
1797  NOERR();
1798  break;
1799  case ECLASS:
1800  startp = v->now;
1801  endp = scanplain(v);
1802  INSIST(startp < endp, REG_ECOLLATE);
1803  NOERR();
1804  startc = element(v, startp, endp);
1805  NOERR();
1806  cv = eclass(v, startc, (v->cflags & REG_ICASE));
1807  NOERR();
1808  subcolorcvec(v, cv, lp, rp);
1809  return;
1810  break;
1811  case CCLASS:
1812  startp = v->now;
1813  endp = scanplain(v);
1814  INSIST(startp < endp, REG_ECTYPE);
1815  NOERR();
1816  cls = lookupcclass(v, startp, endp);
1817  NOERR();
1818  charclass(v, cls, lp, rp);
1819  return;
1820  break;
1821  case CCLASSS:
1822  charclass(v, (enum char_classes) v->nextvalue, lp, rp);
1823  NEXT();
1824  return;
1825  break;
1826  case CCLASSC:
1827  /* we cannot call charclasscomplement() immediately */
1828  have_cclassc[v->nextvalue] = true;
1829  NEXT();
1830  return;
1831  break;
1832  default:
1833  ERR(REG_ASSERT);
1834  return;
1835  break;
1836  }
1837 
1838  if (SEE(RANGE))
1839  {
1840  NEXT();
1841  switch (v->nexttype)
1842  {
1843  case PLAIN:
1844  case RANGE:
1845  endc = v->nextvalue;
1846  NEXT();
1847  NOERR();
1848  break;
1849  case COLLEL:
1850  startp = v->now;
1851  endp = scanplain(v);
1852  INSIST(startp < endp, REG_ECOLLATE);
1853  NOERR();
1854  endc = element(v, startp, endp);
1855  NOERR();
1856  break;
1857  default:
1858  ERR(REG_ERANGE);
1859  return;
1860  break;
1861  }
1862  }
1863  else
1864  endc = startc;
1865 
1866  /*
1867  * Ranges are unportable. Actually, standard C does guarantee that digits
1868  * are contiguous, but making that an exception is just too complicated.
1869  */
1870  if (startc != endc)
1871  NOTE(REG_UUNPORT);
1872  cv = range(v, startc, endc, (v->cflags & REG_ICASE));
1873  NOERR();
1874  subcolorcvec(v, cv, lp, rp);
1875 }
1876 
1877 /*
1878  * scanplain - scan PLAIN contents of [. etc.
1879  *
1880  * Certain bits of trickery in regc_lex.c know that this code does not try
1881  * to look past the final bracket of the [. etc.
1882  */
1883 static const chr * /* just after end of sequence */
1884 scanplain(struct vars *v)
1885 {
1886  const chr *endp;
1887 
1888  assert(SEE(COLLEL) || SEE(ECLASS) || SEE(CCLASS));
1889  NEXT();
1890 
1891  endp = v->now;
1892  while (SEE(PLAIN))
1893  {
1894  endp = v->now;
1895  NEXT();
1896  }
1897 
1898  assert(SEE(END) || ISERR());
1899  NEXT();
1900 
1901  return endp;
1902 }
1903 
1904 /*
1905  * onechr - fill in arcs for a plain character, and possible case complements
1906  * This is mostly a shortcut for efficient handling of the common case.
1907  */
1908 static void
1909 onechr(struct vars *v,
1910  chr c,
1911  struct state *lp,
1912  struct state *rp)
1913 {
1914  if (!(v->cflags & REG_ICASE))
1915  {
1916  color lastsubcolor = COLORLESS;
1917 
1918  subcoloronechr(v, c, lp, rp, &lastsubcolor);
1919  return;
1920  }
1921 
1922  /* rats, need general case anyway... */
1923  subcolorcvec(v, allcases(v, c), lp, rp);
1924 }
1925 
1926 /*
1927  * optimizebracket - see if bracket expression can be converted to RAINBOW
1928  *
1929  * Cases such as "[\s\S]" can produce a set of arcs of all colors, which we
1930  * can replace by a single RAINBOW arc for efficiency. (This might seem
1931  * like a silly way to write ".", but it's seemingly a common locution in
1932  * some other flavors of regex, so take the trouble to support it well.)
1933  */
1934 static void
1935 optimizebracket(struct vars *v,
1936  struct state *lp,
1937  struct state *rp)
1938 {
1939  struct colordesc *cd;
1940  struct colordesc *end = CDEND(v->cm);
1941  struct arc *a;
1942  bool israinbow;
1943 
1944  /*
1945  * Scan lp's out-arcs and transiently mark the mentioned colors. We
1946  * expect that all of lp's out-arcs are plain, non-RAINBOW arcs to rp.
1947  * (Note: there shouldn't be any pseudocolors yet, but check anyway.)
1948  */
1949  for (a = lp->outs; a != NULL; a = a->outchain)
1950  {
1951  assert(a->type == PLAIN);
1952  assert(a->co >= 0); /* i.e. not RAINBOW */
1953  assert(a->to == rp);
1954  cd = &v->cm->cd[a->co];
1955  assert(!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO));
1956  cd->flags |= COLMARK;
1957  }
1958 
1959  /* Scan colors, clear transient marks, check for unmarked live colors */
1960  israinbow = true;
1961  for (cd = v->cm->cd; cd < end; cd++)
1962  {
1963  if (cd->flags & COLMARK)
1964  cd->flags &= ~COLMARK;
1965  else if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO))
1966  israinbow = false;
1967  }
1968 
1969  /* Can't do anything if not all colors have arcs */
1970  if (!israinbow)
1971  return;
1972 
1973  /* OK, drop existing arcs and replace with a rainbow */
1974  while ((a = lp->outs) != NULL)
1975  freearc(v->nfa, a);
1976  newarc(v->nfa, PLAIN, RAINBOW, lp, rp);
1977 }
1978 
1979 /*
1980  * wordchrs - set up word-chr list for word-boundary stuff, if needed
1981  *
1982  * The list is kept as a bunch of circular arcs on an otherwise-unused state.
1983  *
1984  * Note that this must not be called while we have any open subcolors,
1985  * else construction of the list would confuse color bookkeeping.
1986  * Hence, we can't currently apply a similar optimization in
1987  * charclass[complement](), as those need to be usable within bracket
1988  * expressions.
1989  */
1990 static void
1991 wordchrs(struct vars *v)
1992 {
1993  struct state *cstate;
1994  struct cvec *cv;
1995 
1996  if (v->wordchrs != NULL)
1997  return; /* done already */
1998 
1999  /* make dummy state to hang the cache arcs on */
2000  cstate = newstate(v->nfa);
2001  NOERR();
2002 
2003  /* obtain possibly-cached cvec for \w characters */
2004  NOTE(REG_ULOCALE);
2005  cv = cclasscvec(v, CC_WORD, (v->cflags & REG_ICASE));
2006  NOERR();
2007 
2008  /* build the arcs; this may cause color splitting */
2009  subcolorcvec(v, cv, cstate, cstate);
2010  NOERR();
2011 
2012  /* close new open subcolors to ensure the cache entry is self-contained */
2013  okcolors(v->nfa, v->cm);
2014  NOERR();
2015 
2016  /* success! save the cache pointer */
2017  v->wordchrs = cstate;
2018 }
2019 
2020 /*
2021  * processlacon - generate the NFA representation of a LACON
2022  *
2023  * In the general case this is just newlacon() + newarc(), but some cases
2024  * can be optimized.
2025  */
2026 static void
2027 processlacon(struct vars *v,
2028  struct state *begin, /* start of parsed LACON sub-re */
2029  struct state *end, /* end of parsed LACON sub-re */
2030  int latype,
2031  struct state *lp, /* left state to hang it on */
2032  struct state *rp) /* right state to hang it on */
2033 {
2034  struct state *s1;
2035  int n;
2036 
2037  /*
2038  * Check for lookaround RE consisting of a single plain color arc (or set
2039  * of arcs); this would typically be a simple chr or a bracket expression.
2040  */
2041  s1 = single_color_transition(begin, end);
2042  switch (latype)
2043  {
2044  case LATYPE_AHEAD_POS:
2045  /* If lookahead RE is just colorset C, convert to AHEAD(C) */
2046  if (s1 != NULL)
2047  {
2048  cloneouts(v->nfa, s1, lp, rp, AHEAD);
2049  return;
2050  }
2051  break;
2052  case LATYPE_AHEAD_NEG:
2053  /* If lookahead RE is just colorset C, convert to AHEAD(^C)|$ */
2054  if (s1 != NULL)
2055  {
2056  colorcomplement(v->nfa, v->cm, AHEAD, s1, lp, rp);
2057  newarc(v->nfa, '$', 1, lp, rp);
2058  newarc(v->nfa, '$', 0, lp, rp);
2059  return;
2060  }
2061  break;
2062  case LATYPE_BEHIND_POS:
2063  /* If lookbehind RE is just colorset C, convert to BEHIND(C) */
2064  if (s1 != NULL)
2065  {
2066  cloneouts(v->nfa, s1, lp, rp, BEHIND);
2067  return;
2068  }
2069  break;
2070  case LATYPE_BEHIND_NEG:
2071  /* If lookbehind RE is just colorset C, convert to BEHIND(^C)|^ */
2072  if (s1 != NULL)
2073  {
2074  colorcomplement(v->nfa, v->cm, BEHIND, s1, lp, rp);
2075  newarc(v->nfa, '^', 1, lp, rp);
2076  newarc(v->nfa, '^', 0, lp, rp);
2077  return;
2078  }
2079  break;
2080  default:
2081  assert(NOTREACHED);
2082  }
2083 
2084  /* General case: we need a LACON subre and arc */
2085  n = newlacon(v, begin, end, latype);
2086  newarc(v->nfa, LACON, n, lp, rp);
2087 }
2088 
2089 /*
2090  * subre - allocate a subre
2091  */
2092 static struct subre *
2093 subre(struct vars *v,
2094  int op,
2095  int flags,
2096  struct state *begin,
2097  struct state *end)
2098 {
2099  struct subre *ret = v->treefree;
2100 
2101  /*
2102  * Checking for stack overflow here is sufficient to protect parse() and
2103  * its recursive subroutines.
2104  */
2105  if (STACK_TOO_DEEP(v->re))
2106  {
2107  ERR(REG_ETOOBIG);
2108  return NULL;
2109  }
2110 
2111  if (ret != NULL)
2112  v->treefree = ret->child;
2113  else
2114  {
2115  ret = (struct subre *) MALLOC(sizeof(struct subre));
2116  if (ret == NULL)
2117  {
2118  ERR(REG_ESPACE);
2119  return NULL;
2120  }
2121  ret->chain = v->treechain;
2122  v->treechain = ret;
2123  }
2124 
2125  assert(strchr("=b|.*(", op) != NULL);
2126 
2127  ret->op = op;
2128  ret->flags = flags;
2129  ret->latype = (char) -1;
2130  ret->id = 0; /* will be assigned later */
2131  ret->capno = 0;
2132  ret->backno = 0;
2133  ret->min = ret->max = 1;
2134  ret->child = NULL;
2135  ret->sibling = NULL;
2136  ret->begin = begin;
2137  ret->end = end;
2138  ZAPCNFA(ret->cnfa);
2139 
2140  return ret;
2141 }
2142 
2143 /*
2144  * freesubre - free a subRE subtree
2145  *
2146  * This frees child node(s) of the given subRE too,
2147  * but not its siblings.
2148  */
2149 static void
2150 freesubre(struct vars *v, /* might be NULL */
2151  struct subre *sr)
2152 {
2153  if (sr == NULL)
2154  return;
2155 
2156  if (sr->child != NULL)
2157  freesubreandsiblings(v, sr->child);
2158 
2159  freesrnode(v, sr);
2160 }
2161 
2162 /*
2163  * freesubreandsiblings - free a subRE subtree
2164  *
2165  * This frees child node(s) of the given subRE too,
2166  * as well as any following siblings.
2167  */
2168 static void
2169 freesubreandsiblings(struct vars *v, /* might be NULL */
2170  struct subre *sr)
2171 {
2172  while (sr != NULL)
2173  {
2174  struct subre *next = sr->sibling;
2175 
2176  freesubre(v, sr);
2177  sr = next;
2178  }
2179 }
2180 
2181 /*
2182  * freesrnode - free one node in a subRE subtree
2183  */
2184 static void
2185 freesrnode(struct vars *v, /* might be NULL */
2186  struct subre *sr)
2187 {
2188  if (sr == NULL)
2189  return;
2190 
2191  if (!NULLCNFA(sr->cnfa))
2192  freecnfa(&sr->cnfa);
2193  sr->flags = 0; /* in particular, not INUSE */
2194  sr->child = sr->sibling = NULL;
2195  sr->begin = sr->end = NULL;
2196 
2197  if (v != NULL && v->treechain != NULL)
2198  {
2199  /* we're still parsing, maybe we can reuse the subre */
2200  sr->child = v->treefree;
2201  v->treefree = sr;
2202  }
2203  else
2204  FREE(sr);
2205 }
2206 
2207 /*
2208  * removecaptures - remove unnecessary capture subREs
2209  *
2210  * If the caller said that it doesn't care about subexpression match data,
2211  * we may delete the "capture" markers on subREs that are not referenced
2212  * by any backrefs, and then simplify anything that's become non-messy.
2213  * Call this only if REG_NOSUB flag is set.
2214  */
2215 static void
2216 removecaptures(struct vars *v,
2217  struct subre *t)
2218 {
2219  struct subre *t2;
2220 
2221  assert(t != NULL);
2222 
2223  /*
2224  * If this isn't itself a backref target, clear capno and tentatively
2225  * clear CAP flag.
2226  */
2227  if (!(t->flags & BRUSE))
2228  {
2229  t->capno = 0;
2230  t->flags &= ~CAP;
2231  }
2232 
2233  /* Now recurse to children */
2234  for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
2235  {
2236  removecaptures(v, t2);
2237  /* Propagate child CAP flag back up, if it's still set */
2238  if (t2->flags & CAP)
2239  t->flags |= CAP;
2240  }
2241 
2242  /*
2243  * If t now contains neither captures nor backrefs, there's no longer any
2244  * need to care where its sub-match boundaries are, so we can reduce it to
2245  * a simple DFA node. (Note in particular that MIXED child greediness is
2246  * not a hindrance here, so we don't use the MESSY() macro.)
2247  */
2248  if ((t->flags & (CAP | BACKR)) == 0)
2249  {
2250  if (t->child)
2251  freesubreandsiblings(v, t->child);
2252  t->child = NULL;
2253  t->op = '=';
2254  t->flags &= ~MIXED;
2255  }
2256 }
2257 
2258 /*
2259  * numst - number tree nodes (assigning "id" indexes)
2260  */
2261 static int /* next number */
2262 numst(struct subre *t,
2263  int start) /* starting point for subtree numbers */
2264 {
2265  int i;
2266  struct subre *t2;
2267 
2268  assert(t != NULL);
2269 
2270  i = start;
2271  t->id = i++;
2272  for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
2273  i = numst(t2, i);
2274  return i;
2275 }
2276 
2277 /*
2278  * markst - mark tree nodes as INUSE
2279  *
2280  * Note: this is a great deal more subtle than it looks. During initial
2281  * parsing of a regex, all subres are linked into the treechain list;
2282  * discarded ones are also linked into the treefree list for possible reuse.
2283  * After we are done creating all subres required for a regex, we run markst()
2284  * then cleanst(), which results in discarding all subres not reachable from
2285  * v->tree. We then clear v->treechain, indicating that subres must be found
2286  * by descending from v->tree. This changes the behavior of freesubre(): it
2287  * will henceforth FREE() unwanted subres rather than sticking them into the
2288  * treefree list. (Doing that any earlier would result in dangling links in
2289  * the treechain list.) This all means that freev() will clean up correctly
2290  * if invoked before or after markst()+cleanst(); but it would not work if
2291  * called partway through this state conversion, so we mustn't error out
2292  * in or between these two functions.
2293  */
2294 static void
2295 markst(struct subre *t)
2296 {
2297  struct subre *t2;
2298 
2299  assert(t != NULL);
2300 
2301  t->flags |= INUSE;
2302  for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
2303  markst(t2);
2304 }
2305 
2306 /*
2307  * cleanst - free any tree nodes not marked INUSE
2308  */
2309 static void
2310 cleanst(struct vars *v)
2311 {
2312  struct subre *t;
2313  struct subre *next;
2314 
2315  for (t = v->treechain; t != NULL; t = next)
2316  {
2317  next = t->chain;
2318  if (!(t->flags & INUSE))
2319  FREE(t);
2320  }
2321  v->treechain = NULL;
2322  v->treefree = NULL; /* just on general principles */
2323 }
2324 
2325 /*
2326  * nfatree - turn a subRE subtree into a tree of compacted NFAs
2327  */
2328 static long /* optimize results from top node */
2329 nfatree(struct vars *v,
2330  struct subre *t,
2331  FILE *f) /* for debug output */
2332 {
2333  struct subre *t2;
2334 
2335  assert(t != NULL && t->begin != NULL);
2336 
2337  for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
2338  (DISCARD) nfatree(v, t2, f);
2339 
2340  return nfanode(v, t, 0, f);
2341 }
2342 
2343 /*
2344  * nfanode - do one NFA for nfatree or lacons
2345  *
2346  * If converttosearch is true, apply makesearch() to the NFA.
2347  */
2348 static long /* optimize results */
2349 nfanode(struct vars *v,
2350  struct subre *t,
2351  int converttosearch,
2352  FILE *f) /* for debug output */
2353 {
2354  struct nfa *nfa;
2355  long ret = 0;
2356 
2357  assert(t->begin != NULL);
2358 
2359 #ifdef REG_DEBUG
2360  if (f != NULL)
2361  {
2362  char idbuf[50];
2363 
2364  fprintf(f, "\n\n\n========= TREE NODE %s ==========\n",
2365  stid(t, idbuf, sizeof(idbuf)));
2366  }
2367 #endif
2368  nfa = newnfa(v, v->cm, v->nfa);
2369  NOERRZ();
2370  dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final);
2371  if (!ISERR())
2372  specialcolors(nfa);
2373  if (!ISERR())
2374  ret = optimize(nfa, f);
2375  if (converttosearch && !ISERR())
2376  makesearch(v, nfa);
2377  if (!ISERR())
2378  compact(nfa, &t->cnfa);
2379 
2380  freenfa(nfa);
2381  return ret;
2382 }
2383 
2384 /*
2385  * newlacon - allocate a lookaround-constraint subRE
2386  */
2387 static int /* lacon number */
2388 newlacon(struct vars *v,
2389  struct state *begin,
2390  struct state *end,
2391  int latype)
2392 {
2393  int n;
2394  struct subre *newlacons;
2395  struct subre *sub;
2396 
2397  if (v->nlacons == 0)
2398  {
2399  n = 1; /* skip 0th */
2400  newlacons = (struct subre *) MALLOC(2 * sizeof(struct subre));
2401  }
2402  else
2403  {
2404  n = v->nlacons;
2405  newlacons = (struct subre *) REALLOC(v->lacons,
2406  (n + 1) * sizeof(struct subre));
2407  }
2408  if (newlacons == NULL)
2409  {
2410  ERR(REG_ESPACE);
2411  return 0;
2412  }
2413  v->lacons = newlacons;
2414  v->nlacons = n + 1;
2415  sub = &v->lacons[n];
2416  sub->begin = begin;
2417  sub->end = end;
2418  sub->latype = latype;
2419  ZAPCNFA(sub->cnfa);
2420  return n;
2421 }
2422 
2423 /*
2424  * freelacons - free lookaround-constraint subRE vector
2425  */
2426 static void
2427 freelacons(struct subre *subs,
2428  int n)
2429 {
2430  struct subre *sub;
2431  int i;
2432 
2433  assert(n > 0);
2434  for (sub = subs + 1, i = n - 1; i > 0; sub++, i--) /* no 0th */
2435  if (!NULLCNFA(sub->cnfa))
2436  freecnfa(&sub->cnfa);
2437  FREE(subs);
2438 }
2439 
2440 /*
2441  * rfree - free a whole RE (insides of regfree)
2442  */
2443 static void
2444 rfree(regex_t *re)
2445 {
2446  struct guts *g;
2447 
2448  if (re == NULL || re->re_magic != REMAGIC)
2449  return;
2450 
2451  re->re_magic = 0; /* invalidate RE */
2452  g = (struct guts *) re->re_guts;
2453  re->re_guts = NULL;
2454  re->re_fns = NULL;
2455  if (g != NULL)
2456  {
2457  g->magic = 0;
2458  freecm(&g->cmap);
2459  if (g->tree != NULL)
2460  freesubre((struct vars *) NULL, g->tree);
2461  if (g->lacons != NULL)
2462  freelacons(g->lacons, g->nlacons);
2463  if (!NULLCNFA(g->search))
2464  freecnfa(&g->search);
2465  FREE(g);
2466  }
2467 }
2468 
2469 /*
2470  * rstacktoodeep - check for stack getting dangerously deep
2471  *
2472  * Return nonzero to fail the operation with error code REG_ETOOBIG,
2473  * zero to keep going
2474  *
2475  * The current implementation is Postgres-specific. If we ever get around
2476  * to splitting the regex code out as a standalone library, there will need
2477  * to be some API to let applications define a callback function for this.
2478  */
2479 static int
2480 rstacktoodeep(void)
2481 {
2482  return stack_is_too_deep();
2483 }
2484 
2485 #ifdef REG_DEBUG
2486 
2487 /*
2488  * dump - dump an RE in human-readable form
2489  */
2490 static void
2491 dump(regex_t *re,
2492  FILE *f)
2493 {
2494  struct guts *g;
2495  int i;
2496 
2497  if (re->re_magic != REMAGIC)
2498  fprintf(f, "bad magic number (0x%x not 0x%x)\n", re->re_magic,
2499  REMAGIC);
2500  if (re->re_guts == NULL)
2501  {
2502  fprintf(f, "NULL guts!!!\n");
2503  return;
2504  }
2505  g = (struct guts *) re->re_guts;
2506  if (g->magic != GUTSMAGIC)
2507  fprintf(f, "bad guts magic number (0x%x not 0x%x)\n", g->magic,
2508  GUTSMAGIC);
2509 
2510  fprintf(f, "\n\n\n========= DUMP ==========\n");
2511  fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n",
2512  (int) re->re_nsub, re->re_info, re->re_csize, g->ntree);
2513 
2514  dumpcolors(&g->cmap, f);
2515  if (!NULLCNFA(g->search))
2516  {
2517  fprintf(f, "\nsearch:\n");
2518  dumpcnfa(&g->search, f);
2519  }
2520  for (i = 1; i < g->nlacons; i++)
2521  {
2522  struct subre *lasub = &g->lacons[i];
2523  const char *latype;
2524 
2525  switch (lasub->latype)
2526  {
2527  case LATYPE_AHEAD_POS:
2528  latype = "positive lookahead";
2529  break;
2530  case LATYPE_AHEAD_NEG:
2531  latype = "negative lookahead";
2532  break;
2533  case LATYPE_BEHIND_POS:
2534  latype = "positive lookbehind";
2535  break;
2536  case LATYPE_BEHIND_NEG:
2537  latype = "negative lookbehind";
2538  break;
2539  default:
2540  latype = "???";
2541  break;
2542  }
2543  fprintf(f, "\nla%d (%s):\n", i, latype);
2544  dumpcnfa(&lasub->cnfa, f);
2545  }
2546  fprintf(f, "\n");
2547  dumpst(g->tree, f, 0);
2548 }
2549 
2550 /*
2551  * dumpst - dump a subRE tree
2552  */
2553 static void
2554 dumpst(struct subre *t,
2555  FILE *f,
2556  int nfapresent) /* is the original NFA still around? */
2557 {
2558  if (t == NULL)
2559  fprintf(f, "null tree\n");
2560  else
2561  stdump(t, f, nfapresent);
2562  fflush(f);
2563 }
2564 
2565 /*
2566  * stdump - recursive guts of dumpst
2567  */
2568 static void
2569 stdump(struct subre *t,
2570  FILE *f,
2571  int nfapresent) /* is the original NFA still around? */
2572 {
2573  char idbuf[50];
2574  struct subre *t2;
2575 
2576  fprintf(f, "%s. `%c'", stid(t, idbuf, sizeof(idbuf)), t->op);
2577  if (t->flags & LONGER)
2578  fprintf(f, " longest");
2579  if (t->flags & SHORTER)
2580  fprintf(f, " shortest");
2581  if (t->flags & MIXED)
2582  fprintf(f, " hasmixed");
2583  if (t->flags & CAP)
2584  fprintf(f, " hascapture");
2585  if (t->flags & BACKR)
2586  fprintf(f, " hasbackref");
2587  if (t->flags & BRUSE)
2588  fprintf(f, " isreferenced");
2589  if (!(t->flags & INUSE))
2590  fprintf(f, " UNUSED");
2591  if (t->latype != (char) -1)
2592  fprintf(f, " latype(%d)", t->latype);
2593  if (t->capno != 0)
2594  fprintf(f, " capture(%d)", t->capno);
2595  if (t->backno != 0)
2596  fprintf(f, " backref(%d)", t->backno);
2597  if (t->min != 1 || t->max != 1)
2598  {
2599  fprintf(f, " {%d,", t->min);
2600  if (t->max != DUPINF)
2601  fprintf(f, "%d", t->max);
2602  fprintf(f, "}");
2603  }
2604  if (nfapresent)
2605  fprintf(f, " %ld-%ld", (long) t->begin->no, (long) t->end->no);
2606  if (t->child != NULL)
2607  fprintf(f, " C:%s", stid(t->child, idbuf, sizeof(idbuf)));
2608  /* printing second child isn't necessary, but it is often helpful */
2609  if (t->child != NULL && t->child->sibling != NULL)
2610  fprintf(f, " C2:%s", stid(t->child->sibling, idbuf, sizeof(idbuf)));
2611  if (t->sibling != NULL)
2612  fprintf(f, " S:%s", stid(t->sibling, idbuf, sizeof(idbuf)));
2613  if (!NULLCNFA(t->cnfa))
2614  {
2615  fprintf(f, "\n");
2616  dumpcnfa(&t->cnfa, f);
2617  }
2618  fprintf(f, "\n");
2619  for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
2620  stdump(t2, f, nfapresent);
2621 }
2622 
2623 /*
2624  * stid - identify a subtree node for dumping
2625  */
2626 static const char * /* points to buf or constant string */
2627 stid(struct subre *t,
2628  char *buf,
2629  size_t bufsize)
2630 {
2631  /* big enough for hex int or decimal t->id? */
2632  if (bufsize < sizeof(void *) * 2 + 3 || bufsize < sizeof(t->id) * 3 + 1)
2633  return "unable";
2634  if (t->id != 0)
2635  sprintf(buf, "%d", t->id);
2636  else
2637  sprintf(buf, "%p", t);
2638  return buf;
2639 }
2640 #endif /* REG_DEBUG */
2641 
2642 
2643 #include "regc_lex.c"
2644 #include "regc_color.c"
2645 #include "regc_nfa.c"
2646 #include "regc_cvec.c"
2647 #include "regc_pg_locale.c"
2648 #include "regc_locale.c"
FREE
#define FREE(ptr)
Definition: cryptohash.c:37
err
void err(int eval, const char *fmt,...)
Definition: err.c:43
bufsize
#define bufsize
Definition: indent_globs.h:36
debug
static bool debug
Definition: initdb.c:162
y
int y
Definition: isn.c:72
b
int b
Definition: isn.c:70
x
int x
Definition: isn.c:71
init
int init
Definition: isn.c:75
a
int a
Definition: isn.c:69
j
int j
Definition: isn.c:74
i
int i
Definition: isn.c:73
if
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
fflush
static void const char fflush(stdout)
pg_wchar
unsigned int pg_wchar
Definition: mbprint.c:31
generate_unaccent_rules.type
type
Definition: generate_unaccent_rules.py:276
generate_unaccent_rules.stdout
stdout
Definition: generate_unaccent_rules.py:35
len
const void size_t len
Definition: pg_crc32c_sse42.c:24
buf
static char * buf
Definition: pg_test_fsync.c:67
sprintf
#define sprintf
Definition: port.h:240
fprintf
#define fprintf
Definition: port.h:242
stack_is_too_deep
bool stack_is_too_deep(void)
Definition: postgres.c:3522
Oid
unsigned int Oid
Definition: postgres_ext.h:31
c
char * c
Definition: preproc-cursor.c:31
s1
char * s1
Definition: preproc-strings.c:33
s2
char * s2
Definition: preproc-strings.c:33
string
char string[11]
Definition: preproc-type.c:52
regc_color.c
regc_cvec.c
regc_lex.c
regc_locale.c
regc_nfa.c
regc_pg_locale.c
pg_set_regex_collation
void pg_set_regex_collation(Oid collation)
Definition: regc_pg_locale.c:232
freecvec
static void freecvec(struct cvec *cv)
COLLEL
#define COLLEL
Definition: regcomp.c:333
mergeins
static void mergeins(struct nfa *nfa, struct state *s, struct arc **arcarray, int arccount)
subcoloronechr
static void subcoloronechr(struct vars *v, chr ch, struct state *lp, struct state *rp, color *lastsubcolor)
newhicolorrow
static int newhicolorrow(struct colormap *cm, int oldrow)
NWBDRY
#define NWBDRY
Definition: regcomp.c:344
pg_wc_islower
static int pg_wc_islower(pg_wchar c)
pg_wc_isword
static int pg_wc_isword(pg_wchar c)
cleartraverse
static void cleartraverse(struct nfa *nfa, struct state *s)
REDUCE
#define REDUCE(x)
cparc
static void cparc(struct nfa *nfa, struct arc *oa, struct state *from, struct state *to)
subcolorcvec
static void subcolorcvec(struct vars *v, struct cvec *cv, struct state *lp, struct state *rp)
cclasscvec
static struct cvec * cclasscvec(struct vars *v, enum char_classes cclasscode, int cases)
clonesuccessorstates
static void clonesuccessorstates(struct nfa *nfa, struct state *ssource, struct state *sclone, struct state *spredecessor, struct arc *refarc, char *curdonemap, char *outerdonemap, int nstates)
INF
#define INF
emptyreachable
static struct state * emptyreachable(struct nfa *nfa, struct state *s, struct state *lastfound, struct arc **inarcsorig)
pg_wc_isspace
static int pg_wc_isspace(pg_wchar c)
pg_wc_tolower
static pg_wchar pg_wc_tolower(pg_wchar c)
NOTE
#define NOTE(b)
Definition: regcomp.c:324
combine
static int combine(struct nfa *nfa, struct arc *con, struct arc *a)
freecolor
static void freecolor(struct colormap *cm, color co)
copyouts
static void copyouts(struct nfa *nfa, struct state *oldState, struct state *newState)
wordchrs
static void wordchrs(struct vars *v)
Definition: regcomp.c:1991
sortins_cmp
static int sortins_cmp(const void *a, const void *b)
pg_wc_ispunct
static int pg_wc_ispunct(pg_wchar c)
NOERR
#define NOERR()
Definition: regcomp.c:320
cleanup
static void cleanup(struct nfa *nfa)
findconstraintloop
static int findconstraintloop(struct nfa *nfa, struct state *s)
END
#define END
Definition: regcomp.c:336
compact
static void compact(struct nfa *nfa, struct cnfa *cnfa)
pg_wc_isgraph
static int pg_wc_isgraph(pg_wchar c)
specialcolors
static void specialcolors(struct nfa *nfa)
freesubreandsiblings
static void freesubreandsiblings(struct vars *v, struct subre *sr)
Definition: regcomp.c:2169
dupnfa
static void dupnfa(struct nfa *nfa, struct state *start, struct state *stop, struct state *from, struct state *to)
range
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
SBEGIN
#define SBEGIN
Definition: regcomp.c:345
analyze
static long analyze(struct nfa *nfa)
ISERR
#define ISERR()
Definition: regcomp.c:316
duptraverse
static void duptraverse(struct nfa *nfa, struct state *s, struct state *stmp)
freesubre
static void freesubre(struct vars *v, struct subre *sr)
Definition: regcomp.c:2150
newarc
static void newarc(struct nfa *nfa, int t, color co, struct state *from, struct state *to)
repeat
static void repeat(struct vars *v, struct state *lp, struct state *rp, int m, int n)
Definition: regcomp.c:1584
lexescape
static int lexescape(struct vars *v)
pg_wc_toupper
static pg_wchar pg_wc_toupper(pg_wchar c)
makesearch
static void makesearch(struct vars *v, struct nfa *nfa)
Definition: regcomp.c:619
moresubs
static void moresubs(struct vars *v, int wanted)
Definition: regcomp.c:553
casecmp
static int casecmp(const chr *x, const chr *y, size_t len)
checkmatchall_recurse
static bool checkmatchall_recurse(struct nfa *nfa, struct state *s, bool **haspaths)
functions
static const struct fns functions
Definition: regcomp.c:356
newhicolorcols
static void newhicolorcols(struct colormap *cm)
parsebranch
static struct subre * parsebranch(struct vars *v, int stopper, int type, struct state *left, struct state *right, int partial)
Definition: regcomp.c:783
freenfa
static void freenfa(struct nfa *nfa)
optimizebracket
static void optimizebracket(struct vars *v, struct state *lp, struct state *rp)
Definition: regcomp.c:1935
pg_wc_isprint
static int pg_wc_isprint(pg_wchar c)
CCLASSS
#define CCLASSS
Definition: regcomp.c:337
EMPTYARC
#define EMPTYARC(x, y)
Definition: regcomp.c:325
createarc
static void createarc(struct nfa *nfa, int t, color co, struct state *from, struct state *to)
ERR
#define ERR(e)
Definition: regcomp.c:319
isconstraintarc
static int isconstraintarc(struct arc *a)
pg_wc_isalnum
static int pg_wc_isalnum(pg_wchar c)
allocarc
static struct arc * allocarc(struct nfa *nfa)
single_color_transition
static struct state * single_color_transition(struct state *s1, struct state *s2)
CCLASS
#define CCLASS
Definition: regcomp.c:335
rstacktoodeep
static int rstacktoodeep(void)
Definition: regcomp.c:2480
WBDRY
#define WBDRY
Definition: regcomp.c:343
fixempties
static void fixempties(struct nfa *nfa, FILE *f)
pg_wc_isdigit
static int pg_wc_isdigit(pg_wchar c)
skip
static void skip(struct vars *v)
pg_regcomp
int pg_regcomp(regex_t *re, const chr *string, size_t len, int flags, Oid collation)
Definition: regcomp.c:370
lookupcclass
static enum char_classes lookupcclass(struct vars *v, const chr *startp, const chr *endp)
cleanst
static void cleanst(struct vars *v)
Definition: regcomp.c:2310
SEE
#define SEE(t)
Definition: regcomp.c:313
copyins
static void copyins(struct nfa *nfa, struct state *oldState, struct state *newState)
push
static int push(struct nfa *nfa, struct arc *con, struct state **intermediates)
newcolor
static color newcolor(struct colormap *cm)
PAIR
#define PAIR(x, y)
moveouts
static void moveouts(struct nfa *nfa, struct state *oldState, struct state *newState)
lexdigits
static chr lexdigits(struct vars *v, int base, int minlen, int maxlen)
hasconstraintout
static int hasconstraintout(struct state *s)
freearc
static void freearc(struct nfa *nfa, struct arc *victim)
DIGIT
#define DIGIT
Definition: regcomp.c:331
checkmatchall
static void checkmatchall(struct nfa *nfa)
addchr
static void addchr(struct cvec *cv, chr c)
subcolorhi
static color subcolorhi(struct colormap *cm, color *pco)
ARCV
#define ARCV(t, val)
colorchain
static void colorchain(struct colormap *cm, struct arc *a)
scannum
static int scannum(struct vars *v)
Definition: regcomp.c:1553
newfstate
static struct state * newfstate(struct nfa *nfa, int flag)
sortins
static void sortins(struct nfa *nfa, struct state *s)
cloneouts
static void cloneouts(struct nfa *nfa, struct state *old, struct state *from, struct state *to, int type)
newnfa
static struct nfa * newnfa(struct vars *v, struct colormap *cm, struct nfa *parent)
carc_cmp
static int carc_cmp(const void *a, const void *b)
parseqatom
static struct subre * parseqatom(struct vars *v, int stopper, int type, struct state *lp, struct state *rp, struct subre *top)
Definition: regcomp.c:836
CCLASSC
#define CCLASSC
Definition: regcomp.c:338
freecm
static void freecm(struct colormap *cm)
optimize
static long optimize(struct nfa *nfa, FILE *f)
uncolorchain
static void uncolorchain(struct colormap *cm, struct arc *a)
CNOERR
#define CNOERR()
rfree
static void rfree(regex_t *re)
Definition: regcomp.c:2444
eclass
static struct cvec * eclass(struct vars *v, chr c, int cases)
sortouts
static void sortouts(struct nfa *nfa, struct state *s)
NOERRN
#define NOERRN()
Definition: regcomp.c:321
scanplain
static const chr * scanplain(struct vars *v)
Definition: regcomp.c:1884
deltraverse
static void deltraverse(struct nfa *nfa, struct state *leftend, struct state *s)
SOME
#define SOME
dropstate
static void dropstate(struct nfa *nfa, struct state *s)
okcolors
static void okcolors(struct nfa *nfa, struct colormap *cm)
BEHIND
#define BEHIND
Definition: regcomp.c:342
addrange
static void addrange(struct cvec *cv, chr from, chr to)
maxcolor
static color maxcolor(struct colormap *cm)
initcm
static void initcm(struct vars *v, struct colormap *cm)
removetraverse
static void removetraverse(struct nfa *nfa, struct state *s)
newline
static chr newline(void)
charclass
static void charclass(struct vars *v, enum char_classes cls, struct state *lp, struct state *rp)
Definition: regcomp.c:1492
bracket
static void bracket(struct vars *v, struct state *lp, struct state *rp)
Definition: regcomp.c:1671
cbracket
static void cbracket(struct vars *v, struct state *lp, struct state *rp)
Definition: regcomp.c:1727
pushfwd
static void pushfwd(struct nfa *nfa, FILE *f)
pseudocolor
static color pseudocolor(struct colormap *cm)
cmp
static int cmp(const chr *x, const chr *y, size_t len)
subre
static struct subre * subre(struct vars *v, int op, int flags, struct state *begin, struct state *end)
Definition: regcomp.c:2093
hasnonemptyout
static int hasnonemptyout(struct state *s)
nfanode
static long nfanode(struct vars *v, struct subre *t, int converttosearch, FILE *f)
Definition: regcomp.c:2349
freesrnode
static void freesrnode(struct vars *v, struct subre *sr)
Definition: regcomp.c:2185
ECLASS
#define ECLASS
Definition: regcomp.c:334
pullback
static void pullback(struct nfa *nfa, FILE *f)
BACKREF
#define BACKREF
Definition: regcomp.c:332
LACON
#define LACON
Definition: regcomp.c:340
markcanreach
static void markcanreach(struct nfa *nfa, struct state *s, struct state *okay, struct state *mark)
removecaptures
static void removecaptures(struct vars *v, struct subre *t)
Definition: regcomp.c:2216
brenext
static int brenext(struct vars *v, chr c)
EOS
#define EOS
Definition: regcomp.c:329
lexstart
static void lexstart(struct vars *v)
nonword
static void nonword(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1456
AHEAD
#define AHEAD
Definition: regcomp.c:341
newstate
static struct state * newstate(struct nfa *nfa)
delsub
static void delsub(struct nfa *nfa, struct state *lp, struct state *rp)
clearcvec
static struct cvec * clearcvec(struct cvec *cv)
prefixes
static void prefixes(struct vars *v)
moveins
static void moveins(struct nfa *nfa, struct state *oldState, struct state *newState)
check_in_colors_match
static bool check_in_colors_match(struct state *s, color co1, color co2)
PLAIN
#define PLAIN
Definition: regcomp.c:330
SEND
#define SEND
Definition: regcomp.c:346
removeconstraints
static void removeconstraints(struct nfa *nfa, struct state *start, struct state *stop)
charclasscomplement
static void charclasscomplement(struct vars *v, enum char_classes cls, struct state *lp, struct state *rp)
Definition: regcomp.c:1516
RANGE
#define RANGE
Definition: regcomp.c:339
parse
static struct subre * parse(struct vars *v, int stopper, int type, struct state *init, struct state *final)
Definition: regcomp.c:715
sortouts_cmp
static int sortouts_cmp(const void *a, const void *b)
EAT
#define EAT(t)
Definition: regcomp.c:314
newlacon
static int newlacon(struct vars *v, struct state *begin, struct state *end, int latype)
Definition: regcomp.c:2388
INSIST
#define INSIST(c, e)
Definition: regcomp.c:323
subcolor
static color subcolor(struct colormap *cm, chr c)
getcvec
static struct cvec * getcvec(struct vars *v, int nchrs, int nranges)
rainbow
static void rainbow(struct nfa *nfa, struct colormap *cm, int type, color but, struct state *from, struct state *to)
allcases
static struct cvec * allcases(struct vars *v, chr c)
colorcomplement
static void colorcomplement(struct nfa *nfa, struct colormap *cm, int type, struct state *of, struct state *from, struct state *to)
carcsort
static void carcsort(struct carc *first, size_t n)
pull
static int pull(struct nfa *nfa, struct arc *con, struct state **intermediates)
subcoloronerange
static void subcoloronerange(struct vars *v, chr from, chr to, struct state *lp, struct state *rp, color *lastsubcolor)
changearctarget
static void changearctarget(struct arc *a, struct state *newto)
element
static chr element(struct vars *v, const chr *startp, const chr *endp)
NOERRZ
#define NOERRZ()
Definition: regcomp.c:322
freelacons
static void freelacons(struct subre *subs, int n)
Definition: regcomp.c:2427
findarc
static struct arc * findarc(struct state *s, int type, color co)
processlacon
static void processlacon(struct vars *v, struct state *begin, struct state *end, int latype, struct state *lp, struct state *rp)
Definition: regcomp.c:2027
changearcsource
static void changearcsource(struct arc *a, struct state *newfrom)
subcoloronerow
static void subcoloronerow(struct vars *v, int rownum, struct state *lp, struct state *rp, color *lastsubcolor)
freestate
static void freestate(struct nfa *nfa, struct state *s)
dumpnfa
static void dumpnfa(struct nfa *nfa, FILE *f)
brackpart
static void brackpart(struct vars *v, struct state *lp, struct state *rp, bool *have_cclassc)
Definition: regcomp.c:1761
markreachable
static void markreachable(struct nfa *nfa, struct state *s, struct state *okay, struct state *mark)
before
static int before(chr x, chr y)
chrnamed
static chr chrnamed(struct vars *v, const chr *startp, const chr *endp, chr lastresort)
onechr
static void onechr(struct vars *v, chr c, struct state *lp, struct state *rp)
Definition: regcomp.c:1909
numst
static int numst(struct subre *t, int start)
Definition: regcomp.c:2262
word
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1474
fixconstraintloops
static void fixconstraintloops(struct nfa *nfa, FILE *f)
freev
static int freev(struct vars *v, int err)
Definition: regcomp.c:590
nfatree
static long nfatree(struct vars *v, struct subre *t, FILE *f)
Definition: regcomp.c:2329
pg_wc_isupper
static int pg_wc_isupper(pg_wchar c)
check_out_colors_match
static bool check_out_colors_match(struct state *s, color co1, color co2)
breakconstraintloop
static void breakconstraintloop(struct nfa *nfa, struct state *sinitial)
pg_wc_isalpha
static int pg_wc_isalpha(pg_wchar c)
markst
static void markst(struct subre *t)
Definition: regcomp.c:2295
NEXT
#define NEXT()
Definition: regcomp.c:312
cclass_column_index
static int cclass_column_index(struct colormap *cm, chr c)
freecnfa
static void freecnfa(struct cnfa *cnfa)
newsub
static color newsub(struct colormap *cm, color co)
newcvec
static struct cvec * newcvec(int nchrs, int nranges)
next
static int next(struct vars *v)
REALLOC
#define REALLOC(p, n)
Definition: regcustom.h:54
MALLOC
#define MALLOC(n)
Definition: regcustom.h:52
chr
pg_wchar chr
Definition: regcustom.h:59
assert
#define assert(x)
Definition: regcustom.h:56
REG_ICASE
#define REG_ICASE
Definition: regex.h:106
REG_DUMP
#define REG_DUMP
Definition: regex.h:115
REG_ECTYPE
#define REG_ECTYPE
Definition: regex.h:141
REG_PROGRESS
#define REG_PROGRESS
Definition: regex.h:117
REG_ASSERT
#define REG_ASSERT
Definition: regex.h:151
REG_UPBOTCH
#define REG_UPBOTCH
Definition: regex.h:65
REG_BADRPT
#define REG_BADRPT
Definition: regex.h:150
REG_ADVANCED
#define REG_ADVANCED
Definition: regex.h:103
REG_EXPANDED
#define REG_EXPANDED
Definition: regex.h:108
REG_NLANCH
#define REG_NLANCH
Definition: regex.h:110
REG_INVARG
#define REG_INVARG
Definition: regex.h:152
REG_EXTENDED
#define REG_EXTENDED
Definition: regex.h:101
REG_NLSTOP
#define REG_NLSTOP
Definition: regex.h:109
REG_ADVF
#define REG_ADVF
Definition: regex.h:102
REG_UUNSPEC
#define REG_UUNSPEC
Definition: regex.h:68
REG_ETOOBIG
#define REG_ETOOBIG
Definition: regex.h:155
REG_ERANGE
#define REG_ERANGE
Definition: regex.h:148
REG_ESUBREG
#define REG_ESUBREG
Definition: regex.h:143
REG_BADBR
#define REG_BADBR
Definition: regex.h:147
REG_NEWLINE
#define REG_NEWLINE
Definition: regex.h:111
REG_NOSUB
#define REG_NOSUB
Definition: regex.h:107
REG_USHORTEST
#define REG_USHORTEST
Definition: regex.h:73
REG_ULOCALE
#define REG_ULOCALE
Definition: regex.h:70
REG_ECOLLATE
#define REG_ECOLLATE
Definition: regex.h:140
REG_UUNPORT
#define REG_UUNPORT
Definition: regex.h:69
REG_EPAREN
#define REG_EPAREN
Definition: regex.h:145
REG_ESPACE
#define REG_ESPACE
Definition: regex.h:149
REG_QUOTE
#define REG_QUOTE
Definition: regex.h:104
BACKR
#define BACKR
Definition: regguts.h:484
NUM_CCLASSES
#define NUM_CCLASSES
Definition: regguts.h:144
LATYPE_AHEAD_NEG
#define LATYPE_AHEAD_NEG
Definition: regguts.h:105
PSEUDO
#define PSEUDO
Definition: regguts.h:186
RAINBOW
#define RAINBOW
Definition: regguts.h:159
LATYPE_BEHIND_POS
#define LATYPE_BEHIND_POS
Definition: regguts.h:106
STACK_TOO_DEEP
#define STACK_TOO_DEEP(re)
Definition: regguts.h:521
CAP
#define CAP
Definition: regguts.h:483
ZAPCNFA
#define ZAPCNFA(cnfa)
Definition: regguts.h:434
REMAGIC
#define REMAGIC
Definition: regguts.h:101
color
short color
Definition: regguts.h:155
COMBINE
#define COMBINE(f1, f2)
Definition: regguts.h:494
UP
#define UP(f)
Definition: regguts.h:490
PREF
#define PREF(f)
Definition: regguts.h:492
NOTREACHED
#define NOTREACHED
Definition: regguts.h:96
GUTSMAGIC
#define GUTSMAGIC
Definition: regguts.h:531
COLORLESS
#define COLORLESS
Definition: regguts.h:158
LATYPE_BEHIND_NEG
#define LATYPE_BEHIND_NEG
Definition: regguts.h:107
DUPINF
#define DUPINF
Definition: regguts.h:99
COLMARK
#define COLMARK
Definition: regguts.h:187
DUPMAX
#define DUPMAX
Definition: regguts.h:98
UNUSEDCOLOR
#define UNUSEDCOLOR(cd)
Definition: regguts.h:190
LATYPE_IS_AHEAD
#define LATYPE_IS_AHEAD(la)
Definition: regguts.h:109
NULLCNFA
#define NULLCNFA(cnfa)
Definition: regguts.h:436
LONGER
#define LONGER
Definition: regguts.h:480
char_classes
char_classes
Definition: regguts.h:139
CC_WORD
@ CC_WORD
Definition: regguts.h:141
INUSE
#define INUSE
Definition: regguts.h:486
CDEND
#define CDEND(cm)
Definition: regguts.h:237
MESSY
#define MESSY(f)
Definition: regguts.h:491
BRUSE
#define BRUSE
Definition: regguts.h:485
DISCARD
#define DISCARD
Definition: regguts.h:58
MIXED
#define MIXED
Definition: regguts.h:482
VS
#define VS(x)
Definition: regguts.h:61
MATCHALL
#define MATCHALL
Definition: regguts.h:412
SHORTER
#define SHORTER
Definition: regguts.h:481
LATYPE_AHEAD_POS
#define LATYPE_AHEAD_POS
Definition: regguts.h:104
arc
Definition: regguts.h:296
arc::from
struct state * from
Definition: regguts.h:299
arc::co
color co
Definition: regguts.h:298
arc::to
struct state * to
Definition: regguts.h:300
carc
Definition: regguts.h:401
cnfa
Definition: regguts.h:407
colordesc::flags
int flags
Definition: regguts.h:184
colormap::cd
struct colordesc * cd
Definition: regguts.h:236
cvec
Definition: regguts.h:279
cvec::nchrs
int nchrs
Definition: regguts.h:280
cvec::cclasscode
int cclasscode
Definition: regguts.h:286
cvec::nranges
int nranges
Definition: regguts.h:283
fns
Definition: regguts.h:516
guts
Definition: regguts.h:529
guts::tree
struct subre * tree
Definition: regguts.h:535
guts::lacons
struct subre * lacons
Definition: regguts.h:540
guts::magic
int magic
Definition: regguts.h:530
guts::info
long info
Definition: regguts.h:533
guts::search
struct cnfa search
Definition: regguts.h:536
guts::ntree
int ntree
Definition: regguts.h:537
guts::cflags
int cflags
Definition: regguts.h:532
guts::nsub
size_t nsub
Definition: regguts.h:534
guts::nlacons
int nlacons
Definition: regguts.h:541
guts::cmap
struct colormap cmap
Definition: regguts.h:538
nfa
Definition: regguts.h:349
nfa::v
struct vars * v
Definition: regguts.h:369
nfa::final
struct state * final
Definition: regguts.h:352
nfa::maxmatchall
int maxmatchall
Definition: regguts.h:368
nfa::bos
color bos[2]
Definition: regguts.h:364
nfa::flags
int flags
Definition: regguts.h:366
nfa::pre
struct state * pre
Definition: regguts.h:350
nfa::cm
struct colormap * cm
Definition: regguts.h:363
nfa::parent
struct nfa * parent
Definition: regguts.h:370
nfa::init
struct state * init
Definition: regguts.h:351
regex_t
Definition: regex.h:56
regex_t::re_guts
char * re_guts
Definition: regex.h:78
regex_t::re_info
long re_info
Definition: regex.h:59
regex_t::re_csize
int re_csize
Definition: regex.h:74
regex_t::re_nsub
size_t re_nsub
Definition: regex.h:58
regex_t::re_magic
int re_magic
Definition: regex.h:57
regex_t::re_collation
Oid re_collation
Definition: regex.h:76
regex_t::re_fns
char * re_fns
Definition: regex.h:79
state
Definition: regguts.h:323
state::nins
int nins
Definition: regguts.h:327
state::nouts
int nouts
Definition: regguts.h:328
state::tmp
struct state * tmp
Definition: regguts.h:331
state::outs
struct arc * outs
Definition: regguts.h:330
state::ins
struct arc * ins
Definition: regguts.h:329
state::no
int no
Definition: regguts.h:324
subre
Definition: regguts.h:477
subre::backno
int backno
Definition: regguts.h:498
subre::op
char op
Definition: regguts.h:478
subre::chain
struct subre * chain
Definition: regguts.h:506
subre::end
struct state * end
Definition: regguts.h:504
subre::min
short min
Definition: regguts.h:499
subre::max
short max
Definition: regguts.h:500
subre::sibling
struct subre * sibling
Definition: regguts.h:502
subre::flags
char flags
Definition: regguts.h:479
subre::id
int id
Definition: regguts.h:496
subre::cnfa
struct cnfa cnfa
Definition: regguts.h:505
subre::latype
char latype
Definition: regguts.h:495
subre::child
struct subre * child
Definition: regguts.h:501
subre::capno
int capno
Definition: regguts.h:497
subre::begin
struct state * begin
Definition: regguts.h:503
vars
Definition: regcomp.c:281
vars::now
const chr * now
Definition: regcomp.c:283
vars::cm
struct colormap * cm
Definition: regcomp.c:296
vars::tree
struct subre * tree
Definition: regcomp.c:299
vars::subs
struct subre ** subs
Definition: regcomp.c:292
vars::nlacons
int nlacons
Definition: regcomp.c:306
vars::stop
const chr * stop
Definition: regcomp.c:284
vars::lacons
struct subre * lacons
Definition: regcomp.c:305
vars::spaceused
size_t spaceused
Definition: regcomp.c:308
vars::err
int err
Definition: regcomp.c:285
vars::cflags
int cflags
Definition: regcomp.c:286
vars::treechain
struct subre * treechain
Definition: regcomp.c:300
vars::lexcon
int lexcon
Definition: regcomp.c:290
vars::nextvalue
chr nextvalue
Definition: regcomp.c:289
vars::ntree
int ntree
Definition: regcomp.c:302
vars::re
regex_t * re
Definition: regcomp.c:282
vars::sub10
struct subre * sub10[10]
Definition: regcomp.c:294
vars::cv2
struct cvec * cv2
Definition: regcomp.c:304
vars::treefree
struct subre * treefree
Definition: regcomp.c:301
vars::nfa
struct nfa * nfa
Definition: regcomp.c:295
vars::nsubs
size_t nsubs
Definition: regcomp.c:293
vars::wordchrs
struct state * wordchrs
Definition: regcomp.c:298
vars::nexttype
int nexttype
Definition: regcomp.c:288
vars::nsubexp
int nsubexp
Definition: regcomp.c:291
vars::cv
struct cvec * cv
Definition: regcomp.c:303
vars::nlcolor
color nlcolor
Definition: regcomp.c:297
vars::lasttype
int lasttype
Definition: regcomp.c:287
flag
char * flag(int b)
Definition: test-ctype.c:33