summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordkf <donal.k.fellows@manchester.ac.uk>2008-07-01 14:29:11 (GMT)
committerdkf <donal.k.fellows@manchester.ac.uk>2008-07-01 14:29:11 (GMT)
commit349fc26e6c278e0d1de00458c76a113ae8425f88 (patch)
tree155be98abe3f09f2c334dd275fd725cdaf10506d
parentf35ac41c5ad6fb2efa6d0833f0299549c69a6329 (diff)
downloadtcl-349fc26e6c278e0d1de00458c76a113ae8425f88.zip
tcl-349fc26e6c278e0d1de00458c76a113ae8425f88.tar.gz
tcl-349fc26e6c278e0d1de00458c76a113ae8425f88.tar.bz2
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]
-rw-r--r--ChangeLog7
-rw-r--r--generic/regc_nfa.c17
-rw-r--r--generic/regcomp.c2
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 *);