* generic/tclUtil.c (TclReToGlob): add extra check for multiple

	inner *s that leads to poor recursive glob matching, defer to
	original RE instead.  tclbench RE var backtrack.

2 files changed, 20 insertions, 2 deletions

diff --git a/ChangeLog b/ChangeLog
index d7c7573..76cb2fb 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2010-12-03  Jeff Hobbs  <jeffh@ActiveState.com>
+
+	* generic/tclUtil.c (TclReToGlob): add extra check for multiple
+	inner *s that leads to poor recursive glob matching, defer to
+	original RE instead.  tclbench RE var backtrack.
+
 2010-12-01  Kevin B. Kenny  <kennykb@acm.org>
 
 	* generic/tclStrToD.c (SetPrecisionLimits, TclDoubleDigits):
diff --git a/generic/tclUtil.c b/generic/tclUtil.c
index 2a23fd2..ee17166 100644
--- a/generic/tclUtil.c
+++ b/generic/tclUtil.c
@@ -11,7 +11,7 @@
  * See the file "license.terms" for information on usage and redistribution of
  * this file, and for a DISCLAIMER OF ALL WARRANTIES.
  *
- * RCS: @(#) $Id: tclUtil.c,v 1.97.2.8 2010/11/30 20:59:28 andreas_kupries Exp $
+ * RCS: @(#) $Id: tclUtil.c,v 1.97.2.9 2010/12/03 22:27:44 hobbs Exp $
  */
 
 #include "tclInt.h"
@@ -3326,7 +3326,7 @@ TclReToGlob(
     Tcl_DString *dsPtr,
     int *exactPtr)
 {
-    int anchorLeft, anchorRight, lastIsStar;
+    int anchorLeft, anchorRight, lastIsStar, numStars;
     char *dsStr, *dsStrStart, *msg;
     const char *p, *strEnd;
 
@@ -3385,6 +3385,7 @@ TclReToGlob(
     p = reStr;
     anchorRight = 0;
     lastIsStar = 0;
+    numStars = 0;
 
     if (*p == '^') {
 	anchorLeft = 1;
@@ -3448,6 +3449,7 @@ TclReToGlob(
 		    if (!lastIsStar) {
 			*dsStr++ = '*';
 			lastIsStar = 1;
+			numStars++;
 		    }
 		    continue;
 		} else if (p[1] == '+') {
@@ -3455,6 +3457,7 @@ TclReToGlob(
 		    *dsStr++ = '?';
 		    *dsStr++ = '*';
 		    lastIsStar = 1;
+		    numStars++;
 		    continue;
 		}
 	    }
@@ -3478,6 +3481,15 @@ TclReToGlob(
 	}
 	lastIsStar = 0;
     }
+    if (numStars > 1) {
+	/*
+	 * Heuristic: if >1 non-anchoring *, the risk is large that glob
+	 * matching is slower than the RE engine, so report invalid.
+	 */
+	msg = "excessive recursive glob backtrack potential";
+	goto invalidGlob;
+    }
+
     if (!anchorRight && !lastIsStar) {
 	*dsStr++ = '*';
     }