summaryrefslogtreecommitdiffstats
path: root/generic/regexec.c
diff options
context:
space:
mode:
Diffstat (limited to 'generic/regexec.c')
-rw-r--r--generic/regexec.c1049
1 files changed, 583 insertions, 466 deletions
diff --git a/generic/regexec.c b/generic/regexec.c
index 3b9af3e..6d12827 100644
--- a/generic/regexec.c
+++ b/generic/regexec.c
@@ -107,13 +107,13 @@ struct vars {
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 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 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)
@@ -126,21 +126,20 @@ struct vars {
/* 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 cnfa *const, struct colormap *const, struct dfa *const, struct dfa *const, chr **const);
-static void zapSubexpressions(regmatch_t *const, const size_t);
-static void zapSubtree(struct vars *const, struct subre *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 dissect(struct vars *const, struct subre *, chr *const, chr *const);
-static int concatenationDissect(struct vars *const, struct subre *const, chr *const, chr *const);
-static int alternationDissect(struct vars *const, struct subre *, chr *const, chr *const);
-static inline int complicatedDissect(struct vars *const, struct subre *const, chr *const, chr *const);
-static int complicatedCapturingDissect(struct vars *const, struct subre *const, chr *const, chr *const);
-static int complicatedConcatenationDissect(struct vars *const, struct subre *const, chr *const, chr *const);
-static int complicatedReversedDissect(struct vars *const, struct subre *const, chr *const, chr *const);
-static int complicatedBackrefDissect(struct vars *const, struct subre *const, chr *const, chr *const);
-static int complicatedAlternationDissect(struct vars *const, struct subre *, 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);
@@ -174,10 +173,11 @@ exec(
AllocVars(v);
int st, backref;
size_t n;
+ size_t i;
#define LOCALMAT 20
regmatch_t mat[LOCALMAT];
-#define LOCALMEM 40
- regoff_t mem[LOCALMEM];
+#define LOCALDFAS 40
+ struct dfa *subdfas[LOCALDFAS];
/*
* Sanity checks.
@@ -235,28 +235,20 @@ exec(
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);
- }
- FreeVars(v);
- return REG_ESPACE;
- }
- } else {
- v->mem = NULL;
+ 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);
+ FreeVars(v);
+ return REG_ESPACE;
}
+ for (i = 0; i < n; i++)
+ v->subdfas[i] = NULL;
/*
* Do it.
@@ -274,7 +266,7 @@ exec(
*/
if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) {
- zapSubexpressions(pmatch, nmatch);
+ zapallsubs(pmatch, nmatch);
n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t));
}
@@ -286,14 +278,35 @@ exec(
if (v->pmatch != pmatch && v->pmatch != mat) {
FREE(v->pmatch);
}
- if (v->mem != NULL && v->mem != mem) {
- FREE(v->mem);
+ 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;
}
/*
+ - 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 *);
*/
@@ -357,7 +370,10 @@ simpleFind(
} else {
end = longest(v, d, begin, v->stop, &hitend);
}
- NOERR();
+ if (ISERR()) {
+ freeDFA(d);
+ return v->err;
+ }
if (hitend && cold == NULL) {
cold = begin;
}
@@ -388,11 +404,11 @@ simpleFind(
}
/*
- * Submatches.
+ * Find submatches.
*/
- zapSubexpressions(v->pmatch, v->nmatch);
- return dissect(v, v->g->tree, begin, end);
+ zapallsubs(v->pmatch, v->nmatch);
+ return cdissect(v, v->g->tree, begin, end);
}
/*
@@ -488,9 +504,8 @@ complicatedFindLoop(
}
MDEBUG(("tentative end %ld\n", LOFF(end)));
- zapSubexpressions(v->pmatch, v->nmatch);
- zapSubtree(v, v->g->tree);
- er = complicatedDissect(v, v->g->tree, begin, 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);
@@ -501,6 +516,7 @@ complicatedFindLoop(
}
if (er != REG_NOMATCH) {
ERR(er);
+ *coldp = cold;
return er;
}
if ((shorter) ? end == estop : end == begin) {
@@ -525,11 +541,11 @@ complicatedFindLoop(
}
/*
- - zapSubexpressions - initialize the subexpression matches to "no match"
- ^ static void zapSubexpressions(regmatch_t *, size_t);
+ - zapallsubs - initialize all subexpression matches to "no match"
+ ^ static void zapallsubs(regmatch_t *, size_t);
*/
static void
-zapSubexpressions(
+zapallsubs(
regmatch_t *const p,
const size_t n)
{
@@ -542,36 +558,33 @@ zapSubexpressions(
}
/*
- - zapSubtree - initialize the retry memory of a subtree to zeros
- ^ static void zapSubtree(struct vars *, struct subre *);
+ - zaptreesubs - initialize subexpressions within subtree to "no match"
+ ^ static void zaptreesubs(struct vars *, struct subre *);
*/
static void
-zapSubtree(
+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;
+ 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) {
- zapSubtree(v, t->left);
+ zaptreesubs(v, t->left);
}
if (t->right != NULL) {
- zapSubtree(v, t->right);
+ zaptreesubs(v, t->right);
}
}
/*
- - subset - set any subexpression relevant to a successful subre
+ - subset - set subexpression match data for a successful subre
^ static void subset(struct vars *, struct subre *, chr *, chr *);
*/
static void
@@ -594,247 +607,91 @@ subset(
}
/*
- - 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(
- struct vars *const v,
+cdissect(
+ struct vars *v,
struct subre *t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
+ chr *begin, /* beginning of relevant substring */
+ chr *end) /* end of same */
{
-#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
- restart:
-#endif
- 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 */
- case '|': /* alternation */
- assert(t->left != NULL);
- return alternationDissect(v, t, begin, end);
- case 'b': /* back ref -- shouldn't be calling us! */
- return REG_ASSERT;
- case '.': /* concatenation */
- assert(t->left != NULL && t->right != NULL);
- return concatenationDissect(v, t, begin, end);
- case '(': /* capturing */
- assert(t->left != NULL && t->right == NULL);
- assert(t->subno > 0);
- subset(v, t, begin, end);
-#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
- t = t->left;
- goto restart;
-#else
- return dissect(v, t->left, begin, end);
-#endif
- default:
- return REG_ASSERT;
- }
-}
-
-/*
- - concatenationDissect - determine concatenation subexpression matches
- - (uncomplicated)
- ^ static int concatenationDissect(struct vars *, struct subre *, chr *, chr *);
- */
-static int /* regexec return code */
-concatenationDissect(
- struct vars *const v,
- struct subre *const t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
-{
- struct dfa *d, *d2;
- chr *mid;
- int i;
- int shorter = (t->left->flags&SHORTER) ? 1 : 0;
- chr *stop = (shorter) ? end : begin;
-
- assert(t->op == '.');
- assert(t->left != NULL && t->left->cnfa.nstates > 0);
- assert(t->right != NULL && t->right->cnfa.nstates > 0);
-
- d = newDFA(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
- NOERR();
- d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, &v->dfa2);
- if (ISERR()) {
- assert(d2 == NULL);
- freeDFA(d);
- return v->err;
- }
-
- /*
- * Pick a tentative midpoint.
- */
-
- if (shorter) {
- mid = shortest(v, d, begin, begin, end, NULL, NULL);
- } else {
- mid = longest(v, d, begin, end, 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, 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, NULL, NULL);
- } else {
- mid = longest(v, d, begin, mid-1, NULL);
- }
- if (mid == NULL) {
- /*
- * Failed to find a new one!
- */
-
- MDEBUG(("failed midpoint!\n"));
- freeDFA(d);
- freeDFA(d2);
- return REG_ASSERT;
- }
- MDEBUG(("new midpoint %ld\n", LOFF(mid)));
- }
-
- /*
- * Satisfaction.
- */
-
- MDEBUG(("successful\n"));
- freeDFA(d);
- freeDFA(d2);
- i = dissect(v, t->left, begin, mid);
- if (i != REG_OKAY) {
- return i;
- }
- return dissect(v, t->right, mid, end);
-}
-
-/*
- - alternationDissect - determine alternative subexpression matches (uncomplicated)
- ^ static int alternationDissect(struct vars *, struct subre *, chr *, chr *);
- */
-static int /* regexec return code */
-alternationDissect(
- struct vars *const v,
- struct subre *t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
-{
- int i;
-
- assert(t != NULL);
- assert(t->op == '|');
-
- for (i = 0; t != NULL; t = t->right, i++) {
- struct dfa *d;
+ int er;
- 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, NULL) == end) {
- MDEBUG(("success\n"));
- freeDFA(d);
- return dissect(v, t->left, begin, end);
- }
- freeDFA(d);
- }
- return REG_ASSERT; /* none of them matched?!? */
-}
-
-/*
- - complicatedDissect - 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 complicatedDissect(struct vars *, struct subre *, chr *, chr *);
- */
-static inline int /* regexec return code */
-complicatedDissect(
- struct vars *const v,
- struct subre *const t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
-{
assert(t != NULL);
- MDEBUG(("complicatedDissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));
+ MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));
switch (t->op) {
case '=': /* terminal node */
assert(t->left == NULL && t->right == NULL);
- return REG_OKAY; /* no action, parent did the work */
- case '|': /* alternation */
- assert(t->left != NULL);
- return complicatedAlternationDissect(v, t, begin, end);
- case 'b': /* back ref -- shouldn't be calling us! */
+ er = REG_OKAY; /* no action, parent did the work */
+ break;
+ case 'b': /* back reference */
assert(t->left == NULL && t->right == NULL);
- return complicatedBackrefDissect(v, t, begin, end);
+ er = cbrdissect(v, t, begin, end);
+ break;
case '.': /* concatenation */
assert(t->left != NULL && t->right != NULL);
- return complicatedConcatenationDissect(v, t, begin, end);
+ 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);
- return complicatedCapturingDissect(v, t, begin, end);
+ er = cdissect(v, t->left, begin, end);
+ if (er == REG_OKAY) {
+ subset(v, t, begin, end);
+ }
+ break;
default:
- return REG_ASSERT;
+ er = REG_ASSERT;
+ break;
}
-}
-static int /* regexec return code */
-complicatedCapturingDissect(
- struct vars *const v,
- struct subre *const t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
-{
- int er = complicatedDissect(v, t->left, begin, end);
+ /*
+ * 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));
- if (er == REG_OKAY) {
- subset(v, t, begin, end);
- }
return er;
}
/*
- - complicatedConcatenationDissect - 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 complicatedConcatenationDissect(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 */
-complicatedConcatenationDissect(
- struct vars *const v,
- struct subre *const t,
- chr *const begin, /* beginning of relevant substring */
- chr *const 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, *d2;
chr *mid;
@@ -842,39 +699,23 @@ complicatedConcatenationDissect(
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));
- if (t->left->flags&SHORTER) { /* reverse scan */
- return complicatedReversedDissect(v, t, begin, end);
- }
+ d = getsubdfa(v, t->left);
+ NOERR();
+ d2 = getsubdfa(v, t->right);
+ NOERR();
- 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));
+ MDEBUG(("cConcat %d\n", t->id));
/*
* Pick a tentative midpoint.
*/
-
- if (v->mem[t->retry] == 0) {
- mid = longest(v, d, begin, end, 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)));
+ 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.
@@ -886,24 +727,20 @@ complicatedConcatenationDissect(
*/
if (longest(v, d2, mid, end, NULL) == end) {
- int er = complicatedDissect(v, t->left, begin, mid);
+ int er = cdissect(v, t->left, begin, mid);
if (er == REG_OKAY) {
- er = complicatedDissect(v, t->right, mid, end);
+ er = cdissect(v, t->right, mid, end);
if (er == REG_OKAY) {
/*
* Satisfaction.
*/
MDEBUG(("successful\n"));
- freeDFA(d);
- freeDFA(d2);
return REG_OKAY;
}
}
- if ((er != REG_OKAY) && (er != REG_NOMATCH)) {
- freeDFA(d);
- freeDFA(d2);
+ if (er != REG_NOMATCH) {
return er;
}
}
@@ -917,9 +754,7 @@ complicatedConcatenationDissect(
* All possibilities exhausted.
*/
- MDEBUG(("%d no midpoint\n", t->retry));
- freeDFA(d);
- freeDFA(d2);
+ MDEBUG(("%d no midpoint\n", t->id));
return REG_NOMATCH;
}
mid = longest(v, d, begin, mid-1, NULL);
@@ -928,31 +763,25 @@ complicatedConcatenationDissect(
* Failed to find a new one.
*/
- MDEBUG(("%d failed midpoint\n", t->retry));
- freeDFA(d);
- freeDFA(d2);
+ MDEBUG(("%d failed midpoint\n", t->id));
return REG_NOMATCH;
}
- MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
- v->mem[t->retry] = (mid - begin) + 1;
- zapSubtree(v, t->left);
- zapSubtree(v, t->right);
+ MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));
+ zaptreesubs(v, t->left);
+ zaptreesubs(v, t->right);
}
}
/*
- - complicatedReversedDissect - 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 complicatedReversedDissect(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 */
-complicatedReversedDissect(
- struct vars *const v,
- struct subre *const t,
- chr *const begin, /* beginning of relevant substring */
- chr *const 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, *d2;
chr *mid;
@@ -962,38 +791,22 @@ complicatedReversedDissect(
assert(t->right != NULL && t->right->cnfa.nstates > 0);
assert(t->left->flags&SHORTER);
- /*
- * Concatenation -- need to split the substring between parts.
- */
+ d = getsubdfa(v, t->left);
+ NOERR();
+ d2 = getsubdfa(v, t->right);
+ NOERR();
- d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
- if (ISERR()) {
- return v->err;
- }
- d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
- if (ISERR()) {
- freeDFA(d);
- return v->err;
- }
- MDEBUG(("cRev %d\n", t->retry));
+ MDEBUG(("crevcon %d\n", t->id));
/*
* Pick a tentative midpoint.
*/
- if (v->mem[t->retry] == 0) {
- mid = shortest(v, d, begin, begin, end, NULL, 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)));
+ 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.
@@ -1005,24 +818,20 @@ complicatedReversedDissect(
*/
if (longest(v, d2, mid, end, NULL) == end) {
- int er = complicatedDissect(v, t->left, begin, mid);
+ int er = cdissect(v, t->left, begin, mid);
if (er == REG_OKAY) {
- er = complicatedDissect(v, t->right, mid, end);
+ er = cdissect(v, t->right, mid, end);
if (er == REG_OKAY) {
/*
* Satisfaction.
*/
MDEBUG(("successful\n"));
- freeDFA(d);
- freeDFA(d2);
return REG_OKAY;
}
}
- if (er != REG_OKAY && er != REG_NOMATCH) {
- freeDFA(d);
- freeDFA(d2);
+ if (er != REG_NOMATCH) {
return er;
}
}
@@ -1036,9 +845,7 @@ complicatedReversedDissect(
* All possibilities exhausted.
*/
- MDEBUG(("%d no midpoint\n", t->retry));
- freeDFA(d);
- freeDFA(d2);
+ MDEBUG(("%d no midpoint\n", t->id));
return REG_NOMATCH;
}
mid = shortest(v, d, begin, mid+1, end, NULL, NULL);
@@ -1047,164 +854,474 @@ complicatedReversedDissect(
* Failed to find a new one.
*/
- MDEBUG(("%d failed midpoint\n", t->retry));
- freeDFA(d);
- freeDFA(d2);
+ MDEBUG(("%d failed midpoint\n", t->id));
return REG_NOMATCH;
}
- MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
- v->mem[t->retry] = (mid - begin) + 1;
- zapSubtree(v, t->left);
- zapSubtree(v, t->right);
+ MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));
+ zaptreesubs(v, t->left);
+ zaptreesubs(v, t->right);
}
}
/*
- - complicatedBackrefDissect - determine backref subexpression matches
- ^ static int complicatedBackrefDissect(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 */
-complicatedBackrefDissect(
- struct vars *const v,
- struct subre *const t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
+cbrdissect(
+ struct vars *v,
+ struct subre *t,
+ chr *begin, /* beginning of relevant substring */
+ chr *end) /* end of same */
{
- int i, n = t->subno, min = t->min, max = t->max;
- chr *paren, *p, *stop;
- size_t len;
+ 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->retry, n, min, max));
+ 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;
}
- paren = v->start + v->pmatch[n].rm_so;
- len = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
+ brstring = v->start + v->pmatch[n].rm_so;
+ brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
- /*
- * No room to maneuver -- retries are pointless.
- */
-
- if (v->mem[t->retry]) {
+ /* 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;
}
- v->mem[t->retry] = 1;
-
- /*
- * Special-case zero-length string.
- */
-
- if (len == 0) {
- if (begin == end) {
+ if (begin == end) {
+ /* matches only if zero repetitions are okay */
+ if (min == 0) {
+ MDEBUG(("cbackref matched trivially\n"));
return REG_OKAY;
}
return REG_NOMATCH;
}
/*
- * And too-short string.
+ * check target length to see if it could possibly be an allowed number of
+ * repetitions of brstring
*/
- assert(end >= begin);
- if ((size_t)(end - begin) < len) {
+ 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;
}
- stop = end - len;
- /*
- * Count occurrences.
- */
+ 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);
- i = 0;
- for (p = begin; p <= stop && (i < max || max == DUPINF); p += len) {
- if (v->g->compare(paren, p, len) != 0) {
- break;
+ 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;
+ }
}
- i++;
+
+ t = t->right;
}
- MDEBUG(("cbackref found %d\n", i));
+
+ 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);
/*
- * And sort it out.
+ * 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;
+ }
- if (p != end) { /* didn't consume all of it */
- return REG_NOMATCH;
+ /*
+ * 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;
}
- if (min <= i && (i <= max || max == DUPINF)) {
- return REG_OKAY;
+ 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--;
+ }
}
- return REG_NOMATCH; /* out of range */
+
+ /* all possibilities exhausted */
+ MDEBUG(("%d failed\n", t->id));
+ FREE(endpts);
+ return REG_NOMATCH;
}
/*
- - complicatedAlternationDissect - determine alternative subexpression matches (w.
- - complications)
- ^ static int complicatedAlternationDissect(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 */
-complicatedAlternationDissect(
- struct vars *const v,
- struct subre *t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
+creviterdissect(struct vars * v,
+ struct subre * t,
+ chr *begin, /* beginning of relevant substring */
+ chr *end) /* end of same */
{
- 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 */
+ 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);
-#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
- if (0) {
- doRight:
- t = t->right;
- }
-#endif
- if (t == NULL) {
- return REG_NOMATCH;
+ /*
+ * 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;
}
- assert(t->op == '|');
- if (v->mem[t->retry] == TRIED) {
- goto doRight;
+
+ /*
+ * 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));
- MDEBUG(("cAlt n%d\n", t->retry));
- assert(t->left != NULL);
+ /*
+ * 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.
+ */
- if (v->mem[t->retry] == UNTRIED) {
- struct dfa *d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
+ /* 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;
+ }
- if (ISERR()) {
- return v->err;
+ k++;
+ limit = endpts[k - 1];
+ continue;
}
- if (longest(v, d, begin, end, NULL) != end) {
- freeDFA(d);
- v->mem[t->retry] = TRIED;
- goto doRight;
+
+ /*
+ * 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;
}
- freeDFA(d);
- MDEBUG(("cAlt matched\n"));
- v->mem[t->retry] = TRYING;
- }
- er = complicatedDissect(v, t->left, begin, end);
- if (er != REG_NOMATCH) {
- 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--;
+ }
}
- v->mem[t->retry] = TRIED;
-#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
- goto doRight;
-#else
- doRight:
- return complicatedAlternationDissect(v, t->right, begin, end);
-#endif
+ /* all possibilities exhausted */
+ MDEBUG(("%d failed\n", t->id));
+ FREE(endpts);
+ return REG_NOMATCH;
}
#include "rege_dfa.c"
generated by cgit v0.12 at 2024-11-18 09:58:46 (GMT)