PostgreSQL Source Code  git master
regcomp.c File Reference
#include "regex/regguts.h"
#include "regc_lex.c"
#include "regc_color.c"
#include "regc_nfa.c"
#include "regc_cvec.c"
#include "regc_pg_locale.c"
#include "regc_locale.c"
Include dependency graph for regcomp.c:

Go to the source code of this file.

Data Structures

struct  vars
 

Macros

#define INCOMPATIBLE   1 /* destroys arc */
 
#define SATISFIED   2 /* constraint satisfied */
 
#define COMPATIBLE   3 /* compatible but not satisfied yet */
 
#define REPLACEARC   4 /* replace arc's color with constraint color */
 
#define NEXT()   (next(v)) /* advance by one token */
 
#define SEE(t)   (v->nexttype == (t)) /* is next token this? */
 
#define EAT(t)   (SEE(t) && next(v)) /* if next is this, swallow it */
 
#define VISERR(vv)   ((vv)->err != 0) /* have we seen an error yet? */
 
#define ISERR()   VISERR(v)
 
#define VERR(vv, e)
 
#define ERR(e)   VERR(v, e) /* record an error */
 
#define NOERR()   {if (ISERR()) return;} /* if error seen, return */
 
#define NOERRN()   {if (ISERR()) return NULL;} /* NOERR with retval */
 
#define NOERRZ()   {if (ISERR()) return 0;} /* NOERR with retval */
 
#define INSIST(c, e)   do { if (!(c)) ERR(e); } while (0) /* error if c false */
 
#define NOTE(b)   (v->re->re_info |= (b)) /* note visible condition */
 
#define EMPTYARC(x, y)   newarc(v->nfa, EMPTY, 0, x, y)
 
#define EMPTY   'n' /* no token present */
 
#define EOS   'e' /* end of string */
 
#define PLAIN   'p' /* ordinary character */
 
#define DIGIT   'd' /* digit (in bound) */
 
#define BACKREF   'b' /* back reference */
 
#define COLLEL   'I' /* start of [. */
 
#define ECLASS   'E' /* start of [= */
 
#define CCLASS   'C' /* start of [: */
 
#define END   'X' /* end of [. [= [: */
 
#define CCLASSS   's' /* char class shorthand escape */
 
#define CCLASSC   'c' /* complement char class shorthand escape */
 
#define RANGE   'R' /* - within [] which might be range delim. */
 
#define LACON   'L' /* lookaround constraint subRE */
 
#define AHEAD   'a' /* color-lookahead arc */
 
#define BEHIND   'r' /* color-lookbehind arc */
 
#define WBDRY   'w' /* word boundary constraint */
 
#define NWBDRY   'W' /* non-word-boundary constraint */
 
#define CANTMATCH   'x' /* arc that cannot match anything */
 
#define SBEGIN   'A' /* beginning of string (even if not BOL) */
 
#define SEND   'Z' /* end of string (even if not EOL) */
 
#define COLORED(a)
 
#define CNOERR()   { if (ISERR()) return freev(v, v->err); }
 
#define ARCV(t, val)   newarc(v->nfa, t, val, lp, rp)
 
#define SOME   2
 
#define INF   3
 
#define PAIR(x, y)   ((x)*4 + (y))
 
#define REDUCE(x)   ( ((x) == DUPINF) ? INF : (((x) > 1) ? SOME : (x)) )
 

Functions

static void moresubs (struct vars *v, int wanted)
 
static int freev (struct vars *v, int err)
 
static void makesearch (struct vars *v, struct nfa *nfa)
 
static struct subreparse (struct vars *v, int stopper, int type, struct state *init, struct state *final)
 
static struct subreparsebranch (struct vars *v, int stopper, int type, struct state *left, struct state *right, int partial)
 
static struct subreparseqatom (struct vars *v, int stopper, int type, struct state *lp, struct state *rp, struct subre *top)
 
static void nonword (struct vars *v, int dir, struct state *lp, struct state *rp)
 
static void word (struct vars *v, int dir, struct state *lp, struct state *rp)
 
static void charclass (struct vars *v, enum char_classes cls, struct state *lp, struct state *rp)
 
static void charclasscomplement (struct vars *v, enum char_classes cls, struct state *lp, struct state *rp)
 
static int scannum (struct vars *v)
 
static void repeat (struct vars *v, struct state *lp, struct state *rp, int m, int n)
 
static void bracket (struct vars *v, struct state *lp, struct state *rp)
 
static void cbracket (struct vars *v, struct state *lp, struct state *rp)
 
static void brackpart (struct vars *v, struct state *lp, struct state *rp, bool *have_cclassc)
 
static const chrscanplain (struct vars *v)
 
static void onechr (struct vars *v, chr c, struct state *lp, struct state *rp)
 
static void optimizebracket (struct vars *v, struct state *lp, struct state *rp)
 
static void wordchrs (struct vars *v)
 
static void processlacon (struct vars *v, struct state *begin, struct state *end, int latype, struct state *lp, struct state *rp)
 
static struct subresubre (struct vars *v, int op, int flags, struct state *begin, struct state *end)
 
static void freesubre (struct vars *v, struct subre *sr)
 
static void freesubreandsiblings (struct vars *v, struct subre *sr)
 
static void freesrnode (struct vars *v, struct subre *sr)
 
static void removecaptures (struct vars *v, struct subre *t)
 
static int numst (struct subre *t, int start)
 
static void markst (struct subre *t)
 
static void cleanst (struct vars *v)
 
static long nfatree (struct vars *v, struct subre *t, FILE *f)
 
static long nfanode (struct vars *v, struct subre *t, int converttosearch, FILE *f)
 
static int newlacon (struct vars *v, struct state *begin, struct state *end, int latype)
 
static void freelacons (struct subre *subs, int n)
 
static void rfree (regex_t *re)
 
static int rstacktoodeep (void)
 
static void lexstart (struct vars *v)
 
static void prefixes (struct vars *v)
 
static int next (struct vars *v)
 
static int lexescape (struct vars *v)
 
static chr lexdigits (struct vars *v, int base, int minlen, int maxlen)
 
static int brenext (struct vars *v, chr c)
 
static void skip (struct vars *v)
 
static chr newline (void)
 
static chr chrnamed (struct vars *v, const chr *startp, const chr *endp, chr lastresort)
 
static void initcm (struct vars *v, struct colormap *cm)
 
static void freecm (struct colormap *cm)
 
static color maxcolor (struct colormap *cm)
 
static color newcolor (struct colormap *cm)
 
static void freecolor (struct colormap *cm, color co)
 
static color pseudocolor (struct colormap *cm)
 
static color subcolor (struct colormap *cm, chr c)
 
static color subcolorhi (struct colormap *cm, color *pco)
 
static color newsub (struct colormap *cm, color co)
 
static int newhicolorrow (struct colormap *cm, int oldrow)
 
static void newhicolorcols (struct colormap *cm)
 
static void subcolorcvec (struct vars *v, struct cvec *cv, struct state *lp, struct state *rp)
 
static void subcoloronechr (struct vars *v, chr ch, struct state *lp, struct state *rp, color *lastsubcolor)
 
static void subcoloronerange (struct vars *v, chr from, chr to, struct state *lp, struct state *rp, color *lastsubcolor)
 
static void subcoloronerow (struct vars *v, int rownum, struct state *lp, struct state *rp, color *lastsubcolor)
 
static void okcolors (struct nfa *nfa, struct colormap *cm)
 
static void colorchain (struct colormap *cm, struct arc *a)
 
static void uncolorchain (struct colormap *cm, struct arc *a)
 
static void rainbow (struct nfa *nfa, struct colormap *cm, int type, color but, struct state *from, struct state *to)
 
static void colorcomplement (struct nfa *nfa, struct colormap *cm, int type, struct state *of, struct state *from, struct state *to)
 
static struct nfanewnfa (struct vars *v, struct colormap *cm, struct nfa *parent)
 
static void freenfa (struct nfa *nfa)
 
static struct statenewstate (struct nfa *nfa)
 
static struct statenewfstate (struct nfa *nfa, int flag)
 
static void dropstate (struct nfa *nfa, struct state *s)
 
static void freestate (struct nfa *nfa, struct state *s)
 
static void newarc (struct nfa *nfa, int t, color co, struct state *from, struct state *to)
 
static void createarc (struct nfa *nfa, int t, color co, struct state *from, struct state *to)
 
static struct arcallocarc (struct nfa *nfa)
 
static void freearc (struct nfa *nfa, struct arc *victim)
 
static void changearcsource (struct arc *a, struct state *newfrom)
 
static void changearctarget (struct arc *a, struct state *newto)
 
static int hasnonemptyout (struct state *s)
 
static struct arcfindarc (struct state *s, int type, color co)
 
static void cparc (struct nfa *nfa, struct arc *oa, struct state *from, struct state *to)
 
static void sortins (struct nfa *nfa, struct state *s)
 
static int sortins_cmp (const void *a, const void *b)
 
static void sortouts (struct nfa *nfa, struct state *s)
 
static int sortouts_cmp (const void *a, const void *b)
 
static void moveins (struct nfa *nfa, struct state *oldState, struct state *newState)
 
static void copyins (struct nfa *nfa, struct state *oldState, struct state *newState)
 
static void mergeins (struct nfa *nfa, struct state *s, struct arc **arcarray, int arccount)
 
static void moveouts (struct nfa *nfa, struct state *oldState, struct state *newState)
 
static void copyouts (struct nfa *nfa, struct state *oldState, struct state *newState)
 
static void cloneouts (struct nfa *nfa, struct state *old, struct state *from, struct state *to, int type)
 
static void delsub (struct nfa *nfa, struct state *lp, struct state *rp)
 
static void deltraverse (struct nfa *nfa, struct state *leftend, struct state *s)
 
static void dupnfa (struct nfa *nfa, struct state *start, struct state *stop, struct state *from, struct state *to)
 
static void duptraverse (struct nfa *nfa, struct state *s, struct state *stmp)
 
static void removeconstraints (struct nfa *nfa, struct state *start, struct state *stop)
 
static void removetraverse (struct nfa *nfa, struct state *s)
 
static void cleartraverse (struct nfa *nfa, struct state *s)
 
static struct statesingle_color_transition (struct state *s1, struct state *s2)
 
static void specialcolors (struct nfa *nfa)
 
static long optimize (struct nfa *nfa, FILE *f)
 
static void pullback (struct nfa *nfa, FILE *f)
 
static int pull (struct nfa *nfa, struct arc *con, struct state **intermediates)
 
static void pushfwd (struct nfa *nfa, FILE *f)
 
static int push (struct nfa *nfa, struct arc *con, struct state **intermediates)
 
static int combine (struct nfa *nfa, struct arc *con, struct arc *a)
 
static void fixempties (struct nfa *nfa, FILE *f)
 
static struct stateemptyreachable (struct nfa *nfa, struct state *s, struct state *lastfound, struct arc **inarcsorig)
 
static int isconstraintarc (struct arc *a)
 
static int hasconstraintout (struct state *s)
 
static void fixconstraintloops (struct nfa *nfa, FILE *f)
 
static int findconstraintloop (struct nfa *nfa, struct state *s)
 
static void breakconstraintloop (struct nfa *nfa, struct state *sinitial)
 
static void clonesuccessorstates (struct nfa *nfa, struct state *ssource, struct state *sclone, struct state *spredecessor, struct arc *refarc, char *curdonemap, char *outerdonemap, int nstates)
 
static void removecantmatch (struct nfa *nfa)
 
static void cleanup (struct nfa *nfa)
 
static void markreachable (struct nfa *nfa, struct state *s, struct state *okay, struct state *mark)
 
static void markcanreach (struct nfa *nfa, struct state *s, struct state *okay, struct state *mark)
 
static long analyze (struct nfa *nfa)
 
static void checkmatchall (struct nfa *nfa)
 
static bool checkmatchall_recurse (struct nfa *nfa, struct state *s, bool **haspaths)
 
static bool check_out_colors_match (struct state *s, color co1, color co2)
 
static bool check_in_colors_match (struct state *s, color co1, color co2)
 
static void compact (struct nfa *nfa, struct cnfa *cnfa)
 
static void carcsort (struct carc *first, size_t n)
 
static int carc_cmp (const void *a, const void *b)
 
static void freecnfa (struct cnfa *cnfa)
 
static void dumpnfa (struct nfa *nfa, FILE *f)
 
static struct cvecnewcvec (int nchrs, int nranges)
 
static struct cvecclearcvec (struct cvec *cv)
 
static void addchr (struct cvec *cv, chr c)
 
static void addrange (struct cvec *cv, chr from, chr to)
 
static struct cvecgetcvec (struct vars *v, int nchrs, int nranges)
 
static void freecvec (struct cvec *cv)
 
static int pg_wc_isdigit (pg_wchar c)
 
static int pg_wc_isalpha (pg_wchar c)
 
static int pg_wc_isalnum (pg_wchar c)
 
static int pg_wc_isword (pg_wchar c)
 
static int pg_wc_isupper (pg_wchar c)
 
static int pg_wc_islower (pg_wchar c)
 
static int pg_wc_isgraph (pg_wchar c)
 
static int pg_wc_isprint (pg_wchar c)
 
static int pg_wc_ispunct (pg_wchar c)
 
static int pg_wc_isspace (pg_wchar c)
 
static pg_wchar pg_wc_toupper (pg_wchar c)
 
static pg_wchar pg_wc_tolower (pg_wchar c)
 
static chr element (struct vars *v, const chr *startp, const chr *endp)
 
static struct cvecrange (struct vars *v, chr a, chr b, int cases)
 
static int before (chr x, chr y)
 
static struct cvececlass (struct vars *v, chr c, int cases)
 
static enum char_classes lookupcclass (struct vars *v, const chr *startp, const chr *endp)
 
static struct cveccclasscvec (struct vars *v, enum char_classes cclasscode, int cases)
 
static int cclass_column_index (struct colormap *cm, chr c)
 
static struct cvecallcases (struct vars *v, chr c)
 
static int cmp (const chr *x, const chr *y, size_t len)
 
static int casecmp (const chr *x, const chr *y, size_t len)
 
int pg_regcomp (regex_t *re, const chr *string, size_t len, int flags, Oid collation)
 

Variables

static const struct fns functions
 

Macro Definition Documentation

◆ AHEAD

#define AHEAD   'a' /* color-lookahead arc */

Definition at line 342 of file regcomp.c.

◆ ARCV

#define ARCV (   t,
  val 
)    newarc(v->nfa, t, val, lp, rp)

◆ BACKREF

#define BACKREF   'b' /* back reference */

Definition at line 333 of file regcomp.c.

◆ BEHIND

#define BEHIND   'r' /* color-lookbehind arc */

Definition at line 343 of file regcomp.c.

◆ CANTMATCH

#define CANTMATCH   'x' /* arc that cannot match anything */

Definition at line 346 of file regcomp.c.

◆ CCLASS

#define CCLASS   'C' /* start of [: */

Definition at line 336 of file regcomp.c.

◆ CCLASSC

#define CCLASSC   'c' /* complement char class shorthand escape */

Definition at line 339 of file regcomp.c.

◆ CCLASSS

#define CCLASSS   's' /* char class shorthand escape */

Definition at line 338 of file regcomp.c.

◆ CNOERR

#define CNOERR ( )    { if (ISERR()) return freev(v, v->err); }

◆ COLLEL

#define COLLEL   'I' /* start of [. */

Definition at line 334 of file regcomp.c.

◆ COLORED

