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

3 files changed, 23 insertions, 26 deletions

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;
 }