diff options
Diffstat (limited to 'generic/regexec.c')
| -rw-r--r-- | generic/regexec.c | 2017 |
1 files changed, 1157 insertions, 860 deletions
diff --git a/generic/regexec.c b/generic/regexec.c index 41d49bd..128d439 100644 --- a/generic/regexec.c +++ b/generic/regexec.c @@ -2,20 +2,20 @@ * re_*exec and friends - match REs * * 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. - * + * thanks all of them. + * * Redistribution and use in source and binary forms -- with or without * modification -- are permitted for any purpose, provided that * redistributions in source form retain this entire copyright notice and * indicate the origin and nature of any modifications. - * - * I'd appreciate being given credit for this package in the documentation - * of software which uses it, but that is not a requirement. - * + * + * I'd appreciate being given credit for this package in the documentation of + * software which uses it, but that is not a requirement. + * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL @@ -26,1013 +26,1310 @@ * 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. - * */ #include "regguts.h" +/* + * Lazy-DFA representation. + */ - -/* lazy-DFA representation */ struct arcp { /* "pointer" to an outarc */ - struct sset *ss; - color co; + 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 */ + 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((void*)(bv), (void*)((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 */ + 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 */ +/* + * 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]; + 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. + */ - -/* 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; + 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) */ + struct dfa **subdfas; /* per-subre DFAs */ + struct smalldfa dfa1; + struct smalldfa dfa2; }; -#define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */ +#define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */ #define ISERR() VISERR(v) -#define VERR(vv,e) (((vv)->err) ? (vv)->err : ((vv)->err = (e))) -#define ERR(e) VERR(v, e) /* record an error */ +#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 */ /* =====^!^===== begin forwards =====^!^===== */ /* automatically gathered by fwd; do not hand-edit */ /* === regexec.c === */ -int exec _ANSI_ARGS_((regex_t *, CONST chr *, size_t, rm_detail_t *, size_t, regmatch_t [], int)); -static int find _ANSI_ARGS_((struct vars *, struct cnfa *, struct colormap *)); -static int cfind _ANSI_ARGS_((struct vars *, struct cnfa *, struct colormap *)); -static int cfindloop _ANSI_ARGS_((struct vars *, struct cnfa *, struct colormap *, struct dfa *, struct dfa *, chr **)); -static VOID zapsubs _ANSI_ARGS_((regmatch_t *, size_t)); -static VOID zapmem _ANSI_ARGS_((struct vars *, struct subre *)); -static VOID subset _ANSI_ARGS_((struct vars *, struct subre *, chr *, chr *)); -static int dissect _ANSI_ARGS_((struct vars *, struct subre *, chr *, chr *)); -static int condissect _ANSI_ARGS_((struct vars *, struct subre *, chr *, chr *)); -static int altdissect _ANSI_ARGS_((struct vars *, struct subre *, chr *, chr *)); -static int cdissect _ANSI_ARGS_((struct vars *, struct subre *, chr *, chr *)); -static int ccondissect _ANSI_ARGS_((struct vars *, struct subre *, chr *, chr *)); -static int crevdissect _ANSI_ARGS_((struct vars *, struct subre *, chr *, chr *)); -static int cbrdissect _ANSI_ARGS_((struct vars *, struct subre *, chr *, chr *)); -static int caltdissect _ANSI_ARGS_((struct vars *, struct subre *, chr *, chr *)); +int exec(regex_t *, const chr *, size_t, rm_detail_t *, size_t, regmatch_t [], int); +static struct dfa *getsubdfa(struct vars *, struct subre *); +static int simpleFind(struct vars *const, struct cnfa *const, struct colormap *const); +static int complicatedFind(struct vars *const, struct cnfa *const, struct colormap *const); +static int complicatedFindLoop(struct vars *const, struct cnfa *const, struct colormap *const, struct dfa *const, struct dfa *const, chr **const); +static void zapallsubs(regmatch_t *const, const size_t); +static void zaptreesubs(struct vars *const, struct subre *const); +static void subset(struct vars *const, struct subre *const, chr *const, chr *const); +static int cdissect(struct vars *, struct subre *, chr *, chr *); +static int ccondissect(struct vars *, struct subre *, chr *, chr *); +static int crevcondissect(struct vars *, struct subre *, chr *, chr *); +static int cbrdissect(struct vars *, struct subre *, chr *, chr *); +static int caltdissect(struct vars *, struct subre *, chr *, chr *); +static int citerdissect(struct vars *, struct subre *, chr *, chr *); +static int creviterdissect(struct vars *, struct subre *, chr *, chr *); /* === rege_dfa.c === */ -static chr *longest _ANSI_ARGS_((struct vars *, struct dfa *, chr *, chr *, int *)); -static chr *shortest _ANSI_ARGS_((struct vars *, struct dfa *, chr *, chr *, chr *, chr **, int *)); -static chr *lastcold _ANSI_ARGS_((struct vars *, struct dfa *)); -static struct dfa *newdfa _ANSI_ARGS_((struct vars *, struct cnfa *, struct colormap *, struct smalldfa *)); -static VOID freedfa _ANSI_ARGS_((struct dfa *)); -static unsigned hash _ANSI_ARGS_((unsigned *, int)); -static struct sset *initialize _ANSI_ARGS_((struct vars *, struct dfa *, chr *)); -static struct sset *miss _ANSI_ARGS_((struct vars *, struct dfa *, struct sset *, pcolor, chr *, chr *)); -static int lacon _ANSI_ARGS_((struct vars *, struct cnfa *, chr *, pcolor)); -static struct sset *getvacant _ANSI_ARGS_((struct vars *, struct dfa *, chr *, chr *)); -static struct sset *pickss _ANSI_ARGS_((struct vars *, struct dfa *, chr *, chr *)); +static chr *longest(struct vars *const, struct dfa *const, chr *const, chr *const, int *const); +static chr *shortest(struct vars *const, struct dfa *const, chr *const, chr *const, chr *const, chr **const, int *const); +static chr *lastCold(struct vars *const, struct dfa *const); +static struct dfa *newDFA(struct vars *const, struct cnfa *const, struct colormap *const, struct smalldfa *); +static void freeDFA(struct dfa *const); +static unsigned hash(unsigned *const, const int); +static struct sset *initialize(struct vars *const, struct dfa *const, chr *const); +static struct sset *miss(struct vars *const, struct dfa *const, struct sset *const, const pcolor, chr *const, chr *const); +static int checkLAConstraint(struct vars *const, struct cnfa *const, chr *const, const pcolor); +static struct sset *getVacantSS(struct vars *const, struct dfa *const, chr *const, chr *const); +static struct sset *pickNextSS(struct vars *const, struct dfa *const, chr *const, chr *const); /* automatically gathered by fwd; do not hand-edit */ /* =====^!^===== end forwards =====^!^===== */ - - - + /* - exec - match regular expression - ^ int exec(regex_t *, CONST chr *, size_t, rm_detail_t *, + ^ int exec(regex_t *, const chr *, size_t, rm_detail_t *, ^ size_t, regmatch_t [], int); */ int -exec(re, string, len, details, nmatch, pmatch, flags) -regex_t *re; -CONST chr *string; -size_t len; -rm_detail_t *details; -size_t nmatch; -regmatch_t pmatch[]; -int flags; +exec( + 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®_EXPECT) && details == NULL) - return REG_INVARG; - if (v->g->info®_UIMPOSSIBLE) - return REG_NOMATCH; - backref = (v->g->info®_UBACKREF) ? 1 : 0; - v->eflags = flags; - if (v->g->cflags®_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)); + AllocVars(v); + int st, backref; + size_t n; + size_t i; +#define LOCALMAT 20 + regmatch_t mat[LOCALMAT]; +#define LOCALDFAS 40 + struct dfa *subdfas[LOCALDFAS]; + + /* + * Sanity checks. + */ + + if (re == NULL || string == NULL || re->re_magic != REMAGIC) { + FreeVars(v); + return REG_INVARG; + } + if (re->re_csize != sizeof(chr)) { + FreeVars(v); + return REG_MIXED; + } + + /* + * Setup. + */ + + v->re = re; + v->g = (struct guts *)re->re_guts; + if ((v->g->cflags®_EXPECT) && details == NULL) { + FreeVars(v); + return REG_INVARG; + } + if (v->g->info®_UIMPOSSIBLE) { + FreeVars(v); + return REG_NOMATCH; + } + backref = (v->g->info®_UBACKREF) ? 1 : 0; + v->eflags = flags; + if (v->g->cflags®_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)); } - - /* clean up */ + if (v->pmatch == NULL) { + FreeVars(v); + 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; + assert(v->g->ntree >= 0); + n = (size_t) v->g->ntree; + if (n <= LOCALDFAS) + v->subdfas = subdfas; + else + v->subdfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *)); + if (v->subdfas == NULL) { if (v->pmatch != pmatch && v->pmatch != mat) - FREE(v->pmatch); - if (v->mem != NULL && v->mem != mem) - FREE(v->mem); - return st; + FREE(v->pmatch); + FreeVars(v); + return REG_ESPACE; + } + for (i = 0; i < n; i++) + v->subdfas[i] = NULL; + + /* + * Do it. + */ + + assert(v->g->tree != NULL); + if (backref) { + st = complicatedFind(v, &v->g->tree->cnfa, &v->g->cmap); + } else { + st = simpleFind(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) { + zapallsubs(pmatch, nmatch); + n = (nmatch < v->nmatch) ? nmatch : v->nmatch; + memcpy((void*)(pmatch), (void*)(v->pmatch), n*sizeof(regmatch_t)); + } + + /* + * Clean up. + */ + + if (v->pmatch != pmatch && v->pmatch != mat) { + FREE(v->pmatch); + } + n = (size_t) v->g->ntree; + for (i = 0; i < n; i++) { + if (v->subdfas[i] != NULL) + freeDFA(v->subdfas[i]); + } + if (v->subdfas != subdfas) + FREE(v->subdfas); + FreeVars(v); + return st; } - + /* - - find - find a match for the main NFA (no-complications case) - ^ static int find(struct vars *, struct cnfa *, struct colormap *); + - getsubdfa - create or re-fetch the DFA for a subre node + * We only need to create the DFA once per overall regex execution. + * The DFA will be freed by the cleanup step in exec(). + */ +static struct dfa * +getsubdfa(struct vars * v, + struct subre * t) +{ + if (v->subdfas[t->id] == NULL) { + v->subdfas[t->id] = newDFA(v, &t->cnfa, &v->g->cmap, DOMALLOC); + if (ISERR()) + return NULL; + } + return v->subdfas[t->id]; +} + +/* + - simpleFind - find a match for the main NFA (no-complications case) + ^ static int simpleFind(struct vars *, struct cnfa *, struct colormap *); */ static int -find(v, cnfa, cm) -struct vars *v; -struct cnfa *cnfa; -struct colormap *cm; +simpleFind( + struct vars *const v, + struct cnfa *const cnfa, + struct colormap *const 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®_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 */ + struct dfa *s, *d; + chr *begin, *end = NULL; + chr *cold; + chr *open, *close; /* Open and close of range of possible + * starts */ + 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, NULL); + freeDFA(s); + NOERR(); + if (v->g->cflags®_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); } - 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 */ + 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, NULL, &hitend); + } else { + end = longest(v, d, begin, v->stop, &hitend); + } + if (ISERR()) { + freeDFA(d); + return v->err; } - 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®_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 (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®_EXPECT) { + if (cold != NULL) { + v->details->rm_extend.rm_so = OFF(cold); + } else { + v->details->rm_extend.rm_so = OFF(v->stop); } - if (v->nmatch == 1) /* no need for submatches */ - return REG_OKAY; + 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); -} + /* + * Find submatches. + */ + zapallsubs(v->pmatch, v->nmatch); + return cdissect(v, v->g->tree, begin, end); +} + /* - - cfind - find a match for the main NFA (with complications) - ^ static int cfind(struct vars *, struct cnfa *, struct colormap *); + - complicatedFind - find a match for the main NFA (with complications) + ^ static int complicatedFind(struct vars *, struct cnfa *, struct colormap *); */ static int -cfind(v, cnfa, cm) -struct vars *v; -struct cnfa *cnfa; -struct colormap *cm; +complicatedFind( + struct vars *const v, + struct cnfa *const cnfa, + struct colormap *const 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®_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 */ + struct dfa *s, *d; + chr *cold = NULL; /* silence gcc 4 warning */ + 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 = complicatedFindLoop(v, cnfa, cm, d, s, &cold); + + freeDFA(d); + freeDFA(s); + NOERR(); + if (v->g->cflags®_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); } - return ret; + v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */ + } + return ret; } - + /* - - cfindloop - the heart of cfind - ^ static int cfindloop(struct vars *, struct cnfa *, struct colormap *, + - complicatedFindLoop - the heart of complicatedFind + ^ static int complicatedFindLoop(struct vars *, struct cnfa *, struct colormap *, ^ struct dfa *, struct dfa *, chr **); */ static int -cfindloop(v, cnfa, cm, d, s, coldp) -struct vars *v; -struct cnfa *cnfa; -struct colormap *cm; -struct dfa *d; -struct dfa *s; -chr **coldp; /* where to put coldstart pointer */ +complicatedFindLoop( + struct vars *const v, + struct cnfa *const cnfa, + struct colormap *const cm, + struct dfa *const d, + struct dfa *const s, + chr **const 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); + chr *begin, *end; + chr *cold; + chr *open, *close; /* Open and close of range of possible + * starts */ + chr *estart, *estop; + int er, hitend; + int shorter = v->g->tree->flags&SHORTER; + + 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, NULL); + if (close == NULL) { + break; /* NOTE BREAK */ + } + assert(cold != NULL); + open = cold; 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; - } + MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close))); + for (begin = open; begin <= close; begin++) { + MDEBUG(("\ncomplicatedFind trying at %ld\n", LOFF(begin))); + estart = begin; + estop = v->stop; + for (;;) { + if (shorter) { + end = shortest(v, d, begin, estart, estop, NULL, &hitend); + } else { + end = longest(v, d, begin, estop, &hitend); + } + if (hitend && cold == NULL) { + cold = begin; + } + if (end == NULL) { + break; /* NOTE BREAK OUT */ } - } while (close < v->stop); - *coldp = cold; - return REG_NOMATCH; -} + MDEBUG(("tentative end %ld\n", LOFF(end))); + zapallsubs(v->pmatch, v->nmatch); + 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); + *coldp = cold; + return er; + } + if ((shorter) ? end == estop : end == begin) { + break; + } + + /* + * 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 *, size_t); + - zapallsubs - initialize all subexpression matches to "no match" + ^ static void zapallsubs(regmatch_t *, size_t); */ -static VOID -zapsubs(p, n) -regmatch_t *p; -size_t n; +static void +zapallsubs( + regmatch_t *const p, + const size_t n) { - size_t i; + size_t i; - for (i = n-1; i > 0; i--) { - p[i].rm_so = -1; - p[i].rm_eo = -1; - } + 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 *, struct subre *); + - zaptreesubs - initialize subexpressions within subtree to "no match" + ^ static void zaptreesubs(struct vars *, struct subre *); */ -static VOID -zapmem(v, t) -struct vars *v; -struct subre *t; +static void +zaptreesubs( + struct vars *const v, + struct subre *const 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->op == '(') { + int n = t->subno; + assert(n > 0); + if ((size_t) n < v->nmatch) { + v->pmatch[n].rm_so = -1; + v->pmatch[n].rm_eo = -1; } - - if (t->left != NULL) - zapmem(v, t->left); - if (t->right != NULL) - zapmem(v, t->right); + } + + if (t->left != NULL) { + zaptreesubs(v, t->left); + } + if (t->right != NULL) { + zaptreesubs(v, t->right); + } } - + /* - - subset - set any subexpression relevant to a successful subre - ^ static VOID subset(struct vars *, struct subre *, chr *, chr *); + - subset - set subexpression match data for a successful subre + ^ static void subset(struct vars *, struct subre *, chr *, chr *); */ -static VOID -subset(v, sub, begin, end) -struct vars *v; -struct subre *sub; -chr *begin; -chr *end; +static void +subset( + struct vars *const v, + struct subre *const sub, + chr *const begin, + chr *const end) { - int n = sub->subno; + int n = sub->subno; - assert(n > 0); - if ((size_t)n >= v->nmatch) - return; + 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); + 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 dissect(struct vars *, struct subre *, chr *, chr *); + - cdissect - check backrefs and determine subexpression matches + * cdissect recursively processes a subre tree to check matching of backrefs + * and/or identify submatch boundaries for capture nodes. The proposed match + * runs from "begin" to "end" (not including "end"), and we are basically + * "dissecting" it to see where the submatches are. + * Before calling any level of cdissect, the caller must have run the node's + * DFA and found that the proposed substring satisfies the DFA. (We make + * the caller do that because in concatenation and iteration nodes, it's + * much faster to check all the substrings against the child DFAs before we + * recurse.) Also, caller must have cleared subexpression match data via + * zaptreesubs (or zapallsubs at the top level). + ^ static int cdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -dissect(v, t, begin, end) -struct vars *v; -struct subre *t; -chr *begin; /* beginning of relevant substring */ -chr *end; /* end of same */ +cdissect( + 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; + 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); + er = REG_OKAY; /* no action, parent did the work */ + break; + case 'b': /* back reference */ + assert(t->left == NULL && t->right == NULL); + er = cbrdissect(v, t, begin, end); + break; + case '.': /* concatenation */ + assert(t->left != NULL && t->right != NULL); + if (t->left->flags & SHORTER) /* reverse scan */ + er = crevcondissect(v, t, begin, end); + else + er = ccondissect(v, t, begin, end); + break; + case '|': /* alternation */ + assert(t->left != NULL); + er = caltdissect(v, t, begin, end); + break; + case '*': /* iteration */ + assert(t->left != NULL); + if (t->left->flags & SHORTER) /* reverse scan */ + er = creviterdissect(v, t, begin, end); + else + er = citerdissect(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); } + break; + default: + er = REG_ASSERT; + break; + } + + /* + * We should never have a match failure unless backrefs lurk below; + * otherwise, either caller failed to check the DFA, or there's some + * inconsistency between the DFA and the node's innards. + */ + assert(er != REG_NOMATCH || (t->flags & BACKR)); + + return er; } - + /* - - condissect - determine concatenation subexpression matches (uncomplicated) - ^ static int condissect(struct vars *, struct subre *, chr *, chr *); + - ccondissect - dissect match for concatenation node + ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -condissect(v, t, begin, end) -struct vars *v; -struct subre *t; -chr *begin; /* beginning of relevant substring */ -chr *end; /* end of same */ +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 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; + struct dfa *d, *d2; + chr *mid; + + 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)); + + d = getsubdfa(v, t->left); + NOERR(); + d2 = getsubdfa(v, t->right); + NOERR(); + + MDEBUG(("cConcat %d\n", t->id)); + + /* + * Pick a tentative midpoint. + */ + mid = longest(v, d, begin, end, (int *) NULL); + if (mid == NULL) { + return REG_NOMATCH; + } + MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); + + /* + * Iterate until satisfaction or failure. + */ + + for (;;) { + /* + * Try this midpoint on for size. + */ + + if (longest(v, d2, mid, end, NULL) == end) { + int er = cdissect(v, t->left, begin, mid); + + if (er == REG_OKAY) { + er = cdissect(v, t->right, mid, end); + if (er == REG_OKAY) { + /* + * Satisfaction. + */ + + MDEBUG(("successful\n")); + return REG_OKAY; + } + } + if (er != REG_NOMATCH) { + return er; + } } - /* pick a tentative midpoint */ - if (shorter) - mid = shortest(v, d, begin, begin, end, (chr **)NULL, - (int *)NULL); - else - 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))); + /* + * That midpoint didn't work, find a new one. + */ + + if (mid == begin) { + /* + * All possibilities exhausted. + */ + + MDEBUG(("%d no midpoint\n", t->id)); + return REG_NOMATCH; } + mid = longest(v, d, begin, mid-1, NULL); + if (mid == NULL) { + /* + * Failed to find a new one. + */ - /* 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); + MDEBUG(("%d failed midpoint\n", t->id)); + return REG_NOMATCH; + } + MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid))); + zaptreesubs(v, t->left); + zaptreesubs(v, t->right); + } } - + /* - - altdissect - determine alternative subexpression matches (uncomplicated) - ^ static int altdissect(struct vars *, struct subre *, chr *, chr *); + - crevcondissect - dissect match for concatenation node, shortest-first + ^ static int crevcondissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -altdissect(v, t, begin, end) -struct vars *v; -struct subre *t; -chr *begin; /* beginning of relevant substring */ -chr *end; /* end of same */ +crevcondissect( + struct vars *v, + struct subre *t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { - struct dfa *d; - int i; + struct dfa *d, *d2; + chr *mid; - assert(t != NULL); - assert(t->op == '|'); + 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); + + d = getsubdfa(v, t->left); + NOERR(); + d2 = getsubdfa(v, t->right); + NOERR(); + + MDEBUG(("crevcon %d\n", t->id)); + + /* + * Pick a tentative midpoint. + */ - 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); + mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL); + if (mid == NULL) { + return REG_NOMATCH; + } + MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); + + /* + * Iterate until satisfaction or failure. + */ + + for (;;) { + /* + * Try this midpoint on for size. + */ + + if (longest(v, d2, mid, end, NULL) == end) { + int er = cdissect(v, t->left, begin, mid); + + if (er == REG_OKAY) { + er = cdissect(v, t->right, mid, end); + if (er == REG_OKAY) { + /* + * Satisfaction. + */ + + MDEBUG(("successful\n")); + return REG_OKAY; } - freedfa(d); + } + if (er != REG_NOMATCH) { + return er; + } } - return REG_ASSERT; /* none of them matched?!? */ -} + /* + * That midpoint didn't work, find a new one. + */ + + if (mid == end) { + /* + * All possibilities exhausted. + */ + + MDEBUG(("%d no midpoint\n", t->id)); + return REG_NOMATCH; + } + mid = shortest(v, d, begin, mid+1, end, NULL, NULL); + if (mid == NULL) { + /* + * Failed to find a new one. + */ + + MDEBUG(("%d failed midpoint\n", t->id)); + return REG_NOMATCH; + } + MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid))); + zaptreesubs(v, t->left); + zaptreesubs(v, t->right); + } +} + /* - - 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 cdissect(struct vars *, struct subre *, chr *, chr *); + - cbrdissect - dissect match for backref node + ^ static int cbrdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -cdissect(v, t, begin, end) -struct vars *v; -struct subre *t; -chr *begin; /* beginning of relevant substring */ -chr *end; /* end of same */ +cbrdissect( + struct vars *v, + struct subre *t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { - int er; + int n = t->subno, min = t->min, max = t->max; + size_t numreps; + size_t tlen; + size_t brlen; + chr *brstring; + chr *p; + + 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->id, n, min, max)); + + /* get the backreferenced string */ + if (v->pmatch[n].rm_so == -1) { + return REG_NOMATCH; + } + brstring = v->start + v->pmatch[n].rm_so; + brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so; + + /* special cases for zero-length strings */ + if (brlen == 0) { + /* + * matches only if target is zero length, but any number of + * repetitions can be considered to be present + */ + if (begin == end && min <= max) { + MDEBUG(("cbackref matched trivially\n")); + return REG_OKAY; + } + return REG_NOMATCH; + } + if (begin == end) { + /* matches only if zero repetitions are okay */ + if (min == 0) { + MDEBUG(("cbackref matched trivially\n")); + return REG_OKAY; + } + return REG_NOMATCH; + } - assert(t != NULL); - MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op)); + /* + * check target length to see if it could possibly be an allowed number of + * repetitions of brstring + */ - 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; - } -} + assert(end > begin); + tlen = end - begin; + if (tlen % brlen != 0) + return REG_NOMATCH; + numreps = tlen / brlen; + if (numreps < (size_t)min || (numreps > (size_t)max && max != DUPINF)) + return REG_NOMATCH; + + /* okay, compare the actual string contents */ + p = begin; + while (numreps-- > 0) { + if ((*v->g->compare) (brstring, p, brlen) != 0) + return REG_NOMATCH; + p += brlen; + } + MDEBUG(("cbackref matched\n")); + return REG_OKAY; +} + /* - - 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 ccondissect(struct vars *, struct subre *, chr *, chr *); + - caltdissect - dissect match for alternation node + ^ static int caltdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -ccondissect(v, t, begin, end) -struct vars *v; -struct subre *t; -chr *begin; /* beginning of relevant substring */ -chr *end; /* end of same */ +caltdissect( + 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; + struct dfa *d; + int er; - assert(t->op == '.'); + /* We loop, rather than tail-recurse, to handle a chain of alternatives */ + while (t != NULL) { + 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); + MDEBUG(("calt n%d\n", t->id)); - 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))); + d = getsubdfa(v, t->left); + NOERR(); + if (longest(v, d, begin, end, (int *) NULL) == end) { + MDEBUG(("calt matched\n")); + er = cdissect(v, t->left, begin, end); + if (er != REG_NOMATCH) { + return er; + } } - /* 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); - } + t = t->right; + } - /* satisfaction */ - MDEBUG(("successful\n")); - freedfa(d); - freedfa(d2); - return REG_OKAY; + return REG_NOMATCH; } - + /* - - 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 crevdissect(struct vars *, struct subre *, chr *, chr *); + - citerdissect - dissect match for iteration node + ^ static int citerdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -crevdissect(v, t, begin, end) -struct vars *v; -struct subre *t; -chr *begin; /* beginning of relevant substring */ -chr *end; /* end of same */ +citerdissect(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; + struct dfa *d; + chr **endpts; + chr *limit; + int min_matches; + size_t max_matches; + int nverified; + int k; + int i; + int er; + + assert(t->op == '*'); + assert(t->left != NULL && t->left->cnfa.nstates > 0); + assert(!(t->left->flags & SHORTER)); + assert(begin <= end); + + /* + * If zero matches are allowed, and target string is empty, just declare + * victory. OTOH, if target string isn't empty, zero matches can't work + * so we pretend the min is 1. + */ + min_matches = t->min; + if (min_matches <= 0) { + if (begin == end) + return REG_OKAY; + min_matches = 1; + } + + /* + * We need workspace to track the endpoints of each sub-match. Normally + * we consider only nonzero-length sub-matches, so there can be at most + * end-begin of them. However, if min is larger than that, we will also + * consider zero-length sub-matches in order to find enough matches. + * + * For convenience, endpts[0] contains the "begin" pointer and we store + * sub-match endpoints in endpts[1..max_matches]. + */ + max_matches = end - begin; + if (max_matches > (size_t)t->max && t->max != DUPINF) + max_matches = t->max; + if (max_matches < (size_t)min_matches) + max_matches = min_matches; + endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *)); + if (endpts == NULL) + return REG_ESPACE; + endpts[0] = begin; + + d = getsubdfa(v, t->left); + if (ISERR()) { + FREE(endpts); + return v->err; + } + MDEBUG(("citer %d\n", t->id)); + + /* + * Our strategy is to first find a set of sub-match endpoints that are + * valid according to the child node's DFA, and then recursively dissect + * each sub-match to confirm validity. If any validity check fails, + * backtrack the last sub-match and try again. And, when we next try for + * a validity check, we need not recheck any successfully verified + * sub-matches that we didn't move the endpoints of. nverified remembers + * how many sub-matches are currently known okay. + */ + + /* initialize to consider first sub-match */ + nverified = 0; + k = 1; + limit = end; + + /* iterate until satisfaction or failure */ + while (k > 0) { + /* try to find an endpoint for the k'th sub-match */ + endpts[k] = longest(v, d, endpts[k - 1], limit, (int *) NULL); + if (endpts[k] == NULL) { + /* no match possible, so see if we can shorten previous one */ + k--; + goto backtrack; } - 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))); + MDEBUG(("%d: working endpoint %d: %ld\n", + t->id, k, LOFF(endpts[k]))); + + /* k'th sub-match can no longer be considered verified */ + if (nverified >= k) + nverified = k - 1; + + if (endpts[k] != end) { + /* haven't reached end yet, try another iteration if allowed */ + if ((size_t)k >= max_matches) { + /* must try to shorten some previous match */ + k--; + goto backtrack; + } + + /* reject zero-length match unless necessary to achieve min */ + if (endpts[k] == endpts[k - 1] && + (k >= min_matches || min_matches - k < end - endpts[k])) + goto backtrack; + + k++; + limit = end; + continue; } - /* 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; - } + /* + * We've identified a way to divide the string into k sub-matches + * that works so far as the child DFA can tell. If k is an allowed + * number of matches, start the slow part: recurse to verify each + * sub-match. We always have k <= max_matches, needn't check that. + */ + if (k < min_matches) + goto backtrack; + + MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k)); + + for (i = nverified + 1; i <= k; i++) { + zaptreesubs(v, t->left); + er = cdissect(v, t->left, endpts[i - 1], endpts[i]); + if (er == REG_OKAY) { + nverified = i; + continue; + } + if (er == REG_NOMATCH) + break; + /* oops, something failed */ + FREE(endpts); + 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; + if (i > k) { + /* satisfaction */ + MDEBUG(("%d successful\n", t->id)); + FREE(endpts); + return REG_OKAY; + } + + /* match failed to verify, so backtrack */ + + backtrack: + /* + * Must consider shorter versions of the current sub-match. However, + * we'll only ask for a zero-length match if necessary. + */ + while (k > 0) { + chr *prev_end = endpts[k - 1]; + + if (endpts[k] > prev_end) { + limit = endpts[k] - 1; + if (limit > prev_end || + (k < min_matches && min_matches - k >= end - prev_end)) { + /* break out of backtrack loop, continue the outer one */ + break; } - 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); + } + /* can't shorten k'th sub-match any more, consider previous one */ + k--; } + } - /* satisfaction */ - MDEBUG(("successful\n")); - freedfa(d); - freedfa(d2); - return REG_OKAY; + /* all possibilities exhausted */ + MDEBUG(("%d failed\n", t->id)); + FREE(endpts); + return REG_NOMATCH; } - + /* - - cbrdissect - determine backref subexpression matches - ^ static int cbrdissect(struct vars *, struct subre *, chr *, chr *); + - creviterdissect - dissect match for iteration node, shortest-first + ^ static int creviterdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -cbrdissect(v, t, begin, end) -struct vars *v; -struct subre *t; -chr *begin; /* beginning of relevant substring */ -chr *end; /* end of same */ +creviterdissect(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; + struct dfa *d; + chr **endpts; + chr *limit; + int min_matches; + size_t max_matches; + int nverified; + int k; + int i; + int er; + + assert(t->op == '*'); + assert(t->left != NULL && t->left->cnfa.nstates > 0); + assert(t->left->flags & SHORTER); + assert(begin <= end); + + /* + * If zero matches are allowed, and target string is empty, just declare + * victory. OTOH, if target string isn't empty, zero matches can't work + * so we pretend the min is 1. + */ + min_matches = t->min; + if (min_matches <= 0) { + if (begin == end) + return REG_OKAY; + min_matches = 1; + } + + /* + * We need workspace to track the endpoints of each sub-match. Normally + * we consider only nonzero-length sub-matches, so there can be at most + * end-begin of them. However, if min is larger than that, we will also + * consider zero-length sub-matches in order to find enough matches. + * + * For convenience, endpts[0] contains the "begin" pointer and we store + * sub-match endpoints in endpts[1..max_matches]. + */ + max_matches = end - begin; + if (max_matches > (size_t)t->max && t->max != DUPINF) + max_matches = t->max; + if (max_matches < (size_t)min_matches) + max_matches = min_matches; + endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *)); + if (endpts == NULL) + return REG_ESPACE; + endpts[0] = begin; + + d = getsubdfa(v, t->left); + if (ISERR()) { + FREE(endpts); + return v->err; + } + MDEBUG(("creviter %d\n", t->id)); + + /* + * Our strategy is to first find a set of sub-match endpoints that are + * valid according to the child node's DFA, and then recursively dissect + * each sub-match to confirm validity. If any validity check fails, + * backtrack the last sub-match and try again. And, when we next try for + * a validity check, we need not recheck any successfully verified + * sub-matches that we didn't move the endpoints of. nverified remembers + * how many sub-matches are currently known okay. + */ + + /* initialize to consider first sub-match */ + nverified = 0; + k = 1; + limit = begin; + + /* iterate until satisfaction or failure */ + while (k > 0) { + /* disallow zero-length match unless necessary to achieve min */ + if (limit == endpts[k - 1] && + limit != end && + (k >= min_matches || min_matches - k < end - limit)) + limit++; + + /* if this is the last allowed sub-match, it must reach to the end */ + if ((size_t)k >= max_matches) + limit = end; + + /* try to find an endpoint for the k'th sub-match */ + endpts[k] = shortest(v, d, endpts[k - 1], limit, end, + (chr **) NULL, (int *) NULL); + if (endpts[k] == NULL) { + /* no match possible, so see if we can lengthen previous one */ + k--; + goto backtrack; + } + MDEBUG(("%d: working endpoint %d: %ld\n", + t->id, k, LOFF(endpts[k]))); + + /* k'th sub-match can no longer be considered verified */ + if (nverified >= k) + nverified = k - 1; + + if (endpts[k] != end) { + /* haven't reached end yet, try another iteration if allowed */ + if ((size_t)k >= max_matches) { + /* must try to lengthen some previous match */ + k--; + goto backtrack; + } + + k++; + limit = endpts[k - 1]; + continue; } - /* 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++; + /* + * We've identified a way to divide the string into k sub-matches + * that works so far as the child DFA can tell. If k is an allowed + * number of matches, start the slow part: recurse to verify each + * sub-match. We always have k <= max_matches, needn't check that. + */ + if (k < min_matches) + goto backtrack; + + MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k)); + + for (i = nverified + 1; i <= k; i++) { + zaptreesubs(v, t->left); + er = cdissect(v, t->left, endpts[i - 1], endpts[i]); + if (er == REG_OKAY) { + nverified = i; + continue; + } + if (er == REG_NOMATCH) + break; + /* oops, something failed */ + FREE(endpts); + return er; } - 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 caltdissect(struct vars *, struct subre *, chr *, chr *); - */ -static int /* regexec return code */ -caltdissect(v, t, begin, end) -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); + if (i > k) { + /* satisfaction */ + MDEBUG(("%d successful\n", t->id)); + FREE(endpts); + return REG_OKAY; + } - MDEBUG(("calt n%d\n", t->retry)); - assert(t->left != NULL); + /* match failed to verify, so backtrack */ - 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; + backtrack: + /* + * Must consider longer versions of the current sub-match. + */ + while (k > 0) { + if (endpts[k] < end) { + limit = endpts[k] + 1; + /* break out of backtrack loop, continue the outer one */ + break; + } + /* can't lengthen k'th sub-match any more, consider previous one */ + k--; } + } - 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); + /* all possibilities exhausted */ + MDEBUG(("%d failed\n", t->id)); + FREE(endpts); + return REG_NOMATCH; } - - #include "rege_dfa.c" + +/* + * Local Variables: + * mode: c + * c-basic-offset: 4 + * fill-column: 78 + * End: + */ |