[1115587][0e0e150e49] Major fix for regexp handling of quantified backrefs.

Contributed by Tom Lane from the Postgres project.

1 files changed, 523 insertions, 417 deletions

diff --git a/generic/regexec.c b/generic/regexec.c
index 3b9af3e..e502ca5 100644
--- a/generic/regexec.c
+++ b/generic/regexec.c
@@ -107,7 +107,6 @@ 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 smalldfa dfa1;
     struct smalldfa dfa2;
 };
@@ -129,18 +128,16 @@ int exec(regex_t *, const chr *, size_t, rm_detail_t *, size_t, regmatch_t [], i
 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);
@@ -176,8 +173,6 @@ exec(
     size_t n;
 #define	LOCALMAT	20
     regmatch_t mat[LOCALMAT];
-#define	LOCALMEM	40
-    regoff_t mem[LOCALMEM];
 
     /*
      * Sanity checks.
@@ -235,28 +230,6 @@ 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;
-    }
 
     /*
      * Do it.
@@ -274,7 +247,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,9 +259,6 @@ exec(
     if (v->pmatch != pmatch && v->pmatch != mat) {
 	FREE(v->pmatch);
     }
-    if (v->mem != NULL && v->mem != mem) {
-	FREE(v->mem);
-    }
     FreeVars(v);
     return st;
 }
@@ -388,11 +358,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 +458,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);
@@ -525,11 +494,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 +511,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,243 +560,87 @@ subset(
 }
 
 /*
- - dissect - determine subexpression matches (uncomplicated case)
- ^ static int dissect(struct vars *, struct subre *, chr *, chr *);
- */
-static int			/* regexec return code */
-dissect(
-    struct vars *const v,
-    struct subre *t,
-    chr *const begin,		/* beginning of relevant substring */
-    chr *const 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 *);
+ - 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 */
-concatenationDissect(
+cdissect(
     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;
+    int er;
 
     assert(t != NULL);
-    assert(t->op == '|');
-
-    for (i = 0; t != NULL; t = t->right, i++) {
-	struct dfa *d;
-
-	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 - concatenation subexpression matches (with complications)
+ ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *);
  */
 static int			/* regexec return code */
-complicatedConcatenationDissect(
+ccondissect(
     struct vars *const v,
     struct subre *const t,
     chr *const begin,		/* beginning of relevant substring */
@@ -842,10 +652,7 @@ complicatedConcatenationDissect(
     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 complicatedReversedDissect(v, t, begin, end);
-    }
+    assert(!(t->left->flags & SHORTER));
 
     d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
     if (ISERR()) {
@@ -856,25 +663,18 @@ complicatedConcatenationDissect(
 	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) {
+	freeDFA(d);
+	freeDFA(d2);
+	return REG_NOMATCH;
     }
+    MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
 
     /*
      * Iterate until satisfaction or failure.
@@ -886,10 +686,10 @@ 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.
@@ -901,7 +701,7 @@ complicatedConcatenationDissect(
 		    return REG_OKAY;
 		}
 	    }
-	    if ((er != REG_OKAY) && (er != REG_NOMATCH)) {
+	    if (er != REG_NOMATCH) {
 		freeDFA(d);
 		freeDFA(d2);
 		return er;
@@ -917,7 +717,7 @@ complicatedConcatenationDissect(
 	     * All possibilities exhausted.
 	     */
 
-	    MDEBUG(("%d no midpoint\n", t->retry));
+	    MDEBUG(("%d no midpoint\n", t->id));
 	    freeDFA(d);
 	    freeDFA(d2);
 	    return REG_NOMATCH;
@@ -928,27 +728,23 @@ complicatedConcatenationDissect(
 	     * Failed to find a new one.
 	     */
 
-	    MDEBUG(("%d failed midpoint\n", t->retry));
+	    MDEBUG(("%d failed midpoint\n", t->id));
 	    freeDFA(d);
 	    freeDFA(d2);
 	    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(
+crevcondissect(
     struct vars *const v,
     struct subre *const t,
     chr *const begin,		/* beginning of relevant substring */
@@ -962,10 +758,6 @@ complicatedReversedDissect(
     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;
@@ -975,25 +767,19 @@ complicatedReversedDissect(
 	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) {
+	freeDFA(d);
+	freeDFA(d2);
+	return REG_NOMATCH;
     }
+    MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
 
     /*
      * Iterate until satisfaction or failure.
@@ -1005,10 +791,10 @@ 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.
@@ -1020,7 +806,7 @@ complicatedReversedDissect(
 		    return REG_OKAY;
 		}
 	    }
-	    if (er != REG_OKAY && er != REG_NOMATCH) {
+	    if (er != REG_NOMATCH) {
 		freeDFA(d);
 		freeDFA(d2);
 		return er;
@@ -1036,7 +822,7 @@ complicatedReversedDissect(
 	     * All possibilities exhausted.
 	     */
 
-	    MDEBUG(("%d no midpoint\n", t->retry));
+	    MDEBUG(("%d no midpoint\n", t->id));
 	    freeDFA(d);
 	    freeDFA(d2);
 	    return REG_NOMATCH;
@@ -1047,164 +833,484 @@ complicatedReversedDissect(
 	     * Failed to find a new one.
 	     */
 
-	    MDEBUG(("%d failed midpoint\n", t->retry));
+	    MDEBUG(("%d failed midpoint\n", t->id));
 	    freeDFA(d);
 	    freeDFA(d2);
 	    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(
+cbrdissect(
     struct vars *const v,
     struct subre *const t,
     chr *const begin,		/* beginning of relevant substring */
     chr *const 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;
+
+    /* 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;
+    }
 
     /*
-     * No room to maneuver -- retries are pointless.
+     * check target length to see if it could possibly be an allowed number of
+     * repetitions of brstring
      */
 
-    if (v->mem[t->retry]) {
+    assert(end > begin);
+    tlen = end - begin;
+    if (tlen % brlen != 0)
+	return REG_NOMATCH;
+    numreps = tlen / brlen;
+    if (numreps < min || (numreps > 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;
     }
-    v->mem[t->retry] = 1;
 
-    /*
-     * Special-case zero-length string.
-     */
+    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 *const v,
+    struct subre *t,
+    chr *const begin,		/* beginning of relevant substring */
+    chr *const end)		/* end of same */
+{
+    struct dfa *d;
+    int er;
 
-    if (len == 0) {
-	if (begin == end) {
-	    return REG_OKAY;
+    /* 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 = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
+	NOERR();
+	if (longest(v, d, begin, end, (int *) NULL) == end) {
+	    freeDFA(d);
+	    MDEBUG(("calt matched\n"));
+	    er = cdissect(v, t->left, begin, end);
+	    if (er != REG_NOMATCH) {
+		return er;
+	    }
 	}
-	return REG_NOMATCH;
+	freeDFA(d);
+
+	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);
+
     /*
-     * And too-short string.
+     * 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.
      */
-
-    assert(end >= begin);
-    if ((size_t)(end - begin) < len) {
-	return REG_NOMATCH;
+    min_matches = t->min;
+    if (min_matches <= 0) {
+	if (begin == end)
+	    return REG_OKAY;
+	min_matches = 1;
     }
-    stop = end - len;
 
     /*
-     * Count occurrences.
+     * 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 > t->max && t->max != DUPINF)
+	max_matches = t->max;
+    if (max_matches < min_matches)
+	max_matches = min_matches;
+    endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *));
+    if (endpts == NULL)
+	return REG_ESPACE;
+    endpts[0] = begin;
 
-    i = 0;
-    for (p = begin; p <= stop && (i < max || max == DUPINF); p += len) {
-	if (v->g->compare(paren, p, len) != 0) {
-	    break;
-	}
-	i++;
+    d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
+    if (ISERR()) {
+	FREE(endpts);
+	return v->err;
     }
-    MDEBUG(("cbackref found %d\n", i));
+    MDEBUG(("citer %d\n", t->id));
 
     /*
-     * And sort it out.
+     * 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 (p != end) {		/* didn't consume all of it */
-	return REG_NOMATCH;
-    }
-    if (min <= i && (i <= max || max == DUPINF)) {
-	return REG_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 (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 */
+	    freeDFA(d);
+	    FREE(endpts);
+	    return er;
+	}
+
+	if (i > k) {
+	    /* satisfaction */
+	    MDEBUG(("%d successful\n", t->id));
+	    freeDFA(d);
+	    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));
+    freeDFA(d);
+    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 > t->max && t->max != DUPINF)
+	max_matches = t->max;
+    if (max_matches < min_matches)
+	max_matches = min_matches;
+    endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *));
+    if (endpts == NULL)
+	return REG_ESPACE;
+    endpts[0] = begin;
+
+    d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
+    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 (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 (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) {
+
+	/*
+	 * 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 */
 	    freeDFA(d);
-	    v->mem[t->retry] = TRIED;
-	    goto doRight;
+	    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));
+	    freeDFA(d);
+	    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));
+    freeDFA(d);
+    FREE(endpts);
+    return REG_NOMATCH;
 }
 
 #include "rege_dfa.c"