summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordkf <donal.k.fellows@manchester.ac.uk>2010-02-01 11:19:28 (GMT)
committerdkf <donal.k.fellows@manchester.ac.uk>2010-02-01 11:19:28 (GMT)
commit8dc76eca1beb59a4b83d3a8465e445a23ce9b4fb (patch)
treebcbbb1be2539993ae7b60ac93724fef8f6851b67
parent0ef0708322e51a6c0a8c283ec573d5f74cf03d58 (diff)
downloadtcl-8dc76eca1beb59a4b83d3a8465e445a23ce9b4fb.zip
tcl-8dc76eca1beb59a4b83d3a8465e445a23ce9b4fb.tar.gz
tcl-8dc76eca1beb59a4b83d3a8465e445a23ce9b4fb.tar.bz2
[Bug 2942697]: Rework the RE engine so that certain pathological patterns are
matched much more rapidly. Many thanks to Tom Lane for dianosing this issue and providing an initial patch.
-rw-r--r--ChangeLog10
-rw-r--r--generic/regexec.c66
2 files changed, 43 insertions, 33 deletions
diff --git a/ChangeLog b/ChangeLog
index 981328b..9249bc2 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,7 +1,15 @@
+2010-02-01 Donal K. Fellows <dkf@users.sf.net>
+
+ * generic/regexec.c (ccondissect, crevdissect): [Bug 2942697]: Rework
+ these functions so that certain pathological patterns are matched much
+ more rapidly. Many thanks to Tom Lane for dianosing this issue and
+ providing an initial patch.
+
2009-11-16 Alexandre Ferrieux <ferrieux@users.sourceforge.net>
* generic/tclEncoding.c: (Backport) Fix [Bug 2891556] and improve
- * tests/econding.test: test to detect similar manifestations in the future.
+ * tests/econding.test: test to detect similar manifestations in the
+ future.
2009-11-12 Andreas Kupries <andreask@activestate.com>
diff --git a/generic/regexec.c b/generic/regexec.c
index 3eb73d1..be459d3 100644
--- a/generic/regexec.c
+++ b/generic/regexec.c
@@ -784,16 +784,23 @@ chr *end; /* end of same */
/* iterate until satisfaction or failure */
for (;;) {
/* try this midpoint on for size */
- er = cdissect(v, t->left, begin, mid);
- if (er == REG_OKAY &&
- longest(v, d2, mid, end, (int *)NULL) == end &&
- (er = cdissect(v, t->right, mid, end)) ==
- REG_OKAY)
- break; /* NOTE BREAK OUT */
- if (er != REG_OKAY && er != REG_NOMATCH) {
- freedfa(d);
- freedfa(d2);
- return er;
+ if (longest(v, d2, mid, end, NULL) == end) {
+ 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);
+ return er;
+ }
}
/* that midpoint didn't work, find a new one */
@@ -817,12 +824,6 @@ chr *end; /* end of same */
zapmem(v, t->left);
zapmem(v, t->right);
}
-
- /* satisfaction */
- MDEBUG(("successful\n"));
- freedfa(d);
- freedfa(d2);
- return REG_OKAY;
}
/*
@@ -877,16 +878,23 @@ chr *end; /* end of same */
/* iterate until satisfaction or failure */
for (;;) {
/* try this midpoint on for size */
- er = cdissect(v, t->left, begin, mid);
- if (er == REG_OKAY &&
- longest(v, d2, mid, end, (int *)NULL) == end &&
- (er = cdissect(v, t->right, mid, end)) ==
- REG_OKAY)
- break; /* NOTE BREAK OUT */
- if (er != REG_OKAY && er != REG_NOMATCH) {
- freedfa(d);
- freedfa(d2);
- return er;
+ if (longest(v, d2, mid, end, NULL) == end) {
+ 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);
+ return er;
+ }
}
/* that midpoint didn't work, find a new one */
@@ -910,12 +918,6 @@ chr *end; /* end of same */
zapmem(v, t->left);
zapmem(v, t->right);
}
-
- /* satisfaction */
- MDEBUG(("successful\n"));
- freedfa(d);
- freedfa(d2);
- return REG_OKAY;
}
/*