PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
regcomp.c File Reference
#include "regex/regguts.h"
#include "regc_lex.c"
#include "regc_color.c"
#include "regc_nfa.c"
#include "regc_cvec.c"
#include "regc_pg_locale.c"
#include "regc_locale.c"
Include dependency graph for regcomp.c:

Go to the source code of this file.

Data Structures

struct  vars
 

Macros

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

Functions

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

Variables

static const struct fns functions
 

Macro Definition Documentation

◆ AHEAD

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

Definition at line 342 of file regcomp.c.

◆ ARCV

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

◆ BACKREF

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

Definition at line 333 of file regcomp.c.

◆ BEHIND

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

Definition at line 343 of file regcomp.c.

◆ CANTMATCH

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

Definition at line 346 of file regcomp.c.

◆ CCLASS

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

Definition at line 336 of file regcomp.c.

◆ CCLASSC

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

Definition at line 339 of file regcomp.c.

◆ CCLASSS

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

Definition at line 338 of file regcomp.c.

◆ CNOERR

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

◆ COLLEL

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

Definition at line 334 of file regcomp.c.

◆ COLORED

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

Definition at line 352 of file regcomp.c.

◆ COMPATIBLE

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

Definition at line 201 of file regcomp.c.

◆ DIGIT

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

Definition at line 332 of file regcomp.c.

◆ EAT

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

Definition at line 315 of file regcomp.c.

◆ ECLASS

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

Definition at line 335 of file regcomp.c.

◆ EMPTY

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

Definition at line 329 of file regcomp.c.

◆ EMPTYARC

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

Definition at line 326 of file regcomp.c.

◆ END

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

Definition at line 337 of file regcomp.c.

◆ EOS

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

Definition at line 330 of file regcomp.c.

◆ ERR

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

Definition at line 320 of file regcomp.c.

◆ INCOMPATIBLE

#define INCOMPATIBLE   1 /* destroys arc */

Definition at line 199 of file regcomp.c.

◆ INF

#define INF   3

◆ INSIST

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

Definition at line 324 of file regcomp.c.

◆ ISERR

#define ISERR ( )    VISERR(v)

Definition at line 317 of file regcomp.c.

◆ LACON

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

Definition at line 341 of file regcomp.c.

◆ NEXT

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

Definition at line 313 of file regcomp.c.

◆ NOERR

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

Definition at line 321 of file regcomp.c.

◆ NOERRN

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

Definition at line 322 of file regcomp.c.

◆ NOERRZ

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

Definition at line 323 of file regcomp.c.

◆ NOTE

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

Definition at line 325 of file regcomp.c.

◆ NWBDRY

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

Definition at line 345 of file regcomp.c.

◆ PAIR

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

◆ PLAIN

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

Definition at line 331 of file regcomp.c.

◆ RANGE

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

Definition at line 340 of file regcomp.c.

◆ REDUCE

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

◆ REPLACEARC

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

Definition at line 202 of file regcomp.c.

◆ SATISFIED

#define SATISFIED   2 /* constraint satisfied */

Definition at line 200 of file regcomp.c.

◆ SBEGIN

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

Definition at line 347 of file regcomp.c.

◆ SEE

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

Definition at line 314 of file regcomp.c.

◆ SEND

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

Definition at line 348 of file regcomp.c.

◆ SOME

#define SOME   2

◆ VERR

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

Definition at line 318 of file regcomp.c.

◆ VISERR

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

Definition at line 316 of file regcomp.c.

◆ WBDRY

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

Definition at line 344 of file regcomp.c.

Function Documentation

◆ addchr()

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

◆ addrange()

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

◆ allcases()

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

Referenced by onechr().

◆ allocarc()

static struct arc * allocarc ( struct nfa nfa)
static

◆ analyze()

static long analyze ( struct nfa nfa)
static

◆ before()

static int before ( chr  x,
chr  y 
)
static

◆ bracket()

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

Definition at line 1673 of file regcomp.c.

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

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

Referenced by cbracket(), and parseqatom().

◆ brackpart()

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

Definition at line 1763 of file regcomp.c.

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

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

