diff options
author | dkf <dkf@noemail.net> | 2010-02-01 11:12:00 (GMT) |
---|---|---|
committer | dkf <dkf@noemail.net> | 2010-02-01 11:12:00 (GMT) |
commit | 6a0a7cf15ca7459471bcce1df5524ff050a2b24b (patch) | |
tree | 39bc26fb3acf944bf541192fef351f5c0a327c73 /generic/regexec.c | |
parent | c032dde640bf4a88ea104874ef18df4a8def1e1c (diff) | |
download | tcl-6a0a7cf15ca7459471bcce1df5524ff050a2b24b.zip tcl-6a0a7cf15ca7459471bcce1df5524ff050a2b24b.tar.gz tcl-6a0a7cf15ca7459471bcce1df5524ff050a2b24b.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.
FossilOrigin-Name: 05ea9ca3eba3919fe5584069545c13c133f5cfd6
Diffstat (limited to 'generic/regexec.c')
-rw-r--r-- | generic/regexec.c | 91 |
1 files changed, 41 insertions, 50 deletions
diff --git a/generic/regexec.c b/generic/regexec.c index d39685c..c902209 100644 --- a/generic/regexec.c +++ b/generic/regexec.c @@ -624,27 +624,21 @@ dissect( case '=': /* terminal node */ assert(t->left == NULL && t->right == NULL); return REG_OKAY; /* no action, parent did the work */ - break; case '|': /* alternation */ assert(t->left != NULL); return altdissect(v, t, begin, end); - break; case 'b': /* back ref -- shouldn't be calling us! */ return REG_ASSERT; - break; case '.': /* concatenation */ assert(t->left != NULL && t->right != NULL); return condissect(v, t, begin, end); - break; case '(': /* capturing */ assert(t->left != NULL && t->right == NULL); assert(t->subno > 0); subset(v, t, begin, end); return dissect(v, t->left, begin, end); - break; default: return REG_ASSERT; - break; } } @@ -802,19 +796,15 @@ cdissect( case '=': /* terminal node */ assert(t->left == NULL && t->right == NULL); return REG_OKAY; /* no action, parent did the work */ - break; case '|': /* alternation */ assert(t->left != NULL); return caltdissect(v, t, begin, end); - break; case 'b': /* back ref -- shouldn't be calling us! */ assert(t->left == NULL && t->right == NULL); return cbrdissect(v, t, begin, end); - break; case '.': /* concatenation */ assert(t->left != NULL && t->right != NULL); return ccondissect(v, t, begin, end); - break; case '(': /* capturing */ assert(t->left != NULL && t->right == NULL); assert(t->subno > 0); @@ -823,10 +813,8 @@ cdissect( subset(v, t, begin, end); } return er; - break; default: return REG_ASSERT; - break; } } @@ -843,8 +831,7 @@ ccondissect( chr *begin, /* beginning of relevant substring */ chr *end) /* end of same */ { - struct dfa *d; - struct dfa *d2; + struct dfa *d, *d2; chr *mid; int er; @@ -894,15 +881,26 @@ ccondissect( * Try this midpoint on for size. */ - er = cdissect(v, t->left, begin, mid); - if ((er == REG_OKAY) && (longest(v, d2, mid, end, 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; + } } /* @@ -935,15 +933,6 @@ ccondissect( zapmem(v, t->left); zapmem(v, t->right); } - - /* - * Satisfaction. - */ - - MDEBUG(("successful\n")); - freedfa(d); - freedfa(d2); - return REG_OKAY; } /* @@ -1011,15 +1000,26 @@ crevdissect( * Try this midpoint on for size. */ - er = cdissect(v, t->left, begin, mid); - if ((er == REG_OKAY) && (longest(v, d2, mid, end, 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; + } } /* @@ -1052,15 +1052,6 @@ crevdissect( zapmem(v, t->left); zapmem(v, t->right); } - - /* - * Satisfaction. - */ - - MDEBUG(("successful\n")); - freedfa(d); - freedfa(d2); - return REG_OKAY; } /* |