#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 subre *	parse (struct vars v, int stopper, int type, struct state init, struct state *final)

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

static struct subre *	parseqatom (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 chr *	scanplain (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 subre *	subre (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 nfa *	newnfa (struct vars v, struct colormap cm, struct nfa *parent)

static void	freenfa (struct nfa *nfa)

static struct state *	newstate (struct nfa *nfa)

static struct state *	newfstate (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 arc *	allocarc (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 arc *	findarc (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 state *	single_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 state *	emptyreachable (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 cvec *	newcvec (int nchrs, int nranges)

static struct cvec *	clearcvec (struct cvec *cv)

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

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

static struct cvec *	getcvec (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 cvec *	range (struct vars *v, chr a, chr b, int cases)

static int	before (chr x, chr y)

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

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

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

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

static struct cvec *	allcases (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))

a

int a

Definition: isn.c:73

BEHIND

#define BEHIND

Definition: regcomp.c:343

AHEAD

#define AHEAD

Definition: regcomp.c:342

PLAIN

#define PLAIN

Definition: regcomp.c:331

type

const char * type

Definition: wait_event_funcs.c:27

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)))

err

void err(int eval, const char *fmt,...)

Definition: err.c:43

e

Definition: preproc-init.c:82

EOS

#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.

{
    /*
     * We can't process complemented char classes (e.g. \W) immediately while
     * scanning the bracket expression, else color bookkeeping gets confused.
     * Instead, remember whether we saw any in have_cclassc[], and process
     * them at the end.
     */
    bool        have_cclassc[NUM_CCLASSES];
    bool        any_cclassc;
    int         i;
 
    memset(have_cclassc, false, sizeof(have_cclassc));
 
    assert(SEE('['));
    NEXT();
    while (!SEE(']') && !SEE(EOS))
        brackpart(v, lp, rp, have_cclassc);
    assert(SEE(']') || ISERR());
 
    /* close up open subcolors from the positive bracket elements */
    okcolors(v->nfa, v->cm);
    NOERR();
 
    /* now handle any complemented elements */
    any_cclassc = false;
    for (i = 0; i < NUM_CCLASSES; i++)
    {
        if (have_cclassc[i])
        {
            charclasscomplement(v, (enum char_classes) i, lp, rp);
            NOERR();
            any_cclassc = true;
        }
    }
 
    /*
     * If we had any complemented elements, see if we can optimize the bracket
     * into a rainbow.  Since a complemented element is the only way a WHITE
     * arc could get into the result, there's no point in checking otherwise.
     */
    if (any_cclassc)
        optimizebracket(v, lp, rp);
}

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.

{
    chr         startc;
    chr         endc;
    struct cvec *cv;
    enum char_classes cls;
    const chr  *startp;
    const chr  *endp;
 
    /* parse something, get rid of special cases, take shortcuts */
    switch (v->nexttype)
    {
        case RANGE:             /* a-b-c or other botch */
            ERR(REG_ERANGE);
            return;
            break;
        case PLAIN:
            startc = v->nextvalue;
            NEXT();
            /* shortcut for ordinary chr (not range) */
            if (!SEE(RANGE))
            {
                onechr(v, startc, lp, rp);
                return;
            }
            NOERR();
            break;
        case COLLEL:
            startp = v->now;
            endp = scanplain(v);
            INSIST(startp < endp, REG_ECOLLATE);
            NOERR();
            startc = element(v, startp, endp);
            NOERR();
            break;
        case ECLASS:
            startp = v->now;
            endp = scanplain(v);
            INSIST(startp < endp, REG_ECOLLATE);
            NOERR();
            startc = element(v, startp, endp);
            NOERR();
            cv = eclass(v, startc, (v->cflags & REG_ICASE));
            NOERR();
            subcolorcvec(v, cv, lp, rp);
            return;
            break;
        case CCLASS:
            startp = v->now;
            endp = scanplain(v);
            INSIST(startp < endp, REG_ECTYPE);
            NOERR();
            cls = lookupcclass(v, startp, endp);
            NOERR();
            charclass(v, cls, lp, rp);
            return;
            break;
        case CCLASSS:
            charclass(v, (enum char_classes) v->nextvalue, lp, rp);
            NEXT();
            return;
            break;
        case CCLASSC:
            /* we cannot call charclasscomplement() immediately */
            have_cclassc[v->nextvalue] = true;
            NEXT();
            return;
            break;
        default:
            ERR(REG_ASSERT);
            return;
            break;
    }
 
    if (SEE(RANGE))
    {
        NEXT();
        switch (v->nexttype)
        {
            case PLAIN:
            case RANGE:
                endc = v->nextvalue;
                NEXT();
                NOERR();
                break;
            case COLLEL:
                startp = v->now;
                endp = scanplain(v);
                INSIST(startp < endp, REG_ECOLLATE);
                NOERR();
                endc = element(v, startp, endp);
                NOERR();
                break;
            default:
                ERR(REG_ERANGE);
                return;
                break;
        }
    }
    else
        endc = startc;
 
    /*
     * Ranges are unportable.  Actually, standard C does guarantee that digits
     * are contiguous, but making that an exception is just too complicated.
     */
    if (startc != endc)
        NOTE(REG_UUNPORT);
    cv = range(v, startc, endc, (v->cflags & REG_ICASE));
    NOERR();
    subcolorcvec(v, cv, lp, rp);
}

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.

{
    struct state *left = newstate(v->nfa);
    struct state *right = newstate(v->nfa);
 
    NOERR();
    bracket(v, left, right);
 
    /* in NLSTOP mode, ensure newline is not part of the result set */
    if (v->cflags & REG_NLSTOP)
        newarc(v->nfa, PLAIN, v->nlcolor, left, right);
    NOERR();
 
    assert(lp->nouts == 0);     /* all outarcs will be ours */
 
    /*
     * Easy part of complementing, and all there is to do since the MCCE code
     * was removed.  Note that the result of colorcomplement() cannot be a
     * rainbow, since we don't allow empty brackets; so there's no point in
     * calling optimizebracket() again.
     */
    colorcomplement(v->nfa, v->cm, PLAIN, left, lp, rp);
    NOERR();
    dropstate(v->nfa, left);
    assert(right->nins == 0);
    freestate(v->nfa, right);
}

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

Referenced by charclass(), charclasscomplement(), and wordchrs().

◆ 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.

{
    struct cvec *cv;
 
    /* obtain possibly-cached cvec for char class */
    NOTE(REG_ULOCALE);
    cv = cclasscvec(v, cls, (v->cflags & REG_ICASE));
    NOERR();
 
    /* build the arcs; this may cause color splitting */
    subcolorcvec(v, cv, lp, rp);
}

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.

{
    struct state *cstate;
    struct cvec *cv;
 
    /* make dummy state to hang temporary arcs on */
    cstate = newstate(v->nfa);
    NOERR();
 
    /* obtain possibly-cached cvec for char class */
    NOTE(REG_ULOCALE);
    cv = cclasscvec(v, cls, (v->cflags & REG_ICASE));
    NOERR();
 
    /* build arcs for char class; this may cause color splitting */
    subcolorcvec(v, cv, cstate, cstate);
    NOERR();
 
    /* clean up any subcolors in the arc set */
    okcolors(v->nfa, v->cm);
    NOERR();
 
    /* now build output arcs for the complement of the char class */
    colorcomplement(v->nfa, v->cm, PLAIN, cstate, lp, rp);
    NOERR();
 
    /* clean up dummy state */
    dropstate(v->nfa, cstate);
}

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.

{
    struct subre *t;
    struct subre *next;
 
    for (t = v->treechain; t != NULL; t = next)
    {
        next = t->chain;
        if (!(t->flags & INUSE))
            FREE(t);
    }
    v->treechain = NULL;
    v->treefree = NULL;         /* just on general principles */
}

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

Referenced by cbracket(), charclasscomplement(), nonword(), and processlacon().

◆ 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.

{
    struct subre *sub;
    int         i;
 
    assert(n > 0);
    for (sub = subs + 1, i = n - 1; i > 0; sub++, i--)  /* no 0th */
        if (!NULLCNFA(sub->cnfa))
            freecnfa(&sub->cnfa);
    FREE(subs);
}

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.

{
    if (sr == NULL)
        return;
 
    if (!NULLCNFA(sr->cnfa))
        freecnfa(&sr->cnfa);
    sr->flags = 0;              /* in particular, not INUSE */
    sr->child = sr->sibling = NULL;
    sr->begin = sr->end = NULL;
 
    if (v != NULL && v->treechain != NULL)
    {
        /* we're still parsing, maybe we can reuse the subre */
        sr->child = v->treefree;
        v->treefree = sr;
    }
    else
        FREE(sr);
}

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.

{
    if (sr == NULL)
        return;
 
    if (sr->child != NULL)
        freesubreandsiblings(v, sr->child);
 
    freesrnode(v, sr);
}

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.

{
    while (sr != NULL)
    {
        struct subre *next = sr->sibling;
 
        freesubre(v, sr);
        sr = next;
    }
}

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.

{
    if (v->re != NULL)
        rfree(v->re);
    if (v->subs != v->sub10)
        FREE(v->subs);
    if (v->nfa != NULL)
        freenfa(v->nfa);
    if (v->tree != NULL)
        freesubre(v, v->tree);
    if (v->treechain != NULL)
        cleanst(v);
    if (v->cv != NULL)
        freecvec(v->cv);
    if (v->cv2 != NULL)
        freecvec(v->cv2);
    if (v->lacons != NULL)
        freelacons(v->lacons, v->nlacons);
    ERR(err);                   /* nop if err==0 */
 
    return v->err;
}

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.

{
    struct arc *a;
    struct arc *b;
    struct state *pre = nfa->pre;
    struct state *s;
    struct state *s2;
    struct state *slist;
 
    /* no loops are needed if it's anchored */
    for (a = pre->outs; a != NULL; a = a->outchain)
    {
        assert(a->type == PLAIN);
        if (a->co != nfa->bos[0] && a->co != nfa->bos[1])
            break;
    }
    if (a != NULL)
    {
        /* add implicit .* in front */
        rainbow(nfa, v->cm, PLAIN, COLORLESS, pre, pre);
 
        /* and ^* and \A* too -- not always necessary, but harmless */
        newarc(nfa, PLAIN, nfa->bos[0], pre, pre);
        newarc(nfa, PLAIN, nfa->bos[1], pre, pre);
 
        /*
         * The pattern is still MATCHALL if it was before, but the max match
         * length is now infinity.
         */
        if (nfa->flags & MATCHALL)
            nfa->maxmatchall = DUPINF;
    }
 
    /*
     * Now here's the subtle part.  Because many REs have no lookback
     * constraints, often knowing when you were in the pre state tells you
     * little; it's the next state(s) that are informative.  But some of them
     * may have other inarcs, i.e. it may be possible to make actual progress
     * and then return to one of them.  We must de-optimize such cases,
     * splitting each such state into progress and no-progress states.
     */
 
    /* first, make a list of the states reachable from pre and elsewhere */
    slist = NULL;
    for (a = pre->outs; a != NULL; a = a->outchain)
    {
        s = a->to;
        for (b = s->ins; b != NULL; b = b->inchain)
        {
            if (b->from != pre)
                break;
        }
 
        /*
         * We want to mark states as being in the list already by having non
         * NULL tmp fields, but we can't just store the old slist value in tmp
         * because that doesn't work for the first such state.  Instead, the
         * first list entry gets its own address in tmp.
         */
        if (b != NULL && s->tmp == NULL)
        {
            s->tmp = (slist != NULL) ? slist : s;
            slist = s;
        }
    }
 
    /* do the splits */
    for (s = slist; s != NULL; s = s2)
    {
        s2 = newstate(nfa);
        NOERR();
        copyouts(nfa, s, s2);
        NOERR();
        for (a = s->ins; a != NULL; a = b)
        {
            b = a->inchain;
            if (a->from != pre)
            {
                cparc(nfa, a, a->from, s2);
                freearc(nfa, a);
            }
        }
        s2 = (s->tmp != s) ? s->tmp : NULL;
        s->tmp = NULL;          /* clean up while we're at it */
    }
}

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.

{
    struct subre *t2;
 
    assert(t != NULL);
 
    t->flags |= INUSE;
    for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
        markst(t2);
}

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.

{
    struct subre **p;
    size_t      n;
 
    assert(wanted > 0 && (size_t) wanted >= v->nsubs);
    n = (size_t) wanted * 3 / 2 + 1;
 
    if (v->subs == v->sub10)
    {
        p = (struct subre **) MALLOC(n * sizeof(struct subre *));
        if (p != NULL)
            memcpy(VS(p), VS(v->subs),
                   v->nsubs * sizeof(struct subre *));
    }
    else
        p = (struct subre **) REALLOC(v->subs, n * sizeof(struct subre *));
    if (p == NULL)
    {
        ERR(REG_ESPACE);
        return;
    }
    v->subs = p;
    for (p = &v->subs[v->nsubs]; v->nsubs < n; p++, v->nsubs++)
        *p = NULL;
    assert(v->nsubs == n);
    assert((size_t) wanted < v->nsubs);
}

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

Referenced by cbracket(), makesearch(), nonword(), optimizebracket(), and processlacon().

◆ 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.

{
    int         n;
    struct subre *newlacons;
    struct subre *sub;
 
    if (v->nlacons == 0)
    {
        n = 1;                  /* skip 0th */
        newlacons = (struct subre *) MALLOC(2 * sizeof(struct subre));
    }
    else
    {
        n = v->nlacons;
        newlacons = (struct subre *) REALLOC(v->lacons,
                                             (n + 1) * sizeof(struct subre));
    }
    if (newlacons == NULL)
    {
        ERR(REG_ESPACE);
        return 0;
    }
    v->lacons = newlacons;
    v->nlacons = n + 1;
    sub = &v->lacons[n];
    sub->begin = begin;
    sub->end = end;
    sub->latype = latype;
    ZAPCNFA(sub->cnfa);
    return n;
}

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

Referenced by cbracket(), charclasscomplement(), makesearch(), parse(), parsebranch(), parseqatom(), repeat(), and wordchrs().

◆ 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.

{
    struct nfa *nfa;
    long        ret = 0;
 
    assert(t->begin != NULL);
 
#ifdef REG_DEBUG
    if (f != NULL)
    {
        char        idbuf[50];
 
        fprintf(f, "\n\n\n========= TREE NODE %s ==========\n",
                stid(t, idbuf, sizeof(idbuf)));
    }
#endif
    nfa = newnfa(v, v->cm, v->nfa);
    NOERRZ();
    dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final);
    nfa->flags = v->nfa->flags;
    if (!ISERR())
        specialcolors(nfa);
    if (!ISERR())
        ret = optimize(nfa, f);
    if (converttosearch && !ISERR())
        makesearch(v, nfa);
    if (!ISERR())
        compact(nfa, &t->cnfa);
 
    freenfa(nfa);
    return ret;
}

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.

{
    struct subre *t2;
 
    assert(t != NULL && t->begin != NULL);
 
    for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
        (DISCARD) nfatree(v, t2, f);
 
    return nfanode(v, t, 0, f);
}

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.

{
    int         anchor = (dir == AHEAD) ? '$' : '^';
 
    assert(dir == AHEAD || dir == BEHIND);
    newarc(v->nfa, anchor, 1, lp, rp);
    newarc(v->nfa, anchor, 0, lp, rp);
    colorcomplement(v->nfa, v->cm, dir, v->wordchrs, lp, rp);
    /* (no need for special attention to \n) */
}

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.

{
    int         i;
    struct subre *t2;
 
    assert(t != NULL);
 
    i = start;
    t->id = i++;
    for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
        i = numst(t2, i);
    return i;
}

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

Referenced by bracket(), charclasscomplement(), parseqatom(), pg_regcomp(), and wordchrs().

◆ onechr()

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

static

Definition at line 1911 of file regcomp.c.

{
    if (!(v->cflags & REG_ICASE))
    {
        color       lastsubcolor = COLORLESS;
 
        subcoloronechr(v, c, lp, rp, &lastsubcolor);
        return;
    }
 
    /* rats, need general case anyway... */
    subcolorcvec(v, allcases(v, c), lp, rp);
}

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.

{
    struct colordesc *cd;
    struct colordesc *end = CDEND(v->cm);
    struct arc *a;
    bool        israinbow;
 
    /*
     * Scan lp's out-arcs and transiently mark the mentioned colors.  We
     * expect that all of lp's out-arcs are plain, non-RAINBOW arcs to rp.
     * (Note: there shouldn't be any pseudocolors yet, but check anyway.)
     */
    for (a = lp->outs; a != NULL; a = a->outchain)
    {
        assert(a->type == PLAIN);
        assert(a->co >= 0);     /* i.e. not RAINBOW */
        assert(a->to == rp);
        cd = &v->cm->cd[a->co];
        assert(!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO));
        cd->flags |= COLMARK;
    }
 
    /* Scan colors, clear transient marks, check for unmarked live colors */
    israinbow = true;
    for (cd = v->cm->cd; cd < end; cd++)
    {
        if (cd->flags & COLMARK)
            cd->flags &= ~COLMARK;
        else if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO))
            israinbow = false;
    }
 
    /* Can't do anything if not all colors have arcs */
    if (!israinbow)
        return;
 
    /* OK, drop existing arcs and replace with a rainbow */
    while ((a = lp->outs) != NULL)
        freearc(v->nfa, a);
    newarc(v->nfa, PLAIN, RAINBOW, lp, rp);
}

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.

