/*
* 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.
*
* 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.
*/
#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((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 */
};
#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];
};
/*
* 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) */
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 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
*/
/* =====^!^===== begin forwards =====^!^===== */
/* automatically gathered by fwd; do not hand-edit */
/* === regexec.c === */
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 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(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 *,
^ size_t, regmatch_t [], int);
*/
int
exec(
regex_t *re,
const chr *string,
size_t len,
rm_detail_t *details,
size_t nmatch,
regmatch_t pmatch[],
int flags)
{
AllocVars(v);
int st, backref;
int n;
int 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));
}
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 = 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);
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 = 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;
}
/*
- 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, NULL);
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
simpleFind(
struct vars *const v,
struct cnfa *const cnfa,
struct colormap *const cm)
{
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);
}
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;
}
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);
}
v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */
}
if (v->nmatch == 1) { /* no need for submatches */
return REG_OKAY;
}
/*
* Find submatches.
*/
zapallsubs(v->pmatch, v->nmatch);
return cdissect(v, v->g->tree, begin, end);
}
/*
- complicatedFind - find a match for the main NFA (with complications)
^ static int complicatedFind(struct vars *, struct cnfa *, struct colormap *);
*/
static int
complicatedFind(
struct vars *const v,
struct cnfa *const cnfa,
struct colormap *const cm)
{
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, 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 */
}
return ret;
}
/*
- complicatedFindLoop - the heart of complicatedFind
^ static int complicatedFindLoop(struct vars *,
^ struct dfa *, struct dfa *, chr **);
*/
static int
complicatedFindLoop(
struct vars *const v,
struct dfa *const d,
struct dfa *const s,
chr **const coldp) /* where to put coldstart pointer */
{
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;
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 */
}
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;
}
/*
- zapallsubs - initialize all subexpression matches to "no match"
^ static void zapallsubs(regmatch_t *, size_t);
*/
static void
zapallsubs(
regmatch_t *const p,
const size_t n)
{
size_t i;
for (i = n-1; i > 0; i--) {
p[i].rm_so = -1;
p[i].rm_eo = -1;
}
}
/*
- zaptreesubs - initialize subexpressions within subtree to "no match"
^ static void zaptreesubs(struct vars *, struct subre *);
*/
static void
zaptreesubs(
struct vars *const v,
struct subre *const t)
{
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) {
zaptreesubs(v, t->left);
}
if (t->right != NULL) {
zaptreesubs(v, t->right);
}
}
/*
- subset - set subexpression match data for a successful subre
^ static void subset(struct vars *, struct subre *, chr *, chr *);
*/
static void
subset(
struct vars *const v,
struct subre *const sub,
chr *const begin,
chr *const 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);
}
/*
- 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 */
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);
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;
}
/*
- ccondissect - dissect match for concatenation node
^ static int ccondissect(struct vars *, struct subre *, chr *, chr *);
*/
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, *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;
}
}
/*
* 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.
*/
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);
}
}
/*
- crevcondissect - dissect match for concatenation node, shortest-first
^ static int crevcondissect(struct vars *, struct subre *, chr *, chr *);
*/
static int /* regexec return code */
crevcondissect(
struct vars *v,
struct subre *t,
chr *begin, /* beginning of relevant substring */
chr *end) /* end of same */
{
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(("crevcon %d\n", t->id));
/*
* Pick a tentative midpoint.
*/
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;
}
}
if (er != REG_NOMATCH) {
return er;
}
}
/*
* 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);
}
}
/*
- cbrdissect - dissect match for backref node
^ static int cbrdissect(struct vars *, struct subre *, chr *, chr *);
*/
static int /* regexec return code */
cbrdissect(
struct vars *v,
struct subre *t,
chr *begin, /* beginning of relevant substring */
chr *end) /* end of same */
{
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 == TCL_INDEX_NONE) {
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;
}
/*
* check target length to see if it could possibly be an allowed number of
* repetitions of brstring
*/
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;
}
/*
- caltdissect - dissect match for alternation node
^ static int caltdissect(struct vars *, struct subre *, chr *, chr *);
*/
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;
/* 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);
MDEBUG(("calt n%d\n", t->id));
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;
}
}
t = t->right;
}
return REG_NOMATCH;
}
/*
- citerdissect - dissect match for iteration node
^ static int citerdissect(struct vars *, struct subre *, chr *, chr *);
*/
static int /* regexec return code */
citerdissect(struct vars * v,
struct subre * t,
chr *begin, /* beginning of relevant substring */
chr *end) /* end of same */
{
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(("%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;
}
/*
* 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;
}
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;
}
}
/* can't shorten k'th sub-match any more, consider previous one */
k--;
}
}
/* all possibilities exhausted */
MDEBUG(("%d failed\n", t->id));
FREE(endpts);
return REG_NOMATCH;
}
/*
- creviterdissect - dissect match for iteration node, shortest-first
^ static int creviterdissect(struct vars *, struct subre *, chr *, chr *);
*/
static int /* regexec return code */
creviterdissect(struct vars * v,
struct subre * t,
chr *begin, /* beginning of relevant substring */
chr *end) /* end of same */
{
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;
}
/*
* 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;
}
if (i > k) {
/* satisfaction */
MDEBUG(("%d successful\n", t->id));
FREE(endpts);
return REG_OKAY;
}
/* match failed to verify, so backtrack */
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--;
}
}
/* 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:
*/