To: vim_dev@googlegroups.com

Subject: Patch 7.3.1106

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

Problem:    New regexp engine: saving and restoring lastlist in the states

	    takes a lot of time.

Solution:   Use a second lastlist value for the first recursive call.

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

*** ../vim-7.3.1105/src/regexp.h	2013-06-02 15:55:52.000000000 +0200

--- src/regexp.h	2013-06-03 11:29:26.000000000 +0200

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

*** 72,78 ****

      nfa_state_T		*out;

      nfa_state_T		*out1;

      int			id;

!     int			lastlist;

      int			negated;

      int			val;

  };

--- 72,78 ----

      nfa_state_T		*out;

      nfa_state_T		*out1;

      int			id;

!     int			lastlist[2]; /* 0: normal, 1: recursive */

      int			negated;

      int			val;

  };

*** ../vim-7.3.1105/src/regexp_nfa.c	2013-06-02 22:37:39.000000000 +0200

--- src/regexp_nfa.c	2013-06-03 12:15:17.000000000 +0200

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

*** 255,260 ****

--- 255,269 ----

  /* If not NULL match must end at this position */

  static save_se_T *nfa_endp = NULL;

+ /* listid is global, so that it increases on recursive calls to

+  * nfa_regmatch(), which means we don't have to clear the lastlist field of

+  * all the states. */

+ static int nfa_listid;

+ static int nfa_alt_listid;

+ 

+ /* 0 for first call to nfa_regmatch(), 1 for recursive call. */

+ static int nfa_ll_index = 0;

+ 

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

  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));

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

*** 2169,2175 ****

      s->out1 = out1;

      s->id   = istate;

!     s->lastlist = 0;

      s->negated = FALSE;

      return s;

--- 2178,2185 ----

      s->out1 = out1;

      s->id   = istate;

!     s->lastlist[0] = 0;

!     s->lastlist[1] = 0;

      s->negated = FALSE;

      return s;

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

*** 3113,3121 ****

  #endif

  	    /* These nodes do not need to be added, but we need to bail out

  	     * when it was tried to be added to this list before. */

! 	    if (state->lastlist == l->id)

  		goto skip_add;

! 	    state->lastlist = l->id;

  	    break;

  	case NFA_BOL:

--- 3123,3131 ----

  #endif

  	    /* These nodes do not need to be added, but we need to bail out

  	     * when it was tried to be added to this list before. */

! 	    if (state->lastlist[nfa_ll_index] == l->id)

  		goto skip_add;

! 	    state->lastlist[nfa_ll_index] = l->id;

  	    break;

  	case NFA_BOL:

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

*** 3131,3137 ****

  	    /* FALLTHROUGH */

  	default:

! 	    if (state->lastlist == l->id)

  	    {

  		/* This state is already in the list, don't add it again,

  		 * unless it is an MOPEN that is used for a backreference. */

--- 3141,3147 ----

  	    /* FALLTHROUGH */

  	default:

! 	    if (state->lastlist[nfa_ll_index] == l->id)

  	    {

  		/* This state is already in the list, don't add it again,

  		 * unless it is an MOPEN that is used for a backreference. */

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

*** 3173,3179 ****

  	    }

  	    /* add the state to the list */

! 	    state->lastlist = l->id;

  	    thread = &l->t[l->n++];

  	    thread->state = state;

  	    copy_sub(&thread->subs.norm, &subs->norm);

--- 3183,3189 ----

  	    }

  	    /* add the state to the list */

! 	    state->lastlist[nfa_ll_index] = l->id;

  	    thread = &l->t[l->n++];

  	    thread->state = state;

  	    copy_sub(&thread->subs.norm, &subs->norm);

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

*** 3616,3621 ****

--- 3626,3632 ----

  /*

   * Save list IDs for all NFA states of "prog" into "list".

   * Also reset the IDs to zero.

+  * Only used for the recursive value lastlist[1].

   */

      static void

  nfa_save_listids(prog, list)

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