{
    struct subre *branches;     /* top level */
    struct subre *lastbranch;   /* latest branch */
 
    assert(stopper == ')' || stopper == EOS);
 
    branches = subre(v, '|', LONGER, init, final);
    NOERRN();
    lastbranch = NULL;
    do
    {                           /* a branch */
        struct subre *branch;
        struct state *left;     /* scaffolding for branch */
        struct state *right;
 
        left = newstate(v->nfa);
        right = newstate(v->nfa);
        NOERRN();
        EMPTYARC(init, left);
        EMPTYARC(right, final);
        NOERRN();
        branch = parsebranch(v, stopper, type, left, right, 0);
        NOERRN();
        if (lastbranch)
            lastbranch->sibling = branch;
        else
            branches->child = branch;
        branches->flags |= UP(branches->flags | branch->flags);
        lastbranch = branch;
    } while (EAT('|'));
    assert(SEE(stopper) || SEE(EOS));
 
    if (!SEE(stopper))
    {
        assert(stopper == ')' && SEE(EOS));
        ERR(REG_EPAREN);
    }
 
    /* optimize out simple cases */
    if (lastbranch == branches->child)
    {                           /* only one branch */
        assert(lastbranch->sibling == NULL);
        freesrnode(v, branches);
        branches = lastbranch;
    }
    else if (!MESSY(branches->flags))
    {                           /* no interesting innards */
        freesubreandsiblings(v, branches->child);
        branches->child = NULL;
        branches->op = '=';
    }
 
    return branches;
}

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.

