Commit: patch 9.2.0971: "=~" and the match functions compile their pattern on every call

patch 9.2.0971: "=~" and the match functions compile their pattern on every call

Commit: https://github.com/vim/vim/commit/be1616190eb6ed00aaef4ddfb6c835019c1453bc
Author: Samuel Schlesinger <[email protected]>
Date:   Tue Aug 18 19:41:13 2026 +0000

    patch 9.2.0971: "=~" and the match functions compile their pattern on every call
    
    Problem:  "=~", match(), matchstr(), matchlist(), matchbufline(),
              matchstrlist() and split() compile their pattern on every
              call.  A script matching a list of items against one
              pattern compiles it once per item, which can dwarf the
              cost of the match itself.
    Solution: Keep the compiled program of the last pattern in a cache
              (Samuel Schlesinger).
    
    The cache owns the program only between uses: eval_regcomp() hands
    it to the caller and empties the cache, and eval_regfree() adopts
    the program the caller ends up with, so the automatic engine
    falling back to the backtracking engine, which frees the original
    program, needs no special handling and vim_regfree() is unchanged.
    The key covers the pattern, 'encoding' and 'regexpengine', sampled
    when compiling; when user code run from a nested evaluation changes
    an option in the key, or re-enters the compile/free pair, the
    program is freed instead of cached.  Patterns whose compilation
    depends on state outside the key are not cached: "~", bracket
    classes, the cursor-relative atoms \%.l, \%.c and \%.v, and a
    "\%#=" engine prefix.  'ignorecase' applies at execution time as
    before.
    
    Benchmarks (min of 3, macOS arm64, uncached to cached): filter() of
    100000 items with a plugin-sized pattern 0.211s to 0.048s; a
    generated 200-branch alternation over 10000 items 0.455s to 0.037s,
    and with 'regexpengine' 1 forcing the backtracking engine 0.851s to
    0.021s; a short inline pattern over 100000 items 0.109s to 0.061s.
    
    closes: #20941
    
    Co-Authored-By: Claude <[email protected]>
    Signed-off-by: Samuel Schlesinger <[email protected]>
    Signed-off-by: Christian Brabandt <[email protected]>

diff --git a/src/alloc.c b/src/alloc.c
index d6eb6f29c..69d484018 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -447,6 +447,7 @@ free_all_mem(void)
     free_signs();
 # endif
 # ifdef FEAT_EVAL
+    free_eval_regcomp_cache();
     set_expr_line(NULL, NULL);
 # endif
 # ifdef FEAT_DIFF
diff --git a/src/eval.c b/src/eval.c
index d5373c099..759c4acb4 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -3188,6 +3188,178 @@ set_context_for_expression(
     xp->xp_pattern = arg;
 }
 
