From 8dc76eca1beb59a4b83d3a8465e445a23ce9b4fb Mon Sep 17 00:00:00 2001 From: dkf Date: Mon, 1 Feb 2010 11:19:28 +0000 Subject: [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. --- ChangeLog | 10 ++++++++- generic/regexec.c | 66 ++++++++++++++++++++++++++++--------------------------- 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 + + * 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 * 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 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; } /* -- cgit v0.12