{
    struct state *lp;           /* left end of current construct */
    int         seencontent;    /* is there anything in this branch yet? */
    struct subre *t;
 
    lp = left;
    seencontent = 0;
    t = subre(v, '=', 0, left, right);  /* op '=' is tentative */
    NOERRN();
    while (!SEE('|') && !SEE(stopper) && !SEE(EOS))
    {
        if (seencontent)
        {                       /* implicit concat operator */
            lp = newstate(v->nfa);
            NOERRN();
            moveins(v->nfa, right, lp);
        }
        seencontent = 1;
 
        /* NB, recursion in parseqatom() may swallow rest of branch */
        t = parseqatom(v, stopper, type, lp, right, t);
        NOERRN();
    }
 
    if (!seencontent)
    {                           /* empty branch */
        if (!partial)
            NOTE(REG_UUNSPEC);
        assert(lp == left);
        EMPTYARC(left, right);
    }
 
    return t;
}

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.

{
    struct state *s;            /* temporaries for new states */
    struct state *s2;
 
#define  ARCV(t, val)    newarc(v->nfa, t, val, lp, rp)
    int         m,
                n;
    struct subre *atom;         /* atom's subtree */
    struct subre *t;
    int         cap;            /* capturing parens? */
    int         latype;         /* lookaround constraint type */
    int         subno;          /* capturing-parens or backref number */
    int         atomtype;
    int         qprefer;        /* quantifier short/long preference */
    int         f;
    struct subre **atomp;       /* where the pointer to atom is */
 
    /* initial bookkeeping */
    atom = NULL;
    assert(lp->nouts == 0);     /* must string new code */
    assert(rp->nins == 0);      /* between lp and rp */
    subno = 0;                  /* just to shut lint up */
 
    /* an atom or constraint... */
    atomtype = v->nexttype;
    switch (atomtype)
    {
            /* first, constraints, which end by returning */
        case '^':
            ARCV('^', 1);
            if (v->cflags & REG_NLANCH)
                ARCV(BEHIND, v->nlcolor);
            NEXT();
            return top;
            break;
        case '$':
            ARCV('$', 1);
            if (v->cflags & REG_NLANCH)
                ARCV(AHEAD, v->nlcolor);
            NEXT();
            return top;
            break;
        case SBEGIN:
            ARCV('^', 1);       /* BOL */
            ARCV('^', 0);       /* or BOS */
            NEXT();
            return top;
            break;
        case SEND:
            ARCV('$', 1);       /* EOL */
            ARCV('$', 0);       /* or EOS */
            NEXT();
            return top;
            break;
        case '<':
            wordchrs(v);
            s = newstate(v->nfa);
            NOERRN();
            nonword(v, BEHIND, lp, s);
            word(v, AHEAD, s, rp);
            NEXT();
            return top;
            break;
        case '>':
            wordchrs(v);
            s = newstate(v->nfa);
            NOERRN();
            word(v, BEHIND, lp, s);
            nonword(v, AHEAD, s, rp);
            NEXT();
            return top;
            break;
        case WBDRY:
            wordchrs(v);
            s = newstate(v->nfa);
            NOERRN();
            nonword(v, BEHIND, lp, s);
            word(v, AHEAD, s, rp);
            s = newstate(v->nfa);
            NOERRN();
            word(v, BEHIND, lp, s);
            nonword(v, AHEAD, s, rp);
            NEXT();
            return top;
            break;
        case NWBDRY:
            wordchrs(v);
            s = newstate(v->nfa);
            NOERRN();
            word(v, BEHIND, lp, s);
            word(v, AHEAD, s, rp);
            s = newstate(v->nfa);
            NOERRN();
            nonword(v, BEHIND, lp, s);
            nonword(v, AHEAD, s, rp);
            NEXT();
            return top;
            break;
        case LACON:             /* lookaround constraint */
            latype = v->nextvalue;
            NEXT();
            s = newstate(v->nfa);
            s2 = newstate(v->nfa);
            NOERRN();
            t = parse(v, ')', LACON, s, s2);
            freesubre(v, t);    /* internal structure irrelevant */
            NOERRN();
            assert(SEE(')'));
            NEXT();
            processlacon(v, s, s2, latype, lp, rp);
            return top;
            break;
            /* then errors, to get them out of the way */
        case '*':
        case '+':
        case '?':
        case '{':
            ERR(REG_BADRPT);
            return top;
            break;
        default:
            ERR(REG_ASSERT);
            return top;
            break;
            /* then plain characters, and minor variants on that theme */
        case ')':               /* unbalanced paren */
            if ((v->cflags & REG_ADVANCED) != REG_EXTENDED)
            {
                ERR(REG_EPAREN);
                return top;
            }
            /* legal in EREs due to specification botch */
            NOTE(REG_UPBOTCH);
            /* fall through into case PLAIN */
            /* FALLTHROUGH */
        case PLAIN:
            onechr(v, v->nextvalue, lp, rp);
            okcolors(v->nfa, v->cm);
            NOERRN();
            NEXT();
            break;
        case '[':
            if (v->nextvalue == 1)
                bracket(v, lp, rp);
            else
                cbracket(v, lp, rp);
            assert(SEE(']') || ISERR());
            NEXT();
            break;
        case CCLASSS:
            charclass(v, (enum char_classes) v->nextvalue, lp, rp);
            okcolors(v->nfa, v->cm);
            NEXT();
            break;
        case CCLASSC:
            charclasscomplement(v, (enum char_classes) v->nextvalue, lp, rp);
            /* charclasscomplement() did okcolors() internally */
            NEXT();
            break;
        case '.':
            rainbow(v->nfa, v->cm, PLAIN,
                    (v->cflags & REG_NLSTOP) ? v->nlcolor : COLORLESS,
                    lp, rp);
            NEXT();
            break;
            /* and finally the ugly stuff */
        case '(':               /* value flags as capturing or non */
            cap = (type == LACON) ? 0 : v->nextvalue;
            if (cap)
            {
                v->nsubexp++;
                subno = v->nsubexp;
                if ((size_t) subno >= v->nsubs)
                    moresubs(v, subno);
            }
            else
                atomtype = PLAIN;   /* something that's not '(' */
            NEXT();
 
            /*
             * Make separate endpoint states to keep this sub-NFA distinct
             * from what surrounds it.  We need to be sure that when we
             * duplicate the sub-NFA for a backref, we get the right
             * states/arcs and no others.  In particular, letting a backref
             * duplicate the sub-NFA from lp to rp would be quite wrong,
             * because we may add quantification superstructure around this
             * atom below.  (Perhaps we could skip the extra states for
             * non-capturing parens, but it seems not worth the trouble.)
             */
            s = newstate(v->nfa);
            s2 = newstate(v->nfa);
            NOERRN();
            /* We may not need these arcs, but keep things connected for now */
            EMPTYARC(lp, s);
            EMPTYARC(s2, rp);
            NOERRN();
            atom = parse(v, ')', type, s, s2);
            assert(SEE(')') || ISERR());
            NEXT();
            NOERRN();
            if (cap)
            {
                if (atom->capno == 0)
                {
                    /* normal case: just mark the atom as capturing */
                    atom->flags |= CAP;
                    atom->capno = subno;
                }
                else
                {
                    /* generate no-op wrapper node to handle "((x))" */
                    t = subre(v, '(', atom->flags | CAP, s, s2);
                    NOERRN();
                    t->capno = subno;
                    t->child = atom;
                    atom = t;
                }
                assert(v->subs[subno] == NULL);
                v->subs[subno] = atom;
            }
            /* postpone everything else pending possible {0} */
            break;
        case BACKREF:           /* the Feature From The Black Lagoon */
            INSIST(type != LACON, REG_ESUBREG);
            subno = v->nextvalue;
            assert(subno > 0);
            INSIST(subno < v->nsubs, REG_ESUBREG);
            NOERRN();
            INSIST(v->subs[subno] != NULL, REG_ESUBREG);
            NOERRN();
            atom = subre(v, 'b', BACKR, lp, rp);
            NOERRN();
            atom->backno = subno;
            v->subs[subno]->flags |= BRUSE;
            EMPTYARC(lp, rp);   /* temporarily, so there's something */
            NEXT();
            break;
    }
 
    /* ...and an atom may be followed by a quantifier */
    switch (v->nexttype)
    {
        case '*':
            m = 0;
            n = DUPINF;
            qprefer = (v->nextvalue) ? LONGER : SHORTER;
            NEXT();
            break;
        case '+':
            m = 1;
            n = DUPINF;
            qprefer = (v->nextvalue) ? LONGER : SHORTER;
            NEXT();
            break;
        case '?':
            m = 0;
            n = 1;
            qprefer = (v->nextvalue) ? LONGER : SHORTER;
            NEXT();
            break;
        case '{':
            NEXT();
            m = scannum(v);
            if (EAT(','))
            {
                if (SEE(DIGIT))
                    n = scannum(v);
                else
                    n = DUPINF;
                if (m > n)
                {
                    ERR(REG_BADBR);
                    return top;
                }
                /* {m,n} exercises preference, even if it's {m,m} */
                qprefer = (v->nextvalue) ? LONGER : SHORTER;
            }
            else
            {
                n = m;
                /* {m} passes operand's preference through */
                qprefer = 0;
            }
            if (!SEE('}'))
            {                   /* catches errors too */
                ERR(REG_BADBR);
                return top;
            }
            NEXT();
            break;
        default:                /* no quantifier */
            m = n = 1;
            qprefer = 0;
            break;
    }
 
    /* annoying special case:  {0} or {0,0} cancels everything */
    if (m == 0 && n == 0)
    {
        /*
         * If we had capturing subexpression(s) within the atom, we don't want
         * to destroy them, because it's legal (if useless) to back-ref them
         * later.  Hence, just unlink the atom from lp/rp and then ignore it.
         */
        if (atom != NULL && (atom->flags & CAP))
        {
            delsub(v->nfa, lp, atom->begin);
            delsub(v->nfa, atom->end, rp);
        }
        else
        {
            /* Otherwise, we can clean up any subre infrastructure we made */
            if (atom != NULL)
                freesubre(v, atom);
            delsub(v->nfa, lp, rp);
        }
        EMPTYARC(lp, rp);
        return top;
    }
 
    /* if not a messy case, avoid hard part */
    assert(!MESSY(top->flags));
    f = top->flags | qprefer | ((atom != NULL) ? atom->flags : 0);
    if (atomtype != '(' && atomtype != BACKREF && !MESSY(UP(f)))
    {
        if (!(m == 1 && n == 1))
            repeat(v, lp, rp, m, n);
        if (atom != NULL)
            freesubre(v, atom);
        top->flags = f;
        return top;
    }
 
    /*
     * hard part:  something messy
     *
     * That is, capturing parens, back reference, short/long clash, or an atom
     * with substructure containing one of those.
     */
 
    /* now we'll need a subre for the contents even if they're boring */
    if (atom == NULL)
    {
        atom = subre(v, '=', 0, lp, rp);
        NOERRN();
    }
 
    /*
     * For what follows, we need the atom to have its own begin/end states
     * that are distinct from lp/rp, so that we can wrap iteration structure
     * around it.  The parenthesized-atom case above already made suitable
     * states (and we don't want to modify a capturing subre, since it's
     * already recorded in v->subs[]).  Otherwise, we need more states.
     */
    if (atom->begin == lp || atom->end == rp)
    {
        s = newstate(v->nfa);
        s2 = newstate(v->nfa);
        NOERRN();
        moveouts(v->nfa, lp, s);
        moveins(v->nfa, rp, s2);
        atom->begin = s;
        atom->end = s2;
    }
    else
    {
        /* The atom's OK, but we must temporarily disconnect it from lp/rp */
        /* (this removes the EMPTY arcs we made above) */
        delsub(v->nfa, lp, atom->begin);
        delsub(v->nfa, atom->end, rp);
    }
 
    /*----------
     * Prepare a general-purpose state skeleton.
     *
     * In the no-backrefs case, we want this:
     *
     * [lp] ---> [s] ---prefix---> ---atom---> ---rest---> [rp]
     *
     * where prefix is some repetitions of atom, and "rest" is the remainder
     * of the branch.  In the general case we need:
     *
     * [lp] ---> [s] ---iterator---> [s2] ---rest---> [rp]
     *
     * where the iterator wraps around the atom.
     *
     * We make the s state here for both cases; s2 is made below if needed
     *----------
     */
    s = newstate(v->nfa);       /* set up starting state */
    NOERRN();
    EMPTYARC(lp, s);
    NOERRN();
 
    /* break remaining subRE into x{...} and what follows */
    t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp);
    NOERRN();
    t->child = atom;
    atomp = &t->child;
 
    /*
     * Here we should recurse to fill t->child->sibling ... but we must
     * postpone that to the end.  One reason is that t->child may be replaced
     * below, and we don't want to worry about its sibling link.
     */
 
    /*
     * Convert top node to a concatenation of the prefix (top->child, covering
     * whatever we parsed previously) and remaining (t).  Note that the prefix
     * could be empty, in which case this concatenation node is unnecessary.
     * To keep things simple, we operate in a general way for now, and get rid
     * of unnecessary subres below.
     */
    assert(top->op == '=' && top->child == NULL);
    top->child = subre(v, '=', top->flags, top->begin, lp);
    NOERRN();
    top->op = '.';
    top->child->sibling = t;
    /* top->flags will get updated later */
 
    /* if it's a backref, now is the time to replicate the subNFA */
    if (atomtype == BACKREF)
    {
        assert(atom->begin->nouts == 1);    /* just the EMPTY */
        delsub(v->nfa, atom->begin, atom->end);
        assert(v->subs[subno] != NULL);
 
        /*
         * And here's why the recursion got postponed: it must wait until the
         * skeleton is filled in, because it may hit a backref that wants to
         * copy the filled-in skeleton.
         */
        dupnfa(v->nfa, v->subs[subno]->begin, v->subs[subno]->end,
               atom->begin, atom->end);
        NOERRN();
 
        /* The backref node's NFA should not enforce any constraints */
        removeconstraints(v->nfa, atom->begin, atom->end);
        NOERRN();
    }
 
    /*
     * It's quantifier time.  If the atom is just a backref, we'll let it deal
     * with quantifiers internally.
     */
    if (atomtype == BACKREF)
    {
        /* special case:  backrefs have internal quantifiers */
        EMPTYARC(s, atom->begin);   /* empty prefix */
        /* just stuff everything into atom */
        repeat(v, atom->begin, atom->end, m, n);
        atom->min = (short) m;
        atom->max = (short) n;
        atom->flags |= COMBINE(qprefer, atom->flags);
        /* rest of branch can be strung starting from atom->end */
        s2 = atom->end;
    }
    else if (m == 1 && n == 1 &&
             (qprefer == 0 ||
              (atom->flags & (LONGER | SHORTER | MIXED)) == 0 ||
              qprefer == (atom->flags & (LONGER | SHORTER | MIXED))))
    {
        /* no/vacuous quantifier:  done */
        EMPTYARC(s, atom->begin);   /* empty prefix */
        /* rest of branch can be strung starting from atom->end */
        s2 = atom->end;
    }
    else if (!(atom->flags & (CAP | BACKR)))
    {
        /*
         * If there's no captures nor backrefs in the atom being repeated, we
         * don't really care where the submatches of the iteration are, so we
         * don't need an iteration node.  Make a plain DFA node instead.
         */
        EMPTYARC(s, atom->begin);   /* empty prefix */
        repeat(v, atom->begin, atom->end, m, n);
        f = COMBINE(qprefer, atom->flags);
        t = subre(v, '=', f, atom->begin, atom->end);
        NOERRN();
        freesubre(v, atom);
        *atomp = t;
        /* rest of branch can be strung starting from t->end */
        s2 = t->end;
    }
    else if (m > 0 && !(atom->flags & BACKR))
    {
        /*
         * If there's no backrefs involved, we can turn x{m,n} into
         * x{m-1,n-1}x, with capturing parens in only the second x.  This is
         * valid because we only care about capturing matches from the final
         * iteration of the quantifier.  It's a win because we can implement
         * the backref-free left side as a plain DFA node, since we don't
         * really care where its submatches are.
         */
        dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin);
        assert(m >= 1 && m != DUPINF && n >= 1);
        repeat(v, s, atom->begin, m - 1, (n == DUPINF) ? n : n - 1);
        f = COMBINE(qprefer, atom->flags);
        t = subre(v, '.', f, s, atom->end); /* prefix and atom */
        NOERRN();
        t->child = subre(v, '=', PREF(f), s, atom->begin);
        NOERRN();
        t->child->sibling = atom;
        *atomp = t;
        /* rest of branch can be strung starting from atom->end */
        s2 = atom->end;
    }
    else
    {
        /* general case: need an iteration node */
        s2 = newstate(v->nfa);
        NOERRN();
        moveouts(v->nfa, atom->end, s2);
        NOERRN();
        dupnfa(v->nfa, atom->begin, atom->end, s, s2);
        repeat(v, s, s2, m, n);
        f = COMBINE(qprefer, atom->flags);
        t = subre(v, '*', f, s, s2);
        NOERRN();
        t->min = (short) m;
        t->max = (short) n;
        t->child = atom;
        *atomp = t;
        /* rest of branch is to be strung from iteration's end state */
    }
 
    /* and finally, look after that postponed recursion */
    t = top->child->sibling;
    if (!(SEE('|') || SEE(stopper) || SEE(EOS)))
    {
        /* parse all the rest of the branch, and insert in t->child->sibling */
        t->child->sibling = parsebranch(v, stopper, type, s2, rp, 1);
        NOERRN();
        assert(SEE('|') || SEE(stopper) || SEE(EOS));
 
        /* here's the promised update of the flags */
        t->flags |= COMBINE(t->flags, t->child->sibling->flags);
        top->flags |= COMBINE(top->flags, t->flags);
 
        /* neither t nor top could be directly marked for capture as yet */
        assert(t->capno == 0);
        assert(top->capno == 0);
 
        /*
         * At this point both top and t are concatenation (op == '.') subres,
         * and we have top->child = prefix of branch, top->child->sibling = t,
         * t->child = messy atom (with quantification superstructure if
         * needed), t->child->sibling = rest of branch.
         *
         * If the messy atom was the first thing in the branch, then
         * top->child is vacuous and we can get rid of one level of
         * concatenation.
         */
        assert(top->child->op == '=');
        if (top->child->begin == top->child->end)
        {
            assert(!MESSY(top->child->flags));
            freesubre(v, top->child);
            top->child = t->child;
            freesrnode(v, t);
        }
 
        /*
         * Otherwise, it's possible that t->child is not messy in itself, but
         * we considered it messy because its greediness conflicts with what
         * preceded it.  Then it could be that the combination of t->child and
         * the rest of the branch is also not messy, in which case we can get
         * rid of the child concatenation by merging t->child and the rest of
         * the branch into one plain DFA node.
         */
        else if (t->child->op == '=' &&
                 t->child->sibling->op == '=' &&
                 !MESSY(UP(t->child->flags | t->child->sibling->flags)))
        {
            t->op = '=';
            t->flags = COMBINE(t->child->flags, t->child->sibling->flags);
            freesubreandsiblings(v, t->child);
            t->child = NULL;
        }
    }
    else
    {
        /*
         * There's nothing left in the branch, so we don't need the second
         * concatenation node 't'.  Just link s2 straight to rp.
         */
        EMPTYARC(s2, rp);
        top->child->sibling = t->child;
        top->flags |= COMBINE(top->flags, top->child->sibling->flags);
        freesrnode(v, t);
 
        /*
         * Again, it could be that top->child is vacuous (if the messy atom
         * was in fact the only thing in the branch).  In that case we need no
         * concatenation at all; just replace top with top->child->sibling.
         */
        assert(top->child->op == '=');
        if (top->child->begin == top->child->end)
        {
            assert(!MESSY(top->child->flags));
            t = top->child->sibling;
            top->child->sibling = NULL;
            freesubre(v, top);
            top = t;
        }
    }
 
    return top;
}

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.

