* generic/regc_color.c:

	* generic/regc_cvec.c:
	* generic/regc_lex.c:
	* generic/regc_locale.c:
	* generic/regcomp.c:
	* generic/regcustom.h:
	* generic/regerrs.h:
	* generic/regex.h:
	* generic/regexec.c:
	* generic/regguts.h:
	* generic/tclRegexp.c:
	* generic/tclTest.c:
	* tests/reg.test: updated to Henry Spencer's new regexp engine
	(mid-Sept 99).  Should greatly reduce stack space reqs.

12 files changed, 127 insertions, 142 deletions

diff --git a/generic/regc_color.c b/generic/regc_color.c
index 503bca2..5aed21c 100644
--- a/generic/regc_color.c
+++ b/generic/regc_color.c
@@ -97,7 +97,7 @@ struct colormap *cm;
 	cm->magic = 0;
 	if (NBYTS > 1)
 		cmtreefree(cm, cm->tree, 0);
-	for (i = 1; i < cm->max; i++)		/* skip WHITE */
+	for (i = 1; i <= cm->max; i++)		/* skip WHITE */
 		if (!UNUSEDCOLOR(&cm->cd[i])) {
 			cb = cm->cd[i].block;
 			if (cb != NULL)
@@ -456,7 +456,7 @@ struct state *rp;
 	color co;
 	color sco;
 
-	assert((uc & BYTMASK) == 0);
+	assert((uc % BYTTAB) == 0);
 
 	/* find its color block, making new pointer blocks as needed */
 	t = cm->tree;
@@ -614,8 +614,6 @@ struct arc *a;
 	a->colorchain = NULL;	/* paranoia */
 }
 
-#ifdef NOTDEF			/* This isn't used currently. */
-
 /*
  - singleton - is this character in its own color?
  ^ static int singleton(struct colormap *, pchr c);
@@ -633,8 +631,6 @@ pchr c;
 	return 0;
 }
 
-#endif /* NOTDEF */
-
 /*
  - rainbow - add arcs of all full colors (but one) between specified states
  ^ static VOID rainbow(struct nfa *, struct colormap *, int, pcolor,
diff --git a/generic/regc_cvec.c b/generic/regc_cvec.c
index 73ccc56..86765ea 100644
--- a/generic/regc_cvec.c
+++ b/generic/regc_cvec.c
@@ -110,8 +110,6 @@ pchr to;
 	cv->nranges++;
 }
 
-#ifdef NOTDEF			/* This isn't used currently. */
-
 /*
  - addmcce - add an MCCE to a cvec
  ^ static VOID addmcce(struct cvec *, chr *, chr *);
@@ -122,25 +120,26 @@ struct cvec *cv;
 chr *startp;			/* beginning of text */
 chr *endp;			/* just past end of text */
 {
-	int n = endp - startp;
+	int len;
 	int i;
 	chr *s;
 	chr *d;
 
-	assert(n > 0);
-	assert(cv->nchrs + n < cv->chrspace - cv->nmccechrs);
+	if (startp == NULL && endp == NULL)
+		return;
+	len = endp - startp;
+	assert(len > 0);
+	assert(cv->nchrs + len < cv->chrspace - cv->nmccechrs);
 	assert(cv->nmcces < cv->mccespace);
-	d = &cv->chrs[cv->chrspace - cv->nmccechrs - n - 1];
+	d = &cv->chrs[cv->chrspace - cv->nmccechrs - len - 1];
 	cv->mcces[cv->nmcces++] = d;
-	for (s = startp, i = n; i > 0; s++, i--)
+	for (s = startp, i = len; i > 0; s++, i--)
 		*d++ = *s;
 	*d++ = 0;		/* endmarker */
 	assert(d == &cv->chrs[cv->chrspace - cv->nmccechrs]);
-	cv->nmccechrs += n + 1;
+	cv->nmccechrs += len + 1;
 }
 
