diff options
author | Bram Moolenaar <Bram@vim.org> | 2014-11-05 14:27:36 +0100 |
---|---|---|
committer | Bram Moolenaar <Bram@vim.org> | 2014-11-05 14:27:36 +0100 |
commit | fda3729a064d6466cec6ac83dd1bfcc437ea4cc9 (patch) | |
tree | 7642145192f29ec2050ac8e9cc890ddc353615af /src/regexp.c | |
parent | 4f7e821f26019c14f4470deb0867c919548d5cd5 (diff) |
updated for version 7.4.497v7.4.497
Problem: With some regexp patterns the NFA engine uses many states and
becomes very slow. To the user it looks like Vim freezes.
Solution: When the number of states reaches a limit fall back to the old
engine. (Christian Brabandt)
Diffstat (limited to 'src/regexp.c')
-rw-r--r-- | src/regexp.c | 138 |
1 files changed, 113 insertions, 25 deletions
diff --git a/src/regexp.c b/src/regexp.c index f19e139710..6e5655a995 100644 --- a/src/regexp.c +++ b/src/regexp.c @@ -8011,13 +8011,10 @@ static regengine_T bt_regengine = bt_regcomp, bt_regfree, bt_regexec_nl, - bt_regexec_multi -#ifdef DEBUG - ,(char_u *)"" -#endif + bt_regexec_multi, + (char_u *)"" }; - #include "regexp_nfa.c" static regengine_T nfa_regengine = @@ -8025,18 +8022,14 @@ static regengine_T nfa_regengine = nfa_regcomp, nfa_regfree, nfa_regexec_nl, - nfa_regexec_multi -#ifdef DEBUG - ,(char_u *)"" -#endif + nfa_regexec_multi, + (char_u *)"" }; /* Which regexp engine to use? Needed for vim_regcomp(). * Must match with 'regexpengine'. */ static int regexp_engine = 0; -#define AUTOMATIC_ENGINE 0 -#define BACKTRACKING_ENGINE 1 -#define NFA_ENGINE 2 + #ifdef DEBUG static char_u regname[][30] = { "AUTOMATIC Regexp Engine", @@ -8083,10 +8076,8 @@ vim_regcomp(expr_arg, re_flags) regexp_engine = AUTOMATIC_ENGINE; } } -#ifdef DEBUG bt_regengine.expr = expr; nfa_regengine.expr = expr; -#endif /* * First try the NFA engine, unless backtracking was requested. @@ -8096,7 +8087,8 @@ vim_regcomp(expr_arg, re_flags) else prog = bt_regengine.regcomp(expr, re_flags); - if (prog == NULL) /* error compiling regexp with initial engine */ + /* Check for error compiling regexp with initial engine. */ + if (prog == NULL) { #ifdef BT_REGEXP_DEBUG_LOG if (regexp_engine != BACKTRACKING_ENGINE) /* debugging log for NFA */ @@ -8114,13 +8106,27 @@ vim_regcomp(expr_arg, re_flags) } #endif /* - * If the NFA engine failed, the backtracking engine won't work either. + * If the NFA engine failed, try the backtracking engine. + * Disabled for now, both engines fail on the same patterns. + * Re-enable when regcomp() fails when the pattern would work better + * with the other engine. * if (regexp_engine == AUTOMATIC_ENGINE) + { prog = bt_regengine.regcomp(expr, re_flags); + regexp_engine == BACKTRACKING_ENGINE; + } */ } + if (prog != NULL) + { + /* Store the info needed to call regcomp() again when the engine turns + * out to be very slow when executing it. */ + prog->re_engine = regexp_engine; + prog->re_flags = re_flags; + } + return prog; } @@ -8135,20 +8141,75 @@ vim_regfree(prog) prog->engine->regfree(prog); } +#ifdef FEAT_EVAL +static void report_re_switch __ARGS((char_u *pat)); + + static void +report_re_switch(pat) + char_u *pat; +{ + if (p_verbose > 0) + { + verbose_enter(); + MSG_PUTS(_("Switching to backtracking RE engine for pattern: ")); + MSG_PUTS(pat); + verbose_leave(); + } +} +#endif + +static int vim_regexec_both __ARGS((regmatch_T *rmp, char_u *line, colnr_T col, int nl)); + /* * Match a regexp against a string. * "rmp->regprog" is a compiled regexp as returned by vim_regcomp(). * Uses curbuf for line count and 'iskeyword'. + * When "nl" is TRUE consider a "\n" in "line" to be a line break. * * Return TRUE if there is a match, FALSE if not. */ + static int +vim_regexec_both(rmp, line, col, nl) + regmatch_T *rmp; + char_u *line; /* string to match against */ + colnr_T col; /* column to start looking for match */ + int nl; +{ + int result = rmp->regprog->engine->regexec_nl(rmp, line, col, nl); + + /* NFA engine aborted because it's very slow. */ + if (rmp->regprog->re_engine == AUTOMATIC_ENGINE + && result == NFA_TOO_EXPENSIVE) + { + int save_p_re = p_re; + int re_flags = rmp->regprog->re_flags; + char_u *pat = vim_strsave(((nfa_regprog_T *)rmp->regprog)->pattern); + + p_re = BACKTRACKING_ENGINE; + vim_regfree(rmp->regprog); + if (pat != NULL) + { +#ifdef FEAT_EVAL + report_re_switch(pat); +#endif + rmp->regprog = vim_regcomp(pat, re_flags); + if (rmp->regprog != NULL) + result = rmp->regprog->engine->regexec_nl(rmp, line, col, nl); + vim_free(pat); + } + + p_re = save_p_re; + } + return result; +} + int vim_regexec(rmp, line, col) - regmatch_T *rmp; - char_u *line; /* string to match against */ - colnr_T col; /* column to start looking for match */ + regmatch_T *rmp; + char_u *line; + colnr_T col; { - return rmp->regprog->engine->regexec_nl(rmp, line, col, FALSE); + return vim_regexec_both(rmp, line, col, FALSE); } #if defined(FEAT_MODIFY_FNAME) || defined(FEAT_EVAL) \ @@ -8158,11 +8219,11 @@ vim_regexec(rmp, line, col) */ int vim_regexec_nl(rmp, line, col) - regmatch_T *rmp; - char_u *line; - colnr_T col; + regmatch_T *rmp; + char_u *line; + colnr_T col; { - return rmp->regprog->engine->regexec_nl(rmp, line, col, TRUE); + return vim_regexec_both(rmp, line, col, TRUE); } #endif @@ -8183,5 +8244,32 @@ vim_regexec_multi(rmp, win, buf, lnum, col, tm) colnr_T col; /* column to start looking for match */ proftime_T *tm; /* timeout limit or NULL */ { - return rmp->regprog->engine->regexec_multi(rmp, win, buf, lnum, col, tm); + int result = rmp->regprog->engine->regexec_multi( + rmp, win, buf, lnum, col, tm); + + /* NFA engine aborted because it's very slow. */ + if (rmp->regprog->re_engine == AUTOMATIC_ENGINE + && result == NFA_TOO_EXPENSIVE) + { + int save_p_re = p_re; + int re_flags = rmp->regprog->re_flags; + char_u *pat = vim_strsave(((nfa_regprog_T *)rmp->regprog)->pattern); + + p_re = BACKTRACKING_ENGINE; + vim_regfree(rmp->regprog); + if (pat != NULL) + { +#ifdef FEAT_EVAL + report_re_switch(pat); +#endif + rmp->regprog = vim_regcomp(pat, re_flags); + if (rmp->regprog != NULL) + result = rmp->regprog->engine->regexec_multi( + rmp, win, buf, lnum, col, tm); + vim_free(pat); + } + p_re = save_p_re; + } + + return result; } |