To: vim_dev@googlegroups.com

Subject: Patch 7.3.1133

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.1133

Problem:    New regexp engine is a bit slow.

Solution:   Skip ahead to a character that must match.  Don't try matching a

	    "^" patter past the start of line.

Files:	    src/regexp_nfa.c, src/regexp.h

*** ../vim-7.3.1132/src/regexp_nfa.c	2013-06-06 18:04:47.000000000 +0200

--- src/regexp_nfa.c	2013-06-06 18:37:23.000000000 +0200

***************

*** 257,262 ****

--- 257,264 ----

  static int nfa_ll_index = 0;

  static int nfa_regcomp_start __ARGS((char_u *expr, int re_flags));

+ static int nfa_get_reganch __ARGS((nfa_state_T *start, int depth));

+ static int nfa_get_regstart __ARGS((nfa_state_T *start, int depth));

  static int nfa_recognize_char_class __ARGS((char_u *start, char_u *end, int extra_newl));

  static int nfa_emit_equi_class __ARGS((int c, int neg));

  static int nfa_regatom __ARGS((void));

***************

*** 331,336 ****

--- 333,487 ----

  }

  /*

+  * Figure out if the NFA state list starts with an anchor, must match at start

+  * of the line.

+  */

+     static int

+ nfa_get_reganch(start, depth)

+     nfa_state_T *start;

+     int		depth;

+ {

+     nfa_state_T *p = start;

+ 

+     if (depth > 4)

+ 	return 0;

+ 

+     while (p != NULL)

+     {

+ 	switch (p->c)

+ 	{

+ 	    case NFA_BOL:

+ 	    case NFA_BOF:

+ 		return 1; /* yes! */

+ 

+ 	    case NFA_ZSTART:

+ 	    case NFA_ZEND:

+ 	    case NFA_CURSOR:

+ 	    case NFA_VISUAL:

+ 

+ 	    case NFA_MOPEN:

+ 	    case NFA_MOPEN1:

+ 	    case NFA_MOPEN2:

+ 	    case NFA_MOPEN3:

+ 	    case NFA_MOPEN4:

+ 	    case NFA_MOPEN5:

+ 	    case NFA_MOPEN6:

+ 	    case NFA_MOPEN7:

+ 	    case NFA_MOPEN8:

+ 	    case NFA_MOPEN9:

+ 	    case NFA_NOPEN:

+ #ifdef FEAT_SYN_HL

+ 	    case NFA_ZOPEN:

+ 	    case NFA_ZOPEN1:

+ 	    case NFA_ZOPEN2:

+ 	    case NFA_ZOPEN3:

+ 	    case NFA_ZOPEN4:

+ 	    case NFA_ZOPEN5:

+ 	    case NFA_ZOPEN6:

+ 	    case NFA_ZOPEN7:

+ 	    case NFA_ZOPEN8:

+ 	    case NFA_ZOPEN9:

+ #endif

+ 		p = p->out;

+ 		break;

+ 

+ 	    case NFA_SPLIT:

+ 		return nfa_get_reganch(p->out, depth + 1)

+ 				       && nfa_get_reganch(p->out1, depth + 1);

+ 

+ 	    default:

+ 		return 0; /* noooo */

+ 	}

+     }

+     return 0;

+ }

+ 

+ /*

+  * Figure out if the NFA state list starts with a character which must match

+  * at start of the match.

+  */

+     static int

+ nfa_get_regstart(start, depth)

+     nfa_state_T *start;

+     int		depth;

