From e059535b05f7310bf3bad4d53cb343ecfe6aa801 Mon Sep 17 00:00:00 2001
From: "jan.nijtmans" <nijtmans@users.sourceforge.net>
Date: Fri, 29 Jan 2016 15:27:20 +0000
Subject: 8.5-with-8.6-regexp

---
 generic/regc_color.c  |   45 +-
 generic/regc_cvec.c   |    7 +-
 generic/regc_lex.c    |   65 ++-
 generic/regc_locale.c |    2 +-
 generic/regc_nfa.c    |  127 +++---
 generic/regcomp.c     |  190 +++++----
 generic/regcustom.h   |   22 +-
 generic/rege_dfa.c    |  241 +++++------
 generic/regerror.c    |    4 +-
 generic/regex.h       |   71 ++--
 generic/regexec.c     | 1132 +++++++++++++++++++++++++++----------------------
 generic/regfronts.c   |    6 +-
 generic/regguts.h     |   80 ++--
 13 files changed, 1078 insertions(+), 914 deletions(-)

diff --git a/generic/regc_color.c b/generic/regc_color.c
index 35e7904..92e0aad 100644
--- a/generic/regc_color.c
+++ b/generic/regc_color.c
@@ -37,7 +37,7 @@
 
 /*
  - initcm - set up new colormap
- ^ static VOID initcm(struct vars *, struct colormap *);
+ ^ static void initcm(struct vars *, struct colormap *);
  */
 static void
 initcm(
@@ -88,7 +88,7 @@ initcm(
 
 /*
  - freecm - free dynamically-allocated things in a colormap
- ^ static VOID freecm(struct colormap *);
+ ^ static void freecm(struct colormap *);
  */
 static void
 freecm(
@@ -116,7 +116,7 @@ freecm(
 
 /*
  - cmtreefree - free a non-terminal part of a colormap tree
- ^ static VOID cmtreefree(struct colormap *, union tree *, int);
+ ^ static void cmtreefree(struct colormap *, union tree *, int);
  */
 static void
 cmtreefree(
@@ -294,7 +294,7 @@ newcolor(
 
 /*
  - freecolor - free a color (must have no arcs or subcolor)
- ^ static VOID freecolor(struct colormap *, pcolor);
+ ^ static void freecolor(struct colormap *, pcolor);
  */
 static void
 freecolor(
@@ -327,7 +327,7 @@ freecolor(
 	    cm->free = cm->cd[cm->free].sub;
 	}
 	if (cm->free > 0) {
-	    assert(cm->free < cm->max);
+	    assert((size_t)cm->free < cm->max);
 	    pco = cm->free;
 	    nco = cm->cd[pco].sub;
 	    while (nco > 0) {
@@ -339,7 +339,7 @@ freecolor(
 		    nco = cm->cd[nco].sub;
 		    cm->cd[pco].sub = nco;
 		} else {
-		    assert(nco < cm->max);
+		    assert((size_t)nco < cm->max);
 		    pco = nco;
 		    nco = cm->cd[pco].sub;
 		}
@@ -429,7 +429,7 @@ newsub(
 
 /*
  - subrange - allocate new subcolors to this range of chrs, fill in arcs
- ^ static VOID subrange(struct vars *, pchr, pchr, struct state *,
+ ^ static void subrange(struct vars *, pchr, pchr, struct state *,
  ^ 	struct state *);
  */
 static void
@@ -477,7 +477,7 @@ subrange(
 
 /*
  - subblock - allocate new subcolors for one tree block of chrs, fill in arcs
- ^ static VOID subblock(struct vars *, pchr, struct state *, struct state *);
+ ^ static void subblock(struct vars *, pchr, struct state *, struct state *);
  */
 static void
 subblock(
@@ -582,7 +582,7 @@ subblock(
 
 /*
  - okcolors - promote subcolors to full colors
- ^ static VOID okcolors(struct nfa *, struct colormap *);
+ ^ static void okcolors(struct nfa *, struct colormap *);
  */
 static void
 okcolors(
@@ -643,7 +643,7 @@ okcolors(
 
 /*
  - colorchain - add this arc to the color chain of its color
- ^ static VOID colorchain(struct colormap *, struct arc *);
+ ^ static void colorchain(struct colormap *, struct arc *);
  */
 static void
 colorchain(
@@ -662,7 +662,7 @@ colorchain(
 
 /*
  - uncolorchain - delete this arc from the color chain of its color
- ^ static VOID uncolorchain(struct colormap *, struct arc *);
+ ^ static void uncolorchain(struct colormap *, struct arc *);
  */
 static void
 uncolorchain(
@@ -688,7 +688,7 @@ uncolorchain(
 
 /*
  - rainbow - add arcs of all full colors (but one) between specified states
- ^ static VOID rainbow(struct nfa *, struct colormap *, int, pcolor,
+ ^ static void rainbow(struct nfa *, struct colormap *, int, pcolor,
  ^ 	struct state *, struct state *);
  */
 static void
@@ -715,7 +715,7 @@ rainbow(
 /*
  - colorcomplement - add arcs of complementary colors
  * The calling sequence ought to be reconciled with cloneouts().
- ^ static VOID colorcomplement(struct nfa *, struct colormap *, int,
+ ^ static void colorcomplement(struct nfa *, struct colormap *, int,
  ^ 	struct state *, struct state *, struct state *);
  */
 static void
@@ -748,7 +748,7 @@ colorcomplement(
 
 /*
  - dumpcolors - debugging output
- ^ static VOID dumpcolors(struct colormap *, FILE *);
+ ^ static void dumpcolors(struct colormap *, FILE *);
  */
 static void
 dumpcolors(
@@ -777,18 +777,19 @@ dumpcolors(
 	    }
 
 	    /*
-	     * It's hard to do this more efficiently.
+	     * Unfortunately, it's hard to do this next bit more efficiently.
+	     *
+	     * Spencer's original coding has the loop iterating from CHR_MIN
+	     * to CHR_MAX, but that's utterly unusable for 32-bit chr, or
+	     * even 16-bit.  For debugging purposes it seems fine to print
+	     * only chr codes up to 1000 or so.
 	     */
 
-	    for (c=CHR_MIN ; c<CHR_MAX ; c++) {
+	    for (c=CHR_MIN ; c<1000 ; c++) {
 		if (GETCOLOR(cm, c) == co) {
 		    dumpchr(c, f);
 		}
 	    }
-	    assert(c == CHR_MAX);
-	    if (GETCOLOR(cm, c) == co) {
-		dumpchr(c, f);
-	    }
 	    fprintf(f, "\n");
 	}
     }
@@ -796,7 +797,7 @@ dumpcolors(
 
 /*
  - fillcheck - check proper filling of a tree
- ^ static VOID fillcheck(struct colormap *, union tree *, int, FILE *);
+ ^ static void fillcheck(struct colormap *, union tree *, int, FILE *);
  */
 static void
 fillcheck(
@@ -825,7 +826,7 @@ fillcheck(
 /*
  - dumpchr - print a chr
  * Kind of char-centric but works well enough for debug use.
- ^ static VOID dumpchr(pchr, FILE *);
+ ^ static void dumpchr(pchr, FILE *);
  */
 static void
 dumpchr(
diff --git a/generic/regc_cvec.c b/generic/regc_cvec.c
index 64f34cd..d450d3e 100644
--- a/generic/regc_cvec.c
+++ b/generic/regc_cvec.c
@@ -74,19 +74,20 @@ clearcvec(
 
 /*
  - addchr - add a chr to a cvec
- ^ static VOID addchr(struct cvec *, pchr);
+ ^ static void addchr(struct cvec *, pchr);
  */
 static void
 addchr(
     struct cvec *cv,		/* character vector */
     pchr c)			/* character to add */
 {
+    assert(cv->nchrs < cv->chrspace);
     cv->chrs[cv->nchrs++] = (chr)c;
 }
 
 /*
  - addrange - add a range to a cvec
- ^ static VOID addrange(struct cvec *, pchr, pchr);
+ ^ static void addrange(struct cvec *, pchr, pchr);
  */
 static void
 addrange(
@@ -128,7 +129,7 @@ getcvec(
 
 /*
  - freecvec - free a cvec
- ^ static VOID freecvec(struct cvec *);
+ ^ static void freecvec(struct cvec *);
  */
 static void
 freecvec(
diff --git a/generic/regc_lex.c b/generic/regc_lex.c
index 8d07c59..16e3ae9 100644
--- a/generic/regc_lex.c
+++ b/generic/regc_lex.c
@@ -63,7 +63,7 @@
 
 /*
  - lexstart - set up lexical stuff, scan leading options
- ^ static VOID lexstart(struct vars *);
+ ^ static void lexstart(struct vars *);
  */
 static void
 lexstart(
@@ -89,7 +89,7 @@ lexstart(
 
 /*
  - prefixes - implement various special prefixes
- ^ static VOID prefixes(struct vars *);
+ ^ static void prefixes(struct vars *);
  */
 static void
 prefixes(
@@ -207,7 +207,7 @@ prefixes(
  - lexnest - "call a subroutine", interpolating string at the lexical level
  * Note, this is not a very general facility.  There are a number of
  * implicit assumptions about what sorts of strings can be subroutines.
- ^ static VOID lexnest(struct vars *, const chr *, const chr *);
+ ^ static void lexnest(struct vars *, const chr *, const chr *);
  */
 static void
 lexnest(
@@ -275,7 +275,7 @@ static const chr brbackw[] = {	/* \w within brackets */
 /*
  - lexword - interpolate a bracket expression for word characters
  * Possibly ought to inquire whether there is a "word" character class.
- ^ static VOID lexword(struct vars *);
+ ^ static void lexword(struct vars *);
  */
 static void
 lexword(
@@ -742,6 +742,7 @@ lexescape(
     struct vars *v)
 {
     chr c;
+    int i;
     static const chr alert[] = {
 	CHR('a'), CHR('l'), CHR('e'), CHR('r'), CHR('t')
     };
@@ -818,18 +819,23 @@ lexescape(
 	RETV(PLAIN, CHR('\t'));
 	break;
     case CHR('u'):
-	c = lexdigits(v, 16, 4, 4);
+	c = (uchr) lexdigits(v, 16, 1, 4);
 	if (ISERR()) {
 	    FAILW(REG_EESCAPE);
 	}
 	RETV(PLAIN, c);
 	break;
     case CHR('U'):
-	c = lexdigits(v, 16, 8, 8);
+	i = lexdigits(v, 16, 1, 8);
 	if (ISERR()) {
 	    FAILW(REG_EESCAPE);
 	}
-	RETV(PLAIN, c);
+	if (i > 0xFFFF) {
+	    /* TODO: output a Surrogate pair
+	     */
+	    i = 0xFFFD;
+	}
+	RETV(PLAIN, (uchr) i);
 	break;
     case CHR('v'):
 	RETV(PLAIN, CHR('\v'));
@@ -844,7 +850,7 @@ lexescape(
 	break;
     case CHR('x'):
 	NOTE(REG_UUNPORT);
-	c = lexdigits(v, 16, 1, 255);	/* REs >255 long outside spec */
+	c = (uchr) lexdigits(v, 16, 1, 2);
 	if (ISERR()) {
 	    FAILW(REG_EESCAPE);
 	}
@@ -866,7 +872,7 @@ lexescape(
     case CHR('9'):
 	save = v->now;
 	v->now--;		/* put first digit back */
-	c = lexdigits(v, 10, 1, 255);	/* REs >255 long outside spec */
+	c = (uchr) lexdigits(v, 10, 1, 255);	/* REs >255 long outside spec */
 	if (ISERR()) {
 	    FAILW(REG_EESCAPE);
 	}
@@ -893,10 +899,15 @@ lexescape(
     case CHR('0'):
 	NOTE(REG_UUNPORT);
 	v->now--;		/* put first digit back */
-	c = lexdigits(v, 8, 1, 3);
+	c = (uchr) lexdigits(v, 8, 1, 3);
 	if (ISERR()) {
 	    FAILW(REG_EESCAPE);
 	}
+	if (c > 0xff) {
+	    /* out of range, so we handled one digit too much */
+	    v->now--;
+	    c >>= 3;
+	}
 	RETV(PLAIN, c);
 	break;
     default:
@@ -909,23 +920,27 @@ lexescape(
 
 /*
  - lexdigits - slurp up digits and return chr value
- ^ static chr lexdigits(struct vars *, int, int, int);
+ ^ static int lexdigits(struct vars *, int, int, int);
  */
-static chr			/* chr value; errors signalled via ERR */
+static int			/* chr value; errors signalled via ERR */
 lexdigits(
     struct vars *v,
     int base,
     int minlen,
     int maxlen)
 {
-    uchr n;			/* unsigned to avoid overflow misbehavior */
+    int n;
     int len;
     chr c;
     int d;
-    CONST uchr ub = (uchr) base;
+    const uchr ub = (uchr) base;
 
     n = 0;
     for (len = 0; len < maxlen && !ATEOS(); len++) {
+	if (n > 0x10fff) {
+	    /* Stop when continuing would otherwise overflow */
+	    break;
+	}
 	c = *v->now++;
 	switch (c) {
 	case CHR('0'): case CHR('1'): case CHR('2'): case CHR('3'):
@@ -958,7 +973,7 @@ lexdigits(
 	ERR(REG_EESCAPE);
     }
 
-    return (chr)n;
+    return n;
 }
 
 /*
@@ -1080,7 +1095,7 @@ brenext(
 
 /*
  - skip - skip white space and comments in expanded form
- ^ static VOID skip(struct vars *);
+ ^ static void skip(struct vars *);
  */
 static void
 skip(
@@ -1124,24 +1139,6 @@ newline(void)
 }
 
 /*
- - ch - return the chr sequence for regc_locale.c's fake collating element ch
- * This helps confine use of CHR to this source file.  Beware that the caller
- * knows how long the sequence is.
- ^ #ifdef REG_DEBUG
- ^ static const chr *ch(NOPARMS);
- ^ #endif
- */
-#ifdef REG_DEBUG
-static const chr *
-ch(void)
-{
-    static const chr chstr[] = { CHR('c'), CHR('h'), CHR('\0') };
-
-    return chstr;
-}
-#endif
-
-/*
  - chrnamed - return the chr known by a given (chr string) name
  * The code is a bit clumsy, but this routine gets only such specialized
  * use that it hardly matters.
diff --git a/generic/regc_locale.c b/generic/regc_locale.c
index 2a4248e..3c10cb6 100644
--- a/generic/regc_locale.c
+++ b/generic/regc_locale.c
@@ -389,7 +389,7 @@ static const crange spaceRangeTable[] = {
 #define NUM_SPACE_RANGE (sizeof(spaceRangeTable)/sizeof(crange))
 
 static const chr spaceCharTable[] = {
-    0x20, 0xa0, 0x1680, 0x180e, 0x2028, 0x2029, 0x202f, 0x205f,
+    0x20, 0x85, 0xa0, 0x1680, 0x180e, 0x2028, 0x2029, 0x202f, 0x205f,
     0x2060, 0x3000, 0xfeff
 };
 
diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c
index 6280e5e..088c6c0 100644
--- a/generic/regc_nfa.c
+++ b/generic/regc_nfa.c
@@ -90,7 +90,7 @@ newnfa(
 
 /*
  - freenfa - free an entire NFA
- ^ static VOID freenfa(struct nfa *);
+ ^ static void freenfa(struct nfa *);
  */
 static void
 freenfa(
@@ -184,7 +184,7 @@ newfstate(
 
 /*
  - dropstate - delete a state's inarcs and outarcs and free it
- ^ static VOID dropstate(struct nfa *, struct state *);
+ ^ static void dropstate(struct nfa *, struct state *);
  */
 static void
 dropstate(
@@ -204,7 +204,7 @@ dropstate(
 
 /*
  - freestate - free a state, which has no in-arcs or out-arcs
- ^ static VOID freestate(struct nfa *, struct state *);
+ ^ static void freestate(struct nfa *, struct state *);
  */
 static void
 freestate(
@@ -235,7 +235,7 @@ freestate(
 
 /*
  - destroystate - really get rid of an already-freed state
- ^ static VOID destroystate(struct nfa *, struct state *);
+ ^ static void destroystate(struct nfa *, struct state *);
  */
 static void
 destroystate(
@@ -260,7 +260,7 @@ destroystate(
 
 /*
  - newarc - set up a new arc within an NFA
- ^ static VOID newarc(struct nfa *, int, pcolor, struct state *,
+ ^ static void newarc(struct nfa *, int, pcolor, struct state *,
  ^	struct state *);
  */
 /*
@@ -293,7 +293,7 @@ newarc(
 	    }
 	}
     }
-  
+
     /* no dup, so create the arc */
     createarc(nfa, t, co, from, to);
 }
@@ -410,7 +410,7 @@ allocarc(
 
 /*
  - freearc - free an arc
- ^ static VOID freearc(struct nfa *, struct arc *);
+ ^ static void freearc(struct nfa *, struct arc *);
  */
 static void
 freearc(
@@ -569,7 +569,7 @@ findarc(
 
 /*
  - cparc - allocate a new arc within an NFA, copying details from old one
- ^ static VOID cparc(struct nfa *, struct arc *, struct state *,
+ ^ static void cparc(struct nfa *, struct arc *, struct state *,
  ^ 	struct state *);
  */
 static void
@@ -657,7 +657,7 @@ sortins_cmp(
     }
     return 0;
 }
- 
+
 /*
  * sortouts - sort the out arcs of a state by to/color/type
  */
@@ -756,7 +756,7 @@ sortouts_cmp(
  * checks become too slow.  In that case we proceed by sorting and merging
  * the arc lists, and then we can indeed just update the arcs in-place.
  *
- ^ static VOID moveins(struct nfa *, struct state *, struct state *);
+ ^ static void moveins(struct nfa *, struct state *, struct state *);
  */
 static void
 moveins(
@@ -1016,7 +1016,7 @@ mergeins(
 
 /*
  - moveouts - move all out arcs of a state to another state
- ^ static VOID moveouts(struct nfa *, struct state *, struct state *);
+ ^ static void moveouts(struct nfa *, struct state *, struct state *);
  */
 static void
 moveouts(
@@ -1176,7 +1176,7 @@ copyouts(
 
 /*
  - cloneouts - copy out arcs of a state to another state pair, modifying type
- ^ static VOID cloneouts(struct nfa *, struct state *, struct state *,
+ ^ static void cloneouts(struct nfa *, struct state *, struct state *,
  ^ 	struct state *, int);
  */
 static void
@@ -1200,7 +1200,7 @@ cloneouts(
  - delsub - delete a sub-NFA, updating subre pointers if necessary
  * This uses a recursive traversal of the sub-NFA, marking already-seen
  * states using their tmp pointer.
- ^ static VOID delsub(struct nfa *, struct state *, struct state *);
+ ^ static void delsub(struct nfa *, struct state *, struct state *);
  */
 static void
 delsub(
@@ -1223,7 +1223,7 @@ delsub(
 /*
  - deltraverse - the recursive heart of delsub
  * This routine's basic job is to destroy all out-arcs of the state.
- ^ static VOID deltraverse(struct nfa *, struct state *, struct state *);
+ ^ static void deltraverse(struct nfa *, struct state *, struct state *);
  */
 static void
 deltraverse(
@@ -1266,7 +1266,7 @@ deltraverse(
  * Another recursive traversal, this time using tmp to point to duplicates as
  * well as mark already-seen states. (You knew there was a reason why it's a
  * state pointer, didn't you? :-))
- ^ static VOID dupnfa(struct nfa *, struct state *, struct state *,
+ ^ static void dupnfa(struct nfa *, struct state *, struct state *,
  ^ 	struct state *, struct state *);
  */
 static void
@@ -1283,7 +1283,7 @@ dupnfa(
     }
 
     stop->tmp = to;
-    duptraverse(nfa, start, from);
+    duptraverse(nfa, start, from, 0);
     /* done, except for clearing out the tmp pointers */
 
     stop->tmp = NULL;
@@ -1292,13 +1292,14 @@ dupnfa(
 
 /*
  - duptraverse - recursive heart of dupnfa
- ^ static VOID duptraverse(struct nfa *, struct state *, struct state *);
+ ^ static void duptraverse(struct nfa *, struct state *, struct state *);
  */
 static void
 duptraverse(
     struct nfa *nfa,
     struct state *s,
-    struct state *stmp)		/* s's duplicate, or NULL */
+    struct state *stmp,		/* s's duplicate, or NULL */
+    int depth)
 {
     struct arc *a;
 
@@ -1312,8 +1313,20 @@ duptraverse(
 	return;
     }
 
+    /*
+     * Arbitrary depth limit. Needs tuning, but this value is sufficient to
+     * make all normal tests (not reg-33.14) pass.
+     */
+#ifndef DUPTRAVERSE_MAX_DEPTH
+#define DUPTRAVERSE_MAX_DEPTH 15000
+#endif
+
+    if (depth++ > DUPTRAVERSE_MAX_DEPTH) {
+	NERR(REG_ESPACE);
+    }
+
     for (a=s->outs ; a!=NULL && !NISERR() ; a=a->outchain) {
-	duptraverse(nfa, a->to, NULL);
+	duptraverse(nfa, a->to, NULL, depth);
 	if (NISERR()) {
 	    break;
 	}
@@ -1324,7 +1337,7 @@ duptraverse(
 
 /*
  - cleartraverse - recursive cleanup for algorithms that leave tmp ptrs set
- ^ static VOID cleartraverse(struct nfa *, struct state *);
+ ^ static void cleartraverse(struct nfa *, struct state *);
  */
 static void
 cleartraverse(
@@ -1345,7 +1358,7 @@ cleartraverse(
 
 /*
  - specialcolors - fill in special colors for an NFA
- ^ static VOID specialcolors(struct nfa *);
+ ^ static void specialcolors(struct nfa *);
  */
 static void
 specialcolors(
@@ -1428,7 +1441,7 @@ optimize(
 
 /*
  - pullback - pull back constraints backward to eliminate them
- ^ static VOID pullback(struct nfa *, FILE *);
+ ^ static void pullback(struct nfa *, FILE *);
  */
 static void
 pullback(
@@ -1608,7 +1621,7 @@ pull(
 
 /*
  - pushfwd - push forward constraints forward to eliminate them
- ^ static VOID pushfwd(struct nfa *, FILE *);
+ ^ static void pushfwd(struct nfa *, FILE *);
  */
 static void
 pushfwd(
@@ -1847,7 +1860,7 @@ combine(
 
 /*
  - fixempties - get rid of EMPTY arcs
- ^ static VOID fixempties(struct nfa *, FILE *);
+ ^ static void fixempties(struct nfa *, FILE *);
  */
 static void
 fixempties(
@@ -2007,7 +2020,7 @@ fixempties(
 		    arcarray[arccount++] = a;
 		}
 	    }
-  
+
   	    /* Reset the tmp fields as we walk back */
   	    nexts = s2->tmp;
   	    s2->tmp = NULL;
@@ -2029,7 +2042,7 @@ fixempties(
 	}
 	inarcsorig[s->no] = a;
     }
-  
+
     FREE(arcarray);
     FREE(inarcsorig);
 
@@ -2180,7 +2193,7 @@ fixconstraintloops(
  	    dropstate(nfa, s);
 	}
     }
- 
+
     /* Nothing to do if no remaining constraint arcs */
     if (NISERR() || !hasconstraints) {
 	return;
@@ -2670,7 +2683,7 @@ clonesuccessorstates(
 
 /*
  - cleanup - clean up NFA after optimizations
- ^ static VOID cleanup(struct nfa *);
+ ^ static void cleanup(struct nfa *);
  */
 static void
 cleanup(
@@ -2711,7 +2724,7 @@ cleanup(
 
 /*
  - markreachable - recursive marking of reachable states
- ^ static VOID markreachable(struct nfa *, struct state *, struct state *,
+ ^ static void markreachable(struct nfa *, struct state *, struct state *,
  ^ 	struct state *);
  */
 static void
@@ -2735,7 +2748,7 @@ markreachable(
 
 /*
  - markcanreach - recursive marking of states which can reach here
- ^ static VOID markcanreach(struct nfa *, struct state *, struct state *,
+ ^ static void markcanreach(struct nfa *, struct state *, struct state *,
  ^ 	struct state *);
  */
 static void
@@ -2783,7 +2796,7 @@ analyze(
 
 /*
  - compact - construct the compact representation of an NFA
- ^ static VOID compact(struct nfa *, struct cnfa *);
+ ^ static void compact(struct nfa *, struct cnfa *);
  */
 static void
 compact(
@@ -2803,13 +2816,16 @@ compact(
     narcs = 0;
     for (s = nfa->states; s != NULL; s = s->next) {
 	nstates++;
-	narcs += 1 + s->nouts + 1;
-	/* 1 as a fake for flags, nouts for arcs, 1 as endmarker */
+	narcs += s->nouts + 1;	/* need one extra for endmarker */
     }
 
+    cnfa->stflags = (char *) MALLOC(nstates * sizeof(char));
     cnfa->states = (struct carc **) MALLOC(nstates * sizeof(struct carc *));
     cnfa->arcs = (struct carc *) MALLOC(narcs * sizeof(struct carc));
-    if (cnfa->states == NULL || cnfa->arcs == NULL) {
+    if (cnfa->stflags == NULL || cnfa->states == NULL || cnfa->arcs == NULL) {
+	if (cnfa->stflags != NULL) {
+	    FREE(cnfa->stflags);
+	}
 	if (cnfa->states != NULL) {
 	    FREE(cnfa->states);
 	}
@@ -2832,9 +2848,8 @@ compact(
     ca = cnfa->arcs;
     for (s = nfa->states; s != NULL; s = s->next) {
 	assert((size_t) s->no < nstates);
+	cnfa->stflags[s->no] = 0;
 	cnfa->states[s->no] = ca;
-	ca->co = 0;		/* clear and skip flags "arc" */
-	ca++;
 	first = ca;
 	for (a = s->outs; a != NULL; a = a->outchain) {
 	    switch (a->type) {
@@ -2868,14 +2883,14 @@ compact(
      */
 
     for (a = nfa->pre->outs; a != NULL; a = a->outchain) {
-	cnfa->states[a->to->no]->co = 1;
+	cnfa->stflags[a->to->no] = CNFA_NOPROGRESS;
     }
-    cnfa->states[nfa->pre->no]->co = 1;
+    cnfa->stflags[nfa->pre->no] = CNFA_NOPROGRESS;
 }
 
 /*
  - carcsort - sort compacted-NFA arcs by color
- ^ static VOID carcsort(struct carc *, struct carc *);
+ ^ static void carcsort(struct carc *, struct carc *);
  */
 static void
 carcsort(
@@ -2894,7 +2909,7 @@ carc_cmp(
 {
     const struct carc *aa = (const struct carc *) a;
     const struct carc *bb = (const struct carc *) b;
-  
+
     if (aa->co < bb->co) {
 	return -1;
     }
@@ -2912,7 +2927,7 @@ carc_cmp(
 
 /*
  - freecnfa - free a compacted NFA
- ^ static VOID freecnfa(struct cnfa *);
+ ^ static void freecnfa(struct cnfa *);
  */
 static void
 freecnfa(
@@ -2920,13 +2935,14 @@ freecnfa(
 {
     assert(cnfa->nstates != 0);	/* not empty already */
     cnfa->nstates = 0;
+    FREE(cnfa->stflags);
     FREE(cnfa->states);
     FREE(cnfa->arcs);
 }
 
 /*
  - dumpnfa - dump an NFA in human-readable form
- ^ static VOID dumpnfa(struct nfa *, FILE *);
+ ^ static void dumpnfa(struct nfa *, FILE *);
  */
 static void
 dumpnfa(
@@ -2972,7 +2988,7 @@ dumpnfa(
 
 /*
  - dumpstate - dump an NFA state in human-readable form
- ^ static VOID dumpstate(struct state *, FILE *);
+ ^ static void dumpstate(struct state *, FILE *);
  */
 static void
 dumpstate(
@@ -3002,7 +3018,7 @@ dumpstate(
 
 /*
  - dumparcs - dump out-arcs in human-readable form
- ^ static VOID dumparcs(struct state *, FILE *);
+ ^ static void dumparcs(struct state *, FILE *);
  */
 static void
 dumparcs(
@@ -3036,7 +3052,7 @@ dumparcs(
 
 /*
  - dumparc - dump one outarc in readable form, including prefixing tab
- ^ static VOID dumparc(struct arc *, struct state *, FILE *);
+ ^ static void dumparc(struct arc *, struct state *, FILE *);
  */
 static void
 dumparc(
@@ -3110,7 +3126,7 @@ dumparc(
 
 /*
  - dumpcnfa - dump a compacted NFA in human-readable form
- ^ static VOID dumpcnfa(struct cnfa *, FILE *);
+ ^ static void dumpcnfa(struct cnfa *, FILE *);
  */
 static void
 dumpcnfa(
@@ -3138,7 +3154,7 @@ dumpcnfa(
     }
     fprintf(f, "\n");
     for (st = 0; st < cnfa->nstates; st++) {
-	dumpcstate(st, cnfa->states[st], cnfa, f);
+	dumpcstate(st, cnfa, f);
     }
     fflush(f);
 #endif
@@ -3151,25 +3167,24 @@ dumpcnfa(
 
 /*
  - dumpcstate - dump a compacted-NFA state in human-readable form
- ^ static VOID dumpcstate(int, struct carc *, struct cnfa *, FILE *);
+ ^ static void dumpcstate(int, struct cnfa *, FILE *);
  */
 static void
 dumpcstate(
     int st,
-    struct carc *ca,
     struct cnfa *cnfa,
     FILE *f)
 {
-    int i;
+    struct carc *ca;
     int pos;
 
-    fprintf(f, "%d%s", st, (ca[0].co) ? ":" : ".");
+    fprintf(f, "%d%s", st, (cnfa->stflags[st] & CNFA_NOPROGRESS) ? ":" : ".");
     pos = 1;
-    for (i = 1; ca[i].co != COLORLESS; i++) {
-	if (ca[i].co < cnfa->ncolors) {
-	    fprintf(f, "\t[%ld]->%d", (long) ca[i].co, ca[i].to);
+    for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++) {
+	if (ca->co < cnfa->ncolors) {
+	    fprintf(f, "\t[%ld]->%d", (long) ca->co, ca->to);
 	} else {
-	    fprintf(f, "\t:%ld:->%d", (long) ca[i].co-cnfa->ncolors,ca[i].to);
+	    fprintf(f, "\t:%ld:->%d", (long) (ca->co - cnfa->ncolors), ca->to);
 	}
 	if (pos == 5) {
 	    fprintf(f, "\n");
@@ -3178,7 +3193,7 @@ dumpcstate(
 	    pos++;
 	}
     }
-    if (i == 1 || pos != 1) {
+    if (ca == cnfa->states[st] || pos != 1) {
 	fprintf(f, "\n");
     }
     fflush(f);
diff --git a/generic/regcomp.c b/generic/regcomp.c
index 8287b7e..211cd70 100644
--- a/generic/regcomp.c
+++ b/generic/regcomp.c
@@ -79,13 +79,10 @@ static void lexnest(struct vars *, const chr *, const chr *);
 static void lexword(struct vars *);
 static int next(struct vars *);
 static int lexescape(struct vars *);
-static chr lexdigits(struct vars *, int, int, int);
+static int lexdigits(struct vars *, int, int, int);
 static int brenext(struct vars *, pchr);
 static void skip(struct vars *);
 static chr newline(NOPARMS);
-#ifdef REG_DEBUG
-static const chr *ch(NOPARMS);
-#endif
 static chr chrnamed(struct vars *, const chr *, const chr *, pchr);
 /* === regc_color.c === */
 static void initcm(struct vars *, struct colormap *);
@@ -139,7 +136,7 @@ static void cloneouts(struct nfa *, struct state *, struct state *, struct state
 static void delsub(struct nfa *, struct state *, struct state *);
 static void deltraverse(struct nfa *, struct state *, struct state *);
 static void dupnfa(struct nfa *, struct state *, struct state *, struct state *, struct state *);
-static void duptraverse(struct nfa *, struct state *, struct state *);
+static void duptraverse(struct nfa *, struct state *, struct state *, int);
 static void cleartraverse(struct nfa *, struct state *);
 static void specialcolors(struct nfa *);
 static long optimize(struct nfa *, FILE *);
@@ -177,7 +174,7 @@ static void dumparc(struct arc *, struct state *, FILE *);
 #endif
 static void dumpcnfa(struct cnfa *, FILE *);
 #ifdef REG_DEBUG
-static void dumpcstate(int, struct carc *, struct cnfa *, FILE *);
+static void dumpcstate(int, struct cnfa *, FILE *);
 #endif
 /* === regc_cvec.c === */
 static struct cvec *clearcvec(struct cvec *);
@@ -222,7 +219,7 @@ struct vars {
     struct subre *tree;		/* subexpression tree */
     struct subre *treechain;	/* all tree nodes allocated */
     struct subre *treefree;	/* any free tree nodes */
-    int ntree;			/* number of tree nodes */
+    int ntree;			/* number of tree nodes, plus one */
     struct cvec *cv;		/* interface cvec */
     struct cvec *cv2;		/* utility cvec */
     struct subre *lacons;	/* lookahead-constraint vector */
@@ -236,13 +233,13 @@ struct vars {
 #define	EAT(t)	(SEE(t) && next(v))	/* if next is this, swallow it */
 #define	VISERR(vv)	((vv)->err != 0)/* have we seen an error yet? */
 #define	ISERR()	VISERR(v)
-#define	VERR(vv,e) \
-	((vv)->nexttype = EOS, ((vv)->err) ? (vv)->err : ((vv)->err = (e)))
+#define VERR(vv,e)	((vv)->nexttype = EOS, \
+			 (vv)->err = ((vv)->err ? (vv)->err : (e)))
 #define	ERR(e)	VERR(v, e)		/* record an error */
 #define	NOERR()	{if (ISERR()) return;}	/* if error seen, return */
 #define	NOERRN()	{if (ISERR()) return NULL;}	/* NOERR with retval */
 #define	NOERRZ()	{if (ISERR()) return 0;}	/* NOERR with retval */
-#define	INSIST(c, e)	((c) ? 0 : ERR(e))	/* if condition false, error */
+#define INSIST(c, e) do { if (!(c)) ERR(e); } while (0)	/* error if c false */
 #define	NOTE(b)	(v->re->re_info |= (b))		/* note visible condition */
 #define	EMPTYARC(x, y)	newarc(v->nfa, EMPTY, 0, x, y)
 
@@ -271,12 +268,14 @@ struct vars {
 	((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND)
 
 /* static function list */
-static struct fns functions = {
+static const struct fns functions = {
     rfree,			/* regfree insides */
 };
 
 /*
  - compile - compile regular expression
+ * Note: on failure, no resources remain allocated, so regfree()
+ * need not be applied to re.
  ^ int compile(regex_t *, const chr *, size_t, int);
  */
 int
@@ -607,7 +606,7 @@ makesearch(
 		break;
 	    }
 	}
- 
+
 	/*
 	 * We want to mark states as being in the list already by having non
 	 * NULL tmp fields, but we can't just store the old slist value in tmp
@@ -1120,11 +1119,17 @@ parseqatom(
     /*
      * Prepare a general-purpose state skeleton.
      *
-     *    ---> [s] ---prefix---> [begin] ---atom---> [end] ----rest---> [rp]
-     *   /                                            /
-     * [lp] ----> [s2] ----bypass---------------------
+     * In the no-backrefs case, we want this:
+     *
+     * [lp] ---> [s] ---prefix---> [begin] ---atom---> [end] ---rest---> [rp]
+     *
+     * where prefix is some repetitions of atom.  In the general case we need
      *
-     * where bypass is an empty, and prefix is some repetitions of atom
+     * [lp] ---> [s] ---iterator---> [s2] ---rest---> [rp]
+     *
+     * where the iterator wraps around [begin] ---atom---> [end]
+     *
+     * We make the s state here for both cases; s2 is made below if needed
      */
 
     s = newstate(v->nfa);	/* first, new endpoints for the atom */
@@ -1135,11 +1140,9 @@ parseqatom(
     NOERR();
     atom->begin = s;
     atom->end = s2;
-    s = newstate(v->nfa);	/* and spots for prefix and bypass */
-    s2 = newstate(v->nfa);
+    s = newstate(v->nfa);	/* set up starting state */
     NOERR();
     EMPTYARC(lp, s);
-    EMPTYARC(lp, s2);
     NOERR();
 
     /*
@@ -1186,27 +1189,8 @@ parseqatom(
     }
 
     /*
-     * It's quantifier time; first, turn x{0,...} into x{1,...}|empty
-     */
-
-    if (m == 0) {
-	EMPTYARC(s2, atom->end);/* the bypass */
-	assert(PREF(qprefer) != 0);
-	f = COMBINE(qprefer, atom->flags);
-	t = subre(v, '|', f, lp, atom->end);
-	NOERR();
-	t->left = atom;
-	t->right = subre(v, '|', PREF(f), s2, atom->end);
-	NOERR();
-	t->right->left = subre(v, '=', 0, s2, atom->end);
-	NOERR();
-	*atomp = t;
-	atomp = &t->left;
-	m = 1;
-    }
-
-    /*
-     * Deal with the rest of the quantifier.
+     * It's quantifier time.  If the atom is just a backref, we'll let it deal
+     * with quantifiers internally.
      */
 
     if (atomtype == BACKREF) {
@@ -1224,16 +1208,24 @@ parseqatom(
 	atom->min = (short) m;
 	atom->max = (short) n;
 	atom->flags |= COMBINE(qprefer, atom->flags);
+	/* rest of branch can be strung starting from atom->end */
+	s2 = atom->end;
     } else if (m == 1 && n == 1) {
 	/*
 	 * No/vacuous quantifier: done.
 	 */
 
 	EMPTYARC(s, atom->begin);	/* empty prefix */
-    } else {
+	/* rest of branch can be strung starting from atom->end */
+	s2 = atom->end;
+    } else if (m > 0 && !(atom->flags & BACKR)) {
 	/*
-	 * Turn x{m,n} into x{m-1,n-1}x, with capturing parens in only second
-	 * x
+	 * If there's no backrefs involved, we can turn x{m,n} into
+	 * x{m-1,n-1}x, with capturing parens in only the second x.  This
+	 * is valid because we only care about capturing matches from the
+	 * final iteration of the quantifier.  It's a win because we can
+	 * implement the backref-free left side as a plain DFA node, since
+	 * we don't really care where its submatches are.
 	 */
 
 	dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin);
@@ -1246,6 +1238,24 @@ parseqatom(
 	NOERR();
 	t->right = atom;
 	*atomp = t;
+	/* rest of branch can be strung starting from atom->end */
+	s2 = atom->end;
+    } else {
+	/* general case: need an iteration node */
+	s2 = newstate(v->nfa);
+	NOERR();
+	moveouts(v->nfa, atom->end, s2);
+	NOERR();
+	dupnfa(v->nfa, atom->begin, atom->end, s, s2);
+	repeat(v, s, s2, m, n);
+	f = COMBINE(qprefer, atom->flags);
+	t = subre(v, '*', f, s, s2);
+	NOERR();
+	t->min = (short) m;
+	t->max = (short) n;
+	t->left = atom;
+	*atomp = t;
+	/* rest of branch is to be strung from iteration's end state */
     }
 
     /*
@@ -1254,10 +1264,10 @@ parseqatom(
 
     t = top->right;
     if (!(SEE('|') || SEE(stopper) || SEE(EOS))) {
-	t->right = parsebranch(v, stopper, type, atom->end, rp, 1);
+	t->right = parsebranch(v, stopper, type, s2, rp, 1);
     } else {
-	EMPTYARC(atom->end, rp);
-	t->right = subre(v, '=', 0, atom->end, rp);
+	EMPTYARC(s2, rp);
+	t->right = subre(v, '=', 0, s2, rp);
     }
     NOERR();
     assert(SEE('|') || SEE(stopper) || SEE(EOS));
@@ -1324,6 +1334,8 @@ scannum(
 
 /*
  - repeat - replicate subNFA for quantifiers
+ * The sub-NFA strung from lp to rp is modified to represent m to n
+ * repetitions of its initial contents.
  * The duplication sequences used here are chosen carefully so that any
  * pointers starting out pointing into the subexpression end up pointing into
  * the last occurrence. (Note that it may not be strung between the same left
@@ -1484,7 +1496,7 @@ brackpart(
     celt startc, endc;
     struct cvec *cv;
     const chr *startp, *endp;
-    chr c[1];
+    chr c;
 
     /*
      * Parse something, get rid of special cases, take shortcuts.
@@ -1496,7 +1508,7 @@ brackpart(
 	return;
 	break;
     case PLAIN:
-	c[0] = v->nextvalue;
+	c = v->nextvalue;
 	NEXT();
 
 	/*
@@ -1504,10 +1516,10 @@ brackpart(
 	 */
 
 	if (!SEE(RANGE)) {
-	    onechr(v, c[0], lp, rp);
+	    onechr(v, c, lp, rp);
 	    return;
 	}
-	startc = element(v, c, c+1);
+	startc = element(v, &c, &c+1);
 	NOERR();
 	break;
     case COLLEL:
@@ -1551,9 +1563,9 @@ brackpart(
 	switch (v->nexttype) {
 	case PLAIN:
 	case RANGE:
-	    c[0] = v->nextvalue;
+	    c = v->nextvalue;
 	    NEXT();
-	    endc = element(v, c, c+1);
+	    endc = element(v, &c, &c+1);
 	    NOERR();
 	    break;
 	case COLLEL:
@@ -1733,11 +1745,11 @@ subre(
 	v->treechain = ret;
     }
 
-    assert(strchr("|.b(=", op) != NULL);
+    assert(strchr("=b|.*(", op) != NULL);
 
     ret->op = op;
     ret->flags = flags;
-    ret->retry = 0;
+    ret->id = 0;		/* will be assigned later */
     ret->subno = 0;
     ret->min = ret->max = 1;
     ret->left = NULL;
@@ -1790,7 +1802,8 @@ freesrnode(
     }
     sr->flags = 0;
 
-    if (v != NULL) {
+    if (v != NULL && v->treechain != NULL) {
+	/* we're still parsing, maybe we can reuse the subre */
 	sr->left = v->treefree;
 	v->treefree = sr;
     } else {
@@ -1818,7 +1831,7 @@ optst(
 }
 
 /*
- - numst - number tree nodes (assigning retry indexes)
+ - numst - number tree nodes (assigning "id" indexes)
  ^ static int numst(struct subre *, int);
  */
 static int			/* next number */
@@ -1831,7 +1844,7 @@ numst(
     assert(t != NULL);
 
     i = start;
-    t->retry = (short) i++;
+    t->id = (short) i++;
     if (t->left != NULL) {
 	i = numst(t->left, i);
     }
@@ -1843,6 +1856,19 @@ numst(
 
 /*
  - markst - mark tree nodes as INUSE
+ * Note: this is a great deal more subtle than it looks.  During initial
+ * parsing of a regex, all subres are linked into the treechain list;
+ * discarded ones are also linked into the treefree list for possible reuse.
+ * After we are done creating all subres required for a regex, we run markst()
+ * then cleanst(), which results in discarding all subres not reachable from
+ * v->tree.  We then clear v->treechain, indicating that subres must be found
+ * by descending from v->tree.  This changes the behavior of freesubre(): it
+ * will henceforth FREE() unwanted subres rather than sticking them into the
+ * treefree list.  (Doing that any earlier would result in dangling links in
+ * the treechain list.)  This all means that freev() will clean up correctly
+ * if invoked before or after markst()+cleanst(); but it would not work if
+ * called partway through this state conversion, so we mustn't error out
+ * in or between these two functions.
  ^ static void markst(struct subre *);
  */
 static void
@@ -1949,24 +1975,26 @@ newlacon(
     struct state *end,
     int pos)
 {
-    struct subre *sub;
     int n;
+    struct subre *newlacons;
+    struct subre *sub;
 
     if (v->nlacons == 0) {
-	v->lacons = (struct subre *) MALLOC(2 * sizeof(struct subre));
 	n = 1;		/* skip 0th */
-	v->nlacons = 2;
+	newlacons = (struct subre *) MALLOC(2 * sizeof(struct subre));
     } else {
-	v->lacons = (struct subre *) REALLOC(v->lacons,
-		(v->nlacons+1)*sizeof(struct subre));
-	n = v->nlacons++;
+	n = v->nlacons;
+	newlacons = (struct subre *) REALLOC(v->lacons,
+					     (n + 1) * sizeof(struct subre));
     }
 
-    if (v->lacons == NULL) {
+    if (newlacons == NULL) {
 	ERR(REG_ESPACE);
 	return 0;
     }
 
+    v->lacons = newlacons;
+    v->nlacons = n + 1;
     sub = &v->lacons[n];
     sub->begin = begin;
     sub->end = end;
@@ -2014,18 +2042,20 @@ rfree(
     g = (struct guts *) re->re_guts;
     re->re_guts = NULL;
     re->re_fns = NULL;
-    g->magic = 0;
-    freecm(&g->cmap);
-    if (g->tree != NULL) {
-	freesubre(NULL, g->tree);
-    }
-    if (g->lacons != NULL) {
-	freelacons(g->lacons, g->nlacons);
-    }
-    if (!NULLCNFA(g->search)) {
-	freecnfa(&g->search);
+    if (g != NULL) {
+	g->magic = 0;
+	freecm(&g->cmap);
+	if (g->tree != NULL) {
+	    freesubre(NULL, g->tree);
+	}
+	if (g->lacons != NULL) {
+	    freelacons(g->lacons, g->nlacons);
+	}
+	if (!NULLCNFA(g->search)) {
+	    freecnfa(&g->search);
+	}
+	FREE(g);
     }
-    FREE(g);
 }
 
 /*
@@ -2057,7 +2087,7 @@ dump(
 
     fprintf(f, "\n\n\n========= DUMP ==========\n");
     fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n",
-	    re->re_nsub, re->re_info, re->re_csize, g->ntree);
+	    (int) re->re_nsub, re->re_info, re->re_csize, g->ntree);
 
     dumpcolors(&g->cmap, f);
     if (!NULLCNFA(g->search)) {
@@ -2166,14 +2196,14 @@ stid(
     size_t bufsize)
 {
     /*
-     * Big enough for hex int or decimal t->retry?
+     * Big enough for hex int or decimal t->id?
      */
 
-    if (bufsize < sizeof(void*)*2 + 3 || bufsize < sizeof(t->retry)*3 + 1) {
+    if (bufsize < sizeof(void*)*2 + 3 || bufsize < sizeof(t->id)*3 + 1) {
 	return "unable";
     }
-    if (t->retry != 0) {
-	sprintf(buf, "%d", t->retry);
+    if (t->id != 0) {
+	sprintf(buf, "%d", t->id);
     } else {
 	sprintf(buf, "%p", t);
     }
diff --git a/generic/regcustom.h b/generic/regcustom.h
index 57a2d47..681b97d 100644
--- a/generic/regcustom.h
+++ b/generic/regcustom.h
@@ -30,16 +30,16 @@
  * Headers if any.
  */
 
-#include "tclInt.h"
+#include "regex.h"
 
 /*
  * Overrides for regguts.h definitions, if any.
  */
 
 #define	FUNCPTR(name, args)	(*name)args
-#define	MALLOC(n)		ckalloc(n)
+#define	MALLOC(n)		VS(attemptckalloc(n))
 #define	FREE(p)			ckfree(VS(p))
-#define	REALLOC(p,n)		ckrealloc(VS(p),n)
+#define	REALLOC(p,n)		VS(attemptckrealloc(VS(p),n))
 
 /*
  * Do not insert extras between the "begin" and "end" lines - this chunk is
@@ -60,12 +60,6 @@
 #ifdef __REG_REGOFF_T
 #undef __REG_REGOFF_T
 #endif
-#ifdef __REG_VOID_T
-#undef __REG_VOID_T
-#endif
-#ifdef __REG_CONST
-#undef __REG_CONST
-#endif
 #ifdef __REG_NOFRONT
 #undef __REG_NOFRONT
 #endif
@@ -75,8 +69,6 @@
 /* Interface types */
 #define	__REG_WIDE_T	Tcl_UniChar
 #define	__REG_REGOFF_T	long	/* Not really right, but good enough... */
-#define	__REG_VOID_T	void
-#define	__REG_CONST	const
 /* Names and declarations */
 #define	__REG_WIDE_COMPILE	TclReComp
 #define	__REG_WIDE_EXEC		TclReExec
@@ -155,7 +147,9 @@ typedef int celt;		/* Type to hold chr, or NOCELT */
 #endif
 
 /*
- * And pick up the standard header.
+ * Local Variables:
+ * mode: c
+ * c-basic-offset: 4
+ * fill-column: 78
+ * End:
  */
-
-#include "regex.h"
diff --git a/generic/rege_dfa.c b/generic/rege_dfa.c
index e233680..e5f22c4 100644
--- a/generic/rege_dfa.c
+++ b/generic/rege_dfa.c
@@ -36,17 +36,16 @@
  */
 static chr *			/* endpoint, or NULL */
 longest(
-    struct vars *v,		/* used only for debug and exec flags */
-    struct dfa *d,
-    chr *start,			/* where the match should start */
-    chr *stop,			/* match must end at or before here */
-    int *hitstopp)		/* record whether hit v->stop, if non-NULL */
+    struct vars *const v,	/* used only for debug and exec flags */
+    struct dfa *const d,
+    chr *const start,		/* where the match should start */
+    chr *const stop,		/* match must end at or before here */
+    int *const hitstopp)	/* record whether hit v->stop, if non-NULL */
 {
     chr *cp;
     chr *realstop = (stop == v->stop) ? stop : stop + 1;
     color co;
-    struct sset *css;
-    struct sset *ss;
+    struct sset *css, *ss;
     chr *post;
     int i;
     struct colormap *cm = d->cm;
@@ -85,7 +84,7 @@ longest(
 
     if (v->eflags&REG_FTRACE) {
 	while (cp < realstop) {
-	    FDEBUG(("+++ at c%d +++\n", css - d->ssets));
+	    FDEBUG(("+++ at c%d +++\n", (int) (css - d->ssets)));
 	    co = GETCOLOR(cm, *cp);
 	    FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
 	    ss = css->outs[co];
@@ -119,7 +118,7 @@ longest(
      * Shutdown.
      */
 
-    FDEBUG(("+++ shutdown at c%d +++\n", css - d->ssets));
+    FDEBUG(("+++ shutdown at c%d +++\n", (int) (css - d->ssets)));
     if (cp == v->stop && stop == v->stop) {
 	if (hitstopp != NULL) {
 	    *hitstopp = 1;
@@ -164,20 +163,19 @@ longest(
  */
 static chr *			/* endpoint, or NULL */
 shortest(
-    struct vars *v,
-    struct dfa *d,
-    chr *start,			/* where the match should start */
-    chr *min,			/* match must end at or after here */
-    chr *max,			/* match must end at or before here */
-    chr **coldp,		/* store coldstart pointer here, if nonNULL */
-    int *hitstopp)		/* record whether hit v->stop, if non-NULL */
+    struct vars *const v,
+    struct dfa *const d,
+    chr *const start,		/* where the match should start */
+    chr *const min,		/* match must end at or after here */
+    chr *const max,		/* match must end at or before here */
+    chr **const coldp,		/* store coldstart pointer here, if nonNULL */
+    int *const hitstopp)	/* record whether hit v->stop, if non-NULL */
 {
     chr *cp;
     chr *realmin = (min == v->stop) ? min : min + 1;
     chr *realmax = (max == v->stop) ? max : max + 1;
     color co;
-    struct sset *css;
-    struct sset *ss;
+    struct sset *css, *ss;
     struct colormap *cm = d->cm;
 
     /*
@@ -215,7 +213,7 @@ shortest(
 
     if (v->eflags&REG_FTRACE) {
 	while (cp < realmax) {
-	    FDEBUG(("--- at c%d ---\n", css - d->ssets));
+	    FDEBUG(("--- at c%d ---\n", (int) (css - d->ssets)));
 	    co = GETCOLOR(cm, *cp);
 	    FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
 	    ss = css->outs[co];
@@ -256,7 +254,7 @@ shortest(
     }
 
     if (coldp != NULL) {	/* report last no-progress state set, if any */
-	*coldp = lastcold(v, d);
+	*coldp = lastCold(v, d);
     }
 
     if ((ss->flags&POSTSTATE) && cp > min) {
@@ -284,19 +282,18 @@ shortest(
 }
 
 /*
- - lastcold - determine last point at which no progress had been made
- ^ static chr *lastcold(struct vars *, struct dfa *);
+ - lastCold - determine last point at which no progress had been made
+ ^ static chr *lastCold(struct vars *, struct dfa *);
  */
 static chr *			/* endpoint, or NULL */
-lastcold(
-    struct vars *v,
-    struct dfa *d)
+lastCold(
+    struct vars *const v,
+    struct dfa *const d)
 {
     struct sset *ss;
-    chr *nopr;
+    chr *nopr = d->lastnopr;
     int i;
 
-    nopr = d->lastnopr;
     if (nopr == NULL) {
 	nopr = v->start;
     }
@@ -309,15 +306,15 @@ lastcold(
 }
 
 /*
- - newdfa - set up a fresh DFA
- ^ static struct dfa *newdfa(struct vars *, struct cnfa *,
+ - newDFA - set up a fresh DFA
+ ^ static struct dfa *newDFA(struct vars *, struct cnfa *,
  ^ 	struct colormap *, struct smalldfa *);
  */
 static struct dfa *
-newdfa(
-    struct vars *v,
-    struct cnfa *cnfa,
-    struct colormap *cm,
+newDFA(
+    struct vars *const v,
+    struct cnfa *const cnfa,
+    struct colormap *const cm,
     struct smalldfa *sml)	/* preallocated space, may be NULL */
 {
     struct dfa *d;
@@ -345,12 +342,12 @@ newdfa(
 	d->cptsmalloced = 0;
 	d->mallocarea = (smallwas == NULL) ? (char *)sml : NULL;
     } else {
-	d = (struct dfa *)MALLOC(sizeof(struct dfa));
+	d = (struct dfa *) MALLOC(sizeof(struct dfa));
 	if (d == NULL) {
 	    ERR(REG_ESPACE);
 	    return NULL;
 	}
-	d->ssets = (struct sset *)MALLOC(nss * sizeof(struct sset));
+	d->ssets = (struct sset *) MALLOC(nss * sizeof(struct sset));
 	d->statesarea = (unsigned *)
 		MALLOC((nss+WORK) * wordsper * sizeof(unsigned));
 	d->work = &d->statesarea[nss * wordsper];
@@ -362,7 +359,7 @@ newdfa(
 	d->mallocarea = (char *)d;
 	if (d->ssets == NULL || d->statesarea == NULL ||
 		d->outsarea == NULL || d->incarea == NULL) {
-	    freedfa(d);
+	    freeDFA(d);
 	    ERR(REG_ESPACE);
 	    return NULL;
 	}
@@ -387,12 +384,12 @@ newdfa(
 }
 
 /*
- - freedfa - free a DFA
- ^ static void freedfa(struct dfa *);
+ - freeDFA - free a DFA
+ ^ static void freeDFA(struct dfa *);
  */
 static void
-freedfa(
-    struct dfa *d)
+freeDFA(
+    struct dfa *const d)
 {
     if (d->cptsmalloced) {
 	if (d->ssets != NULL) {
@@ -421,8 +418,8 @@ freedfa(
  */
 static unsigned
 hash(
-    unsigned *uv,
-    int n)
+    unsigned *const uv,
+    const int n)
 {
     int i;
     unsigned h;
@@ -440,9 +437,9 @@ hash(
  */
 static struct sset *
 initialize(
-    struct vars *v,		/* used only for debug flags */
-    struct dfa *d,
-    chr *start)
+    struct vars *const v,	/* used only for debug flags */
+    struct dfa *const d,
+    chr *const start)
 {
     struct sset *ss;
     int i;
@@ -454,7 +451,7 @@ initialize(
     if (d->nssused > 0 && (d->ssets[0].flags&STARTER)) {
 	ss = &d->ssets[0];
     } else {			/* no, must (re)build it */
-	ss = getvacant(v, d, start, start);
+	ss = getVacantSS(v, d, start, start);
 	for (i = 0; i < d->wordsper; i++) {
 	    ss->states[i] = 0;
 	}
@@ -484,23 +481,18 @@ initialize(
  */
 static struct sset *		/* NULL if goes to empty set */
 miss(
-    struct vars *v,		/* used only for debug flags */
-    struct dfa *d,
-    struct sset *css,
-    pcolor co,
-    chr *cp,			/* next chr */
-    chr *start)			/* where the attempt got started */
+    struct vars *const v,	/* used only for debug flags */
+    struct dfa *const d,
+    struct sset *const css,
+    const pcolor co,
+    chr *const cp,		/* next chr */
+    chr *const start)		/* where the attempt got started */
 {
     struct cnfa *cnfa = d->cnfa;
-    int i;
     unsigned h;
     struct carc *ca;
     struct sset *p;
-    int ispost;
-    int noprogress;
-    int gotstate;
-    int dolacons;
-    int sawlacons;
+    int i, isPost, noProgress, gotState, doLAConstraints, sawLAConstraints;
 
     /*
      * For convenience, we can be called even if it might not be a miss.
@@ -519,57 +511,57 @@ miss(
     for (i = 0; i < d->wordsper; i++) {
 	d->work[i] = 0;
     }
-    ispost = 0;
-    noprogress = 1;
-    gotstate = 0;
+    isPost = 0;
+    noProgress = 1;
+    gotState = 0;
     for (i = 0; i < d->nstates; i++) {
 	if (ISBSET(css->states, i)) {
-	    for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++) {
+	    for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) {
 		if (ca->co == co) {
 		    BSET(d->work, ca->to);
-		    gotstate = 1;
+		    gotState = 1;
 		    if (ca->to == cnfa->post) {
-			ispost = 1;
+			isPost = 1;
 		    }
-		    if (!cnfa->states[ca->to]->co) {
-			noprogress = 0;
+		    if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS)) {
+			noProgress = 0;
 		    }
 		    FDEBUG(("%d -> %d\n", i, ca->to));
 		}
 	    }
 	}
     }
-    dolacons = (gotstate) ? (cnfa->flags&HASLACONS) : 0;
-    sawlacons = 0;
-    while (dolacons) {		/* transitive closure */
-	dolacons = 0;
+    doLAConstraints = (gotState ? (cnfa->flags&HASLACONS) : 0);
+    sawLAConstraints = 0;
+    while (doLAConstraints) {		/* transitive closure */
+	doLAConstraints = 0;
 	for (i = 0; i < d->nstates; i++) {
 	    if (ISBSET(d->work, i)) {
-		for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++) {
-		    if (ca->co <= cnfa->ncolors) {
-			continue; /* NOTE CONTINUE */
+		for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) {
+		    if (ca->co < cnfa->ncolors) {
+			continue;	/* NOTE CONTINUE */
 		    }
-		    sawlacons = 1;
+		    sawLAConstraints = 1;
 		    if (ISBSET(d->work, ca->to)) {
-			continue; /* NOTE CONTINUE */
+			continue;	/* NOTE CONTINUE */
 		    }
-		    if (!lacon(v, cnfa, cp, ca->co)) {
-			continue; /* NOTE CONTINUE */
+		    if (!checkLAConstraint(v, cnfa, cp, ca->co)) {
+			continue;	/* NOTE CONTINUE */
 		    }
 		    BSET(d->work, ca->to);
-		    dolacons = 1;
+		    doLAConstraints = 1;
 		    if (ca->to == cnfa->post) {
-			ispost = 1;
+			isPost = 1;
 		    }
-		    if (!cnfa->states[ca->to]->co) {
-			noprogress = 0;
+		    if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS)) {
+			noProgress = 0;
 		    }
 		    FDEBUG(("%d :> %d\n", i, ca->to));
 		}
 	    }
 	}
     }
-    if (!gotstate) {
+    if (!gotState) {
 	return NULL;
     }
     h = HASH(d->work, d->wordsper);
@@ -580,19 +572,19 @@ miss(
 
     for (p = d->ssets, i = d->nssused; i > 0; p++, i--) {
 	 if (HIT(h, d->work, p, d->wordsper)) {
-	     FDEBUG(("cached c%d\n", p - d->ssets));
+	     FDEBUG(("cached c%d\n", (int) (p - d->ssets)));
 	     break;			/* NOTE BREAK OUT */
 	 }
     }
     if (i == 0) {		/* nope, need a new cache entry */
-	p = getvacant(v, d, cp, start);
+	p = getVacantSS(v, d, cp, start);
 	assert(p != css);
 	for (i = 0; i < d->wordsper; i++) {
 	    p->states[i] = d->work[i];
 	}
 	p->hash = h;
-	p->flags = (ispost) ? POSTSTATE : 0;
-	if (noprogress) {
+	p->flags = (isPost ? POSTSTATE : 0);
+	if (noProgress) {
 	    p->flags |= NOPROGRESS;
 	}
 
@@ -601,26 +593,27 @@ miss(
 	 */
     }
 
-    if (!sawlacons) {		/* lookahead conds. always cache miss */
-	FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, p - d->ssets));
+    if (!sawLAConstraints) {	/* lookahead conds. always cache miss */
+	FDEBUG(("c%d[%d]->c%d\n",
+		(int) (css - d->ssets), co, (int) (p - d->ssets)));
 	css->outs[co] = p;
 	css->inchain[co] = p->ins;
 	p->ins.ss = css;
-	p->ins.co = (color)co;
+	p->ins.co = (color) co;
     }
     return p;
 }
 
 /*
- - lacon - lookahead-constraint checker for miss()
- ^ static int lacon(struct vars *, struct cnfa *, chr *, pcolor);
+ - checkLAConstraint - lookahead-constraint checker for miss()
+ ^ static int checkLAConstraint(struct vars *, struct cnfa *, chr *, pcolor);
  */
 static int			/* predicate:  constraint satisfied? */
-lacon(
-    struct vars *v,
-    struct cnfa *pcnfa,		/* parent cnfa */
-    chr *cp,
-    pcolor co)			/* "color" of the lookahead constraint */
+checkLAConstraint(
+    struct vars *const v,
+    struct cnfa *const pcnfa,	/* parent cnfa */
+    chr *const cp,
+    const pcolor co)		/* "color" of the lookahead constraint */
 {
     int n;
     struct subre *sub;
@@ -632,38 +625,36 @@ lacon(
     assert(n < v->g->nlacons && v->g->lacons != NULL);
     FDEBUG(("=== testing lacon %d\n", n));
     sub = &v->g->lacons[n];
-    d = newdfa(v, &sub->cnfa, &v->g->cmap, &sd);
+    d = newDFA(v, &sub->cnfa, &v->g->cmap, &sd);
     if (d == NULL) {
 	ERR(REG_ESPACE);
 	return 0;
     }
-    end = longest(v, d, cp, v->stop, (int *)NULL);
-    freedfa(d);
+    end = longest(v, d, cp, v->stop, NULL);
+    freeDFA(d);
     FDEBUG(("=== lacon %d match %d\n", n, (end != NULL)));
     return (sub->subno) ? (end != NULL) : (end == NULL);
 }
 
 /*
- - getvacant - get a vacant state set
+ - getVacantSS - get a vacant state set
  * This routine clears out the inarcs and outarcs, but does not otherwise
  * clear the innards of the state set -- that's up to the caller.
- ^ static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);
+ ^ static struct sset *getVacantSS(struct vars *, struct dfa *, chr *, chr *);
  */
 static struct sset *
-getvacant(
-    struct vars *v,		/* used only for debug flags */
-    struct dfa *d,
-    chr *cp,
-    chr *start)
+getVacantSS(
+    struct vars *const v,	/* used only for debug flags */
+    struct dfa *const d,
+    chr *const cp,
+    chr *const start)
 {
     int i;
-    struct sset *ss;
-    struct sset *p;
-    struct arcp ap;
-    struct arcp lastap = {NULL, 0}; /* silence gcc 4 warning */
+    struct sset *ss, *p;
+    struct arcp ap, lastap = {NULL, 0}; /* silence gcc 4 warning */
     color co;
 
-    ss = pickss(v, d, cp, start);
+    ss = pickNextSS(v, d, cp, start);
     assert(!(ss->flags&LOCKED));
 
     /*
@@ -673,7 +664,7 @@ getvacant(
     ap = ss->ins;
     while ((p = ap.ss) != NULL) {
 	co = ap.co;
-	FDEBUG(("zapping c%d's %ld outarc\n", p - d->ssets, (long)co));
+	FDEBUG(("zapping c%d's %ld outarc\n", (int) (p - d->ssets), (long)co));
 	p->outs[co] = NULL;
 	ap = p->inchain[co];
 	p->inchain[co].ss = NULL; /* paranoia */
@@ -690,13 +681,12 @@ getvacant(
 	if (p == NULL) {
 	    continue;		/* NOTE CONTINUE */
 	}
-	FDEBUG(("del outarc %d from c%d's in chn\n", i, p - d->ssets));
+	FDEBUG(("del outarc %d from c%d's in chn\n", i, (int) (p - d->ssets)));
 	if (p->ins.ss == ss && p->ins.co == i) {
 	    p->ins = ss->inchain[i];
 	} else {
 	    assert(p->ins.ss != NULL);
-	    for (ap = p->ins; ap.ss != NULL &&
-		    !(ap.ss == ss && ap.co == i);
+	    for (ap = p->ins; ap.ss != NULL && !(ap.ss == ss && ap.co == i);
 		    ap = ap.ss->inchain[ap.co]) {
 		lastap = ap;
 	    }
@@ -729,19 +719,18 @@ getvacant(
 }
 
 /*
- - pickss - pick the next stateset to be used
- ^ static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);
+ - pickNextSS - pick the next stateset to be used
+ ^ static struct sset *pickNextSS(struct vars *, struct dfa *, chr *, chr *);
  */
 static struct sset *
-pickss(
-    struct vars *v,		/* used only for debug flags */
-    struct dfa *d,
-    chr *cp,
-    chr *start)
+pickNextSS(
+    struct vars *const v,	/* used only for debug flags */
+    struct dfa *const d,
+    chr *const cp,
+    chr *const start)
 {
     int i;
-    struct sset *ss;
-    struct sset *end;
+    struct sset *ss, *end;
     chr *ancient;
 
     /*
@@ -784,7 +773,7 @@ pickss(
 	if ((ss->lastseen == NULL || ss->lastseen < ancient)
 		&& !(ss->flags&LOCKED)) {
 	    d->search = ss + 1;
-	    FDEBUG(("replacing c%d\n", ss - d->ssets));
+	    FDEBUG(("replacing c%d\n", (int) (ss - d->ssets)));
 	    return ss;
 	}
     }
@@ -792,7 +781,7 @@ pickss(
 	if ((ss->lastseen == NULL || ss->lastseen < ancient)
 		&& !(ss->flags&LOCKED)) {
 	    d->search = ss + 1;
-	    FDEBUG(("replacing c%d\n", ss - d->ssets));
+	    FDEBUG(("replacing c%d\n", (int) (ss - d->ssets)));
 	    return ss;
 	}
     }
diff --git a/generic/regerror.c b/generic/regerror.c
index a1a0163..49d93ed 100644
--- a/generic/regerror.c
+++ b/generic/regerror.c
@@ -41,7 +41,7 @@ static const char unk[] = "*** unknown regex error code 0x%x ***";
  * Struct to map among codes, code names, and explanations.
  */
 
-static struct rerr {
+static const struct rerr {
     int code;
     const char *name;
     const char *explain;
@@ -62,7 +62,7 @@ regerror(
     char *errbuf,		/* Result buffer (unless errbuf_size==0) */
     size_t errbuf_size)		/* Available space in errbuf, can be 0 */
 {
-    struct rerr *r;
+    const struct rerr *r;
     const char *msg;
     char convbuf[sizeof(unk)+50]; /* 50 = plenty for int */
     size_t len;
diff --git a/generic/regex.h b/generic/regex.h
index b5b11bd..8845f72 100644
--- a/generic/regex.h
+++ b/generic/regex.h
@@ -1,5 +1,8 @@
 #ifndef _REGEX_H_
 #define	_REGEX_H_	/* never again */
+
+#include "tclInt.h"
+
 /*
  * regular expressions
  *
@@ -89,12 +92,6 @@ extern "C" {
 #ifdef __REG_REGOFF_T
 #undef __REG_REGOFF_T
 #endif
-#ifdef __REG_VOID_T
-#undef __REG_VOID_T
-#endif
-#ifdef __REG_CONST
-#undef __REG_CONST
-#endif
 #ifdef __REG_NOFRONT
 #undef __REG_NOFRONT
 #endif
@@ -104,8 +101,6 @@ extern "C" {
 /* interface types */
 #define	__REG_WIDE_T	Tcl_UniChar
 #define	__REG_REGOFF_T	long	/* not really right, but good enough... */
-#define	__REG_VOID_T	VOID
-#define	__REG_CONST	CONST
 /* names and declarations */
 #define	__REG_WIDE_COMPILE	TclReComp
 #define	__REG_WIDE_EXEC		TclReExec
@@ -131,26 +126,6 @@ typedef long regoff_t;
 #endif
 
 /*
- * For benefit of old compilers, we offer <sys/types.h> the option of
- * overriding the `void' type used to declare nonexistent return types.
- */
-#ifdef __REG_VOID_T
-typedef __REG_VOID_T re_void;
-#else
-typedef void re_void;
-#endif
-
-/*
- * Also for benefit of old compilers, <sys/types.h> can supply a macro which
- * expands to a substitute for `const'.
- */
-#ifndef __REG_CONST
-#define	__REG_CONST	const
-#endif
-
-
-
-/*
  * other interface types
  */
 
@@ -194,13 +169,13 @@ typedef struct {
 /*
  * compilation
  ^ #ifndef __REG_NOCHAR
- ^ int re_comp(regex_t *, __REG_CONST char *, size_t, int);
+ ^ int re_comp(regex_t *, const char *, size_t, int);
  ^ #endif
  ^ #ifndef __REG_NOFRONT
- ^ int regcomp(regex_t *, __REG_CONST char *, int);
+ ^ int regcomp(regex_t *, const char *, int);
  ^ #endif
  ^ #ifdef __REG_WIDE_T
- ^ int __REG_WIDE_COMPILE(regex_t *, __REG_CONST __REG_WIDE_T *, size_t, int);
+ ^ int __REG_WIDE_COMPILE(regex_t *, const __REG_WIDE_T *, size_t, int);
  ^ #endif
  */
 #define	REG_BASIC	000000	/* BREs (convenience) */
@@ -225,14 +200,14 @@ typedef struct {
 /*
  * execution
  ^ #ifndef __REG_NOCHAR
- ^ int re_exec(regex_t *, __REG_CONST char *, size_t,
+ ^ int re_exec(regex_t *, const char *, size_t,
  ^				rm_detail_t *, size_t, regmatch_t [], int);
  ^ #endif
  ^ #ifndef __REG_NOFRONT
- ^ int regexec(regex_t *, __REG_CONST char *, size_t, regmatch_t [], int);
+ ^ int regexec(regex_t *, const char *, size_t, regmatch_t [], int);
  ^ #endif
  ^ #ifdef __REG_WIDE_T
- ^ int __REG_WIDE_EXEC(regex_t *, __REG_CONST __REG_WIDE_T *, size_t,
+ ^ int __REG_WIDE_EXEC(regex_t *, const __REG_WIDE_T *, size_t,
  ^				rm_detail_t *, size_t, regmatch_t [], int);
  ^ #endif
  */
@@ -245,7 +220,7 @@ typedef struct {
 
 /*
  * misc generics (may be more functions here eventually)
- ^ re_void regfree(regex_t *);
+ ^ void regfree(regex_t *);
  */
 
 /*
@@ -257,7 +232,7 @@ typedef struct {
  * of character is used for error reports is independent of what kind is used
  * in matching.
  *
- ^ extern size_t regerror(int, __REG_CONST regex_t *, char *, size_t);
+ ^ extern size_t regerror(int, const regex_t *, char *, size_t);
  */
 #define	REG_OKAY	 0	/* no errors detected */
 #define	REG_NOMATCH	 1	/* failed to match */
@@ -290,25 +265,25 @@ typedef struct {
 /* automatically gathered by fwd; do not hand-edit */
 /* === regproto.h === */
 #ifndef __REG_NOCHAR
-int re_comp(regex_t *, __REG_CONST char *, size_t, int);
+int re_comp(regex_t *, const char *, size_t, int);
 #endif
 #ifndef __REG_NOFRONT
-int regcomp(regex_t *, __REG_CONST char *, int);
+int regcomp(regex_t *, const char *, int);
 #endif
 #ifdef __REG_WIDE_T
-MODULE_SCOPE int __REG_WIDE_COMPILE(regex_t *, __REG_CONST __REG_WIDE_T *, size_t, int);
+MODULE_SCOPE int __REG_WIDE_COMPILE(regex_t *, const __REG_WIDE_T *, size_t, int);
 #endif
 #ifndef __REG_NOCHAR
-int re_exec(regex_t *, __REG_CONST char *, size_t, rm_detail_t *, size_t, regmatch_t [], int);
+int re_exec(regex_t *, const char *, size_t, rm_detail_t *, size_t, regmatch_t [], int);
 #endif
 #ifndef __REG_NOFRONT
-int regexec(regex_t *, __REG_CONST char *, size_t, regmatch_t [], int);
+int regexec(regex_t *, const char *, size_t, regmatch_t [], int);
 #endif
 #ifdef __REG_WIDE_T
-MODULE_SCOPE int __REG_WIDE_EXEC(regex_t *, __REG_CONST __REG_WIDE_T *, size_t, rm_detail_t *, size_t, regmatch_t [], int);
+MODULE_SCOPE int __REG_WIDE_EXEC(regex_t *, const __REG_WIDE_T *, size_t, rm_detail_t *, size_t, regmatch_t [], int);
 #endif
-MODULE_SCOPE re_void regfree(regex_t *);
-MODULE_SCOPE size_t regerror(int, __REG_CONST regex_t *, char *, size_t);
+MODULE_SCOPE void regfree(regex_t *);
+MODULE_SCOPE size_t regerror(int, const regex_t *, char *, size_t);
 /* automatically gathered by fwd; do not hand-edit */
 /* =====^!^===== end forwards =====^!^===== */
 
@@ -320,3 +295,11 @@ MODULE_SCOPE size_t regerror(int, __REG_CONST regex_t *, char *, size_t);
 #endif
 
 #endif
+
+/*
+ * Local Variables:
+ * mode: c
+ * c-basic-offset: 4
+ * fill-column: 78
+ * End:
+ */
diff --git a/generic/regexec.c b/generic/regexec.c
index f3be137..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)
@@ -125,45 +125,45 @@ struct vars {
 /* =====^!^===== 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 int find(struct vars *, struct cnfa *, struct colormap *);
-static int cfind(struct vars *, struct cnfa *, struct colormap *);
-static int cfindloop(struct vars *, struct cnfa *, struct colormap *, struct dfa *, struct dfa *, chr **);
-static VOID zapsubs(regmatch_t *, size_t);
-static VOID zapmem(struct vars *, struct subre *);
-static VOID subset(struct vars *, struct subre *, chr *, chr *);
-static int dissect(struct vars *, struct subre *, chr *, chr *);
-static int condissect(struct vars *, struct subre *, chr *, chr *);
-static int altdissect(struct vars *, struct subre *, chr *, chr *);
+int exec(regex_t *, const chr *, size_t, rm_detail_t *, size_t, regmatch_t [], int);
+static struct dfa *getsubdfa(struct vars *, struct subre *);
+static int simpleFind(struct vars *const, struct cnfa *const, struct colormap *const);
+static int complicatedFind(struct vars *const, struct cnfa *const, struct colormap *const);
+static int complicatedFindLoop(struct vars *const, struct cnfa *const, struct colormap *const, struct dfa *const, struct dfa *const, chr **const);
+static void zapallsubs(regmatch_t *const, const size_t);
+static void zaptreesubs(struct vars *const, struct subre *const);
+static void subset(struct vars *const, struct subre *const, chr *const, chr *const);
 static int cdissect(struct vars *, struct subre *, chr *, chr *);
 static int ccondissect(struct vars *, struct subre *, chr *, chr *);
-static int crevdissect(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 *, struct dfa *, chr *, chr *, int *);
-static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *, chr **, int *);
-static chr *lastcold(struct vars *, struct dfa *);
-static struct dfa *newdfa(struct vars *, struct cnfa *, struct colormap *, struct smalldfa *);
-static VOID freedfa(struct dfa *);
-static unsigned hash(unsigned *, int);
-static struct sset *initialize(struct vars *, struct dfa *, chr *);
-static struct sset *miss(struct vars *, struct dfa *, struct sset *, pcolor, chr *, chr *);
-static int lacon(struct vars *, struct cnfa *, chr *, pcolor);
-static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);
-static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);
+static chr *longest(struct vars *const, struct dfa *const, chr *const, chr *const, int *const);
+static chr *shortest(struct vars *const, struct dfa *const, chr *const, chr *const, chr *const, chr **const, int *const);
+static chr *lastCold(struct vars *const, struct dfa *const);
+static struct dfa *newDFA(struct vars *const, struct cnfa *const, struct colormap *const, struct smalldfa *);
+static void freeDFA(struct dfa *const);
+static unsigned hash(unsigned *const, const int);
+static struct sset *initialize(struct vars *const, struct dfa *const, chr *const);
+static struct sset *miss(struct vars *const, struct dfa *const, struct sset *const, const pcolor, chr *const, chr *const);
+static int checkLAConstraint(struct vars *const, struct cnfa *const, chr *const, const pcolor);
+static struct sset *getVacantSS(struct vars *const, struct dfa *const, chr *const, chr *const);
+static struct sset *pickNextSS(struct vars *const, struct dfa *const, chr *const, chr *const);
 /* automatically gathered by fwd; do not hand-edit */
 /* =====^!^===== end forwards =====^!^===== */
 
 /*
  - exec - match regular expression
- ^ int exec(regex_t *, CONST chr *, size_t, rm_detail_t *,
+ ^ int exec(regex_t *, const chr *, size_t, rm_detail_t *,
  ^					size_t, regmatch_t [], int);
  */
 int
 exec(
     regex_t *re,
-    CONST chr *string,
+    const chr *string,
     size_t len,
     rm_detail_t *details,
     size_t nmatch,
@@ -171,13 +171,13 @@ exec(
     int flags)
 {
     AllocVars(v);
-    int st;
+    int st, backref;
     size_t n;
-    int backref;
+    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.
@@ -264,9 +256,9 @@ exec(
 
     assert(v->g->tree != NULL);
     if (backref) {
-	st = cfind(v, &v->g->tree->cnfa, &v->g->cmap);
+	st = complicatedFind(v, &v->g->tree->cnfa, &v->g->cmap);
     } else {
-	st = find(v, &v->g->tree->cnfa, &v->g->cmap);
+	st = simpleFind(v, &v->g->tree->cnfa, &v->g->cmap);
     }
 
     /*
@@ -274,7 +266,7 @@ exec(
      */
 
     if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) {
-	zapsubs(pmatch, nmatch);
+	zapallsubs(pmatch, nmatch);
 	n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
 	memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t));
     }
@@ -286,31 +278,49 @@ 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;
 }
 
 /*
- - find - find a match for the main NFA (no-complications case)
- ^ static int find(struct vars *, struct cnfa *, struct colormap *);
+ - getsubdfa - create or re-fetch the DFA for a subre node
+ * We only need to create the DFA once per overall regex execution.
+ * The DFA will be freed by the cleanup step in exec().
+ */
+static struct dfa *
+getsubdfa(struct vars * v,
+	  struct subre * t)
+{
+    if (v->subdfas[t->id] == NULL) {
+	v->subdfas[t->id] = newDFA(v, &t->cnfa, &v->g->cmap, DOMALLOC);
+	if (ISERR())
+	    return NULL;
+    }
+    return v->subdfas[t->id];
+}
+
+/*
+ - simpleFind - find a match for the main NFA (no-complications case)
+ ^ static int simpleFind(struct vars *, struct cnfa *, struct colormap *);
  */
 static int
-find(
-    struct vars *v,
-    struct cnfa *cnfa,
-    struct colormap *cm)
+simpleFind(
+    struct vars *const v,
+    struct cnfa *const cnfa,
+    struct colormap *const cm)
 {
-    struct dfa *s;
-    struct dfa *d;
-    chr *begin;
-    chr *end = NULL;
+    struct dfa *s, *d;
+    chr *begin, *end = NULL;
     chr *cold;
-    chr *open;			/* Open and close of range of possible
+    chr *open, *close;		/* Open and close of range of possible
 				 * starts */
-    chr *close;
     int hitend;
     int shorter = (v->g->tree->flags&SHORTER) ? 1 : 0;
 
@@ -318,13 +328,13 @@ find(
      * First, a shot with the search RE.
      */
 
-    s = newdfa(v, &v->g->search, cm, &v->dfa1);
+    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);
+    freeDFA(s);
     NOERR();
     if (v->g->cflags&REG_EXPECT) {
 	assert(v->details != NULL);
@@ -350,7 +360,7 @@ find(
     open = cold;
     cold = NULL;
     MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close)));
-    d = newdfa(v, cnfa, cm, &v->dfa1);
+    d = newDFA(v, cnfa, cm, &v->dfa1);
     assert(!(ISERR() && d != NULL));
     NOERR();
     for (begin = open; begin <= close; begin++) {
@@ -360,7 +370,10 @@ find(
 	} else {
 	    end = longest(v, d, begin, v->stop, &hitend);
 	}
-	NOERR();
+	if (ISERR()) {
+	    freeDFA(d);
+	    return v->err;
+	}
 	if (hitend && cold == NULL) {
 	    cold = begin;
 	}
@@ -369,7 +382,7 @@ find(
 	}
     }
     assert(end != NULL);	/* search RE succeeded so loop should */
-    freedfa(d);
+    freeDFA(d);
 
     /*
      * And pin down details.
@@ -391,41 +404,40 @@ find(
     }
 
     /*
-     * Submatches.
+     * Find submatches.
      */
 
-    zapsubs(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);
 }
 
 /*
- - cfind - find a match for the main NFA (with complications)
- ^ static int cfind(struct vars *, struct cnfa *, struct colormap *);
+ - complicatedFind - find a match for the main NFA (with complications)
+ ^ static int complicatedFind(struct vars *, struct cnfa *, struct colormap *);
  */
 static int
-cfind(
-    struct vars *v,
-    struct cnfa *cnfa,
-    struct colormap *cm)
+complicatedFind(
+    struct vars *const v,
+    struct cnfa *const cnfa,
+    struct colormap *const cm)
 {
-    struct dfa *s;
-    struct dfa *d;
+    struct dfa *s, *d;
     chr *cold = NULL; /* silence gcc 4 warning */
     int ret;
 
-    s = newdfa(v, &v->g->search, cm, &v->dfa1);
+    s = newDFA(v, &v->g->search, cm, &v->dfa1);
     NOERR();
-    d = newdfa(v, cnfa, cm, &v->dfa2);
+    d = newDFA(v, cnfa, cm, &v->dfa2);
     if (ISERR()) {
 	assert(d == NULL);
-	freedfa(s);
+	freeDFA(s);
 	return v->err;
     }
 
-    ret = cfindloop(v, cnfa, cm, d, s, &cold);
+    ret = complicatedFindLoop(v, cnfa, cm, d, s, &cold);
 
-    freedfa(d);
-    freedfa(s);
+    freeDFA(d);
+    freeDFA(s);
     NOERR();
     if (v->g->cflags&REG_EXPECT) {
 	assert(v->details != NULL);
@@ -440,30 +452,26 @@ cfind(
 }
 
 /*
- - cfindloop - the heart of cfind
- ^ static int cfindloop(struct vars *, struct cnfa *, struct colormap *,
+ - complicatedFindLoop - the heart of complicatedFind
+ ^ static int complicatedFindLoop(struct vars *, struct cnfa *, struct colormap *,
  ^	struct dfa *, struct dfa *, chr **);
  */
 static int
-cfindloop(
-    struct vars *v,
-    struct cnfa *cnfa,
-    struct colormap *cm,
-    struct dfa *d,
-    struct dfa *s,
-    chr **coldp)		/* where to put coldstart pointer */
+complicatedFindLoop(
+    struct vars *const v,
+    struct cnfa *const cnfa,
+    struct colormap *const cm,
+    struct dfa *const d,
+    struct dfa *const s,
+    chr **const coldp)		/* where to put coldstart pointer */
 {
-    chr *begin;
-    chr *end;
+    chr *begin, *end;
     chr *cold;
-    chr *open;			/* Open and close of range of possible
+    chr *open, *close;		/* Open and close of range of possible
 				 * starts */
-    chr *close;
-    chr *estart;
-    chr *estop;
-    int er;
+    chr *estart, *estop;
+    int er, hitend;
     int shorter = v->g->tree->flags&SHORTER;
-    int hitend;
 
     assert(d != NULL && s != NULL);
     cold = NULL;
@@ -479,7 +487,7 @@ cfindloop(
 	cold = NULL;
 	MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close)));
 	for (begin = open; begin <= close; begin++) {
-	    MDEBUG(("\ncfind trying at %ld\n", LOFF(begin)));
+	    MDEBUG(("\ncomplicatedFind trying at %ld\n", LOFF(begin)));
 	    estart = begin;
 	    estop = v->stop;
 	    for (;;) {
@@ -496,8 +504,7 @@ cfindloop(
 		}
 
 		MDEBUG(("tentative end %ld\n", LOFF(end)));
-		zapsubs(v->pmatch, v->nmatch);
-		zapmem(v, v->g->tree);
+		zapallsubs(v->pmatch, v->nmatch);
 		er = cdissect(v, v->g->tree, begin, end);
 		if (er == REG_OKAY) {
 		    if (v->nmatch > 0) {
@@ -509,6 +516,7 @@ cfindloop(
 		}
 		if (er != REG_NOMATCH) {
 		    ERR(er);
+		    *coldp = cold;
 		    return er;
 		}
 		if ((shorter) ? end == estop : end == begin) {
@@ -533,13 +541,13 @@ cfindloop(
 }
 
 /*
- - zapsubs - initialize the subexpression matches to "no match"
- ^ static VOID zapsubs(regmatch_t *, size_t);
+ - zapallsubs - initialize all subexpression matches to "no match"
+ ^ static void zapallsubs(regmatch_t *, size_t);
  */
 static void
-zapsubs(
-    regmatch_t *p,
-    size_t n)
+zapallsubs(
+    regmatch_t *const p,
+    const size_t n)
 {
     size_t i;
 
@@ -550,44 +558,41 @@ zapsubs(
 }
 
 /*
- - zapmem - initialize the retry memory of a subtree to zeros
- ^ static VOID zapmem(struct vars *, struct subre *);
+ - zaptreesubs - initialize subexpressions within subtree to "no match"
+ ^ static void zaptreesubs(struct vars *, struct subre *);
  */
 static void
-zapmem(
-    struct vars *v,
-    struct subre *t)
+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) {
-	zapmem(v, t->left);
+	zaptreesubs(v, t->left);
     }
     if (t->right != NULL) {
-	zapmem(v, t->right);
+	zaptreesubs(v, t->right);
     }
 }
 
 /*
- - subset - set any subexpression relevant to a successful subre
- ^ static VOID subset(struct vars *, struct subre *, chr *, chr *);
+ - subset - set subexpression match data for a successful subre
+ ^ static void subset(struct vars *, struct subre *, chr *, chr *);
  */
 static void
 subset(
-    struct vars *v,
-    struct subre *sub,
-    chr *begin,
-    chr *end)
+    struct vars *const v,
+    struct subre *const sub,
+    chr *const begin,
+    chr *const end)
 {
     int n = sub->subno;
 
@@ -602,185 +607,25 @@ subset(
 }
 
 /*
- - dissect - determine subexpression matches (uncomplicated case)
- ^ static int dissect(struct vars *, struct subre *, chr *, chr *);
- */
-static int			/* regexec return code */
-dissect(
-    struct vars *v,
-    struct subre *t,
-    chr *begin,			/* beginning of relevant substring */
-    chr *end)			/* end of same */
-{
-    assert(t != NULL);
-    MDEBUG(("dissect %ld-%ld\n", LOFF(begin), LOFF(end)));
-
-    switch (t->op) {
-    case '=':			/* terminal node */
-	assert(t->left == NULL && t->right == NULL);
-	return REG_OKAY;	/* no action, parent did the work */
-    case '|':			/* alternation */
-	assert(t->left != NULL);
-	return altdissect(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 condissect(v, t, begin, end);
-    case '(':			/* capturing */
-	assert(t->left != NULL && t->right == NULL);
-	assert(t->subno > 0);
-	subset(v, t, begin, end);
-	return dissect(v, t->left, begin, end);
-    default:
-	return REG_ASSERT;
-    }
-}
-
-/*
- - condissect - determine concatenation subexpression matches (uncomplicated)
- ^ static int condissect(struct vars *, struct subre *, chr *, chr *);
- */
-static int			/* regexec return code */
-condissect(
-    struct vars *v,
-    struct subre *t,
-    chr *begin,			/* beginning of relevant substring */
-    chr *end)			/* end of same */
-{
-    struct dfa *d;
-    struct dfa *d2;
-    chr *mid;
-    int i;
-    int shorter = (t->left->flags&SHORTER) ? 1 : 0;
-    chr *stop = (shorter) ? end : begin;
-
-    assert(t->op == '.');
-    assert(t->left != NULL && t->left->cnfa.nstates > 0);
-    assert(t->right != NULL && t->right->cnfa.nstates > 0);
-
-    d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
-    NOERR();
-    d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &v->dfa2);
-    if (ISERR()) {
-	assert(d2 == NULL);
-	freedfa(d);
-	return v->err;
-    }
-
-    /*
-     * Pick a tentative midpoint.
-     */
-
-    if (shorter) {
-	mid = shortest(v, d, begin, begin, end, 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);
-}
-
-/*
- - altdissect - determine alternative subexpression matches (uncomplicated)
- ^ static int altdissect(struct vars *, struct subre *, chr *, chr *);
- */
-static int			/* regexec return code */
-altdissect(
-    struct vars *v,
-    struct subre *t,
-    chr *begin,			/* beginning of relevant substring */
-    chr *end)			/* end of same */
-{
-    struct dfa *d;
-    int i;
-
-    assert(t != NULL);
-    assert(t->op == '|');
-
-    for (i = 0; t != NULL; t = t->right, i++) {
-	MDEBUG(("trying %dth\n", i));
-	assert(t->left != NULL && t->left->cnfa.nstates > 0);
-	d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
-	if (ISERR()) {
-	    return v->err;
-	}
-	if (longest(v, d, begin, end, NULL) == end) {
-	    MDEBUG(("success\n"));
-	    freedfa(d);
-	    return dissect(v, t->left, begin, end);
-	}
-	freedfa(d);
-    }
-    return REG_ASSERT;		/* none of them matched?!? */
-}
-
-/*
- - cdissect - determine subexpression matches (with complications)
- * The retry memory stores the offset of the trial midpoint from begin, plus 1
- * so that 0 uniquely means "clean slate".
+ - 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 */
+    chr *begin,		/* beginning of relevant substring */
+    chr *end)		/* end of same */
 {
     int er;
 
@@ -790,16 +635,30 @@ cdissect(
     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 caltdissect(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 cbrdissect(v, t, begin, end);
+	er = cbrdissect(v, t, begin, end);
+	break;
     case '.':			/* concatenation */
 	assert(t->left != NULL && t->right != NULL);
-	return ccondissect(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);
@@ -807,65 +666,56 @@ cdissect(
 	if (er == REG_OKAY) {
 	    subset(v, t, begin, end);
 	}
-	return er;
+	break;
     default:
-	return REG_ASSERT;
+	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 - 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".
+ - 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 */
+    chr *begin,		/* beginning of relevant substring */
+    chr *end)		/* end of same */
 {
     struct dfa *d, *d2;
     chr *mid;
-    int er;
 
     assert(t->op == '.');
     assert(t->left != NULL && t->left->cnfa.nstates > 0);
     assert(t->right != NULL && t->right->cnfa.nstates > 0);
+    assert(!(t->left->flags & SHORTER));
 
-    if (t->left->flags&SHORTER) { /* reverse scan */
-	return crevdissect(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.
@@ -877,23 +727,20 @@ ccondissect(
 	 */
 
 	if (longest(v, d2, mid, end, NULL) == end) {
-	    er = cdissect(v, t->left, begin, mid);
+	    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"));
-		    freedfa(d);
-		    freedfa(d2);
 		    return REG_OKAY;
 		}
 	    }
-	    if ((er != REG_OKAY) && (er != REG_NOMATCH)) {
-		freedfa(d);
-		freedfa(d2);
+	    if (er != REG_NOMATCH) {
 		return er;
 	    }
 	}
@@ -907,9 +754,7 @@ ccondissect(
 	     * 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);
@@ -918,73 +763,50 @@ ccondissect(
 	     * 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;
-	zapmem(v, t->left);
-	zapmem(v, t->right);
+	MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));
+	zaptreesubs(v, t->left);
+	zaptreesubs(v, t->right);
     }
 }
 
 /*
- - crevdissect - determine backref shortest-first subexpression matches
- * The retry memory stores the offset of the trial midpoint from begin, plus 1
- * so that 0 uniquely means "clean slate".
- ^ static int crevdissect(struct vars *, struct subre *, chr *, chr *);
+ - crevcondissect - dissect match for concatenation node, shortest-first
+ ^ static int crevcondissect(struct vars *, struct subre *, chr *, chr *);
  */
 static int			/* regexec return code */
-crevdissect(
+crevcondissect(
     struct vars *v,
     struct subre *t,
-    chr *begin,			/* beginning of relevant substring */
-    chr *end)			/* end of same */
+    chr *begin,		/* beginning of relevant substring */
+    chr *end)		/* end of same */
 {
-    struct dfa *d;
-    struct dfa *d2;
+    struct dfa *d, *d2;
     chr *mid;
-    int er;
 
     assert(t->op == '.');
     assert(t->left != NULL && t->left->cnfa.nstates > 0);
     assert(t->right != NULL && t->right->cnfa.nstates > 0);
     assert(t->left->flags&SHORTER);
 
-    /*
-     * Concatenation -- need to split the substring between parts.
-     */
+    d = 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.
@@ -996,7 +818,8 @@ crevdissect(
 	 */
 
 	if (longest(v, d2, mid, end, NULL) == end) {
-	    er = cdissect(v, t->left, begin, mid);
+	    int er = cdissect(v, t->left, begin, mid);
+
 	    if (er == REG_OKAY) {
 		er = cdissect(v, t->right, mid, end);
 		if (er == REG_OKAY) {
@@ -1005,14 +828,10 @@ crevdissect(
 		     */
 
 		    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;
 	    }
 	}
@@ -1026,9 +845,7 @@ crevdissect(
 	     * 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);
@@ -1037,157 +854,474 @@ crevdissect(
 	     * 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;
-	zapmem(v, t->left);
-	zapmem(v, t->right);
+	MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));
+	zaptreesubs(v, t->left);
+	zaptreesubs(v, t->right);
     }
 }
 
 /*
- - cbrdissect - determine backref subexpression matches
+ - 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 */
+    chr *begin,		/* beginning of relevant substring */
+    chr *end)		/* end of same */
 {
-    int i;
-    int n = t->subno;
-    size_t len;
-    chr *paren;
+    int n = t->subno, min = t->min, max = t->max;
+    size_t numreps;
+    size_t tlen;
+    size_t brlen;
+    chr *brstring;
     chr *p;
-    chr *stop;
-    int min = t->min;
-    int max = t->max;
 
     assert(t != NULL);
     assert(t->op == 'b');
     assert(n >= 0);
     assert((size_t)n < v->nmatch);
 
-    MDEBUG(("cbackref n%d %d{%d-%d}\n", t->retry, n, min, max));
+    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;
 }
 
 /*
- - caltdissect - determine alternative subexpression matches (w. complications)
- ^ static int caltdissect(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 */
-caltdissect(
-    struct vars *v,
-    struct subre *t,
-    chr *begin,			/* beginning of relevant substring */
-    chr *end)			/* end of same */
+creviterdissect(struct vars * v,
+		struct subre * t,
+		chr *begin,	/* beginning of relevant substring */
+		chr *end)	/* end of same */
 {
     struct dfa *d;
-    int er;
-#define	UNTRIED	0		/* not yet tried at all */
-#define	TRYING	1		/* top matched, trying submatches */
-#define	TRIED	2		/* top didn't match or submatches exhausted */
+    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 (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) {
-	return caltdissect(v, t->right, begin, end);
+
+    /*
+     * 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) {
-	d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
-	if (ISERR()) {
-	    return v->err;
+    /* 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;
 	}
-	if (longest(v, d, begin, end, NULL) != end) {
-	    freedfa(d);
-	    v->mem[t->retry] = TRIED;
-	    return caltdissect(v, t->right, begin, 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 */
+	    FREE(endpts);
+	    return er;
 	}
-	freedfa(d);
-	MDEBUG(("calt matched\n"));
-	v->mem[t->retry] = TRYING;
-    }
 
-    er = cdissect(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;
-    return caltdissect(v, t->right, begin, end);
+    /* all possibilities exhausted */
+    MDEBUG(("%d failed\n", t->id));
+    FREE(endpts);
+    return REG_NOMATCH;
 }
 
 #include "rege_dfa.c"
diff --git a/generic/regfronts.c b/generic/regfronts.c
index 5003297..088a640 100644
--- a/generic/regfronts.c
+++ b/generic/regfronts.c
@@ -39,7 +39,7 @@
 int
 regcomp(
     regex_t *re,
-    CONST char *str,
+    const char *str,
     int flags)
 {
     size_t len;
@@ -61,12 +61,12 @@ regcomp(
 int
 regexec(
     regex_t *re,
-    CONST char *str,
+    const char *str,
     size_t nmatch,
     regmatch_t pmatch[],
     int flags)
 {
-    CONST char *start;
+    const char *start;
     size_t len;
     int f = flags;
 
diff --git a/generic/regguts.h b/generic/regguts.h
index 72bdcb3..1ac2465 100644
--- a/generic/regguts.h
+++ b/generic/regguts.h
@@ -39,15 +39,6 @@
  * Things that regcustom.h might override.
  */
 
-/* standard header files (NULL is a reasonable indicator for them) */
-#ifndef NULL
-#include <stdio.h>
-#include <stdlib.h>
-#include <ctype.h>
-#include <limits.h>
-#include <string.h>
-#endif
-
 /* assertions */
 #ifndef assert
 #ifndef REG_DEBUG
@@ -75,11 +66,6 @@
 #define	NOPARMS	void		/* for empty parm lists */
 #endif
 
-/* const */
-#ifndef CONST
-#define	CONST	const		/* for old compilers, might be empty */
-#endif
-
 /* function-pointer declarator */
 #ifndef FUNCPTR
 #if __STDC__ >= 1
@@ -101,9 +87,6 @@
 #endif
 
 /* want size of a char in bits, and max value in bounded quantifiers */
-#ifndef CHAR_BIT
-#include <limits.h>
-#endif
 #ifndef _POSIX2_RE_DUP_MAX
 #define	_POSIX2_RE_DUP_MAX 255	/* normally from <limits.h> */
 #endif
@@ -203,7 +186,14 @@ struct colordesc {
     union tree *block;		/* block of solid color, if any */
 };
 
-/* the color map itself */
+/*
+ * The color map itself
+ *
+ * Much of the data in the colormap struct is only used at compile time.
+ * However, the bulk of the space usage is in the "tree" structure, so it's
+ * not clear that there's much point in converting the rest to a more compact
+ * form when compilation is finished.
+ */
 struct colormap {
     int magic;
 #define	CMMAGIC	0x876
@@ -259,12 +249,11 @@ struct cvec {
 struct state;
 
 struct arc {
-    int type;
-#define	ARCFREE	'\0'
+    int type;			/* 0 if free, else an NFA arc type code */
     color co;
     struct state *from;		/* where it's from (and contained within) */
     struct state *to;		/* where it's to */
-    struct arc *outchain;	/* *from's outs chain or free chain */
+    struct arc *outchain;	/* link in *from's outs chain or free chain */
     struct arc *outchainRev;	/* back-link in *from's outs chain */
 #define	freechain outchain	/* we do not maintain "freechainRev" */
     struct arc *inchain;	/* *to's ins chain */
@@ -313,11 +302,22 @@ struct nfa {
 
 /*
  * definitions for compacted NFA
+ *
+ * The main space savings in a compacted NFA is from making the arcs as small
+ * as possible.  We store only the transition color and next-state number for
+ * each arc.  The list of out arcs for each state is an array beginning at
+ * cnfa.states[statenumber], and terminated by a dummy carc struct with
+ * co == COLORLESS.
+ *
+ * The non-dummy carc structs are of two types: plain arcs and LACON arcs.
+ * Plain arcs just store the transition color number as "co".  LACON arcs
+ * store the lookahead constraint number plus cnfa.ncolors as "co".  LACON
+ * arcs can be distinguished from plain by testing for co >= cnfa.ncolors.
  */
 
 struct carc {
     color co;			/* COLORLESS is list terminator */
-    int to;			/* state number */
+    int to;			/* next-state number */
 };
 
 struct cnfa {
@@ -329,7 +329,10 @@ struct cnfa {
     int post;			/* teardown state number */
     color bos[2];		/* colors, if any, assigned to BOS and BOL */
     color eos[2];		/* colors, if any, assigned to EOS and EOL */
+    char *stflags;		/* vector of per-state flags bytes */
+#define CNFA_NOPROGRESS	01	/* flag bit for a no-progress state */
     struct carc **states;	/* vector of pointers to outarc lists */
+    /* states[n] are pointers into a single malloc'd array of arcs */
     struct carc *arcs;		/* the area for the lists */
 };
 #define	ZAPCNFA(cnfa)	((cnfa).nstates = 0)
@@ -350,11 +353,28 @@ struct cnfa {
 
 /*
  * subexpression tree
+ *
+ * "op" is one of:
+ *	'='  plain regex without interesting substructure (implemented as DFA)
+ *	'b'  back-reference (has no substructure either)
+ *	'('  capture node: captures the match of its single child
+ *	'.'  concatenation: matches a match for left, then a match for right
+ *	'|'  alternation: matches a match for left or a match for right
+ *	'*'  iteration: matches some number of matches of its single child
+ *
+ * Note: the right child of an alternation must be another alternation or
+ * NULL; hence, an N-way branch requires N alternation nodes, not N-1 as you
+ * might expect.  This could stand to be changed.  Actually I'd rather see
+ * a single alternation node with N children, but that will take revising
+ * the representation of struct subre.
+ *
+ * Note: when a backref is directly quantified, we stick the min/max counts
+ * into the backref rather than plastering an iteration node on top.  This is
+ * for efficiency: there is no need to search for possible division points.
  */
 
 struct subre {
-    char op;			/* '|', '.' (concat), 'b' (backref), '(',
-				 * '=' */
+    char op;			/* see type codes above */
     char flags;
 #define	LONGER	01		/* prefers longer match */
 #define	SHORTER	02		/* prefers shorter match */
@@ -370,10 +390,10 @@ struct subre {
 #define	PREF(f)	((f)&NOPROP)
 #define	PREF2(f1, f2)	((PREF(f1) != 0) ? PREF(f1) : PREF(f2))
 #define	COMBINE(f1, f2)	(UP((f1)|(f2)) | PREF2(f1, f2))
-    short retry;		/* index into retry memory */
+    short id;			/* ID of subre (1..ntree-1) */
     int subno;			/* subexpression number (for 'b' and '(') */
-    short min;			/* min repetitions, for backref only */
-    short max;			/* max repetitions, for backref only */
+    short min;			/* min repetitions for iteration or backref */
+    short max;			/* max repetitions for iteration or backref */
     struct subre *left;		/* left child, if any (also freelist chain) */
     struct subre *right;	/* right child, if any */
     struct state *begin;	/* outarcs from here... */
@@ -388,7 +408,7 @@ struct subre {
  */
 
 struct fns {
-    VOID FUNCPTR(free, (regex_t *));
+    void FUNCPTR(free, (regex_t *));
 };
 
 /*
@@ -403,9 +423,9 @@ struct guts {
     size_t nsub;		/* copy of re_nsub */
     struct subre *tree;
     struct cnfa search;		/* for fast preliminary search */
-    int ntree;
+    int ntree;			/* number of subre's, plus one */
     struct colormap cmap;
-    int FUNCPTR(compare, (CONST chr *, CONST chr *, size_t));
+    int FUNCPTR(compare, (const chr *, const chr *, size_t));
     struct subre *lacons;	/* lookahead-constraint vector */
     int nlacons;		/* size of lacons */
 };
-- 
cgit v0.12


From c6539f705204b2d9e3162304ac3a06c824ce5f39 Mon Sep 17 00:00:00 2001
From: "jan.nijtmans" <nijtmans@users.sourceforge.net>
Date: Fri, 29 Jan 2016 22:32:03 +0000
Subject: Backout TIP #388 implementation, this part doesn't belong in 8.5

---
 generic/regc_lex.c  | 35 ++++++++++-------------------------
 generic/regcomp.c   |  2 +-
 generic/regcustom.h |  2 +-
 3 files changed, 12 insertions(+), 27 deletions(-)

diff --git a/generic/regc_lex.c b/generic/regc_lex.c
index 16e3ae9..588932b 100644
--- a/generic/regc_lex.c
+++ b/generic/regc_lex.c
@@ -742,7 +742,6 @@ lexescape(
     struct vars *v)
 {
     chr c;
-    int i;
     static const chr alert[] = {
 	CHR('a'), CHR('l'), CHR('e'), CHR('r'), CHR('t')
     };
@@ -819,23 +818,18 @@ lexescape(
 	RETV(PLAIN, CHR('\t'));
 	break;
     case CHR('u'):
-	c = (uchr) lexdigits(v, 16, 1, 4);
+	c = lexdigits(v, 16, 4, 4);
 	if (ISERR()) {
 	    FAILW(REG_EESCAPE);
 	}
 	RETV(PLAIN, c);
 	break;
     case CHR('U'):
-	i = lexdigits(v, 16, 1, 8);
+	c = lexdigits(v, 16, 8, 8);
 	if (ISERR()) {
 	    FAILW(REG_EESCAPE);
 	}
-	if (i > 0xFFFF) {
-	    /* TODO: output a Surrogate pair
-	     */
-	    i = 0xFFFD;
-	}
-	RETV(PLAIN, (uchr) i);
+	RETV(PLAIN, c);
 	break;
     case CHR('v'):
 	RETV(PLAIN, CHR('\v'));
@@ -850,7 +844,7 @@ lexescape(
 	break;
     case CHR('x'):
 	NOTE(REG_UUNPORT);
-	c = (uchr) lexdigits(v, 16, 1, 2);
+	c = lexdigits(v, 16, 1, 255);	/* REs >255 long outside spec */
 	if (ISERR()) {
 	    FAILW(REG_EESCAPE);
 	}
@@ -872,7 +866,7 @@ lexescape(
     case CHR('9'):
 	save = v->now;
 	v->now--;		/* put first digit back */
-	c = (uchr) lexdigits(v, 10, 1, 255);	/* REs >255 long outside spec */
+	c = lexdigits(v, 10, 1, 255);	/* REs >255 long outside spec */
 	if (ISERR()) {
 	    FAILW(REG_EESCAPE);
 	}
@@ -899,15 +893,10 @@ lexescape(
     case CHR('0'):
 	NOTE(REG_UUNPORT);
 	v->now--;		/* put first digit back */
-	c = (uchr) lexdigits(v, 8, 1, 3);
+	c = lexdigits(v, 8, 1, 3);
 	if (ISERR()) {
 	    FAILW(REG_EESCAPE);
 	}
-	if (c > 0xff) {
-	    /* out of range, so we handled one digit too much */
-	    v->now--;
-	    c >>= 3;
-	}
 	RETV(PLAIN, c);
 	break;
     default:
@@ -920,16 +909,16 @@ lexescape(
 
 /*
  - lexdigits - slurp up digits and return chr value
- ^ static int lexdigits(struct vars *, int, int, int);
+ ^ static chr lexdigits(struct vars *, int, int, int);
  */
-static int			/* chr value; errors signalled via ERR */
+static chr			/* chr value; errors signalled via ERR */
 lexdigits(
     struct vars *v,
     int base,
     int minlen,
     int maxlen)
 {
-    int n;
+    uchr n;			/* unsigned to avoid overflow misbehavior */
     int len;
     chr c;
     int d;
@@ -937,10 +926,6 @@ lexdigits(
 
     n = 0;
     for (len = 0; len < maxlen && !ATEOS(); len++) {
-	if (n > 0x10fff) {
-	    /* Stop when continuing would otherwise overflow */
-	    break;
-	}
 	c = *v->now++;
 	switch (c) {
 	case CHR('0'): case CHR('1'): case CHR('2'): case CHR('3'):
@@ -973,7 +958,7 @@ lexdigits(
 	ERR(REG_EESCAPE);
     }
 
-    return n;
+    return (chr)n;
 }
 
 /*
diff --git a/generic/regcomp.c b/generic/regcomp.c
index 211cd70..bee35d0 100644
--- a/generic/regcomp.c
+++ b/generic/regcomp.c
@@ -79,7 +79,7 @@ static void lexnest(struct vars *, const chr *, const chr *);
 static void lexword(struct vars *);
 static int next(struct vars *);
 static int lexescape(struct vars *);
-static int lexdigits(struct vars *, int, int, int);
+static chr lexdigits(struct vars *, int, int, int);
 static int brenext(struct vars *, pchr);
 static void skip(struct vars *);
 static chr newline(NOPARMS);
diff --git a/generic/regcustom.h b/generic/regcustom.h
index 681b97d..c2583fa 100644
--- a/generic/regcustom.h
+++ b/generic/regcustom.h
@@ -89,7 +89,7 @@ typedef int celt;		/* Type to hold chr, or NOCELT */
 #define	NOCELT (-1)		/* Celt value which is not valid chr */
 #define	CHR(c) (UCHAR(c))	/* Turn char literal into chr literal */
 #define	DIGITVAL(c) ((c)-'0')	/* Turn chr digit into its value */
-#if TCL_UTF_MAX > 4
+#if TCL_UTF_MAX > 3
 #define	CHRBITS	32		/* Bits in a chr; must not use sizeof */
 #define	CHR_MIN	0x00000000	/* Smallest and largest chr; the value */
 #define	CHR_MAX	0xffffffff	/* CHR_MAX-CHR_MIN+1 should fit in uchr */
-- 
cgit v0.12


From 7f3416400096e5498584c1ee4cad6b110314a936 Mon Sep 17 00:00:00 2001
From: "jan.nijtmans" <nijtmans@users.sourceforge.net>
Date: Fri, 29 Jan 2016 22:49:52 +0000
Subject: Backout TIP #413 as well

---
 generic/regc_locale.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/generic/regc_locale.c b/generic/regc_locale.c
index 3c10cb6..2a4248e 100644
--- a/generic/regc_locale.c
+++ b/generic/regc_locale.c
@@ -389,7 +389,7 @@ static const crange spaceRangeTable[] = {
 #define NUM_SPACE_RANGE (sizeof(spaceRangeTable)/sizeof(crange))
 
 static const chr spaceCharTable[] = {
-    0x20, 0x85, 0xa0, 0x1680, 0x180e, 0x2028, 0x2029, 0x202f, 0x205f,
+    0x20, 0xa0, 0x1680, 0x180e, 0x2028, 0x2029, 0x202f, 0x205f,
     0x2060, 0x3000, 0xfeff
 };
 
-- 
cgit v0.12

