vim-patch:8.2.4760: using matchfuzzy() on a long list can take a while

Problem:    Using matchfuzzy() on a long list can take a while.
Solution:   Add a limit to the number of matches. (Yasuhiro Matsumoto,
            closes vim/vim#10189)
https://github.com/vim/vim/commit/9029a6e9931eede1d44f613687a2c01b9fe514ec

3 files changed, 43 insertions, 8 deletions

diff --git a/runtime/doc/builtin.txt b/runtime/doc/builtin.txt
index 81d7f4b83a..3e75914743 100644
--- a/runtime/doc/builtin.txt
+++ b/runtime/doc/builtin.txt
@@ -4975,7 +4975,7 @@ matchfuzzy({list}, {str} [, {dict}])			*matchfuzzy()*
 
 		If {list} is a list of dictionaries, then the optional {dict}
 		argument supports the following additional items:
-		    key		key of the item which is fuzzy matched against
+		    key		Key of the item which is fuzzy matched against
 				{str}. The value of this item should be a
 				string.
 		    text_cb	|Funcref| that will be called for every item
@@ -4983,6 +4983,8 @@ matchfuzzy({list}, {str} [, {dict}])			*matchfuzzy()*
 				This should accept a dictionary item as the
 				argument and return the text for that item to
 				use for fuzzy matching.
+		    limit	Maximum number of matches in {list} to be
+				returned.  Zero means no limit.
 
 		{str} is treated as a literal string and regular expression
 		matching is NOT supported.  The maximum supported {str} length
@@ -4995,6 +4997,9 @@ matchfuzzy({list}, {str} [, {dict}])			*matchfuzzy()*
 		empty list is returned. If length of {str} is greater than
 		256, then returns an empty list.
 
+		When {limit} is given, matchfuzzy() will find up to this
+		number of matches in {list} and return them in sorted order.
+
 		Refer to |fuzzy-matching| for more information about fuzzy
 		matching strings.
 
diff --git a/src/nvim/search.c b/src/nvim/search.c
index 4fc5ac93aa..67f0197d4b 100644
--- a/src/nvim/search.c
+++ b/src/nvim/search.c
@@ -5095,7 +5095,8 @@ static int fuzzy_match_item_compare(const void *const s1, const void *const s2)
 /// matches for each item.
 static void fuzzy_match_in_list(list_T *const items, char_u *const str, const bool matchseq,
                                 const char_u *const key, Callback *const item_cb,
-                                const bool retmatchpos, list_T *const fmatchlist)
+                                const bool retmatchpos, list_T *const fmatchlist,
+                                const long max_matches)
   FUNC_ATTR_NONNULL_ARG(2, 5, 7)
 {
   const long len = tv_list_len(items);
@@ -5103,9 +5104,10 @@ static void fuzzy_match_in_list(list_T *const items, char_u *const str, const bo
     return;
   }
 
+  // TODO(vim): when using a limit use that instead of "len"
   fuzzyItem_T *const ptrs = xcalloc(len, sizeof(fuzzyItem_T));
   long i = 0;
-  bool found_match = false;
+  long found_match = 0;
   uint32_t matches[MAX_FUZZY_MATCHES];
 
   // For all the string items in items, get the fuzzy matching score
@@ -5113,6 +5115,14 @@ static void fuzzy_match_in_list(list_T *const items, char_u *const str, const bo
     ptrs[i].idx = i;
     ptrs[i].item = li;
     ptrs[i].score = SCORE_NONE;
+
+    // TODO(vim): instead of putting all items in ptrs[] should only add
+    // matching items there.
+    if (max_matches > 0 && found_match >= max_matches) {
+      i++;
+      continue;
+    }
+
     char_u *itemstr = NULL;
     typval_T rettv;
     rettv.v_type = VAR_UNKNOWN;
@@ -5159,13 +5169,13 @@ static void fuzzy_match_in_list(list_T *const items, char_u *const str, const bo
         }
       }
       ptrs[i].score = score;
-      found_match = true;
+      found_match++;
     }
     i++;
     tv_clear(&rettv);
   });
 