{
    struct vars var;
    struct vars *v = &var;
    struct guts *g;
    int         i;
    size_t      j;
 
#ifdef REG_DEBUG
    FILE       *debug = (flags & REG_PROGRESS) ? stdout : (FILE *) NULL;
#else
    FILE       *debug = (FILE *) NULL;
#endif
 
#define  CNOERR()    { if (ISERR()) return freev(v, v->err); }
 
    /* sanity checks */
 
    if (re == NULL || string == NULL)
        return REG_INVARG;
    if ((flags & REG_QUOTE) &&
        (flags & (REG_ADVANCED | REG_EXPANDED | REG_NEWLINE)))
        return REG_INVARG;
    if (!(flags & REG_EXTENDED) && (flags & REG_ADVF))
        return REG_INVARG;
 
    /* Initialize locale-dependent support */
    pg_set_regex_collation(collation);
 
    /* initial setup (after which freev() is callable) */
    v->re = re;
    v->now = string;
    v->stop = v->now + len;
    v->err = 0;
    v->cflags = flags;
    v->nsubexp = 0;
    v->subs = v->sub10;
    v->nsubs = 10;
    for (j = 0; j < v->nsubs; j++)
        v->subs[j] = NULL;
    v->nfa = NULL;
    v->cm = NULL;
    v->nlcolor = COLORLESS;
    v->wordchrs = NULL;
    v->tree = NULL;
    v->treechain = NULL;
    v->treefree = NULL;
    v->cv = NULL;
    v->cv2 = NULL;
    v->lacons = NULL;
    v->nlacons = 0;
    v->spaceused = 0;
    re->re_magic = REMAGIC;
    re->re_info = 0;            /* bits get set during parse */
    re->re_csize = sizeof(chr);
    re->re_collation = collation;
    re->re_guts = NULL;
    re->re_fns = VS(&functions);
 
    /* more complex setup, malloced things */
    re->re_guts = VS(MALLOC(sizeof(struct guts)));
    if (re->re_guts == NULL)
        return freev(v, REG_ESPACE);
    g = (struct guts *) re->re_guts;
    g->tree = NULL;
    initcm(v, &g->cmap);
    v->cm = &g->cmap;
    g->lacons = NULL;
    g->nlacons = 0;
    ZAPCNFA(g->search);
    v->nfa = newnfa(v, v->cm, (struct nfa *) NULL);
    CNOERR();
    /* set up a reasonably-sized transient cvec for getcvec usage */
    v->cv = newcvec(100, 20);
    if (v->cv == NULL)
        return freev(v, REG_ESPACE);
 
    /* parsing */
    lexstart(v);                /* also handles prefixes */
    if ((v->cflags & REG_NLSTOP) || (v->cflags & REG_NLANCH))
    {
        /* assign newline a unique color */
        v->nlcolor = subcolor(v->cm, newline());
        okcolors(v->nfa, v->cm);
    }
    CNOERR();
    v->tree = parse(v, EOS, PLAIN, v->nfa->init, v->nfa->final);
    assert(SEE(EOS));           /* even if error; ISERR() => SEE(EOS) */
    CNOERR();
    assert(v->tree != NULL);
 
    /* finish setup of nfa and its subre tree */
    specialcolors(v->nfa);
    CNOERR();
#ifdef REG_DEBUG
    if (debug != NULL)
    {
        fprintf(debug, "\n\n\n========= RAW ==========\n");
        dumpnfa(v->nfa, debug);
        dumpst(v->tree, debug, 1);
    }
#endif
    if (v->cflags & REG_NOSUB)
        removecaptures(v, v->tree);
    v->ntree = numst(v->tree, 1);
    markst(v->tree);
    cleanst(v);
#ifdef REG_DEBUG
    if (debug != NULL)
    {
        fprintf(debug, "\n\n\n========= TREE FIXED ==========\n");
        dumpst(v->tree, debug, 1);
    }
#endif
 
    /* build compacted NFAs for tree and lacons */
    re->re_info |= nfatree(v, v->tree, debug);
    CNOERR();
    assert(v->nlacons == 0 || v->lacons != NULL);
    for (i = 1; i < v->nlacons; i++)
    {
        struct subre *lasub = &v->lacons[i];
 
#ifdef REG_DEBUG
        if (debug != NULL)
            fprintf(debug, "\n\n\n========= LA%d ==========\n", i);
#endif
 
        /* Prepend .* to pattern if it's a lookbehind LACON */
        nfanode(v, lasub, !LATYPE_IS_AHEAD(lasub->latype), debug);
    }
    CNOERR();
    if (v->tree->flags & SHORTER)
        NOTE(REG_USHORTEST);
 
    /* build compacted NFAs for tree, lacons, fast search */
#ifdef REG_DEBUG
    if (debug != NULL)
        fprintf(debug, "\n\n\n========= SEARCH ==========\n");
#endif
    /* can sacrifice main NFA now, so use it as work area */
    (DISCARD) optimize(v->nfa, debug);
    CNOERR();
    makesearch(v, v->nfa);
    CNOERR();
    compact(v->nfa, &g->search);
    CNOERR();
 
    /* looks okay, package it up */
    re->re_nsub = v->nsubexp;
    v->re = NULL;               /* freev no longer frees re */
    g->magic = GUTSMAGIC;
    g->cflags = v->cflags;
    g->info = re->re_info;
    g->nsub = re->re_nsub;
    g->tree = v->tree;
    v->tree = NULL;
    g->ntree = v->ntree;
    g->compare = (v->cflags & REG_ICASE) ? casecmp : cmp;
    g->lacons = v->lacons;
    v->lacons = NULL;
    g->nlacons = v->nlacons;
 
#ifdef REG_DEBUG
    if (flags & REG_DUMP)
    {
        dump(re, stdout);
        fflush(stdout);
    }
#endif
 
    assert(v->err == 0);
    return freev(v, 0);
}

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.

