home *** CD-ROM | disk | FTP | other *** search
/ vim.ftp.fu-berlin.de / 2015-02-03.vim.ftp.fu-berlin.de.tar / vim.ftp.fu-berlin.de / patches / 7.3 / 7.3.1133 < prev    next >
Encoding:
Internet Message Format  |  2013-06-05  |  8.6 KB
  1. To: vim_dev@googlegroups.com
  2. Subject: Patch 7.3.1133
  3. Fcc: outbox
  4. From: Bram Moolenaar <Bram@moolenaar.net>
  5. Mime-Version: 1.0
  6. Content-Type: text/plain; charset=UTF-8
  7. Content-Transfer-Encoding: 8bit
  8. ------------
  9.  
  10. Patch 7.3.1133
  11. Problem:    New regexp engine is a bit slow.
  12. Solution:   Skip ahead to a character that must match.  Don't try matching a
  13.         "^" patter past the start of line.
  14. Files:        src/regexp_nfa.c, src/regexp.h
  15.  
  16.  
  17. *** ../vim-7.3.1132/src/regexp_nfa.c    2013-06-06 18:04:47.000000000 +0200
  18. --- src/regexp_nfa.c    2013-06-06 18:37:23.000000000 +0200
  19. ***************
  20. *** 257,262 ****
  21. --- 257,264 ----
  22.   static int nfa_ll_index = 0;
  23.   
  24.   static int nfa_regcomp_start __ARGS((char_u *expr, int re_flags));
  25. + static int nfa_get_reganch __ARGS((nfa_state_T *start, int depth));
  26. + static int nfa_get_regstart __ARGS((nfa_state_T *start, int depth));
  27.   static int nfa_recognize_char_class __ARGS((char_u *start, char_u *end, int extra_newl));
  28.   static int nfa_emit_equi_class __ARGS((int c, int neg));
  29.   static int nfa_regatom __ARGS((void));
  30. ***************
  31. *** 331,336 ****
  32. --- 333,487 ----
  33.   }
  34.   
  35.   /*
  36. +  * Figure out if the NFA state list starts with an anchor, must match at start
  37. +  * of the line.
  38. +  */
  39. +     static int
  40. + nfa_get_reganch(start, depth)
  41. +     nfa_state_T *start;
  42. +     int        depth;
  43. + {
  44. +     nfa_state_T *p = start;
  45. + 
  46. +     if (depth > 4)
  47. +     return 0;
  48. + 
  49. +     while (p != NULL)
  50. +     {
  51. +     switch (p->c)
  52. +     {
  53. +         case NFA_BOL:
  54. +         case NFA_BOF:
  55. +         return 1; /* yes! */
  56. + 
  57. +         case NFA_ZSTART:
  58. +         case NFA_ZEND:
  59. +         case NFA_CURSOR:
  60. +         case NFA_VISUAL:
  61. + 
  62. +         case NFA_MOPEN:
  63. +         case NFA_MOPEN1:
  64. +         case NFA_MOPEN2:
  65. +         case NFA_MOPEN3:
  66. +         case NFA_MOPEN4:
  67. +         case NFA_MOPEN5:
  68. +         case NFA_MOPEN6:
  69. +         case NFA_MOPEN7:
  70. +         case NFA_MOPEN8:
  71. +         case NFA_MOPEN9:
  72. +         case NFA_NOPEN:
  73. + #ifdef FEAT_SYN_HL
  74. +         case NFA_ZOPEN:
  75. +         case NFA_ZOPEN1:
  76. +         case NFA_ZOPEN2:
  77. +         case NFA_ZOPEN3:
  78. +         case NFA_ZOPEN4:
  79. +         case NFA_ZOPEN5:
  80. +         case NFA_ZOPEN6:
  81. +         case NFA_ZOPEN7:
  82. +         case NFA_ZOPEN8:
  83. +         case NFA_ZOPEN9:
  84. + #endif
  85. +         p = p->out;
  86. +         break;
  87. + 
  88. +         case NFA_SPLIT:
  89. +         return nfa_get_reganch(p->out, depth + 1)
  90. +                        && nfa_get_reganch(p->out1, depth + 1);
  91. + 
  92. +         default:
  93. +         return 0; /* noooo */
  94. +     }
  95. +     }
  96. +     return 0;
  97. + }
  98. + 
  99. + /*
  100. +  * Figure out if the NFA state list starts with a character which must match
  101. +  * at start of the match.
  102. +  */
  103. +     static int
  104. + nfa_get_regstart(start, depth)
  105. +     nfa_state_T *start;
  106. +     int        depth;
  107. + {
  108. +     nfa_state_T *p = start;
  109. + 
  110. +     if (depth > 4)
  111. +     return 0;
  112. + 
  113. +     while (p != NULL)
  114. +     {
  115. +     switch (p->c)
  116. +     {
  117. +         /* all kinds of zero-width matches */
  118. +         case NFA_BOL:
  119. +         case NFA_BOF:
  120. +         case NFA_BOW:
  121. +         case NFA_EOW:
  122. +         case NFA_ZSTART:
  123. +         case NFA_ZEND:
  124. +         case NFA_CURSOR:
  125. +         case NFA_VISUAL:
  126. +         case NFA_LNUM:
  127. +         case NFA_LNUM_GT:
  128. +         case NFA_LNUM_LT:
  129. +         case NFA_COL:
  130. +         case NFA_COL_GT:
  131. +         case NFA_COL_LT:
  132. +         case NFA_VCOL:
  133. +         case NFA_VCOL_GT:
  134. +         case NFA_VCOL_LT:
  135. +         case NFA_MARK:
  136. +         case NFA_MARK_GT:
  137. +         case NFA_MARK_LT:
  138. + 
  139. +         case NFA_MOPEN:
  140. +         case NFA_MOPEN1:
  141. +         case NFA_MOPEN2:
  142. +         case NFA_MOPEN3:
  143. +         case NFA_MOPEN4:
  144. +         case NFA_MOPEN5:
  145. +         case NFA_MOPEN6:
  146. +         case NFA_MOPEN7:
  147. +         case NFA_MOPEN8:
  148. +         case NFA_MOPEN9:
  149. +         case NFA_NOPEN:
  150. + #ifdef FEAT_SYN_HL
  151. +         case NFA_ZOPEN:
  152. +         case NFA_ZOPEN1:
  153. +         case NFA_ZOPEN2:
  154. +         case NFA_ZOPEN3:
  155. +         case NFA_ZOPEN4:
  156. +         case NFA_ZOPEN5:
  157. +         case NFA_ZOPEN6:
  158. +         case NFA_ZOPEN7:
  159. +         case NFA_ZOPEN8:
  160. +         case NFA_ZOPEN9:
  161. + #endif
  162. +         p = p->out;
  163. +         break;
  164. + 
  165. +         case NFA_SPLIT:
  166. +         {
  167. +         int c1 = nfa_get_regstart(p->out, depth + 1);
  168. +         int c2 = nfa_get_regstart(p->out1, depth + 1);
  169. + 
  170. +         if (c1 == c2)
  171. +             return c1; /* yes! */
  172. +         return 0;
  173. +         }
  174. + 
  175. +         default:
  176. +         if (p->c > 0 && !p->negated)
  177. +             return p->c; /* yes! */
  178. +         return 0;
  179. +     }
  180. +     }
  181. +     return 0;
  182. + }
  183. + 
  184. + /*
  185.    * Allocate more space for post_start.  Called when
  186.    * running above the estimated number of states.
  187.    */
  188. ***************
  189. *** 2121,2126 ****
  190. --- 2272,2281 ----
  191.       if (debugf != NULL)
  192.       {
  193.       nfa_print_state(debugf, prog->start);
  194. + 
  195. +     fprintf(debugf, "reganch: %d\n", prog->reganch);
  196. +     fprintf(debugf, "regstart: %d\n", prog->regstart);
  197. + 
  198.       fclose(debugf);
  199.       }
  200.   }
  201. ***************
  202. *** 4248,4253 ****
  203. --- 4403,4412 ----
  204.           t = &neglist->t[0];
  205.           neglist->n--;
  206.           listidx--;
  207. + #ifdef ENABLE_LOG
  208. +         fprintf(log_fd, "     using neglist entry, %d remaining\n",
  209. +             neglist->n);
  210. + #endif
  211.           }
  212.           else
  213.           t = &thislist->t[listidx];
  214. ***************
  215. *** 4688,4694 ****
  216.   
  217.           case NFA_END_NEG_RANGE:
  218.           /* This follows a series of negated nodes, like:
  219. !          * CHAR(x), NFA_NOT, CHAR(y), NFA_NOT etc. */
  220.           if (curc > 0)
  221.           {
  222.               ll = nextlist;
  223. --- 4847,4853 ----
  224.   
  225.           case NFA_END_NEG_RANGE:
  226.           /* This follows a series of negated nodes, like:
  227. !          * NOT CHAR(x), NOT CHAR(y), etc. */
  228.           if (curc > 0)
  229.           {
  230.               ll = nextlist;
  231. ***************
  232. *** 5304,5316 ****
  233.    * Returns 0 for failure, number of lines contained in the match otherwise.
  234.    */
  235.       static long
  236. ! nfa_regexec_both(line, col)
  237.       char_u    *line;
  238. !     colnr_T    col;        /* column to start looking for match */
  239.   {
  240.       nfa_regprog_T   *prog;
  241.       long        retval = 0L;
  242.       int            i;
  243.   
  244.       if (REG_MULTI)
  245.       {
  246. --- 5463,5476 ----
  247.    * Returns 0 for failure, number of lines contained in the match otherwise.
  248.    */
  249.       static long
  250. ! nfa_regexec_both(line, startcol)
  251.       char_u    *line;
  252. !     colnr_T    startcol;    /* column to start looking for match */
  253.   {
  254.       nfa_regprog_T   *prog;
  255.       long        retval = 0L;
  256.       int            i;
  257. +     colnr_T        col = startcol;
  258.   
  259.       if (REG_MULTI)
  260.       {
  261. ***************
  262. *** 5333,5342 ****
  263.       goto theend;
  264.       }
  265.   
  266. -     /* If the start column is past the maximum column: no need to try. */
  267. -     if (ireg_maxcol > 0 && col >= ireg_maxcol)
  268. -     goto theend;
  269. - 
  270.       /* If pattern contains "\c" or "\C": overrule value of ireg_ic */
  271.       if (prog->regflags & RF_ICASE)
  272.       ireg_ic = TRUE;
  273. --- 5493,5498 ----
  274. ***************
  275. *** 5361,5366 ****
  276. --- 5517,5548 ----
  277.       nfa_regengine.expr = prog->pattern;
  278.   #endif
  279.   
  280. +     if (prog->reganch && col > 0)
  281. +     return 0L;
  282. + 
  283. +     if (prog->regstart != NUL)
  284. +     {
  285. +     char_u *s;
  286. + 
  287. +     /* Skip until the char we know it must start with.
  288. +      * Used often, do some work to avoid call overhead. */
  289. +     if (!ireg_ic
  290. + #ifdef FEAT_MBYTE
  291. +             && !has_mbyte
  292. + #endif
  293. +             )
  294. +         s = vim_strbyte(regline + col, prog->regstart);
  295. +     else
  296. +         s = cstrchr(regline + col, prog->regstart);
  297. +     if (s == NULL)
  298. +         return 0L;
  299. +     col = (int)(s - regline);
  300. +     }
  301. + 
  302. +     /* If the start column is past the maximum column: no need to try. */
  303. +     if (ireg_maxcol > 0 && col >= ireg_maxcol)
  304. +     goto theend;
  305. + 
  306.       nstate = prog->nstate;
  307.       for (i = 0; i < nstate; ++i)
  308.       {
  309. ***************
  310. *** 5459,5464 ****
  311. --- 5641,5650 ----
  312.       prog->has_zend = nfa_has_zend;
  313.       prog->has_backref = nfa_has_backref;
  314.       prog->nsubexp = regnpar;
  315. + 
  316. +     prog->reganch = nfa_get_reganch(prog->start, 0);
  317. +     prog->regstart = nfa_get_regstart(prog->start, 0);
  318. + 
  319.   #ifdef ENABLE_LOG
  320.       nfa_postfix_dump(expr, OK);
  321.       nfa_dump(prog);
  322. *** ../vim-7.3.1132/src/regexp.h    2013-06-03 12:17:00.000000000 +0200
  323. --- src/regexp.h    2013-06-06 17:19:23.000000000 +0200
  324. ***************
  325. *** 87,92 ****
  326. --- 87,96 ----
  327.       unsigned        regflags;
  328.   
  329.       nfa_state_T        *start;        /* points into state[] */
  330. + 
  331. +     int            reganch;    /* pattern starts with ^ */
  332. +     int            regstart;    /* char at start of pattern */
  333. + 
  334.       int            has_zend;    /* pattern contains \ze */
  335.       int            has_backref;    /* pattern contains \1 .. \9 */
  336.   #ifdef FEAT_SYN_HL
  337. *** ../vim-7.3.1132/src/version.c    2013-06-06 18:04:47.000000000 +0200
  338. --- src/version.c    2013-06-06 18:43:55.000000000 +0200
  339. ***************
  340. *** 730,731 ****
  341. --- 730,733 ----
  342.   {   /* Add new patch number below this line */
  343. + /**/
  344. +     1133,
  345.   /**/
  346.  
  347. -- 
  348. From "know your smileys":
  349.  %    Bike accident.  A bit far-fetched, I suppose; although...
  350.              o      _     _         _
  351.      _o     /\_   _ \\o  (_)\__/o  (_)
  352.    _< \_   _>(_) (_)/<_    \_| \   _|/' \/
  353.   (_)>(_) (_)        (_)   (_)    (_)'  _\o_
  354.  
  355.  /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net   \\\
  356. ///        sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
  357. \\\  an exciting new programming language -- http://www.Zimbu.org        ///
  358.  \\\            help me help AIDS victims -- http://ICCF-Holland.org    ///
  359.