patch 8.2.4760: using matchfuzzy() on a long list can take a whilev8.2.4760

Problem:    Using matchfuzzy() on a long list can take a while.
Solution:   Add a limit to the number of matches. (Yasuhiro Matsumoto,
            closes #10189)

4 files changed, 47 insertions, 6 deletions

diff --git a/runtime/doc/builtin.txt b/runtime/doc/builtin.txt
index f6a791d9f..e99a81302 100644
--- a/runtime/doc/builtin.txt
+++ b/runtime/doc/builtin.txt
@@ -5581,7 +5581,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
@@ -5589,6 +5589,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
@@ -5601,6 +5603,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/search.c b/src/search.c
index 470bde214..42b66671c 100644
--- a/src/search.c
+++ b/src/search.c
@@ -4648,19 +4648,21 @@ fuzzy_match_in_list(
 	char_u		*key,
 	callback_T	*item_cb,
 	int		retmatchpos,
-	list_T		*fmatchlist)
+	list_T		*fmatchlist,
+	long		max_matches)
 {
     long	len;
     fuzzyItem_T	*ptrs;
     listitem_T	*li;
     long	i = 0;
-    int		found_match = FALSE;
+    long	found_match = 0;
     int_u	matches[MAX_FUZZY_MATCHES];
 
     len = list_len(items);
     if (len == 0)
 	return;
 
+    // TODO: when using a limit use that instead of "len"
     ptrs = ALLOC_CLEAR_MULT(fuzzyItem_T, len);
     if (ptrs == NULL)
 	return;
@@ -4675,6 +4677,15 @@ fuzzy_match_in_list(
 	ptrs[i].idx = i;
 	ptrs[i].item = li;
 	ptrs[i].score = SCORE_NONE;
+
+	// TODO: instead of putting all items in ptrs[] should only add
+	// matching items there.
+	if (max_matches > 0 && found_match >= max_matches)
+	{
+	    i++;
+	    continue;
+	}
+
 	itemstr = NULL;
 	rettv.v_type = VAR_UNKNOWN;
 	if (li->li_tv.v_type == VAR_STRING)	// list of strings
@@ -4736,13 +4747,13 @@ fuzzy_match_in_list(
 		}
 	    }
 	    ptrs[i].score = score;
-	    found_match = TRUE;
+	    ++found_match;
 	}
 	++i;
 	clear_tv(&rettv);
     }
 
-    if (found_match)
+    if (found_match > 0)
     {
 	list_T		*l;
 
@@ -4822,6 +4833,7 @@ do_fuzzymatch(typval_T *argvars, typval_T *rettv, int retmatchpos)
     char_u	*key = NULL;
     int		ret;
     int		matchseq = FALSE;
+    long	max_matches = 0;
 
     if (in_vim9script()
 	    && (check_for_list_arg(argvars, 0) == FAIL
@@ -4879,6 +4891,16 @@ do_fuzzymatch(typval_T *argvars, typval_T *rettv, int retmatchpos)
 		return;
 	    }
 	}
+	else if ((di = dict_find(d, (char_u *)"limit", -1)) != NULL)
+	{
+	    if (di->di_tv.v_type != VAR_NUMBER)
+	    {
+		semsg(_(e_invalid_argument_str), tv_get_string(&di->di_tv));
+		return;
+	    }
+	    max_matches = (long)tv_get_number_chk(&di->di_tv, NULL);
+	}
+
 	if (dict_has_key(d, "matchseq"))
 	    matchseq = TRUE;
     }
@@ -4913,7 +4935,7 @@ do_fuzzymatch(typval_T *argvars, typval_T *rettv, int retmatchpos)
     }
 
     fuzzy_match_in_list(argvars[0].vval.v_list, tv_get_string(&argvars[1]),
-	    matchseq, key, &cb, retmatchpos, rettv->vval.v_list);
+	    matchseq, key, &cb, retmatchpos, rettv->vval.v_list, max_matches);
 
 done:
     free_callback(&cb);
diff --git a/src/testdir/test_matchfuzzy.vim b/src/testdir/test_matchfuzzy.vim
index ddd179652..8c0477c96 100644
--- a/src/testdir/test_matchfuzzy.vim
+++ b/src/testdir/test_matchfuzzy.vim
@@ -230,4 +230,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
diff --git a/src/version.c b/src/version.c
index 4c28b3789..1a6425138 100644
--- a/src/version.c
+++ b/src/version.c
@@ -747,6 +747,8 @@ static char *(features[]) =
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    4760,
+/**/
     4759,
 /**/
     4758,