To: vim_dev@googlegroups.com Subject: Patch 7.4.593 Fcc: outbox From: Bram Moolenaar Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit ------------ Patch 7.4.593 Problem: Crash when searching for "x\{0,90000}". (Dominique Pelle) Solution: Bail out from the NFA engine when the max limit is much higher than the min limit. Files: src/regexp_nfa.c, src/regexp.c, src/vim.h *** ../vim-7.4.592/src/regexp_nfa.c 2015-01-18 16:46:28.983828439 +0100 --- src/regexp_nfa.c 2015-01-27 12:47:42.515592198 +0100 *************** *** 244,249 **** --- 244,252 ---- static char_u e_misplaced[] = N_("E866: (NFA regexp) Misplaced %c"); static char_u e_ill_char_class[] = N_("E877: (NFA regexp) Invalid character class: %ld"); + /* re_flags passed to nfa_regcomp() */ + static int nfa_re_flags; + /* NFA regexp \ze operator encountered. */ static int nfa_has_zend; *************** *** 2011,2020 **** * * */ if (minval == 0 && maxval == MAX_LIMIT) { ! if (greedy) /* \{}, \{0,} */ EMIT(NFA_STAR); ! else /* \{-}, \{-0,} */ EMIT(NFA_STAR_NONGREEDY); break; --- 2014,2023 ---- * * */ if (minval == 0 && maxval == MAX_LIMIT) { ! if (greedy) /* { { (match the braces) */ /* \{}, \{0,} */ EMIT(NFA_STAR); ! else /* { { (match the braces) */ /* \{-}, \{-0,} */ EMIT(NFA_STAR_NONGREEDY); break; *************** *** 2030,2035 **** --- 2033,2044 ---- return OK; } + /* The engine is very inefficient (uses too many states) when the + * maximum is much larger than the minimum. Bail out if we can + * use the other engine. */ + if ((nfa_re_flags & RE_AUTO) && maxval > minval + 200) + return FAIL; + /* Ignore previous call to nfa_regatom() */ post_ptr = post_start + my_post_start; /* Save parse state after the repeated atom and the \{} */ *************** *** 7046,7051 **** --- 7055,7061 ---- return NULL; nfa_regengine.expr = expr; + nfa_re_flags = re_flags; init_class_tab(); *** ../vim-7.4.592/src/regexp.c 2014-11-20 23:07:00.515474686 +0100 --- src/regexp.c 2015-01-27 12:49:02.170719494 +0100 *************** *** 8081,8087 **** * First try the NFA engine, unless backtracking was requested. */ if (regexp_engine != BACKTRACKING_ENGINE) ! prog = nfa_regengine.regcomp(expr, re_flags); else prog = bt_regengine.regcomp(expr, re_flags); --- 8081,8088 ---- * First try the NFA engine, unless backtracking was requested. */ if (regexp_engine != BACKTRACKING_ENGINE) ! prog = nfa_regengine.regcomp(expr, ! re_flags + (regexp_engine == AUTOMATIC_ENGINE ? RE_AUTO : 0)); else prog = bt_regengine.regcomp(expr, re_flags); *************** *** 8105,8120 **** #endif /* * 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) --- 8106,8119 ---- #endif /* * If the NFA engine failed, try the backtracking engine. ! * The NFA engine also fails for patterns that it can't handle well ! * but are still valid patterns, thus a retry should work. ! */ if (regexp_engine == AUTOMATIC_ENGINE) { + regexp_engine = BACKTRACKING_ENGINE; prog = bt_regengine.regcomp(expr, re_flags); } } if (prog != NULL) *** ../vim-7.4.592/src/vim.h 2014-12-08 04:16:26.269702835 +0100 --- src/vim.h 2015-01-27 12:41:57.483371986 +0100 *************** *** 1020,1025 **** --- 1020,1026 ---- #define RE_MAGIC 1 /* 'magic' option */ #define RE_STRING 2 /* match in string instead of buffer text */ #define RE_STRICT 4 /* don't allow [abc] without ] */ + #define RE_AUTO 8 /* automatic engine selection */ #ifdef FEAT_SYN_HL /* values for reg_do_extmatch */ *** ../vim-7.4.592/src/version.c 2015-01-27 11:26:11.041183653 +0100 --- src/version.c 2015-01-27 12:52:44.720281369 +0100 *************** *** 743,744 **** --- 743,746 ---- { /* Add new patch number below this line */ + /**/ + 593, /**/ -- hundred-and-one symptoms of being an internet addict: 121. You ask for e-mail adresses instead of telephone numbers. /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net \\\ /// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\ \\\ an exciting new programming language -- http://www.Zimbu.org /// \\\ help me help AIDS victims -- http://ICCF-Holland.org ///