vim-patch:9.0.0622: matchaddpos() can get slow when adding many matches

Problem:    matchaddpos() can get slow when adding many matches.
Solution:   Update the next available match ID when manually picking an ID and
            remove check if the available ID can be used. (idea by Rick Howe)
https://github.com/vim/vim/commit/9f573a8df02d9f699a43d2afbd1d2841d700b9ad

5 files changed, 25 insertions, 126 deletions

diff --git a/runtime/doc/builtin.txt b/runtime/doc/builtin.txt
index ba345bf03c..2f44a41699 100644
--- a/runtime/doc/builtin.txt
+++ b/runtime/doc/builtin.txt
@@ -5010,7 +5010,7 @@ matchadd({group}, {pattern} [, {priority} [, {id} [, {dict}]]])
 		respectively.  3 is reserved for use by the |matchparen|
 		plugin.
 		If the {id} argument is not specified or -1, |matchadd()|
-		automatically chooses a free ID.
+		automatically chooses a free ID, which is at least 1000.
 
 		The optional {dict} argument allows for further custom
 		values. Currently this is used to specify a match specific
diff --git a/src/nvim/match.c b/src/nvim/match.c
index e06643d998..b422dc0ba8 100644
--- a/src/nvim/match.c
+++ b/src/nvim/match.c
@@ -58,16 +58,26 @@ static int match_add(win_T *wp, const char *const grp, const char *const pat, in
           (int64_t)id);
     return -1;
   }