{
    struct state *s1;
    int         n;
 
    /*
     * Check for lookaround RE consisting of a single plain color arc (or set
     * of arcs); this would typically be a simple chr or a bracket expression.
     */
    s1 = single_color_transition(begin, end);
    switch (latype)
    {
        case LATYPE_AHEAD_POS:
            /* If lookahead RE is just colorset C, convert to AHEAD(C) */
            if (s1 != NULL)
            {
                cloneouts(v->nfa, s1, lp, rp, AHEAD);
                return;
            }
            break;
        case LATYPE_AHEAD_NEG:
            /* If lookahead RE is just colorset C, convert to AHEAD(^C)|$ */
            if (s1 != NULL)
            {
                colorcomplement(v->nfa, v->cm, AHEAD, s1, lp, rp);
                newarc(v->nfa, '$', 1, lp, rp);
                newarc(v->nfa, '$', 0, lp, rp);
                return;
            }
            break;
        case LATYPE_BEHIND_POS:
            /* If lookbehind RE is just colorset C, convert to BEHIND(C) */
            if (s1 != NULL)
            {
                cloneouts(v->nfa, s1, lp, rp, BEHIND);
                return;
            }
            break;
        case LATYPE_BEHIND_NEG:
            /* If lookbehind RE is just colorset C, convert to BEHIND(^C)|^ */
            if (s1 != NULL)
            {
                colorcomplement(v->nfa, v->cm, BEHIND, s1, lp, rp);
                newarc(v->nfa, '^', 1, lp, rp);
                newarc(v->nfa, '^', 0, lp, rp);
                return;
            }
            break;
        default:
            assert(NOTREACHED);
    }
 
    /* General case: we need a LACON subre and arc */
    n = newlacon(v, begin, end, latype);
    newarc(v->nfa, LACON, n, lp, rp);
}

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.