Referenced by bracket().

◆ breakconstraintloop()

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

◆ brenext()

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

◆ carc_cmp()

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

◆ carcsort()

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

◆ casecmp()

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

Referenced by pg_regcomp().

◆ cbracket()

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

Definition at line 1729 of file regcomp.c.

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

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

Referenced by parseqatom().

◆ cclass_column_index()

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

◆ cclasscvec()

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

◆ changearcsource()

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

◆ changearctarget()

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

◆ charclass()

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

Definition at line 1494 of file regcomp.c.

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

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

Referenced by brackpart(), and parseqatom().

◆ charclasscomplement()

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

Definition at line 1518 of file regcomp.c.

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

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

Referenced by bracket(), and parseqatom().

◆ check_in_colors_match()

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

◆ check_out_colors_match()

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

◆ checkmatchall()

static void checkmatchall ( struct nfa nfa)
static

◆ checkmatchall_recurse()

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

◆ chrnamed()

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

◆ cleanst()

static void cleanst ( struct vars v)
static

Definition at line 2312 of file regcomp.c.

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

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

Referenced by freev(), and pg_regcomp().

◆ cleanup()

static void cleanup ( struct nfa nfa)
static

◆ clearcvec()

static struct cvec * clearcvec ( struct cvec cv)
static

◆ cleartraverse()

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

◆ cloneouts()

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

Referenced by processlacon(), and word().

◆ clonesuccessorstates()

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

◆ cmp()

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

Referenced by pg_regcomp().

◆ colorchain()

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

◆ colorcomplement()

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

◆ combine()

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

◆ compact()

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

Referenced by nfanode(), and pg_regcomp().

◆ copyins()

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

◆ copyouts()

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

Referenced by makesearch().

◆ cparc()

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

Referenced by makesearch().

◆ createarc()

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

◆ delsub()

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

Referenced by parseqatom(), and repeat().

◆ deltraverse()

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

◆ dropstate()

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

Referenced by cbracket(), and charclasscomplement().

◆ dumpnfa()

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

Referenced by pg_regcomp().

◆ dupnfa()

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

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

◆ duptraverse()

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

◆ eclass()

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

Referenced by brackpart().

◆ element()

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

Referenced by brackpart().

◆ emptyreachable()

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

◆ findarc()

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

◆ findconstraintloop()

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

◆ fixconstraintloops()

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

◆ fixempties()

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

◆ freearc()

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

Referenced by makesearch(), and optimizebracket().

◆ freecm()

static void freecm ( struct colormap cm)
static

Referenced by rfree().

◆ freecnfa()

static void freecnfa ( struct cnfa cnfa)
static

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

◆ freecolor()

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

◆ freecvec()

static void freecvec ( struct cvec cv)
static

Referenced by freev().

◆ freelacons()

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

Definition at line 2430 of file regcomp.c.

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

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

Referenced by freev(), and rfree().

◆ freenfa()

static void freenfa ( struct nfa nfa)
static

Referenced by freev(), and nfanode().

◆ freesrnode()

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

Definition at line 2187 of file regcomp.c.

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

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

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

◆ freestate()

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

Referenced by cbracket().

◆ freesubre()

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

Definition at line 2152 of file regcomp.c.

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

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

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

◆ freesubreandsiblings()

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

Definition at line 2171 of file regcomp.c.

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

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

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

◆ freev()

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

Definition at line 592 of file regcomp.c.

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

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

Referenced by pg_regcomp().

◆ getcvec()

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

◆ hasconstraintout()

static int hasconstraintout ( struct state s)
static

◆ hasnonemptyout()

static int hasnonemptyout ( struct state s)
static

◆ initcm()

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

Referenced by pg_regcomp().

◆ isconstraintarc()

static int isconstraintarc ( struct arc a)
static

◆ lexdigits()

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

◆ lexescape()

static int lexescape ( struct vars v)
static

◆ lexstart()

static void lexstart ( struct vars v)
static

Referenced by pg_regcomp().

◆ lookupcclass()

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

Referenced by brackpart().

◆ makesearch()

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