#define COLORED (   a)
Value:
((a)->co >= 0 && \
((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND))
int a
Definition: isn.c:68
#define BEHIND
Definition: regcomp.c:343
#define AHEAD
Definition: regcomp.c:342
#define PLAIN
Definition: regcomp.c:331
const char * type

Definition at line 352 of file regcomp.c.

◆ COMPATIBLE

#define COMPATIBLE   3 /* compatible but not satisfied yet */

Definition at line 201 of file regcomp.c.

◆ DIGIT

#define DIGIT   'd' /* digit (in bound) */

Definition at line 332 of file regcomp.c.

◆ EAT

#define EAT (   t)    (SEE(t) && next(v)) /* if next is this, swallow it */

Definition at line 315 of file regcomp.c.

◆ ECLASS

#define ECLASS   'E' /* start of [= */

Definition at line 335 of file regcomp.c.

◆ EMPTY

#define EMPTY   'n' /* no token present */

Definition at line 329 of file regcomp.c.

◆ EMPTYARC

#define EMPTYARC (   x,
  y 
)    newarc(v->nfa, EMPTY, 0, x, y)

Definition at line 326 of file regcomp.c.

◆ END

#define END   'X' /* end of [. [= [: */

Definition at line 337 of file regcomp.c.

◆ EOS

#define EOS   'e' /* end of string */

Definition at line 330 of file regcomp.c.

◆ ERR

#define ERR (   e)    VERR(v, e) /* record an error */

Definition at line 320 of file regcomp.c.

◆ INCOMPATIBLE

#define INCOMPATIBLE   1 /* destroys arc */

Definition at line 199 of file regcomp.c.

◆ INF

#define INF   3

◆ INSIST

#define INSIST (   c,
  e 
)    do { if (!(c)) ERR(e); } while (0) /* error if c false */

Definition at line 324 of file regcomp.c.

◆ ISERR

#define ISERR ( )    VISERR(v)

Definition at line 317 of file regcomp.c.

◆ LACON

#define LACON   'L' /* lookaround constraint subRE */

Definition at line 341 of file regcomp.c.

◆ NEXT

#define NEXT ( )    (next(v)) /* advance by one token */

Definition at line 313 of file regcomp.c.

◆ NOERR

#define NOERR ( )    {if (ISERR()) return;} /* if error seen, return */

Definition at line 321 of file regcomp.c.

◆ NOERRN

#define NOERRN ( )    {if (ISERR()) return NULL;} /* NOERR with retval */

Definition at line 322 of file regcomp.c.

◆ NOERRZ

#define NOERRZ ( )    {if (ISERR()) return 0;} /* NOERR with retval */

Definition at line 323 of file regcomp.c.

◆ NOTE

#define NOTE (   b)    (v->re->re_info |= (b)) /* note visible condition */

Definition at line 325 of file regcomp.c.

◆ NWBDRY

#define NWBDRY   'W' /* non-word-boundary constraint */

Definition at line 345 of file regcomp.c.

◆ PAIR

#define PAIR (   x,
  y 
)    ((x)*4 + (y))

◆ PLAIN

#define PLAIN   'p' /* ordinary character */

Definition at line 331 of file regcomp.c.

◆ RANGE

#define RANGE   'R' /* - within [] which might be range delim. */

Definition at line 340 of file regcomp.c.

◆ REDUCE

#define REDUCE (   x)    ( ((x) == DUPINF) ? INF : (((x) > 1) ? SOME : (x)) )

◆ REPLACEARC

#define REPLACEARC   4 /* replace arc's color with constraint color */

Definition at line 202 of file regcomp.c.

◆ SATISFIED

#define SATISFIED   2 /* constraint satisfied */

Definition at line 200 of file regcomp.c.

◆ SBEGIN

#define SBEGIN   'A' /* beginning of string (even if not BOL) */

Definition at line 347 of file regcomp.c.

◆ SEE

#define SEE (   t)    (v->nexttype == (t)) /* is next token this? */

Definition at line 314 of file regcomp.c.

◆ SEND

#define SEND   'Z' /* end of string (even if not EOL) */

Definition at line 348 of file regcomp.c.

◆ SOME

#define SOME   2

◆ VERR

#define VERR (   vv,
  e 
)
Value:
((vv)->nexttype = EOS, \
(vv)->err = ((vv)->err ? (vv)->err : (e)))
void err(int eval, const char *fmt,...)
Definition: err.c:43
e
Definition: preproc-init.c:82
#define EOS
Definition: regcomp.c:330

Definition at line 318 of file regcomp.c.

◆ VISERR

#define VISERR (   vv)    ((vv)->err != 0) /* have we seen an error yet? */

Definition at line 316 of file regcomp.c.

◆ WBDRY

#define WBDRY   'w' /* word boundary constraint */

Definition at line 344 of file regcomp.c.

Function Documentation

◆ addchr()

static void addchr ( struct cvec cv,
chr  c 
)
static

◆ addrange()

static void addrange ( struct cvec cv,
chr  from,
chr  to 
)
static

◆ allcases()

static struct cvec* allcases ( struct vars v,
chr  c 
)
static

Referenced by onechr().

◆ allocarc()

static struct arc* allocarc ( struct nfa nfa)
static

◆ analyze()

static long analyze ( struct nfa nfa)
static

◆ before()

static int before ( chr  x,
chr  y 
)
static

◆ bracket()

static void bracket ( struct vars v,
struct state lp,
struct state rp 
)
static

Definition at line 1673 of file regcomp.c.

1676 {
1677  /*
1678  * We can't process complemented char classes (e.g. \W) immediately while
1679  * scanning the bracket expression, else color bookkeeping gets confused.
1680  * Instead, remember whether we saw any in have_cclassc[], and process
1681  * them at the end.
1682  */
1683  bool have_cclassc[NUM_CCLASSES];
1684  bool any_cclassc;
1685  int i;
1686 
1687  memset(have_cclassc, false, sizeof(have_cclassc));
1688 
1689  assert(SEE('['));
1690  NEXT();
1691  while (!SEE(']') && !SEE(EOS))
1692  brackpart(v, lp, rp, have_cclassc);
1693  assert(SEE(']') || ISERR());
1694 
1695  /* close up open subcolors from the positive bracket elements */
1696  okcolors(v->nfa, v->cm);
1697  NOERR();
1698 
1699  /* now handle any complemented elements */
1700  any_cclassc = false;
1701  for (i = 0; i < NUM_CCLASSES; i++)
1702  {
1703  if (have_cclassc[i])
1704  {
1705  charclasscomplement(v, (enum char_classes) i, lp, rp);
1706  NOERR();
1707  any_cclassc = true;
1708  }
1709  }
1710 
1711  /*
1712  * If we had any complemented elements, see if we can optimize the bracket
1713  * into a rainbow. Since a complemented element is the only way a WHITE
1714  * arc could get into the result, there's no point in checking otherwise.
1715  */
1716  if (any_cclassc)
1717  optimizebracket(v, lp, rp);
1718 }
int i
Definition: isn.c:72
#define NOERR()
Definition: regcomp.c:321
#define ISERR()
Definition: regcomp.c:317
static void optimizebracket(struct vars *v, struct state *lp, struct state *rp)
Definition: regcomp.c:1937
#define SEE(t)
Definition: regcomp.c:314
static void okcolors(struct nfa *nfa, struct colormap *cm)
static void charclasscomplement(struct vars *v, enum char_classes cls, struct state *lp, struct state *rp)
Definition: regcomp.c:1518
static void brackpart(struct vars *v, struct state *lp, struct state *rp, bool *have_cclassc)
Definition: regcomp.c:1763
#define NEXT()
Definition: regcomp.c:313
#define assert(x)
Definition: regcustom.h:56
#define NUM_CCLASSES
Definition: regguts.h:144
char_classes
Definition: regguts.h:139
struct colormap * cm
Definition: regcomp.c:297
struct nfa * nfa
Definition: regcomp.c:296

References assert, brackpart(), charclasscomplement(), vars::cm, EOS, i, ISERR, NEXT, vars::nfa, NOERR, NUM_CCLASSES, okcolors(), optimizebracket(), and SEE.

Referenced by cbracket(), and parseqatom().

◆ brackpart()

static void brackpart ( struct vars v,
struct state lp,
struct state rp,
bool *  have_cclassc 
)
static

Definition at line 1763 of file regcomp.c.

1767 {
1768  chr startc;
1769  chr endc;
1770  struct cvec *cv;
1771  enum char_classes cls;
1772  const chr *startp;
1773  const chr *endp;
1774 
1775  /* parse something, get rid of special cases, take shortcuts */
1776  switch (v->nexttype)
1777  {
1778  case RANGE: /* a-b-c or other botch */
1779  ERR(REG_ERANGE);
1780  return;
1781  break;
1782  case PLAIN:
1783  startc = v->nextvalue;
1784  NEXT();
1785  /* shortcut for ordinary chr (not range) */
1786  if (!SEE(RANGE))
1787  {
1788  onechr(v, startc, lp, rp);
1789  return;
1790  }
1791  NOERR();
1792  break;
1793  case COLLEL:
1794  startp = v->now;
1795  endp = scanplain(v);
1796  INSIST(startp < endp, REG_ECOLLATE);
1797  NOERR();
1798  startc = element(v, startp, endp);
1799  NOERR();
1800  break;
1801  case ECLASS:
1802  startp = v->now;
1803  endp = scanplain(v);
1804  INSIST(startp < endp, REG_ECOLLATE);
1805  NOERR();
1806  startc = element(v, startp, endp);
1807  NOERR();
1808  cv = eclass(v, startc, (v->cflags & REG_ICASE));
1809  NOERR();
1810  subcolorcvec(v, cv, lp, rp);
1811  return;
1812  break;
1813  case CCLASS:
1814  startp = v->now;
1815  endp = scanplain(v);
1816  INSIST(startp < endp, REG_ECTYPE);
1817  NOERR();
1818  cls = lookupcclass(v, startp, endp);
1819  NOERR();
1820  charclass(v, cls, lp, rp);
1821  return;
1822  break;
1823  case CCLASSS:
1824  charclass(v, (enum char_classes) v->nextvalue, lp, rp);
1825  NEXT();
1826  return;
1827  break;
1828  case CCLASSC:
1829  /* we cannot call charclasscomplement() immediately */
1830  have_cclassc[v->nextvalue] = true;
1831  NEXT();
1832  return;
1833  break;
1834  default:
1835  ERR(REG_ASSERT);
1836  return;
1837  break;
1838  }
1839 
1840  if (SEE(RANGE))
1841  {
1842  NEXT();
1843  switch (v->nexttype)
1844  {
1845  case PLAIN:
1846  case RANGE:
1847  endc = v->nextvalue;
1848  NEXT();
1849  NOERR();
1850  break;
1851  case COLLEL:
1852  startp = v->now;
1853  endp = scanplain(v);
1854  INSIST(startp < endp, REG_ECOLLATE);
1855  NOERR();
1856  endc = element(v, startp, endp);
1857  NOERR();
1858  break;
1859  default:
1860  ERR(REG_ERANGE);
1861  return;
1862  break;
1863  }
1864  }
1865  else
1866  endc = startc;
1867 
1868  /*
1869  * Ranges are unportable. Actually, standard C does guarantee that digits
1870  * are contiguous, but making that an exception is just too complicated.
1871  */
1872  if (startc != endc)
1873  NOTE(REG_UUNPORT);
1874  cv = range(v, startc, endc, (v->cflags & REG_ICASE));
1875  NOERR();
1876  subcolorcvec(v, cv, lp, rp);
1877 }
#define COLLEL
Definition: regcomp.c:334
static void subcolorcvec(struct vars *v, struct cvec *cv, struct state *lp, struct state *rp)
#define NOTE(b)
Definition: regcomp.c:325
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
#define CCLASSS
Definition: regcomp.c:338
#define ERR(e)
Definition: regcomp.c:320
#define CCLASS
Definition: regcomp.c:336
static enum char_classes lookupcclass(struct vars *v, const chr *startp, const chr *endp)
#define CCLASSC
Definition: regcomp.c:339
static struct cvec * eclass(struct vars *v, chr c, int cases)
static const chr * scanplain(struct vars *v)
Definition: regcomp.c:1886
static void charclass(struct vars *v, enum char_classes cls, struct state *lp, struct state *rp)
Definition: regcomp.c:1494
#define ECLASS
Definition: regcomp.c:335
#define RANGE
Definition: regcomp.c:340
#define INSIST(c, e)
Definition: regcomp.c:324
static chr element(struct vars *v, const chr *startp, const chr *endp)
static void onechr(struct vars *v, chr c, struct state *lp, struct state *rp)
Definition: regcomp.c:1911
pg_wchar chr
Definition: regcustom.h:59
#define REG_ICASE
Definition: regex.h:184
#define REG_ECTYPE
Definition: regex.h:219
#define REG_ASSERT
Definition: regex.h:229
#define REG_ERANGE
Definition: regex.h:226
#define REG_ECOLLATE
Definition: regex.h:218
#define REG_UUNPORT
Definition: regex.h:147
Definition: regguts.h:279
const chr * now
Definition: regcomp.c:284
int cflags
Definition: regcomp.c:287
chr nextvalue
Definition: regcomp.c:290
int nexttype
Definition: regcomp.c:289

References CCLASS, CCLASSC, CCLASSS, vars::cflags, charclass(), COLLEL, eclass(), ECLASS, element(), ERR, INSIST, lookupcclass(), NEXT, vars::nexttype, vars::nextvalue, NOERR, NOTE, vars::now, onechr(), PLAIN, range(), RANGE, REG_ASSERT, REG_ECOLLATE, REG_ECTYPE, REG_ERANGE, REG_ICASE, REG_UUNPORT, scanplain(), SEE, and subcolorcvec().

Referenced by bracket().

◆ breakconstraintloop()

static void breakconstraintloop ( struct nfa nfa,
struct state sinitial 
)
static

◆ brenext()

static int brenext ( struct vars v,
chr  c 
)
static

◆ carc_cmp()

static int carc_cmp ( const void *  a,
const void *  b 
)
static

◆ carcsort()

static void carcsort ( struct carc first,
size_t  n 
)
static

◆ casecmp()

static int casecmp ( const chr x,
const chr y,
size_t  len 
)
static

Referenced by pg_regcomp().

◆ cbracket()

static void cbracket ( struct vars v,
struct state lp,
struct state rp 
)
static

Definition at line 1729 of file regcomp.c.

1732 {
1733  struct state *left = newstate(v->nfa);
1734  struct state *right = newstate(v->nfa);
1735 
1736  NOERR();
1737  bracket(v, left, right);
1738 
1739  /* in NLSTOP mode, ensure newline is not part of the result set */
1740  if (v->cflags & REG_NLSTOP)
1741  newarc(v->nfa, PLAIN, v->nlcolor, left, right);
1742  NOERR();
1743 
1744  assert(lp->nouts == 0); /* all outarcs will be ours */
1745 
1746  /*
1747  * Easy part of complementing, and all there is to do since the MCCE code
1748  * was removed. Note that the result of colorcomplement() cannot be a
1749  * rainbow, since we don't allow empty brackets; so there's no point in
1750  * calling optimizebracket() again.
1751  */
1752  colorcomplement(v->nfa, v->cm, PLAIN, left, lp, rp);
1753  NOERR();
1754  dropstate(v->nfa, left);
1755  assert(right->nins == 0);
1756  freestate(v->nfa, right);
1757 }
static void newarc(struct nfa *nfa, int t, color co, struct state *from, struct state *to)
static void dropstate(struct nfa *nfa, struct state *s)
static void bracket(struct vars *v, struct state *lp, struct state *rp)
Definition: regcomp.c:1673
static struct state * newstate(struct nfa *nfa)
static void colorcomplement(struct nfa *nfa, struct colormap *cm, int type, struct state *of, struct state *from, struct state *to)
static void freestate(struct nfa *nfa, struct state *s)
#define REG_NLSTOP
Definition: regex.h:187
Definition: regguts.h:323
int nins
Definition: regguts.h:327
int nouts
Definition: regguts.h:328
color nlcolor
Definition: regcomp.c:298

