From: Ryan Norton Date: Wed, 16 Jul 2003 22:03:51 +0000 (+0000) Subject: Tcl regex lib X-Git-Url: https://git.saurik.com/wxWidgets.git/commitdiff_plain/c0a7edde10fbc1d280ea1864e34db865e09d4e7d Tcl regex lib git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@22024 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775 --- diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c index a016af0b77..a84b939944 100644 --- a/src/regex/regcomp.c +++ b/src/regex/regcomp.c @@ -1,1610 +1,2261 @@ -#if defined(__MWERKS__) && !defined(__MACH__) -typedef long off_t ; -#else -#include -#endif -#include -#include -#include -#include -#include -#include "regex.h" - -#include "utils.h" -#include "regex2.h" +/* + * re_*comp and friends - compile REs + * This file #includes several others (see the bottom). + * + * 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. + * + * 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. + * + * 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 + * 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; + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * $Header: /projects/cvsroot/pgsql-server/src/backend/regex/regcomp.c,v 1.38 2003/08/08 21:41:56 momjian Exp $ + * + */ -#include "cclass.h" -#include "cname.h" +#include "regguts.h" /* - * parse structure, passed up and down to avoid global variables and - * other clumsinesses + * forward declarations, up here so forward datatypes etc. are defined early */ -struct parse { - char *next; /* next character in RE */ - char *end; /* end of string (-> NUL normally) */ - int error; /* has an error been seen? */ - sop *strip; /* malloced strip */ - sopno ssize; /* malloced strip size (allocated) */ - sopno slen; /* malloced strip length (used) */ - int ncsalloc; /* number of csets allocated */ - struct re_guts *g; -# define NPAREN 10 /* we need to remember () 1-9 for back refs */ - sopno pbegin[NPAREN]; /* -> ( ([0] unused) */ - sopno pend[NPAREN]; /* -> ) ([0] unused) */ +/* === regcomp.c === */ +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 chr *scanplain(struct vars *); +static void leaders(struct vars *, struct cvec *); +static void onechr(struct vars *, chr, struct state *, struct state *); +static void dovec(struct vars *, struct cvec *, struct state *, struct state *); +static celt nextleader(struct vars *, chr, chr); +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 *); + +#ifdef REG_DEBUG +static void dump(regex_t *, FILE *); +static void dumpst(struct subre *, FILE *, int); +static void stdump(struct subre *, FILE *, int); +static char *stid(struct subre *, char *, size_t); +#endif +/* === regc_lex.c === */ +static void lexstart(struct vars *); +static void prefixes(struct vars *); +static void lexnest(struct vars *, chr *, 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 *, chr); +static void skip(struct vars *); +static chr newline(void); +static chr chrnamed(struct vars *, chr *, chr *, chr); + +/* === regc_color.c === */ +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 *, chr, 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 *, chr c); +static color newsub(struct colormap *, pcolor); +static void subrange(struct vars *, chr, chr, struct state *, struct state *); +static void subblock(struct vars *, chr, 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 int singleton(struct colormap *, chr c); +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(struct colormap *, FILE *); +static void fillcheck(struct colormap *, union tree *, int, FILE *); +static void dumpchr(chr, FILE *); +#endif +/* === regc_nfa.c === */ +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(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(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 *); +static void dumpcnfa(struct cnfa *, FILE *); +static void dumpcstate(int, struct carc *, struct cnfa *, FILE *); +#endif +/* === regc_cvec.c === */ +static struct cvec *newcvec(int, int, int); +static struct cvec *clearcvec(struct cvec *); +static void addchr(struct cvec *, chr); +static void addrange(struct cvec *, chr, chr); +static void addmcce(struct cvec *, chr *, chr *); +static int haschr(struct cvec *, chr); +static struct cvec *getcvec(struct vars *, int, int, int); +static void freecvec(struct cvec *); + +/* === regc_locale.c === */ +static int wx_isdigit(wx_wchar c); +static int wx_isalpha(wx_wchar c); +static int wx_isalnum(wx_wchar c); +static int wx_isupper(wx_wchar c); +static int wx_islower(wx_wchar c); +static int wx_isgraph(wx_wchar c); +static int wx_ispunct(wx_wchar c); +static int wx_isspace(wx_wchar c); +static wx_wchar wx_toupper(wx_wchar c); +static wx_wchar wx_tolower(wx_wchar c); +static int nmcces(struct vars *); +static int nleaders(struct vars *); +static struct cvec *allmcces(struct vars *, struct cvec *); +static celt element(struct vars *, chr *, 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 *, chr *, chr *, int); +static struct cvec *allcases(struct vars *, chr); +static int cmp(const chr *, const chr *, size_t); +static int casecmp(const chr *, const chr *, size_t); + + +/* 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 */ }; -#include "regcomp.ih" +/* 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 ISERR() VISERR(v) +#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 */ +#define NOERRZ() {if (ISERR()) return 0;} /* NOERR with retval */ +#define INSIST(c, e) ((c) ? 0 : ERR(e)) /* if condition false, + * error */ +#define NOTE(b) (v->re->re_info |= (b)) /* note visible condition */ +#define EMPTYARC(x, y) newarc(v->nfa, EMPTY, 0, x, y) + +/* token type codes, some also used as NFA arc types */ +#define EMPTY 'n' /* no token present */ +#define EOS 'e' /* end of string */ +#define PLAIN 'p' /* ordinary character */ +#define DIGIT 'd' /* digit (in bound) */ +#define BACKREF 'b' /* back reference */ +#define COLLEL 'I' /* start of [. */ +#define ECLASS 'E' /* start of [= */ +#define CCLASS 'C' /* start of [: */ +#define END 'X' /* end of [. [= [: */ +#define RANGE 'R' /* - within [] which might be range delim. */ +#define LACON 'L' /* lookahead constraint subRE */ +#define AHEAD 'a' /* color-lookahead arc */ +#define BEHIND 'r' /* color-lookbehind arc */ +#define WBDRY 'w' /* word boundary constraint */ +#define NWBDRY 'W' /* non-word-boundary constraint */ +#define SBEGIN 'A' /* beginning of string (even if not BOL) */ +#define SEND 'Z' /* end of string (even if not EOL) */ +#define 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) + + + +/* static function list */ +static struct fns functions = { + rfree, /* regfree insides */ +}; -static char nuls[10]; /* place to point scanner in event of error */ -/* - * macros for use with parse structure - * BEWARE: these know that the parse structure is named `p' !!! - */ -#define PEEK() (*p->next) -#define PEEK2() (*(p->next+1)) -#define MORE() (p->next < p->end) -#define MORE2() (p->next+1 < p->end) -#define SEE(c) (MORE() && PEEK() == (c)) -#define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b)) -#define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0) -#define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0) -#define NEXT() (p->next++) -#define NEXT2() (p->next += 2) -#define NEXTn(n) (p->next += (n)) -#define GETNEXT() (*p->next++) -#define SETERROR(e) seterr(p, (e)) -#define REQUIRE(co, e) ((void)((co) || SETERROR(e))) -#define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e)) -#define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e)) -#define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e)) -#define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd)) -#define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos) -#define AHEAD(pos) dofwd(p, pos, HERE()-(pos)) -#define ASTERN(sop, pos) EMIT(sop, HERE()-pos) -#define HERE() (p->slen) -#define THERE() (p->slen - 1) -#define THERETHERE() (p->slen - 2) -#define DROP(n) (p->slen -= (n)) - -#ifndef NDEBUG -static int never = 0; /* for use in asserts; shuts lint up */ -#else -#define never 0 /* some s have bugs too */ -#endif /* - - regcomp - interface for parser and compilation - = extern int regcomp(regex_t *, const char *, int); - = #define REG_BASIC 0000 - = #define REG_EXTENDED 0001 - = #define REG_ICASE 0002 - = #define REG_NOSUB 0004 - = #define REG_NEWLINE 0010 - = #define REG_NOSPEC 0020 - = #define REG_PEND 0040 - = #define REG_DUMP 0200 + * regcomp - compile regular expression */ -int /* 0 success, otherwise REG_something */ -regcomp(preg, pattern, cflags) -regex_t *preg; -const char *pattern; -int cflags; +int +regcomp(regex_t *re, + const chr *string, + int flags) { - struct parse pa; - register struct re_guts *g; - register struct parse *p = &pa; - register int i; - register size_t len; -#ifdef REDEBUG -# define GOODFLAGS(f) (f) -#else -# define GOODFLAGS(f) ((f)&~REG_DUMP) -#endif + + size_t nLen = 0; + chr* s2 = (chr*) string; - cflags = GOODFLAGS(cflags); - if ((cflags®_EXTENDED) && (cflags®_NOSPEC)) - return(REG_INVARG); - - if (cflags®_PEND) { - if (preg->re_endp < pattern) - return(REG_INVARG); - len = preg->re_endp - pattern; - } else - len = strlen((char *)pattern); - - /* do the mallocs early so failure handling is easy */ - g = (struct re_guts *)malloc(sizeof(struct re_guts) + - (NC-1)*sizeof(cat_t)); - if (g == NULL) - return(REG_ESPACE); - p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */ - p->strip = (sop *)malloc(p->ssize * sizeof(sop)); - p->slen = 0; - if (p->strip == NULL) { - free((char *)g); - return(REG_ESPACE); - } + if (string && *string) + { + while(*++s2); + } - /* set things up */ - p->g = g; - p->next = (char *)pattern; /* convenience; we do not modify it */ - p->end = p->next + len; - p->error = 0; - p->ncsalloc = 0; - for (i = 0; i < NPAREN; i++) { - p->pbegin[i] = 0; - p->pend[i] = 0; - } - g->csetsize = NC; - g->sets = NULL; - g->setbits = NULL; - g->ncsets = 0; - g->cflags = cflags; - g->iflags = 0; - g->nbol = 0; - g->neol = 0; - g->must = NULL; - g->mlen = 0; - g->nsub = 0; - g->ncategories = 1; /* category 0 is "everything else" */ - g->categories = &g->catspace[-(CHAR_MIN)]; - (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t)); - g->backrefs = 0; - - /* do it */ - EMIT(OEND, 0); - g->firststate = THERE(); - if (cflags®_EXTENDED) - p_ere(p, OUT); - else if (cflags®_NOSPEC) - p_str(p); - else - p_bre(p, OUT, OUT); - EMIT(OEND, 0); - g->laststate = THERE(); - - /* tidy up loose ends and fill things in */ - categorize(p, g); - stripsnug(p, g); - findmust(p, g); - g->nplus = pluscount(p, g); - g->magic = MAGIC2; - preg->re_nsub = g->nsub; - preg->re_g = g; - preg->re_magic = MAGIC1; -#ifndef REDEBUG - /* not debugging, so can't rely on the assert() in regexec() */ - if (g->iflags&BAD) - SETERROR(REG_ASSERT); -#endif + nLen = ((s2 - string) / sizeof(chr)); - /* win or lose, we're done */ - if (p->error != 0) /* lose */ - regfree(preg); - return(p->error); + return wx_regcomp(re, string, nLen, flags); } - -/* - - p_ere - ERE parser top level, concatenation and alternation - == static void p_ere(register struct parse *p, int stop); - */ -static void -p_ere(p, stop) -register struct parse *p; -int stop; /* character this ERE should end at */ +int +wx_regcomp(regex_t *re, + const chr *string, + size_t len, + int flags) { - register char c; - register sopno prevback; - register sopno prevfwd; - register sopno conc; - register int first = 1; /* is this the first alternative? */ - - for (;;) { - /* do a bunch of concatenated expressions */ - conc = HERE(); - while (MORE() && (c = PEEK()) != '|' && c != stop) - p_ere_exp(p); - REQUIRE(HERE() != conc, REG_EMPTY); /* require nonempty */ - - if (!EAT('|')) - break; /* NOTE BREAK OUT */ - - if (first) { - INSERT(OCH_, conc); /* offset is wrong */ - prevfwd = conc; - prevback = conc; - first = 0; + struct vars var; + struct vars *v = &var; + struct guts *g; + int i; + size_t j; + +#ifdef REG_DEBUG + FILE *debug = (flags & REG_PROGRESS) ? stdout : (FILE *) NULL; + +#else + FILE *debug = (FILE *) NULL; +#endif + +#define CNOERR() { if (ISERR()) return freev(v, v->err); } + + /* sanity checks */ + + if (re == NULL || string == NULL) + return REG_INVARG; + if ((flags & REG_QUOTE) && + (flags & (REG_ADVANCED | REG_EXPANDED | REG_NEWLINE))) + return REG_INVARG; + if (!(flags & REG_EXTENDED) && (flags & REG_ADVF)) + return REG_INVARG; + + /* 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 & REG_NLSTOP) || (v->cflags & REG_NLANCH)) + { + /* assign newline a unique color */ + v->nlcolor = subcolor(v->cm, newline()); + okcolors(v->nfa, v->cm); + } + CNOERR(); + v->tree = parse(v, EOS, PLAIN, v->nfa->init, v->nfa->final); + assert(SEE(EOS)); /* even if error; ISERR() => SEE(EOS) */ + CNOERR(); + assert(v->tree != NULL); + + /* finish setup of nfa and its subre tree */ + specialcolors(v->nfa); + CNOERR(); +#ifdef REG_DEBUG + if (debug != NULL) + { + fprintf(debug, "\n\n\n========= RAW ==========\n"); + dumpnfa(v->nfa, debug); + dumpst(v->tree, debug, 1); } - ASTERN(OOR1, prevback); - prevback = THERE(); - AHEAD(prevfwd); /* fix previous offset */ - prevfwd = HERE(); - EMIT(OOR2, 0); /* offset is very wrong */ +#endif + optst(v, v->tree); + v->ntree = numst(v->tree, 1); + markst(v->tree); + cleanst(v); +#ifdef REG_DEBUG + if (debug != NULL) + { + fprintf(debug, "\n\n\n========= TREE FIXED ==========\n"); + dumpst(v->tree, debug, 1); } +#endif - if (!first) { /* tail-end fixups */ - AHEAD(prevfwd); - ASTERN(O_CH, prevback); + /* 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++) + { +#ifdef REG_DEBUG + if (debug != NULL) + fprintf(debug, "\n\n\n========= LA%d ==========\n", i); +#endif + nfanode(v, &v->lacons[i], debug); } + CNOERR(); + if (v->tree->flags & SHORTER) + NOTE(REG_USHORTEST); + + /* build compacted NFAs for tree, lacons, fast search */ +#ifdef REG_DEBUG + if (debug != NULL) + fprintf(debug, "\n\n\n========= SEARCH ==========\n"); +#endif + /* can sacrifice main NFA now, so use it as work area */ + (DISCARD) optimize(v->nfa, debug); + CNOERR(); + makesearch(v, v->nfa); + CNOERR(); + compact(v->nfa, &g->search); + CNOERR(); + + /* looks okay, package it up */ + re->re_nsub = v->nsubexp; + v->re = NULL; /* freev no longer frees re */ + g->magic = GUTSMAGIC; + g->cflags = v->cflags; + g->info = re->re_info; + g->nsub = re->re_nsub; + g->tree = v->tree; + v->tree = NULL; + g->ntree = v->ntree; + g->compare = (v->cflags & REG_ICASE) ? casecmp : cmp; + g->lacons = v->lacons; + v->lacons = NULL; + g->nlacons = v->nlacons; + +#ifdef REG_DEBUG + if (flags & REG_DUMP) + dump(re, stdout); +#endif - assert(!MORE() || SEE(stop)); + assert(v->err == 0); + return freev(v, 0); } /* - - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op - == static void p_ere_exp(register struct parse *p); + * moresubs - enlarge subRE vector */ static void -p_ere_exp(p) -register struct parse *p; +moresubs(struct vars * v, + int wanted) /* want enough room for this one */ { - register char c; - register sopno pos; - register int count; - register int count2; - register sopno subno; - int wascaret = 0; - - assert(MORE()); /* caller should have ensured this */ - c = GETNEXT(); - - pos = HERE(); - switch (c) { - case '(': - REQUIRE(MORE(), REG_EPAREN); - p->g->nsub++; - subno = p->g->nsub; - if (subno < NPAREN) - p->pbegin[subno] = HERE(); - EMIT(OLPAREN, subno); - if (!SEE(')')) - p_ere(p, ')'); - if (subno < NPAREN) { - p->pend[subno] = HERE(); - assert(p->pend[subno] != 0); + 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 *)); } - EMIT(ORPAREN, subno); - MUSTEAT(')', REG_EPAREN); - break; -#ifndef POSIX_MISTAKE - case ')': /* happens only if no current unmatched ( */ - /* - * You may ask, why the ifndef? Because I didn't notice - * this until slightly too late for 1003.2, and none of the - * other 1003.2 regular-expression reviewers noticed it at - * all. So an unmatched ) is legal POSIX, at least until - * we can get it fixed. - */ - SETERROR(REG_EPAREN); - break; -#endif - case '^': - EMIT(OBOL, 0); - p->g->iflags |= USEBOL; - p->g->nbol++; - wascaret = 1; - break; - case '$': - EMIT(OEOL, 0); - p->g->iflags |= USEEOL; - p->g->neol++; - break; - case '|': - SETERROR(REG_EMPTY); - break; - case '*': - case '+': - case '?': - SETERROR(REG_BADRPT); - break; - case '.': - if (p->g->cflags®_NEWLINE) - nonnewline(p); else - EMIT(OANY, 0); - break; - case '[': - p_bracket(p); - break; - case '\\': - REQUIRE(MORE(), REG_EESCAPE); - c = GETNEXT(); - ordinary(p, c); - break; - case '{': /* okay as ordinary except if digit follows */ - REQUIRE(!MORE() || !isdigit(PEEK()), REG_BADRPT); - /* FALLTHROUGH */ - default: - ordinary(p, c); - break; - } - - if (!MORE()) + p = (struct subre **) REALLOC(v->subs, n * sizeof(struct subre *)); + if (p == NULL) + { + ERR(REG_ESPACE); return; - c = PEEK(); - /* we call { a repetition if followed by a digit */ - if (!( c == '*' || c == '+' || c == '?' || - (c == '{' && MORE2() && isdigit(PEEK2())) )) - return; /* no repetition, we're done */ - NEXT(); - - REQUIRE(!wascaret, REG_BADRPT); - switch (c) { - case '*': /* implemented as +? */ - /* this case does not require the (y|) trick, noKLUDGE */ - INSERT(OPLUS_, pos); - ASTERN(O_PLUS, pos); - INSERT(OQUEST_, pos); - ASTERN(O_QUEST, pos); - break; - case '+': - INSERT(OPLUS_, pos); - ASTERN(O_PLUS, pos); - break; - case '?': - /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ - INSERT(OCH_, pos); /* offset slightly wrong */ - ASTERN(OOR1, pos); /* this one's right */ - AHEAD(pos); /* fix the OCH_ */ - EMIT(OOR2, 0); /* offset very wrong... */ - AHEAD(THERE()); /* ...so fix it */ - ASTERN(O_CH, THERETHERE()); - break; - case '{': - count = p_count(p); - if (EAT(',')) { - if (isdigit(PEEK())) { - count2 = p_count(p); - REQUIRE(count <= count2, REG_BADBR); - } else /* single number with comma */ - count2 = INFINITY; - } else /* just a single number */ - count2 = count; - repeat(p, pos, count, count2); - if (!EAT('}')) { /* error heuristics */ - while (MORE() && PEEK() != '}') - NEXT(); - REQUIRE(MORE(), REG_EBRACE); - SETERROR(REG_BADBR); - } - break; } - - if (!MORE()) - return; - c = PEEK(); - if (!( c == '*' || c == '+' || c == '?' || - (c == '{' && MORE2() && isdigit(PEEK2())) ) ) - return; - SETERROR(REG_BADRPT); + 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); } /* - - p_str - string (no metacharacters) "parser" - == static void p_str(register struct parse *p); + * 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. */ -static void -p_str(p) -register struct parse *p; +static int +freev(struct vars * v, + int err) { - REQUIRE(MORE(), REG_EMPTY); - while (MORE()) - ordinary(p, GETNEXT()); + 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; } /* - - p_bre - BRE parser top level, anchoring and concatenation - == static void p_bre(register struct parse *p, register int end1, \ - == register int end2); - * Giving end1 as OUT essentially eliminates the end1/end2 check. - * - * This implementation is a bit of a kludge, in that a trailing $ is first - * taken as an ordinary character and then revised to be an anchor. The - * only undesirable side effect is that '$' gets included as a character - * category in such cases. This is fairly harmless; not worth fixing. - * The amount of lookahead needed to avoid this kludge is excessive. + * makesearch - turn an NFA into a search NFA (implicit prepend of .*?) + * NFA must have been optimize()d already. */ static void -p_bre(p, end1, end2) -register struct parse *p; -register int end1; /* first terminating character */ -register int end2; /* second terminating character */ +makesearch(struct vars * v, + struct nfa * nfa) { - register sopno start = HERE(); - register int first = 1; /* first subexpression? */ - register int wasdollar = 0; - - if (EAT('^')) { - EMIT(OBOL, 0); - p->g->iflags |= USEBOL; - p->g->nbol++; - } - while (MORE() && !SEETWO(end1, end2)) { - wasdollar = p_simp_re(p, first); - first = 0; + 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 (wasdollar) { /* oops, that was a trailing anchor */ - DROP(1); - EMIT(OEOL, 0); - p->g->iflags |= USEEOL; - p->g->neol++; + if (a != NULL) + { + /* add implicit .* in front */ + rainbow(nfa, v->cm, PLAIN, COLORLESS, pre, pre); + + /* and ^* and \A* too -- not always necessary, but harmless */ + newarc(nfa, PLAIN, nfa->bos[0], pre, pre); + newarc(nfa, PLAIN, nfa->bos[1], pre, pre); } - REQUIRE(HERE() != start, REG_EMPTY); /* require nonempty */ -} - -/* - - p_simp_re - parse a simple RE, an atom possibly followed by a repetition - == static int p_simp_re(register struct parse *p, int starordinary); + /* + * 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. */ -static int /* was the simple RE an unbackslashed $? */ -p_simp_re(p, starordinary) -register struct parse *p; -int starordinary; /* is a leading * an ordinary character? */ -{ - register int c; - register int count; - register int count2; - register sopno pos; - register int i; - register sopno subno; -# define BACKSL (1<g->cflags®_NEWLINE) - nonnewline(p); - else - EMIT(OANY, 0); - break; - case '[': - p_bracket(p); - break; - case BACKSL|'{': - SETERROR(REG_BADRPT); - break; - case BACKSL|'(': - p->g->nsub++; - subno = p->g->nsub; - if (subno < NPAREN) - p->pbegin[subno] = HERE(); - EMIT(OLPAREN, subno); - /* the MORE here is an error heuristic */ - if (MORE() && !SEETWO('\\', ')')) - p_bre(p, '\\', ')'); - if (subno < NPAREN) { - p->pend[subno] = HERE(); - assert(p->pend[subno] != 0); - } - EMIT(ORPAREN, subno); - REQUIRE(EATTWO('\\', ')'), REG_EPAREN); - break; - case BACKSL|')': /* should not get here -- must be user */ - case BACKSL|'}': - SETERROR(REG_EPAREN); - break; - case BACKSL|'1': - case BACKSL|'2': - case BACKSL|'3': - case BACKSL|'4': - case BACKSL|'5': - case BACKSL|'6': - case BACKSL|'7': - case BACKSL|'8': - case BACKSL|'9': - i = (c&~BACKSL) - '0'; - assert(i < NPAREN); - if (p->pend[i] != 0) { - assert(i <= p->g->nsub); - EMIT(OBACK_, i); - assert(p->pbegin[i] != 0); - assert(OP(p->strip[p->pbegin[i]]) == OLPAREN); - assert(OP(p->strip[p->pend[i]]) == ORPAREN); - (void) dupl(p, p->pbegin[i]+1, p->pend[i]); - EMIT(O_BACK, i); - } else - SETERROR(REG_ESUBREG); - p->g->backrefs = 1; - break; - case '*': - REQUIRE(starordinary, REG_BADRPT); - /* FALLTHROUGH */ - default: - ordinary(p, (char)c); /* takes off BACKSL, if any */ + + /* 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 */ + s->tmp = slist; + slist = s; } - - if (EAT('*')) { /* implemented as +? */ - /* this case does not require the (y|) trick, noKLUDGE */ - INSERT(OPLUS_, pos); - ASTERN(O_PLUS, pos); - INSERT(OQUEST_, pos); - ASTERN(O_QUEST, pos); - } else if (EATTWO('\\', '{')) { - count = p_count(p); - if (EAT(',')) { - if (MORE() && isdigit(PEEK())) { - count2 = p_count(p); - REQUIRE(count <= count2, REG_BADBR); - } else /* single number with comma */ - count2 = INFINITY; - } else /* just a single number */ - count2 = count; - repeat(p, pos, count, count2); - if (!EATTWO('\\', '}')) { /* error heuristics */ - while (MORE() && !SEETWO('\\', '}')) - NEXT(); - REQUIRE(MORE(), REG_EBRACE); - SETERROR(REG_BADBR); } - } else if (c == (unsigned char)'$') /* $ (but not \$) ends it */ - return(1); - return(0); + /* 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 */ + } } /* - - p_count - parse a repetition count - == static int p_count(register struct parse *p); + * 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. */ -static int /* the value */ -p_count(p) -register struct parse *p; +static struct subre * +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 */ { - register int count = 0; - register int ndigits = 0; + 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); + 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); + } - while (MORE() && isdigit(PEEK()) && count <= DUPMAX) { - count = count*10 + (GETNEXT() - '0'); - ndigits++; + /* 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 = '='; } - REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR); - return(count); + return branches; } /* - - p_bracket - parse a bracketed character list - == static void p_bracket(register struct parse *p); + * parsebranch - parse one branch of an RE * - * Note a significant property of this code: if the allocset() did SETERROR, - * no set operations are done. + * This mostly manages concatenation, working closely with parseqatom(). + * Concatenated things are bundled up as much as possible, with separate + * ',' nodes introduced only when necessary due to substructure. */ -static void -p_bracket(p) -register struct parse *p; +static struct subre * +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? */ { - register cset *cs = allocset(p); - register int invert = 0; - - /* Dept of Truly Sickening Special-Case Kludges */ - if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) { - EMIT(OBOW, 0); - NEXTn(6); - return; - } - if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) { - EMIT(OEOW, 0); - NEXTn(6); - return; + 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; - if (EAT('^')) - invert++; /* make note to invert set at end */ - if (EAT(']')) - CHadd(cs, ']'); - else if (EAT('-')) - CHadd(cs, '-'); - while (MORE() && PEEK() != ']' && !SEETWO('-', ']')) - p_b_term(p, cs); - if (EAT('-')) - CHadd(cs, '-'); - MUSTEAT(']', REG_EBRACK); - - if (p->error != 0) /* don't mess things up further */ - return; - - if (p->g->cflags®_ICASE) { - register int i; - register int ci; - - for (i = p->g->csetsize - 1; i >= 0; i--) - if (CHIN(cs, i) && isalpha(i)) { - ci = othercase(i); - if (ci != i) - CHadd(cs, ci); - } - if (cs->multis != NULL) - mccase(p, cs); + /* NB, recursion in parseqatom() may swallow rest of branch */ + parseqatom(v, stopper, type, lp, right, t); } - if (invert) { - register int i; - for (i = p->g->csetsize - 1; i >= 0; i--) - if (CHIN(cs, i)) - CHsub(cs, i); - else - CHadd(cs, i); - if (p->g->cflags®_NEWLINE) - CHsub(cs, '\n'); - if (cs->multis != NULL) - mcinvert(p, cs); + if (!seencontent) + { /* empty branch */ + if (!partial) + NOTE(REG_UUNSPEC); + assert(lp == left); + EMPTYARC(left, right); } - assert(cs->multis == NULL); /* xxx */ - - if (nch(p, cs) == 1) { /* optimize singleton sets */ - ordinary(p, firstch(p, cs)); - freeset(p, cs); - } else - EMIT(OANYOF, freezeset(p, cs)); + return t; } /* - - p_b_term - parse one term of a bracketed character list - == static void p_b_term(register struct parse *p, register cset *cs); + * 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 -p_b_term(p, cs) -register struct parse *p; -register cset *cs; +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 */ { - register char c; - register char start, finish; - register int i; - - /* classify what we've got */ - switch ((MORE()) ? PEEK() : '\0') { - case '[': - c = (MORE2()) ? PEEK2() : '\0'; + 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 & REG_NLANCH) + ARCV(BEHIND, v->nlcolor); + NEXT(); + return; + break; + case '$': + ARCV('$', 1); + if (v->cflags & REG_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 '-': - SETERROR(REG_ERANGE); - return; /* NOTE 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; + 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: - c = '\0'; + ERR(REG_ASSERT); + return; break; + /* then plain characters, and minor variants on that theme */ + case ')': /* unbalanced paren */ + if ((v->cflags & REG_ADVANCED) != REG_EXTENDED) + { + ERR(REG_EPAREN); + return; } - - switch (c) { - case ':': /* character class */ - NEXT2(); - REQUIRE(MORE(), REG_EBRACK); - c = PEEK(); - REQUIRE(c != '-' && c != ']', REG_ECTYPE); - p_b_cclass(p, cs); - REQUIRE(MORE(), REG_EBRACK); - REQUIRE(EATTWO(':', ']'), REG_ECTYPE); + /* 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 '=': /* equivalence class */ - NEXT2(); - REQUIRE(MORE(), REG_EBRACK); - c = PEEK(); - REQUIRE(c != '-' && c != ']', REG_ECOLLATE); - p_b_eclass(p, cs); - REQUIRE(MORE(), REG_EBRACK); - REQUIRE(EATTWO('=', ']'), REG_ECOLLATE); + case '[': + if (v->nextvalue == 1) + bracket(v, lp, rp); + else + cbracket(v, lp, rp); + assert(SEE(']') || ISERR()); + NEXT(); break; - default: /* symbol, ordinary character, or range */ -/* xxx revision needed for multichar stuff */ - start = p_b_symbol(p); - if (SEE('-') && MORE2() && PEEK2() != ']') { - /* range */ + case '.': + rainbow(v->nfa, v->cm, PLAIN, + (v->cflags & REG_NLSTOP) ? v->nlcolor : COLORLESS, + lp, rp); NEXT(); - if (EAT('-')) - finish = '-'; + 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 - finish = p_b_symbol(p); - } else - finish = start; -/* xxx what about signed chars here... */ - REQUIRE(start <= finish, REG_ERANGE); - for (i = start; i <= finish; i++) - CHadd(cs, i); + 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; } -} -/* - - p_b_cclass - parse a character-class name and deal with it - == static void p_b_cclass(register struct parse *p, register cset *cs); - */ -static void -p_b_cclass(p, cs) -register struct parse *p; -register cset *cs; -{ - register char *sp = p->next; - register struct cclass *cp; - register size_t len; - register char *u; - register char c; - - while (MORE() && isalpha(PEEK())) + /* ...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(); - len = p->next - sp; - for (cp = cclasses; cp->name != NULL; cp++) - if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0') break; - if (cp->name == NULL) { - /* oops, didn't find it */ - SETERROR(REG_ECTYPE); + 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; + } - u = cp->chars; - while ((c = *u++) != '\0') - CHadd(cs, c); - for (u = cp->multis; *u != '\0'; u += strlen(u) + 1) - MCadd(p, cs, u); -} + /* 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; + } -/* - - p_b_eclass - parse an equivalence-class name and deal with it - == static void p_b_eclass(register struct parse *p, register cset *cs); - * - * This implementation is incomplete. xxx + /* 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. */ -static void -p_b_eclass(p, cs) -register struct parse *p; -register cset *cs; -{ - register char c; - c = p_b_coll_elem(p, '='); - CHadd(cs, c); -} + /* now we'll need a subre for the contents even if they're boring */ + if (atom == NULL) + { + atom = subre(v, '=', 0, lp, rp); + NOERR(); + } -/* - - p_b_symbol - parse a character or [..]ed multicharacter collating symbol - == static char p_b_symbol(register struct parse *p); + /* + * 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 */ -static char /* value of symbol */ -p_b_symbol(p) -register struct parse *p; -{ - register char value; + 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; + } - REQUIRE(MORE(), REG_EBRACK); - if (!EATTWO('[', '.')) - return(GETNEXT()); + /* 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; + } - /* collating symbol */ - value = p_b_coll_elem(p, '.'); - REQUIRE(EATTWO('.', ']'), REG_ECOLLATE); - return(value); + /* 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); } /* - - p_b_coll_elem - parse a collating-element name and look it up - == static char p_b_coll_elem(register struct parse *p, int endc); + * nonword - generate arcs for non-word-character ahead or behind */ -static char /* value of collating element */ -p_b_coll_elem(p, endc) -register struct parse *p; -int endc; /* name ended by endc,']' */ +static void +nonword(struct vars * v, + int dir, /* AHEAD or BEHIND */ + struct state * lp, + struct state * rp) { - register char *sp = p->next; - register struct cname *cp; - register int len; + int anchor = (dir == AHEAD) ? '$' : '^'; - while (MORE() && !SEETWO(endc, ']')) - NEXT(); - if (!MORE()) { - SETERROR(REG_EBRACK); - return(0); - } - len = p->next - sp; - for (cp = cnames; cp->name != NULL; cp++) - if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0') - return(cp->code); /* known name */ - if (len == 1) - return(*sp); /* single character */ - SETERROR(REG_ECOLLATE); /* neither */ - return(0); + 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) */ } /* - - othercase - return the case counterpart of an alphabetic - == static char othercase(int ch); + * word - generate arcs for word character ahead or behind */ -static char /* if no counterpart, return ch */ -othercase(ch) -int ch; +static void +word(struct vars * v, + int dir, /* AHEAD or BEHIND */ + struct state * lp, + struct state * rp) { - assert(isalpha(ch)); - if (isupper(ch)) - return(tolower(ch)); - else if (islower(ch)) - return(toupper(ch)); - else /* peculiar, but could happen */ - return(ch); + assert(dir == AHEAD || dir == BEHIND); + cloneouts(v->nfa, v->wordchrs, lp, rp, dir); + /* (no need for special attention to \n) */ } /* - - bothcases - emit a dualcase version of a two-case character - == static void bothcases(register struct parse *p, int ch); - * - * Boy, is this implementation ever a kludge... + * scannum - scan a number */ -static void -bothcases(p, ch) -register struct parse *p; -int ch; +static int /* value, <= DUPMAX */ +scannum(struct vars * v) { - register char *oldnext = p->next; - register char *oldend = p->end; - char bracket[3]; - - assert(othercase(ch) != ch); /* p_bracket() would recurse */ - p->next = bracket; - p->end = bracket+2; - bracket[0] = ch; - bracket[1] = ']'; - bracket[2] = '\0'; - p_bracket(p); - assert(p->next == bracket+2); - p->next = oldnext; - p->end = oldend; + 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; } /* - - ordinary - emit an ordinary character - == static void ordinary(register struct parse *p, register int ch); + * 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 -ordinary(p, ch) -register struct parse *p; -register int ch; +repeat(struct vars * v, + struct state * lp, + struct state * rp, + int m, + int n) { - register cat_t *cap = p->g->categories; - - if ((p->g->cflags®_ICASE) && isalpha(ch) && othercase(ch) != ch) - bothcases(p, ch); - else { - EMIT(OCHAR, (unsigned char)ch); - if (cap[ch] == 0) - cap[ch] = p->g->ncategories++; +#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; } } /* - - nonnewline - emit REG_NEWLINE version of OANY - == static void nonnewline(register struct parse *p); - * - * Boy, is this implementation ever a kludge... + * bracket - handle non-complemented bracket expression + * Also called from cbracket for complemented bracket expressions. */ static void -nonnewline(p) -register struct parse *p; +bracket(struct vars * v, + struct state * lp, + struct state * rp) { - register char *oldnext = p->next; - register char *oldend = p->end; - char bracket[4]; - - p->next = bracket; - p->end = bracket+3; - bracket[0] = '^'; - bracket[1] = '\n'; - bracket[2] = ']'; - bracket[3] = '\0'; - p_bracket(p); - assert(p->next == bracket+3); - p->next = oldnext; - p->end = oldend; + assert(SEE('[')); + NEXT(); + while (!SEE(']') && !SEE(EOS)) + brackpart(v, lp, rp); + assert(SEE(']') || ISERR()); + okcolors(v->nfa, v->cm); } /* - - repeat - generate code for a bounded repetition, recursively if needed - == static void repeat(register struct parse *p, sopno start, int from, int to); + * 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 + * arcs as the b.e. is seen... but that gets messy. */ static void -repeat(p, start, from, to) -register struct parse *p; -sopno start; /* operand from here to end of strip */ -int from; /* repeated from this number */ -int to; /* to this number of times (maybe INFINITY) */ +cbracket(struct vars * v, + struct state * lp, + struct state * rp) { - register sopno finish = HERE(); -# define N 2 -# define INF 3 -# define REP(f, t) ((f)*8 + (t)) -# define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N) - register sopno copy; - - if (p->error != 0) /* head off possible runaway recursion */ + 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; + + NOERR(); + bracket(v, left, right); + if (v->cflags & REG_NLSTOP) + newarc(v->nfa, PLAIN, v->nlcolor, left, right); + NOERR(); + + assert(lp->nouts == 0); /* all outarcs will be ours */ + + /* easy part of complementing */ + 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(); + } - assert(from <= to); + delsub(v->nfa, left, right); + assert(left->nouts == 0); + freestate(v->nfa, left); + assert(right->nins == 0); + freestate(v->nfa, right); +} - switch (REP(MAP(from), MAP(to))) { - case REP(0, 0): /* must be user doing this */ - DROP(finish-start); /* drop the operand */ +/* + * brackpart - handle one item (or range) within a bracket expression + */ +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 */ + switch (v->nexttype) + { + case RANGE: /* a-b-c or other botch */ + ERR(REG_ERANGE); + return; break; - case REP(0, 1): /* as x{1,1}? */ - case REP(0, N): /* as x{1,n}? */ - case REP(0, INF): /* as x{1,}? */ - /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ - INSERT(OCH_, start); /* offset is wrong... */ - repeat(p, start+1, 1, to); - ASTERN(OOR1, start); - AHEAD(start); /* ... fix it */ - EMIT(OOR2, 0); - AHEAD(THERE()); - ASTERN(O_CH, THERETHERE()); + 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 REP(1, 1): /* trivial case */ - /* done */ + case COLLEL: + startp = v->now; + endp = scanplain(v); + INSIST(startp < endp, REG_ECOLLATE); + NOERR(); + startc = element(v, startp, endp); + NOERR(); + break; + case ECLASS: + startp = v->now; + endp = scanplain(v); + INSIST(startp < endp, REG_ECOLLATE); + NOERR(); + startc = element(v, startp, endp); + NOERR(); + cv = eclass(v, startc, (v->cflags & REG_ICASE)); + NOERR(); + dovec(v, cv, lp, rp); + return; break; - case REP(1, N): /* as x?x{1,n-1} */ - /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ - INSERT(OCH_, start); - ASTERN(OOR1, start); - AHEAD(start); - EMIT(OOR2, 0); /* offset very wrong... */ - AHEAD(THERE()); /* ...so fix it */ - ASTERN(O_CH, THERETHERE()); - copy = dupl(p, start+1, finish+1); - assert(copy == finish+4); - repeat(p, copy, 1, to-1); + case CCLASS: + startp = v->now; + endp = scanplain(v); + INSIST(startp < endp, REG_ECTYPE); + NOERR(); + cv = cclass(v, startp, endp, (v->cflags & REG_ICASE)); + NOERR(); + dovec(v, cv, lp, rp); + return; break; - case REP(1, INF): /* as x+ */ - INSERT(OPLUS_, start); - ASTERN(O_PLUS, start); + default: + ERR(REG_ASSERT); + return; break; - case REP(N, N): /* as xx{m-1,n-1} */ - copy = dupl(p, start, finish); - repeat(p, copy, from-1, to-1); + } + + 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 REP(N, INF): /* as xx{n-1,INF} */ - copy = dupl(p, start, finish); - repeat(p, copy, from-1, to); + case COLLEL: + startp = v->now; + endp = scanplain(v); + INSIST(startp < endp, REG_ECOLLATE); + NOERR(); + endc = element(v, startp, endp); + NOERR(); break; - default: /* "can't happen" */ - SETERROR(REG_ASSERT); /* just in case */ + default: + ERR(REG_ERANGE); + return; break; } + } + else + endc = startc; + + /* + * Ranges are unportable. Actually, standard C does guarantee that + * digits are contiguous, but making that an exception is just too + * complicated. + */ + if (startc != endc) + NOTE(REG_UUNPORT); + cv = range(v, startc, endc, (v->cflags & REG_ICASE)); + NOERR(); + dovec(v, cv, lp, rp); } /* - - seterr - set an error condition - == static int seterr(register struct parse *p, int e); + * 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 int /* useless but makes type checking happy */ -seterr(p, e) -register struct parse *p; -int e; +static chr * /* just after end of sequence */ +scanplain(struct vars * v) { - if (p->error == 0) /* keep earliest error condition */ - p->error = e; - p->next = nuls; /* try to bring things to a halt */ - p->end = nuls; - return(0); /* make the return value well-defined */ + chr *endp; + + assert(SEE(COLLEL) || SEE(ECLASS) || SEE(CCLASS)); + NEXT(); + + endp = v->now; + while (SEE(PLAIN)) + { + endp = v->now; + NEXT(); + } + + assert(SEE(END) || ISERR()); + NEXT(); + + return endp; } /* - - allocset - allocate a set of characters for [] - == static cset *allocset(register struct parse *p); + * 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 cset * -allocset(p) -register struct parse *p; +static void +leaders(struct vars * v, + struct cvec * cv) { - register int no = p->g->ncsets++; - register size_t nc; - register size_t nbytes; - register cset *cs; - register size_t css = (size_t)p->g->csetsize; - register int i; - - if (no >= p->ncsalloc) { /* need another column of space */ - p->ncsalloc += CHAR_BIT; - nc = p->ncsalloc; - assert(nc % CHAR_BIT == 0); - nbytes = nc / CHAR_BIT * css; - if (p->g->sets == NULL) - p->g->sets = (cset *)malloc(nc * sizeof(cset)); - else - p->g->sets = (cset *)realloc((char *)p->g->sets, - nc * sizeof(cset)); - if (p->g->setbits == NULL) - p->g->setbits = (uch *)malloc(nbytes); - else { - p->g->setbits = (uch *)realloc((char *)p->g->setbits, - nbytes); - /* xxx this isn't right if setbits is now NULL */ - for (i = 0; i < no; i++) - p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT); + 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); } - if (p->g->sets != NULL && p->g->setbits != NULL) - (void) memset((char *)p->g->setbits + (nbytes - css), - 0, css); - else { - no = 0; - SETERROR(REG_ESPACE); - /* caller's responsibility not to do set ops */ + 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); } - - assert(p->g->sets != NULL); /* xxx */ - cs = &p->g->sets[no]; - cs->ptr = p->g->setbits + css*((no)/CHAR_BIT); - cs->mask = 1 << ((no) % CHAR_BIT); - cs->hash = 0; - cs->smultis = 0; - cs->multis = NULL; - - return(cs); } /* - - freeset - free a now-unused set - == static void freeset(register struct parse *p, register cset *cs); + * 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 -freeset(p, cs) -register struct parse *p; -register cset *cs; +onechr(struct vars * v, + chr c, + struct state * lp, + struct state * rp) { - register size_t i; - register cset *top = &p->g->sets[p->g->ncsets]; - register size_t css = (size_t)p->g->csetsize; - - for (i = 0; i < css; i++) - CHsub(cs, i); - if (cs == top-1) /* recover only the easy case */ - p->g->ncsets--; + if (!(v->cflags & REG_ICASE)) + { + newarc(v->nfa, PLAIN, subcolor(v->cm, c), lp, rp); + return; + } + + /* rats, need general case anyway... */ + dovec(v, allcases(v, c), lp, rp); } /* - - freezeset - final processing on a set of characters - == static int freezeset(register struct parse *p, register cset *cs); - * - * The main task here is merging identical sets. This is usually a waste - * of time (although the hash code minimizes the overhead), but can win - * big if REG_ICASE is being used. REG_ICASE, by the way, is why the hash - * is done using addition rather than xor -- all ASCII [aA] sets xor to - * the same value! + * dovec - fill in arcs for each element of a cvec + * This one has to handle the messy cases, like MCCEs and MCCE leaders. */ -static int /* set number */ -freezeset(p, cs) -register struct parse *p; -register cset *cs; +static void +dovec(struct vars * v, + struct cvec * cv, + struct state * lp, + struct state * rp) { - register uch h = cs->hash; - register size_t i; - register cset *top = &p->g->sets[p->g->ncsets]; - register cset *cs2; - register size_t css = (size_t)p->g->csetsize; - - /* look for an earlier one which is the same */ - for (cs2 = &p->g->sets[0]; cs2 < top; cs2++) - if (cs2->hash == h && cs2 != cs) { - /* maybe */ - for (i = 0; i < css; i++) - if (!!CHIN(cs2, i) != !!CHIN(cs, i)) - break; /* no */ - if (i == css) - break; /* yes */ + 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); + } + } - if (cs2 < top) { /* found one */ - freeset(p, cs); - cs = cs2; + /* 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); } - return((int)(cs - p->g->sets)); -} + if ((leads == NULL || leads->nchrs == 0) && cv->nmcces == 0) + return; -/* - - firstch - return first character in a set (which must have at least one) - == static int firstch(register struct parse *p, register cset *cs); - */ -static int /* character; there is no "none" value */ -firstch(p, cs) -register struct parse *p; -register cset *cs; -{ - register size_t i; - register size_t css = (size_t)p->g->csetsize; - - for (i = 0; i < css; i++) - if (CHIN(cs, i)) - return((char)i); - assert(never); - return(0); /* arbitrary */ + /* 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(); + } } /* - - nch - number of characters in a set - == static int nch(register struct parse *p, register cset *cs); + * nextleader - find next MCCE leader within range */ -static int -nch(p, cs) -register struct parse *p; -register cset *cs; +static celt /* NOCELT means none */ +nextleader(struct vars * v, + chr from, + chr to) { - register size_t i; - register size_t css = (size_t)p->g->csetsize; - register int n = 0; - - for (i = 0; i < css; i++) - if (CHIN(cs, i)) - n++; - return(n); + 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; } /* - - mcadd - add a collating element to a cset - == static void mcadd(register struct parse *p, register cset *cs, \ - == register char *cp); + * 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 -mcadd(p, cs, cp) -register struct parse *p; -register cset *cs; -register char *cp; +wordchrs(struct vars * v) { - register size_t oldend = cs->smultis; + struct state *left; + struct state *right; - cs->smultis += strlen(cp) + 1; - if (cs->multis == NULL) - cs->multis = malloc(cs->smultis); - else - cs->multis = realloc(cs->multis, cs->smultis); - if (cs->multis == NULL) { - SETERROR(REG_ESPACE); + if (v->wordchrs != NULL) + { + NEXT(); /* for consistency */ return; } - (void) strcpy(cs->multis + oldend - 1, cp); - cs->multis[cs->smultis - 1] = '\0'; + 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; } -/* these functions don't seem to be used (yet?), suppress warnings */ -#if 0 /* - - mcsub - subtract a collating element from a cset - == static void mcsub(register cset *cs, register char *cp); + * subre - allocate a subre */ -static void -mcsub(cs, cp) -register cset *cs; -register char *cp; +static struct subre * +subre(struct vars * v, + int op, + int flags, + struct state * begin, + struct state * end) { - register char *fp = mcfind(cs, cp); - register size_t len = strlen(fp); + struct subre *ret; - assert(fp != NULL); - (void) memmove(fp, fp + len + 1, - cs->smultis - (fp + len + 1 - cs->multis)); - cs->smultis -= len; - - if (cs->smultis == 0) { - free(cs->multis); - cs->multis = NULL; - return; + 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; } - cs->multis = realloc(cs->multis, cs->smultis); - assert(cs->multis != NULL); -} + assert(strchr("|.b(=", op) != NULL); -/* - - mcin - is a collating element in a cset? - == static int mcin(register cset *cs, register char *cp); - */ -static int -mcin(cs, cp) -register cset *cs; -register char *cp; -{ - return(mcfind(cs, cp) != 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; } /* - - mcfind - find a collating element in a cset - == static char *mcfind(register cset *cs, register char *cp); + * freesubre - free a subRE subtree */ -static char * -mcfind(cs, cp) -register cset *cs; -register char *cp; +static void +freesubre(struct vars * v, /* might be NULL */ + struct subre * sr) { - register char *p; - - if (cs->multis == NULL) - return(NULL); - for (p = cs->multis; *p != '\0'; p += strlen(p) + 1) - if (strcmp(cp, p) == 0) - return(p); - return(NULL); + if (sr == NULL) + return; + + if (sr->left != NULL) + freesubre(v, sr->left); + if (sr->right != NULL) + freesubre(v, sr->right); + + freesrnode(v, sr); } -#endif /* 0 */ /* - - mcinvert - invert the list of collating elements in a cset - == static void mcinvert(register struct parse *p, register cset *cs); - * - * This would have to know the set of possibilities. Implementation - * is deferred. + * freesrnode - free one node in a subRE subtree */ static void -mcinvert(p, cs) -register struct parse *p; -register cset *cs; +freesrnode(struct vars * v, /* might be NULL */ + struct subre * sr) { - assert(cs->multis == NULL); /* xxx */ + 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); } /* - - mccase - add case counterparts of the list of collating elements in a cset - == static void mccase(register struct parse *p, register cset *cs); - * - * This would have to know the set of possibilities. Implementation - * is deferred. + * optst - optimize a subRE subtree */ static void -mccase(p, cs) -register struct parse *p; -register cset *cs; +optst(struct vars * v, + struct subre * t) { - assert(cs->multis == NULL); /* xxx */ + if (t == NULL) + return; + + /* recurse through children */ + if (t->left != NULL) + optst(v, t->left); + if (t->right != NULL) + optst(v, t->right); } /* - - isinsets - is this character in any sets? - == static int isinsets(register struct re_guts *g, int c); + * numst - number tree nodes (assigning retry indexes) */ -static int /* predicate */ -isinsets(g, c) -register struct re_guts *g; -int c; +static int /* next number */ +numst(struct subre * t, + int start) /* starting point for subtree numbers */ { - register uch *col; - register int i; - register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT; - register unsigned uc = (unsigned char)c; - - for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize) - if (col[uc] != 0) - return(1); - return(0); + 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; } /* - - samesets - are these two characters in exactly the same sets? - == static int samesets(register struct re_guts *g, int c1, int c2); + * markst - mark tree nodes as INUSE */ -static int /* predicate */ -samesets(g, c1, c2) -register struct re_guts *g; -int c1; -int c2; +static void +markst(struct subre * t) { - register uch *col; - register int i; - register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT; - register unsigned uc1 = (unsigned char)c1; - register unsigned uc2 = (unsigned char)c2; - - for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize) - if (col[uc1] != col[uc2]) - return(0); - return(1); + assert(t != NULL); + + t->flags |= INUSE; + if (t->left != NULL) + markst(t->left); + if (t->right != NULL) + markst(t->right); } /* - - categorize - sort out character categories - == static void categorize(struct parse *p, register struct re_guts *g); + * cleanst - free any tree nodes not marked INUSE */ static void -categorize(p, g) -struct parse *p; -register struct re_guts *g; +cleanst(struct vars * v) { - register cat_t *cats = g->categories; - register int c; - register int c2; - register cat_t cat; - - /* avoid making error situations worse */ - if (p->error != 0) - return; - - for (c = CHAR_MIN; c <= CHAR_MAX; c++) - if (cats[c] == 0 && isinsets(g, c)) { - cat = g->ncategories++; - cats[c] = cat; - for (c2 = c+1; c2 <= CHAR_MAX; c2++) - if (cats[c2] == 0 && samesets(g, c, c2)) - cats[c2] = cat; + struct subre *t; + struct subre *next; + + for (t = v->treechain; t != NULL; t = next) + { + next = t->chain; + if (!(t->flags & INUSE)) + FREE(t); } + v->treechain = NULL; + v->treefree = NULL; /* just on general principles */ } /* - - dupl - emit a duplicate of a bunch of sops - == static sopno dupl(register struct parse *p, sopno start, sopno finish); + * nfatree - turn a subRE subtree into a tree of compacted NFAs */ -static sopno /* start of duplicate */ -dupl(p, start, finish) -register struct parse *p; -sopno start; /* from here */ -sopno finish; /* to this less one */ +static long /* optimize results from top node */ +nfatree(struct vars * v, + struct subre * t, + FILE *f) /* for debug output */ { - register sopno ret = HERE(); - register sopno len = finish - start; - - assert(finish >= start); - if (len == 0) - return(ret); - enlarge(p, p->ssize + len); /* this many unexpected additions */ - assert(p->ssize >= p->slen + len); - (void) memcpy((char *)(p->strip + p->slen), - (char *)(p->strip + start), (size_t)len*sizeof(sop)); - p->slen += len; - return(ret); + 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); + + return nfanode(v, t, f); } /* - - doemit - emit a strip operator - == static void doemit(register struct parse *p, sop op, size_t opnd); - * - * It might seem better to implement this as a macro with a function as - * hard-case backup, but it's just too big and messy unless there are - * some changes to the data structures. Maybe later. + * nfanode - do one NFA for nfatree */ -static void -doemit(p, op, opnd) -register struct parse *p; -sop op; -size_t opnd; +static long /* optimize results */ +nfanode(struct vars * v, + struct subre * t, + FILE *f) /* for debug output */ { - /* avoid making error situations worse */ - if (p->error != 0) - return; + struct nfa *nfa; + long ret = 0; - /* deal with oversize operands ("can't happen", more or less) */ - assert(opnd < 1<begin != NULL); - /* deal with undersized strip */ - if (p->slen >= p->ssize) - enlarge(p, (p->ssize+1) / 2 * 3); /* +50% */ - assert(p->slen < p->ssize); +#ifdef REG_DEBUG + if (f != NULL) + { + char idbuf[50]; - /* finally, it's all reduced to the easy case */ - p->strip[p->slen++] = SOP(op, opnd); + fprintf(f, "\n\n\n========= TREE NODE %s ==========\n", + stid(t, idbuf, sizeof(idbuf))); + } +#endif + nfa = newnfa(v, v->cm, v->nfa); + NOERRZ(); + dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final); + if (!ISERR()) + { + specialcolors(nfa); + ret = optimize(nfa, f); + } + if (!ISERR()) + compact(nfa, &t->cnfa); + + freenfa(nfa); + return ret; } /* - - doinsert - insert a sop into the strip - == static void doinsert(register struct parse *p, sop op, size_t opnd, sopno pos); + * newlacon - allocate a lookahead-constraint subRE */ -static void -doinsert(p, op, opnd, pos) -register struct parse *p; -sop op; -size_t opnd; -sopno pos; +static int /* lacon number */ +newlacon(struct vars * v, + struct state * begin, + struct state * end, + int pos) { - register sopno sn; - register sop s; - register int i; - - /* avoid making error situations worse */ - if (p->error != 0) - return; - - sn = HERE(); - EMIT(op, opnd); /* do checks, ensure space */ - assert(HERE() == sn+1); - s = p->strip[sn]; - - /* adjust paren pointers */ - assert(pos > 0); - for (i = 1; i < NPAREN; i++) { - if (p->pbegin[i] >= pos) { - p->pbegin[i]++; + 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; } - if (p->pend[i] >= pos) { - p->pend[i]++; + 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; } - - memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos], - (HERE()-pos-1)*sizeof(sop)); - p->strip[pos] = s; + sub = &v->lacons[n]; + sub->begin = begin; + sub->end = end; + sub->subno = pos; + ZAPCNFA(sub->cnfa); + return n; } /* - - dofwd - complete a forward reference - == static void dofwd(register struct parse *p, sopno pos, sop value); + * freelacons - free lookahead-constraint subRE vector */ static void -dofwd(p, pos, value) -register struct parse *p; -register sopno pos; -sop value; +freelacons(struct subre * subs, + int n) { - /* avoid making error situations worse */ - if (p->error != 0) - return; - - assert(value < 1<strip[pos] = OP(p->strip[pos]) | value; + 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); } /* - - enlarge - enlarge the strip - == static void enlarge(register struct parse *p, sopno size); + * rfree - free a whole RE (insides of regfree) */ static void -enlarge(p, size) -register struct parse *p; -register sopno size; +rfree(regex_t *re) { - register sop *sp; + struct guts *g; - if (p->ssize >= size) + if (re == NULL || re->re_magic != REMAGIC) return; - sp = (sop *)realloc(p->strip, size*sizeof(sop)); - if (sp == NULL) { - SETERROR(REG_ESPACE); - return; - } - p->strip = sp; - p->ssize = size; + 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); } +#ifdef REG_DEBUG + /* - - stripsnug - compact the strip - == static void stripsnug(register struct parse *p, register struct re_guts *g); + * dump - dump an RE in human-readable form */ static void -stripsnug(p, g) -register struct parse *p; -register struct re_guts *g; +dump(regex_t *re, + FILE *f) { - g->nstates = p->slen; - g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop)); - if (g->strip == NULL) { - SETERROR(REG_ESPACE); - g->strip = p->strip; + 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); } /* - - findmust - fill in must and mlen with longest mandatory literal string - == static void findmust(register struct parse *p, register struct re_guts *g); - * - * This algorithm could do fancy things like analyzing the operands of | - * for common subsequences. Someday. This code is simple and finds most - * of the interesting cases. - * - * Note that must and mlen got initialized during setup. + * dumpst - dump a subRE tree */ static void -findmust(p, g) -struct parse *p; -register struct re_guts *g; +dumpst(struct subre * t, + FILE *f, + int nfapresent) /* is the original NFA still around? */ { - register sop *scan; - sop *start; - register sop *newstart; - register sopno newlen; - register sop s; - register char *cp; - register sopno i; - - /* avoid making error situations worse */ - if (p->error != 0) - return; - - /* find the longest OCHAR sequence in strip */ - newlen = 0; - scan = g->strip + 1; - do { - s = *scan++; - switch (OP(s)) { - case OCHAR: /* sequence member */ - if (newlen == 0) /* new sequence */ - newstart = scan - 1; - newlen++; - break; - case OPLUS_: /* things that don't break one */ - case OLPAREN: - case ORPAREN: - break; - case OQUEST_: /* things that must be skipped */ - case OCH_: - scan--; - do { - scan += OPND(s); - s = *scan; - /* assert() interferes w debug printouts */ - if (OP(s) != O_QUEST && OP(s) != O_CH && - OP(s) != OOR2) { - g->iflags |= BAD; - return; - } - } while (OP(s) != O_QUEST && OP(s) != O_CH); - /* fallthrough */ - default: /* things that break a sequence */ - if (newlen > g->mlen) { /* ends one */ - start = newstart; - g->mlen = newlen; - } - newlen = 0; - break; - } - } while (OP(s) != OEND); - - if (g->mlen == 0) /* there isn't one */ - return; + if (t == NULL) + fprintf(f, "null tree\n"); + else + stdump(t, f, nfapresent); + fflush(f); +} - /* turn it into a character string */ - g->must = malloc((size_t)g->mlen + 1); - if (g->must == NULL) { /* argh; just forget it */ - g->mlen = 0; - return; +/* + * stdump - recursive guts of dumpst + */ +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, "}"); } - cp = g->must; - scan = start; - for (i = g->mlen; i > 0; i--) { - while (OP(s = *scan++) != OCHAR) - continue; - assert(cp < g->must + g->mlen); - *cp++ = (char)OPND(s); + 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); + fprintf(f, "\n"); } - assert(cp == g->must + g->mlen); - *cp++ = '\0'; /* just on general principles */ + if (t->left != NULL) + stdump(t->left, f, nfapresent); + if (t->right != NULL) + stdump(t->right, f, nfapresent); } /* - - pluscount - count + nesting - == static sopno pluscount(register struct parse *p, register struct re_guts *g); + * stid - identify a subtree node for dumping */ -static sopno /* nesting depth */ -pluscount(p, g) -struct parse *p; -register struct re_guts *g; +static char * /* points to buf or constant string */ +stid(struct subre * t, + char *buf, + size_t bufsize) { - register sop *scan; - register sop s; - register sopno plusnest = 0; - register sopno maxnest = 0; - - if (p->error != 0) - return(0); /* there may not be an OEND */ - - scan = g->strip + 1; - do { - s = *scan++; - switch (OP(s)) { - case OPLUS_: - plusnest++; - break; - case O_PLUS: - if (plusnest > maxnest) - maxnest = plusnest; - plusnest--; - break; - } - } while (OP(s) != OEND); - if (plusnest != 0) - g->iflags |= BAD; - return(maxnest); + /* big enough for hex int or decimal t->retry? */ + if (bufsize < sizeof(int) * 2 + 3 || bufsize < sizeof(t->retry) * 3 + 1) + return "unable"; + if (t->retry != 0) + sprintf(buf, "%d", t->retry); + else + sprintf(buf, "0x%x", (int) t); /* may lose bits, that's okay */ + return buf; } +#endif /* REG_DEBUG */ + + +#include "regc_lex.c" +#include "regc_color.c" +#include "regc_nfa.c" +#include "regc_cvec.c" +#include "regc_locale.c" diff --git a/src/regex/regcustom.h b/src/regex/regcustom.h new file mode 100644 index 0000000000..15ea15f495 --- /dev/null +++ b/src/regex/regcustom.h @@ -0,0 +1,92 @@ +/* + * 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. + * + * 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. + * + * 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 + * 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; + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * $Id$ + */ + +/* headers if any */ +#include +#include +#include +#include +#include +#ifndef wxCHECK_GCC_VERSION +#define wxCHECK_GCC_VERSION( major, minor ) \ + ( defined(__GNUC__) && defined(__GNUC_MINOR__) \ + && ( ( __GNUC__ > (major) ) \ + || ( __GNUC__ == (major) && __GNUC_MINOR__ >= (minor) ) ) ) +#endif + +#ifdef wxUSE_NEW_REGEX + + #if !wxUSE_UNICODE + # define wx_wchar char + #else // Unicode + #if (defined(__GNUC__) && !wxCHECK_GCC_VERSION(2, 96)) + # define wx_wchar __WCHAR_TYPE__ + #else // __WCHAR_TYPE__ and gcc < 2.96 + // standard case + # define wx_wchar wchar_t + #endif // __WCHAR_TYPE__ + #endif // ASCII/Unicode + +#else + + #define wx_wchar char + +#endif + + +/* overrides for regguts.h definitions, if any */ +#define FUNCPTR(name, args) (*name) args +#define MALLOC(n) malloc(n) +#define FREE(p) free(VS(p)) +#define REALLOC(p,n) realloc(VS(p),n) + +/* internal character type and related */ +typedef wx_wchar chr; /* the type itself */ +typedef unsigned uchr; /* unsigned type that will hold a chr */ +typedef int celt; /* type to hold chr, MCCE number, or + * NOCELT */ + +#define NOCELT (-1) /* celt value which is not valid chr or + * MCCE */ +#define CHR(c) ((unsigned char) (c)) /* turn char literal into chr + * literal */ +#define DIGITVAL(c) ((c)-'0') /* turn chr digit into its value */ +#define CHRBITS 32 /* bits in a chr; must not use sizeof */ +#define CHR_MIN 0x00000000 /* smallest and largest chr; the value */ +#define CHR_MAX 0xfffffffe /* CHR_MAX-CHR_MIN+1 should fit in uchr */ + +/* functions operating on chr */ +#define iscalnum(x) wx_isalnum(x) +#define iscalpha(x) wx_isalpha(x) +#define iscdigit(x) wx_isdigit(x) +#define iscspace(x) wx_isspace(x) + +/* and pick up the standard header */ +#include "regex.h" diff --git a/src/regex/regerror.c b/src/regex/regerror.c index b4c839adf5..4fd08556ba 100644 --- a/src/regex/regerror.c +++ b/src/regex/regerror.c @@ -1,130 +1,126 @@ -#if defined(__MWERKS__) && !defined(__MACH__) -typedef long off_t ; -#else -#include -#endif -#include -#include -#include -#include -#include -#include "regex.h" - -#include "utils.h" -#include "regerror.ih" - /* - = #define REG_OKAY 0 - = #define REG_NOMATCH 1 - = #define REG_BADPAT 2 - = #define REG_ECOLLATE 3 - = #define REG_ECTYPE 4 - = #define REG_EESCAPE 5 - = #define REG_ESUBREG 6 - = #define REG_EBRACK 7 - = #define REG_EPAREN 8 - = #define REG_EBRACE 9 - = #define REG_BADBR 10 - = #define REG_ERANGE 11 - = #define REG_ESPACE 12 - = #define REG_BADRPT 13 - = #define REG_EMPTY 14 - = #define REG_ASSERT 15 - = #define REG_INVARG 16 - = #define REG_ATOI 255 // convert name to number (!) - = #define REG_ITOA 0400 // convert number to name (!) + * regerror - error-code expansion + * + * 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. + * + * 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. + * + * 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 + * 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; + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * $Header: /projects/cvsroot/pgsql-server/src/backend/regex/regerror.c,v 1.26 2003/08/04 00:43:21 momjian Exp $ + * */ -static struct rerr { + +#include "regguts.h" + +/* unknown-error explanation */ +static char unk[] = "*** unknown regex error code 0x%x ***"; + +/* struct to map among codes, code names, and explanations */ +static struct rerr +{ int code; char *name; char *explain; -} rerrs[] = { - { REG_OKAY, "REG_OKAY", "no errors detected" }, - { REG_NOMATCH, "REG_NOMATCH", "regexec() failed to match" }, - { REG_BADPAT, "REG_BADPAT", "invalid regular expression" }, - { REG_ECOLLATE, "REG_ECOLLATE", "invalid collating element" }, - { REG_ECTYPE, "REG_ECTYPE", "invalid character class" }, - { REG_EESCAPE, "REG_EESCAPE", "trailing backslash (\\)" }, - { REG_ESUBREG, "REG_ESUBREG", "invalid backreference number" }, - { REG_EBRACK, "REG_EBRACK", "brackets ([ ]) not balanced" }, - { REG_EPAREN, "REG_EPAREN", "parentheses not balanced" }, - { REG_EBRACE, "REG_EBRACE", "braces not balanced" }, - { REG_BADBR, "REG_BADBR", "invalid repetition count(s)" }, - { REG_ERANGE, "REG_ERANGE", "invalid character range" }, - { REG_ESPACE, "REG_ESPACE", "out of memory" }, - { REG_BADRPT, "REG_BADRPT", "repetition-operator operand invalid" }, - { REG_EMPTY, "REG_EMPTY", "empty (sub)expression" }, - { REG_ASSERT, "REG_ASSERT", "\"can't happen\" -- you found a bug" }, - { REG_INVARG, "REG_INVARG", "invalid argument to regex routine" }, - { -1, "", "*** unknown regexp error code ***" }, +} rerrs[] = + +{ + /* the actual table is built from regex.h */ +#include "regerrs.h" + { + -1, "", "oops" + }, /* explanation special-cased in code */ }; +size_t +regerror(int errcode, /* error code, or REG_ATOI or REG_ITOA */ + const regex_t *preg, /* associated regex_t (unused at present) */ + char *errbuf, /* result buffer (unless errbuf_size==0) */ + size_t errbuf_size) /* available space in errbuf, can be 0 */ + { return regerror(errcode, preg, errbuf, errbuf_size); } /* - - regerror - the interface to error numbers - = extern size_t regerror(int, const regex_t *, char *, size_t); + * pg_regerror - the interface to error numbers */ /* ARGSUSED */ -size_t -regerror(errcode, preg, errbuf, errbuf_size) -int errcode; -const regex_t *preg; -char *errbuf; -size_t errbuf_size; +size_t /* actual space needed (including NUL) */ +wx_regerror(int errcode, /* error code, or REG_ATOI or REG_ITOA */ + const regex_t *preg, /* associated regex_t (unused at present) */ + char *errbuf, /* result buffer (unless errbuf_size==0) */ + size_t errbuf_size) /* available space in errbuf, can be 0 */ { - register struct rerr *r; - register size_t len; - register int target = errcode &~ REG_ITOA; - register char *s; - char convbuf[50]; + struct rerr *r; + char *msg; + char convbuf[sizeof(unk) + 50]; /* 50 = plenty for int */ + size_t len; + int icode; - if (errcode == REG_ATOI) - s = regatoi(preg, convbuf); - else { + switch (errcode) + { + case REG_ATOI: /* convert name to number */ for (r = rerrs; r->code >= 0; r++) - if (r->code == target) + if (strcmp(r->name, errbuf) == 0) break; - - if (errcode®_ITOA) { + sprintf(convbuf, "%d", r->code); /* -1 for unknown */ + msg = convbuf; + break; + case REG_ITOA: /* convert number to name */ + icode = atoi(errbuf); /* not our problem if this fails */ + for (r = rerrs; r->code >= 0; r++) + if (r->code == icode) + break; + if (r->code >= 0) + msg = r->name; + else + { /* unknown; tell him the number */ + sprintf(convbuf, "REG_%u", (unsigned) icode); + msg = convbuf; + } + break; + default: /* a real, normal error code */ + for (r = rerrs; r->code >= 0; r++) + if (r->code == errcode) + break; if (r->code >= 0) - (void) strcpy(convbuf, r->name); + msg = r->explain; else - sprintf(convbuf, "REG_0x%x", target); - assert(strlen(convbuf) < sizeof(convbuf)); - s = convbuf; - } else - s = r->explain; + { /* unknown; say so */ + sprintf(convbuf, unk, errcode); + msg = convbuf; + } + break; } - len = strlen(s) + 1; - if (errbuf_size > 0) { + len = strlen(msg) + 1; /* space needed, including NUL */ + if (errbuf_size > 0) + { if (errbuf_size > len) - (void) strcpy(errbuf, s); - else { - (void) strncpy(errbuf, s, errbuf_size-1); - errbuf[errbuf_size-1] = '\0'; + strcpy(errbuf, msg); + else + { /* truncate to fit */ + memcpy(errbuf, msg, errbuf_size - 1); /*RN - was strncpy*/ + errbuf[errbuf_size - 1] = '\0'; } } - return(len); -} - -/* - - regatoi - internal routine to implement REG_ATOI - == static char *regatoi(const regex_t *preg, char *localbuf); - */ -static char * -regatoi(preg, localbuf) -const regex_t *preg; -char *localbuf; -{ - register struct rerr *r; - - for (r = rerrs; r->code >= 0; r++) - if (strcmp(r->name, preg->re_endp) == 0) - break; - if (r->code < 0) - return("0"); - - sprintf(localbuf, "%d", r->code); - return(localbuf); + return len; } diff --git a/src/regex/regexec.c b/src/regex/regexec.c index d64bc28fcb..c3a29093f5 100644 --- a/src/regex/regexec.c +++ b/src/regex/regexec.c @@ -1,144 +1,1089 @@ /* - * the outer shell of regexec() + * re_*exec and friends - match REs * - * This file includes engine.c *twice*, after muchos fiddling with the - * macros that code uses. This lets the same code operate on two different - * representations for state sets. - */ -#if defined(__MWERKS__) && !defined(__MACH__) -typedef long off_t ; -#else -#include -#endif -#include -#include -#include -#include -#include -#include "regex.h" - -#include "utils.h" -#include "regex2.h" - -#ifdef REDEBUG -static int nope = 0; /* for use in asserts; shuts lint up */ -#endif - -/* macros for manipulating states, small version */ -#define states unsigned -#define states1 unsigned /* for later use in regexec() decision */ -#define CLEAR(v) ((v) = 0) -#define SET0(v, n) ((v) &= ~((unsigned)1 << (n))) -#define SET1(v, n) ((v) |= (unsigned)1 << (n)) -#define ISSET(v, n) ((v) & ((unsigned)1 << (n))) -#define ASSIGN(d, s) ((d) = (s)) -#define EQ(a, b) ((a) == (b)) -#define STATEVARS int dummy /* dummy version */ -#define STATESETUP(m, n) /* nothing */ -#define STATETEARDOWN(m) /* nothing */ -#define SETUP(v) ((v) = 0) -#define onestate unsigned -#define INIT(o, n) ((o) = (unsigned)1 << (n)) -#define INC(o) ((o) <<= 1) -#define ISSTATEIN(v, o) ((v) & (o)) -/* some abbreviations; note that some of these know variable names! */ -/* do "if I'm here, I can also be there" etc without branches */ -#define FWD(dst, src, n) ((dst) |= ((unsigned)(src)&(here)) << (n)) -#define BACK(dst, src, n) ((dst) |= ((unsigned)(src)&(here)) >> (n)) -#define ISSETBACK(v, n) ((v) & ((unsigned)here >> (n))) -/* function names */ -#define SNAMES /* engine.c looks after details */ - -#include "engine.c" - -/* now undo things */ -#undef states -#undef CLEAR -#undef SET0 -#undef SET1 -#undef ISSET -#undef ASSIGN -#undef EQ -#undef STATEVARS -#undef STATESETUP -#undef STATETEARDOWN -#undef SETUP -#undef onestate -#undef INIT -#undef INC -#undef ISSTATEIN -#undef FWD -#undef BACK -#undef ISSETBACK -#undef SNAMES - -/* macros for manipulating states, large version */ -#define states char * -#define CLEAR(v) memset(v, 0, m->g->nstates) -#define SET0(v, n) ((v)[n] = 0) -#define SET1(v, n) ((v)[n] = 1) -#define ISSET(v, n) ((v)[n]) -#define ASSIGN(d, s) memcpy(d, s, m->g->nstates) -#define EQ(a, b) (memcmp(a, b, m->g->nstates) == 0) -#define STATEVARS int vn; char *space -#define STATESETUP(m, nv) { (m)->space = malloc((nv)*(m)->g->nstates); \ - if ((m)->space == NULL) return(REG_ESPACE); \ - (m)->vn = 0; } -#define STATETEARDOWN(m) { free((m)->space); } -#define SETUP(v) ((v) = &m->space[m->vn++ * m->g->nstates]) -#define onestate int -#define INIT(o, n) ((o) = (n)) -#define INC(o) ((o)++) -#define ISSTATEIN(v, o) ((v)[o]) -/* some abbreviations; note that some of these know variable names! */ -/* do "if I'm here, I can also be there" etc without branches */ -#define FWD(dst, src, n) ((dst)[here+(n)] |= (src)[here]) -#define BACK(dst, src, n) ((dst)[here-(n)] |= (src)[here]) -#define ISSETBACK(v, n) ((v)[here - (n)]) -/* function names */ -#define LNAMES /* flag */ - -#include "engine.c" - -/* - - regexec - interface for matching - = extern int regexec(const regex_t *, const char *, size_t, \ - = regmatch_t [], int); - = #define REG_NOTBOL 00001 - = #define REG_NOTEOL 00002 - = #define REG_STARTEND 00004 - = #define REG_TRACE 00400 // tracing of execution - = #define REG_LARGE 01000 // force large representation - = #define REG_BACKR 02000 // force use of backref code + * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved. * - * We put this here so we can exploit knowledge of the state representation - * when choosing which matcher to call. Also, by this point the matchers - * have been prototyped. - */ -int /* 0 success, REG_NOMATCH failure */ -regexec(preg, string, nmatch, pmatch, eflags) -const regex_t *preg; -const char *string; -size_t nmatch; -regmatch_t pmatch[]; -int eflags; -{ - register struct re_guts *g = preg->re_g; -#ifdef REDEBUG -# define GOODFLAGS(f) (f) -#else -# define GOODFLAGS(f) ((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND)) -#endif - - if (preg->re_magic != MAGIC1 || g->magic != MAGIC2) - return(REG_BADPAT); - assert(!(g->iflags&BAD)); - if (g->iflags&BAD) /* backstop for no-debug case */ - return(REG_BADPAT); - eflags = GOODFLAGS(eflags); - - if (g->nstates <= CHAR_BIT*sizeof(states1) && !(eflags®_LARGE)) - return(smatcher(g, (char *)string, nmatch, pmatch, eflags)); + * 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. + * + * 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. + * + * 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 + * 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; + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * $Header: /projects/cvsroot/pgsql-server/src/backend/regex/regexec.c,v 1.23 2003/08/08 21:41:56 momjian Exp $ + * + */ + +#include "regguts.h" + + + +/* lazy-DFA representation */ +struct arcp +{ /* "pointer" to an outarc */ + struct sset *ss; + color co; +}; + +struct sset +{ /* state set */ + unsigned *states; /* pointer to bitvector */ + unsigned hash; /* hash of bitvector */ +#define HASH(bv, nw) (((nw) == 1) ? *(bv) : hash(bv, nw)) +#define HIT(h,bv,ss,nw) ((ss)->hash == (h) && ((nw) == 1 || \ + memcmp(VS(bv), VS((ss)->states), (nw)*sizeof(unsigned)) == 0)) + int flags; +#define STARTER 01 /* the initial state set */ +#define POSTSTATE 02 /* includes the goal state */ +#define LOCKED 04 /* locked in cache */ +#define NOPROGRESS 010 /* zero-progress state set */ + struct arcp ins; /* chain of inarcs pointing here */ + chr *lastseen; /* last entered on arrival here */ + struct sset **outs; /* outarc vector indexed by color */ + struct arcp *inchain; /* chain-pointer vector for outarcs */ +}; + +struct dfa +{ + int nssets; /* size of cache */ + int nssused; /* how many entries occupied yet */ + int nstates; /* number of states */ + int ncolors; /* length of outarc and inchain vectors */ + int wordsper; /* length of state-set bitvectors */ + struct sset *ssets; /* state-set cache */ + unsigned *statesarea; /* bitvector storage */ + unsigned *work; /* pointer to work area within statesarea */ + struct sset **outsarea; /* outarc-vector storage */ + struct arcp *incarea; /* inchain storage */ + struct cnfa *cnfa; + struct colormap *cm; + chr *lastpost; /* location of last cache-flushed success */ + chr *lastnopr; /* location of last cache-flushed + * NOPROGRESS */ + struct sset *search; /* replacement-search-pointer memory */ + int cptsmalloced; /* were the areas individually malloced? */ + char *mallocarea; /* self, or master malloced area, or NULL */ +}; + +#define WORK 1 /* number of work bitvectors needed */ + +/* setup for non-malloc allocation for small cases */ +#define FEWSTATES 20 /* must be less than UBITS */ +#define FEWCOLORS 15 +struct smalldfa +{ + struct dfa dfa; + struct sset ssets[FEWSTATES * 2]; + unsigned statesarea[FEWSTATES * 2 + WORK]; + struct sset *outsarea[FEWSTATES * 2 * FEWCOLORS]; + struct arcp incarea[FEWSTATES * 2 * FEWCOLORS]; +}; + +#define DOMALLOC ((struct smalldfa *)NULL) /* force malloc */ + + + +/* internal variables, bundled for easy passing around */ +struct vars +{ + regex_t *re; + struct guts *g; + int eflags; /* copies of arguments */ + size_t nmatch; + regmatch_t *pmatch; + rm_detail_t *details; + chr *start; /* start of string */ + chr *stop; /* just past end of string */ + int err; /* error code if any (0 none) */ + regoff_t *mem; /* memory vector for backtracking */ + struct smalldfa dfa1; + struct smalldfa dfa2; +}; + +#define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */ +#define ISERR() VISERR(v) +#define VERR(vv,e) (((vv)->err) ? (vv)->err : ((vv)->err = (e))) +#define ERR(e) VERR(v, e) /* record an error */ +#define NOERR() {if (ISERR()) return v->err;} /* if error seen, return + * it */ +#define OFF(p) ((p) - v->start) +#define LOFF(p) ((long)OFF(p)) + + + +/* + * forward declarations + */ +/* === regexec.c === */ +static int find(struct vars *, struct cnfa *, struct colormap *); +static int cfind(struct vars *, struct cnfa *, struct colormap *); +static int cfindloop(struct vars *, struct cnfa *, struct colormap *, struct dfa *, struct dfa *, chr **); +static void zapsubs(regmatch_t *, size_t); +static void zapmem(struct vars *, struct subre *); +static void subset(struct vars *, struct subre *, chr *, chr *); +static int dissect(struct vars *, struct subre *, chr *, chr *); +static int condissect(struct vars *, struct subre *, chr *, chr *); +static int altdissect(struct vars *, struct subre *, chr *, chr *); +static int cdissect(struct vars *, struct subre *, chr *, chr *); +static int ccondissect(struct vars *, struct subre *, chr *, chr *); +static int crevdissect(struct vars *, struct subre *, chr *, chr *); +static int cbrdissect(struct vars *, struct subre *, chr *, chr *); +static int caltdissect(struct vars *, struct subre *, chr *, chr *); + +/* === rege_dfa.c === */ +static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *); +static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *, chr **, int *); +static chr *lastcold(struct vars *, struct dfa *); +static struct dfa *newdfa(struct vars *, struct cnfa *, struct colormap *, struct smalldfa *); +static void freedfa(struct dfa *); +static unsigned hash(unsigned *, int); +static struct sset *initialize(struct vars *, struct dfa *, chr *); +static struct sset *miss(struct vars *, struct dfa *, struct sset *, pcolor, chr *, chr *); +static int lacon(struct vars *, struct cnfa *, chr *, pcolor); +static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *); +static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *); + + +/* + * regexec - match regular expression + */ +int +regexec(regex_t *re, + const chr *string, + size_t nmatch, + regmatch_t pmatch[], + int flags) +{ + rm_detail_t det; + size_t nLen = 0; + chr* s2 = (chr*) string; + + if (string && *string) + { + while(*++s2); + } + + nLen = ((s2 - string) / sizeof(chr)); + + return wx_regexec(re, string, nLen, &det, nmatch, pmatch, flags); +} +int +wx_regexec(regex_t *re, + const chr *string, + size_t len, + rm_detail_t *details, + size_t nmatch, + regmatch_t pmatch[], + int flags) +{ + struct vars var; + register struct vars *v = &var; + int st; + size_t n; + int backref; + +#define LOCALMAT 20 + regmatch_t mat[LOCALMAT]; + +#define LOCALMEM 40 + regoff_t mem[LOCALMEM]; + + /* sanity checks */ + if (re == NULL || string == NULL || re->re_magic != REMAGIC) + return REG_INVARG; + if (re->re_csize != sizeof(chr)) + return REG_MIXED; + + /* setup */ + v->re = re; + v->g = (struct guts *) re->re_guts; + if ((v->g->cflags & REG_EXPECT) && details == NULL) + return REG_INVARG; + if (v->g->info & REG_UIMPOSSIBLE) + return REG_NOMATCH; + backref = (v->g->info & REG_UBACKREF) ? 1 : 0; + v->eflags = flags; + if (v->g->cflags & REG_NOSUB) + nmatch = 0; /* override client */ + v->nmatch = nmatch; + if (backref) + { + /* need work area */ + if (v->g->nsub + 1 <= LOCALMAT) + v->pmatch = mat; + else + v->pmatch = (regmatch_t *) MALLOC((v->g->nsub + 1) * + sizeof(regmatch_t)); + if (v->pmatch == NULL) + return REG_ESPACE; + v->nmatch = v->g->nsub + 1; + } + else + v->pmatch = pmatch; + v->details = details; + v->start = (chr *) string; + v->stop = (chr *) string + len; + v->err = 0; + if (backref) + { + /* need retry memory */ + assert(v->g->ntree >= 0); + n = (size_t) v->g->ntree; + if (n <= LOCALMEM) + v->mem = mem; + else + v->mem = (regoff_t *) MALLOC(n * sizeof(regoff_t)); + if (v->mem == NULL) + { + if (v->pmatch != pmatch && v->pmatch != mat) + FREE(v->pmatch); + return REG_ESPACE; + } + } + else + v->mem = NULL; + + /* do it */ + assert(v->g->tree != NULL); + if (backref) + st = cfind(v, &v->g->tree->cnfa, &v->g->cmap); + else + st = find(v, &v->g->tree->cnfa, &v->g->cmap); + + /* copy (portion of) match vector over if necessary */ + if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) + { + zapsubs(pmatch, nmatch); + n = (nmatch < v->nmatch) ? nmatch : v->nmatch; + memcpy(VS(pmatch), VS(v->pmatch), n * sizeof(regmatch_t)); + } + + /* clean up */ + if (v->pmatch != pmatch && v->pmatch != mat) + FREE(v->pmatch); + if (v->mem != NULL && v->mem != mem) + FREE(v->mem); + return st; +} + +/* + * find - find a match for the main NFA (no-complications case) + */ +static int +find(struct vars * v, + struct cnfa * cnfa, + struct colormap * cm) +{ + struct dfa *s; + struct dfa *d; + chr *begin; + chr *end = NULL; + chr *cold; + chr *open; /* open and close of range of possible + * starts */ + chr *close; + int hitend; + int shorter = (v->g->tree->flags & SHORTER) ? 1 : 0; + + /* first, a shot with the search RE */ + s = newdfa(v, &v->g->search, cm, &v->dfa1); + assert(!(ISERR() && s != NULL)); + NOERR(); + MDEBUG(("\nsearch at %ld\n", LOFF(v->start))); + cold = NULL; + close = shortest(v, s, v->start, v->start, v->stop, &cold, (int *) NULL); + freedfa(s); + NOERR(); + if (v->g->cflags & REG_EXPECT) + { + assert(v->details != NULL); + if (cold != NULL) + v->details->rm_extend.rm_so = OFF(cold); + else + v->details->rm_extend.rm_so = OFF(v->stop); + v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */ + } + if (close == NULL) /* not found */ + return REG_NOMATCH; + if (v->nmatch == 0) /* found, don't need exact location */ + return REG_OKAY; + + /* find starting point and match */ + assert(cold != NULL); + open = cold; + cold = NULL; + MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close))); + d = newdfa(v, cnfa, cm, &v->dfa1); + assert(!(ISERR() && d != NULL)); + NOERR(); + for (begin = open; begin <= close; begin++) + { + MDEBUG(("\nfind trying at %ld\n", LOFF(begin))); + if (shorter) + end = shortest(v, d, begin, begin, v->stop, + (chr **) NULL, &hitend); + else + end = longest(v, d, begin, v->stop, &hitend); + NOERR(); + if (hitend && cold == NULL) + cold = begin; + if (end != NULL) + break; /* NOTE BREAK OUT */ + } + assert(end != NULL); /* search RE succeeded so loop should */ + freedfa(d); + + /* and pin down details */ + assert(v->nmatch > 0); + v->pmatch[0].rm_so = OFF(begin); + v->pmatch[0].rm_eo = OFF(end); + if (v->g->cflags & REG_EXPECT) + { + if (cold != NULL) + v->details->rm_extend.rm_so = OFF(cold); + else + v->details->rm_extend.rm_so = OFF(v->stop); + v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */ + } + if (v->nmatch == 1) /* no need for submatches */ + return REG_OKAY; + + /* submatches */ + zapsubs(v->pmatch, v->nmatch); + return dissect(v, v->g->tree, begin, end); +} + +/* + * cfind - find a match for the main NFA (with complications) + */ +static int +cfind(struct vars * v, + struct cnfa * cnfa, + struct colormap * cm) +{ + struct dfa *s; + struct dfa *d; + chr *cold; + int ret; + + s = newdfa(v, &v->g->search, cm, &v->dfa1); + NOERR(); + d = newdfa(v, cnfa, cm, &v->dfa2); + if (ISERR()) + { + assert(d == NULL); + freedfa(s); + return v->err; + } + + ret = cfindloop(v, cnfa, cm, d, s, &cold); + + freedfa(d); + freedfa(s); + NOERR(); + if (v->g->cflags & REG_EXPECT) + { + assert(v->details != NULL); + if (cold != NULL) + v->details->rm_extend.rm_so = OFF(cold); + else + v->details->rm_extend.rm_so = OFF(v->stop); + v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */ + } + return ret; +} + +/* + * cfindloop - the heart of cfind + */ +static int +cfindloop(struct vars * v, + struct cnfa * cnfa, + struct colormap * cm, + struct dfa * d, + struct dfa * s, + chr **coldp) /* where to put coldstart pointer */ +{ + chr *begin; + chr *end; + chr *cold; + chr *open; /* open and close of range of possible + * starts */ + chr *close; + chr *estart; + chr *estop; + int er; + int shorter = v->g->tree->flags & SHORTER; + int hitend; + + assert(d != NULL && s != NULL); + cold = NULL; + close = v->start; + do + { + MDEBUG(("\ncsearch at %ld\n", LOFF(close))); + close = shortest(v, s, close, close, v->stop, &cold, (int *) NULL); + if (close == NULL) + break; /* NOTE BREAK */ + assert(cold != NULL); + open = cold; + cold = NULL; + MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close))); + for (begin = open; begin <= close; begin++) + { + MDEBUG(("\ncfind trying at %ld\n", LOFF(begin))); + estart = begin; + estop = v->stop; + for (;;) + { + if (shorter) + end = shortest(v, d, begin, estart, + estop, (chr **) NULL, &hitend); + else + end = longest(v, d, begin, estop, + &hitend); + if (hitend && cold == NULL) + cold = begin; + if (end == NULL) + break; /* NOTE BREAK OUT */ + MDEBUG(("tentative end %ld\n", LOFF(end))); + zapsubs(v->pmatch, v->nmatch); + zapmem(v, v->g->tree); + er = cdissect(v, v->g->tree, begin, end); + if (er == REG_OKAY) + { + if (v->nmatch > 0) + { + v->pmatch[0].rm_so = OFF(begin); + v->pmatch[0].rm_eo = OFF(end); + } + *coldp = cold; + return REG_OKAY; + } + if (er != REG_NOMATCH) + { + ERR(er); + return er; + } + if ((shorter) ? end == estop : end == begin) + { + /* no point in trying again */ + *coldp = cold; + return REG_NOMATCH; + } + /* go around and try again */ + if (shorter) + estart = end + 1; + else + estop = end - 1; + } + } + } while (close < v->stop); + + *coldp = cold; + return REG_NOMATCH; +} + +/* + * zapsubs - initialize the subexpression matches to "no match" + */ +static void +zapsubs(regmatch_t *p, + size_t n) +{ + size_t i; + + for (i = n - 1; i > 0; i--) + { + p[i].rm_so = -1; + p[i].rm_eo = -1; + } +} + +/* + * zapmem - initialize the retry memory of a subtree to zeros + */ +static void +zapmem(struct vars * v, + struct subre * t) +{ + if (t == NULL) + return; + + assert(v->mem != NULL); + v->mem[t->retry] = 0; + if (t->op == '(') + { + assert(t->subno > 0); + v->pmatch[t->subno].rm_so = -1; + v->pmatch[t->subno].rm_eo = -1; + } + + if (t->left != NULL) + zapmem(v, t->left); + if (t->right != NULL) + zapmem(v, t->right); +} + +/* + * subset - set any subexpression relevant to a successful subre + */ +static void +subset(struct vars * v, + struct subre * sub, + chr *begin, + chr *end) +{ + int n = sub->subno; + + assert(n > 0); + if ((size_t) n >= v->nmatch) + return; + + MDEBUG(("setting %d\n", n)); + v->pmatch[n].rm_so = OFF(begin); + v->pmatch[n].rm_eo = OFF(end); +} + +/* + * dissect - determine subexpression matches (uncomplicated case) + */ +static int /* regexec return code */ +dissect(struct vars * v, + struct subre * t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ +{ + assert(t != NULL); + MDEBUG(("dissect %ld-%ld\n", LOFF(begin), LOFF(end))); + + switch (t->op) + { + case '=': /* terminal node */ + assert(t->left == NULL && t->right == NULL); + return REG_OKAY; /* no action, parent did the work */ + break; + case '|': /* alternation */ + assert(t->left != NULL); + return altdissect(v, t, begin, end); + break; + case 'b': /* back ref -- shouldn't be calling us! */ + return REG_ASSERT; + break; + case '.': /* concatenation */ + assert(t->left != NULL && t->right != NULL); + return condissect(v, t, begin, end); + break; + case '(': /* capturing */ + assert(t->left != NULL && t->right == NULL); + assert(t->subno > 0); + subset(v, t, begin, end); + return dissect(v, t->left, begin, end); + break; + default: + return REG_ASSERT; + break; + } +} + +/* + * condissect - determine concatenation subexpression matches (uncomplicated) + */ +static int /* regexec return code */ +condissect(struct vars * v, + struct subre * t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ +{ + struct dfa *d; + struct dfa *d2; + chr *mid; + int i; + int shorter = (t->left->flags & SHORTER) ? 1 : 0; + chr *stop = (shorter) ? end : begin; + + assert(t->op == '.'); + assert(t->left != NULL && t->left->cnfa.nstates > 0); + assert(t->right != NULL && t->right->cnfa.nstates > 0); + + d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1); + NOERR(); + d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &v->dfa2); + if (ISERR()) + { + assert(d2 == NULL); + freedfa(d); + return v->err; + } + + /* pick a tentative midpoint */ + if (shorter) + mid = shortest(v, d, begin, begin, end, (chr **) NULL, + (int *) NULL); else - return(lmatcher(g, (char *)string, nmatch, pmatch, eflags)); + mid = longest(v, d, begin, end, (int *) NULL); + if (mid == NULL) + { + freedfa(d); + freedfa(d2); + return REG_ASSERT; + } + MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); + + /* iterate until satisfaction or failure */ + while (longest(v, d2, mid, end, (int *) NULL) != end) + { + /* that midpoint didn't work, find a new one */ + if (mid == stop) + { + /* all possibilities exhausted! */ + MDEBUG(("no midpoint!\n")); + freedfa(d); + freedfa(d2); + return REG_ASSERT; + } + if (shorter) + mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL, + (int *) NULL); + else + mid = longest(v, d, begin, mid - 1, (int *) NULL); + if (mid == NULL) + { + /* failed to find a new one! */ + MDEBUG(("failed midpoint!\n")); + freedfa(d); + freedfa(d2); + return REG_ASSERT; + } + MDEBUG(("new midpoint %ld\n", LOFF(mid))); + } + + /* satisfaction */ + MDEBUG(("successful\n")); + freedfa(d); + freedfa(d2); + i = dissect(v, t->left, begin, mid); + if (i != REG_OKAY) + return i; + return dissect(v, t->right, mid, end); +} + +/* + * altdissect - determine alternative subexpression matches (uncomplicated) + */ +static int /* regexec return code */ +altdissect(struct vars * v, + struct subre * t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ +{ + struct dfa *d; + int i; + + assert(t != NULL); + assert(t->op == '|'); + + for (i = 0; t != NULL; t = t->right, i++) + { + MDEBUG(("trying %dth\n", i)); + assert(t->left != NULL && t->left->cnfa.nstates > 0); + d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1); + if (ISERR()) + return v->err; + if (longest(v, d, begin, end, (int *) NULL) == end) + { + MDEBUG(("success\n")); + freedfa(d); + return dissect(v, t->left, begin, end); + } + freedfa(d); + } + return REG_ASSERT; /* none of them matched?!? */ +} + +/* + * cdissect - determine subexpression matches (with complications) + * The retry memory stores the offset of the trial midpoint from begin, + * plus 1 so that 0 uniquely means "clean slate". + */ +static int /* regexec return code */ +cdissect(struct vars * v, + struct subre * t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ +{ + int er; + + assert(t != NULL); + MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op)); + + switch (t->op) + { + case '=': /* terminal node */ + assert(t->left == NULL && t->right == NULL); + return REG_OKAY; /* no action, parent did the work */ + break; + case '|': /* alternation */ + assert(t->left != NULL); + return caltdissect(v, t, begin, end); + break; + case 'b': /* back ref -- shouldn't be calling us! */ + assert(t->left == NULL && t->right == NULL); + return cbrdissect(v, t, begin, end); + break; + case '.': /* concatenation */ + assert(t->left != NULL && t->right != NULL); + return ccondissect(v, t, begin, end); + break; + case '(': /* capturing */ + assert(t->left != NULL && t->right == NULL); + assert(t->subno > 0); + er = cdissect(v, t->left, begin, end); + if (er == REG_OKAY) + subset(v, t, begin, end); + return er; + break; + default: + return REG_ASSERT; + break; + } } + +/* + * ccondissect - concatenation subexpression matches (with complications) + * The retry memory stores the offset of the trial midpoint from begin, + * plus 1 so that 0 uniquely means "clean slate". + */ +static int /* regexec return code */ +ccondissect(struct vars * v, + struct subre * t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ +{ + struct dfa *d; + struct dfa *d2; + chr *mid; + int er; + + assert(t->op == '.'); + assert(t->left != NULL && t->left->cnfa.nstates > 0); + assert(t->right != NULL && t->right->cnfa.nstates > 0); + + if (t->left->flags & SHORTER) /* reverse scan */ + return crevdissect(v, t, begin, end); + + d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + if (ISERR()) + return v->err; + d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC); + if (ISERR()) + { + freedfa(d); + return v->err; + } + MDEBUG(("cconcat %d\n", t->retry)); + + /* pick a tentative midpoint */ + if (v->mem[t->retry] == 0) + { + mid = longest(v, d, begin, end, (int *) NULL); + if (mid == NULL) + { + freedfa(d); + freedfa(d2); + return REG_NOMATCH; + } + MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); + v->mem[t->retry] = (mid - begin) + 1; + } + else + { + mid = begin + (v->mem[t->retry] - 1); + MDEBUG(("working midpoint %ld\n", LOFF(mid))); + } + + /* iterate until satisfaction or failure */ + for (;;) + { + /* try this midpoint on for size */ + er = cdissect(v, t->left, begin, mid); + if (er == REG_OKAY && + longest(v, d2, mid, end, (int *) NULL) == end && + (er = cdissect(v, t->right, mid, end)) == + REG_OKAY) + break; /* NOTE BREAK OUT */ + if (er != REG_OKAY && er != REG_NOMATCH) + { + freedfa(d); + freedfa(d2); + return er; + } + + /* that midpoint didn't work, find a new one */ + if (mid == begin) + { + /* all possibilities exhausted */ + MDEBUG(("%d no midpoint\n", t->retry)); + freedfa(d); + freedfa(d2); + return REG_NOMATCH; + } + mid = longest(v, d, begin, mid - 1, (int *) NULL); + if (mid == NULL) + { + /* failed to find a new one */ + MDEBUG(("%d failed midpoint\n", t->retry)); + freedfa(d); + freedfa(d2); + return REG_NOMATCH; + } + MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid))); + v->mem[t->retry] = (mid - begin) + 1; + zapmem(v, t->left); + zapmem(v, t->right); + } + + /* satisfaction */ + MDEBUG(("successful\n")); + freedfa(d); + freedfa(d2); + return REG_OKAY; +} + +/* + * crevdissect - determine backref shortest-first subexpression matches + * The retry memory stores the offset of the trial midpoint from begin, + * plus 1 so that 0 uniquely means "clean slate". + */ +static int /* regexec return code */ +crevdissect(struct vars * v, + struct subre * t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ +{ + struct dfa *d; + struct dfa *d2; + chr *mid; + int er; + + assert(t->op == '.'); + assert(t->left != NULL && t->left->cnfa.nstates > 0); + assert(t->right != NULL && t->right->cnfa.nstates > 0); + assert(t->left->flags & SHORTER); + + /* concatenation -- need to split the substring between parts */ + d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + if (ISERR()) + return v->err; + d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC); + if (ISERR()) + { + freedfa(d); + return v->err; + } + MDEBUG(("crev %d\n", t->retry)); + + /* pick a tentative midpoint */ + if (v->mem[t->retry] == 0) + { + mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL); + if (mid == NULL) + { + freedfa(d); + freedfa(d2); + return REG_NOMATCH; + } + MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); + v->mem[t->retry] = (mid - begin) + 1; + } + else + { + mid = begin + (v->mem[t->retry] - 1); + MDEBUG(("working midpoint %ld\n", LOFF(mid))); + } + + /* iterate until satisfaction or failure */ + for (;;) + { + /* try this midpoint on for size */ + er = cdissect(v, t->left, begin, mid); + if (er == REG_OKAY && + longest(v, d2, mid, end, (int *) NULL) == end && + (er = cdissect(v, t->right, mid, end)) == + REG_OKAY) + break; /* NOTE BREAK OUT */ + if (er != REG_OKAY && er != REG_NOMATCH) + { + freedfa(d); + freedfa(d2); + return er; + } + + /* that midpoint didn't work, find a new one */ + if (mid == end) + { + /* all possibilities exhausted */ + MDEBUG(("%d no midpoint\n", t->retry)); + freedfa(d); + freedfa(d2); + return REG_NOMATCH; + } + mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL, (int *) NULL); + if (mid == NULL) + { + /* failed to find a new one */ + MDEBUG(("%d failed midpoint\n", t->retry)); + freedfa(d); + freedfa(d2); + return REG_NOMATCH; + } + MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid))); + v->mem[t->retry] = (mid - begin) + 1; + zapmem(v, t->left); + zapmem(v, t->right); + } + + /* satisfaction */ + MDEBUG(("successful\n")); + freedfa(d); + freedfa(d2); + return REG_OKAY; +} + +/* + * cbrdissect - determine backref subexpression matches + */ +static int /* regexec return code */ +cbrdissect(struct vars * v, + struct subre * t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ +{ + int i; + int n = t->subno; + size_t len; + chr *paren; + chr *p; + chr *stop; + int min = t->min; + int max = t->max; + + assert(t != NULL); + assert(t->op == 'b'); + assert(n >= 0); + assert((size_t) n < v->nmatch); + + MDEBUG(("cbackref n%d %d{%d-%d}\n", t->retry, n, min, max)); + + if (v->pmatch[n].rm_so == -1) + return REG_NOMATCH; + paren = v->start + v->pmatch[n].rm_so; + len = v->pmatch[n].rm_eo - v->pmatch[n].rm_so; + + /* no room to maneuver -- retries are pointless */ + if (v->mem[t->retry]) + return REG_NOMATCH; + v->mem[t->retry] = 1; + + /* special-case zero-length string */ + if (len == 0) + { + if (begin == end) + return REG_OKAY; + return REG_NOMATCH; + } + + /* and too-short string */ + assert(end >= begin); + if ((size_t) (end - begin) < len) + return REG_NOMATCH; + stop = end - len; + + /* count occurrences */ + i = 0; + for (p = begin; p <= stop && (i < max || max == INFINITY); p += len) + { + if ((*v->g->compare) (paren, p, len) != 0) + break; + i++; + } + MDEBUG(("cbackref found %d\n", i)); + + /* and sort it out */ + if (p != end) /* didn't consume all of it */ + return REG_NOMATCH; + if (min <= i && (i <= max || max == INFINITY)) + return REG_OKAY; + return REG_NOMATCH; /* out of range */ +} + +/* + * caltdissect - determine alternative subexpression matches (w. complications) + */ +static int /* regexec return code */ +caltdissect(struct vars * v, + struct subre * t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ +{ + struct dfa *d; + int er; + +#define UNTRIED 0 /* not yet tried at all */ +#define TRYING 1 /* top matched, trying submatches */ +#define TRIED 2 /* top didn't match or submatches + * exhausted */ + + if (t == NULL) + return REG_NOMATCH; + assert(t->op == '|'); + if (v->mem[t->retry] == TRIED) + return caltdissect(v, t->right, begin, end); + + MDEBUG(("calt n%d\n", t->retry)); + assert(t->left != NULL); + + if (v->mem[t->retry] == UNTRIED) + { + d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + if (ISERR()) + return v->err; + if (longest(v, d, begin, end, (int *) NULL) != end) + { + freedfa(d); + v->mem[t->retry] = TRIED; + return caltdissect(v, t->right, begin, end); + } + freedfa(d); + MDEBUG(("calt matched\n")); + v->mem[t->retry] = TRYING; + } + + er = cdissect(v, t->left, begin, end); + if (er != REG_NOMATCH) + return er; + + v->mem[t->retry] = TRIED; + return caltdissect(v, t->right, begin, end); +} + + + +#include "rege_dfa.c" diff --git a/src/regex/regfree.c b/src/regex/regfree.c index 52d09f6e66..569bd204aa 100644 --- a/src/regex/regfree.c +++ b/src/regex/regfree.c @@ -1,41 +1,57 @@ -#if defined(__MWERKS__) && !defined(__MACH__) -typedef long off_t ; -#else -#include -#endif -#include -#include -#include "regex.h" +/* + * regfree - free an RE + * + * 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. + * + * 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. + * + * 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 + * 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; + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * $Header: /projects/cvsroot/pgsql-server/src/backend/regex/regfree.c,v 1.17 2003/08/04 00:43:21 momjian Exp $ + * + * + * You might think that this could be incorporated into regcomp.c, and + * that would be a reasonable idea... except that this is a generic + * function (with a generic name), applicable to all compiled REs + * regardless of the size of their characters, whereas the stuff in + * regcomp.c gets compiled once per character size. + */ + +#include "regguts.h" -#include "utils.h" -#include "regex2.h" /* - - regfree - free everything - = extern void regfree(regex_t *); + * pg_regfree - free an RE (generic function, punts to RE-specific function) + * + * Ignoring invocation with NULL is a convenience. */ void -regfree(preg) -regex_t *preg; +regfree(regex_t *re) +{ wx_regfree(re); } +void +wx_regfree(regex_t *re) { - register struct re_guts *g; - - if (preg->re_magic != MAGIC1) /* oops */ - return; /* nice to complain, but hard */ - - g = preg->re_g; - if (g == NULL || g->magic != MAGIC2) /* oops again */ + if (re == NULL) return; - preg->re_magic = 0; /* mark it invalid */ - g->magic = 0; /* mark it invalid */ - - if (g->strip != NULL) - free((char *)g->strip); - if (g->sets != NULL) - free((char *)g->sets); - if (g->setbits != NULL) - free((char *)g->setbits); - if (g->must != NULL) - free(g->must); - free((char *)g); + (*((struct fns *) re->re_fns)->free) (re); }