Definition at line 621 of file regcomp.c.

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

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

Referenced by nfanode(), and pg_regcomp().

◆ markcanreach()

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

◆ markreachable()

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

◆ markst()

static void markst ( struct subre t)
static

Definition at line 2297 of file regcomp.c.

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

References assert, subre::child, subre::flags, INUSE, markst(), and subre::sibling.

Referenced by markst(), and pg_regcomp().

◆ maxcolor()

static color maxcolor ( struct colormap cm)
static

◆ mergeins()

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

◆ moresubs()

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

Definition at line 555 of file regcomp.c.

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

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

Referenced by parseqatom().

◆ moveins()

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

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

◆ moveouts()

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

Referenced by parseqatom(), and repeat().

◆ newarc()

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

◆ newcolor()

static color newcolor ( struct colormap cm)
static

◆ newcvec()

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

Referenced by pg_regcomp().

◆ newfstate()

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

◆ newhicolorcols()

static void newhicolorcols ( struct colormap cm)
static

◆ newhicolorrow()

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

◆ newlacon()

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

Definition at line 2391 of file regcomp.c.

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

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

Referenced by processlacon().

◆ newline()

static chr newline ( void  )
static

Referenced by pg_regcomp().

◆ newnfa()

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

Referenced by nfanode(), and pg_regcomp().

◆ newstate()

static struct state * newstate ( struct nfa nfa)
static

◆ newsub()

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

◆ next()

static int next ( struct vars v)
static

Referenced by cleanst(), and freesubreandsiblings().

◆ nfanode()

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

Definition at line 2351 of file regcomp.c.

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

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

Referenced by nfatree(), and pg_regcomp().

◆ nfatree()

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

Definition at line 2331 of file regcomp.c.

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

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

Referenced by nfatree(), and pg_regcomp().

◆ nonword()

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

Definition at line 1458 of file regcomp.c.

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

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

Referenced by parseqatom().

◆ numst()

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

Definition at line 2264 of file regcomp.c.

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

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

Referenced by numst(), and pg_regcomp().

◆ okcolors()

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

◆ onechr()

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

Definition at line 1911 of file regcomp.c.

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

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

Referenced by brackpart(), and parseqatom().

◆ optimize()

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

Referenced by nfanode(), and pg_regcomp().

◆ optimizebracket()

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

Definition at line 1937 of file regcomp.c.

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

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

Referenced by bracket().

◆ parse()

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

Definition at line 717 of file regcomp.c.

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

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

Referenced by add_foreign_final_paths(), add_foreign_grouping_paths(), add_foreign_ordered_paths(), add_paths_to_grouping_rel(), build_minmax_path(), can_partial_agg(), check_sql_stmt_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(), expand_virtual_generated_columns(), flatten_simple_union_all(), get_nullingrels(), get_number_of_groups(), get_sql_fn_result_tlist(), get_useful_group_keys_orderings(), grouping_planner(), is_degenerate_grouping(), json_manifest_array_end(), json_manifest_array_start(), json_manifest_finalize_file(), json_manifest_finalize_system_identifier(), json_manifest_finalize_version(), json_manifest_finalize_wal_range(), json_manifest_object_end(), json_manifest_object_field_start(), json_manifest_object_start(), json_manifest_scalar(), json_parse_manifest(), json_parse_manifest_incremental_chunk(), json_parse_manifest_incremental_init(), limit_needed(), main(), make_group_input_target(), make_sort_input_target(), max_parallel_hazard(), parseqatom(), perform_pullup_replace_vars(), pg_regcomp(), pgss_planner(), plan_set_operations(), planner(), preprocess_groupclause(), preprocess_grouping_sets(), preprocess_limit(), preprocess_minmax_aggregates(), preprocess_rowmarks(), preprocess_targetlist(), pull_up_constant_function(), pull_up_simple_subquery(), pull_up_simple_values(), query_planner(), remove_useless_groupby_columns(), replace_empty_jointree(), resolve_unique_index_expr(), set_subquery_pathlist(), standard_planner(), standard_qp_callback(), subquery_planner(), transform_MERGE_to_join(), and verify_manifest_checksum().