References assert, bracket(), vars::cflags, vars::cm, colorcomplement(), dropstate(), freestate(), newarc(), newstate(), vars::nfa, state::nins, vars::nlcolor, NOERR, state::nouts, PLAIN, and REG_NLSTOP.

Referenced by parseqatom().

◆ cclass_column_index()

static int cclass_column_index ( struct colormap cm,
chr  c 
)
static

◆ cclasscvec()

static struct cvec* cclasscvec ( struct vars v,
enum char_classes  cclasscode,
int  cases 
)
static

◆ changearcsource()

static void changearcsource ( struct arc a,
struct state newfrom 
)
static

◆ changearctarget()

static void changearctarget ( struct arc a,
struct state newto 
)
static

◆ charclass()

static void charclass ( struct vars v,
enum char_classes  cls,
struct state lp,
struct state rp 
)
static

Definition at line 1494 of file regcomp.c.

1498 {
1499  struct cvec *cv;
1500 
1501  /* obtain possibly-cached cvec for char class */
1502  NOTE(REG_ULOCALE);
1503  cv = cclasscvec(v, cls, (v->cflags & REG_ICASE));
1504  NOERR();
1505 
1506  /* build the arcs; this may cause color splitting */
1507  subcolorcvec(v, cv, lp, rp);
1508 }
static struct cvec * cclasscvec(struct vars *v, enum char_classes cclasscode, int cases)
#define REG_ULOCALE
Definition: regex.h:148

References cclasscvec(), vars::cflags, NOERR, NOTE, REG_ICASE, REG_ULOCALE, and subcolorcvec().

Referenced by brackpart(), and parseqatom().

◆ charclasscomplement()

static void charclasscomplement ( struct vars v,
enum char_classes  cls,
struct state lp,
struct state rp 
)
static

Definition at line 1518 of file regcomp.c.

1522 {
1523  struct state *cstate;
1524  struct cvec *cv;
1525 
1526  /* make dummy state to hang temporary arcs on */
1527  cstate = newstate(v->nfa);
1528  NOERR();
1529 
1530  /* obtain possibly-cached cvec for char class */
1531  NOTE(REG_ULOCALE);
1532  cv = cclasscvec(v, cls, (v->cflags & REG_ICASE));
1533  NOERR();
1534 
1535  /* build arcs for char class; this may cause color splitting */
1536  subcolorcvec(v, cv, cstate, cstate);
1537  NOERR();
1538 
1539  /* clean up any subcolors in the arc set */
1540  okcolors(v->nfa, v->cm);
1541  NOERR();
1542 
1543  /* now build output arcs for the complement of the char class */
1544  colorcomplement(v->nfa, v->cm, PLAIN, cstate, lp, rp);
1545  NOERR();
1546 
1547  /* clean up dummy state */
1548  dropstate(v->nfa, cstate);
1549 }

References cclasscvec(), vars::cflags, vars::cm, colorcomplement(), dropstate(), newstate(), vars::nfa, NOERR, NOTE, okcolors(), PLAIN, REG_ICASE, REG_ULOCALE, and subcolorcvec().

Referenced by bracket(), and parseqatom().

◆ check_in_colors_match()

static bool check_in_colors_match ( struct state s,
color  co1,
color  co2 
)
static

◆ check_out_colors_match()

static bool check_out_colors_match ( struct state s,
color  co1,
color  co2 
)
static

◆ checkmatchall()

static void checkmatchall ( struct nfa nfa)
static

◆ checkmatchall_recurse()

static bool checkmatchall_recurse ( struct nfa nfa,
struct state s,
bool **  haspaths 
)
static

◆ chrnamed()

static chr chrnamed ( struct vars v,
const chr startp,
const chr endp,
chr  lastresort 
)
static

◆ cleanst()

static void cleanst ( struct vars v)
static

Definition at line 2312 of file regcomp.c.

2313 {
2314  struct subre *t;
2315  struct subre *next;
2316 
2317  for (t = v->treechain; t != NULL; t = next)
2318  {
2319  next = t->chain;
2320  if (!(t->flags & INUSE))
2321  FREE(t);
2322  }
2323  v->treechain = NULL;
2324  v->treefree = NULL; /* just on general principles */
2325 }
static int next(struct vars *v)
#define INUSE
Definition: regguts.h:488
Definition: regguts.h:479
struct subre * chain
Definition: regguts.h:508
char flags
Definition: regguts.h:481
struct subre * treechain
Definition: regcomp.c:301
struct subre * treefree
Definition: regcomp.c:302
@ FREE
Definition: task.c:94

References subre::chain, subre::flags, FREE, INUSE, next(), vars::treechain, and vars::treefree.

Referenced by freev(), and pg_regcomp().

◆ cleanup()

static void cleanup ( struct nfa nfa)
static

◆ clearcvec()

static struct cvec* clearcvec ( struct cvec cv)
static

◆ cleartraverse()

static void cleartraverse ( struct nfa nfa,
struct state s 
)
static

◆ cloneouts()

static void cloneouts ( struct nfa nfa,
struct state old,
struct state from,
struct state to,
int  type 
)
static

Referenced by processlacon(), and word().

◆ clonesuccessorstates()

static void clonesuccessorstates ( struct nfa nfa,
struct state ssource,
struct state sclone,
struct state spredecessor,
struct arc refarc,
char *  curdonemap,
char *  outerdonemap,
int  nstates 
)
static

◆ cmp()

static int cmp ( const chr x,
const chr y,
size_t  len 
)
static

Referenced by pg_regcomp().

◆ colorchain()

static void colorchain ( struct colormap cm,
struct arc a 
)
static

◆ colorcomplement()

static void colorcomplement ( struct nfa nfa,
struct colormap cm,
int  type,
struct state of,
struct state from,
struct state to 
)
static

◆ combine()

static int combine ( struct nfa nfa,
struct arc con,
struct arc a 
)
static

◆ compact()

static void compact ( struct nfa nfa,
struct cnfa cnfa 
)
static

Referenced by nfanode(), and pg_regcomp().

◆ copyins()

static void copyins ( struct nfa nfa,
struct state oldState,
struct state newState 
)
static

◆ copyouts()

static void copyouts ( struct nfa nfa,
struct state oldState,
struct state newState 
)
static

Referenced by makesearch().

◆ cparc()

static void cparc ( struct nfa nfa,
struct arc oa,
struct state from,
struct state to 
)
static

Referenced by makesearch().

◆ createarc()

static void createarc ( struct nfa nfa,
int  t,
color  co,
struct state from,
struct state to 
)
static

◆ delsub()

static void delsub ( struct nfa nfa,
struct state lp,
struct state rp 
)
static

Referenced by parseqatom(), and repeat().

◆ deltraverse()

static void deltraverse ( struct nfa nfa,
struct state leftend,
struct state s 
)
static

◆ dropstate()

static void dropstate ( struct nfa nfa,
struct state s 
)
static

Referenced by cbracket(), and charclasscomplement().

◆ dumpnfa()

static void dumpnfa ( struct nfa nfa,
FILE *  f 
)
static

Referenced by pg_regcomp().

◆ dupnfa()

static void dupnfa ( struct nfa nfa,
struct state start,
struct state stop,
struct state from,
struct state to 
)
static

Referenced by nfanode(), parseqatom(), and repeat().

◆ duptraverse()

static void duptraverse ( struct nfa nfa,
struct state s,
struct state stmp 
)
static

◆ eclass()

static struct cvec* eclass ( struct vars v,
chr  c,
int  cases 
)
static

Referenced by brackpart().

◆ element()

static chr element ( struct vars v,
const chr startp,
const chr endp 
)
static

Referenced by brackpart().

◆ emptyreachable()

static struct state* emptyreachable ( struct nfa nfa,
struct state s,
struct state lastfound,
struct arc **  inarcsorig 
)
static

◆ findarc()

static struct arc* findarc ( struct state s,
int  type,
color  co 
)
static

◆ findconstraintloop()

static int findconstraintloop ( struct nfa nfa,
struct state s 
)
static

◆ fixconstraintloops()

static void fixconstraintloops ( struct nfa nfa,
FILE *  f 
)
static

◆ fixempties()

static void fixempties ( struct nfa nfa,
FILE *  f 
)
static

◆ freearc()

static void freearc ( struct nfa nfa,
struct arc victim 
)
static

Referenced by makesearch(), and optimizebracket().

◆ freecm()

static void freecm ( struct colormap cm)
static

Referenced by rfree().

◆ freecnfa()

static void freecnfa ( struct cnfa cnfa)
static

Referenced by freelacons(), freesrnode(), and rfree().

◆ freecolor()

static void freecolor ( struct colormap cm,
color  co 
)
static

◆ freecvec()

static void freecvec ( struct cvec cv)
static

Referenced by freev().

◆ freelacons()

static void freelacons ( struct subre subs,
int  n 
)
static

Definition at line 2430 of file regcomp.c.

2432 {
2433  struct subre *sub;
2434  int i;
2435 
2436  assert(n > 0);
2437  for (sub = subs + 1, i = n - 1; i > 0; sub++, i--) /* no 0th */
2438  if (!NULLCNFA(sub->cnfa))
2439  freecnfa(&sub->cnfa);
2440  FREE(subs);
2441 }
static void freecnfa(struct cnfa *cnfa)
#define NULLCNFA(cnfa)
Definition: regguts.h:438
struct cnfa cnfa
Definition: regguts.h:507

References assert, subre::cnfa, FREE, freecnfa(), i, and NULLCNFA.

Referenced by freev(), and rfree().

◆ freenfa()

static void freenfa ( struct nfa nfa)
static

Referenced by freev(), and nfanode().

◆ freesrnode()

static void freesrnode ( struct vars v,
struct subre sr 
)
static

Definition at line 2187 of file regcomp.c.

2189 {
2190  if (sr == NULL)
2191  return;
2192 
2193  if (!NULLCNFA(sr->cnfa))
2194  freecnfa(&sr->cnfa);
2195  sr->flags = 0; /* in particular, not INUSE */
2196  sr->child = sr->sibling = NULL;
2197  sr->begin = sr->end = NULL;
2198 
2199  if (v != NULL && v->treechain != NULL)
2200  {
2201  /* we're still parsing, maybe we can reuse the subre */
2202  sr->child = v->treefree;
2203  v->treefree = sr;
2204  }
2205  else
2206  FREE(sr);
2207 }
struct state * end
Definition: regguts.h:506
struct subre * sibling
Definition: regguts.h:504
struct subre * child
Definition: regguts.h:503
struct state * begin
Definition: regguts.h:505

References subre::begin, subre::child, subre::cnfa, subre::end, subre::flags, FREE, freecnfa(), NULLCNFA, subre::sibling, vars::treechain, and vars::treefree.

Referenced by freesubre(), parse(), and parseqatom().

◆ freestate()

static void freestate ( struct nfa nfa,
struct state s 
)
static

Referenced by cbracket().

◆ freesubre()

static void freesubre ( struct vars v,
struct subre sr 
)
static

Definition at line 2152 of file regcomp.c.

2154 {
2155  if (sr == NULL)
2156  return;
2157 
2158  if (sr->child != NULL)
2159  freesubreandsiblings(v, sr->child);
2160 
2161  freesrnode(v, sr);
2162 }
static void freesubreandsiblings(struct vars *v, struct subre *sr)
Definition: regcomp.c:2171
static void freesrnode(struct vars *v, struct subre *sr)
Definition: regcomp.c:2187

References subre::child, freesrnode(), and freesubreandsiblings().

Referenced by freesubreandsiblings(), freev(), parseqatom(), and rfree().

◆ freesubreandsiblings()

static void freesubreandsiblings ( struct vars v,
struct subre sr 
)
static

Definition at line 2171 of file regcomp.c.

2173 {
2174  while (sr != NULL)
2175  {
2176  struct subre *next = sr->sibling;
2177 
2178  freesubre(v, sr);
2179  sr = next;
2180  }
2181 }
static void freesubre(struct vars *v, struct subre *sr)
Definition: regcomp.c:2152

References freesubre(), next(), and subre::sibling.

Referenced by freesubre(), parse(), parseqatom(), and removecaptures().

◆ freev()

static int freev ( struct vars v,
int  err 
)
static

Definition at line 592 of file regcomp.c.

594 {
595  if (v->re != NULL)
596  rfree(v->re);
597  if (v->subs != v->sub10)
598  FREE(v->subs);
599  if (v->nfa != NULL)
600  freenfa(v->nfa);
601  if (v->tree != NULL)
602  freesubre(v, v->tree);
603  if (v->treechain != NULL)
604  cleanst(v);
605  if (v->cv != NULL)
606  freecvec(v->cv);
607  if (v->cv2 != NULL)
608  freecvec(v->cv2);
609  if (v->lacons != NULL)
610  freelacons(v->lacons, v->nlacons);
611  ERR(err); /* nop if err==0 */
612 
613  return v->err;
614 }
static void freecvec(struct cvec *cv)
static void freenfa(struct nfa *nfa)
static void cleanst(struct vars *v)
Definition: regcomp.c:2312
static void rfree(regex_t *re)
Definition: regcomp.c:2447
static void freelacons(struct subre *subs, int n)
Definition: regcomp.c:2430
struct subre * tree
Definition: regcomp.c:300
struct subre ** subs
Definition: regcomp.c:293
int nlacons
Definition: regcomp.c:307
struct subre * lacons
Definition: regcomp.c:306
int err
Definition: regcomp.c:286
regex_t * re
Definition: regcomp.c:283
struct subre * sub10[10]
Definition: regcomp.c:295
struct cvec * cv2
Definition: regcomp.c:305
struct cvec * cv
Definition: regcomp.c:304

References cleanst(), vars::cv, vars::cv2, vars::err, ERR, err(), FREE, freecvec(), freelacons(), freenfa(), freesubre(), vars::lacons, vars::nfa, vars::nlacons, vars::re, rfree(), vars::sub10, vars::subs, vars::tree, and vars::treechain.

Referenced by pg_regcomp().

◆ getcvec()

static struct cvec* getcvec ( struct vars v,
int  nchrs,
int  nranges 
)
static

◆ hasconstraintout()

static int hasconstraintout ( struct state s)
static

◆ hasnonemptyout()

static int hasnonemptyout ( struct state s)
static

◆ initcm()

static void initcm ( struct vars v,
struct colormap cm 
)
static

Referenced by pg_regcomp().

◆ isconstraintarc()

static int isconstraintarc ( struct arc a)
static

◆ lexdigits()

static chr lexdigits ( struct vars v,
int  base,
int  minlen,
int  maxlen 
)
static

◆ lexescape()

static int lexescape ( struct vars v)
static

◆ lexstart()

static void lexstart ( struct vars v)
static

Referenced by pg_regcomp().

◆ lookupcclass()

static enum char_classes lookupcclass ( struct vars v,
const chr startp,
const chr endp 
)
static

Referenced by brackpart().

◆ makesearch()

static void makesearch ( struct vars v,
struct nfa nfa 
)
static

Definition at line 621 of file regcomp.c.

