From e6974114fb27a0076a6c887040e96de4a9dd509d Mon Sep 17 00:00:00 2001 From: zeertzjq Date: Mon, 25 Apr 2022 08:02:52 +0800 Subject: 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 --- runtime/doc/builtin.txt | 7 ++++++- src/nvim/search.c | 32 +++++++++++++++++++++++++------- src/nvim/testdir/test_matchfuzzy.vim | 12 ++++++++++++ 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 -- cgit From 13e54f713034e1a38eaf613d11b43ea8c42ca7df Mon Sep 17 00:00:00 2001 From: zeertzjq Date: Mon, 25 Apr 2022 08:15:00 +0800 Subject: vim-patch:8.2.4765: function matchfuzzy() sorts too many items Problem: Function matchfuzzy() sorts too many items. Solution: Only put matches in the array. (Yegappan Lakshmanan, closes vim/vim#10208) https://github.com/vim/vim/commit/047a7019b293918343998ccbdfabd48c771f5eef --- src/nvim/search.c | 75 ++++++++++++++++++++++++++----------------------------- 1 file changed, 36 insertions(+), 39 deletions(-) diff --git a/src/nvim/search.c b/src/nvim/search.c index 67f0197d4b..48df289831 100644 --- a/src/nvim/search.c +++ b/src/nvim/search.c @@ -5093,34 +5093,28 @@ static int fuzzy_match_item_compare(const void *const s1, const void *const s2) /// for each item or use 'item_cb' Funcref function to get the string. /// If 'retmatchpos' is true, then return a list of positions where 'str' /// matches for each item. -static void fuzzy_match_in_list(list_T *const items, char_u *const str, const bool matchseq, +static void fuzzy_match_in_list(list_T *const l, char_u *const str, const bool matchseq, const char_u *const key, Callback *const item_cb, 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); + long len = tv_list_len(l); if (len == 0) { return; } + if (max_matches > 0 && len > max_matches) { + len = max_matches; + } - // TODO(vim): when using a limit use that instead of "len" - fuzzyItem_T *const ptrs = xcalloc(len, sizeof(fuzzyItem_T)); - long i = 0; - long found_match = 0; + fuzzyItem_T *const items = xcalloc(len, sizeof(fuzzyItem_T)); + long match_count = 0; uint32_t matches[MAX_FUZZY_MATCHES]; // For all the string items in items, get the fuzzy matching score - TV_LIST_ITER(items, li, { - 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; + TV_LIST_ITER(l, li, { + if (max_matches > 0 && match_count >= max_matches) { + break; } char_u *itemstr = NULL; @@ -5153,31 +5147,33 @@ static void fuzzy_match_in_list(list_T *const items, char_u *const str, const bo int score; if (itemstr != NULL && fuzzy_match(itemstr, str, matchseq, &score, matches, - sizeof(matches) / sizeof(matches[0]))) { + MAX_FUZZY_MATCHES)) { + items[match_count].idx = match_count; + items[match_count].item = li; + items[match_count].score = score; + // Copy the list of matching positions in itemstr to a list, if // 'retmatchpos' is set. if (retmatchpos) { - ptrs[i].lmatchpos = tv_list_alloc(kListLenMayKnow); + items[match_count].lmatchpos = tv_list_alloc(kListLenMayKnow); int j = 0; const char_u *p = str; while (*p != NUL) { if (!ascii_iswhite(utf_ptr2char(p))) { - tv_list_append_number(ptrs[i].lmatchpos, matches[j]); + tv_list_append_number(items[match_count].lmatchpos, matches[j]); j++; } MB_PTR_ADV(p); } } - ptrs[i].score = score; - found_match++; + match_count++; } - i++; tv_clear(&rettv); }); - if (found_match > 0) { + if (match_count > 0) { // Sort the list by the descending order of the match score - qsort(ptrs, len, sizeof(fuzzyItem_T), fuzzy_match_item_compare); + qsort(items, match_count, sizeof(fuzzyItem_T), fuzzy_match_item_compare); // For matchfuzzy(), return a list of matched strings. // ['str1', 'str2', 'str3'] @@ -5186,48 +5182,49 @@ static void fuzzy_match_in_list(list_T *const items, char_u *const str, const bo // is a list of lists where each list item is a list of matched // character positions. The third item is a list of matching scores. // [['str1', 'str2', 'str3'], [[1, 3], [1, 3], [1, 3]]] - list_T *l; + list_T *retlist; if (retmatchpos) { const listitem_T *const li = tv_list_find(fmatchlist, 0); assert(li != NULL && TV_LIST_ITEM_TV(li)->vval.v_list != NULL); - l = TV_LIST_ITEM_TV(li)->vval.v_list; + retlist = TV_LIST_ITEM_TV(li)->vval.v_list; } else { - l = fmatchlist; + retlist = fmatchlist; } // Copy the matching strings with a valid score to the return list - for (i = 0; i < len; i++) { - if (ptrs[i].score == SCORE_NONE) { + for (long i = 0; i < match_count; i++) { + if (items[i].score == SCORE_NONE) { break; } - tv_list_append_tv(l, TV_LIST_ITEM_TV(ptrs[i].item)); + tv_list_append_tv(retlist, TV_LIST_ITEM_TV(items[i].item)); } // next copy the list of matching positions if (retmatchpos) { const listitem_T *li = tv_list_find(fmatchlist, -2); assert(li != NULL && TV_LIST_ITEM_TV(li)->vval.v_list != NULL); - l = TV_LIST_ITEM_TV(li)->vval.v_list; - for (i = 0; i < len; i++) { - if (ptrs[i].score == SCORE_NONE) { + retlist = TV_LIST_ITEM_TV(li)->vval.v_list; + + for (long i = 0; i < match_count; i++) { + if (items[i].score == SCORE_NONE) { break; } - tv_list_append_list(l, ptrs[i].lmatchpos); + tv_list_append_list(retlist, items[i].lmatchpos); } // copy the matching scores li = tv_list_find(fmatchlist, -1); assert(li != NULL && TV_LIST_ITEM_TV(li)->vval.v_list != NULL); - l = TV_LIST_ITEM_TV(li)->vval.v_list; - for (i = 0; i < len; i++) { - if (ptrs[i].score == SCORE_NONE) { + retlist = TV_LIST_ITEM_TV(li)->vval.v_list; + for (long i = 0; i < match_count; i++) { + if (items[i].score == SCORE_NONE) { break; } - tv_list_append_number(l, ptrs[i].score); + tv_list_append_number(retlist, items[i].score); } } } - xfree(ptrs); + xfree(items); } /// Do fuzzy matching. Returns the list of matched strings in 'rettv'. -- cgit