diff options
Diffstat (limited to 'generic/regcomp.c')
| -rw-r--r-- | generic/regcomp.c | 3572 |
1 files changed, 1781 insertions, 1791 deletions
diff --git a/generic/regcomp.c b/generic/regcomp.c index 66cdf33..6dea04b 100644 --- a/generic/regcomp.c +++ b/generic/regcomp.c @@ -2,24 +2,24 @@ * re_*comp and friends - compile REs * This file #includes several others (see the bottom). * - * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved. - * + * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved. + * * Development of this software was funded, in part, by Cray Research Inc., * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics - * Corporation, none of whom are responsible for the results. The author - * thanks all of them. - * + * Corporation, none of whom are responsible for the results. The author + * thanks all of them. + * * Redistribution and use in source and binary forms -- with or without * modification -- are permitted for any purpose, provided that * redistributions in source form retain this entire copyright notice and * indicate the origin and nature of any modifications. - * - * I'd appreciate being given credit for this package in the documentation - * of software which uses it, but that is not a requirement. - * + * + * I'd appreciate being given credit for this package in the documentation of + * software which uses it, but that is not a requirement. + * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY - * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL + * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; @@ -38,203 +38,189 @@ /* =====^!^===== begin forwards =====^!^===== */ /* automatically gathered by fwd; do not hand-edit */ /* === regcomp.c === */ -int compile _ANSI_ARGS_((regex_t *, CONST chr *, size_t, int)); -static VOID moresubs _ANSI_ARGS_((struct vars *, int)); -static int freev _ANSI_ARGS_((struct vars *, int)); -static VOID makesearch _ANSI_ARGS_((struct vars *, struct nfa *)); -static struct subre *parse _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *)); -static struct subre *parsebranch _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *, int)); -static VOID parseqatom _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *, struct subre *)); -static VOID nonword _ANSI_ARGS_((struct vars *, int, struct state *, struct state *)); -static VOID word _ANSI_ARGS_((struct vars *, int, struct state *, struct state *)); -static int scannum _ANSI_ARGS_((struct vars *)); -static VOID repeat _ANSI_ARGS_((struct vars *, struct state *, struct state *, int, int)); -static VOID bracket _ANSI_ARGS_((struct vars *, struct state *, struct state *)); -static VOID cbracket _ANSI_ARGS_((struct vars *, struct state *, struct state *)); -static VOID brackpart _ANSI_ARGS_((struct vars *, struct state *, struct state *)); -static chr *scanplain _ANSI_ARGS_((struct vars *)); -static VOID leaders _ANSI_ARGS_((struct vars *, struct cvec *)); -static VOID onechr _ANSI_ARGS_((struct vars *, pchr, struct state *, struct state *)); -static VOID dovec _ANSI_ARGS_((struct vars *, struct cvec *, struct state *, struct state *)); -static celt nextleader _ANSI_ARGS_((struct vars *, pchr, pchr)); -static VOID wordchrs _ANSI_ARGS_((struct vars *)); -static struct subre *subre _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *)); -static VOID freesubre _ANSI_ARGS_((struct vars *, struct subre *)); -static VOID freesrnode _ANSI_ARGS_((struct vars *, struct subre *)); -static VOID optst _ANSI_ARGS_((struct vars *, struct subre *)); -static int numst _ANSI_ARGS_((struct subre *, int)); -static VOID markst _ANSI_ARGS_((struct subre *)); -static VOID cleanst _ANSI_ARGS_((struct vars *)); -static long nfatree _ANSI_ARGS_((struct vars *, struct subre *, FILE *)); -static long nfanode _ANSI_ARGS_((struct vars *, struct subre *, FILE *)); -static int newlacon _ANSI_ARGS_((struct vars *, struct state *, struct state *, int)); -static VOID freelacons _ANSI_ARGS_((struct subre *, int)); -static VOID rfree _ANSI_ARGS_((regex_t *)); -static VOID dump _ANSI_ARGS_((regex_t *, FILE *)); -static VOID dumpst _ANSI_ARGS_((struct subre *, FILE *, int)); -static VOID stdump _ANSI_ARGS_((struct subre *, FILE *, int)); -static char *stid _ANSI_ARGS_((struct subre *, char *, size_t)); +int compile(regex_t *, const chr *, size_t, int); +static void moresubs(struct vars *, int); +static int freev(struct vars *, int); +static void makesearch(struct vars *, struct nfa *); +static struct subre *parse(struct vars *, int, int, struct state *, struct state *); +static struct subre *parsebranch(struct vars *, int, int, struct state *, struct state *, int); +static void parseqatom(struct vars *, int, int, struct state *, struct state *, struct subre *); +static void nonword(struct vars *, int, struct state *, struct state *); +static void word(struct vars *, int, struct state *, struct state *); +static int scannum(struct vars *); +static void repeat(struct vars *, struct state *, struct state *, int, int); +static void bracket(struct vars *, struct state *, struct state *); +static void cbracket(struct vars *, struct state *, struct state *); +static void brackpart(struct vars *, struct state *, struct state *); +static const chr *scanplain(struct vars *); +static void onechr(struct vars *, pchr, struct state *, struct state *); +static void dovec(struct vars *, struct cvec *, struct state *, struct state *); +static void wordchrs(struct vars *); +static struct subre *subre(struct vars *, int, int, struct state *, struct state *); +static void freesubre(struct vars *, struct subre *); +static void freesrnode(struct vars *, struct subre *); +static void optst(struct vars *, struct subre *); +static int numst(struct subre *, int); +static void markst(struct subre *); +static void cleanst(struct vars *); +static long nfatree(struct vars *, struct subre *, FILE *); +static long nfanode(struct vars *, struct subre *, FILE *); +static int newlacon(struct vars *, struct state *, struct state *, int); +static void freelacons(struct subre *, int); +static void rfree(regex_t *); +static void dump(regex_t *, FILE *); +static void dumpst(struct subre *, FILE *, int); +static void stdump(struct subre *, FILE *, int); +static const char *stid(struct subre *, char *, size_t); /* === regc_lex.c === */ -static VOID lexstart _ANSI_ARGS_((struct vars *)); -static VOID prefixes _ANSI_ARGS_((struct vars *)); -static VOID lexnest _ANSI_ARGS_((struct vars *, chr *, chr *)); -static VOID lexword _ANSI_ARGS_((struct vars *)); -static int next _ANSI_ARGS_((struct vars *)); -static int lexescape _ANSI_ARGS_((struct vars *)); -static chr lexdigits _ANSI_ARGS_((struct vars *, int, int, int)); -static int brenext _ANSI_ARGS_((struct vars *, pchr)); -static VOID skip _ANSI_ARGS_((struct vars *)); -static chr newline _ANSI_ARGS_((NOPARMS)); +static void lexstart(struct vars *); +static void prefixes(struct vars *); +static void lexnest(struct vars *, const chr *, const chr *); +static void lexword(struct vars *); +static int next(struct vars *); +static int lexescape(struct vars *); +static chr lexdigits(struct vars *, int, int, int); +static int brenext(struct vars *, pchr); +static void skip(struct vars *); +static chr newline(NOPARMS); #ifdef REG_DEBUG -static chr *ch _ANSI_ARGS_((NOPARMS)); +static const chr *ch(NOPARMS); #endif -static chr chrnamed _ANSI_ARGS_((struct vars *, chr *, chr *, pchr)); +static chr chrnamed(struct vars *, const chr *, const chr *, pchr); /* === regc_color.c === */ -static VOID initcm _ANSI_ARGS_((struct vars *, struct colormap *)); -static VOID freecm _ANSI_ARGS_((struct colormap *)); -static VOID cmtreefree _ANSI_ARGS_((struct colormap *, union tree *, int)); -static color setcolor _ANSI_ARGS_((struct colormap *, pchr, pcolor)); -static color maxcolor _ANSI_ARGS_((struct colormap *)); -static color newcolor _ANSI_ARGS_((struct colormap *)); -static VOID freecolor _ANSI_ARGS_((struct colormap *, pcolor)); -static color pseudocolor _ANSI_ARGS_((struct colormap *)); -static color subcolor _ANSI_ARGS_((struct colormap *, pchr c)); -static color newsub _ANSI_ARGS_((struct colormap *, pcolor)); -static VOID subrange _ANSI_ARGS_((struct vars *, pchr, pchr, struct state *, struct state *)); -static VOID subblock _ANSI_ARGS_((struct vars *, pchr, struct state *, struct state *)); -static VOID okcolors _ANSI_ARGS_((struct nfa *, struct colormap *)); -static VOID colorchain _ANSI_ARGS_((struct colormap *, struct arc *)); -static VOID uncolorchain _ANSI_ARGS_((struct colormap *, struct arc *)); -static int singleton _ANSI_ARGS_((struct colormap *, pchr c)); -static VOID rainbow _ANSI_ARGS_((struct nfa *, struct colormap *, int, pcolor, struct state *, struct state *)); -static VOID colorcomplement _ANSI_ARGS_((struct nfa *, struct colormap *, int, struct state *, struct state *, struct state *)); +static void initcm(struct vars *, struct colormap *); +static void freecm(struct colormap *); +static void cmtreefree(struct colormap *, union tree *, int); +static color setcolor(struct colormap *, pchr, pcolor); +static color maxcolor(struct colormap *); +static color newcolor(struct colormap *); +static void freecolor(struct colormap *, pcolor); +static color pseudocolor(struct colormap *); +static color subcolor(struct colormap *, pchr c); +static color newsub(struct colormap *, pcolor); +static void subrange(struct vars *, pchr, pchr, struct state *, struct state *); +static void subblock(struct vars *, pchr, struct state *, struct state *); +static void okcolors(struct nfa *, struct colormap *); +static void colorchain(struct colormap *, struct arc *); +static void uncolorchain(struct colormap *, struct arc *); +static void rainbow(struct nfa *, struct colormap *, int, pcolor, struct state *, struct state *); +static void colorcomplement(struct nfa *, struct colormap *, int, struct state *, struct state *, struct state *); #ifdef REG_DEBUG -static VOID dumpcolors _ANSI_ARGS_((struct colormap *, FILE *)); -static VOID fillcheck _ANSI_ARGS_((struct colormap *, union tree *, int, FILE *)); -static VOID dumpchr _ANSI_ARGS_((pchr, FILE *)); +static void dumpcolors(struct colormap *, FILE *); +static void fillcheck(struct colormap *, union tree *, int, FILE *); +static void dumpchr(pchr, FILE *); #endif /* === regc_nfa.c === */ -static struct nfa *newnfa _ANSI_ARGS_((struct vars *, struct colormap *, struct nfa *)); -static VOID freenfa _ANSI_ARGS_((struct nfa *)); -static struct state *newstate _ANSI_ARGS_((struct nfa *)); -static struct state *newfstate _ANSI_ARGS_((struct nfa *, int flag)); -static VOID dropstate _ANSI_ARGS_((struct nfa *, struct state *)); -static VOID freestate _ANSI_ARGS_((struct nfa *, struct state *)); -static VOID destroystate _ANSI_ARGS_((struct nfa *, struct state *)); -static VOID newarc _ANSI_ARGS_((struct nfa *, int, pcolor, struct state *, struct state *)); -static struct arc *allocarc _ANSI_ARGS_((struct nfa *, struct state *)); -static VOID freearc _ANSI_ARGS_((struct nfa *, struct arc *)); -static struct arc *findarc _ANSI_ARGS_((struct state *, int, pcolor)); -static VOID cparc _ANSI_ARGS_((struct nfa *, struct arc *, struct state *, struct state *)); -static VOID moveins _ANSI_ARGS_((struct nfa *, struct state *, struct state *)); -static VOID copyins _ANSI_ARGS_((struct nfa *, struct state *, struct state *)); -static VOID moveouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *)); -static VOID copyouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *)); -static VOID cloneouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *, int)); -static VOID delsub _ANSI_ARGS_((struct nfa *, struct state *, struct state *)); -static VOID deltraverse _ANSI_ARGS_((struct nfa *, struct state *, struct state *)); -static VOID dupnfa _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *, struct state *)); -static VOID duptraverse _ANSI_ARGS_((struct nfa *, struct state *, struct state *)); -static VOID cleartraverse _ANSI_ARGS_((struct nfa *, struct state *)); -static VOID specialcolors _ANSI_ARGS_((struct nfa *)); -static long optimize _ANSI_ARGS_((struct nfa *, FILE *)); -static VOID pullback _ANSI_ARGS_((struct nfa *, FILE *)); -static int pull _ANSI_ARGS_((struct nfa *, struct arc *)); -static VOID pushfwd _ANSI_ARGS_((struct nfa *, FILE *)); -static int push _ANSI_ARGS_((struct nfa *, struct arc *)); +static struct nfa *newnfa(struct vars *, struct colormap *, struct nfa *); +static void freenfa(struct nfa *); +static struct state *newstate(struct nfa *); +static struct state *newfstate(struct nfa *, int flag); +static void dropstate(struct nfa *, struct state *); +static void freestate(struct nfa *, struct state *); +static void destroystate(struct nfa *, struct state *); +static void newarc(struct nfa *, int, pcolor, struct state *, struct state *); +static struct arc *allocarc(struct nfa *, struct state *); +static void freearc(struct nfa *, struct arc *); +static struct arc *findarc(struct state *, int, pcolor); +static void cparc(struct nfa *, struct arc *, struct state *, struct state *); +static void moveins(struct nfa *, struct state *, struct state *); +static void copyins(struct nfa *, struct state *, struct state *); +static void moveouts(struct nfa *, struct state *, struct state *); +static void copyouts(struct nfa *, struct state *, struct state *); +static void cloneouts(struct nfa *, struct state *, struct state *, struct state *, int); +static void delsub(struct nfa *, struct state *, struct state *); +static void deltraverse(struct nfa *, struct state *, struct state *); +static void dupnfa(struct nfa *, struct state *, struct state *, struct state *, struct state *); +static void duptraverse(struct nfa *, struct state *, struct state *); +static void cleartraverse(struct nfa *, struct state *); +static void specialcolors(struct nfa *); +static long optimize(struct nfa *, FILE *); +static void pullback(struct nfa *, FILE *); +static int pull(struct nfa *, struct arc *); +static void pushfwd(struct nfa *, FILE *); +static int push(struct nfa *, struct arc *); #define INCOMPATIBLE 1 /* destroys arc */ #define SATISFIED 2 /* constraint satisfied */ #define COMPATIBLE 3 /* compatible but not satisfied yet */ -static int combine _ANSI_ARGS_((struct arc *, struct arc *)); -static VOID fixempties _ANSI_ARGS_((struct nfa *, FILE *)); -static int unempty _ANSI_ARGS_((struct nfa *, struct arc *)); -static VOID cleanup _ANSI_ARGS_((struct nfa *)); -static VOID markreachable _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *)); -static VOID markcanreach _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *)); -static long analyze _ANSI_ARGS_((struct nfa *)); -static VOID compact _ANSI_ARGS_((struct nfa *, struct cnfa *)); -static VOID carcsort _ANSI_ARGS_((struct carc *, struct carc *)); -static VOID freecnfa _ANSI_ARGS_((struct cnfa *)); -static VOID dumpnfa _ANSI_ARGS_((struct nfa *, FILE *)); +static int combine(struct arc *, struct arc *); +static void fixempties(struct nfa *, FILE *); +static int unempty(struct nfa *, struct arc *); +static void cleanup(struct nfa *); +static void markreachable(struct nfa *, struct state *, struct state *, struct state *); +static void markcanreach(struct nfa *, struct state *, struct state *, struct state *); +static long analyze(struct nfa *); +static void compact(struct nfa *, struct cnfa *); +static void carcsort(struct carc *, struct carc *); +static void freecnfa(struct cnfa *); +static void dumpnfa(struct nfa *, FILE *); #ifdef REG_DEBUG -static VOID dumpstate _ANSI_ARGS_((struct state *, FILE *)); -static VOID dumparcs _ANSI_ARGS_((struct state *, FILE *)); -static int dumprarcs _ANSI_ARGS_((struct arc *, struct state *, FILE *, int)); -static VOID dumparc _ANSI_ARGS_((struct arc *, struct state *, FILE *)); +static void dumpstate(struct state *, FILE *); +static void dumparcs(struct state *, FILE *); +static int dumprarcs(struct arc *, struct state *, FILE *, int); +static void dumparc(struct arc *, struct state *, FILE *); #endif -static VOID dumpcnfa _ANSI_ARGS_((struct cnfa *, FILE *)); +static void dumpcnfa(struct cnfa *, FILE *); #ifdef REG_DEBUG -static VOID dumpcstate _ANSI_ARGS_((int, struct carc *, struct cnfa *, FILE *)); +static void dumpcstate(int, struct carc *, struct cnfa *, FILE *); #endif /* === regc_cvec.c === */ -static struct cvec *newcvec _ANSI_ARGS_((int, int, int)); -static struct cvec *clearcvec _ANSI_ARGS_((struct cvec *)); -static VOID addchr _ANSI_ARGS_((struct cvec *, pchr)); -static VOID addrange _ANSI_ARGS_((struct cvec *, pchr, pchr)); -static VOID addmcce _ANSI_ARGS_((struct cvec *, chr *, chr *)); -static int haschr _ANSI_ARGS_((struct cvec *, pchr)); -static struct cvec *getcvec _ANSI_ARGS_((struct vars *, int, int, int)); -static VOID freecvec _ANSI_ARGS_((struct cvec *)); +static struct cvec *clearcvec(struct cvec *); +static void addchr(struct cvec *, pchr); +static void addrange(struct cvec *, pchr, pchr); +static struct cvec *newcvec(int, int); +static struct cvec *getcvec(struct vars *, int, int); +static void freecvec(struct cvec *); /* === regc_locale.c === */ -static int nmcces _ANSI_ARGS_((struct vars *)); -static int nleaders _ANSI_ARGS_((struct vars *)); -static struct cvec *allmcces _ANSI_ARGS_((struct vars *, struct cvec *)); -static celt element _ANSI_ARGS_((struct vars *, CONST chr *, CONST chr *)); -static struct cvec *range _ANSI_ARGS_((struct vars *, celt, celt, int)); -static int before _ANSI_ARGS_((celt, celt)); -static struct cvec *eclass _ANSI_ARGS_((struct vars *, celt, int)); -static struct cvec *cclass _ANSI_ARGS_((struct vars *, CONST chr *, CONST chr *, int)); -static struct cvec *allcases _ANSI_ARGS_((struct vars *, pchr)); -static int cmp _ANSI_ARGS_((CONST chr *, CONST chr *, size_t)); -static int casecmp _ANSI_ARGS_((CONST chr *, CONST chr *, size_t)); +static celt element(struct vars *, const chr *, const chr *); +static struct cvec *range(struct vars *, celt, celt, int); +static int before(celt, celt); +static struct cvec *eclass(struct vars *, celt, int); +static struct cvec *cclass(struct vars *, const chr *, const chr *, int); +static struct cvec *allcases(struct vars *, pchr); +static int cmp(const chr *, const chr *, size_t); +static int casecmp(const chr *, const chr *, size_t); /* automatically gathered by fwd; do not hand-edit */ /* =====^!^===== end forwards =====^!^===== */ - - - + /* internal variables, bundled for easy passing around */ struct vars { - regex_t *re; - chr *now; /* scan pointer into string */ - chr *stop; /* end of string */ - chr *savenow; /* saved now and stop for "subroutine call" */ - chr *savestop; - int err; /* error code (0 if none) */ - int cflags; /* copy of compile flags */ - int lasttype; /* type of previous token */ - int nexttype; /* type of next token */ - chr nextvalue; /* value (if any) of next token */ - int lexcon; /* lexical context type (see lex.c) */ - int nsubexp; /* subexpression count */ - struct subre **subs; /* subRE pointer vector */ - size_t nsubs; /* length of vector */ - struct subre *sub10[10]; /* initial vector, enough for most */ - struct nfa *nfa; /* the NFA */ - struct colormap *cm; /* character color map */ - color nlcolor; /* color of newline */ - struct state *wordchrs; /* state in nfa holding word-char outarcs */ - struct subre *tree; /* subexpression tree */ - struct subre *treechain; /* all tree nodes allocated */ - struct subre *treefree; /* any free tree nodes */ - int ntree; /* number of tree nodes */ - struct cvec *cv; /* interface cvec */ - struct cvec *cv2; /* utility cvec */ - struct cvec *mcces; /* collating-element information */ -# define ISCELEADER(v,c) (v->mcces != NULL && haschr(v->mcces, (c))) - struct state *mccepbegin; /* in nfa, start of MCCE prototypes */ - struct state *mccepend; /* in nfa, end of MCCE prototypes */ - struct subre *lacons; /* lookahead-constraint vector */ - int nlacons; /* size of lacons */ + regex_t *re; + const chr *now; /* scan pointer into string */ + const chr *stop; /* end of string */ + const chr *savenow; /* saved now and stop for "subroutine call" */ + const chr *savestop; + int err; /* error code (0 if none) */ + int cflags; /* copy of compile flags */ + int lasttype; /* type of previous token */ + int nexttype; /* type of next token */ + chr nextvalue; /* value (if any) of next token */ + int lexcon; /* lexical context type (see lex.c) */ + int nsubexp; /* subexpression count */ + struct subre **subs; /* subRE pointer vector */ + size_t nsubs; /* length of vector */ + struct subre *sub10[10]; /* initial vector, enough for most */ + struct nfa *nfa; /* the NFA */ + struct colormap *cm; /* character color map */ + color nlcolor; /* color of newline */ + struct state *wordchrs; /* state in nfa holding word-char outarcs */ + struct subre *tree; /* subexpression tree */ + struct subre *treechain; /* all tree nodes allocated */ + struct subre *treefree; /* any free tree nodes */ + int ntree; /* number of tree nodes */ + struct cvec *cv; /* interface cvec */ + struct cvec *cv2; /* utility cvec */ + struct subre *lacons; /* lookahead-constraint vector */ + int nlacons; /* size of lacons */ }; /* parsing macros; most know that `v' is the struct vars pointer */ #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 VISERR(vv) ((vv)->err != 0)/* have we seen an error yet? */ #define ISERR() VISERR(v) -#define VERR(vv,e) ((vv)->nexttype = EOS, ((vv)->err) ? (vv)->err :\ - ((vv)->err = (e))) +#define VERR(vv,e) \ + ((vv)->nexttype = EOS, ((vv)->err) ? (vv)->err : ((vv)->err = (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 */ @@ -264,395 +250,459 @@ struct vars { #define PREFER 'P' /* length preference */ /* is an arc colored, and hence on a color chain? */ -#define COLORED(a) ((a)->type == PLAIN || (a)->type == AHEAD || \ - (a)->type == BEHIND) - - +#define COLORED(a) \ + ((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND) /* static function list */ static struct fns functions = { - rfree, /* regfree insides */ + rfree, /* regfree insides */ }; - - - + /* - compile - compile regular expression - ^ int compile(regex_t *, CONST chr *, size_t, int); + ^ int compile(regex_t *, const chr *, size_t, int); */ int -compile(re, string, len, flags) -regex_t *re; -CONST chr *string; -size_t len; -int flags; +compile( + regex_t *re, + const chr *string, + size_t len, + int flags) { - struct vars var; - struct vars *v = &var; - struct guts *g; - int i; - size_t j; - FILE *debug = (flags®_PROGRESS) ? stdout : (FILE *)NULL; -# define CNOERR() { if (ISERR()) return freev(v, v->err); } - - /* sanity checks */ - - if (re == NULL || string == NULL) - return REG_INVARG; - if ((flags®_QUOTE) && - (flags&(REG_ADVANCED|REG_EXPANDED|REG_NEWLINE))) - return REG_INVARG; - if (!(flags®_EXTENDED) && (flags®_ADVF)) - return REG_INVARG; - - /* initial setup (after which freev() is callable) */ - v->re = re; - v->now = (chr *)string; - v->stop = v->now + len; - v->savenow = v->savestop = NULL; - 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->mcces = NULL; - v->lacons = NULL; - v->nlacons = 0; - re->re_magic = REMAGIC; - re->re_info = 0; /* bits get set during parse */ - re->re_csize = sizeof(chr); - 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(); - v->cv = newcvec(100, 20, 10); - if (v->cv == NULL) - return freev(v, REG_ESPACE); - i = nmcces(v); - if (i > 0) { - v->mcces = newcvec(nleaders(v), 0, i); - CNOERR(); - v->mcces = allmcces(v, v->mcces); - leaders(v, v->mcces); - addmcce(v->mcces, (chr *)NULL, (chr *)NULL); /* dummy */ - } - CNOERR(); - - /* parsing */ - lexstart(v); /* also handles prefixes */ - if ((v->cflags®_NLSTOP) || (v->cflags®_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(); - if (debug != NULL) { - fprintf(debug, "\n\n\n========= RAW ==========\n"); - dumpnfa(v->nfa, debug); - dumpst(v->tree, debug, 1); - } - optst(v, v->tree); - v->ntree = numst(v->tree, 1); - markst(v->tree); - cleanst(v); + AllocVars(v); + struct guts *g; + int i; + size_t j; + FILE *debug = (flags®_PROGRESS) ? stdout : NULL; +#define CNOERR() { if (ISERR()) return freev(v, v->err); } + + /* + * Sanity checks. + */ + + if (re == NULL || string == NULL) { + FreeVars(v); + return REG_INVARG; + } + if ((flags®_QUOTE) && (flags&(REG_ADVANCED|REG_EXPANDED|REG_NEWLINE))) { + FreeVars(v); + return REG_INVARG; + } + if (!(flags®_EXTENDED) && (flags®_ADVF)) { + FreeVars(v); + return REG_INVARG; + } + + /* + * Initial setup (after which freev() is callable). + */ + + v->re = re; + v->now = string; + v->stop = v->now + len; + v->savenow = v->savestop = NULL; + 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; + re->re_magic = REMAGIC; + re->re_info = 0; /* bits get set during parse */ + re->re_csize = sizeof(chr); + 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, NULL); + CNOERR(); + v->cv = newcvec(100, 20); + if (v->cv == NULL) { + return freev(v, REG_ESPACE); + } + + /* + * Parsing. + */ + + lexstart(v); /* also handles prefixes */ + if ((v->cflags®_NLSTOP) || (v->cflags®_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(); + if (debug != NULL) { + fprintf(debug, "\n\n\n========= RAW ==========\n"); + dumpnfa(v->nfa, debug); + dumpst(v->tree, debug, 1); + } + optst(v, v->tree); + v->ntree = numst(v->tree, 1); + markst(v->tree); + cleanst(v); + if (debug != NULL) { + fprintf(debug, "\n\n\n========= TREE FIXED ==========\n"); + dumpst(v->tree, debug, 1); + } + + /* + * 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++) { if (debug != NULL) { - fprintf(debug, "\n\n\n========= TREE FIXED ==========\n"); - dumpst(v->tree, debug, 1); + fprintf(debug, "\n\n\n========= LA%d ==========\n", i); } + nfanode(v, &v->lacons[i], debug); + } + CNOERR(); + if (v->tree->flags&SHORTER) { + NOTE(REG_USHORTEST); + } - /* 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++) { - if (debug != NULL) - fprintf(debug, "\n\n\n========= LA%d ==========\n", i); - nfanode(v, &v->lacons[i], debug); - } - CNOERR(); - if (v->tree->flags&SHORTER) - NOTE(REG_USHORTEST); - - /* build compacted NFAs for tree, lacons, fast search */ - if (debug != NULL) - fprintf(debug, "\n\n\n========= SEARCH ==========\n"); - /* 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®_ICASE) ? casecmp : cmp; - g->lacons = v->lacons; - v->lacons = NULL; - g->nlacons = v->nlacons; - - if (flags®_DUMP) - dump(re, stdout); - - assert(v->err == 0); - return freev(v, 0); -} + /* + * Build compacted NFAs for tree, lacons, fast search. + */ + + if (debug != NULL) { + fprintf(debug, "\n\n\n========= SEARCH ==========\n"); + } + + /* + * 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®_ICASE) ? casecmp : cmp; + g->lacons = v->lacons; + v->lacons = NULL; + g->nlacons = v->nlacons; + + if (flags®_DUMP) { + dump(re, stdout); + } + + assert(v->err == 0); + return freev(v, 0); +} + /* - moresubs - enlarge subRE vector - ^ static VOID moresubs(struct vars *, int); + ^ static void moresubs(struct vars *, int); */ -static VOID -moresubs(v, wanted) -struct vars *v; -int wanted; /* want enough room for this one */ +static void +moresubs( + struct vars *v, + int wanted) /* want enough room for this one */ { - 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; + 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(p, v->subs, v->nsubs * sizeof(struct subre *)); } - 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); + } 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); } - + /* - freev - free vars struct's substructures where necessary - * Optionally does error-number setting, and always returns error code - * (if any), to make error-handling code terser. + * Optionally does error-number setting, and always returns error code (if + * any), to make error-handling code terser. ^ static int freev(struct vars *, int); */ static int -freev(v, err) -struct vars *v; -int err; +freev( + struct vars *v, + int err) { - 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->mcces != NULL) - freecvec(v->mcces); - if (v->lacons != NULL) - freelacons(v->lacons, v->nlacons); - ERR(err); /* nop if err==0 */ - - return v->err; + register int ret; + + 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 */ + + ret = v->err; + FreeVars(v); + return ret; } - + /* - makesearch - turn an NFA into a search NFA (implicit prepend of .*?) * NFA must have been optimize()d already. - ^ static VOID makesearch(struct vars *, struct nfa *); + ^ static void makesearch(struct vars *, struct nfa *); */ -static VOID -makesearch(v, nfa) -struct vars *v; -struct nfa *nfa; +static void +makesearch( + struct vars *v, + struct nfa *nfa) { - 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); + struct arc *a, *b; + struct state *pre = nfa->pre; + struct state *s, *s2, *slist; - /* 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); + /* + * 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); /* - * 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. + * And ^* and \A* too -- not always necessary, but harmless. */ - /* first, make a list of the states */ - 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; - if (b != NULL) { /* must be split */ - if (s->tmp == NULL) { /* if not already in the list */ - /* (fixes bugs 505048, 230589, */ - /* 840258, 504785) */ - s->tmp = slist; - slist = s; - } - } + newarc(nfa, PLAIN, nfa->bos[0], pre, pre); + newarc(nfa, PLAIN, nfa->bos[1], pre, pre); + } + + /* + * 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. + */ + + 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; + } + } + if (b != NULL && s->tmp == NULL) { + /* + * Must be split if not already in the list (fixes bugs 505048, + * 230589, 840258, 504785). + */ + + s->tmp = slist; + slist = s; } + } + + /* + * Do the splits. + */ + + for (s=slist ; s!=NULL ; s=s2) { + s2 = newstate(nfa); - /* do the splits */ - for (s = slist; s != NULL; s = s2) { - s2 = newstate(nfa); - copyouts(nfa, s, s2); - 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->tmp = NULL; /* clean up while we're at it */ + copyouts(nfa, s, s2); + 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->tmp = NULL; /* clean up while we're at it */ + } } - + /* - parse - parse an RE - * This is actually just the top level, which parses a bunch of branches - * tied together with '|'. They appear in the tree as the left children - * of a chain of '|' subres. + * This is actually just the top level, which parses a bunch of branches tied + * together with '|'. They appear in the tree as the left children of a chain + * of '|' subres. ^ static struct subre *parse(struct vars *, int, int, struct state *, ^ struct state *); */ static struct subre * -parse(v, stopper, type, init, final) -struct vars *v; -int stopper; /* EOS or ')' */ -int type; /* LACON (lookahead subRE) or PLAIN */ -struct state *init; /* initial state */ -struct state *final; /* final state */ +parse( + struct vars *v, + int stopper, /* EOS or ')' */ + int type, /* LACON (lookahead subRE) or PLAIN */ + struct state *init, /* initial state */ + struct state *final) /* final state */ { - struct state *left; /* scaffolding for branch */ - struct state *right; - struct subre *branches; /* top level */ - struct subre *branch; /* current branch */ - struct subre *t; /* temporary */ - int firstbranch; /* is this the first branch? */ - - assert(stopper == ')' || stopper == EOS); - - branches = subre(v, '|', LONGER, init, final); + struct state *left, *right; /* scaffolding for branch */ + struct subre *branches; /* top level */ + struct subre *branch; /* current branch */ + struct subre *t; /* temporary */ + int firstbranch; /* is this the first branch? */ + + assert(stopper == ')' || stopper == EOS); + + branches = subre(v, '|', LONGER, init, final); + NOERRN(); + branch = branches; + firstbranch = 1; + do { /* a branch */ + if (!firstbranch) { + /* + * Need a place to hang the branch. + */ + + branch->right = subre(v, '|', LONGER, init, final); + NOERRN(); + branch = branch->right; + } + firstbranch = 0; + left = newstate(v->nfa); + right = newstate(v->nfa); NOERRN(); - branch = branches; - firstbranch = 1; - do { /* a branch */ - if (!firstbranch) { - /* need a place to hang it */ - branch->right = subre(v, '|', LONGER, init, final); - NOERRN(); - branch = branch->right; - } - firstbranch = 0; - left = newstate(v->nfa); - right = newstate(v->nfa); - NOERRN(); - EMPTYARC(init, left); - EMPTYARC(right, final); - NOERRN(); - branch->left = parsebranch(v, stopper, type, left, right, 0); - NOERRN(); - branch->flags |= UP(branch->flags | branch->left->flags); - if ((branch->flags &~ branches->flags) != 0) /* new flags */ - for (t = branches; t != branch; t = t->right) - t->flags |= branch->flags; - } while (EAT('|')); - assert(SEE(stopper) || SEE(EOS)); - - if (!SEE(stopper)) { - assert(stopper == ')' && SEE(EOS)); - ERR(REG_EPAREN); + EMPTYARC(init, left); + EMPTYARC(right, final); + NOERRN(); + branch->left = parsebranch(v, stopper, type, left, right, 0); + NOERRN(); + branch->flags |= UP(branch->flags | branch->left->flags); + if ((branch->flags &~ branches->flags) != 0) { /* new flags */ + for (t = branches; t != branch; t = t->right) { + t->flags |= branch->flags; + } } + } while (EAT('|')); + assert(SEE(stopper) || SEE(EOS)); - /* optimize out simple cases */ - if (branch == branches) { /* only one branch */ - assert(branch->right == NULL); - t = branch->left; - branch->left = NULL; - freesubre(v, branches); - branches = t; - } else if (!MESSY(branches->flags)) { /* no interesting innards */ - freesubre(v, branches->left); - branches->left = NULL; - freesubre(v, branches->right); - branches->right = NULL; - branches->op = '='; - } + if (!SEE(stopper)) { + assert(stopper == ')' && SEE(EOS)); + ERR(REG_EPAREN); + } - return branches; -} + /* + * Optimize out simple cases. + */ + if (branch == branches) { /* only one branch */ + assert(branch->right == NULL); + t = branch->left; + branch->left = NULL; + freesubre(v, branches); + branches = t; + } else if (!MESSY(branches->flags)) { /* no interesting innards */ + freesubre(v, branches->left); + branches->left = NULL; + freesubre(v, branches->right); + branches->right = NULL; + branches->op = '='; + } + + return branches; +} + /* - parsebranch - parse one branch of an RE * This mostly manages concatenation, working closely with parseqatom(). @@ -662,1514 +712,1446 @@ struct state *final; /* final state */ ^ struct state *, int); */ static struct subre * -parsebranch(v, stopper, type, left, right, partial) -struct vars *v; -int stopper; /* EOS or ')' */ -int type; /* LACON (lookahead subRE) or PLAIN */ -struct state *left; /* leftmost state */ -struct state *right; /* rightmost state */ -int partial; /* is this only part of a branch? */ +parsebranch( + struct vars *v, + int stopper, /* EOS or ')' */ + int type, /* LACON (lookahead subRE) or PLAIN */ + struct state *left, /* leftmost state */ + struct state *right, /* rightmost state */ + int partial) /* is this only part of a branch? */ { - 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 */ - parseqatom(v, stopper, type, lp, right, t); + 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 */ + parseqatom(v, stopper, type, lp, right, t); + } - if (!seencontent) { /* empty branch */ - if (!partial) - NOTE(REG_UUNSPEC); - assert(lp == left); - EMPTYARC(left, right); + if (!seencontent) { /* empty branch */ + if (!partial) { + NOTE(REG_UUNSPEC); } + assert(lp == left); + EMPTYARC(left, right); + } - return t; + return t; } - + /* - parseqatom - parse one quantified atom or constraint of an RE - * The bookkeeping near the end cooperates very closely with parsebranch(); - * in particular, it contains a recursion that can involve parsing the rest - * of the branch, making this function's name somewhat inaccurate. - ^ static VOID parseqatom(struct vars *, int, int, struct state *, + * The bookkeeping near the end cooperates very closely with parsebranch(); in + * particular, it contains a recursion that can involve parsing the rest of + * the branch, making this function's name somewhat inaccurate. + ^ static void parseqatom(struct vars *, int, int, struct state *, ^ struct state *, struct subre *); */ -static VOID -parseqatom(v, stopper, type, lp, rp, top) -struct vars *v; -int stopper; /* EOS or ')' */ -int type; /* LACON (lookahead subRE) or PLAIN */ -struct state *lp; /* left state to hang it on */ -struct state *rp; /* right state to hang it on */ -struct subre *top; /* subtree top */ +static void +parseqatom( + struct vars *v, + int stopper, /* EOS or ')' */ + int type, /* LACON (lookahead subRE) or PLAIN */ + struct state *lp, /* left state to hang it on */ + struct state *rp, /* right state to hang it on */ + struct subre *top) /* subtree top */ { - 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 pos; /* positive lookahead? */ - 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) { + 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 pos; /* positive lookahead? */ + 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®_NLANCH) - ARCV(BEHIND, v->nlcolor); - NEXT(); - return; - break; - case '$': - ARCV('$', 1); - if (v->cflags®_NLANCH) - ARCV(AHEAD, v->nlcolor); - NEXT(); - return; - break; - case SBEGIN: - ARCV('^', 1); /* BOL */ - ARCV('^', 0); /* or BOS */ - NEXT(); - return; - break; - case SEND: - ARCV('$', 1); /* EOL */ - ARCV('$', 0); /* or EOS */ - NEXT(); - return; - break; - case '<': - wordchrs(v); /* does NEXT() */ - s = newstate(v->nfa); - NOERR(); - nonword(v, BEHIND, lp, s); - word(v, AHEAD, s, rp); - return; - break; - case '>': - wordchrs(v); /* does NEXT() */ - s = newstate(v->nfa); - NOERR(); - word(v, BEHIND, lp, s); - nonword(v, AHEAD, s, rp); - return; - break; - case WBDRY: - wordchrs(v); /* does NEXT() */ - s = newstate(v->nfa); - NOERR(); - nonword(v, BEHIND, lp, s); - word(v, AHEAD, s, rp); - s = newstate(v->nfa); - NOERR(); - word(v, BEHIND, lp, s); - nonword(v, AHEAD, s, rp); - return; - break; - case NWBDRY: - wordchrs(v); /* does NEXT() */ - s = newstate(v->nfa); - NOERR(); - word(v, BEHIND, lp, s); - word(v, AHEAD, s, rp); - s = newstate(v->nfa); - NOERR(); - nonword(v, BEHIND, lp, s); - nonword(v, AHEAD, s, rp); - return; - break; - case LACON: /* lookahead constraint */ - pos = v->nextvalue; - NEXT(); - s = newstate(v->nfa); - s2 = newstate(v->nfa); - NOERR(); - t = parse(v, ')', LACON, s, s2); - freesubre(v, t); /* internal structure irrelevant */ - assert(SEE(')') || ISERR()); - NEXT(); - n = newlacon(v, s, s2, pos); - NOERR(); - ARCV(LACON, n); - return; - break; - /* then errors, to get them out of the way */ - case '*': - case '+': - case '?': - case '{': - ERR(REG_BADRPT); - return; - break; - default: - ERR(REG_ASSERT); - return; - break; - /* then plain characters, and minor variants on that theme */ - case ')': /* unbalanced paren */ - if ((v->cflags®_ADVANCED) != REG_EXTENDED) { - ERR(REG_EPAREN); - return; - } - /* legal in EREs due to specification botch */ - NOTE(REG_UPBOTCH); - /* fallthrough into case PLAIN */ - case PLAIN: - onechr(v, v->nextvalue, lp, rp); - okcolors(v->nfa, v->cm); - NOERR(); - NEXT(); - break; - case '[': - if (v->nextvalue == 1) - bracket(v, lp, rp); - else - cbracket(v, lp, rp); - assert(SEE(']') || ISERR()); - NEXT(); - break; - case '.': - rainbow(v->nfa, v->cm, PLAIN, - (v->cflags®_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); - assert((size_t)subno < v->nsubs); - } else - atomtype = PLAIN; /* something that's not '(' */ - NEXT(); - /* need new endpoints because tree will contain pointers */ - s = newstate(v->nfa); - s2 = newstate(v->nfa); - NOERR(); - EMPTYARC(lp, s); - EMPTYARC(s2, rp); - NOERR(); - atom = parse(v, ')', PLAIN, s, s2); - assert(SEE(')') || ISERR()); - NEXT(); - NOERR(); - if (cap) { - v->subs[subno] = atom; - t = subre(v, '(', atom->flags|CAP, lp, rp); - NOERR(); - t->subno = subno; - t->left = atom; - atom = t; - } - /* postpone everything else pending possible {0} */ - break; - case BACKREF: /* the Feature From The Black Lagoon */ - INSIST(type != LACON, REG_ESUBREG); - INSIST(v->nextvalue < v->nsubs, REG_ESUBREG); - INSIST(v->subs[v->nextvalue] != NULL, REG_ESUBREG); - NOERR(); - assert(v->nextvalue > 0); - atom = subre(v, 'b', BACKR, lp, rp); - subno = v->nextvalue; - atom->subno = subno; - EMPTYARC(lp, rp); /* temporarily, so there's something */ - NEXT(); - break; + case '^': + ARCV('^', 1); + if (v->cflags®_NLANCH) { + ARCV(BEHIND, v->nlcolor); } - - /* ...and an atom may be followed by a quantifier */ - switch (v->nexttype) { - case '*': - m = 0; - n = INFINITY; - qprefer = (v->nextvalue) ? LONGER : SHORTER; - NEXT(); - break; - case '+': - m = 1; - n = INFINITY; - 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 = INFINITY; - if (m > n) { - ERR(REG_BADBR); - return; - } - /* {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; - } - NEXT(); - break; - default: /* no quantifier */ - m = n = 1; - qprefer = 0; - break; + NEXT(); + return; + case '$': + ARCV('$', 1); + if (v->cflags®_NLANCH) { + ARCV(AHEAD, v->nlcolor); } + NEXT(); + return; + case SBEGIN: + ARCV('^', 1); /* BOL */ + ARCV('^', 0); /* or BOS */ + NEXT(); + return; + case SEND: + ARCV('$', 1); /* EOL */ + ARCV('$', 0); /* or EOS */ + NEXT(); + return; + case '<': + wordchrs(v); /* does NEXT() */ + s = newstate(v->nfa); + NOERR(); + nonword(v, BEHIND, lp, s); + word(v, AHEAD, s, rp); + return; + case '>': + wordchrs(v); /* does NEXT() */ + s = newstate(v->nfa); + NOERR(); + word(v, BEHIND, lp, s); + nonword(v, AHEAD, s, rp); + return; + case WBDRY: + wordchrs(v); /* does NEXT() */ + s = newstate(v->nfa); + NOERR(); + nonword(v, BEHIND, lp, s); + word(v, AHEAD, s, rp); + s = newstate(v->nfa); + NOERR(); + word(v, BEHIND, lp, s); + nonword(v, AHEAD, s, rp); + return; + case NWBDRY: + wordchrs(v); /* does NEXT() */ + s = newstate(v->nfa); + NOERR(); + word(v, BEHIND, lp, s); + word(v, AHEAD, s, rp); + s = newstate(v->nfa); + NOERR(); + nonword(v, BEHIND, lp, s); + nonword(v, AHEAD, s, rp); + return; + case LACON: /* lookahead constraint */ + pos = v->nextvalue; + NEXT(); + s = newstate(v->nfa); + s2 = newstate(v->nfa); + NOERR(); + t = parse(v, ')', LACON, s, s2); + freesubre(v, t); /* internal structure irrelevant */ + assert(SEE(')') || ISERR()); + NEXT(); + n = newlacon(v, s, s2, pos); + NOERR(); + ARCV(LACON, n); + return; - /* annoying special case: {0} or {0,0} cancels everything */ - if (m == 0 && n == 0) { - if (atom != NULL) - freesubre(v, atom); - if (atomtype == '(') - v->subs[subno] = NULL; - delsub(v->nfa, lp, rp); - EMPTYARC(lp, rp); - return; + /* + * Then errors, to get them out of the way. + */ + + case '*': + case '+': + case '?': + case '{': + ERR(REG_BADRPT); + return; + default: + ERR(REG_ASSERT); + return; + + /* + * Then plain characters, and minor variants on that theme. + */ + + case ')': /* unbalanced paren */ + if ((v->cflags®_ADVANCED) != REG_EXTENDED) { + ERR(REG_EPAREN); + return; } - /* 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; + /* + * Legal in EREs due to specification botch. + */ + + NOTE(REG_UPBOTCH); + /* fallthrough into case PLAIN */ + case PLAIN: + onechr(v, v->nextvalue, lp, rp); + okcolors(v->nfa, v->cm); + NOERR(); + NEXT(); + break; + case '[': + if (v->nextvalue == 1) { + bracket(v, lp, rp); + } else { + cbracket(v, lp, rp); } + assert(SEE(']') || ISERR()); + NEXT(); + break; + case '.': + rainbow(v->nfa, v->cm, PLAIN, + (v->cflags®_NLSTOP) ? v->nlcolor : COLORLESS, lp, rp); + NEXT(); + break; /* - * hard part: something messy - * That is, capturing parens, back reference, short/long clash, or - * an atom with substructure containing one of those. + * And finally the ugly stuff. */ - /* now we'll need a subre for the contents even if they're boring */ - if (atom == NULL) { - atom = subre(v, '=', 0, lp, rp); - NOERR(); + 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); + } + assert((size_t)subno < v->nsubs); + } else { + atomtype = PLAIN; /* something that's not '(' */ } + NEXT(); /* - * prepare a general-purpose state skeleton - * - * ---> [s] ---prefix---> [begin] ---atom---> [end] ----rest---> [rp] - * / / - * [lp] ----> [s2] ----bypass--------------------- - * - * where bypass is an empty, and prefix is some repetitions of atom + * Need new endpoints because tree will contain pointers. */ - s = newstate(v->nfa); /* first, new endpoints for the atom */ + + 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); NOERR(); - atom->begin = s; - atom->end = s2; - s = newstate(v->nfa); /* and spots for prefix and bypass */ - s2 = newstate(v->nfa); + atom = parse(v, ')', PLAIN, s, s2); + assert(SEE(')') || ISERR()); + NEXT(); NOERR(); - EMPTYARC(lp, s); - EMPTYARC(lp, s2); + if (cap) { + v->subs[subno] = atom; + t = subre(v, '(', atom->flags|CAP, lp, rp); + NOERR(); + t->subno = subno; + t->left = atom; + atom = t; + } + + /* + * Postpone everything else pending possible {0}. + */ + + break; + case BACKREF: /* the Feature From The Black Lagoon */ + INSIST(type != LACON, REG_ESUBREG); + INSIST(v->nextvalue < v->nsubs, REG_ESUBREG); + INSIST(v->subs[v->nextvalue] != NULL, REG_ESUBREG); NOERR(); + assert(v->nextvalue > 0); + atom = subre(v, 'b', BACKR, lp, rp); + subno = v->nextvalue; + atom->subno = subno; + EMPTYARC(lp, rp); /* temporarily, so there's something */ + NEXT(); + break; + } - /* break remaining subRE into x{...} and what follows */ - t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp); - t->left = atom; - atomp = &t->left; - /* here we should recurse... but we must postpone that to the end */ - - /* split top into prefix and remaining */ - assert(top->op == '=' && top->left == NULL && top->right == NULL); - top->left = subre(v, '=', top->flags, top->begin, lp); - top->op = '.'; - top->right = t; - - /* 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); - NOERR(); - } + /* + * ...and an atom may be followed by a quantifier. + */ - /* it's quantifier time; first, turn x{0,...} into x{1,...}|empty */ - if (m == 0) { - EMPTYARC(s2, atom->end); /* the bypass */ - assert(PREF(qprefer) != 0); - f = COMBINE(qprefer, atom->flags); - t = subre(v, '|', f, lp, atom->end); - NOERR(); - t->left = atom; - t->right = subre(v, '|', PREF(f), s2, atom->end); - NOERR(); - t->right->left = subre(v, '=', 0, s2, atom->end); - NOERR(); - *atomp = t; - atomp = &t->left; - m = 1; - } + switch (v->nexttype) { + case '*': + m = 0; + n = INFINITY; + qprefer = (v->nextvalue) ? LONGER : SHORTER; + NEXT(); + break; + case '+': + m = 1; + n = INFINITY; + 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 = INFINITY; + } + if (m > n) { + ERR(REG_BADBR); + return; + } + + /* + * {m,n} exercises preference, even if it's {m,m} + */ - /* deal with the rest of the quantifier */ - 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); - } else if (m == 1 && n == 1) { - /* no/vacuous quantifier: done */ - EMPTYARC(s, atom->begin); /* empty prefix */ + qprefer = (v->nextvalue) ? LONGER : SHORTER; } else { - /* turn x{m,n} into x{m-1,n-1}x, with capturing */ - /* parens in only second x */ - dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin); - assert(m >= 1 && m != INFINITY && n >= 1); - repeat(v, s, atom->begin, m-1, (n == INFINITY) ? n : n-1); - f = COMBINE(qprefer, atom->flags); - t = subre(v, '.', f, s, atom->end); /* prefix and atom */ - NOERR(); - t->left = subre(v, '=', PREF(f), s, atom->begin); - NOERR(); - t->right = atom; - *atomp = t; + n = m; + /* + * {m} passes operand's preference through. + */ + + qprefer = 0; + } + if (!SEE('}')) { /* catches errors too */ + ERR(REG_BADBR); + return; } + NEXT(); + break; + default: /* no quantifier */ + m = n = 1; + qprefer = 0; + break; + } + + /* + * Annoying special case: {0} or {0,0} cancels everything. + */ - /* and finally, look after that postponed recursion */ - t = top->right; - if (!(SEE('|') || SEE(stopper) || SEE(EOS))) - t->right = parsebranch(v, stopper, type, atom->end, rp, 1); - else { - EMPTYARC(atom->end, rp); - t->right = subre(v, '=', 0, atom->end, rp); + if (m == 0 && n == 0) { + if (atom != NULL) { + freesubre(v, atom); } - assert(SEE('|') || SEE(stopper) || SEE(EOS)); - t->flags |= COMBINE(t->flags, t->right->flags); - top->flags |= COMBINE(top->flags, t->flags); -} + if (atomtype == '(') { + v->subs[subno] = NULL; + } + delsub(v->nfa, lp, rp); + EMPTYARC(lp, rp); + return; + } + + /* + * 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; + } + + /* + * 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); + NOERR(); + } + + /* + * Prepare a general-purpose state skeleton. + * + * ---> [s] ---prefix---> [begin] ---atom---> [end] ----rest---> [rp] + * / / + * [lp] ----> [s2] ----bypass--------------------- + * + * where bypass is an empty, and prefix is some repetitions of atom + */ + + s = newstate(v->nfa); /* first, new endpoints for the atom */ + s2 = newstate(v->nfa); + NOERR(); + moveouts(v->nfa, lp, s); + moveins(v->nfa, rp, s2); + NOERR(); + atom->begin = s; + atom->end = s2; + s = newstate(v->nfa); /* and spots for prefix and bypass */ + s2 = newstate(v->nfa); + NOERR(); + EMPTYARC(lp, s); + EMPTYARC(lp, s2); + NOERR(); + + /* + * Break remaining subRE into x{...} and what follows. + */ + + t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp); + t->left = atom; + atomp = &t->left; + + /* + * Here we should recurse... but we must postpone that to the end. + */ + + /* + * Split top into prefix and remaining. + */ + + assert(top->op == '=' && top->left == NULL && top->right == NULL); + top->left = subre(v, '=', top->flags, top->begin, lp); + top->op = '.'; + top->right = t; + + /* + * 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); + NOERR(); + } + /* + * It's quantifier time; first, turn x{0,...} into x{1,...}|empty + */ + + if (m == 0) { + EMPTYARC(s2, atom->end);/* the bypass */ + assert(PREF(qprefer) != 0); + f = COMBINE(qprefer, atom->flags); + t = subre(v, '|', f, lp, atom->end); + NOERR(); + t->left = atom; + t->right = subre(v, '|', PREF(f), s2, atom->end); + NOERR(); + t->right->left = subre(v, '=', 0, s2, atom->end); + NOERR(); + *atomp = t; + atomp = &t->left; + m = 1; + } + + /* + * Deal with the rest of the quantifier. + */ + + 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); + } else if (m == 1 && n == 1) { + /* + * No/vacuous quantifier: done. + */ + + EMPTYARC(s, atom->begin); /* empty prefix */ + } else { + /* + * Turn x{m,n} into x{m-1,n-1}x, with capturing parens in only second + * x + */ + + dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin); + assert(m >= 1 && m != INFINITY && n >= 1); + repeat(v, s, atom->begin, m-1, (n == INFINITY) ? n : n-1); + f = COMBINE(qprefer, atom->flags); + t = subre(v, '.', f, s, atom->end); /* prefix and atom */ + NOERR(); + t->left = subre(v, '=', PREF(f), s, atom->begin); + NOERR(); + t->right = atom; + *atomp = t; + } + + /* + * And finally, look after that postponed recursion. + */ + + t = top->right; + if (!(SEE('|') || SEE(stopper) || SEE(EOS))) { + t->right = parsebranch(v, stopper, type, atom->end, rp, 1); + } else { + EMPTYARC(atom->end, rp); + t->right = subre(v, '=', 0, atom->end, rp); + } + assert(SEE('|') || SEE(stopper) || SEE(EOS)); + t->flags |= COMBINE(t->flags, t->right->flags); + top->flags |= COMBINE(top->flags, t->flags); +} + /* - nonword - generate arcs for non-word-character ahead or behind - ^ static VOID nonword(struct vars *, int, struct state *, struct state *); + ^ static void nonword(struct vars *, int, struct state *, struct state *); */ -static VOID -nonword(v, dir, lp, rp) -struct vars *v; -int dir; /* AHEAD or BEHIND */ -struct state *lp; -struct state *rp; +static void +nonword( + struct vars *v, + int dir, /* AHEAD or BEHIND */ + struct state *lp, + struct state *rp) { - int anchor = (dir == AHEAD) ? '$' : '^'; + 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) */ + 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) */ } - + /* - word - generate arcs for word character ahead or behind - ^ static VOID word(struct vars *, int, struct state *, struct state *); + ^ static void word(struct vars *, int, struct state *, struct state *); */ -static VOID -word(v, dir, lp, rp) -struct vars *v; -int dir; /* AHEAD or BEHIND */ -struct state *lp; -struct state *rp; +static void +word( + struct vars *v, + int dir, /* AHEAD or BEHIND */ + struct state *lp, + struct state *rp) { - assert(dir == AHEAD || dir == BEHIND); - cloneouts(v->nfa, v->wordchrs, lp, rp, dir); - /* (no need for special attention to \n) */ + assert(dir == AHEAD || dir == BEHIND); + cloneouts(v->nfa, v->wordchrs, lp, rp, dir); + /* (no need for special attention to \n) */ } - + /* - scannum - scan a number ^ static int scannum(struct vars *); */ static int /* value, <= DUPMAX */ -scannum(v) -struct vars *v; +scannum( + struct vars *v) { - int n = 0; + 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; + while (SEE(DIGIT) && n < DUPMAX) { + n = n*10 + v->nextvalue; + NEXT(); + } + if (SEE(DIGIT) || n > DUPMAX) { + ERR(REG_BADBR); + return 0; + } + return n; } - + /* - repeat - replicate subNFA for quantifiers * The duplication sequences used here are chosen carefully so that any * pointers starting out pointing into the subexpression end up pointing into - * the last occurrence. (Note that it may not be strung between the same - * left and right end states, however!) This used to be important for the - * subRE tree, although the important bits are now handled by the in-line - * code in parse(), and when this is called, it doesn't matter any more. - ^ static VOID repeat(struct vars *, struct state *, struct state *, int, int); + * the last occurrence. (Note that it may not be strung between the same left + * and right end states, however!) This used to be important for the subRE + * tree, although the important bits are now handled by the in-line code in + * parse(), and when this is called, it doesn't matter any more. + ^ static void repeat(struct vars *, struct state *, struct state *, int, int); */ -static VOID -repeat(v, lp, rp, m, n) -struct vars *v; -struct state *lp; -struct state *rp; -int m; -int n; +static void +repeat( + struct vars *v, + struct state *lp, + struct state *rp, + int m, + int n) { -# define SOME 2 -# define INF 3 -# define PAIR(x, y) ((x)*4 + (y)) -# define REDUCE(x) ( ((x) == INFINITY) ? 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; - } +#define SOME 2 +#define INF 3 +#define PAIR(x, y) ((x)*4 + (y)) +#define REDUCE(x) ( ((x) == INFINITY) ? INF : (((x) > 1) ? SOME : (x)) ) + const int rm = REDUCE(m); + const int rn = REDUCE(n); + struct state *s, *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; + } } - + /* - bracket - handle non-complemented bracket expression * Also called from cbracket for complemented bracket expressions. - ^ static VOID bracket(struct vars *, struct state *, struct state *); + ^ static void bracket(struct vars *, struct state *, struct state *); */ -static VOID -bracket(v, lp, rp) -struct vars *v; -struct state *lp; -struct state *rp; +static void +bracket( + struct vars *v, + struct state *lp, + struct state *rp) { - assert(SEE('[')); - NEXT(); - while (!SEE(']') && !SEE(EOS)) - brackpart(v, lp, rp); - assert(SEE(']') || ISERR()); - okcolors(v->nfa, v->cm); + assert(SEE('[')); + NEXT(); + while (!SEE(']') && !SEE(EOS)) { + brackpart(v, lp, rp); + } + assert(SEE(']') || ISERR()); + okcolors(v->nfa, v->cm); } - + /* - cbracket - handle complemented bracket expression * We do it by calling bracket() with dummy endpoints, and then complementing - * the result. The alternative would be to invoke rainbow(), and then delete + * the result. The alternative would be to invoke rainbow(), and then delete * arcs as the b.e. is seen... but that gets messy. - ^ static VOID cbracket(struct vars *, struct state *, struct state *); + ^ static void cbracket(struct vars *, struct state *, struct state *); */ -static VOID -cbracket(v, lp, rp) -struct vars *v; -struct state *lp; -struct state *rp; +static void +cbracket( + struct vars *v, + struct state *lp, + struct state *rp) { - struct state *left = newstate(v->nfa); - struct state *right = newstate(v->nfa); - struct state *s; - struct arc *a; /* arc from lp */ - struct arc *ba; /* arc from left, from bracket() */ - struct arc *pa; /* MCCE-prototype arc */ - color co; - chr *p; - int i; + struct state *left = newstate(v->nfa); + struct state *right = newstate(v->nfa); - NOERR(); - bracket(v, left, right); - if (v->cflags®_NLSTOP) - newarc(v->nfa, PLAIN, v->nlcolor, left, right); - NOERR(); + NOERR(); + bracket(v, left, right); + if (v->cflags®_NLSTOP) { + newarc(v->nfa, PLAIN, v->nlcolor, left, right); + } + NOERR(); - assert(lp->nouts == 0); /* all outarcs will be ours */ + assert(lp->nouts == 0); /* all outarcs will be ours */ - /* easy part of complementing */ - colorcomplement(v->nfa, v->cm, PLAIN, left, lp, rp); - NOERR(); - if (v->mcces == NULL) { /* no MCCEs -- we're done */ - dropstate(v->nfa, left); - assert(right->nins == 0); - freestate(v->nfa, right); - return; - } - - /* but complementing gets messy in the presence of MCCEs... */ - NOTE(REG_ULOCALE); - for (p = v->mcces->chrs, i = v->mcces->nchrs; i > 0; p++, i--) { - co = GETCOLOR(v->cm, *p); - a = findarc(lp, PLAIN, co); - ba = findarc(left, PLAIN, co); - if (ba == NULL) { - assert(a != NULL); - freearc(v->nfa, a); - } else { - assert(a == NULL); - } - s = newstate(v->nfa); - NOERR(); - newarc(v->nfa, PLAIN, co, lp, s); - NOERR(); - pa = findarc(v->mccepbegin, PLAIN, co); - assert(pa != NULL); - if (ba == NULL) { /* easy case, need all of them */ - cloneouts(v->nfa, pa->to, s, rp, PLAIN); - newarc(v->nfa, '$', 1, s, rp); - newarc(v->nfa, '$', 0, s, rp); - colorcomplement(v->nfa, v->cm, AHEAD, pa->to, s, rp); - } else { /* must be selective */ - if (findarc(ba->to, '$', 1) == NULL) { - newarc(v->nfa, '$', 1, s, rp); - newarc(v->nfa, '$', 0, s, rp); - colorcomplement(v->nfa, v->cm, AHEAD, pa->to, - s, rp); - } - for (pa = pa->to->outs; pa != NULL; pa = pa->outchain) - if (findarc(ba->to, PLAIN, pa->co) == NULL) - newarc(v->nfa, PLAIN, pa->co, s, rp); - if (s->nouts == 0) /* limit of selectivity: none */ - dropstate(v->nfa, s); /* frees arc too */ - } - NOERR(); - } + /* + * Easy part of complementing, and all there is to do since the MCCE code + * was removed. + */ - delsub(v->nfa, left, right); - assert(left->nouts == 0); - freestate(v->nfa, left); - assert(right->nins == 0); - freestate(v->nfa, right); + colorcomplement(v->nfa, v->cm, PLAIN, left, lp, rp); + NOERR(); + dropstate(v->nfa, left); + assert(right->nins == 0); + freestate(v->nfa, right); + return; } - + /* - brackpart - handle one item (or range) within a bracket expression - ^ static VOID brackpart(struct vars *, struct state *, struct state *); + ^ static void brackpart(struct vars *, struct state *, struct state *); */ -static VOID -brackpart(v, lp, rp) -struct vars *v; -struct state *lp; -struct state *rp; +static void +brackpart( + struct vars *v, + struct state *lp, + struct state *rp) { - celt startc; - celt endc; - struct cvec *cv; - chr *startp; - chr *endp; - chr c[1]; - - /* parse something, get rid of special cases, take shortcuts */ + celt startc, endc; + struct cvec *cv; + const chr *startp, *endp; + chr c[1]; + + /* + * 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: + c[0] = v->nextvalue; + NEXT(); + + /* + * Shortcut for ordinary chr (not range). + */ + + if (!SEE(RANGE)) { + onechr(v, c[0], lp, rp); + return; + } + startc = element(v, c, c+1); + 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®_ICASE)); + NOERR(); + dovec(v, cv, lp, rp); + return; + break; + case CCLASS: + startp = v->now; + endp = scanplain(v); + INSIST(startp < endp, REG_ECTYPE); + NOERR(); + cv = cclass(v, startp, endp, (v->cflags®_ICASE)); + NOERR(); + dovec(v, cv, lp, rp); + return; + break; + default: + ERR(REG_ASSERT); + return; + break; + } + + if (SEE(RANGE)) { + NEXT(); switch (v->nexttype) { - case RANGE: /* a-b-c or other botch */ - ERR(REG_ERANGE); - return; - break; case PLAIN: - c[0] = v->nextvalue; - NEXT(); - /* shortcut for ordinary chr (not range, not MCCE leader) */ - if (!SEE(RANGE) && !ISCELEADER(v, c[0])) { - onechr(v, c[0], lp, rp); - return; - } - startc = element(v, c, c+1); - NOERR(); - break; + case RANGE: + c[0] = v->nextvalue; + NEXT(); + endc = element(v, c, c+1); + 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®_ICASE)); - NOERR(); - dovec(v, cv, lp, rp); - return; - break; - case CCLASS: - startp = v->now; - endp = scanplain(v); - INSIST(startp < endp, REG_ECTYPE); - NOERR(); - cv = cclass(v, startp, endp, (v->cflags®_ICASE)); - NOERR(); - dovec(v, cv, lp, rp); - return; - break; + startp = v->now; + endp = scanplain(v); + INSIST(startp < endp, REG_ECOLLATE); + NOERR(); + endc = element(v, startp, endp); + NOERR(); + break; default: - ERR(REG_ASSERT); - return; - break; + ERR(REG_ERANGE); + return; + break; } + } else { + endc = startc; + } - if (SEE(RANGE)) { - NEXT(); - switch (v->nexttype) { - case PLAIN: - case RANGE: - c[0] = v->nextvalue; - NEXT(); - endc = element(v, c, c+1); - 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. + */ - /* - * 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®_ICASE)); - NOERR(); - dovec(v, cv, lp, rp); + if (startc != endc) { + NOTE(REG_UUNPORT); + } + cv = range(v, startc, endc, (v->cflags®_ICASE)); + NOERR(); + dovec(v, cv, lp, rp); } - + /* - scanplain - scan PLAIN contents of [. etc. - * Certain bits of trickery in lex.c know that this code does not try - * to look past the final bracket of the [. etc. - ^ static chr *scanplain(struct vars *); + * Certain bits of trickery in lex.c know that this code does not try to look + * past the final bracket of the [. etc. + ^ static const chr *scanplain(struct vars *); */ -static chr * /* just after end of sequence */ -scanplain(v) -struct vars *v; +static const chr * /* just after end of sequence */ +scanplain( + struct vars *v) { - chr *endp; + const chr *endp; - assert(SEE(COLLEL) || SEE(ECLASS) || SEE(CCLASS)); - NEXT(); + assert(SEE(COLLEL) || SEE(ECLASS) || SEE(CCLASS)); + NEXT(); + endp = v->now; + while (SEE(PLAIN)) { endp = v->now; - while (SEE(PLAIN)) { - endp = v->now; - NEXT(); - } - - assert(SEE(END) || ISERR()); NEXT(); + } - return endp; -} + assert(SEE(END) || ISERR()); + NEXT(); -/* - - leaders - process a cvec of collating elements to also include leaders - * Also gives all characters involved their own colors, which is almost - * certainly necessary, and sets up little disconnected subNFA. - ^ static VOID leaders(struct vars *, struct cvec *); - */ -static VOID -leaders(v, cv) -struct vars *v; -struct cvec *cv; -{ - int mcce; - chr *p; - chr leader; - struct state *s; - struct arc *a; - - v->mccepbegin = newstate(v->nfa); - v->mccepend = newstate(v->nfa); - NOERR(); - - for (mcce = 0; mcce < cv->nmcces; mcce++) { - p = cv->mcces[mcce]; - leader = *p; - if (!haschr(cv, leader)) { - addchr(cv, leader); - s = newstate(v->nfa); - newarc(v->nfa, PLAIN, subcolor(v->cm, leader), - v->mccepbegin, s); - okcolors(v->nfa, v->cm); - } else { - a = findarc(v->mccepbegin, PLAIN, - GETCOLOR(v->cm, leader)); - assert(a != NULL); - s = a->to; - assert(s != v->mccepend); - } - p++; - assert(*p != 0 && *(p+1) == 0); /* only 2-char MCCEs for now */ - newarc(v->nfa, PLAIN, subcolor(v->cm, *p), s, v->mccepend); - okcolors(v->nfa, v->cm); - } + return endp; } - + /* - onechr - fill in arcs for a plain character, and possible case complements * This is mostly a shortcut for efficient handling of the common case. - ^ static VOID onechr(struct vars *, pchr, struct state *, struct state *); + ^ static void onechr(struct vars *, pchr, struct state *, struct state *); */ -static VOID -onechr(v, c, lp, rp) -struct vars *v; -pchr c; -struct state *lp; -struct state *rp; +static void +onechr( + struct vars *v, + pchr c, + struct state *lp, + struct state *rp) { - if (!(v->cflags®_ICASE)) { - newarc(v->nfa, PLAIN, subcolor(v->cm, c), lp, rp); - return; - } + if (!(v->cflags®_ICASE)) { + newarc(v->nfa, PLAIN, subcolor(v->cm, c), lp, rp); + return; + } - /* rats, need general case anyway... */ - dovec(v, allcases(v, c), lp, rp); -} + /* + * Rats, need general case anyway... + */ + dovec(v, allcases(v, c), lp, rp); +} + /* - dovec - fill in arcs for each element of a cvec - * This one has to handle the messy cases, like MCCEs and MCCE leaders. - ^ static VOID dovec(struct vars *, struct cvec *, struct state *, + ^ static void dovec(struct vars *, struct cvec *, struct state *, ^ struct state *); */ -static VOID -dovec(v, cv, lp, rp) -struct vars *v; -struct cvec *cv; -struct state *lp; -struct state *rp; +static void +dovec( + struct vars *v, + struct cvec *cv, + struct state *lp, + struct state *rp) { - chr ch, from, to; - celt ce; - chr *p; - int i; - color co; - struct cvec *leads; - struct arc *a; - struct arc *pa; /* arc in prototype */ - struct state *s; - struct state *ps; /* state in prototype */ - - /* need a place to store leaders, if any */ - if (nmcces(v) > 0) { - assert(v->mcces != NULL); - if (v->cv2 == NULL || v->cv2->nchrs < v->mcces->nchrs) { - if (v->cv2 != NULL) - free(v->cv2); - v->cv2 = newcvec(v->mcces->nchrs, 0, v->mcces->nmcces); - NOERR(); - leads = v->cv2; - } else - leads = clearcvec(v->cv2); - } else - leads = NULL; - - /* first, get the ordinary characters out of the way */ - for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--) { - ch = *p; - if (!ISCELEADER(v, ch)) - newarc(v->nfa, PLAIN, subcolor(v->cm, ch), lp, rp); - else { - assert(singleton(v->cm, ch)); - assert(leads != NULL); - if (!haschr(leads, ch)) - addchr(leads, ch); - } + chr ch, from, to; + const chr *p; + int i; + + for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--) { + ch = *p; + newarc(v->nfa, PLAIN, subcolor(v->cm, ch), lp, rp); + } + + for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--) { + from = *p; + to = *(p+1); + if (from <= to) { + subrange(v, from, to, lp, rp); } + } - /* and the ranges */ - for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--) { - from = *p; - to = *(p+1); - while (from <= to && (ce = nextleader(v, from, to)) != NOCELT) { - if (from < ce) - subrange(v, from, ce - 1, lp, rp); - assert(singleton(v->cm, ce)); - assert(leads != NULL); - if (!haschr(leads, ce)) - addchr(leads, ce); - from = ce + 1; - } - if (from <= to) - subrange(v, from, to, lp, rp); - } - - if ((leads == NULL || leads->nchrs == 0) && cv->nmcces == 0) - return; - - /* deal with the MCCE leaders */ - NOTE(REG_ULOCALE); - for (p = leads->chrs, i = leads->nchrs; i > 0; p++, i--) { - co = GETCOLOR(v->cm, *p); - a = findarc(lp, PLAIN, co); - if (a != NULL) - s = a->to; - else { - s = newstate(v->nfa); - NOERR(); - newarc(v->nfa, PLAIN, co, lp, s); - NOERR(); - } - pa = findarc(v->mccepbegin, PLAIN, co); - assert(pa != NULL); - ps = pa->to; - newarc(v->nfa, '$', 1, s, rp); - newarc(v->nfa, '$', 0, s, rp); - colorcomplement(v->nfa, v->cm, AHEAD, ps, s, rp); - NOERR(); - } - - /* and the MCCEs */ - for (i = 0; i < cv->nmcces; i++) { - p = cv->mcces[i]; - assert(singleton(v->cm, *p)); - if (!singleton(v->cm, *p)) { - ERR(REG_ASSERT); - return; - } - ch = *p++; - co = GETCOLOR(v->cm, ch); - a = findarc(lp, PLAIN, co); - if (a != NULL) - s = a->to; - else { - s = newstate(v->nfa); - NOERR(); - newarc(v->nfa, PLAIN, co, lp, s); - NOERR(); - } - assert(*p != 0); /* at least two chars */ - assert(singleton(v->cm, *p)); - ch = *p++; - co = GETCOLOR(v->cm, ch); - assert(*p == 0); /* and only two, for now */ - newarc(v->nfa, PLAIN, co, s, rp); - NOERR(); - } -} - -/* - - nextleader - find next MCCE leader within range - ^ static celt nextleader(struct vars *, pchr, pchr); - */ -static celt /* NOCELT means none */ -nextleader(v, from, to) -struct vars *v; -pchr from; -pchr to; -{ - int i; - chr *p; - chr ch; - celt it = NOCELT; - - if (v->mcces == NULL) - return it; - - for (i = v->mcces->nchrs, p = v->mcces->chrs; i > 0; i--, p++) { - ch = *p; - if (from <= ch && ch <= to) - if (it == NOCELT || ch < it) - it = ch; - } - return it; } - + /* - wordchrs - set up word-chr list for word-boundary stuff, if needed - * The list is kept as a bunch of arcs between two dummy states; it's - * disposed of by the unreachable-states sweep in NFA optimization. - * Does NEXT(). Must not be called from any unusual lexical context. - * This should be reconciled with the \w etc. handling in lex.c, and - * should be cleaned up to reduce dependencies on input scanning. - ^ static VOID wordchrs(struct vars *); + * The list is kept as a bunch of arcs between two dummy states; it's disposed + * of by the unreachable-states sweep in NFA optimization. Does NEXT(). Must + * not be called from any unusual lexical context. This should be reconciled + * with the \w etc. handling in lex.c, and should be cleaned up to reduce + * dependencies on input scanning. + ^ static void wordchrs(struct vars *); */ -static VOID -wordchrs(v) -struct vars *v; +static void +wordchrs( + struct vars *v) { - struct state *left; - struct state *right; + struct state *left, *right; - if (v->wordchrs != NULL) { - NEXT(); /* for consistency */ - return; - } + if (v->wordchrs != NULL) { + NEXT(); /* for consistency */ + return; + } - left = newstate(v->nfa); - right = newstate(v->nfa); - NOERR(); - /* fine point: implemented with [::], and lexer will set REG_ULOCALE */ - lexword(v); - NEXT(); - assert(v->savenow != NULL && SEE('[')); - bracket(v, left, right); - assert((v->savenow != NULL && SEE(']')) || ISERR()); - NEXT(); - NOERR(); - v->wordchrs = left; -} + left = newstate(v->nfa); + right = newstate(v->nfa); + NOERR(); + /* + * Fine point: implemented with [::], and lexer will set REG_ULOCALE. + */ + + lexword(v); + NEXT(); + assert(v->savenow != NULL && SEE('[')); + bracket(v, left, right); + assert((v->savenow != NULL && SEE(']')) || ISERR()); + NEXT(); + NOERR(); + v->wordchrs = left; +} + /* - subre - allocate a subre ^ static struct subre *subre(struct vars *, int, int, struct state *, ^ struct state *); */ static struct subre * -subre(v, op, flags, begin, end) -struct vars *v; -int op; -int flags; -struct state *begin; -struct state *end; +subre( + struct vars *v, + int op, + int flags, + struct state *begin, + struct state *end) { - struct subre *ret; - - ret = v->treefree; - if (ret != NULL) - v->treefree = ret->left; - else { - ret = (struct subre *)MALLOC(sizeof(struct subre)); - if (ret == NULL) { - ERR(REG_ESPACE); - return NULL; - } - ret->chain = v->treechain; - v->treechain = ret; + struct subre *ret = v->treefree; + + if (ret != NULL) { + v->treefree = ret->left; + } else { + ret = (struct subre *) MALLOC(sizeof(struct subre)); + if (ret == NULL) { + ERR(REG_ESPACE); + return NULL; } - - assert(strchr("|.b(=", op) != NULL); - - ret->op = op; - ret->flags = flags; - ret->retry = 0; - ret->subno = 0; - ret->min = ret->max = 1; - ret->left = NULL; - ret->right = NULL; - ret->begin = begin; - ret->end = end; - ZAPCNFA(ret->cnfa); - - return ret; + ret->chain = v->treechain; + v->treechain = ret; + } + + assert(strchr("|.b(=", op) != NULL); + + ret->op = op; + ret->flags = flags; + ret->retry = 0; + ret->subno = 0; + ret->min = ret->max = 1; + ret->left = NULL; + ret->right = NULL; + ret->begin = begin; + ret->end = end; + ZAPCNFA(ret->cnfa); + + return ret; } - + /* - freesubre - free a subRE subtree - ^ static VOID freesubre(struct vars *, struct subre *); + ^ static void freesubre(struct vars *, struct subre *); */ -static VOID -freesubre(v, sr) -struct vars *v; /* might be NULL */ -struct subre *sr; +static void +freesubre( + struct vars *v, /* might be NULL */ + struct subre *sr) { - if (sr == NULL) - return; - - if (sr->left != NULL) - freesubre(v, sr->left); - if (sr->right != NULL) - freesubre(v, sr->right); - - freesrnode(v, sr); + if (sr == NULL) { + return; + } + + if (sr->left != NULL) { + freesubre(v, sr->left); + } + if (sr->right != NULL) { + freesubre(v, sr->right); + } + + freesrnode(v, sr); } - + /* - freesrnode - free one node in a subRE subtree - ^ static VOID freesrnode(struct vars *, struct subre *); + ^ static void freesrnode(struct vars *, struct subre *); */ -static VOID -freesrnode(v, sr) -struct vars *v; /* might be NULL */ -struct subre *sr; +static void +freesrnode( + struct vars *v, /* might be NULL */ + struct subre *sr) { - if (sr == NULL) - return; - - if (!NULLCNFA(sr->cnfa)) - freecnfa(&sr->cnfa); - sr->flags = 0; - - if (v != NULL) { - sr->left = v->treefree; - v->treefree = sr; - } else - FREE(sr); + if (sr == NULL) { + return; + } + + if (!NULLCNFA(sr->cnfa)) { + freecnfa(&sr->cnfa); + } + sr->flags = 0; + + if (v != NULL) { + sr->left = v->treefree; + v->treefree = sr; + } else { + FREE(sr); + } } - + /* - optst - optimize a subRE subtree - ^ static VOID optst(struct vars *, struct subre *); + ^ static void optst(struct vars *, struct subre *); */ -static VOID -optst(v, t) -struct vars *v; -struct subre *t; +static void +optst( + struct vars *v, + struct subre *t) { /* * DGP (2007-11-13): I assume it was the programmer's intent to eventually * come back and add code to optimize subRE trees, but the routine coded - * just spent effort traversing the tree and doing nothing. We can do + * just spends effort traversing the tree and doing nothing. We can do * nothing with less effort. */ return; } - + /* - numst - number tree nodes (assigning retry indexes) ^ static int numst(struct subre *, int); */ static int /* next number */ -numst(t, start) -struct subre *t; -int start; /* starting point for subtree numbers */ +numst( + struct subre *t, + int start) /* starting point for subtree numbers */ { - int i; - - assert(t != NULL); - - i = start; - t->retry = (short)i++; - if (t->left != NULL) - i = numst(t->left, i); - if (t->right != NULL) - i = numst(t->right, i); - return i; + int i; + + assert(t != NULL); + + i = start; + t->retry = (short) i++; + if (t->left != NULL) { + i = numst(t->left, i); + } + if (t->right != NULL) { + i = numst(t->right, i); + } + return i; } - + /* - markst - mark tree nodes as INUSE - ^ static VOID markst(struct subre *); + ^ static void markst(struct subre *); */ -static VOID -markst(t) -struct subre *t; +static void +markst( + struct subre *t) { - assert(t != NULL); - - t->flags |= INUSE; - if (t->left != NULL) - markst(t->left); - if (t->right != NULL) - markst(t->right); + assert(t != NULL); + + t->flags |= INUSE; + if (t->left != NULL) { + markst(t->left); + } + if (t->right != NULL) { + markst(t->right); + } } - + /* - cleanst - free any tree nodes not marked INUSE - ^ static VOID cleanst(struct vars *); + ^ static void cleanst(struct vars *); */ -static VOID -cleanst(v) -struct vars *v; +static void +cleanst( + struct vars *v) { - struct subre *t; - struct subre *next; + struct subre *t; + struct subre *next; - for (t = v->treechain; t != NULL; t = next) { - next = t->chain; - if (!(t->flags&INUSE)) - FREE(t); + 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 */ + } + v->treechain = NULL; + v->treefree = NULL; /* just on general principles */ } - + /* - nfatree - turn a subRE subtree into a tree of compacted NFAs ^ static long nfatree(struct vars *, struct subre *, FILE *); */ static long /* optimize results from top node */ -nfatree(v, t, f) -struct vars *v; -struct subre *t; -FILE *f; /* for debug output */ +nfatree( + struct vars *v, + struct subre *t, + FILE *f) /* for debug output */ { - assert(t != NULL && t->begin != NULL); + assert(t != NULL && t->begin != NULL); - if (t->left != NULL) - (DISCARD)nfatree(v, t->left, f); - if (t->right != NULL) - (DISCARD)nfatree(v, t->right, f); + if (t->left != NULL) { + (DISCARD) nfatree(v, t->left, f); + } + if (t->right != NULL) { + (DISCARD) nfatree(v, t->right, f); + } - return nfanode(v, t, f); + return nfanode(v, t, f); } - + /* - nfanode - do one NFA for nfatree ^ static long nfanode(struct vars *, struct subre *, FILE *); */ static long /* optimize results */ -nfanode(v, t, f) -struct vars *v; -struct subre *t; -FILE *f; /* for debug output */ +nfanode( + struct vars *v, + struct subre *t, + FILE *f) /* for debug output */ { - struct nfa *nfa; - long ret = 0; - char idbuf[50]; - - assert(t->begin != NULL); - - if (f != NULL) - fprintf(f, "\n\n\n========= TREE NODE %s ==========\n", - stid(t, idbuf, sizeof(idbuf))); - nfa = newnfa(v, v->cm, v->nfa); - NOERRZ(); - dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final); - if (!ISERR()) { - specialcolors(nfa); - ret = optimize(nfa, f); - } - if (!ISERR()) - compact(nfa, &t->cnfa); - - freenfa(nfa); - return ret; + struct nfa *nfa; + long ret = 0; + char idbuf[50]; + + assert(t->begin != NULL); + + if (f != NULL) { + fprintf(f, "\n\n\n========= TREE NODE %s ==========\n", + stid(t, idbuf, sizeof(idbuf))); + } + nfa = newnfa(v, v->cm, v->nfa); + NOERRZ(); + dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final); + if (!ISERR()) { + specialcolors(nfa); + ret = optimize(nfa, f); + } + if (!ISERR()) { + compact(nfa, &t->cnfa); + } + + freenfa(nfa); + return ret; } - + /* - newlacon - allocate a lookahead-constraint subRE ^ static int newlacon(struct vars *, struct state *, struct state *, int); */ static int /* lacon number */ -newlacon(v, begin, end, pos) -struct vars *v; -struct state *begin; -struct state *end; -int pos; +newlacon( + struct vars *v, + struct state *begin, + struct state *end, + int pos) { - int n; - struct subre *sub; - - if (v->nlacons == 0) { - v->lacons = (struct subre *)MALLOC(2 * sizeof(struct subre)); - n = 1; /* skip 0th */ - v->nlacons = 2; - } else { - v->lacons = (struct subre *)REALLOC(v->lacons, - (v->nlacons+1)*sizeof(struct subre)); - n = v->nlacons++; - } - if (v->lacons == NULL) { - ERR(REG_ESPACE); - return 0; - } - sub = &v->lacons[n]; - sub->begin = begin; - sub->end = end; - sub->subno = pos; - ZAPCNFA(sub->cnfa); - return n; + struct subre *sub; + int n; + + if (v->nlacons == 0) { + v->lacons = (struct subre *) MALLOC(2 * sizeof(struct subre)); + n = 1; /* skip 0th */ + v->nlacons = 2; + } else { + v->lacons = (struct subre *) REALLOC(v->lacons, + (v->nlacons+1)*sizeof(struct subre)); + n = v->nlacons++; + } + + if (v->lacons == NULL) { + ERR(REG_ESPACE); + return 0; + } + + sub = &v->lacons[n]; + sub->begin = begin; + sub->end = end; + sub->subno = pos; + ZAPCNFA(sub->cnfa); + return n; } - + /* - freelacons - free lookahead-constraint subRE vector - ^ static VOID freelacons(struct subre *, int); + ^ static void freelacons(struct subre *, int); */ -static VOID -freelacons(subs, n) -struct subre *subs; -int n; +static void +freelacons( + struct subre *subs, + int n) { - 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); -} + 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); +} + /* - rfree - free a whole RE (insides of regfree) - ^ static VOID rfree(regex_t *); + ^ static void rfree(regex_t *); */ -static VOID -rfree(re) -regex_t *re; +static void +rfree( + regex_t *re) { - 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; - 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); + 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; + g->magic = 0; + freecm(&g->cmap); + if (g->tree != NULL) { + freesubre(NULL, g->tree); + } + if (g->lacons != NULL) { + freelacons(g->lacons, g->nlacons); + } + if (!NULLCNFA(g->search)) { + freecnfa(&g->search); + } + FREE(g); } - + /* - dump - dump an RE in human-readable form - ^ static VOID dump(regex_t *, FILE *); + ^ static void dump(regex_t *, FILE *); */ -static VOID -dump(re, f) -regex_t *re; -FILE *f; +static void +dump( + regex_t *re, + FILE *f) { #ifdef REG_DEBUG - struct guts *g; - int i; - - if (re->re_magic != REMAGIC) - fprintf(f, "bad magic number (0x%x not 0x%x)\n", re->re_magic, - REMAGIC); - if (re->re_guts == NULL) { - fprintf(f, "NULL guts!!!\n"); - return; - } - g = (struct guts *)re->re_guts; - if (g->magic != GUTSMAGIC) - fprintf(f, "bad guts magic number (0x%x not 0x%x)\n", g->magic, - GUTSMAGIC); - - fprintf(f, "\n\n\n========= DUMP ==========\n"); - fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n", - re->re_nsub, re->re_info, re->re_csize, g->ntree); - - dumpcolors(&g->cmap, f); - if (!NULLCNFA(g->search)) { - printf("\nsearch:\n"); - dumpcnfa(&g->search, f); - } - for (i = 1; i < g->nlacons; i++) { - fprintf(f, "\nla%d (%s):\n", i, - (g->lacons[i].subno) ? "positive" : "negative"); - dumpcnfa(&g->lacons[i].cnfa, f); - } - fprintf(f, "\n"); - dumpst(g->tree, f, 0); + struct guts *g; + int i; + + if (re->re_magic != REMAGIC) { + fprintf(f, "bad magic number (0x%x not 0x%x)\n", + re->re_magic, REMAGIC); + } + if (re->re_guts == NULL) { + fprintf(f, "NULL guts!!!\n"); + return; + } + g = (struct guts *) re->re_guts; + if (g->magic != GUTSMAGIC) { + fprintf(f, "bad guts magic number (0x%x not 0x%x)\n", + g->magic, GUTSMAGIC); + } + + fprintf(f, "\n\n\n========= DUMP ==========\n"); + fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n", + re->re_nsub, re->re_info, re->re_csize, g->ntree); + + dumpcolors(&g->cmap, f); + if (!NULLCNFA(g->search)) { + printf("\nsearch:\n"); + dumpcnfa(&g->search, f); + } + for (i = 1; i < g->nlacons; i++) { + fprintf(f, "\nla%d (%s):\n", i, + (g->lacons[i].subno) ? "positive" : "negative"); + dumpcnfa(&g->lacons[i].cnfa, f); + } + fprintf(f, "\n"); + dumpst(g->tree, f, 0); #endif } - + /* - dumpst - dump a subRE tree - ^ static VOID dumpst(struct subre *, FILE *, int); + ^ static void dumpst(struct subre *, FILE *, int); */ -static VOID -dumpst(t, f, nfapresent) -struct subre *t; -FILE *f; -int nfapresent; /* is the original NFA still around? */ +static void +dumpst( + struct subre *t, + FILE *f, + int nfapresent) /* is the original NFA still around? */ { - if (t == NULL) - fprintf(f, "null tree\n"); - else - stdump(t, f, nfapresent); - fflush(f); + if (t == NULL) { + fprintf(f, "null tree\n"); + } else { + stdump(t, f, nfapresent); + } + fflush(f); } - + /* - stdump - recursive guts of dumpst - ^ static VOID stdump(struct subre *, FILE *, int); + ^ static void stdump(struct subre *, FILE *, int); */ -static VOID -stdump(t, f, nfapresent) -struct subre *t; -FILE *f; -int nfapresent; /* is the original NFA still around? */ +static void +stdump( + struct subre *t, + FILE *f, + int nfapresent) /* is the original NFA still around? */ { - char idbuf[50]; - - fprintf(f, "%s. `%c'", stid(t, idbuf, sizeof(idbuf)), t->op); - if (t->flags&LONGER) - fprintf(f, " longest"); - if (t->flags&SHORTER) - fprintf(f, " shortest"); - if (t->flags&MIXED) - fprintf(f, " hasmixed"); - if (t->flags&CAP) - fprintf(f, " hascapture"); - if (t->flags&BACKR) - fprintf(f, " hasbackref"); - if (!(t->flags&INUSE)) - fprintf(f, " UNUSED"); - if (t->subno != 0) - fprintf(f, " (#%d)", t->subno); - if (t->min != 1 || t->max != 1) { - fprintf(f, " {%d,", t->min); - if (t->max != INFINITY) - fprintf(f, "%d", t->max); - fprintf(f, "}"); - } - if (nfapresent) - fprintf(f, " %ld-%ld", (long)t->begin->no, (long)t->end->no); - if (t->left != NULL) - fprintf(f, " L:%s", stid(t->left, idbuf, sizeof(idbuf))); - if (t->right != NULL) - fprintf(f, " R:%s", stid(t->right, idbuf, sizeof(idbuf))); - if (!NULLCNFA(t->cnfa)) { - fprintf(f, "\n"); - dumpcnfa(&t->cnfa, f); + char idbuf[50]; + + fprintf(f, "%s. `%c'", stid(t, idbuf, sizeof(idbuf)), t->op); + if (t->flags&LONGER) { + fprintf(f, " longest"); + } + if (t->flags&SHORTER) { + fprintf(f, " shortest"); + } + if (t->flags&MIXED) { + fprintf(f, " hasmixed"); + } + if (t->flags&CAP) { + fprintf(f, " hascapture"); + } + if (t->flags&BACKR) { + fprintf(f, " hasbackref"); + } + if (!(t->flags&INUSE)) { + fprintf(f, " UNUSED"); + } + if (t->subno != 0) { + fprintf(f, " (#%d)", t->subno); + } + if (t->min != 1 || t->max != 1) { + fprintf(f, " {%d,", t->min); + if (t->max != INFINITY) { + fprintf(f, "%d", t->max); } + fprintf(f, "}"); + } + if (nfapresent) { + fprintf(f, " %ld-%ld", (long)t->begin->no, (long)t->end->no); + } + if (t->left != NULL) { + fprintf(f, " L:%s", stid(t->left, idbuf, sizeof(idbuf))); + } + if (t->right != NULL) { + fprintf(f, " R:%s", stid(t->right, idbuf, sizeof(idbuf))); + } + if (!NULLCNFA(t->cnfa)) { fprintf(f, "\n"); - if (t->left != NULL) - stdump(t->left, f, nfapresent); - if (t->right != NULL) - stdump(t->right, f, nfapresent); + dumpcnfa(&t->cnfa, f); + } + fprintf(f, "\n"); + if (t->left != NULL) { + stdump(t->left, f, nfapresent); + } + if (t->right != NULL) { + stdump(t->right, f, nfapresent); + } } - + /* - stid - identify a subtree node for dumping - ^ static char *stid(struct subre *, char *, size_t); + ^ static const char *stid(struct subre *, char *, size_t); */ -static char * /* points to buf or constant string */ -stid(t, buf, bufsize) -struct subre *t; -char *buf; -size_t bufsize; +static const char * /* points to buf or constant string */ +stid( + struct subre *t, + char *buf, + size_t bufsize) { - /* big enough for hex int or decimal t->retry? */ - if (bufsize < sizeof(void*)*2 + 3 || bufsize < sizeof(t->retry)*3 + 1) - return "unable"; - if (t->retry != 0) - sprintf(buf, "%d", t->retry); - else - sprintf(buf, "%p", t); - return buf; + /* + * Big enough for hex int or decimal t->retry? + */ + + if (bufsize < sizeof(void*)*2 + 3 || bufsize < sizeof(t->retry)*3 + 1) { + return "unable"; + } + if (t->retry != 0) { + sprintf(buf, "%d", t->retry); + } else { + sprintf(buf, "%p", t); + } + return buf; } #include "regc_lex.c" @@ -2177,3 +2159,11 @@ size_t bufsize; #include "regc_nfa.c" #include "regc_cvec.c" #include "regc_locale.c" + +/* + * Local Variables: + * mode: c + * c-basic-offset: 4 + * fill-column: 78 + * End: + */ |