To: vim_dev@googlegroups.com Subject: Patch 8.2.4765 Fcc: outbox From: Bram Moolenaar Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit ------------ Patch 8.2.4765 Problem: Function matchfuzzy() sorts too many items. Solution: Only put matches in the array. (Yegappan Lakshmanan, closes #10208) Files: src/search.c *** ../vim-8.2.4764/src/search.c 2022-04-16 12:34:45.481217715 +0100 --- src/search.c 2022-04-16 20:38:22.925237190 +0100 *************** *** 4642,4648 **** */ static void fuzzy_match_in_list( ! list_T *items, char_u *str, int matchseq, char_u *key, --- 4642,4648 ---- */ static void fuzzy_match_in_list( ! list_T *l, char_u *str, int matchseq, char_u *key, *************** *** 4652,4697 **** long max_matches) { long len; ! fuzzyItem_T *ptrs; listitem_T *li; long i = 0; ! 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; // For all the string items in items, get the fuzzy matching score ! FOR_ALL_LIST_ITEMS(items, li) { int score; char_u *itemstr; typval_T rettv; ! 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 itemstr = li->li_tv.vval.v_string; else if (li->li_tv.v_type == VAR_DICT ! && (key != NULL || item_cb->cb_name != NULL)) { // For a dict, either use the specified key to lookup the string or // use the specified callback function to get the string. --- 4652,4689 ---- long max_matches) { long len; ! fuzzyItem_T *items; listitem_T *li; long i = 0; ! long match_count = 0; int_u matches[MAX_FUZZY_MATCHES]; ! len = list_len(l); if (len == 0) return; + if (max_matches > 0 && len > max_matches) + len = max_matches; ! items = ALLOC_CLEAR_MULT(fuzzyItem_T, len); ! if (items == NULL) return; // For all the string items in items, get the fuzzy matching score ! FOR_ALL_LIST_ITEMS(l, li) { int score; char_u *itemstr; typval_T rettv; ! if (max_matches > 0 && match_count >= max_matches) ! break; itemstr = NULL; rettv.v_type = VAR_UNKNOWN; if (li->li_tv.v_type == VAR_STRING) // list of strings itemstr = li->li_tv.vval.v_string; else if (li->li_tv.v_type == VAR_DICT ! && (key != NULL || item_cb->cb_name != NULL)) { // For a dict, either use the specified key to lookup the string or // use the specified callback function to get the string. *************** *** 4717,4724 **** if (itemstr != NULL && fuzzy_match(itemstr, str, matchseq, &score, matches, ! sizeof(matches) / sizeof(matches[0]))) { // Copy the list of matching positions in itemstr to a list, if // 'retmatchpos' is set. if (retmatchpos) --- 4709,4720 ---- if (itemstr != NULL && fuzzy_match(itemstr, str, matchseq, &score, matches, ! 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) *************** *** 4726,4733 **** int j = 0; char_u *p; ! ptrs[i].lmatchpos = list_alloc(); ! if (ptrs[i].lmatchpos == NULL) goto done; p = str; --- 4722,4729 ---- int j = 0; char_u *p; ! items[match_count].lmatchpos = list_alloc(); ! if (items[match_count].lmatchpos == NULL) goto done; p = str; *************** *** 4735,4741 **** { if (!VIM_ISWHITE(PTR2CHAR(p))) { ! if (list_append_number(ptrs[i].lmatchpos, matches[j]) == FAIL) goto done; j++; --- 4731,4737 ---- { if (!VIM_ISWHITE(PTR2CHAR(p))) { ! if (list_append_number(items[match_count].lmatchpos, matches[j]) == FAIL) goto done; j++; *************** *** 4746,4764 **** ++p; } } ! ptrs[i].score = score; ! ++found_match; } - ++i; clear_tv(&rettv); } ! if (found_match > 0) { ! list_T *l; // Sort the list by the descending order of the match score ! qsort((void *)ptrs, (size_t)len, sizeof(fuzzyItem_T), fuzzy_match_item_compare); // For matchfuzzy(), return a list of matched strings. --- 4742,4758 ---- ++p; } } ! ++match_count; } clear_tv(&rettv); } ! if (match_count > 0) { ! list_T *retlist; // Sort the list by the descending order of the match score ! qsort((void *)items, (size_t)match_count, sizeof(fuzzyItem_T), fuzzy_match_item_compare); // For matchfuzzy(), return a list of matched strings. *************** *** 4773,4789 **** li = list_find(fmatchlist, 0); if (li == NULL || li->li_tv.vval.v_list == NULL) goto done; ! l = li->li_tv.vval.v_list; } else ! l = 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) break; ! list_append_tv(l, &ptrs[i].item->li_tv); } // next copy the list of matching positions --- 4767,4783 ---- li = list_find(fmatchlist, 0); if (li == NULL || li->li_tv.vval.v_list == NULL) goto done; ! retlist = li->li_tv.vval.v_list; } else ! retlist = fmatchlist; // Copy the matching strings with a valid score to the return list ! for (i = 0; i < match_count; i++) { ! if (items[i].score == SCORE_NONE) break; ! list_append_tv(retlist, &items[i].item->li_tv); } // next copy the list of matching positions *************** *** 4792,4805 **** li = list_find(fmatchlist, -2); if (li == NULL || li->li_tv.vval.v_list == NULL) goto done; ! l = li->li_tv.vval.v_list; ! for (i = 0; i < len; i++) { ! if (ptrs[i].score == SCORE_NONE) break; ! if (ptrs[i].lmatchpos != NULL ! && list_append_list(l, ptrs[i].lmatchpos) == FAIL) goto done; } --- 4786,4800 ---- li = list_find(fmatchlist, -2); if (li == NULL || li->li_tv.vval.v_list == NULL) goto done; ! retlist = li->li_tv.vval.v_list; ! for (i = 0; i < match_count; i++) { ! if (items[i].score == SCORE_NONE) break; ! if (items[i].lmatchpos != NULL ! && list_append_list(retlist, items[i].lmatchpos) ! == FAIL) goto done; } *************** *** 4807,4825 **** li = list_find(fmatchlist, -1); if (li == NULL || li->li_tv.vval.v_list == NULL) goto done; ! l = li->li_tv.vval.v_list; ! for (i = 0; i < len; i++) { ! if (ptrs[i].score == SCORE_NONE) break; ! if (list_append_number(l, ptrs[i].score) == FAIL) goto done; } } } done: ! vim_free(ptrs); } /* --- 4802,4820 ---- li = list_find(fmatchlist, -1); if (li == NULL || li->li_tv.vval.v_list == NULL) goto done; ! retlist = li->li_tv.vval.v_list; ! for (i = 0; i < match_count; i++) { ! if (items[i].score == SCORE_NONE) break; ! if (list_append_number(retlist, items[i].score) == FAIL) goto done; } } } done: ! vim_free(items); } /* *** ../vim-8.2.4764/src/version.c 2022-04-16 20:04:26.174152095 +0100 --- src/version.c 2022-04-16 20:42:16.976813902 +0100 *************** *** 748,749 **** --- 748,751 ---- { /* Add new patch number below this line */ + /**/ + 4765, /**/ -- Often you're less important than your furniture. If you think about it, you can get fired but your furniture stays behind, gainfully employed at the company that didn't need _you_ anymore. (Scott Adams - The Dilbert principle) /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net \\\ /// \\\ \\\ sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ /// \\\ help me help AIDS victims -- http://ICCF-Holland.org ///