To: vim_dev@googlegroups.com
Subject: Patch 7.3.1151
Fcc: outbox
From: Bram Moolenaar <Bram@moolenaar.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
------------

Patch 7.3.1151
Problem:    New regexp engine: Slow when a look-behind match is followed by a
	    zero-width match.
Solution:   Postpone the look-behind match more often.
Files:	    src/regexp_nfa.c


*** ../vim-7.3.1150/src/regexp_nfa.c	2013-06-08 22:29:59.000000000 +0200
--- src/regexp_nfa.c	2013-06-08 23:11:19.000000000 +0200
***************
*** 2794,2799 ****
--- 2794,2800 ----
      /* unrecognized */
      return -1;
  }
+ 
  /*
   * Convert a postfix form into its equivalent NFA.
   * Return the NFA start state on success, NULL otherwise.
***************
*** 3433,3438 ****
--- 3434,3440 ----
  static void copy_sub_off __ARGS((regsub_T *to, regsub_T *from));
  static int sub_equal __ARGS((regsub_T *sub1, regsub_T *sub2));
  static int has_state_with_pos __ARGS((nfa_list_T *l, nfa_state_T *state, regsubs_T *subs));
+ static int match_follows __ARGS((nfa_state_T *startstate, int depth));
  static int state_in_list __ARGS((nfa_list_T *l, nfa_state_T *state, regsubs_T *subs));
  static void addstate __ARGS((nfa_list_T *l, nfa_state_T *state, regsubs_T *subs, int off));
  static void addstate_here __ARGS((nfa_list_T *l, nfa_state_T *state, regsubs_T *subs, nfa_pim_T *pim, int *ip));
***************
*** 3626,3631 ****
--- 3628,3715 ----
  }
  
  /*
+  * Return TRUE if "state" leads to a NFA_MATCH without advancing the input.
+  */
+     static int
+ match_follows(startstate, depth)
+     nfa_state_T *startstate;
+     int		depth;
+ {
+     nfa_state_T	    *state = startstate;
+ 
+     /* avoid too much recursion */
+     if (depth > 10)
+ 	return FALSE;
+ 
+     for (;;)
+     {
+ 	switch (state->c)
+ 	{
+ 	    case NFA_MATCH:
+ 		return TRUE;
+ 
+ 	    case NFA_SPLIT:
+ 		return match_follows(state->out, depth + 1)
+ 				     || match_follows(state->out1, depth + 1);
+ 
+ 	    case NFA_START_INVISIBLE:
+ 	    case NFA_START_INVISIBLE_BEFORE:
+ 	    case NFA_START_INVISIBLE_NEG:
+ 	    case NFA_START_INVISIBLE_BEFORE_NEG:
+ 	    case NFA_COMPOSING:
+ 		/* skip ahead to next state */
+ 		state = state->out1->out;
+ 		break;
+ 
+ 	    case NFA_ANY:
+ 	    case NFA_IDENT:
+ 	    case NFA_SIDENT:
+ 	    case NFA_KWORD:
+ 	    case NFA_SKWORD:
+ 	    case NFA_FNAME:
+ 	    case NFA_SFNAME:
+ 	    case NFA_PRINT:
+ 	    case NFA_SPRINT:
+ 	    case NFA_WHITE:
+ 	    case NFA_NWHITE:
+ 	    case NFA_DIGIT:
+ 	    case NFA_NDIGIT:
+ 	    case NFA_HEX:
+ 	    case NFA_NHEX:
+ 	    case NFA_OCTAL:
+ 	    case NFA_NOCTAL:
+ 	    case NFA_WORD:
+ 	    case NFA_NWORD:
+ 	    case NFA_HEAD:
+ 	    case NFA_NHEAD:
+ 	    case NFA_ALPHA:
+ 	    case NFA_NALPHA:
+ 	    case NFA_LOWER:
+ 	    case NFA_NLOWER:
+ 	    case NFA_UPPER:
+ 	    case NFA_NUPPER:
+ 	    case NFA_START_COLL:
+ 	    case NFA_START_NEG_COLL:
+ 	    case NFA_NEWL:
+ 		/* state will advance input */
+ 		return FALSE;
+ 
+ 	    default:
+ 		if (state->c > 0)
+ 		    /* state will advance input */
+ 		    return FALSE;
+ 
+ 		/* Others: zero-width or possibly zero-width, might still find
+ 		 * a match at the same position, keep looking. */
+ 		break;
+ 	}
+ 	state = state->out;
+     }
+     return FALSE;
+ }
+ 
+ 
+ /*
   * Return TRUE if "state" is already in list "l".
   */
      static int
***************
*** 5714,5722 ****
  
  	    if (add_state != NULL)
  	    {
! 		if (t->pim != NULL)
  		{
- 		    /* postponed invisible match */
  		    if (t->pim->result == NFA_PIM_TODO)
  		    {
  #ifdef ENABLE_LOG
--- 5798,5808 ----
  
  	    if (add_state != NULL)
  	    {
! 		/* Handle the postponed invisible match before advancing to
! 		 * the next character and for a zero-width match if the match
! 		 * might end without advancing. */
! 		if (t->pim != NULL && (!add_here || match_follows(add_state, 0)))
  		{
  		    if (t->pim->result == NFA_PIM_TODO)
  		    {
  #ifdef ENABLE_LOG
***************
*** 5773,5779 ****
  		}
  
  		if (add_here)
! 		    addstate_here(thislist, add_state, &t->subs, NULL, &listidx);
  		else
  		{
  		    addstate(nextlist, add_state, &t->subs, add_off);
--- 5859,5865 ----
  		}
  
  		if (add_here)
! 		    addstate_here(thislist, add_state, &t->subs, t->pim, &listidx);
  		else
  		{
  		    addstate(nextlist, add_state, &t->subs, add_off);
*** ../vim-7.3.1150/src/version.c	2013-06-08 22:29:59.000000000 +0200
--- src/version.c	2013-06-08 23:23:53.000000000 +0200
***************
*** 730,731 ****
--- 730,733 ----
  {   /* Add new patch number below this line */
+ /**/
+     1151,
  /**/

-- 
hundred-and-one symptoms of being an internet addict:
117. You are more comfortable typing in html.

 /// 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    ///