LCOV - code coverage report
Current view: top level - src/backend/regex - regcomp.c (source / functions) Hit Total Coverage
Test: PostgreSQL 15devel Lines: 923 953 96.9 %
Date: 2021-12-09 04:09:06 Functions: 36 36 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.14