-  if (found_match) {
+  if (found_match > 0) {
     // Sort the list by the descending order of the match score
     qsort(ptrs, len, sizeof(fuzzyItem_T), fuzzy_match_item_compare);
 
@@ -5239,6 +5249,7 @@ static void do_fuzzymatch(const typval_T *const argvars, typval_T *const rettv,
   Callback cb = CALLBACK_NONE;
   const char_u *key = NULL;
   bool matchseq = false;
+  long max_matches = 0;
   if (argvars[2].v_type != VAR_UNKNOWN) {
     if (argvars[2].v_type != VAR_DICT || argvars[2].vval.v_dict == NULL) {
       emsg(_(e_dictreq));
@@ -5248,8 +5259,8 @@ static void do_fuzzymatch(const typval_T *const argvars, typval_T *const rettv,
     // To search a dict, either a callback function or a key can be
     // specified.
     dict_T *const d = argvars[2].vval.v_dict;
-    const dictitem_T *const di = tv_dict_find(d, "key", -1);
-    if (di != NULL) {
+    const dictitem_T *di;
+    if ((di = tv_dict_find(d, "key", -1)) != NULL) {
       if (di->di_tv.v_type != VAR_STRING || di->di_tv.vval.v_string == NULL
           || *di->di_tv.vval.v_string == NUL) {
         semsg(_(e_invarg2), tv_get_string(&di->di_tv));
@@ -5259,7 +5270,14 @@ static void do_fuzzymatch(const typval_T *const argvars, typval_T *const rettv,
     } else if (!tv_dict_get_callback(d, "text_cb", -1, &cb)) {
       semsg(_(e_invargval), "text_cb");
       return;
+    } else if ((di = tv_dict_find(d, "limit", -1)) != NULL) {
+      if (di->di_tv.v_type != VAR_NUMBER) {
+        semsg(_(e_invarg2), tv_get_string(&di->di_tv));
+        return;
+      }
+      max_matches = (long)tv_get_number_chk(&di->di_tv, NULL);
     }
+
     if (tv_dict_find(d, "matchseq", -1) != NULL) {
       matchseq = true;
     }
@@ -5278,7 +5296,7 @@ static void do_fuzzymatch(const typval_T *const argvars, typval_T *const rettv,
   }
 
   fuzzy_match_in_list(argvars[0].vval.v_list, (char_u *)tv_get_string(&argvars[1]), matchseq, key,
-                      &cb, retmatchpos, rettv->vval.v_list);
+                      &cb, retmatchpos, rettv->vval.v_list, max_matches);
   callback_free(&cb);
 }
 
diff --git a/src/nvim/testdir/test_matchfuzzy.vim b/src/nvim/testdir/test_matchfuzzy.vim
index abcc9b40c1..d53f8b0f4d 100644
--- a/src/nvim/testdir/test_matchfuzzy.vim
+++ b/src/nvim/testdir/test_matchfuzzy.vim
@@ -245,4 +245,16 @@ func Test_matchfuzzypos_mbyte()
   call assert_equal([['xффйд'], [[2, 3, 4]], [168]], matchfuzzypos(['xффйд'], 'фйд'))
 endfunc
 
+" Test for matchfuzzy() with limit
+func Test_matchfuzzy_limit()
+  let x = ['1', '2', '3', '2']
+  call assert_equal(['2', '2'], x->matchfuzzy('2'))
+  call assert_equal(['2', '2'], x->matchfuzzy('2', #{}))
+  call assert_equal(['2', '2'], x->matchfuzzy('2', #{limit: 0}))
+  call assert_equal(['2'], x->matchfuzzy('2', #{limit: 1}))
+  call assert_equal(['2', '2'], x->matchfuzzy('2', #{limit: 2}))
+  call assert_equal(['2', '2'], x->matchfuzzy('2', #{limit: 3}))
+  call assert_fails("call matchfuzzy(x, '2', #{limit: '2'})", 'E475:')
+endfunc
+
 " vim: shiftwidth=2 sts=2 expandtab