*** 3629,3636 ****

      p = &prog->state[0];

      for (i = prog->nstate; --i >= 0; )

      {

! 	list[i] = p->lastlist;

! 	p->lastlist = 0;

  	++p;

      }

  }

--- 3640,3647 ----

      p = &prog->state[0];

      for (i = prog->nstate; --i >= 0; )

      {

! 	list[i] = p->lastlist[1];

! 	p->lastlist[1] = 0;

  	++p;

      }

  }

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

*** 3649,3655 ****

      p = &prog->state[0];

      for (i = prog->nstate; --i >= 0; )

      {

! 	p->lastlist = list[i];

  	++p;

      }

  }

--- 3660,3666 ----

      p = &prog->state[0];

      for (i = prog->nstate; --i >= 0; )

      {

! 	p->lastlist[1] = list[i];

  	++p;

      }

  }

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

*** 3683,3692 ****

--- 3694,3705 ----

      char_u	*save_regline = regline;

      int		save_reglnum = reglnum;

      int		save_nfa_match = nfa_match;

+     int		save_nfa_listid = nfa_listid;

      save_se_T   *save_nfa_endp = nfa_endp;

      save_se_T   endpos;

      save_se_T   *endposp = NULL;

      int		result;

+     int		need_restore = FALSE;

      if (state->c == NFA_START_INVISIBLE_BEFORE)

      {

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

*** 3745,3774 ****

  	}

      }

-     /* Call nfa_regmatch() to check if the current concat matches

-      * at this position. The concat ends with the node

-      * NFA_END_INVISIBLE */

-     if (*listids == NULL)

-     {

- 	*listids = (int *)lalloc(sizeof(int) * nstate, TRUE);

- 	if (*listids == NULL)

- 	{

- 	    EMSG(_("E878: (NFA) Could not allocate memory for branch traversal!"));

- 	    return 0;

- 	}

-     }

  #ifdef ENABLE_LOG

      if (log_fd != stderr)

  	fclose(log_fd);

      log_fd = NULL;

  #endif

!     /* Have to clear the listid field of the NFA nodes, so that

!      * nfa_regmatch() and addstate() can run properly after

!      * recursion. */

!     nfa_save_listids(prog, *listids);

      nfa_endp = endposp;

      result = nfa_regmatch(prog, state->out, submatch, m);

!     nfa_restore_listids(prog, *listids);

      /* restore position in input text */

      reginput = save_reginput;

--- 3758,3809 ----

  	}

      }

  #ifdef ENABLE_LOG

      if (log_fd != stderr)

  	fclose(log_fd);

      log_fd = NULL;

  #endif

!     /* Have to clear the lastlist field of the NFA nodes, so that

!      * nfa_regmatch() and addstate() can run properly after recursion. */

!     if (nfa_ll_index == 1)

!     {

! 	/* Already calling nfa_regmatch() recursively.  Save the lastlist[1]

! 	 * values and clear them. */

! 	if (*listids == NULL)

! 	{

! 	    *listids = (int *)lalloc(sizeof(int) * nstate, TRUE);

! 	    if (*listids == NULL)

! 	    {

! 		EMSG(_("E878: (NFA) Could not allocate memory for branch traversal!"));

! 		return 0;

! 	    }

! 	}

! 	nfa_save_listids(prog, *listids);

! 	need_restore = TRUE;

! 	/* any value of nfa_listid will do */

!     }

!     else

!     {

! 	/* First recursive nfa_regmatch() call, switch to the second lastlist

! 	 * entry.  Make sure nfa_listid is different from a previous recursive

! 	 * call, because some states may still have this ID. */

! 	++nfa_ll_index;

! 	if (nfa_listid <= nfa_alt_listid)

! 	    nfa_listid = nfa_alt_listid;

!     }

! 