623 {
624  struct arc *a;
625  struct arc *b;
626  struct state *pre = nfa->pre;
627  struct state *s;
628  struct state *s2;
629  struct state *slist;
630 
631  /* no loops are needed if it's anchored */
632  for (a = pre->outs; a != NULL; a = a->outchain)
633  {
634  assert(a->type == PLAIN);
635  if (a->co != nfa->bos[0] && a->co != nfa->bos[1])
636  break;
637  }
638  if (a != NULL)
639  {
640  /* add implicit .* in front */
641  rainbow(nfa, v->cm, PLAIN, COLORLESS, pre, pre);
642 
643  /* and ^* and \A* too -- not always necessary, but harmless */
644  newarc(nfa, PLAIN, nfa->bos[0], pre, pre);
645  newarc(nfa, PLAIN, nfa->bos[1], pre, pre);
646 
647  /*
648  * The pattern is still MATCHALL if it was before, but the max match
649  * length is now infinity.
650  */
651  if (nfa->flags & MATCHALL)
653  }
654 
655  /*
656  * Now here's the subtle part. Because many REs have no lookback
657  * constraints, often knowing when you were in the pre state tells you
658  * little; it's the next state(s) that are informative. But some of them
659  * may have other inarcs, i.e. it may be possible to make actual progress
660  * and then return to one of them. We must de-optimize such cases,
661  * splitting each such state into progress and no-progress states.
662  */
663 
664  /* first, make a list of the states reachable from pre and elsewhere */
665  slist = NULL;
666  for (a = pre->outs; a != NULL; a = a->outchain)
667  {
668  s = a->to;
669  for (b = s->ins; b != NULL; b = b->inchain)
670  {
671  if (b->from != pre)
672  break;
673  }
674 
675  /*
676  * We want to mark states as being in the list already by having non
677  * NULL tmp fields, but we can't just store the old slist value in tmp
678  * because that doesn't work for the first such state. Instead, the
679  * first list entry gets its own address in tmp.
680  */
681  if (b != NULL && s->tmp == NULL)
682  {
683  s->tmp = (slist != NULL) ? slist : s;
684  slist = s;
685  }
686  }
687 
688  /* do the splits */
689  for (s = slist; s != NULL; s = s2)
690  {
691  s2 = newstate(nfa);
692  NOERR();
693  copyouts(nfa, s, s2);
694  NOERR();
695  for (a = s->ins; a != NULL; a = b)
696  {
697  b = a->inchain;
698  if (a->from != pre)
699  {
700  cparc(nfa, a, a->from, s2);
701  freearc(nfa, a);
702  }
703  }
704  s2 = (s->tmp != s) ? s->tmp : NULL;
705  s->tmp = NULL; /* clean up while we're at it */
706  }
707 }
int b
Definition: isn.c:69
char * s2
static void cparc(struct nfa *nfa, struct arc *oa, struct state *from, struct state *to)
static void copyouts(struct nfa *nfa, struct state *oldState, struct state *newState)
static void freearc(struct nfa *nfa, struct arc *victim)
static void rainbow(struct nfa *nfa, struct colormap *cm, int type, color but, struct state *from, struct state *to)
#define COLORLESS
Definition: regguts.h:158
#define DUPINF
Definition: regguts.h:99
#define MATCHALL
Definition: regguts.h:412
Definition: regguts.h:296
Definition: regguts.h:349
int maxmatchall
Definition: regguts.h:368
color bos[2]
Definition: regguts.h:364
int flags
Definition: regguts.h:366
struct state * pre
Definition: regguts.h:350
struct state * tmp
Definition: regguts.h:331
struct arc * outs
Definition: regguts.h:330
struct arc * ins
Definition: regguts.h:329

References a, assert, b, nfa::bos, vars::cm, COLORLESS, copyouts(), cparc(), DUPINF, nfa::flags, freearc(), state::ins, MATCHALL, nfa::maxmatchall, newarc(), newstate(), NOERR, state::outs, PLAIN, nfa::pre, rainbow(), s2, and state::tmp.

Referenced by nfanode(), and pg_regcomp().

◆ markcanreach()

static void markcanreach ( struct nfa nfa,
struct state s,
struct state okay,
struct state mark 
)
static

◆ markreachable()

static void markreachable ( struct nfa nfa,
struct state s,
struct state okay,
struct state mark 
)
static

◆ markst()

static void markst ( struct subre t)
static

Definition at line 2297 of file regcomp.c.

2298 {
2299  struct subre *t2;
2300 
2301  assert(t != NULL);
2302 
2303  t->flags |= INUSE;
2304  for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
2305  markst(t2);
2306 }
static void markst(struct subre *t)
Definition: regcomp.c:2297

References assert, subre::child, subre::flags, INUSE, and subre::sibling.

Referenced by pg_regcomp().

◆ maxcolor()

static color maxcolor ( struct colormap cm)
static

◆ mergeins()

static void mergeins ( struct nfa nfa,
struct state s,
struct arc **  arcarray,
int  arccount 
)
static

◆ moresubs()

static void moresubs ( struct vars v,
int  wanted 
)
static

Definition at line 555 of file regcomp.c.

557 {
558  struct subre **p;
559  size_t n;
560 
561  assert(wanted > 0 && (size_t) wanted >= v->nsubs);
562  n = (size_t) wanted * 3 / 2 + 1;
563 
564  if (v->subs == v->sub10)
565  {
566  p = (struct subre **) MALLOC(n * sizeof(struct subre *));
567  if (p != NULL)
568  memcpy(VS(p), VS(v->subs),
569  v->nsubs * sizeof(struct subre *));
570  }
571  else
572  p = (struct subre **) REALLOC(v->subs, n * sizeof(struct subre *));
573  if (p == NULL)
574  {
575  ERR(REG_ESPACE);
576  return;
577  }
578  v->subs = p;
579  for (p = &v->subs[v->nsubs]; v->nsubs < n; p++, v->nsubs++)
580  *p = NULL;
581  assert(v->nsubs == n);
582  assert((size_t) wanted < v->nsubs);
583 }
#define REALLOC
Definition: jsonapi.c:59
#define MALLOC(n)
Definition: regcustom.h:52
#define REG_ESPACE
Definition: regex.h:227
#define VS(x)
Definition: regguts.h:61
size_t nsubs
Definition: regcomp.c:294

References assert, ERR, MALLOC, vars::nsubs, REALLOC, REG_ESPACE, vars::sub10, vars::subs, and VS.

Referenced by parseqatom().

◆ moveins()

static void moveins ( struct nfa nfa,
struct state oldState,
struct state newState 
)
static

Referenced by parsebranch(), parseqatom(), and repeat().

◆ moveouts()

static void moveouts ( struct nfa nfa,
struct state oldState,
struct state newState 
)
static

Referenced by parseqatom(), and repeat().

◆ newarc()

static void newarc ( struct nfa nfa,
int  t,
color  co,
struct state from,
struct state to 
)
static

◆ newcolor()

static color newcolor ( struct colormap cm)
static

◆ newcvec()

static struct cvec* newcvec ( int  nchrs,
int  nranges 
)
static

Referenced by pg_regcomp().

◆ newfstate()

static struct state* newfstate ( struct nfa nfa,
int  flag 
)
static

◆ newhicolorcols()

static void newhicolorcols ( struct colormap cm)
static

◆ newhicolorrow()

static int newhicolorrow ( struct colormap cm,
int  oldrow 
)
static

◆ newlacon()

static int newlacon ( struct vars v,
struct state begin,
struct state end,
int  latype 
)
static

Definition at line 2391 of file regcomp.c.

2395 {
2396  int n;
2397  struct subre *newlacons;
2398  struct subre *sub;
2399 
2400  if (v->nlacons == 0)
2401  {
2402  n = 1; /* skip 0th */
2403  newlacons = (struct subre *) MALLOC(2 * sizeof(struct subre));
2404  }
2405  else
2406  {
2407  n = v->nlacons;
2408  newlacons = (struct subre *) REALLOC(v->lacons,
2409  (n + 1) * sizeof(struct subre));
2410  }
2411  if (newlacons == NULL)
2412  {
2413  ERR(REG_ESPACE);
2414  return 0;
2415  }
2416  v->lacons = newlacons;
2417  v->nlacons = n + 1;
2418  sub = &v->lacons[n];
2419  sub->begin = begin;
2420  sub->end = end;
2421  sub->latype = latype;
2422  ZAPCNFA(sub->cnfa);
2423  return n;
2424 }
#define ZAPCNFA(cnfa)
Definition: regguts.h:436
char latype
Definition: regguts.h:497

References subre::begin, subre::cnfa, subre::end, ERR, vars::lacons, subre::latype, MALLOC, vars::nlacons, REALLOC, REG_ESPACE, and ZAPCNFA.

Referenced by processlacon().

◆ newline()

static chr newline ( void  )
static

Referenced by pg_regcomp().

◆ newnfa()

static struct nfa* newnfa ( struct vars v,
struct colormap cm,
struct nfa parent 
)
static

Referenced by nfanode(), and pg_regcomp().

◆ newstate()

static struct state* newstate ( struct nfa nfa)
static

◆ newsub()

static color newsub ( struct colormap cm,
color  co 
)
static

◆ next()

static int next ( struct vars v)
static

Referenced by cleanst(), and freesubreandsiblings().

◆ nfanode()

static long nfanode ( struct vars v,
struct subre t,
int  converttosearch,
FILE *  f 
)
static

Definition at line 2351 of file regcomp.c.

2355 {
2356  struct nfa *nfa;
2357  long ret = 0;
2358 
2359  assert(t->begin != NULL);
2360 
2361 #ifdef REG_DEBUG
2362  if (f != NULL)
2363  {
2364  char idbuf[50];
2365 
2366  fprintf(f, "\n\n\n========= TREE NODE %s ==========\n",
2367  stid(t, idbuf, sizeof(idbuf)));
2368  }
2369 #endif
2370  nfa = newnfa(v, v->cm, v->nfa);
2371  NOERRZ();
2372  dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final);
2373  nfa->flags = v->nfa->flags;
2374  if (!ISERR())
2375  specialcolors(nfa);
2376  if (!ISERR())
2377  ret = optimize(nfa, f);
2378  if (converttosearch && !ISERR())
2379  makesearch(v, nfa);
2380  if (!ISERR())
2381  compact(nfa, &t->cnfa);
2382 
2383  freenfa(nfa);
2384  return ret;
2385 }
#define fprintf
Definition: port.h:242
static void compact(struct nfa *nfa, struct cnfa *cnfa)
static void specialcolors(struct nfa *nfa)
static void dupnfa(struct nfa *nfa, struct state *start, struct state *stop, struct state *from, struct state *to)
static void makesearch(struct vars *v, struct nfa *nfa)
Definition: regcomp.c:621
static struct nfa * newnfa(struct vars *v, struct colormap *cm, struct nfa *parent)
static long optimize(struct nfa *nfa, FILE *f)
#define NOERRZ()
Definition: regcomp.c:323
struct vars * v
Definition: regguts.h:369
struct state * final
Definition: regguts.h:352
struct state * init
Definition: regguts.h:351

References assert, subre::begin, vars::cm, subre::cnfa, compact(), dupnfa(), subre::end, nfa::final, nfa::flags, fprintf, freenfa(), nfa::init, ISERR, makesearch(), newnfa(), vars::nfa, NOERRZ, optimize(), specialcolors(), and nfa::v.

Referenced by nfatree(), and pg_regcomp().

◆ nfatree()

static long nfatree ( struct vars v,
struct subre t,
FILE *  f 
)
static

Definition at line 2331 of file regcomp.c.

2334 {
2335  struct subre *t2;
2336 
2337  assert(t != NULL && t->begin != NULL);
2338 
2339  for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
2340  (DISCARD) nfatree(v, t2, f);
2341 
2342  return nfanode(v, t, 0, f);
2343 }
static long nfanode(struct vars *v, struct subre *t, int converttosearch, FILE *f)
Definition: regcomp.c:2351
static long nfatree(struct vars *v, struct subre *t, FILE *f)
Definition: regcomp.c:2331
#define DISCARD
Definition: regguts.h:58

References assert, subre::begin, subre::child, DISCARD, nfanode(), and subre::sibling.

Referenced by pg_regcomp().

◆ nonword()

static void nonword ( struct vars v,
int  dir,
struct state lp,
struct state rp 
)
static

Definition at line 1458 of file regcomp.c.

1462 {
1463  int anchor = (dir == AHEAD) ? '$' : '^';
1464 
1465  assert(dir == AHEAD || dir == BEHIND);
1466  newarc(v->nfa, anchor, 1, lp, rp);
1467  newarc(v->nfa, anchor, 0, lp, rp);
1468  colorcomplement(v->nfa, v->cm, dir, v->wordchrs, lp, rp);
1469  /* (no need for special attention to \n) */
1470 }
struct state * wordchrs
Definition: regcomp.c:299

References AHEAD, assert, BEHIND, vars::cm, colorcomplement(), newarc(), vars::nfa, and vars::wordchrs.

Referenced by parseqatom().

◆ numst()

static int numst ( struct subre t,
int  start 
)
static

Definition at line 2264 of file regcomp.c.

2266 {
2267  int i;
2268  struct subre *t2;
2269 
2270  assert(t != NULL);
2271 
2272  i = start;
2273  t->id = i++;
2274  for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
2275  i = numst(t2, i);
2276  return i;
2277 }
return str start
static int numst(struct subre *t, int start)
Definition: regcomp.c:2264
int id
Definition: regguts.h:498

References assert, subre::child, i, subre::id, subre::sibling, and start.

Referenced by pg_regcomp().

◆ okcolors()

static void okcolors ( struct nfa nfa,
struct colormap cm 
)
static

◆ onechr()

static void onechr ( struct vars v,
chr  c,
struct state lp,
struct state rp 
)
static

Definition at line 1911 of file regcomp.c.

1915 {
1916  if (!(v->cflags & REG_ICASE))
1917  {
1918  color lastsubcolor = COLORLESS;
1919 
1920  subcoloronechr(v, c, lp, rp, &lastsubcolor);
1921  return;
1922  }
1923 
1924  /* rats, need general case anyway... */
1925  subcolorcvec(v, allcases(v, c), lp, rp);
1926 }
char * c
static void subcoloronechr(struct vars *v, chr ch, struct state *lp, struct state *rp, color *lastsubcolor)
static struct cvec * allcases(struct vars *v, chr c)
short color
Definition: regguts.h:155

References allcases(), vars::cflags, COLORLESS, REG_ICASE, subcolorcvec(), and subcoloronechr().

Referenced by brackpart(), and parseqatom().

◆ optimize()

static long optimize ( struct nfa nfa,
FILE *  f 
)
static

Referenced by nfanode(), and pg_regcomp().

◆ optimizebracket()

static void optimizebracket ( struct vars v,
struct state lp,
struct state rp 
)
static

Definition at line 1937 of file regcomp.c.

