Add focussed stack limiting to the RE compiler. Tuning might not yet be right

but it passes everything normally checked in the test suite. [Bug 1905562]

3 files changed, 21 insertions, 5 deletions

diff --git a/ChangeLog b/ChangeLog
index 666974e..3767add 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,4 +1,9 @@
-2008-07-01  Donal K. Fellows  <donal.k.fellows@man.ac.uk>
+2008-07-01  Donal K. Fellows  <dkf@users.sf.net>
+
+	* generic/regc_nfa.c (duptraverse): Impose a maximum stack depth on
+	the single most recursive part of the RE engine. The actual maximum
+	may need tuning, but that needs a system with a small stack to carry
+	out. [Bug 1905562]
 
 	* tests/string.test: Eliminate non-ASCII characters from the actual
 	test script. [Bug 2006884]
diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c
index d8cbd82..4fb3ea6 100644
--- a/generic/regc_nfa.c
+++ b/generic/regc_nfa.c
@@ -725,7 +725,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;
@@ -740,7 +740,8 @@ 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;
 
@@ -754,8 +755,18 @@ duptraverse(
 	return;
     }
 
+    /*
+     * Arbitrary depth limit. Needs tuning, but this value is sufficient to
+     * make all normal tests (not reg-33.14) pass.
+     */
+#define DUPTRAVERSE_MAX_DEPTH 500
+
+    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;
 	}
diff --git a/generic/regcomp.c b/generic/regcomp.c
index afe1b1b..8ff77ad 100644
--- a/generic/regcomp.c
+++ b/generic/regcomp.c
@@ -131,7 +131,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 *);