-#endif /* NOTDEF */
-
 /*
  - haschr - does a cvec contain this chr?
  ^ static int haschr(struct cvec *, pchr);
diff --git a/generic/regc_lex.c b/generic/regc_lex.c
index e20b222..1acc3f4 100644
--- a/generic/regc_lex.c
+++ b/generic/regc_lex.c
@@ -1010,8 +1010,9 @@ newline()
 }
 
 /*
- - ch - return the chr sequence for locale.c's fake collating element ch
- * This helps confine use of CHR to this source file.
+ - 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 chr *ch(NOPARMS);
  ^ #endif
diff --git a/generic/regc_locale.c b/generic/regc_locale.c
index b198727..3bac3ed 100644
--- a/generic/regc_locale.c
+++ b/generic/regc_locale.c
@@ -9,7 +9,7 @@
  * See the file "license.terms" for information on usage and redistribution
  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  *
- * RCS: @(#) $Id: regc_locale.c,v 1.4 1999/06/24 03:27:56 stanton Exp $
+ * RCS: @(#) $Id: regc_locale.c,v 1.4.4.1 1999/11/02 02:09:48 hobbs Exp $
  */
 
 /* ASCII character-name table */
@@ -634,7 +634,7 @@ int cases;			/* all cases? */
 	struct cvec *cv;
 
 	/* crude fake equivalence class for testing */
-	if ((v->cflags&REG_FAKEEC) && c == 'x') {
+	if ((v->cflags&REG_FAKE) && c == 'x') {
 		cv = getcvec(v, 4, 0, 0);
 		addchr(cv, (chr)'x');
 		addchr(cv, (chr)'y');
diff --git a/generic/regcomp.c b/generic/regcomp.c
index f64f1ce..4aba629 100644
--- a/generic/regcomp.c
+++ b/generic/regcomp.c
@@ -105,9 +105,7 @@ static VOID subblock _ANSI_ARGS_((struct vars *, pchr, struct state *, struct st
 static VOID okcolors _ANSI_ARGS_((struct nfa *, struct colormap *));
 static VOID colorchain _ANSI_ARGS_((struct colormap *, struct arc *));
 static VOID uncolorchain _ANSI_ARGS_((struct colormap *, struct arc *));
-#ifdef NOTDEF			/* Avoid compiler warnings. */
 static int singleton _ANSI_ARGS_((struct colormap *, pchr c));
-#endif
 static VOID rainbow _ANSI_ARGS_((struct nfa *, struct colormap *, int, pcolor, struct state *, struct state *));
 static VOID colorcomplement _ANSI_ARGS_((struct nfa *, struct colormap *, int, struct state *, struct state *, struct state *));
 #ifdef REG_DEBUG
@@ -173,9 +171,7 @@ static struct cvec *newcvec _ANSI_ARGS_((int, int, int));
 static struct cvec *clearcvec _ANSI_ARGS_((struct cvec *));
 static VOID addchr _ANSI_ARGS_((struct cvec *, pchr));
 static VOID addrange _ANSI_ARGS_((struct cvec *, pchr, pchr));
-#ifdef NOTDEF			/* Avoid compiler warnings. */
 static VOID addmcce _ANSI_ARGS_((struct cvec *, chr *, chr *));
-#endif
 static int haschr _ANSI_ARGS_((struct cvec *, pchr));
 static struct cvec *getcvec _ANSI_ARGS_((struct vars *, int, int, int));
 static VOID freecvec _ANSI_ARGS_((struct cvec *));
@@ -229,7 +225,6 @@ struct vars {
 	struct state *mccepend;	/* in nfa, end of MCCE prototypes */
 	struct subre *lacons;	/* lookahead-constraint vector */
 	int nlacons;		/* size of lacons */
-	int usedshorter;	/* used short-preferring quantifiers */
 };
 
 /* parsing macros; most know that `v' is the struct vars pointer */
@@ -362,6 +357,7 @@ int flags;
 		CNOERR();
 		v->mcces = allmcces(v, v->mcces);
 		leaders(v, v->mcces);
+		addmcce(v->mcces, (chr *)NULL, (chr *)NULL);	/* dummy */
 	}
 	CNOERR();
 
@@ -386,18 +382,16 @@ int flags;
 		dumpnfa(v->nfa, debug);
 		dumpst(v->tree, debug, 1);
 	}
-	v->usedshorter = 0;
 	optst(v, v->tree);
 	v->ntree = numst(v->tree, 1);
 	markst(v->tree);
 	cleanst(v);
 	if (debug != NULL) {
 		fprintf(debug, "\n\n\n========= TREE FIXED ==========\n");
-		fprintf(debug, "-->\n");
 		dumpst(v->tree, debug, 1);
 	}
 
-	/* build compacted NFAs for tree, lacons, fast search */
+	/* build compacted NFAs for tree and lacons */
 	re->re_info |= nfatree(v, v->tree, debug);
 	CNOERR();
 	assert(v->nlacons == 0 || v->lacons != NULL);
@@ -407,6 +401,10 @@ int flags;
 		nfanode(v, &v->lacons[i], debug);
 	}
 	CNOERR();
+	if (v->tree->flags&SHORTER)
+		NOTE(REG_USHORTEST);
+
+	/* build compacted NFAs for tree, lacons, fast search */
 	if (debug != NULL)
 		fprintf(debug, "\n\n\n========= SEARCH ==========\n");
 	/* can sacrifice main NFA now, so use it as work area */
@@ -431,7 +429,6 @@ int flags;
 	g->lacons = v->lacons;
 	v->lacons = NULL;
 	g->nlacons = v->nlacons;
-	g->usedshorter = v->usedshorter;
 
 	if (flags&REG_DUMP)
 		dump(re, stdout);
@@ -507,7 +504,7 @@ int err;
 }
 
 /*
- - makesearch - turn an NFA into a fast-scan NFA (implicit prepend of .*?)
+ - makesearch - turn an NFA into a search NFA (implicit prepend of .*?)
  * NFA must have been optimize()d already.
  ^ static VOID makesearch(struct vars *, struct nfa *);
  */