1940 {
1941  struct colordesc *cd;
1942  struct colordesc *end = CDEND(v->cm);
1943  struct arc *a;
1944  bool israinbow;
1945 
1946  /*
1947  * Scan lp's out-arcs and transiently mark the mentioned colors. We
1948  * expect that all of lp's out-arcs are plain, non-RAINBOW arcs to rp.
1949  * (Note: there shouldn't be any pseudocolors yet, but check anyway.)
1950  */
1951  for (a = lp->outs; a != NULL; a = a->outchain)
1952  {
1953  assert(a->type == PLAIN);
1954  assert(a->co >= 0); /* i.e. not RAINBOW */
1955  assert(a->to == rp);
1956  cd = &v->cm->cd[a->co];
1957  assert(!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO));
1958  cd->flags |= COLMARK;
1959  }
1960 
1961  /* Scan colors, clear transient marks, check for unmarked live colors */
1962  israinbow = true;
1963  for (cd = v->cm->cd; cd < end; cd++)
1964  {
1965  if (cd->flags & COLMARK)
1966  cd->flags &= ~COLMARK;
1967  else if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO))
1968  israinbow = false;
1969  }
1970 
1971  /* Can't do anything if not all colors have arcs */
1972  if (!israinbow)
1973  return;
1974 
1975  /* OK, drop existing arcs and replace with a rainbow */
1976  while ((a = lp->outs) != NULL)
1977  freearc(v->nfa, a);
1978  newarc(v->nfa, PLAIN, RAINBOW, lp, rp);
1979 }
#define PSEUDO
Definition: regguts.h:186
#define RAINBOW
Definition: regguts.h:159
#define COLMARK
Definition: regguts.h:187
#define UNUSEDCOLOR(cd)
Definition: regguts.h:190
#define CDEND(cm)
Definition: regguts.h:237
int flags
Definition: regguts.h:184
struct colordesc * cd
Definition: regguts.h:236

References a, assert, colormap::cd, CDEND, vars::cm, COLMARK, colordesc::flags, freearc(), newarc(), vars::nfa, state::outs, PLAIN, PSEUDO, RAINBOW, and UNUSEDCOLOR.

Referenced by bracket().

◆ parse()

static struct subre * parse ( struct vars v,
int  stopper,
int  type,
struct state init,
struct state final 
)
static

Definition at line 717 of file regcomp.c.

722 {
723  struct subre *branches; /* top level */
724  struct subre *lastbranch; /* latest branch */
725 
726  assert(stopper == ')' || stopper == EOS);
727 
728  branches = subre(v, '|', LONGER, init, final);
729  NOERRN();
730  lastbranch = NULL;
731  do
732  { /* a branch */
733  struct subre *branch;
734  struct state *left; /* scaffolding for branch */
735  struct state *right;
736 
737  left = newstate(v->nfa);
738  right = newstate(v->nfa);
739  NOERRN();
740  EMPTYARC(init, left);
741  EMPTYARC(right, final);
742  NOERRN();
743  branch = parsebranch(v, stopper, type, left, right, 0);
744  NOERRN();
745  if (lastbranch)
746  lastbranch->sibling = branch;
747  else
748  branches->child = branch;
749  branches->flags |= UP(branches->flags | branch->flags);
750  lastbranch = branch;
751  } while (EAT('|'));
752  assert(SEE(stopper) || SEE(EOS));
753 
754  if (!SEE(stopper))
755  {
756  assert(stopper == ')' && SEE(EOS));
757  ERR(REG_EPAREN);
758  }
759 
760  /* optimize out simple cases */
761  if (lastbranch == branches->child)
762  { /* only one branch */
763  assert(lastbranch->sibling == NULL);
764  freesrnode(v, branches);
765  branches = lastbranch;
766  }
767  else if (!MESSY(branches->flags))
768  { /* no interesting innards */
769  freesubreandsiblings(v, branches->child);
770  branches->child = NULL;
771  branches->op = '=';
772  }
773 
774  return branches;
775 }
int init
Definition: isn.c:74
static struct subre * parsebranch(struct vars *v, int stopper, int type, struct state *left, struct state *right, int partial)
Definition: regcomp.c:785
#define EMPTYARC(x, y)
Definition: regcomp.c:326
#define NOERRN()
Definition: regcomp.c:322
static struct subre * subre(struct vars *v, int op, int flags, struct state *begin, struct state *end)
Definition: regcomp.c:2095
#define EAT(t)
Definition: regcomp.c:315
#define REG_EPAREN
Definition: regex.h:223
#define UP(f)
Definition: regguts.h:492
#define LONGER
Definition: regguts.h:482
#define MESSY(f)
Definition: regguts.h:493
char op
Definition: regguts.h:480

References assert, subre::child, EAT, EMPTYARC, EOS, ERR, subre::flags, freesrnode(), freesubreandsiblings(), init, LONGER, MESSY, newstate(), vars::nfa, NOERRN, subre::op, parsebranch(), REG_EPAREN, SEE, subre::sibling, subre(), type, and UP.

Referenced by add_foreign_final_paths(), add_foreign_grouping_paths(), add_foreign_ordered_paths(), add_paths_to_grouping_rel(), build_minmax_path(), can_partial_agg(), check_sql_fn_retval(), consider_groupingsets_paths(), convert_ANY_sublink_to_join(), convert_EXISTS_sublink_to_join(), create_degenerate_grouping_paths(), create_final_distinct_paths(), create_grouping_paths(), create_limit_plan(), create_partial_distinct_paths(), create_partial_grouping_paths(), delay_execution_planner(), distribute_row_identity_vars(), expand_single_inheritance_child(), flatten_simple_union_all(), get_nullingrels(), get_number_of_groups(), get_useful_group_keys_orderings(), grouping_planner(), is_degenerate_grouping(), json_manifest_array_end(), json_manifest_array_start(), json_manifest_finalize_file(), json_manifest_finalize_system_identifier(), json_manifest_finalize_version(), json_manifest_finalize_wal_range(), json_manifest_object_end(), json_manifest_object_field_start(), json_manifest_object_start(), json_manifest_scalar(), json_parse_manifest(), json_parse_manifest_incremental_chunk(), json_parse_manifest_incremental_init(), limit_needed(), main(), make_group_input_target(), make_sort_input_target(), max_parallel_hazard(), parseqatom(), perform_pullup_replace_vars(), pg_regcomp(), pgss_planner(), plan_set_operations(), planner(), preprocess_groupclause(), preprocess_grouping_sets(), preprocess_limit(), preprocess_minmax_aggregates(), preprocess_rowmarks(), preprocess_targetlist(), pull_up_constant_function(), pull_up_simple_subquery(), pull_up_simple_values(), query_planner(), remove_useless_groupby_columns(), replace_empty_jointree(), resolve_unique_index_expr(), set_subquery_pathlist(), standard_planner(), standard_qp_callback(), subquery_planner(), transform_MERGE_to_join(), and verify_manifest_checksum().

◆ parsebranch()

static struct subre * parsebranch ( struct vars v,
int  stopper,
int  type,
struct state left,
struct state right,
int  partial 
)
static

Definition at line 785 of file regcomp.c.

791 {
792  struct state *lp; /* left end of current construct */
793  int seencontent; /* is there anything in this branch yet? */
794  struct subre *t;
795 
796  lp = left;
797  seencontent = 0;
798  t = subre(v, '=', 0, left, right); /* op '=' is tentative */
799  NOERRN();
800  while (!SEE('|') && !SEE(stopper) && !SEE(EOS))
801  {
802  if (seencontent)
803  { /* implicit concat operator */
804  lp = newstate(v->nfa);
805  NOERRN();
806  moveins(v->nfa, right, lp);
807  }
808  seencontent = 1;
809 
810  /* NB, recursion in parseqatom() may swallow rest of branch */
811  t = parseqatom(v, stopper, type, lp, right, t);
812  NOERRN();
813  }
814 
815  if (!seencontent)
816  { /* empty branch */
817  if (!partial)
818  NOTE(REG_UUNSPEC);
819  assert(lp == left);
820  EMPTYARC(left, right);
821  }
822 
823  return t;
824 }
static struct subre * parseqatom(struct vars *v, int stopper, int type, struct state *lp, struct state *rp, struct subre *top)
Definition: regcomp.c:838
static void moveins(struct nfa *nfa, struct state *oldState, struct state *newState)
#define REG_UUNSPEC
Definition: regex.h:146

References assert, EMPTYARC, EOS, moveins(), newstate(), vars::nfa, NOERRN, NOTE, parseqatom(), REG_UUNSPEC, SEE, subre(), and type.

Referenced by parse(), and parseqatom().

◆ parseqatom()

static struct subre * parseqatom ( struct vars v,
int  stopper,
int  type,
struct state lp,
struct state rp,
struct subre top 
)
static

Definition at line 838 of file regcomp.c.

