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 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 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 341 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 332 of file regcomp.c.

◆ BEHIND

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

Definition at line 342 of file regcomp.c.

◆ CCLASS

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

Definition at line 335 of file regcomp.c.

◆ CCLASSC

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

Definition at line 338 of file regcomp.c.

◆ CCLASSS

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

Definition at line 337 of file regcomp.c.

◆ CNOERR

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

◆ COLLEL

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

Definition at line 333 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:69
#define BEHIND
Definition: regcomp.c:342
#define AHEAD
Definition: regcomp.c:341
#define PLAIN
Definition: regcomp.c:330
const char * type

Definition at line 350 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 331 of file regcomp.c.

◆ EAT

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

Definition at line 314 of file regcomp.c.

◆ ECLASS

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

Definition at line 334 of file regcomp.c.

◆ EMPTY

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

Definition at line 328 of file regcomp.c.

◆ EMPTYARC

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

Definition at line 325 of file regcomp.c.

◆ END

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

Definition at line 336 of file regcomp.c.

◆ EOS

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

Definition at line 329 of file regcomp.c.

◆ ERR

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

Definition at line 319 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 323 of file regcomp.c.

◆ ISERR

#define ISERR ( )    VISERR(v)

Definition at line 316 of file regcomp.c.

◆ LACON

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

Definition at line 340 of file regcomp.c.

◆ NEXT

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

Definition at line 312 of file regcomp.c.

◆ NOERR

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

Definition at line 320 of file regcomp.c.

◆ NOERRN

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

Definition at line 321 of file regcomp.c.

◆ NOERRZ

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

Definition at line 322 of file regcomp.c.

◆ NOTE

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

Definition at line 324 of file regcomp.c.

◆ NWBDRY

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

Definition at line 344 of file regcomp.c.

◆ PAIR

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

◆ PLAIN

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

Definition at line 330 of file regcomp.c.

◆ RANGE

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

Definition at line 339 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 345 of file regcomp.c.

◆ SEE

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

Definition at line 313 of file regcomp.c.

◆ SEND

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

Definition at line 346 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:329

Definition at line 317 of file regcomp.c.

◆ VISERR

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

Definition at line 315 of file regcomp.c.

◆ WBDRY

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

Definition at line 343 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 1671 of file regcomp.c.

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

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 1761 of file regcomp.c.

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

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 1727 of file regcomp.c.

1730 {
1731  struct state *left = newstate(v->nfa);
1732  struct state *right = newstate(v->nfa);
1733 
1734  NOERR();
1735  bracket(v, left, right);
1736 
1737  /* in NLSTOP mode, ensure newline is not part of the result set */
1738  if (v->cflags & REG_NLSTOP)
1739  newarc(v->nfa, PLAIN, v->nlcolor, left, right);
1740  NOERR();
1741 
1742  assert(lp->nouts == 0); /* all outarcs will be ours */
1743 
1744  /*
1745  * Easy part of complementing, and all there is to do since the MCCE code
1746  * was removed. Note that the result of colorcomplement() cannot be a
1747  * rainbow, since we don't allow empty brackets; so there's no point in
1748  * calling optimizebracket() again.
1749  */
1750  colorcomplement(v->nfa, v->cm, PLAIN, left, lp, rp);
1751  NOERR();
1752  dropstate(v->nfa, left);
1753  assert(right->nins == 0);
1754  freestate(v->nfa, right);
1755 }
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:1671
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:297

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 1492 of file regcomp.c.

1496 {
1497  struct cvec *cv;
1498 
1499  /* obtain possibly-cached cvec for char class */
1500  NOTE(REG_ULOCALE);
1501  cv = cclasscvec(v, cls, (v->cflags & REG_ICASE));
1502  NOERR();
1503 
1504  /* build the arcs; this may cause color splitting */
1505  subcolorcvec(v, cv, lp, rp);
1506 }
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 1516 of file regcomp.c.

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

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 2310 of file regcomp.c.

2311 {
2312  struct subre *t;
2313  struct subre *next;
2314 
2315  for (t = v->treechain; t != NULL; t = next)
2316  {
2317  next = t->chain;
2318  if (!(t->flags & INUSE))
2319  FREE(t);
2320  }
2321  v->treechain = NULL;
2322  v->treefree = NULL; /* just on general principles */
2323 }
#define FREE(ptr)
Definition: cryptohash.c:37
static int next(struct vars *v)
#define INUSE
Definition: regguts.h:486
Definition: regguts.h:477
struct subre * chain
Definition: regguts.h:506
char flags
Definition: regguts.h:479
struct subre * treechain
Definition: regcomp.c:300
struct subre * treefree
Definition: regcomp.c:301

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 2427 of file regcomp.c.

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

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 2185 of file regcomp.c.

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

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 2150 of file regcomp.c.

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

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 2169 of file regcomp.c.

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

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 590 of file regcomp.c.

592 {
593  if (v->re != NULL)
594  rfree(v->re);
595  if (v->subs != v->sub10)
596  FREE(v->subs);
597  if (v->nfa != NULL)
598  freenfa(v->nfa);
599  if (v->tree != NULL)
600  freesubre(v, v->tree);
601  if (v->treechain != NULL)
602  cleanst(v);
603  if (v->cv != NULL)
604  freecvec(v->cv);
605  if (v->cv2 != NULL)
606  freecvec(v->cv2);
607  if (v->lacons != NULL)
608  freelacons(v->lacons, v->nlacons);
609  ERR(err); /* nop if err==0 */
610 
611  return v->err;
612 }
static void freecvec(struct cvec *cv)
static void freenfa(struct nfa *nfa)
static void cleanst(struct vars *v)
Definition: regcomp.c:2310
static void rfree(regex_t *re)
Definition: regcomp.c:2444
static void freelacons(struct subre *subs, int n)
Definition: regcomp.c:2427
struct subre * tree
Definition: regcomp.c:299
struct subre ** subs
Definition: regcomp.c:292
int nlacons
Definition: regcomp.c:306
struct subre * lacons
Definition: regcomp.c:305
int err
Definition: regcomp.c:285
regex_t * re
Definition: regcomp.c:282
struct subre * sub10[10]
Definition: regcomp.c:294
struct cvec * cv2
Definition: regcomp.c:304
struct cvec * cv
Definition: regcomp.c:303

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 619 of file regcomp.c.

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

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

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 553 of file regcomp.c.