{
    struct subre *t2;
 
    assert(t != NULL);
 
    /*
     * If this isn't itself a backref target, clear capno and tentatively
     * clear CAP flag.
     */
    if (!(t->flags & BRUSE))
    {
        t->capno = 0;
        t->flags &= ~CAP;
    }
 
    /* Now recurse to children */
    for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
    {
        removecaptures(v, t2);
        /* Propagate child CAP flag back up, if it's still set */
        if (t2->flags & CAP)
            t->flags |= CAP;
    }
 
    /*
     * If t now contains neither captures nor backrefs, there's no longer any
     * need to care where its sub-match boundaries are, so we can reduce it to
     * a simple DFA node.  (Note in particular that MIXED child greediness is
     * not a hindrance here, so we don't use the MESSY() macro.)
     */
    if ((t->flags & (CAP | BACKR)) == 0)
    {
        if (t->child)
            freesubreandsiblings(v, t->child);
        t->child = NULL;
        t->op = '=';
        t->flags &= ~MIXED;
    }
}

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.

{
#define  SOME    2
#define  INF     3
#define  PAIR(x, y)  ((x)*4 + (y))
#define  REDUCE(x)   ( ((x) == DUPINF) ? INF : (((x) > 1) ? SOME : (x)) )
    const int   rm = REDUCE(m);
    const int   rn = REDUCE(n);
    struct state *s;
    struct state *s2;
 
    switch (PAIR(rm, rn))
    {
        case PAIR(0, 0):        /* empty string */
            delsub(v->nfa, lp, rp);
            EMPTYARC(lp, rp);
            break;
        case PAIR(0, 1):        /* do as x| */
            EMPTYARC(lp, rp);
            break;
        case PAIR(0, SOME):     /* do as x{1,n}| */
            repeat(v, lp, rp, 1, n);
            NOERR();
            EMPTYARC(lp, rp);
            break;
        case PAIR(0, INF):      /* loop x around */
            s = newstate(v->nfa);
            NOERR();
            moveouts(v->nfa, lp, s);
            moveins(v->nfa, rp, s);
            EMPTYARC(lp, s);
            EMPTYARC(s, rp);
            break;
        case PAIR(1, 1):        /* no action required */
            break;
        case PAIR(1, SOME):     /* do as x{0,n-1}x = (x{1,n-1}|)x */
            s = newstate(v->nfa);
            NOERR();
            moveouts(v->nfa, lp, s);
            dupnfa(v->nfa, s, rp, lp, s);
            NOERR();
            repeat(v, lp, s, 1, n - 1);
            NOERR();
            EMPTYARC(lp, s);
            break;
        case PAIR(1, INF):      /* add loopback arc */
            s = newstate(v->nfa);
            s2 = newstate(v->nfa);
            NOERR();
            moveouts(v->nfa, lp, s);
            moveins(v->nfa, rp, s2);
            EMPTYARC(lp, s);
            EMPTYARC(s2, rp);
            EMPTYARC(s2, s);
            break;
        case PAIR(SOME, SOME):  /* do as x{m-1,n-1}x */
            s = newstate(v->nfa);
            NOERR();
            moveouts(v->nfa, lp, s);
            dupnfa(v->nfa, s, rp, lp, s);
            NOERR();
            repeat(v, lp, s, m - 1, n - 1);
            break;
        case PAIR(SOME, INF):   /* do as x{m-1,}x */
            s = newstate(v->nfa);
            NOERR();
            moveouts(v->nfa, lp, s);
            dupnfa(v->nfa, s, rp, lp, s);
            NOERR();
            repeat(v, lp, s, m - 1, n);
            break;
        default:
            ERR(REG_ASSERT);
            break;
    }
}

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.

