perf(events): store autocommands in flat vectors (#23256)

Instead of nested linked lists, store autocommands in a flat, contiguous
kvec_t, with one kvec_t per event type. Previously patterns were stored
in each node of the outer linked list, so they can be matched only once
on repeating patterns. They are now reference counted and referenced in
each autocommand, and matching is skipped if the pattern repeats. Speeds
up creation and deletion, execution is not affected.

Co-authored-by: ii14 <ii14@users.noreply.github.com>

2 files changed, 59 insertions, 0 deletions

diff --git a/test/functional/autocmd/autocmd_spec.lua b/test/functional/autocmd/autocmd_spec.lua
index fb5bab445c..82c7f9502f 100644
--- a/test/functional/autocmd/autocmd_spec.lua
+++ b/test/functional/autocmd/autocmd_spec.lua
@@ -611,4 +611,22 @@ describe('autocmd', function()
       eq(4, #meths.get_autocmds { event = "BufReadCmd", group = "TestingPatterns" })
     end)
   end)
+
+  it('no use-after-free when adding autocommands from a callback', function()
+    exec_lua [[
+      vim.cmd "autocmd! TabNew"
+      vim.g.count = 0
+      vim.api.nvim_create_autocmd('TabNew', {
+        callback = function()
+          vim.g.count = vim.g.count + 1
+          for _ = 1, 100 do
+            vim.cmd "autocmd TabNew * let g:count += 1"
+          end
+          return true
+        end,
+      })
+      vim.cmd "tabnew"
+    ]]
+    eq(1, eval('g:count'))  -- Added autocommands should not be executed
+  end)
 end)
diff --git a/test/functional/autocmd/show_spec.lua b/test/functional/autocmd/show_spec.lua
index 505bed834b..9e0a5b819a 100644
--- a/test/functional/autocmd/show_spec.lua
+++ b/test/functional/autocmd/show_spec.lua
@@ -180,4 +180,45 @@ describe(":autocmd", function()
       test_3  User
           B         echo "B3"]]), funcs.execute('autocmd test_3 * B'))
   end)
+
+  it('should skip consecutive patterns', function()
+    exec([[
+      autocmd! BufEnter
+      augroup test_1
+        autocmd BufEnter A echo 'A'
+        autocmd BufEnter A echo 'B'
+        autocmd BufEnter A echo 'C'
+        autocmd BufEnter B echo 'D'
+        autocmd BufEnter B echo 'E'
+        autocmd BufEnter B echo 'F'
+      augroup END
+      augroup test_2
+        autocmd BufEnter C echo 'A'
+        autocmd BufEnter C echo 'B'
+        autocmd BufEnter C echo 'C'
+        autocmd BufEnter D echo 'D'
+        autocmd BufEnter D echo 'E'
+        autocmd BufEnter D echo 'F'
+      augroup END
+
+      let g:output = execute('autocmd BufEnter')
+    ]])
+    eq(dedent([[
+
+      --- Autocommands ---
+      test_1  BufEnter
+          A         echo 'A'
+                    echo 'B'
+                    echo 'C'
+          B         echo 'D'
+                    echo 'E'
+                    echo 'F'
+      test_2  BufEnter
+          C         echo 'A'
+                    echo 'B'
+                    echo 'C'
+          D         echo 'D'
+                    echo 'E'
+                    echo 'F']]), eval('g:output'))
+  end)
 end)