555 {
556  struct subre **p;
557  size_t n;
558 
559  assert(wanted > 0 && (size_t) wanted >= v->nsubs);
560  n = (size_t) wanted * 3 / 2 + 1;
561 
562  if (v->subs == v->sub10)
563  {
564  p = (struct subre **) MALLOC(n * sizeof(struct subre *));
565  if (p != NULL)
566  memcpy(VS(p), VS(v->subs),
567  v->nsubs * sizeof(struct subre *));
568  }
569  else
570  p = (struct subre **) REALLOC(v->subs, n * sizeof(struct subre *));
571  if (p == NULL)
572  {
573  ERR(REG_ESPACE);
574  return;
575  }
576  v->subs = p;
577  for (p = &v->subs[v->nsubs]; v->nsubs < n; p++, v->nsubs++)
578  *p = NULL;
579  assert(v->nsubs == n);
580  assert((size_t) wanted < v->nsubs);
581 }
#define REALLOC(p, n)
Definition: regcustom.h:54
#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:293

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 2388 of file regcomp.c.

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

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 2349 of file regcomp.c.

2353 {
2354  struct nfa *nfa;
2355  long ret = 0;
2356 
2357  assert(t->begin != NULL);
2358 
2359 #ifdef REG_DEBUG
2360  if (f != NULL)
2361  {
2362  char idbuf[50];
2363 
2364  fprintf(f, "\n\n\n========= TREE NODE %s ==========\n",
2365  stid(t, idbuf, sizeof(idbuf)));
2366  }
2367 #endif
2368  nfa = newnfa(v, v->cm, v->nfa);
2369  NOERRZ();
2370  dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final);
2371  if (!ISERR())
2372  specialcolors(nfa);
2373  if (!ISERR())
2374  ret = optimize(nfa, f);
2375  if (converttosearch && !ISERR())
2376  makesearch(v, nfa);
2377  if (!ISERR())
2378  compact(nfa, &t->cnfa);
2379 
2380  freenfa(nfa);
2381  return ret;
2382 }
#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:619
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:322
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, 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 2329 of file regcomp.c.

2332 {
2333  struct subre *t2;
2334 
2335  assert(t != NULL && t->begin != NULL);
2336 
2337  for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
2338  (DISCARD) nfatree(v, t2, f);
2339 
2340  return nfanode(v, t, 0, f);
2341 }
static long nfanode(struct vars *v, struct subre *t, int converttosearch, FILE *f)
Definition: regcomp.c:2349
static long nfatree(struct vars *v, struct subre *t, FILE *f)
Definition: regcomp.c:2329
#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 1456 of file regcomp.c.

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

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 2262 of file regcomp.c.

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

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 1909 of file regcomp.c.

1913 {
1914  if (!(v->cflags & REG_ICASE))
1915  {
1916  color lastsubcolor = COLORLESS;
1917 
1918  subcoloronechr(v, c, lp, rp, &lastsubcolor);
1919  return;
1920  }
1921 
1922  /* rats, need general case anyway... */
1923  subcolorcvec(v, allcases(v, c), lp, rp);
1924 }
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 1935 of file regcomp.c.

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

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

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_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 783 of file regcomp.c.

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

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

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 370 of file regcomp.c.

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

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 2027 of file regcomp.c.

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

◆ removecaptures()

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

Definition at line 2216 of file regcomp.c.

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

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 1584 of file regcomp.c.

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

2445 {
2446  struct guts *g;
2447 
2448  if (re == NULL || re->re_magic != REMAGIC)
2449  return;
2450 
2451  re->re_magic = 0; /* invalidate RE */
2452  g = (struct guts *) re->re_guts;
2453  re->re_guts = NULL;
2454  re->re_fns = NULL;
2455  if (g != NULL)
2456  {
2457  g->magic = 0;
2458  freecm(&g->cmap);
2459  if (g->tree != NULL)
2460  freesubre((struct vars *) NULL, g->tree);
2461  if (g->lacons != NULL)
2462  freelacons(g->lacons, g->nlacons);
2463  if (!NULLCNFA(g->search))
2464  freecnfa(&g->search);
2465  FREE(g);
2466  }
2467 }
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 2480 of file regcomp.c.

2481 {
2482  return stack_is_too_deep();
2483 }
bool stack_is_too_deep(void)
Definition: postgres.c:3545

References stack_is_too_deep().

◆ scannum()

static int scannum ( struct vars v)
static

Definition at line 1553 of file regcomp.c.

1554 {
1555  int n = 0;
1556 
1557  while (SEE(DIGIT) && n < DUPMAX)
1558  {
1559  n = n * 10 + v->nextvalue;
1560  NEXT();
1561  }
1562  if (SEE(DIGIT) || n > DUPMAX)
1563  {
1564  ERR(REG_BADBR);
1565  return 0;
1566  }
1567  return n;
1568 }
#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 1884 of file regcomp.c.

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

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 2093 of file regcomp.c.

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

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 1991 of file regcomp.c.

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