{
    struct guts *g;
 
    if (re == NULL || re->re_magic != REMAGIC)
        return;
 
    re->re_magic = 0;           /* invalidate RE */
    g = (struct guts *) re->re_guts;
    re->re_guts = NULL;
    re->re_fns = NULL;
    if (g != NULL)
    {
        g->magic = 0;
        freecm(&g->cmap);
        if (g->tree != NULL)
            freesubre((struct vars *) NULL, g->tree);
        if (g->lacons != NULL)
            freelacons(g->lacons, g->nlacons);
        if (!NULLCNFA(g->search))
            freecnfa(&g->search);
        FREE(g);
    }
}

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.

{
    return stack_is_too_deep();
}

References stack_is_too_deep().

◆ scannum()

static int scannum ( struct vars * v )

static

Definition at line 1555 of file regcomp.c.

{
    int         n = 0;
 
    while (SEE(DIGIT) && n < DUPMAX)
    {
        n = n * 10 + v->nextvalue;
        NEXT();
    }
    if (SEE(DIGIT) || n > DUPMAX)
    {
        ERR(REG_BADBR);
        return 0;
    }
    return n;
}

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.

{
    const chr  *endp;
 
    assert(SEE(COLLEL) || SEE(ECLASS) || SEE(CCLASS));
    NEXT();
 
    endp = v->now;
    while (SEE(PLAIN))
    {
        endp = v->now;
        NEXT();
    }
 
    assert(SEE(END) || ISERR());
    NEXT();
 
    return endp;
}

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