844 {
845  struct state *s; /* temporaries for new states */
846  struct state *s2;
847 
848 #define ARCV(t, val) newarc(v->nfa, t, val, lp, rp)
849  int m,
850  n;
851  struct subre *atom; /* atom's subtree */
852  struct subre *t;
853  int cap; /* capturing parens? */
854  int latype; /* lookaround constraint type */
855  int subno; /* capturing-parens or backref number */
856  int atomtype;
857  int qprefer; /* quantifier short/long preference */
858  int f;
859  struct subre **atomp; /* where the pointer to atom is */
860 
861  /* initial bookkeeping */
862  atom = NULL;
863  assert(lp->nouts == 0); /* must string new code */
864  assert(rp->nins == 0); /* between lp and rp */
865  subno = 0; /* just to shut lint up */
866 
867  /* an atom or constraint... */
868  atomtype = v->nexttype;
869  switch (atomtype)
870  {
871  /* first, constraints, which end by returning */
872  case '^':
873  ARCV('^', 1);
874  if (v->cflags & REG_NLANCH)
875  ARCV(BEHIND, v->nlcolor);
876  NEXT();
877  return top;
878  break;
879  case '$':
880  ARCV('$', 1);
881  if (v->cflags & REG_NLANCH)
882  ARCV(AHEAD, v->nlcolor);
883  NEXT();
884  return top;
885  break;
886  case SBEGIN:
887  ARCV('^', 1); /* BOL */
888  ARCV('^', 0); /* or BOS */
889  NEXT();
890  return top;
891  break;
892  case SEND:
893  ARCV('$', 1); /* EOL */
894  ARCV('$', 0); /* or EOS */
895  NEXT();
896  return top;
897  break;
898  case '<':
899  wordchrs(v);
900  s = newstate(v->nfa);
901  NOERRN();
902  nonword(v, BEHIND, lp, s);
903  word(v, AHEAD, s, rp);
904  NEXT();
905  return top;
906  break;
907  case '>':
908  wordchrs(v);
909  s = newstate(v->nfa);
910  NOERRN();
911  word(v, BEHIND, lp, s);
912  nonword(v, AHEAD, s, rp);
913  NEXT();
914  return top;
915  break;
916  case WBDRY:
917  wordchrs(v);
918  s = newstate(v->nfa);
919  NOERRN();
920  nonword(v, BEHIND, lp, s);
921  word(v, AHEAD, s, rp);
922  s = newstate(v->nfa);
923  NOERRN();
924  word(v, BEHIND, lp, s);
925  nonword(v, AHEAD, s, rp);
926  NEXT();
927  return top;
928  break;
929  case NWBDRY:
930  wordchrs(v);
931  s = newstate(v->nfa);
932  NOERRN();
933  word(v, BEHIND, lp, s);
934  word(v, AHEAD, s, rp);
935  s = newstate(v->nfa);
936  NOERRN();
937  nonword(v, BEHIND, lp, s);
938  nonword(v, AHEAD, s, rp);
939  NEXT();
940  return top;
941  break;
942  case LACON: /* lookaround constraint */
943  latype = v->nextvalue;
944  NEXT();
945  s = newstate(v->nfa);
946  s2 = newstate(v->nfa);
947  NOERRN();
948  t = parse(v, ')', LACON, s, s2);
949  freesubre(v, t); /* internal structure irrelevant */
950  NOERRN();
951  assert(SEE(')'));
952  NEXT();
953  processlacon(v, s, s2, latype, lp, rp);
954  return top;
955  break;
956  /* then errors, to get them out of the way */
957  case '*':
958  case '+':
959  case '?':
960  case '{':
961  ERR(REG_BADRPT);
962  return top;
963  break;
964  default:
965  ERR(REG_ASSERT);
966  return top;
967  break;
968  /* then plain characters, and minor variants on that theme */
969  case ')': /* unbalanced paren */
970  if ((v->cflags & REG_ADVANCED) != REG_EXTENDED)
971  {
972  ERR(REG_EPAREN);
973  return top;
974  }
975  /* legal in EREs due to specification botch */
976  NOTE(REG_UPBOTCH);
977  /* fall through into case PLAIN */
978  /* FALLTHROUGH */
979  case PLAIN:
980  onechr(v, v->nextvalue, lp, rp);
981  okcolors(v->nfa, v->cm);
982  NOERRN();
983  NEXT();
984  break;
985  case '[':
986  if (v->nextvalue == 1)
987  bracket(v, lp, rp);
988  else
989  cbracket(v, lp, rp);
990  assert(SEE(']') || ISERR());
991  NEXT();
992  break;
993  case CCLASSS:
994  charclass(v, (enum char_classes) v->nextvalue, lp, rp);
995  okcolors(v->nfa, v->cm);
996  NEXT();
997  break;
998  case CCLASSC:
999  charclasscomplement(v, (enum char_classes) v->nextvalue, lp, rp);
1000  /* charclasscomplement() did okcolors() internally */
1001  NEXT();
1002  break;
1003  case '.':
1004  rainbow(v->nfa, v->cm, PLAIN,
1005  (v->cflags & REG_NLSTOP) ? v->nlcolor : COLORLESS,
1006  lp, rp);
1007  NEXT();
1008  break;
1009  /* and finally the ugly stuff */
1010  case '(': /* value flags as capturing or non */
1011  cap = (type == LACON) ? 0 : v->nextvalue;
1012  if (cap)
1013  {
1014  v->nsubexp++;
1015  subno = v->nsubexp;
1016  if ((size_t) subno >= v->nsubs)
1017  moresubs(v, subno);
1018  }
1019  else
1020  atomtype = PLAIN; /* something that's not '(' */
1021  NEXT();
1022 
1023  /*
1024  * Make separate endpoint states to keep this sub-NFA distinct
1025  * from what surrounds it. We need to be sure that when we
1026  * duplicate the sub-NFA for a backref, we get the right
1027  * states/arcs and no others. In particular, letting a backref
1028  * duplicate the sub-NFA from lp to rp would be quite wrong,
1029  * because we may add quantification superstructure around this
1030  * atom below. (Perhaps we could skip the extra states for
1031  * non-capturing parens, but it seems not worth the trouble.)
1032  */
1033  s = newstate(v->nfa);
1034  s2 = newstate(v->nfa);
1035  NOERRN();
1036  /* We may not need these arcs, but keep things connected for now */
1037  EMPTYARC(lp, s);
1038  EMPTYARC(s2, rp);
1039  NOERRN();
1040  atom = parse(v, ')', type, s, s2);
1041  assert(SEE(')') || ISERR());
1042  NEXT();
1043  NOERRN();
1044  if (cap)
1045  {
1046  if (atom->capno == 0)
1047  {
1048  /* normal case: just mark the atom as capturing */
1049  atom->flags |= CAP;
1050  atom->capno = subno;
1051  }
1052  else
1053  {
1054  /* generate no-op wrapper node to handle "((x))" */
1055  t = subre(v, '(', atom->flags | CAP, s, s2);
1056  NOERRN();
1057  t->capno = subno;
1058  t->child = atom;
1059  atom = t;
1060  }
1061  assert(v->subs[subno] == NULL);
1062  v->subs[subno] = atom;
1063  }
1064  /* postpone everything else pending possible {0} */
1065  break;
1066  case BACKREF: /* the Feature From The Black Lagoon */
1068  subno = v->nextvalue;
1069  assert(subno > 0);
1070  INSIST(subno < v->nsubs, REG_ESUBREG);
1071  NOERRN();
1072  INSIST(v->subs[subno] != NULL, REG_ESUBREG);
1073  NOERRN();
1074  atom = subre(v, 'b', BACKR, lp, rp);
1075  NOERRN();
1076  atom->backno = subno;
1077  v->subs[subno]->flags |= BRUSE;
1078  EMPTYARC(lp, rp); /* temporarily, so there's something */
1079  NEXT();
1080  break;
1081  }
1082 
1083  /* ...and an atom may be followed by a quantifier */
1084  switch (v->nexttype)
1085  {
1086  case '*':
1087  m = 0;
1088  n = DUPINF;
1089  qprefer = (v->nextvalue) ? LONGER : SHORTER;
1090  NEXT();
1091  break;
1092  case '+':
1093  m = 1;
1094  n = DUPINF;
1095  qprefer = (v->nextvalue) ? LONGER : SHORTER;
1096  NEXT();
1097  break;
1098  case '?':
1099  m = 0;
1100  n = 1;
1101  qprefer = (v->nextvalue) ? LONGER : SHORTER;
1102  NEXT();
1103  break;
1104  case '{':
1105  NEXT();
1106  m = scannum(v);
1107  if (EAT(','))
1108  {
1109  if (SEE(DIGIT))
1110  n = scannum(v);
1111  else
1112  n = DUPINF;
1113  if (m > n)
1114  {
1115  ERR(REG_BADBR);
1116  return top;
1117  }
1118  /* {m,n} exercises preference, even if it's {m,m} */
1119  qprefer = (v->nextvalue) ? LONGER : SHORTER;
1120  }
1121  else
1122  {
1123  n = m;
1124  /* {m} passes operand's preference through */
1125  qprefer = 0;
1126  }
1127  if (!SEE('}'))
1128  { /* catches errors too */
1129  ERR(REG_BADBR);
1130  return top;
1131  }
1132  NEXT();
1133  break;
1134  default: /* no quantifier */
1135  m = n = 1;
1136  qprefer = 0;
1137  break;
1138  }
1139 
1140  /* annoying special case: {0} or {0,0} cancels everything */
1141  if (m == 0 && n == 0)
1142  {
1143  /*
1144  * If we had capturing subexpression(s) within the atom, we don't want
1145  * to destroy them, because it's legal (if useless) to back-ref them
1146  * later. Hence, just unlink the atom from lp/rp and then ignore it.
1147  */
1148  if (atom != NULL && (atom->flags & CAP))
1149  {
1150  delsub(v->nfa, lp, atom->begin);
1151  delsub(v->nfa, atom->end, rp);
1152  }
1153  else
1154  {
1155  /* Otherwise, we can clean up any subre infrastructure we made */
1156  if (atom != NULL)
1157  freesubre(v, atom);
1158  delsub(v->nfa, lp, rp);
1159  }
1160  EMPTYARC(lp, rp);
1161  return top;
1162  }
1163 
1164  /* if not a messy case, avoid hard part */
1165  assert(!MESSY(top->flags));
1166  f = top->flags | qprefer | ((atom != NULL) ? atom->flags : 0);
1167  if (atomtype != '(' && atomtype != BACKREF && !MESSY(UP(f)))
1168  {
1169  if (!(m == 1 && n == 1))
1170  repeat(v, lp, rp, m, n);
1171  if (atom != NULL)
1172  freesubre(v, atom);
1173  top->flags = f;
1174  return top;
1175  }
1176 
1177  /*
1178  * hard part: something messy
1179  *
1180  * That is, capturing parens, back reference, short/long clash, or an atom
1181  * with substructure containing one of those.
1182  */
1183 
1184  /* now we'll need a subre for the contents even if they're boring */
1185  if (atom == NULL)
1186  {
1187  atom = subre(v, '=', 0, lp, rp);
1188  NOERRN();
1189  }
1190 
1191  /*
1192  * For what follows, we need the atom to have its own begin/end states
1193  * that are distinct from lp/rp, so that we can wrap iteration structure
1194  * around it. The parenthesized-atom case above already made suitable
1195  * states (and we don't want to modify a capturing subre, since it's
1196  * already recorded in v->subs[]). Otherwise, we need more states.
1197  */
1198  if (atom->begin == lp || atom->end == rp)
1199  {
1200  s = newstate(v->nfa);
1201  s2 = newstate(v->nfa);
1202  NOERRN();
1203  moveouts(v->nfa, lp, s);
1204  moveins(v->nfa, rp, s2);
1205  atom->begin = s;
1206  atom->end = s2;
1207  }
1208  else
1209  {
1210  /* The atom's OK, but we must temporarily disconnect it from lp/rp */
1211  /* (this removes the EMPTY arcs we made above) */
1212  delsub(v->nfa, lp, atom->begin);
1213  delsub(v->nfa, atom->end, rp);
1214  }
1215 
1216  /*----------
1217  * Prepare a general-purpose state skeleton.
1218  *
1219  * In the no-backrefs case, we want this:
1220  *
1221  * [lp] ---> [s] ---prefix---> ---atom---> ---rest---> [rp]
1222  *
1223  * where prefix is some repetitions of atom, and "rest" is the remainder
1224  * of the branch. In the general case we need:
1225  *
1226  * [lp] ---> [s] ---iterator---> [s2] ---rest---> [rp]
1227  *
1228  * where the iterator wraps around the atom.
1229  *
1230  * We make the s state here for both cases; s2 is made below if needed
1231  *----------
1232  */
1233  s = newstate(v->nfa); /* set up starting state */
1234  NOERRN();
1235  EMPTYARC(lp, s);
1236  NOERRN();
1237 
1238  /* break remaining subRE into x{...} and what follows */
1239  t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp);
1240  NOERRN();
1241  t->child = atom;
1242  atomp = &t->child;
1243 
1244  /*
1245  * Here we should recurse to fill t->child->sibling ... but we must
1246  * postpone that to the end. One reason is that t->child may be replaced
1247  * below, and we don't want to worry about its sibling link.
1248  */
1249 
1250  /*
1251  * Convert top node to a concatenation of the prefix (top->child, covering
1252  * whatever we parsed previously) and remaining (t). Note that the prefix
1253  * could be empty, in which case this concatenation node is unnecessary.
1254  * To keep things simple, we operate in a general way for now, and get rid
1255  * of unnecessary subres below.
1256  */
1257  assert(top->op == '=' && top->child == NULL);
1258  top->child = subre(v, '=', top->flags, top->begin, lp);
1259  NOERRN();
1260  top->op = '.';
1261  top->child->sibling = t;
1262  /* top->flags will get updated later */
1263 
1264  /* if it's a backref, now is the time to replicate the subNFA */
1265  if (atomtype == BACKREF)
1266  {
1267  assert(atom->begin->nouts == 1); /* just the EMPTY */
1268  delsub(v->nfa, atom->begin, atom->end);
1269  assert(v->subs[subno] != NULL);
1270 
1271  /*
1272  * And here's why the recursion got postponed: it must wait until the
1273  * skeleton is filled in, because it may hit a backref that wants to
1274  * copy the filled-in skeleton.
1275  */
1276  dupnfa(v->nfa, v->subs[subno]->begin, v->subs[subno]->end,
1277  atom->begin, atom->end);
1278  NOERRN();
1279 
1280  /* The backref node's NFA should not enforce any constraints */
1281  removeconstraints(v->nfa, atom->begin, atom->end);
1282  NOERRN();
1283  }
1284 
1285  /*
1286  * It's quantifier time. If the atom is just a backref, we'll let it deal
1287  * with quantifiers internally.
1288  */
1289  if (atomtype == BACKREF)
1290  {
1291  /* special case: backrefs have internal quantifiers */
1292  EMPTYARC(s, atom->begin); /* empty prefix */
1293  /* just stuff everything into atom */
1294  repeat(v, atom->begin, atom->end, m, n);
1295  atom->min = (short) m;
1296  atom->max = (short) n;
1297  atom->flags |= COMBINE(qprefer, atom->flags);
1298  /* rest of branch can be strung starting from atom->end */
1299  s2 = atom->end;
1300  }
1301  else if (m == 1 && n == 1 &&
1302  (qprefer == 0 ||
1303  (atom->flags & (LONGER | SHORTER | MIXED)) == 0 ||
1304  qprefer == (atom->flags & (LONGER | SHORTER | MIXED))))
1305  {
1306  /* no/vacuous quantifier: done */
1307  EMPTYARC(s, atom->begin); /* empty prefix */
1308  /* rest of branch can be strung starting from atom->end */
1309  s2 = atom->end;
1310  }
1311  else if (!(atom->flags & (CAP | BACKR)))
1312  {
1313  /*
1314  * If there's no captures nor backrefs in the atom being repeated, we
1315  * don't really care where the submatches of the iteration are, so we
1316  * don't need an iteration node. Make a plain DFA node instead.
1317  */
1318  EMPTYARC(s, atom->begin); /* empty prefix */
1319  repeat(v, atom->begin, atom->end, m, n);
1320  f = COMBINE(qprefer, atom->flags);
1321  t = subre(v, '=', f, atom->begin, atom->end);
1322  NOERRN();
1323  freesubre(v, atom);
1324  *atomp = t;
1325  /* rest of branch can be strung starting from t->end */
1326  s2 = t->end;
1327  }
1328  else if (m > 0 && !(atom->flags & BACKR))
1329  {
1330  /*
1331  * If there's no backrefs involved, we can turn x{m,n} into
1332  * x{m-1,n-1}x, with capturing parens in only the second x. This is
1333  * valid because we only care about capturing matches from the final
1334  * iteration of the quantifier. It's a win because we can implement
1335  * the backref-free left side as a plain DFA node, since we don't
1336  * really care where its submatches are.
1337  */
1338  dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin);
1339  assert(m >= 1 && m != DUPINF && n >= 1);
1340  repeat(v, s, atom->begin, m - 1, (n == DUPINF) ? n : n - 1);
1341  f = COMBINE(qprefer, atom->flags);
1342  t = subre(v, '.', f, s, atom->end); /* prefix and atom */
1343  NOERRN();
1344  t->child = subre(v, '=', PREF(f), s, atom->begin);
1345  NOERRN();
1346  t->child->sibling = atom;
1347  *atomp = t;
1348  /* rest of branch can be strung starting from atom->end */
1349  s2 = atom->end;
1350  }
1351  else
1352  {
1353  /* general case: need an iteration node */
1354  s2 = newstate(v->nfa);
1355  NOERRN();
1356  moveouts(v->nfa, atom->end, s2);
1357  NOERRN();
1358  dupnfa(v->nfa, atom->begin, atom->end, s, s2);
1359  repeat(v, s, s2, m, n);
1360  f = COMBINE(qprefer, atom->flags);
1361  t = subre(v, '*', f, s, s2);
1362  NOERRN();
1363  t->min = (short) m;
1364  t->max = (short) n;
1365  t->child = atom;
1366  *atomp = t;
1367  /* rest of branch is to be strung from iteration's end state */
1368  }
1369 
1370  /* and finally, look after that postponed recursion */
1371  t = top->child->sibling;
1372  if (!(SEE('|') || SEE(stopper) || SEE(EOS)))
1373  {
1374  /* parse all the rest of the branch, and insert in t->child->sibling */
1375  t->child->sibling = parsebranch(v, stopper, type, s2, rp, 1);
1376  NOERRN();
1377  assert(SEE('|') || SEE(stopper) || SEE(EOS));
1378 
1379  /* here's the promised update of the flags */
1380  t->flags |= COMBINE(t->flags, t->child->sibling->flags);
1381  top->flags |= COMBINE(top->flags, t->flags);
1382 
1383  /* neither t nor top could be directly marked for capture as yet */
1384  assert(t->capno == 0);
1385  assert(top->capno == 0);
1386 
1387  /*
1388  * At this point both top and t are concatenation (op == '.') subres,
1389  * and we have top->child = prefix of branch, top->child->sibling = t,
1390  * t->child = messy atom (with quantification superstructure if
1391  * needed), t->child->sibling = rest of branch.
1392  *
1393  * If the messy atom was the first thing in the branch, then
1394  * top->child is vacuous and we can get rid of one level of
1395  * concatenation.
1396  */
1397  assert(top->child->op == '=');
1398  if (top->child->begin == top->child->end)
1399  {
1400  assert(!MESSY(top->child->flags));
1401  freesubre(v, top->child);
1402  top->child = t->child;
1403  freesrnode(v, t);
1404  }
1405 
1406  /*
1407  * Otherwise, it's possible that t->child is not messy in itself, but
1408  * we considered it messy because its greediness conflicts with what
1409  * preceded it. Then it could be that the combination of t->child and
1410  * the rest of the branch is also not messy, in which case we can get
1411  * rid of the child concatenation by merging t->child and the rest of
1412  * the branch into one plain DFA node.
1413  */
1414  else if (t->child->op == '=' &&
1415  t->child->sibling->op == '=' &&
1416  !MESSY(UP(t->child->flags | t->child->sibling->flags)))
1417  {
1418  t->op = '=';
1419  t->flags = COMBINE(t->child->flags, t->child->sibling->flags);
1420  freesubreandsiblings(v, t->child);
1421  t->child = NULL;
1422  }
1423  }
1424  else
1425  {
1426  /*
1427  * There's nothing left in the branch, so we don't need the second
1428  * concatenation node 't'. Just link s2 straight to rp.
1429  */
1430  EMPTYARC(s2, rp);
1431  top->child->sibling = t->child;
1432  top->flags |= COMBINE(top->flags, top->child->sibling->flags);
1433  freesrnode(v, t);
1434 
1435  /*
1436  * Again, it could be that top->child is vacuous (if the messy atom
1437  * was in fact the only thing in the branch). In that case we need no
1438  * concatenation at all; just replace top with top->child->sibling.
1439  */
1440  assert(top->child->op == '=');
1441  if (top->child->begin == top->child->end)
1442  {
1443  assert(!MESSY(top->child->flags));
1444  t = top->child->sibling;
1445  top->child->sibling = NULL;
1446  freesubre(v, top);
1447  top = t;
1448  }
1449  }
1450 
1451  return top;
1452 }
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:76
#define NWBDRY
Definition: regcomp.c:345
static void wordchrs(struct vars *v)
Definition: regcomp.c:1993
#define SBEGIN
Definition: regcomp.c:347
static void repeat(struct vars *v, struct state *lp, struct state *rp, int m, int n)
Definition: regcomp.c:1586
static void moresubs(struct vars *v, int wanted)
Definition: regcomp.c:555
#define WBDRY
Definition: regcomp.c:344
static void moveouts(struct nfa *nfa, struct state *oldState, struct state *newState)
#define DIGIT
Definition: regcomp.c:332
#define ARCV(t, val)
static int scannum(struct vars *v)
Definition: regcomp.c:1555
static void cbracket(struct vars *v, struct state *lp, struct state *rp)
Definition: regcomp.c:1729
#define BACKREF
Definition: regcomp.c:333
#define LACON
Definition: regcomp.c:341
static void nonword(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1458
static void delsub(struct nfa *nfa, struct state *lp, struct state *rp)
#define SEND
Definition: regcomp.c:348
static void removeconstraints(struct nfa *nfa, struct state *start, struct state *stop)
static struct subre * parse(struct vars *v, int stopper, int type, struct state *init, struct state *final)
Definition: regcomp.c:717
static void processlacon(struct vars *v, struct state *begin, struct state *end, int latype, struct state *lp, struct state *rp)
Definition: regcomp.c:2029
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1476
#define REG_UPBOTCH
Definition: regex.h:143
#define REG_BADRPT
Definition: regex.h:228
#define REG_ADVANCED
Definition: regex.h:181
#define REG_NLANCH
Definition: regex.h:188
#define REG_EXTENDED
Definition: regex.h:179
#define REG_ESUBREG
Definition: regex.h:221
#define REG_BADBR
Definition: regex.h:225
#define BACKR
Definition: regguts.h:486
#define CAP
Definition: regguts.h:485
#define COMBINE(f1, f2)
Definition: regguts.h:496
#define PREF(f)
Definition: regguts.h:494
#define BRUSE
Definition: regguts.h:487
#define MIXED
Definition: regguts.h:484
#define SHORTER
Definition: regguts.h:483
int backno
Definition: regguts.h:500
short min
Definition: regguts.h:501
short max
Definition: regguts.h:502
int capno
Definition: regguts.h:499
int nsubexp
Definition: regcomp.c:292

References AHEAD, ARCV, assert, subre::backno, BACKR, BACKREF, subre::begin, BEHIND, bracket(), BRUSE, CAP, subre::capno, cbracket(), CCLASSC, CCLASSS, vars::cflags, charclass(), charclasscomplement(), subre::child, vars::cm, COLORLESS, COMBINE, delsub(), DIGIT, DUPINF, dupnfa(), EAT, EMPTYARC, subre::end, EOS, ERR, subre::flags, freesrnode(), freesubre(), freesubreandsiblings(), if(), INSIST, ISERR, LACON, subre::latype, LONGER, subre::max, MESSY, subre::min, MIXED, moresubs(), moveins(), moveouts(), newstate(), NEXT, vars::nexttype, vars::nextvalue, vars::nfa, state::nins, vars::nlcolor, NOERRN, nonword(), NOTE, state::nouts, vars::nsubexp, vars::nsubs, NWBDRY, okcolors(), onechr(), subre::op, parse(), parsebranch(), PLAIN, PREF, processlacon(), rainbow(), REG_ADVANCED, REG_ASSERT, REG_BADBR, REG_BADRPT, REG_EPAREN, REG_ESUBREG, REG_EXTENDED, REG_NLANCH, REG_NLSTOP, REG_UPBOTCH, removeconstraints(), repeat(), s2, SBEGIN, scannum(), SEE, SEND, SHORTER, subre::sibling, subre(), vars::subs, type, UP, WBDRY, word(), and wordchrs().

Referenced by parsebranch().

◆ pg_regcomp()

int pg_regcomp ( regex_t re,
const chr string,
size_t  len,
int  flags,
Oid  collation 
)

Definition at line 372 of file regcomp.c.

377 {
378  struct vars var;
379  struct vars *v = &var;
380  struct guts *g;
381  int i;
382  size_t j;
383 
384 #ifdef REG_DEBUG
385  FILE *debug = (flags & REG_PROGRESS) ? stdout : (FILE *) NULL;
386 #else
387  FILE *debug = (FILE *) NULL;
388 #endif
389 
390 #define CNOERR() { if (ISERR()) return freev(v, v->err); }
391 
392  /* sanity checks */
393 
394  if (re == NULL || string == NULL)
395  return REG_INVARG;
396  if ((flags & REG_QUOTE) &&
397  (flags & (REG_ADVANCED | REG_EXPANDED | REG_NEWLINE)))
398  return REG_INVARG;
399  if (!(flags & REG_EXTENDED) && (flags & REG_ADVF))
400  return REG_INVARG;
401 
402  /* Initialize locale-dependent support */
403  pg_set_regex_collation(collation);
404 
405  /* initial setup (after which freev() is callable) */
406  v->re = re;
407  v->now = string;
408  v->stop = v->now + len;
409  v->err = 0;
410  v->cflags = flags;
411  v->nsubexp = 0;
412  v->subs = v->sub10;
413  v->nsubs = 10;
414  for (j = 0; j < v->nsubs; j++)
415  v->subs[j] = NULL;
416  v->nfa = NULL;
417  v->cm = NULL;
418  v->nlcolor = COLORLESS;
419  v->wordchrs = NULL;
420  v->tree = NULL;
421  v->treechain = NULL;
422  v->treefree = NULL;
423  v->cv = NULL;
424  v->cv2 = NULL;
425  v->lacons = NULL;
426  v->nlacons = 0;
427  v->spaceused = 0;
428  re->re_magic = REMAGIC;
429  re->re_info = 0; /* bits get set during parse */
430  re->re_csize = sizeof(chr);
431  re->re_collation = collation;
432  re->re_guts = NULL;
433  re->re_fns = VS(&functions);
434 
435  /* more complex setup, malloced things */
436  re->re_guts = VS(MALLOC(sizeof(struct guts)));
437  if (re->re_guts == NULL)
438  return freev(v, REG_ESPACE);
439  g = (struct guts *) re->re_guts;
440  g->tree = NULL;
441  initcm(v, &g->cmap);
442  v->cm = &g->cmap;
443  g->lacons = NULL;
444  g->nlacons = 0;
445  ZAPCNFA(g->search);
446  v->nfa = newnfa(v, v->cm, (struct nfa *) NULL);
447  CNOERR();
448  /* set up a reasonably-sized transient cvec for getcvec usage */
449  v->cv = newcvec(100, 20);
450  if (v->cv == NULL)
451  return freev(v, REG_ESPACE);
452 
453  /* parsing */
454  lexstart(v); /* also handles prefixes */
455  if ((v->cflags & REG_NLSTOP) || (v->cflags & REG_NLANCH))
456  {
457  /* assign newline a unique color */
458  v->nlcolor = subcolor(v->cm, newline());
459  okcolors(v->nfa, v->cm);
460  }
461  CNOERR();
462  v->tree = parse(v, EOS, PLAIN, v->nfa->init, v->nfa->final);
463  assert(SEE(EOS)); /* even if error; ISERR() => SEE(EOS) */
464  CNOERR();
465  assert(v->tree != NULL);
466 
467  /* finish setup of nfa and its subre tree */
468  specialcolors(v->nfa);
469  CNOERR();
470 #ifdef REG_DEBUG
471  if (debug != NULL)
472  {
473  fprintf(debug, "\n\n\n========= RAW ==========\n");
474  dumpnfa(v->nfa, debug);
475  dumpst(v->tree, debug, 1);
476  }
477 #endif
478  if (v->cflags & REG_NOSUB)
479  removecaptures(v, v->tree);
480  v->ntree = numst(v->tree, 1);
481  markst(v->tree);
482  cleanst(v);
483 #ifdef REG_DEBUG
484  if (debug != NULL)
485  {
486  fprintf(debug, "\n\n\n========= TREE FIXED ==========\n");
487  dumpst(v->tree, debug, 1);
488  }
489 #endif
490 
491  /* build compacted NFAs for tree and lacons */
492  re->re_info |= nfatree(v, v->tree, debug);
493  CNOERR();
494  assert(v->nlacons == 0 || v->lacons != NULL);
495  for (i = 1; i < v->nlacons; i++)
496  {
497  struct subre *lasub = &v->lacons[i];
498 
499 #ifdef REG_DEBUG
500  if (debug != NULL)
501  fprintf(debug, "\n\n\n========= LA%d ==========\n", i);
502 #endif
503 
504  /* Prepend .* to pattern if it's a lookbehind LACON */
505  nfanode(v, lasub, !LATYPE_IS_AHEAD(lasub->latype), debug);
506  }
507  CNOERR();
508  if (v->tree->flags & SHORTER)
510 
511  /* build compacted NFAs for tree, lacons, fast search */
512 #ifdef REG_DEBUG
513  if (debug != NULL)
514  fprintf(debug, "\n\n\n========= SEARCH ==========\n");
515 #endif
516  /* can sacrifice main NFA now, so use it as work area */
517  (DISCARD) optimize(v->nfa, debug);
518  CNOERR();
519  makesearch(v, v->nfa);
520  CNOERR();
521  compact(v->nfa, &g->search);
522  CNOERR();
523 
524  /* looks okay, package it up */
525  re->re_nsub = v->nsubexp;
526  v->re = NULL; /* freev no longer frees re */
527  g->magic = GUTSMAGIC;
528  g->cflags = v->cflags;
529  g->info = re->re_info;
530  g->nsub = re->re_nsub;
531  g->tree = v->tree;
532  v->tree = NULL;
533  g->ntree = v->ntree;
534  g->compare = (v->cflags & REG_ICASE) ? casecmp : cmp;
535  g->lacons = v->lacons;
536  v->lacons = NULL;
537  g->nlacons = v->nlacons;
538 
539 #ifdef REG_DEBUG
540  if (flags & REG_DUMP)
541  {
542  dump(re, stdout);
543  fflush(stdout);
544  }
545 #endif
546 
547  assert(v->err == 0);
548  return freev(v, 0);
549 }
static bool debug
Definition: initdb.c:161
int j
Definition: isn.c:73
static void const char fflush(stdout)
const void size_t len
char string[11]
Definition: preproc-type.c:52
void pg_set_regex_collation(Oid collation)
static int casecmp(const chr *x, const chr *y, size_t len)
static const struct fns functions
Definition: regcomp.c:358
#define CNOERR()
static void initcm(struct vars *v, struct colormap *cm)
static chr newline(void)
static int cmp(const chr *x, const chr *y, size_t len)
static void removecaptures(struct vars *v, struct subre *t)
Definition: regcomp.c:2218
static void lexstart(struct vars *v)
static color subcolor(struct colormap *cm, chr c)
static void dumpnfa(struct nfa *nfa, FILE *f)
static int freev(struct vars *v, int err)
Definition: regcomp.c:592
static struct cvec * newcvec(int nchrs, int nranges)
#define REG_DUMP
Definition: regex.h:193
#define REG_PROGRESS
Definition: regex.h:195
#define REG_EXPANDED
Definition: regex.h:186
#define REG_INVARG
Definition: regex.h:230
#define REG_ADVF
Definition: regex.h:180
#define REG_NEWLINE
Definition: regex.h:189
#define REG_NOSUB
Definition: regex.h:185
#define REG_USHORTEST
Definition: regex.h:151
#define REG_QUOTE
Definition: regex.h:182
#define REMAGIC
Definition: regguts.h:101
#define GUTSMAGIC
Definition: regguts.h:533
#define LATYPE_IS_AHEAD(la)
Definition: regguts.h:109
Definition: regguts.h:531
struct subre * tree
Definition: regguts.h:537
struct subre * lacons
Definition: regguts.h:542
int magic
Definition: regguts.h:532
long info
Definition: regguts.h:535
struct cnfa search
Definition: regguts.h:538
int ntree
Definition: regguts.h:539
int cflags
Definition: regguts.h:534
size_t nsub
Definition: regguts.h:536
int nlacons
Definition: regguts.h:543
struct colormap cmap
Definition: regguts.h:540
Definition: regcomp.c:282
const chr * stop
Definition: regcomp.c:285
size_t spaceused
Definition: regcomp.c:309
int ntree
Definition: regcomp.c:303

References assert, casecmp(), vars::cflags, guts::cflags, cleanst(), vars::cm, guts::cmap, cmp(), CNOERR, COLORLESS, compact(), vars::cv, vars::cv2, debug, DISCARD, dumpnfa(), EOS, vars::err, fflush(), nfa::final, subre::flags, fprintf, freev(), functions, GUTSMAGIC, i, guts::info, nfa::init, initcm(), j, vars::lacons, guts::lacons, subre::latype, LATYPE_IS_AHEAD, len, lexstart(), guts::magic, makesearch(), MALLOC, markst(), newcvec(), newline(), newnfa(), vars::nfa, nfanode(), nfatree(), vars::nlacons, guts::nlacons, vars::nlcolor, NOTE, vars::now, guts::nsub, vars::nsubexp, vars::nsubs, vars::ntree, guts::ntree, numst(), okcolors(), optimize(), parse(), pg_set_regex_collation(), PLAIN, vars::re, REG_ADVANCED, REG_ADVF, REG_DUMP, REG_ESPACE, REG_EXPANDED, REG_EXTENDED, REG_ICASE, REG_INVARG, REG_NEWLINE, REG_NLANCH, REG_NLSTOP, REG_NOSUB, REG_PROGRESS, REG_QUOTE, REG_USHORTEST, REMAGIC, removecaptures(), guts::search, SEE, SHORTER, vars::spaceused, specialcolors(), generate_unaccent_rules::stdout, vars::stop, vars::sub10, subcolor(), vars::subs, vars::tree, guts::tree, vars::treechain, vars::treefree, VS, vars::wordchrs, and ZAPCNFA.

Referenced by NIAddAffix(), RE_compile(), RE_compile_and_cache(), regcomp_auth_token(), and test_re_compile().

◆ pg_wc_isalnum()

static int pg_wc_isalnum ( pg_wchar  c)
static

◆ pg_wc_isalpha()

static int pg_wc_isalpha ( pg_wchar  c)
static

◆ pg_wc_isdigit()

static int pg_wc_isdigit ( pg_wchar  c)
static

◆ pg_wc_isgraph()

static int pg_wc_isgraph ( pg_wchar  c)
static

◆ pg_wc_islower()

static int pg_wc_islower ( pg_wchar  c)
static

◆ pg_wc_isprint()

static int pg_wc_isprint ( pg_wchar  c)
static

◆ pg_wc_ispunct()

static int pg_wc_ispunct ( pg_wchar  c)
static

◆ pg_wc_isspace()

static int pg_wc_isspace ( pg_wchar  c)
static

◆ pg_wc_isupper()

static int pg_wc_isupper ( pg_wchar  c)
static

◆ pg_wc_isword()

static int pg_wc_isword ( pg_wchar  c)
static

◆ pg_wc_tolower()

static pg_wchar pg_wc_tolower ( pg_wchar  c)
static

◆ pg_wc_toupper()

static pg_wchar pg_wc_toupper ( pg_wchar  c)
static

◆ prefixes()

static void prefixes ( struct vars v)
static

◆ processlacon()

static void processlacon ( struct vars v,
struct state begin,
struct state end,
int  latype,
struct state lp,
struct state rp 
)
static

Definition at line 2029 of file regcomp.c.

2035 {
2036  struct state *s1;
2037  int n;
2038 
2039  /*
2040  * Check for lookaround RE consisting of a single plain color arc (or set
2041  * of arcs); this would typically be a simple chr or a bracket expression.
2042  */
2043  s1 = single_color_transition(begin, end);
2044  switch (latype)
2045  {
2046  case LATYPE_AHEAD_POS:
2047  /* If lookahead RE is just colorset C, convert to AHEAD(C) */
2048  if (s1 != NULL)
2049  {
2050  cloneouts(v->nfa, s1, lp, rp, AHEAD);
2051  return;
2052  }
2053  break;
2054  case LATYPE_AHEAD_NEG:
2055  /* If lookahead RE is just colorset C, convert to AHEAD(^C)|$ */
2056  if (s1 != NULL)
2057  {
2058  colorcomplement(v->nfa, v->cm, AHEAD, s1, lp, rp);
2059  newarc(v->nfa, '$', 1, lp, rp);
2060  newarc(v->nfa, '$', 0, lp, rp);
2061  return;
2062  }
2063  break;
2064  case LATYPE_BEHIND_POS:
2065  /* If lookbehind RE is just colorset C, convert to BEHIND(C) */
2066  if (s1 != NULL)
2067  {
2068  cloneouts(v->nfa, s1, lp, rp, BEHIND);
2069  return;
2070  }
2071  break;
2072  case LATYPE_BEHIND_NEG:
2073  /* If lookbehind RE is just colorset C, convert to BEHIND(^C)|^ */
2074  if (s1 != NULL)
2075  {
2076  colorcomplement(v->nfa, v->cm, BEHIND, s1, lp, rp);
2077  newarc(v->nfa, '^', 1, lp, rp);
2078  newarc(v->nfa, '^', 0, lp, rp);
2079  return;
2080  }
2081  break;
2082  default:
2083  assert(NOTREACHED);
2084  }
2085 
2086  /* General case: we need a LACON subre and arc */
2087  n = newlacon(v, begin, end, latype);
2088  newarc(v->nfa, LACON, n, lp, rp);
2089 }
char * s1
static struct state * single_color_transition(struct state *s1, struct state *s2)
static void cloneouts(struct nfa *nfa, struct state *old, struct state *from, struct state *to, int type)
static int newlacon(struct vars *v, struct state *begin, struct state *end, int latype)
Definition: regcomp.c:2391
#define LATYPE_AHEAD_NEG
Definition: regguts.h:105
#define LATYPE_BEHIND_POS
Definition: regguts.h:106
#define NOTREACHED
Definition: regguts.h:96
#define LATYPE_BEHIND_NEG
Definition: regguts.h:107
#define LATYPE_AHEAD_POS
Definition: regguts.h:104

References AHEAD, assert, BEHIND, cloneouts(), vars::cm, colorcomplement(), LACON, LATYPE_AHEAD_NEG, LATYPE_AHEAD_POS, LATYPE_BEHIND_NEG, LATYPE_BEHIND_POS, newarc(), newlacon(), vars::nfa, NOTREACHED, s1, and single_color_transition().

Referenced by parseqatom().

◆ pseudocolor()

static color pseudocolor ( struct colormap cm)
static

◆ pull()

static int pull ( struct nfa nfa,
struct arc con,
struct state **  intermediates 
)
static

◆ pullback()

static void pullback ( struct nfa nfa,
FILE *  f 
)
static

◆ push()

static int push ( struct nfa nfa,
struct arc con,
struct state **  intermediates 
)
static

◆ pushfwd()

static void pushfwd ( struct nfa nfa,
FILE *  f 
)
static

◆ rainbow()

static void rainbow ( struct nfa nfa,
struct colormap cm,
int  type,
color  but,
struct state from,
struct state to 
)
static

Referenced by makesearch(), and parseqatom().

◆ range()

static struct cvec* range ( struct vars v,
chr  a,
chr  b,
int  cases 
)
static

Referenced by brackpart().

◆ removecantmatch()

static void removecantmatch ( struct nfa nfa)
static

◆ removecaptures()

static void removecaptures ( struct vars v,
struct subre t 
)
static

Definition at line 2218 of file regcomp.c.

2220 {
2221  struct subre *t2;
2222 
2223  assert(t != NULL);
2224 
2225  /*
2226  * If this isn't itself a backref target, clear capno and tentatively
2227  * clear CAP flag.
2228  */
2229  if (!(t->flags & BRUSE))
2230  {
2231  t->capno = 0;
2232  t->flags &= ~CAP;
2233  }
2234 
2235  /* Now recurse to children */
2236  for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
2237  {
2238  removecaptures(v, t2);
2239  /* Propagate child CAP flag back up, if it's still set */
2240  if (t2->flags & CAP)
2241  t->flags |= CAP;
2242  }
2243 
2244  /*
2245  * If t now contains neither captures nor backrefs, there's no longer any
2246  * need to care where its sub-match boundaries are, so we can reduce it to
2247  * a simple DFA node. (Note in particular that MIXED child greediness is
2248  * not a hindrance here, so we don't use the MESSY() macro.)
2249  */
2250  if ((t->flags & (CAP | BACKR)) == 0)
2251  {
2252  if (t->child)
2253  freesubreandsiblings(v, t->child);
2254  t->child = NULL;
2255  t->op = '=';
2256  t->flags &= ~MIXED;
2257  }
2258 }

References assert, BACKR, BRUSE, CAP, subre::capno, subre::child, subre::flags, freesubreandsiblings(), MIXED, subre::op, and subre::sibling.

Referenced by pg_regcomp().

◆ removeconstraints()

static void removeconstraints ( struct nfa nfa,
struct state start,
struct state stop 
)
static

Referenced by parseqatom().

◆ removetraverse()

static void removetraverse ( struct nfa nfa,
struct state s 
)
static

◆ repeat()

static void repeat ( struct vars v,
struct state lp,
struct state rp,
int  m,
int  n 
)
static

Definition at line 1586 of file regcomp.c.

1591 {
1592 #define SOME 2
1593 #define INF 3
1594 #define PAIR(x, y) ((x)*4 + (y))
1595 #define REDUCE(x) ( ((x) == DUPINF) ? INF : (((x) > 1) ? SOME : (x)) )
1596  const int rm = REDUCE(m);
1597  const int rn = REDUCE(n);
1598  struct state *s;
1599  struct state *s2;
1600 
1601  switch (PAIR(rm, rn))
1602  {
1603  case PAIR(0, 0): /* empty string */
1604  delsub(v->nfa, lp, rp);
1605  EMPTYARC(lp, rp);
1606  break;
1607  case PAIR(0, 1): /* do as x| */
1608  EMPTYARC(lp, rp);
1609  break;
1610  case PAIR(0, SOME): /* do as x{1,n}| */
1611  repeat(v, lp, rp, 1, n);
1612  NOERR();
1613  EMPTYARC(lp, rp);
1614  break;
1615  case PAIR(0, INF): /* loop x around */
1616  s = newstate(v->nfa);
1617  NOERR();
1618  moveouts(v->nfa, lp, s);
1619  moveins(v->nfa, rp, s);
1620  EMPTYARC(lp, s);
1621  EMPTYARC(s, rp);
1622  break;
1623  case PAIR(1, 1): /* no action required */
1624  break;
1625  case PAIR(1, SOME): /* do as x{0,n-1}x = (x{1,n-1}|)x */
1626  s = newstate(v->nfa);
1627  NOERR();
1628  moveouts(v->nfa, lp, s);
1629  dupnfa(v->nfa, s, rp, lp, s);
1630  NOERR();
1631  repeat(v, lp, s, 1, n - 1);
1632  NOERR();
1633  EMPTYARC(lp, s);
1634  break;
1635  case PAIR(1, INF): /* add loopback arc */
1636  s = newstate(v->nfa);
1637  s2 = newstate(v->nfa);
1638  NOERR();
1639  moveouts(v->nfa, lp, s);
1640  moveins(v->nfa, rp, s2);
1641  EMPTYARC(lp, s);
1642  EMPTYARC(s2, rp);
1643  EMPTYARC(s2, s);
1644  break;
1645  case PAIR(SOME, SOME): /* do as x{m-1,n-1}x */
1646  s = newstate(v->nfa);
1647  NOERR();
1648  moveouts(v->nfa, lp, s);
1649  dupnfa(v->nfa, s, rp, lp, s);
1650  NOERR();
1651  repeat(v, lp, s, m - 1, n - 1);
1652  break;
1653  case PAIR(SOME, INF): /* do as x{m-1,}x */
1654  s = newstate(v->nfa);
1655  NOERR();
1656  moveouts(v->nfa, lp, s);
1657  dupnfa(v->nfa, s, rp, lp, s);
1658  NOERR();
1659  repeat(v, lp, s, m - 1, n);
1660  break;
1661  default:
1662  ERR(REG_ASSERT);
1663  break;
1664  }
1665 }
#define REDUCE(x)
#define INF
#define PAIR(x, y)
#define SOME

References delsub(), dupnfa(), EMPTYARC, ERR, INF, moveins(), moveouts(), newstate(), vars::nfa, NOERR, PAIR, REDUCE, REG_ASSERT, s2, and SOME.

Referenced by parseqatom().

◆ rfree()

static void rfree ( regex_t re)
static

Definition at line 2447 of file regcomp.c.

2448 {
2449  struct guts *g;
2450 
2451  if (re == NULL || re->re_magic != REMAGIC)
2452  return;
2453 
2454  re->re_magic = 0; /* invalidate RE */
2455  g = (struct guts *) re->re_guts;
2456  re->re_guts = NULL;
2457  re->re_fns = NULL;
2458  if (g != NULL)
2459  {
2460  g->magic = 0;
2461  freecm(&g->cmap);
2462  if (g->tree != NULL)
2463  freesubre((struct vars *) NULL, g->tree);
2464  if (g->lacons != NULL)
2465  freelacons(g->lacons, g->nlacons);
2466  if (!NULLCNFA(g->search))
2467  freecnfa(&g->search);
2468  FREE(g);
2469  }
2470 }
static void freecm(struct colormap *cm)

References guts::cmap, FREE, freecm(), freecnfa(), freelacons(), freesubre(), if(), guts::lacons, guts::magic, guts::nlacons, NULLCNFA, REMAGIC, guts::search, and guts::tree.

Referenced by freev().

◆ rstacktoodeep()

static int rstacktoodeep ( void  )
static

Definition at line 2483 of file regcomp.c.

2484 {
2485  return stack_is_too_deep();
2486 }
bool stack_is_too_deep(void)
Definition: postgres.c:3588

References stack_is_too_deep().

◆ scannum()

static int scannum ( struct vars v)
static

Definition at line 1555 of file regcomp.c.

1556 {
1557  int n = 0;
1558 
1559  while (SEE(DIGIT) && n < DUPMAX)
1560  {
1561  n = n * 10 + v->nextvalue;
1562  NEXT();
1563  }
1564  if (SEE(DIGIT) || n > DUPMAX)
1565  {
1566  ERR(REG_BADBR);
1567  return 0;
1568  }
1569  return n;
1570 }
#define DUPMAX
Definition: regguts.h:98

References DIGIT, DUPMAX, ERR, NEXT, vars::nextvalue, REG_BADBR, and SEE.

Referenced by parseqatom().

◆ scanplain()

static const chr * scanplain ( struct vars v)
static

Definition at line 1886 of file regcomp.c.

1887 {
1888  const chr *endp;
1889 
1890  assert(SEE(COLLEL) || SEE(ECLASS) || SEE(CCLASS));
1891  NEXT();
1892 
1893  endp = v->now;
1894  while (SEE(PLAIN))
1895  {
1896  endp = v->now;
1897  NEXT();
1898  }
1899 
1900  assert(SEE(END) || ISERR());
1901  NEXT();
1902 
1903  return endp;
1904 }
#define END
Definition: regcomp.c:337

References assert, CCLASS, COLLEL, ECLASS, END, ISERR, NEXT, vars::now, PLAIN, and SEE.

Referenced by brackpart().

◆ single_color_transition()

static struct state* single_color_transition ( struct state s1,
struct state s2 
)
static

Referenced by processlacon().

◆ skip()

static void skip ( struct vars v)
static

◆ sortins()

static void sortins ( struct nfa nfa,
struct state s 
)
static

◆ sortins_cmp()

static int sortins_cmp ( const void *  a,
const void *  b 
)
static

◆ sortouts()

static void sortouts ( struct nfa nfa,
struct state s 
)
static

◆ sortouts_cmp()

static int sortouts_cmp ( const void *  a,
const void *  b 
)
static

◆ specialcolors()

static void specialcolors ( struct nfa nfa)
static

Referenced by nfanode(), and pg_regcomp().

◆ subcolor()

static color subcolor ( struct colormap cm,
chr  c 
)
static

Referenced by pg_regcomp().

◆ subcolorcvec()

static void subcolorcvec ( struct vars v,
struct cvec cv,
struct state lp,
struct state rp 
)
static

◆ subcolorhi()

static color subcolorhi ( struct colormap cm,
color pco 
)
static

◆ subcoloronechr()

static void subcoloronechr ( struct vars v,
chr  ch,
struct state lp,
struct state rp,
color lastsubcolor 
)
static

Referenced by onechr().

◆ subcoloronerange()

static void subcoloronerange ( struct vars v,
chr  from,
chr  to,
struct state lp,
struct state rp,
color lastsubcolor 
)
static

◆ subcoloronerow()

static void subcoloronerow ( struct vars v,
int  rownum,
struct state lp,
struct state rp,
color lastsubcolor 
)
static

◆ subre()

static struct subre * subre ( struct vars v,
int  op,
int  flags,
struct state begin,
struct state end 
)
static

Definition at line 2095 of file regcomp.c.

2100 {
2101  struct subre *ret = v->treefree;
2102 
2103  /*
2104  * Checking for stack overflow here is sufficient to protect parse() and
2105  * its recursive subroutines.
2106  */
2107  if (STACK_TOO_DEEP(v->re))
2108  {
2109  ERR(REG_ETOOBIG);
2110  return NULL;
2111  }
2112 
2113  if (ret != NULL)
2114  v->treefree = ret->child;
2115  else
2116  {
2117  ret = (struct subre *) MALLOC(sizeof(struct subre));
2118  if (ret == NULL)
2119  {
2120  ERR(REG_ESPACE);
2121  return NULL;
2122  }
2123  ret->chain = v->treechain;
2124  v->treechain = ret;
2125  }
2126 
2127  assert(strchr("=b|.*(", op) != NULL);
2128 
2129  ret->op = op;
2130  ret->flags = flags;
2131  ret->latype = (char) -1;
2132  ret->id = 0; /* will be assigned later */
2133  ret->capno = 0;
2134  ret->backno = 0;
2135  ret->min = ret->max = 1;
2136  ret->child = NULL;
2137  ret->sibling = NULL;
2138  ret->begin = begin;
2139  ret->end = end;
2140  ZAPCNFA(ret->cnfa);
2141 
2142  return ret;
2143 }
#define REG_ETOOBIG
Definition: regex.h:233
#define STACK_TOO_DEEP(re)
Definition: regguts.h:523

References assert, subre::backno, subre::begin, subre::capno, subre::chain, subre::child, subre::cnfa, subre::end, ERR, subre::flags, subre::id, subre::latype, MALLOC, subre::max, subre::min, subre::op, vars::re, REG_ESPACE, REG_ETOOBIG, subre::sibling, STACK_TOO_DEEP, vars::treechain, vars::treefree, and ZAPCNFA.

Referenced by parse(), parsebranch(), and parseqatom().

◆ uncolorchain()

static void uncolorchain ( struct colormap cm,
struct arc a 
)
static

◆ word()

◆ wordchrs()

static void wordchrs ( struct vars v)
static

Definition at line 1993 of file regcomp.c.

1994 {
1995  struct state *cstate;
1996  struct cvec *cv;
1997 
1998  if (v->wordchrs != NULL)
1999  return; /* done already */
2000 
2001  /* make dummy state to hang the cache arcs on */
2002  cstate = newstate(v->nfa);
2003  NOERR();
2004 
2005  /* obtain possibly-cached cvec for \w characters */
2006  NOTE(REG_ULOCALE);
2007  cv = cclasscvec(v, CC_WORD, (v->cflags & REG_ICASE));
2008  NOERR();
2009 
2010  /* build the arcs; this may cause color splitting */
2011  subcolorcvec(v, cv, cstate, cstate);
2012  NOERR();
2013 
2014  /* close new open subcolors to ensure the cache entry is self-contained */
2015  okcolors(v->nfa, v->cm);
2016  NOERR();
2017 
2018  /* success! save the cache pointer */
2019  v->wordchrs = cstate;
2020 }
@ CC_WORD
Definition: regguts.h:141

References CC_WORD, cclasscvec(), vars::cflags, vars::cm, newstate(), vars::nfa, NOERR, NOTE, okcolors(), REG_ICASE, REG_ULOCALE, subcolorcvec(), and vars::wordchrs.

Referenced by parseqatom().

Variable Documentation

◆ functions