◆ parsebranch()

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

Definition at line 785 of file regcomp.c.

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

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

Referenced by parse(), and parseqatom().

◆ parseqatom()

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

Definition at line 838 of file regcomp.c.

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

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

Referenced by parsebranch().

◆ pg_regcomp()

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

Definition at line 372 of file regcomp.c.

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

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

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

◆ pg_wc_isalnum()

static int pg_wc_isalnum ( pg_wchar  c)
static

◆ pg_wc_isalpha()

static int pg_wc_isalpha ( pg_wchar  c)
static

◆ pg_wc_isdigit()

static int pg_wc_isdigit ( pg_wchar  c)
static

◆ pg_wc_isgraph()

static int pg_wc_isgraph ( pg_wchar  c)
static

◆ pg_wc_islower()

static int pg_wc_islower ( pg_wchar  c)
static

◆ pg_wc_isprint()

static int pg_wc_isprint ( pg_wchar  c)
static

◆ pg_wc_ispunct()

static int pg_wc_ispunct ( pg_wchar  c)
static

◆ pg_wc_isspace()

static int pg_wc_isspace ( pg_wchar  c)
static

◆ pg_wc_isupper()

static int pg_wc_isupper ( pg_wchar  c)
static

◆ pg_wc_isword()

static int pg_wc_isword ( pg_wchar  c)
static

◆ pg_wc_tolower()

static pg_wchar pg_wc_tolower ( pg_wchar  c)
static

◆ pg_wc_toupper()

static pg_wchar pg_wc_toupper ( pg_wchar  c)
static

◆ prefixes()

static void prefixes ( struct vars v)
static

◆ processlacon()

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

Definition at line 2029 of file regcomp.c.

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

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

Referenced by parseqatom().

◆ pseudocolor()

static color pseudocolor ( struct colormap cm)
static

◆ pull()

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

◆ pullback()

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

◆ push()

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

◆ pushfwd()

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

◆ rainbow()

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

Referenced by makesearch(), and parseqatom().

◆ range()

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

Referenced by brackpart().

◆ removecantmatch()

static void removecantmatch ( struct nfa nfa)
static

◆ removecaptures()

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

Definition at line 2218 of file regcomp.c.

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

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

Referenced by pg_regcomp(), and removecaptures().

◆ removeconstraints()

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

Referenced by parseqatom().

◆ removetraverse()

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

◆ repeat()

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

Definition at line 1586 of file regcomp.c.

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

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

Referenced by parseqatom(), and repeat().

◆ rfree()

static void rfree ( regex_t re)
static

Definition at line 2447 of file regcomp.c.

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

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

Referenced by freev().

◆ rstacktoodeep()

static int rstacktoodeep ( void  )
static

Definition at line 2483 of file regcomp.c.

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

References stack_is_too_deep().

◆ scannum()

static int scannum ( struct vars v)
static

Definition at line 1555 of file regcomp.c.

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

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

Referenced by parseqatom().

◆ scanplain()

static const chr * scanplain ( struct vars v)
static

Definition at line 1886 of file regcomp.c.

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

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

Referenced by brackpart().

◆ single_color_transition()

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

Referenced by processlacon().

◆ skip()

static void skip ( struct vars v)
static

◆ sortins()

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

◆ sortins_cmp()

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

◆ sortouts()

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

◆ sortouts_cmp()

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

◆ specialcolors()

static void specialcolors ( struct nfa nfa)
static

Referenced by nfanode(), and pg_regcomp().

◆ subcolor()

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

Referenced by pg_regcomp().

◆ subcolorcvec()

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

◆ subcolorhi()

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

◆ subcoloronechr()

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

Referenced by onechr().

◆ subcoloronerange()

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

◆ subcoloronerow()

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

◆ subre()

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

Definition at line 2095 of file regcomp.c.

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

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

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

◆ uncolorchain()

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

◆ word()

◆ wordchrs()

static void wordchrs ( struct vars v)
static

Definition at line 1993 of file regcomp.c.

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

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

Referenced by parseqatom().

Variable Documentation

◆ functions