@@ -1653,6 +1650,10 @@ struct state *rp;
 	for (i = 0; i < cv->nmcces; i++) {
 		p = cv->mcces[i];
 		assert(singleton(v->cm, *p));
+		if (!singleton(v->cm, *p)) {
+			ERR(REG_ASSERT);
+			return;
+		}
 		ch = *p++;
 		co = GETCOLOR(v->cm, ch);
 		a = findarc(lp, PLAIN, co);
@@ -1835,10 +1836,6 @@ struct subre *t;
 	if (t == NULL)
 		return;
 
-	/* preference cleanup and analysis */
-	if (t->flags&SHORTER)
-		v->usedshorter = 1;
-
 	/* recurse through children */
 	if (t->left != NULL)
 		optst(v, t->left);
@@ -1937,7 +1934,7 @@ FILE *f;			/* for debug output */
 {
 	struct nfa *nfa;
 	long ret = 0;
- 	char idbuf[50];
+	char idbuf[50];
 
 	assert(t->begin != NULL);
 
@@ -2066,9 +2063,8 @@ FILE *f;
 								GUTSMAGIC);
 
 	fprintf(f, "\n\n\n========= DUMP ==========\n");
-	fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d, usedshort %d\n", 
-		re->re_nsub, re->re_info, re->re_csize, g->ntree,
-		g->usedshorter);
+	fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n", 
+		re->re_nsub, re->re_info, re->re_csize, g->ntree);
 
 	dumpcolors(&g->cmap, f);
 	if (!NULLCNFA(g->search)) {
diff --git a/generic/regcustom.h b/generic/regcustom.h
index 8770ac7..9f505de 100644
--- a/generic/regcustom.h
+++ b/generic/regcustom.h
@@ -26,11 +26,10 @@
  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
-/* headers (which also pick up the standard ones, or equivalents) */
+/* headers if any */
 #include "tclInt.h"
 
-/* overrides for regguts.h definitions */
-/* function-pointer declarations */
+/* overrides for regguts.h definitions, if any */
 #define	FUNCPTR(name, args)	(*name) _ANSI_ARGS_(args)
 #define	MALLOC(n)		ckalloc(n)
 #define	FREE(p)			ckfree(VS(p))
@@ -62,6 +61,12 @@
 #ifdef __REG_CONST
 #undef __REG_CONST
 #endif
+#ifdef __REG_NOFRONT
+#undef __REG_NOFRONT
+#endif
+#ifdef __REG_NOCHAR
+#undef __REG_NOCHAR
+#endif
 /* interface types */
 #define	__REG_WIDE_T	Tcl_UniChar
 #define	__REG_REGOFF_T	long	/* not really right, but good enough... */
@@ -70,12 +75,8 @@
 /* names and declarations */
 #define	__REG_WIDE_COMPILE	TclReComp
 #define	__REG_WIDE_EXEC		TclReExec
-#ifndef __REG_NOFRONT
 #define	__REG_NOFRONT		/* don't want regcomp() and regexec() */
-#endif
-#ifndef __REG_NOCHAR
 #define	__REG_NOCHAR		/* or the char versions */
-#endif
 #define	regfree		TclReFree
 #define	regerror	TclReError
 /* --- end --- */
@@ -105,7 +106,7 @@ typedef int celt;		/* type to hold chr, MCCE number, or NOCELT */
 #define	exec		TclReExec
 
 /* enable/disable debugging code (by whether REG_DEBUG is defined or not) */
-#ifdef notdef
+#if 0		/* no debug unless requested by makefile */
 #define	REG_DEBUG	/* */
 #endif
 
diff --git a/generic/regerrs.h b/generic/regerrs.h
index 34c1e68..a3d98b6 100644
--- a/generic/regerrs.h
+++ b/generic/regerrs.h
@@ -1,6 +1,6 @@
 { REG_OKAY,	"REG_OKAY",	"no errors detected" },
 { REG_NOMATCH,	"REG_NOMATCH",	"failed to match" },
-{ REG_BADPAT,	"REG_BADPAT",	"invalid regexp (reg version 0.4)" },
+{ REG_BADPAT,	"REG_BADPAT",	"invalid regexp (reg version 0.8)" },
 { REG_ECOLLATE,	"REG_ECOLLATE",	"invalid collating element" },
 { REG_ECTYPE,	"REG_ECTYPE",	"invalid character class" },
 { REG_EESCAPE,	"REG_EESCAPE",	"invalid escape \\ sequence" },
diff --git a/generic/regex.h b/generic/regex.h
index 0016005..8289a50 100644
--- a/generic/regex.h
+++ b/generic/regex.h
@@ -101,6 +101,12 @@ extern "C" {
 #ifdef __REG_CONST
 #undef __REG_CONST
 #endif
+#ifdef __REG_NOFRONT
+#undef __REG_NOFRONT
+#endif
+#ifdef __REG_NOCHAR
+#undef __REG_NOCHAR
+#endif
 /* interface types */
 #define	__REG_WIDE_T	Tcl_UniChar
 #define	__REG_REGOFF_T	long	/* not really right, but good enough... */
@@ -109,12 +115,8 @@ extern "C" {
 /* names and declarations */
 #define	__REG_WIDE_COMPILE	TclReComp
 #define	__REG_WIDE_EXEC		TclReExec
-#ifndef __REG_NOFRONT
 #define	__REG_NOFRONT		/* don't want regcomp() and regexec() */
-#endif
-#ifndef __REG_NOCHAR
 #define	__REG_NOCHAR		/* or the char versions */
-#endif
 #define	regfree		TclReFree
 #define	regerror	TclReError
 /* --- end --- */
@@ -163,7 +165,7 @@ typedef void re_void;
 typedef struct {
 	int re_magic;		/* magic number */
 	size_t re_nsub;		/* number of subexpressions */
-	int re_info;		/* information about RE */
+	long re_info;		/* information about RE */
 #		define	REG_UBACKREF		000001
 #		define	REG_ULOOKAHEAD		000002
 #		define	REG_UBOUNDS		000004
@@ -177,6 +179,7 @@ typedef struct {
 #		define	REG_ULOCALE		002000
 #		define	REG_UEMPTYMATCH		004000
 #		define	REG_UIMPOSSIBLE		010000
+#		define	REG_USHORTEST		020000
 	int re_csize;		/* sizeof(character) */
 	char *re_endp;		/* backward compatibility kludge */
 	/* the rest is opaque pointers to hidden innards */
@@ -225,7 +228,7 @@ typedef struct {
 #define	REG_EXPECT	001000	/* report details on partial/limited matches */
 #define	REG_BOSONLY	002000	/* temporary kludge for BOS-only matches */
 #define	REG_DUMP	004000	/* none of your business :-) */
-#define	REG_FAKEEC	010000	/* none of your business :-) */
+#define	REG_FAKE	010000	/* none of your business :-) */
 #define	REG_PROGRESS	020000	/* none of your business :-) */
 
 
diff --git a/generic/regexec.c b/generic/regexec.c
index 3d216db..7b61a45 100644
--- a/generic/regexec.c
+++ b/generic/regexec.c
@@ -33,29 +33,6 @@
 
 
 
-/* internal variables, bundled for easy passing around */
-struct vars {
-	regex_t *re;
-	struct guts *g;
-	int eflags;		/* copies of arguments */
-	size_t nmatch;
-	regmatch_t *pmatch;
-	rm_detail_t *details;
-	chr *start;		/* start of string */
-	chr *stop;		/* just past end of string */
-	int err;		/* error code if any (0 none) */
-	regoff_t *mem;		/* memory vector for backtracking */
-};
-#define	VISERR(vv)	((vv)->err != 0)	/* have we seen an error yet? */
-#define	ISERR()	VISERR(v)
-#define	VERR(vv,e)	(((vv)->err) ? (vv)->err : ((vv)->err = (e)))
-#define	ERR(e)	VERR(v, e)		/* record an error */
-#define	NOERR()	{if (ISERR()) return;}	/* if error seen, return */
-#define	OFF(p)	((p) - v->start)
-#define	LOFF(p)	((long)OFF(p))
-
-
-
 /* lazy-DFA representation */
 struct arcp {			/* "pointer" to an outarc */
 	struct sset *ss;
@@ -111,9 +88,34 @@ struct smalldfa {
 	struct sset *outsarea[FEWSTATES*2 * FEWCOLORS];
 	struct arcp incarea[FEWSTATES*2 * FEWCOLORS];
 };
+#define	DOMALLOC	((struct smalldfa *)NULL)	/* force malloc */
 
 
 
+/* internal variables, bundled for easy passing around */
+struct vars {
+	regex_t *re;
+	struct guts *g;
+	int eflags;		/* copies of arguments */
+	size_t nmatch;
+	regmatch_t *pmatch;
+	rm_detail_t *details;
+	chr *start;		/* start of string */
+	chr *stop;		/* just past end of string */
+	int err;		/* error code if any (0 none) */
+	regoff_t *mem;		/* memory vector for backtracking */
+	struct smalldfa dfa1;
+	struct smalldfa dfa2;
+};
+#define	VISERR(vv)	((vv)->err != 0)	/* have we seen an error yet? */
+#define	ISERR()	VISERR(v)
+#define	VERR(vv,e)	(((vv)->err) ? (vv)->err : ((vv)->err = (e)))
+#define	ERR(e)	VERR(v, e)		/* record an error */
+#define	NOERR()	{if (ISERR()) return v->err;}	/* if error seen, return it */
+#define	OFF(p)	((p) - v->start)
+#define	LOFF(p)	((long)OFF(p))
+
+
 
 /*
  * forward declarations
@@ -196,8 +198,8 @@ int flags;
 	if (v->g->cflags&REG_NOSUB)
 		nmatch = 0;		/* override client */
 	v->nmatch = nmatch;
-	if (backref && v->nmatch < v->g->nsub + 1) {
-		/* need work area bigger than what user gave us */
+	if (backref) {
+		/* need work area */
 		if (v->g->nsub + 1 <= LOCALMAT)
 			v->pmatch = mat;
 		else
@@ -260,10 +262,8 @@ struct vars *v;
 struct cnfa *cnfa;
 struct colormap *cm;
 {
-	struct smalldfa da;
-	struct dfa *d = newdfa(v, cnfa, cm, &da);
-	struct smalldfa sa;
-	struct dfa *s = newdfa(v, &v->g->search, cm, &sa);
+	struct dfa *s;
+	struct dfa *d;
 	chr *begin;
 	chr *end;
 	chr *cold;
@@ -272,19 +272,15 @@ struct colormap *cm;
 	int hitend;
 	int shorter = (v->g->tree->flags&SHORTER) ? 1 : 0;
 
-	if (ISERR()) {		/* should be newdfa() failure */
-		if (d != NULL)
-			freedfa(d);
-		if (s != NULL)
-			freedfa(s);
-		return v->err;
-	}
-
 	/* first, a shot with the search RE */
+	s = newdfa(v, &v->g->search, cm, &v->dfa1);
+	assert(!(ISERR() && s != NULL));
+	NOERR();
 	MDEBUG(("\nsearch at %ld\n", LOFF(v->start)));
 	cold = NULL;
 	close = shortest(v, s, v->start, v->start, v->stop, &cold, (int *)NULL);
 	freedfa(s);
+	NOERR();
 	if (v->g->cflags&REG_EXPECT) {
 		assert(v->details != NULL);
 		if (cold != NULL)
@@ -293,22 +289,19 @@ struct colormap *cm;
 			v->details->rm_extend.rm_so = OFF(v->stop);
 		v->details->rm_extend.rm_eo = OFF(v->stop);	/* unknown */
 	}
-	if (close == NULL) {		/* not found */
-		freedfa(d);
-		if (ISERR())
-			return v->err;
+	if (close == NULL)		/* not found */
 		return REG_NOMATCH;
-	}
-	if (v->nmatch == 0) {		/* found, don't need exact location */
-		freedfa(d);
+	if (v->nmatch == 0)		/* found, don't need exact location */
 		return REG_OKAY;
-	}
 
-	/* find starting point */
+	/* find starting point and match */
 	assert(cold != NULL);
 	open = cold;
 	cold = NULL;
 	MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close)));
+	d = newdfa(v, cnfa, cm, &v->dfa1);
+	assert(!(ISERR() && d != NULL));
+	NOERR();
 	for (begin = open; begin <= close; begin++) {
 		MDEBUG(("\nfind trying at %ld\n", LOFF(begin)));
 		if (shorter)
@@ -316,6 +309,7 @@ struct colormap *cm;
 							(chr **)NULL, &hitend);
 		else
 			end = longest(v, d, begin, v->stop, &hitend);
+		NOERR();
 		if (hitend && cold == NULL)
 			cold = begin;
 		if (end != NULL)
@@ -335,13 +329,12 @@ struct colormap *cm;
 			v->details->rm_extend.rm_so = OFF(v->stop);
 		v->details->rm_extend.rm_eo = OFF(v->stop);	/* unknown */
 	}
-	if (v->nmatch > 1) {
-		zapsubs(v->pmatch, v->nmatch);
-		return dissect(v, v->g->tree, begin, end);
-	}
-	if (ISERR())
-		return v->err;
-	return REG_OKAY;
+	if (v->nmatch == 1)		/* no need for submatches */
+		return REG_OKAY;
+
+	/* submatches */
+	zapsubs(v->pmatch, v->nmatch);
+	return dissect(v, v->g->tree, begin, end);
 }
 
 /*
@@ -354,17 +347,17 @@ struct vars *v;
 struct cnfa *cnfa;
 struct colormap *cm;
 {
-	struct smalldfa da;
-	struct dfa *d = newdfa(v, cnfa, cm, &da);
-	struct smalldfa sa;
-	struct dfa *s = newdfa(v, &v->g->search, cm, &sa);
+	struct dfa *s;
+	struct dfa *d;
 	chr *cold;
 	int ret;
 
-	if (d == NULL)
-		return v->err;
-	if (s == NULL) {
-		freedfa(d);
+	s = newdfa(v, &v->g->search, cm, &v->dfa1);
+	NOERR();
+	d = newdfa(v, cnfa, cm, &v->dfa2);
+	if (ISERR()) {
+		assert(d == NULL);
+		freedfa(s);
 		return v->err;
 	}
 
@@ -372,8 +365,7 @@ struct colormap *cm;
 
 	freedfa(d);
 	freedfa(s);
-	if (ISERR())
-		return v->err;
+	NOERR();
 	if (v->g->cflags&REG_EXPECT) {
 		assert(v->details != NULL);
 		if (cold != NULL)
@@ -589,9 +581,7 @@ struct subre *t;
 chr *begin;			/* beginning of relevant substring */
 chr *end;			/* end of same */
 {
-	struct smalldfa da;
 	struct dfa *d;
-	struct smalldfa d2a;
 	struct dfa *d2;
 	chr *mid;
 	int i;
@@ -602,11 +592,11 @@ chr *end;			/* end of same */
 	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, &da);
-	if (ISERR())
-		return v->err;
-	d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &d2a);
+	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;
 	}
@@ -670,7 +660,6 @@ struct subre *t;
 chr *begin;			/* beginning of relevant substring */
 chr *end;			/* end of same */
 {
-	struct smalldfa da;
 	struct dfa *d;
 	int i;
 
@@ -680,7 +669,7 @@ chr *end;			/* end of same */
 	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, &da);
+		d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
 		if (ISERR())
 			return v->err;
 		if (longest(v, d, begin, end, (int *)NULL) == end) {
@@ -755,9 +744,7 @@ struct subre *t;
 chr *begin;			/* beginning of relevant substring */
 chr *end;			/* end of same */
 {
-	struct smalldfa da;
 	struct dfa *d;
-	struct smalldfa d2a;
 	struct dfa *d2;
 	chr *mid;
 	int er;
@@ -769,10 +756,10 @@ chr *end;			/* end of same */
 	if (t->left->flags&SHORTER)		/* reverse scan */
 		return crevdissect(v, t, begin, end);
 
-	d = newdfa(v, &t->left->cnfa, &v->g->cmap, &da);
+	d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
 	if (ISERR())
 		return v->err;
-	d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &d2a);
+	d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
 	if (ISERR()) {
 		freedfa(d);
 		return v->err;
@@ -839,7 +826,7 @@ chr *end;			/* end of same */
 }
 
 /*
- - crevdissect - determine shortest-first subexpression matches
+ - 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 *);
@@ -851,9 +838,7 @@ struct subre *t;
 chr *begin;			/* beginning of relevant substring */
 chr *end;			/* end of same */
 {
-	struct smalldfa da;
 	struct dfa *d;
-	struct smalldfa d2a;
 	struct dfa *d2;
 	chr *mid;
 	int er;
@@ -864,10 +849,10 @@ chr *end;			/* end of same */
 	assert(t->left->flags&SHORTER);
 
 	/* concatenation -- need to split the substring between parts */
-	d = newdfa(v, &t->left->cnfa, &v->g->cmap, &da);
+	d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
 	if (ISERR())
 		return v->err;
-	d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &d2a);
+	d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
 	if (ISERR()) {
 		freedfa(d);
 		return v->err;
@@ -1011,7 +996,6 @@ struct subre *t;
 chr *begin;			/* beginning of relevant substring */
 chr *end;			/* end of same */
 {
-	struct smalldfa da;
 	struct dfa *d;
 	int er;
 #	define	UNTRIED	0	/* not yet tried at all */
@@ -1028,7 +1012,7 @@ chr *end;			/* end of same */
 	assert(t->left != NULL);
 
 	if (v->mem[t->retry] == UNTRIED) {
-		d = newdfa(v, &t->left->cnfa, &v->g->cmap, &da);
+		d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
 		if (ISERR())
 			return v->err;
 		if (longest(v, d, begin, end, (int *)NULL) != end) {
diff --git a/generic/regguts.h b/generic/regguts.h
index 45c47f6..36e5092 100644
--- a/generic/regguts.h
+++ b/generic/regguts.h
@@ -1,5 +1,5 @@
 /*
- * Internal interface definitions, etc., for the regex package
+ * Internal interface definitions, etc., for the reg package
  *
  * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
  * 
@@ -77,6 +77,11 @@
 #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
@@ -410,5 +415,4 @@ struct guts {
 	int FUNCPTR(compare, (CONST chr *, CONST chr *, size_t));
 	struct subre *lacons;	/* lookahead-constraint vector */
 	int nlacons;		/* size of lacons */
-	int usedshorter;	/* used non-greedy quantifiers? */
 };
diff --git a/generic/tclRegexp.c b/generic/tclRegexp.c
index 6736465..787cdd9 100644
--- a/generic/tclRegexp.c
+++ b/generic/tclRegexp.c
@@ -10,7 +10,7 @@
  * See the file "license.terms" for information on usage and redistribution
  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  *
- * RCS: @(#) $Id: tclRegexp.c,v 1.9 1999/06/17 19:32:15 stanton Exp $
+ * RCS: @(#) $Id: tclRegexp.c,v 1.9.4.1 1999/11/02 02:09:49 hobbs Exp $
  */
 
 #include "tclInt.h"
@@ -642,7 +642,8 @@ TclRegAbout(interp, re)
 	{REG_ULOCALE,		"REG_ULOCALE"},
 	{REG_UEMPTYMATCH,	"REG_UEMPTYMATCH"},
 	{REG_UIMPOSSIBLE,	"REG_UIMPOSSIBLE"},
-	 {0,			""}
+	{REG_USHORTEST,		"REG_USHORTEST"},
+	{0,			""}
     };
     struct infoname *inf;
     int n;
diff --git a/generic/tclTest.c b/generic/tclTest.c
index c9b2c2b..5fa12c6 100644
--- a/generic/tclTest.c
+++ b/generic/tclTest.c
@@ -13,7 +13,7 @@
  * See the file "license.terms" for information on usage and redistribution
  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  *
- * RCS: @(#) $Id: tclTest.c,v 1.16 1999/08/13 17:53:19 redman Exp $
+ * RCS: @(#) $Id: tclTest.c,v 1.16.2.1 1999/11/02 02:09:50 hobbs Exp $
  */
 
 #define TCL_TEST
@@ -2788,7 +2788,7 @@ TestregexpXflags(string, length, cflagsPtr, eflagsPtr)
 		break;
 	    }
 	    case '+': {
-		cflags |= REG_FAKEEC;
+		cflags |= REG_FAKE;
 		break;
 	    }
 	    case ',': {
@@ -2815,7 +2815,7 @@ TestregexpXflags(string, length, cflagsPtr, eflagsPtr)
 		eflags |= REG_NOTEOL;
 		break;
 	    }
-	    case '?': {
+	    case 't': {
 		cflags |= REG_EXPECT;
 		break;
 	    }