diff options
| author | dkf <donal.k.fellows@manchester.ac.uk> | 2010-02-01 11:19:28 (GMT) |
|---|---|---|
| committer | dkf <donal.k.fellows@manchester.ac.uk> | 2010-02-01 11:19:28 (GMT) |
| commit | 8dc76eca1beb59a4b83d3a8465e445a23ce9b4fb (patch) | |
| tree | bcbbb1be2539993ae7b60ac93724fef8f6851b67 | |
| parent | 0ef0708322e51a6c0a8c283ec573d5f74cf03d58 (diff) | |
| download | tcl-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-- | ChangeLog | 10 | ||||
| -rw-r--r-- | generic/regexec.c | 66 |
2 files changed, 43 insertions, 33 deletions
@@ -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; } /* |