# HG changeset patch
# User Bram Moolenaar <Bram@vim.org>
# Date 1664456403 -7200
# Node ID 66de6909e102cb4ee1fb416366b44b3993efb8bb
# Parent  c6b5eb07032a66cfec1c989d952e89590cdbc342
patch 9.0.0622: matchaddpos() can get slow when adding many matches

Commit: https://github.com/vim/vim/commit/9f573a8df02d9f699a43d2afbd1d2841d700b9ad
Author: Bram Moolenaar <Bram@vim.org>
Date:   Thu Sep 29 13:50:08 2022 +0100

    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)

diff --git a/runtime/doc/builtin.txt b/runtime/doc/builtin.txt
--- a/runtime/doc/builtin.txt
+++ b/runtime/doc/builtin.txt
@@ -5864,7 +5864,7 @@ matchadd({group}, {pattern} [, {priority
 		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/match.c b/src/match.c
--- a/src/match.c
+++ b/src/match.c
@@ -50,19 +50,28 @@ match_add(
 	semsg(_(e_invalid_id_nr_must_be_greater_than_or_equal_to_one_1), id);
 	return -1;
     }
-    if (id != -1)
+    if (id == -1)
     {
-	cur = wp->w_match_head;
-	while (cur != NULL)
-	{
+	// 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(_(e_id_already_taken_nr), 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_namen2id(grp, (int)STRLEN(grp))) == 0)
     {
 	semsg(_(e_no_such_highlight_group_name_str), grp);
@@ -74,17 +83,6 @@ match_add(
 	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 = ALLOC_CLEAR_ONE(matchitem_T);
     if (m == NULL)
diff --git a/src/testdir/test_match.vim b/src/testdir/test_match.vim
--- a/src/testdir/test_match.vim
+++ b/src/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())
 
@@ -119,7 +119,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)
@@ -130,7 +130,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)
@@ -144,7 +144,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
@@ -252,8 +252,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/version.c b/src/version.c
--- a/src/version.c
+++ b/src/version.c
@@ -700,6 +700,8 @@ static char *(features[]) =
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    622,
+/**/
     621,
 /**/
     620,
diff --git a/src/window.c b/src/window.c
--- a/src/window.c
+++ b/src/window.c
@@ -5143,8 +5143,7 @@ win_alloc(win_T *after UNUSED, int hidde
 #endif
     unblock_autocmds();
 #ifdef FEAT_SEARCH_EXTRA
-    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
 #endif
     return new_wp;
 }