+ {

+     nfa_state_T *p = start;

+ 

+     if (depth > 4)

+ 	return 0;

+ 

+     while (p != NULL)

+     {

+ 	switch (p->c)

+ 	{

+ 	    /* all kinds of zero-width matches */

+ 	    case NFA_BOL:

+ 	    case NFA_BOF:

+ 	    case NFA_BOW:

+ 	    case NFA_EOW:

+ 	    case NFA_ZSTART:

+ 	    case NFA_ZEND:

+ 	    case NFA_CURSOR:

+ 	    case NFA_VISUAL:

+ 	    case NFA_LNUM:

+ 	    case NFA_LNUM_GT:

+ 	    case NFA_LNUM_LT:

+ 	    case NFA_COL:

+ 	    case NFA_COL_GT:

+ 	    case NFA_COL_LT:

+ 	    case NFA_VCOL:

+ 	    case NFA_VCOL_GT:

+ 	    case NFA_VCOL_LT:

+ 	    case NFA_MARK:

+ 	    case NFA_MARK_GT:

+ 	    case NFA_MARK_LT:

+ 

+ 	    case NFA_MOPEN:

+ 	    case NFA_MOPEN1:

+ 	    case NFA_MOPEN2:

+ 	    case NFA_MOPEN3:

+ 	    case NFA_MOPEN4:

+ 	    case NFA_MOPEN5:

+ 	    case NFA_MOPEN6:

+ 	    case NFA_MOPEN7:

+ 	    case NFA_MOPEN8:

+ 	    case NFA_MOPEN9:

+ 	    case NFA_NOPEN:

+ #ifdef FEAT_SYN_HL

+ 	    case NFA_ZOPEN:

+ 	    case NFA_ZOPEN1:

+ 	    case NFA_ZOPEN2:

+ 	    case NFA_ZOPEN3:

+ 	    case NFA_ZOPEN4:

+ 	    case NFA_ZOPEN5:

+ 	    case NFA_ZOPEN6:

+ 	    case NFA_ZOPEN7:

+ 	    case NFA_ZOPEN8:

+ 	    case NFA_ZOPEN9:

+ #endif

+ 		p = p->out;

+ 		break;

+ 

+ 	    case NFA_SPLIT:

+ 	    {

+ 		int c1 = nfa_get_regstart(p->out, depth + 1);

+ 		int c2 = nfa_get_regstart(p->out1, depth + 1);

+ 

+ 		if (c1 == c2)

+ 		    return c1; /* yes! */

+ 		return 0;

+ 	    }

+ 

+ 	    default:

+ 		if (p->c > 0 && !p->negated)

+ 		    return p->c; /* yes! */

+ 		return 0;

+ 	}

+     }

+     return 0;

+ }

+ 

+ /*

   * Allocate more space for post_start.  Called when

   * running above the estimated number of states.

   */

***************

*** 2121,2126 ****

--- 2272,2281 ----

      if (debugf != NULL)

      {

  	nfa_print_state(debugf, prog->start);

+ 

+ 	fprintf(debugf, "reganch: %d\n", prog->reganch);

+ 	fprintf(debugf, "regstart: %d\n", prog->regstart);

+ 

  	fclose(debugf);

      }

  }

***************

*** 4248,4253 ****

--- 4403,4412 ----

  		t = &neglist->t[0];

  		neglist->n--;

  		listidx--;

+ #ifdef ENABLE_LOG

+ 		fprintf(log_fd, "     using neglist entry, %d remaining\n",

+ 			neglist->n);

+ #endif

  	    }

  	    else

  		t = &thislist->t[listidx];

***************