!     /* Call nfa_regmatch() to check if the current concat matches at this

!      * position. The concat ends with the node NFA_END_INVISIBLE */

      nfa_endp = endposp;

      result = nfa_regmatch(prog, state->out, submatch, m);

! 

!     if (need_restore)

! 	nfa_restore_listids(prog, *listids);

!     else

!     {

! 	--nfa_ll_index;

! 	nfa_alt_listid = nfa_listid;

!     }

      /* restore position in input text */

      reginput = save_reginput;

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

*** 3776,3781 ****

--- 3811,3817 ----

      reglnum = save_reglnum;

      nfa_match = save_nfa_match;

      nfa_endp = save_nfa_endp;

+     nfa_listid = save_nfa_listid;

  #ifdef ENABLE_LOG

      log_fd = fopen(NFA_REGEXP_RUN_LOG, "a");

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

*** 3821,3827 ****

      nfa_list_T	list[3];

      nfa_list_T	*listtbl[2][2];

      nfa_list_T	*ll;

-     int		listid = 1;

      int		listidx;

      nfa_list_T	*thislist;

      nfa_list_T	*nextlist;

--- 3857,3862 ----

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

*** 3875,3881 ****

  #ifdef ENABLE_LOG

      fprintf(log_fd, "(---) STARTSTATE\n");

  #endif

!     thislist->id = listid;

      addstate(thislist, start, m, 0);

      /* There are two cases when the NFA advances: 1. input char matches the

--- 3910,3916 ----

  #ifdef ENABLE_LOG

      fprintf(log_fd, "(---) STARTSTATE\n");

  #endif

!     thislist->id = nfa_listid + 1;

      addstate(thislist, start, m, 0);

      /* There are two cases when the NFA advances: 1. input char matches the

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

*** 3923,3932 ****

  	nextlist = &list[flag ^= 1];

  	nextlist->n = 0;	    /* clear nextlist */

  	listtbl[1][0] = nextlist;

! 	++listid;

! 	thislist->id = listid;

! 	nextlist->id = listid + 1;

! 	neglist->id = listid + 1;

  #ifdef ENABLE_LOG

  	fprintf(log_fd, "------------------------------------------\n");

--- 3958,3967 ----

  	nextlist = &list[flag ^= 1];

  	nextlist->n = 0;	    /* clear nextlist */

  	listtbl[1][0] = nextlist;

! 	++nfa_listid;

! 	thislist->id = nfa_listid;

! 	nextlist->id = nfa_listid + 1;

! 	neglist->id = nfa_listid + 1;

  #ifdef ENABLE_LOG

  	fprintf(log_fd, "------------------------------------------\n");

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

*** 4843,4848 ****

--- 4878,4885 ----

      nfa_has_zend = prog->has_zend;

      nfa_has_backref = prog->has_backref;

      nfa_nsubexpr = prog->nsubexp;

+     nfa_listid = 1;

+     nfa_alt_listid = 2;

  #ifdef DEBUG

      nfa_regengine.expr = prog->pattern;

  #endif

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

*** 4851,4857 ****

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

      {

  	prog->state[i].id = i;

! 	prog->state[i].lastlist = 0;

      }

      retval = nfa_regtry(prog, col);

--- 4888,4895 ----

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

      {

  	prog->state[i].id = i;

! 	prog->state[i].lastlist[0] = 0;

! 	prog->state[i].lastlist[1] = 0;

      }

      retval = nfa_regtry(prog, col);

*** ../vim-7.3.1105/src/version.c	2013-06-02 22:37:39.000000000 +0200

--- src/version.c	2013-06-03 12:13:15.000000000 +0200

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

*** 730,731 ****

--- 730,733 ----

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

+ /**/

+     1106,

  /**/

-- 

hundred-and-one symptoms of being an internet addict:

59. Your wife says communication is important in a marriage...so you buy

    another computer and install a second phone line so the two of you can

    chat.

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