Referenced by brackpart(), charclass(), charclasscomplement(), onechr(), and wordchrs().

◆ 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.

{
    struct subre *ret = v->treefree;
 
    /*
     * Checking for stack overflow here is sufficient to protect parse() and
     * its recursive subroutines.
     */
    if (STACK_TOO_DEEP(v->re))
    {
        ERR(REG_ETOOBIG);
        return NULL;
    }
 
    if (ret != NULL)
        v->treefree = ret->child;
    else
    {
        ret = (struct subre *) MALLOC(sizeof(struct subre));
        if (ret == NULL)
        {
            ERR(REG_ESPACE);
            return NULL;
        }
        ret->chain = v->treechain;
        v->treechain = ret;
    }
 
    assert(strchr("=b|.*(", op) != NULL);
 
    ret->op = op;
    ret->flags = flags;
    ret->latype = (char) -1;
    ret->id = 0;                /* will be assigned later */
    ret->capno = 0;
    ret->backno = 0;
    ret->min = ret->max = 1;
    ret->child = NULL;
    ret->sibling = NULL;
    ret->begin = begin;
    ret->end = end;
    ZAPCNFA(ret->cnfa);
 
    return ret;
}

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()

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

static

Definition at line 1476 of file regcomp.c.

{
    assert(dir == AHEAD || dir == BEHIND);
    cloneouts(v->nfa, v->wordchrs, lp, rp, dir);
    /* (no need for special attention to \n) */
}

References AHEAD, assert, BEHIND, cloneouts(), vars::nfa, and vars::wordchrs.

Referenced by _metaphone(), addNorm(), AddStem(), addToResult(), byword(), CheckAffix(), CheckCompoundAffixes(), ciprefix(), cmpspell(), compareWORD(), daitch_mokotoff_coding(), dxsyn_lexize(), FindAffixes(), FindWord(), hlfinditem(), itsabbr(), Lookahead(), NIAddSpell(), NINormalizeWord(), NormalizeSubWord(), parseqatom(), pg_leftmost_one_pos32(), pg_leftmost_one_pos64(), pg_popcount32(), pg_popcount32_slow(), pg_popcount64(), pg_popcount64_slow(), pg_rightmost_one_pos32(), pg_rightmost_one_pos64(), pg_rotate_left32(), pg_rotate_right32(), plpgsql_parse_word(), SplitToVariants(), TidStoreSetBlockOffsets(), and unicode_to_utf8word().

◆ wordchrs()

static void wordchrs ( struct vars * v )

static

Definition at line 1993 of file regcomp.c.

{
    struct state *cstate;
    struct cvec *cv;
 
    if (v->wordchrs != NULL)
        return;                 /* done already */
 
    /* make dummy state to hang the cache arcs on */
    cstate = newstate(v->nfa);
    NOERR();
 
    /* obtain possibly-cached cvec for \w characters */
    NOTE(REG_ULOCALE);
    cv = cclasscvec(v, CC_WORD, (v->cflags & REG_ICASE));
    NOERR();
 
    /* build the arcs; this may cause color splitting */
    subcolorcvec(v, cv, cstate, cstate);
    NOERR();
 
    /* close new open subcolors to ensure the cache entry is self-contained */
    okcolors(v->nfa, v->cm);
    NOERR();
 
    /* success! save the cache pointer */
    v->wordchrs = cstate;
}

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

const struct fns functions

static

Initial value:

= {
    rfree,                      
    rstacktoodeep               
}

Definition at line 358 of file regcomp.c.

Referenced by _outRangeTblEntry(), _readRangeTblEntry(), btadjustmembers(), create_functionscan_plan(), ExplainNode(), ginadjustmembers(), gistadjustmembers(), hashadjustmembers(), make_functionscan(), pg_regcomp(), and spgadjustmembers().

Data Structures

Macros

Functions

Variables

Macro Definition Documentation

◆ AHEAD

◆ ARCV

◆ BACKREF

◆ BEHIND

◆ CANTMATCH

◆ CCLASS

◆ CCLASSC

◆ CCLASSS

◆ CNOERR

◆ COLLEL

◆ COLORED

◆ COMPATIBLE

◆ DIGIT

◆ EAT

◆ ECLASS

◆ EMPTY

◆ EMPTYARC

◆ END

◆ EOS

◆ ERR

◆ INCOMPATIBLE

◆ INF

◆ INSIST

◆ ISERR

◆ LACON

◆ NEXT

◆ NOERR

◆ NOERRN

◆ NOERRZ

◆ NOTE

◆ NWBDRY

◆ PAIR

◆ PLAIN

◆ RANGE

◆ REDUCE

◆ REPLACEARC

◆ SATISFIED

◆ SBEGIN

◆ SEE

◆ SEND

◆ SOME

◆ VERR

◆ VISERR

◆ WBDRY

Function Documentation

◆ addchr()

◆ addrange()

◆ allcases()

◆ allocarc()

◆ analyze()

◆ before()

◆ bracket()

◆ brackpart()

◆ breakconstraintloop()

◆ brenext()

◆ carc_cmp()

◆ carcsort()

◆ casecmp()

◆ cbracket()

◆ cclass_column_index()

◆ cclasscvec()

◆ changearcsource()

◆ changearctarget()

◆ charclass()

◆ charclasscomplement()

◆ check_in_colors_match()

◆ check_out_colors_match()

◆ checkmatchall()

◆ checkmatchall_recurse()

◆ chrnamed()

◆ cleanst()

◆ cleanup()

◆ clearcvec()

◆ cleartraverse()

◆ cloneouts()