*** 4688,4694 ****

  	    case NFA_END_NEG_RANGE:

  		/* This follows a series of negated nodes, like:

! 		 * CHAR(x), NFA_NOT, CHAR(y), NFA_NOT etc. */

  		if (curc > 0)

  		{

  		    ll = nextlist;

--- 4847,4853 ----

  	    case NFA_END_NEG_RANGE:

  		/* This follows a series of negated nodes, like:

! 		 * NOT CHAR(x), NOT CHAR(y), etc. */

  		if (curc > 0)

  		{

  		    ll = nextlist;

***************

*** 5304,5316 ****

   * Returns 0 for failure, number of lines contained in the match otherwise.

   */

      static long

! nfa_regexec_both(line, col)

      char_u	*line;

!     colnr_T	col;		/* column to start looking for match */

  {

      nfa_regprog_T   *prog;

      long	    retval = 0L;

      int		    i;

      if (REG_MULTI)

      {

--- 5463,5476 ----

   * Returns 0 for failure, number of lines contained in the match otherwise.

   */

      static long

! nfa_regexec_both(line, startcol)

      char_u	*line;

!     colnr_T	startcol;	/* column to start looking for match */

  {

      nfa_regprog_T   *prog;

      long	    retval = 0L;

      int		    i;

+     colnr_T	    col = startcol;

      if (REG_MULTI)

      {

***************

*** 5333,5342 ****

  	goto theend;

      }

-     /* If the start column is past the maximum column: no need to try. */

-     if (ireg_maxcol > 0 && col >= ireg_maxcol)

- 	goto theend;

- 

      /* If pattern contains "\c" or "\C": overrule value of ireg_ic */

      if (prog->regflags & RF_ICASE)

  	ireg_ic = TRUE;

--- 5493,5498 ----

***************

*** 5361,5366 ****

--- 5517,5548 ----

      nfa_regengine.expr = prog->pattern;

  #endif

+     if (prog->reganch && col > 0)

+ 	return 0L;

+ 

+     if (prog->regstart != NUL)

+     {

+ 	char_u *s;

+ 

+ 	/* Skip until the char we know it must start with.

+ 	 * Used often, do some work to avoid call overhead. */

+ 	if (!ireg_ic

+ #ifdef FEAT_MBYTE

+ 		    && !has_mbyte

+ #endif

+ 		    )

+ 	    s = vim_strbyte(regline + col, prog->regstart);

+ 	else

+ 	    s = cstrchr(regline + col, prog->regstart);

+ 	if (s == NULL)

+ 	    return 0L;

+ 	col = (int)(s - regline);

+     }

+ 

+     /* If the start column is past the maximum column: no need to try. */

+     if (ireg_maxcol > 0 && col >= ireg_maxcol)

+ 	goto theend;

+ 

      nstate = prog->nstate;

      for (i = 0; i < nstate; ++i)

      {

***************

*** 5459,5464 ****

--- 5641,5650 ----

      prog->has_zend = nfa_has_zend;

      prog->has_backref = nfa_has_backref;

      prog->nsubexp = regnpar;

+ 

+     prog->reganch = nfa_get_reganch(prog->start, 0);

+     prog->regstart = nfa_get_regstart(prog->start, 0);

+ 

  #ifdef ENABLE_LOG

      nfa_postfix_dump(expr, OK);

      nfa_dump(prog);

*** ../vim-7.3.1132/src/regexp.h	2013-06-03 12:17:00.000000000 +0200

--- src/regexp.h	2013-06-06 17:19:23.000000000 +0200

***************

*** 87,92 ****

--- 87,96 ----

      unsigned		regflags;

      nfa_state_T		*start;		/* points into state[] */

+ 

+     int			reganch;	/* pattern starts with ^ */

+     int			regstart;	/* char at start of pattern */

+ 

      int			has_zend;	/* pattern contains \ze */

      int			has_backref;	/* pattern contains \1 .. \9 */

  #ifdef FEAT_SYN_HL

*** ../vim-7.3.1132/src/version.c	2013-06-06 18:04:47.000000000 +0200

--- src/version.c	2013-06-06 18:43:55.000000000 +0200

***************

*** 730,731 ****

--- 730,733 ----

  {   /* Add new patch number below this line */

+ /**/

+     1133,

  /**/

-- 

From "know your smileys":

 %	Bike accident.  A bit far-fetched, I suppose; although...

             o      _     _         _

     _o     /\_   _ \\o  (_)\__/o  (_)

   _< \_   _>(_) (_)/<_    \_| \   _|/' \/

  (_)>(_) (_)        (_)   (_)    (_)'  _\o_

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