+/*
+ * Cache with the compiled program of the last pattern used by
+ * pattern_match() and the match functions.  Script loops often evaluate the
+ * same pattern many times; reusing the program avoids compiling it for
+ * every evaluation.  The cache owns the program only between uses:
+ * eval_regcomp() hands it to the caller and empties the cache, and
+ * eval_regfree() adopts the program the caller ends up with.  Thus when
+ * executing replaced the program (the automatic engine falling back to
+ * backtracking frees the original) no freed program is left behind in the
+ * cache.
+ * Adopting the caller's program also means that after a fallback the
+ * backtracking program stays cached until the pattern or an option in the
+ * key changes; the automatic engine is not tried again for it.
+ * The cache must only be used where the pattern is compiled with
+ * RE_MAGIC + RE_STRING and 'cpoptions' made empty, as every caller here
+ * does; both functions check these conditions and fall back to plain
+ * compilation and freeing when they do not hold.
+ * eval_prog_pat and eval_prog_enc are non-NULL whenever eval_prog_cache is
+ * non-NULL.
+ */
+static regprog_T    *eval_prog_cache = NULL;
+static char_u	    *eval_prog_pat = NULL;	// pattern it was compiled for
+static char_u	    *eval_prog_enc = NULL;	// 'encoding' when compiled
+static long	    eval_prog_re;		// 'regexpengine' when compiled
+// State sampled by eval_regcomp() for the eval_regfree() call that gives the
+// program back: user code run in between, e.g. an object's string() method
+// invoked by match() on a list, can change these options, and then the
+// program must not be cached under the changed values.  eval_compile_enc is
+// only ever compared against p_enc, never dereferenced.
+static long	    eval_compile_re;
+static char_u	    *eval_compile_enc;
+static int	    eval_prog_busy = 0;	// programs eval_regcomp() handed out
+					// that were not given back yet
+static int	    eval_prog_reentered = FALSE;  // eval_regcomp() ran while
+						  // a program was handed out
+
+/*
+ * Return true when compiling "pat" depends on more state than the cache key
+ * covers: "~" is replaced with the previous substitute string, bracket
+ * classes like [:alpha:], [=a=] and [.a.] can depend on the locale, the
+ * cursor-relative atoms \%.l, \%.c and \%.v compile the current cursor
+ * position into the program, and a "\%#=" engine prefix makes vim_regcomp()
+ * report E864 for a bad value on every compilation.  The check is
+ * intentionally over-approximate, e.g. a literal "~" or "%." also matches;
+ * such a pattern is compiled every time, which is never wrong.
+ */
+    static bool
+eval_prog_volatile(char_u *pat)
+{
+    char_u *p;
+
+    if (STRNCMP(pat, "\%#=", 4) == 0)
+	return true;
+    for (p = pat; *p != NUL; ++p)
+	if (*p == '~'
+		|| (p[0] == '[' && (p[1] == ':' || p[1] == '=' || p[1] == '.'))
+		|| (p[0] == '%' && (p[1] == '.'
+			|| ((p[1] == '<' || p[1] == '>') && p[2] == '.'))))
+	    return true;
+    return false;
+}
+
+/*
+ * Compile pattern "pat" like vim_regcomp(pat, RE_MAGIC + RE_STRING) would,
+ * but reuse the cached program when it was compiled for the same pattern.
+ * Free the result with eval_regfree(), not with vim_regfree().
+ */
+    regprog_T *
+eval_regcomp(char_u *pat)
+{
+    regprog_T	*prog;
+
+    // Sample the option state the key covers, eval_regfree() checks that it
+    // did not change while the caller was using the program.
+    eval_compile_re = p_re;
+    eval_compile_enc = p_enc;
+    if (eval_prog_busy > 0)
+	// The samples above no longer describe the program already handed
+	// out: its eval_regfree() must drop it instead of caching it.
+	eval_prog_reentered = TRUE;
+
+    if (eval_prog_cache != NULL
+	    && *p_cpo == NUL
+	    && eval_prog_cache->re_flags == RE_MAGIC + RE_STRING
+	    && eval_prog_re == p_re
+	    && STRCMP(eval_prog_pat, pat) == 0
+	    && STRCMP(eval_prog_enc, p_enc) == 0)
+    {
+	prog = eval_prog_cache;
+	// The caller now owns the program, eval_regfree() adopts the
+	// program the caller ends up with.
+	eval_prog_cache = NULL;
+    }
+    else
+	prog = vim_regcomp(pat, RE_MAGIC + RE_STRING);
+    if (prog != NULL)
+	++eval_prog_busy;	// paired with the eval_regfree() call
+    return prog;
+}
+
+/*
+ * Free program "prog", obtained with eval_regcomp() for pattern "pat", by
+ * keeping it in the cache for the next use.  "pat" must be the same string
+ * the program was compiled for and must still be valid.
+ */
+    void
+eval_regfree(char_u *pat, regprog_T *prog)
+{
+    int	    reentered = eval_prog_reentered;
+
+    if (eval_prog_busy > 0 && --eval_prog_busy == 0)
+	eval_prog_reentered = FALSE;
+    if (prog == NULL)
+	return;
+    if (reentered || *p_cpo != NUL
+	    || eval_compile_re != p_re || eval_compile_enc != p_enc)
+    {
+	// 'cpoptions' is not empty, an option in the cache key changed, or
+	// another program was handed out while the caller was using this
+	// one: the samples may not describe this program, do not cache it.
+	vim_regfree(prog);
+	return;
+    }
+    if (eval_prog_pat == NULL || STRCMP(eval_prog_pat, pat) != 0
+	    || STRCMP(eval_prog_enc, p_enc) != 0)
+    {
+	char_u	*pat_copy;
+	char_u	*enc_copy;
+
+	// A cached pattern is known not to be volatile, thus the scan is
+	// only needed when installing a new key.
+	if (eval_prog_volatile(pat))
+	{
+	    // compiling depends on state the cache key does not cover
+	    vim_regfree(prog);
+	    return;
+	}
+	pat_copy = vim_strsave(pat);
+	enc_copy = vim_strsave(p_enc);
+	if (pat_copy == NULL || enc_copy == NULL)
+	{
+	    vim_free(pat_copy);
+	    vim_free(enc_copy);
+	    vim_regfree(prog);
+	    return;
+	}
+	vim_free(eval_prog_pat);
+	vim_free(eval_prog_enc);
+	eval_prog_pat = pat_copy;
+	eval_prog_enc = enc_copy;
+    }
+    // On a cache miss eval_regcomp() left the previous program in the
+    // cache, and a nested evaluation may have stored another one: keep the
+    // most recent program.
+    vim_regfree(eval_prog_cache);
+    eval_prog_cache = prog;
+    eval_prog_re = eval_compile_re;
+}
+
+#if defined(EXITFREE) || defined(PROTO)
+    void
+free_eval_regcomp_cache(void)
+{
+    vim_regfree(eval_prog_cache);
+    eval_prog_cache = NULL;
+    VIM_CLEAR(eval_prog_pat);
+    VIM_CLEAR(eval_prog_enc);
+    eval_prog_busy = 0;
+    eval_prog_reentered = FALSE;
+}
+#endif
+
 /*
  * Return TRUE if "pat" matches "text".
  * Does not use 'cpo' and always uses 'magic'.
@@ -3202,12 +3374,12 @@ pattern_match(char_u *pat, char_u *text, int ic)
     // avoid 'l' flag in 'cpoptions'
     save_cpo = p_cpo;
     p_cpo = empty_option;
-    regmatch.regprog = vim_regcomp(pat, RE_MAGIC + RE_STRING);
+    regmatch.regprog = eval_regcomp(pat);
     if (regmatch.regprog != NULL)
     {
 	regmatch.rm_ic = ic;
 	matches = vim_regexec_nl(&regmatch, text, (colnr_T)0);
-	vim_regfree(regmatch.regprog);
+	eval_regfree(pat, regmatch.regprog);
     }
     p_cpo = save_cpo;
     return matches;
diff --git a/src/evalfunc.c b/src/evalfunc.c
index 6820cd8c9..bf8f00f7a 100644
--- a/src/evalfunc.c
+++ b/src/evalfunc.c
@@ -9228,7 +9228,7 @@ find_some_match(typval_T *argvars, typval_T *rettv, matchtype_T type)
 	    goto theend;
     }
 
-    regmatch.regprog = vim_regcomp(pat, RE_MAGIC + RE_STRING);
+    regmatch.regprog = eval_regcomp(pat);
     if (regmatch.regprog != NULL)
     {
 	regmatch.rm_ic = p_ic;
@@ -9346,7 +9346,7 @@ find_some_match(typval_T *argvars, typval_T *rettv, matchtype_T type)
 	}
 	if (l != NULL)
 	    l->lv_lock = prev_lock;
-	vim_regfree(regmatch.regprog);
+	eval_regfree(pat, regmatch.regprog);
     }
 
 theend:
@@ -9520,7 +9520,7 @@ f_matchbufline(typval_T *argvars, typval_T *rettv)
     save_cpo = p_cpo;
     p_cpo = empty_option;
 
-    regmatch.regprog = vim_regcomp(pat, RE_MAGIC + RE_STRING);
+    regmatch.regprog = eval_regcomp(pat);
     if (regmatch.regprog == NULL)
 	goto theend;
     regmatch.rm_ic = p_ic;
@@ -9535,7 +9535,7 @@ f_matchbufline(typval_T *argvars, typval_T *rettv)
     }
 
 cleanup:
-    vim_regfree(regmatch.regprog);
+    eval_regfree(pat, regmatch.regprog);
 
 theend:
     p_cpo = save_cpo;
@@ -9611,7 +9611,7 @@ f_matchstrlist(typval_T *argvars, typval_T *rettv)
     save_cpo = p_cpo;
     p_cpo = empty_option;
 
-    regmatch.regprog = vim_regcomp(pat, RE_MAGIC + RE_STRING);
+    regmatch.regprog = eval_regcomp(pat);
     if (regmatch.regprog == NULL)
 	goto theend;
     regmatch.rm_ic = p_ic;
@@ -9650,7 +9650,7 @@ f_matchstrlist(typval_T *argvars, typval_T *rettv)
     }
 
 cleanup:
-    vim_regfree(regmatch.regprog);
+    eval_regfree(pat, regmatch.regprog);
 
 theend:
     p_cpo = save_cpo;
@@ -12200,7 +12200,7 @@ f_split(typval_T *argvars, typval_T *rettv)
     if (typeerr)
 	goto theend;
 
-    regmatch.regprog = vim_regcomp(pat, RE_MAGIC + RE_STRING);
+    regmatch.regprog = eval_regcomp(pat);
     if (regmatch.regprog != NULL)
     {
 	regmatch.rm_ic = FALSE;
@@ -12232,7 +12232,7 @@ f_split(typval_T *argvars, typval_T *rettv)
 	    str = regmatch.endp[0];
 	}
 
-	vim_regfree(regmatch.regprog);
+	eval_regfree(pat, regmatch.regprog);
     }
 
 theend:
diff --git a/src/proto/eval.pro b/src/proto/eval.pro
index 2a0312175..448110981 100644
--- a/src/proto/eval.pro
+++ b/src/proto/eval.pro
@@ -34,6 +34,9 @@ void skip_for_lines(void *fi_void, evalarg_T *evalarg);
 int next_for_item(void *fi_void, char_u *arg);
 void free_for_info(void *fi_void);
 void set_context_for_expression(expand_T *xp, char_u *arg, cmdidx_T cmdidx);
+regprog_T *eval_regcomp(char_u *pat);
+void eval_regfree(char_u *pat, regprog_T *prog);
+void free_eval_regcomp_cache(void);
 int pattern_match(char_u *pat, char_u *text, int ic);
 char_u *eval_next_non_blank(char_u *arg, evalarg_T *evalarg, int *getnext);
 char_u *eval_next_line(char_u *arg, evalarg_T *evalarg);
diff --git a/src/testdir/test_eval_stuff.vim b/src/testdir/test_eval_stuff.vim
index e1afbfbe2..69f9b26a6 100644
--- a/src/testdir/test_eval_stuff.vim
+++ b/src/testdir/test_eval_stuff.vim
@@ -1385,4 +1385,65 @@ func Test_clipboard_provider_recursive()
   unlet g:vim_copy_recursive
 endfunc
 
+" Test that caching the compiled pattern of "=~" and the match functions
+" does not change the semantics.
+func Test_eval_pattern_cache()
+  let save_ic = &ignorecase
+  defer execute('let &ignorecase = ' .. save_ic)
+
+  " "~" in a pattern stands for the previous substitute string, a compiled
+  " program must not be reused across a :substitute
+  new
+  call setline(1, 'one')
+  s/one/AAA/
+  call assert_true('xAAAy' =~ 'x~y')
+  call assert_false('xBBBy' =~ 'x~y')
+  call setline(1, 'AAA')
+  s/AAA/BBB/
+  call assert_true('xBBBy' =~ 'x~y')
+  call assert_false('xAAAy' =~ 'x~y')
+  bwipe!
+
+  " 'ignorecase' is applied at execution time, also with a cached program
+  set noignorecase
+  call assert_false('ABC' =~ 'abc')
+  set ignorecase
+  call assert_true('ABC' =~ 'abc')
+  call assert_true('ABC' =~ 'abc')
+  set noignorecase
+  call assert_false('ABC' =~ 'abc')
+
+  " changing 'regexpengine' compiles the pattern again
+  for re in [0, 1, 2]
+    exe 'set re=' .. re
+    call assert_true('abc123' =~ 'a\+bc\d\+')
+    call assert_false('xyz' =~ 'a\+bc\d\+')
+  endfor
+  set re&
+
+  " \%.l, \%.c and \%.v compile the current cursor position into the
+  " program, such a pattern must not be reused after the cursor moved
+  new
+  call setline(1, 'abcdef')
+  call cursor(1, 4)
+  call assert_true('abcdef' =~# '\%.cd')
+  call cursor(1, 2)
+  call assert_false('abcdef' =~# '\%.cd')
+  call assert_true('abcdef' =~# '\%.cb')
+  bwipe!
+
+  " when the automatic engine replaces the program by falling back to the
+  " backtracking engine, the replaced program is the one that is kept
+  call test_override('nfa_fail', 1)
+  defer test_override('nfa_fail', 0)
+  for i in range(3)
+    call assert_true('fallback' =~ 'fall\%(back\)\?')
+    call assert_false('nomatch' =~ 'fall\%(back\)\?')
+  endfor
+  call test_override('nfa_fail', 0)
+  for i in range(3)
+    call assert_true('fallback' =~ 'fall\%(back\)\?')
+  endfor
+endfunc
+
 " vim: shiftwidth=2 sts=2 expandtab
diff --git a/src/version.c b/src/version.c
index 921e57820..c03f5e545 100644
--- a/src/version.c
+++ b/src/version.c
@@ -763,6 +763,8 @@ static char *(features[]) =
 
 static int included_patches[] =
 {   /* Add new patch number below this line */
+/**/
+    971,
 /**/
     970,
 /**/

-- 
-- 
You received this message from the "vim_dev" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php

--- 
You received this message because you are subscribed to the Google Groups "vim_dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
To view this discussion visit https://groups.google.com/d/msgid/vim_dev/E1wwPkA-00AePd-Iw%40256bit.org.