vim-patch:9.0.0951: trying every character position for a match is inefficient (#21198)

Problem:    Trying every character position for a match is inefficient.
Solution:   Use the start position of the match ignoring "\zs".

https://github.com/vim/vim/commit/01105b37a108022515d364201767f7f111ec4222

Co-authored-by: Bram Moolenaar <Bram@vim.org>

4 files changed, 32 insertions, 3 deletions

diff --git a/src/nvim/regexp.c b/src/nvim/regexp.c
index 95557a3469..0d3cb927e9 100644
--- a/src/nvim/regexp.c
+++ b/src/nvim/regexp.c
@@ -958,10 +958,12 @@ static unsigned reg_tofreelen;
 typedef struct {
   regmatch_T *reg_match;
   regmmatch_T *reg_mmatch;
+
   char_u **reg_startp;
   char_u **reg_endp;
   lpos_T *reg_startpos;
   lpos_T *reg_endpos;
+
   win_T *reg_win;
   buf_T *reg_buf;
   linenr_T reg_firstlnum;
diff --git a/src/nvim/regexp_bt.c b/src/nvim/regexp_bt.c
index 2337dbb51c..9411d17f57 100644
--- a/src/nvim/regexp_bt.c
+++ b/src/nvim/regexp_bt.c
@@ -4930,15 +4930,16 @@ static long regtry(bt_regprog_T *prog, colnr_T col, proftime_T *tm, int *timed_o
 /// Match a regexp against a string ("line" points to the string) or multiple
 /// lines (if "line" is NULL, use reg_getline()).
 ///
-/// @param col        column to start search
+/// @param startcol   column to start looking for match
 /// @param tm         timeout limit or NULL
 /// @param timed_out  flag set on timeout or NULL
 ///
 /// @return  0 for failure, or number of lines contained in the match.
-static long bt_regexec_both(char_u *line, colnr_T col, proftime_T *tm, int *timed_out)
+static long bt_regexec_both(char_u *line, colnr_T startcol, proftime_T *tm, int *timed_out)
 {
   bt_regprog_T *prog;
   char_u *s;
+  colnr_T col = startcol;
   long retval = 0L;
 
   // Create "regstack" and "backpos" if they are not allocated yet.
@@ -5113,10 +5114,18 @@ theend:
           || (end->lnum == start->lnum && end->col < start->col)) {
         rex.reg_mmatch->endpos[0] = rex.reg_mmatch->startpos[0];
       }
+
+      // startpos[0] may be set by "\zs", also return the column where
+      // the whole pattern matched.
+      rex.reg_mmatch->rmm_matchcol = col;
     } else {
       if (rex.reg_match->endp[0] < rex.reg_match->startp[0]) {
         rex.reg_match->endp[0] = rex.reg_match->startp[0];
       }
+
+      // startpos[0] may be set by "\zs", also return the column where
+      // the whole pattern matched.
+      rex.reg_match->rm_matchcol = col;
     }
   }
 
diff --git a/src/nvim/regexp_defs.h b/src/nvim/regexp_defs.h
index ee32b8d13a..a3b77f295a 100644
--- a/src/nvim/regexp_defs.h
+++ b/src/nvim/regexp_defs.h
@@ -49,6 +49,8 @@ typedef struct {
   regprog_T *regprog;
   lpos_T startpos[NSUBEXP];
   lpos_T endpos[NSUBEXP];
+
+  colnr_T rmm_matchcol;  ///< match start without "\zs"
   int rmm_ic;
   colnr_T rmm_maxcol;  /// when not zero: maximum column
 } regmmatch_T;
@@ -128,6 +130,8 @@ typedef struct {
   regprog_T *regprog;
   char *startp[NSUBEXP];
   char *endp[NSUBEXP];
+
+  colnr_T rm_matchcol;  ///< match start without "\zs"
   bool rm_ic;
 } regmatch_T;
 
diff --git a/src/nvim/regexp_nfa.c b/src/nvim/regexp_nfa.c
index ed3a0f38a4..e379af16ca 100644
--- a/src/nvim/regexp_nfa.c
+++ b/src/nvim/regexp_nfa.c
@@ -7385,7 +7385,13 @@ static long nfa_regexec_both(char_u *line, colnr_T startcol, proftime_T *tm, int
     // If match_text is set it contains the full text that must match.
     // Nothing else to try. Doesn't handle combining chars well.
     if (prog->match_text != NULL && !rex.reg_icombine) {
-      return find_match_text(col, prog->regstart, prog->match_text);
+      retval = find_match_text(col, prog->regstart, prog->match_text);
+      if (REG_MULTI) {
+        rex.reg_mmatch->rmm_matchcol = col;
+      } else {
+        rex.reg_match->rm_matchcol = col;
+      }
+      return retval;
     }
   }
 
@@ -7421,10 +7427,18 @@ theend:
           || (end->lnum == start->lnum && end->col < start->col)) {
         rex.reg_mmatch->endpos[0] = rex.reg_mmatch->startpos[0];
       }
+
+      // startpos[0] may be set by "\zs", also return the column where
+      // the whole pattern matched.
+      rex.reg_mmatch->rmm_matchcol = col;
     } else {
       if (rex.reg_match->endp[0] < rex.reg_match->startp[0]) {
         rex.reg_match->endp[0] = rex.reg_match->startp[0];
       }
+
+      // startpos[0] may be set by "\zs", also return the column where
+      // the whole pattern matched.
+      rex.reg_match->rm_matchcol = col;
     }
   }