-  if (id != -1) {
-    cur = wp->w_match_head;
-    while (cur != NULL) {
+  if (id == -1) {
+    // use the next available match ID
+    id = wp->w_next_match_id++;
+  } else {
+    // check the given ID is not already in use
+    for (cur = wp->w_match_head; cur != NULL; cur = cur->mit_next) {
       if (cur->mit_id == id) {
         semsg(_("E801: ID already taken: %" PRId64), (int64_t)id);
         return -1;
       }
-      cur = cur->mit_next;
+    }
+
+    // Make sure the next match ID is always higher than the highest
+    // manually selected ID.  Add some extra in case a few more IDs are
+    // added soon.
+    if (wp->w_next_match_id < id + 100) {
+      wp->w_next_match_id = id + 100;
     }
   }
+
   if ((hlg_id = syn_check_group(grp, strlen(grp))) == 0) {
     return -1;
   }
@@ -76,18 +86,6 @@ static int match_add(win_T *wp, const char *const grp, const char *const pat, in
     return -1;
   }
 
-  // Find available match ID.
-  while (id == -1) {
-    cur = wp->w_match_head;
-    while (cur != NULL && cur->mit_id != wp->w_next_match_id) {
-      cur = cur->mit_next;
-    }
-    if (cur == NULL) {
-      id = wp->w_next_match_id;
-    }
-    wp->w_next_match_id++;
-  }
-
   // Build new match.
   m = xcalloc(1, sizeof(matchitem_T));
   if (pos_list != NULL) {
diff --git a/src/nvim/testdir/test_match.vim b/src/nvim/testdir/test_match.vim
index 784c966a5d..4f22e54563 100644
--- a/src/nvim/testdir/test_match.vim
+++ b/src/nvim/testdir/test_match.vim
@@ -36,8 +36,8 @@ function Test_match()
   let m1 = matchadd("MyGroup1", "TODO")
   let m2 = matchadd("MyGroup2", "FIXME", 42)
   let m3 = matchadd("MyGroup3", "XXX", 60, 17)
-  let ans = [{'group': 'MyGroup1', 'pattern': 'TODO', 'priority': 10, 'id': 4},
-        \    {'group': 'MyGroup2', 'pattern': 'FIXME', 'priority': 42, 'id': 5},
+  let ans = [{'group': 'MyGroup1', 'pattern': 'TODO', 'priority': 10, 'id': 1000},
+        \    {'group': 'MyGroup2', 'pattern': 'FIXME', 'priority': 42, 'id': 1001},
         \    {'group': 'MyGroup3', 'pattern': 'XXX', 'priority': 60, 'id': 17}]
   call assert_equal(ans, getmatches())
 
@@ -118,7 +118,7 @@ function Test_match()
   call clearmatches()
 
   call setline(1, 'abcdΣabcdef')
-  eval "MyGroup1"->matchaddpos([[1, 4, 2], [1, 9, 2]])
+  eval "MyGroup1"->matchaddpos([[1, 4, 2], [1, 9, 2]], 10, 42)
   1
   redraw!
   let v1 = screenattr(1, 1)
@@ -129,7 +129,7 @@ function Test_match()
   let v8 = screenattr(1, 8)
   let v9 = screenattr(1, 9)
   let v10 = screenattr(1, 10)
-  call assert_equal([{'group': 'MyGroup1', 'id': 11, 'priority': 10, 'pos1': [1, 4, 2], 'pos2': [1, 9, 2]}], getmatches())
+  call assert_equal([{'group': 'MyGroup1', 'id': 42, 'priority': 10, 'pos1': [1, 4, 2], 'pos2': [1, 9, 2]}], getmatches())
   call assert_notequal(v1, v4)
   call assert_equal(v5, v4)
   call assert_equal(v6, v1)
@@ -143,7 +143,7 @@ function Test_match()
   let m=getmatches()
   call clearmatches()
   call setmatches(m)
-  call assert_equal([{'group': 'MyGroup1', 'id': 11, 'priority': 10, 'pos1': [1, 4, 2], 'pos2': [1,9, 2]}, {'group': 'MyGroup1', 'pattern': '\%2lmatchadd', 'priority': 10, 'id': 12}], getmatches())
+  call assert_equal([{'group': 'MyGroup1', 'id': 42, 'priority': 10, 'pos1': [1, 4, 2], 'pos2': [1,9, 2]}, {'group': 'MyGroup1', 'pattern': '\%2lmatchadd', 'priority': 10, 'id': 1106}], getmatches())
 
   highlight MyGroup1 NONE
   highlight MyGroup2 NONE
@@ -161,7 +161,7 @@ func Test_matchadd_error()
   call clearmatches()
   " Nvim: not an error anymore:
   call matchadd('GroupDoesNotExist', 'X')
-  call assert_equal([{'group': 'GroupDoesNotExist', 'pattern': 'X', 'priority': 10, 'id': 13}], getmatches())
+  call assert_equal([{'group': 'GroupDoesNotExist', 'pattern': 'X', 'priority': 10, 'id': 1206}], getmatches())
   call assert_fails("call matchadd('Search', '\\(')", 'E475:')
   call assert_fails("call matchadd('Search', 'XXX', 1, 123, 1)", 'E715:')
   call assert_fails("call matchadd('Error', 'XXX', 1, 3)", 'E798:')
@@ -253,8 +253,8 @@ func Test_matchaddpos_otherwin()
 
   let savematches = getmatches(winid)
   let expect = [
-        \ {'group': 'Search', 'pattern': '4', 'priority': 10, 'id': 4},
-        \ {'group': 'Error', 'id': 5, 'priority': 10, 'pos1': [1, 2, 1], 'pos2': [2, 2, 1]},
+        \ {'group': 'Search', 'pattern': '4', 'priority': 10, 'id': 1000},
+        \ {'group': 'Error', 'id': 1001, 'priority': 10, 'pos1': [1, 2, 1], 'pos2': [2, 2, 1]},
         \]
   call assert_equal(expect, savematches)
 
diff --git a/src/nvim/window.c b/src/nvim/window.c
index adcf9cdd56..c3806e10ff 100644
--- a/src/nvim/window.c
+++ b/src/nvim/window.c
@@ -4981,8 +4981,7 @@ static win_T *win_alloc(win_T *after, bool hidden)
 
   foldInitWin(new_wp);
   unblock_autocmds();
-  new_wp->w_match_head = NULL;
-  new_wp->w_next_match_id = 4;
+  new_wp->w_next_match_id = 1000;  // up to 1000 can be picked by the user
   return new_wp;
 }
 
diff --git a/test/functional/legacy/063_match_and_matchadd_spec.lua b/test/functional/legacy/063_match_and_matchadd_spec.lua
index d164d9c02f..235a826640 100644
--- a/test/functional/legacy/063_match_and_matchadd_spec.lua
+++ b/test/functional/legacy/063_match_and_matchadd_spec.lua
@@ -3,10 +3,8 @@
 local helpers = require('test.functional.helpers')(after_each)
 local Screen = require('test.functional.ui.screen')
 
-local eval, clear, command = helpers.eval, helpers.clear, helpers.command
-local eq, neq = helpers.eq, helpers.neq
+local clear, command = helpers.clear, helpers.command
 local insert = helpers.insert
-local pcall_err = helpers.pcall_err
 
 describe('063: Test for ":match", "matchadd()" and related functions', function()
   setup(clear)
@@ -19,105 +17,9 @@ describe('063: Test for ":match", "matchadd()" and related functions', function(
       [1] = {background = Screen.colors.Red},
     })
 
-    -- Check that "matcharg()" returns the correct group and pattern if a match
-    -- is defined.
     command("highlight MyGroup1 term=bold ctermbg=red guibg=red")
     command("highlight MyGroup2 term=italic ctermbg=green guibg=green")
     command("highlight MyGroup3 term=underline ctermbg=blue guibg=blue")
-    command("match MyGroup1 /TODO/")
-    command("2match MyGroup2 /FIXME/")
-    command("3match MyGroup3 /XXX/")
-    eq({'MyGroup1', 'TODO'}, eval('matcharg(1)'))
-    eq({'MyGroup2', 'FIXME'}, eval('matcharg(2)'))
-    eq({'MyGroup3', 'XXX'}, eval('matcharg(3)'))
-
-    -- Check that "matcharg()" returns an empty list if the argument is not 1,
-    -- 2 or 3 (only 0 and 4 are tested).
-    eq({}, eval('matcharg(0)'))
-    eq({}, eval('matcharg(4)'))
-
-    -- Check that "matcharg()" returns ['', ''] if a match is not defined.
-    command("match")
-    command("2match")
-    command("3match")
-    eq({'', ''}, eval('matcharg(1)'))
-    eq({'', ''}, eval('matcharg(2)'))
-    eq({'', ''}, eval('matcharg(3)'))
-
-    -- Check that "matchadd()" and "getmatches()" agree on added matches and
-    -- that default values apply.
-    command("let m1 = matchadd('MyGroup1', 'TODO')")
-    command("let m2 = matchadd('MyGroup2', 'FIXME', 42)")
-    command("let m3 = matchadd('MyGroup3', 'XXX', 60, 17)")
-    eq({{group = 'MyGroup1', pattern = 'TODO', priority = 10, id = 4},
-        {group = 'MyGroup2', pattern = 'FIXME', priority = 42, id = 5},
-        {group = 'MyGroup3', pattern = 'XXX', priority = 60, id = 17}},
-      eval('getmatches()'))
-
-    -- Check that "matchdelete()" deletes the matches defined in the previous
-    -- test correctly.
-    command("call matchdelete(m1)")
-    command("call matchdelete(m2)")
-    command("call matchdelete(m3)")
-    eq({}, eval('getmatches()'))
-
-    --- Check that "matchdelete()" returns 0 if successful and otherwise -1.
-    command("let m = matchadd('MyGroup1', 'TODO')")
-    eq(0, eval('matchdelete(m)'))
-
-    -- matchdelete throws error and returns -1 on failure
-    neq(true, pcall(function() eval('matchdelete(42)') end))
-    eq('Vim(let):E803: ID not found: 42', pcall_err(command, 'let r2 = matchdelete(42)'))
-
-    -- Check that "clearmatches()" clears all matches defined by ":match" and
-    -- "matchadd()".
-    command("let m1 = matchadd('MyGroup1', 'TODO')")
-    command("let m2 = matchadd('MyGroup2', 'FIXME', 42)")
-    command("let m3 = matchadd('MyGroup3', 'XXX', 60, 17)")
-    command("match MyGroup1 /COFFEE/")
-    command("2match MyGroup2 /HUMPPA/")
-    command("3match MyGroup3 /VIM/")
-    command("call clearmatches()")
-    eq({}, eval('getmatches()'))
-
-    -- Check that "setmatches()" restores a list of matches saved by
-    -- "getmatches()" without changes. (Matches with equal priority must also
-    -- remain in the same order.)
-    command("let m1 = matchadd('MyGroup1', 'TODO')")
-    command("let m2 = matchadd('MyGroup2', 'FIXME', 42)")
-    command("let m3 = matchadd('MyGroup3', 'XXX', 60, 17)")
-    command("match MyGroup1 /COFFEE/")
-    command("2match MyGroup2 /HUMPPA/")
-    command("3match MyGroup3 /VIM/")
-    command("let ml = getmatches()")
-    local ml = eval("ml")
-    command("call clearmatches()")
-    command("call setmatches(ml)")
-    eq(ml, eval('getmatches()'))
-
-    -- Check that "setmatches()" can correctly restore the matches from matchaddpos()
-    command("call clearmatches()")
-    command("call setmatches(ml)")
-    eq(ml, eval('getmatches()'))
-
-    -- Check that "setmatches()" will not add two matches with the same ID. The
-    -- expected behaviour (for now) is to add the first match but not the
-    -- second and to return -1.
-    eq('Vim(let):E801: ID already taken: 1',
-       pcall_err(command, "let r1 = setmatches([{'group': 'MyGroup1', 'pattern': 'TODO', 'priority': 10, 'id': 1}, {'group': 'MyGroup2', 'pattern': 'FIXME', 'priority': 10, 'id': 1}])"))
-    eq({{group = 'MyGroup1', pattern = 'TODO', priority = 10, id = 1}}, eval('getmatches()'))
-
-    -- Check that "setmatches()" returns 0 if successful and otherwise -1.
-    -- (A range of valid and invalid input values are tried out to generate the
-    -- return values.)
-    eq(0,eval("setmatches([])"))
-    eq(0,eval("setmatches([{'group': 'MyGroup1', 'pattern': 'TODO', 'priority': 10, 'id': 1}])"))
-    command("call clearmatches()")
-    eq('Vim(let):E714: List required', pcall_err(command, 'let rf1 = setmatches(0)'))
-    eq('Vim(let):E474: List item 0 is either not a dictionary or an empty one',
-       pcall_err(command, 'let rf2 = setmatches([0])'))
-    eq('Vim(let):E474: List item 0 is missing one of the required keys',
-       pcall_err(command, "let rf3 = setmatches([{'wrong key': 'wrong value'}])"))
 
     -- Check that "matchaddpos()" positions matches correctly
     insert('abcdefghijklmnopq')