Mercurial > vim

comparison src/search.c @ 28481:3eac1299015a v8.2.4765

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
patch 8.2.4765: function matchfuzzy() sorts too many items Commit: https://github.com/vim/vim/commit/047a7019b293918343998ccbdfabd48c771f5eef Author: Yegappan Lakshmanan <yegappan@yahoo.com> Date: Sat Apr 16 20:42:40 2022 +0100 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 #10208)
author Bram Moolenaar <Bram@vim.org>
date Sat, 16 Apr 2022 21:45:02 +0200
parents 2ade724b3f45
children d770568e6c98
comparison
equal deleted inserted replaced
28480:a08f13ce2bd0 28481:3eac1299015a
4640 * If 'retmatchpos' is TRUE, then return a list of positions where 'str' 4640 * If 'retmatchpos' is TRUE, then return a list of positions where 'str'
4641 * matches for each item. 4641 * matches for each item.
4642 */ 4642 */
4643 static void 4643 static void
4644 fuzzy_match_in_list( 4644 fuzzy_match_in_list(
4645 list_T *items, 4645 list_T *l,
4646 char_u *str, 4646 char_u *str,
4647 int matchseq, 4647 int matchseq,
4648 char_u *key, 4648 char_u *key,
4649 callback_T *item_cb, 4649 callback_T *item_cb,
4650 int retmatchpos, 4650 int retmatchpos,
4651 list_T *fmatchlist, 4651 list_T *fmatchlist,
4652 long max_matches) 4652 long max_matches)
4653 { 4653 {
4654 long len; 4654 long len;
4655 fuzzyItem_T *ptrs; 4655 fuzzyItem_T *items;
4656 listitem_T *li; 4656 listitem_T *li;
4657 long i = 0; 4657 long i = 0;
4658 long found_match = 0; 4658 long match_count = 0;
4659 int_u matches[MAX_FUZZY_MATCHES]; 4659 int_u matches[MAX_FUZZY_MATCHES];
4660 4660
4661 len = list_len(items); 4661 len = list_len(l);
4662 if (len == 0) 4662 if (len == 0)
4663 return; 4663 return;
4664 4664 if (max_matches > 0 && len > max_matches)
4665 // TODO: when using a limit use that instead of "len" 4665 len = max_matches;
4666 ptrs = ALLOC_CLEAR_MULT(fuzzyItem_T, len); 4666
4667 if (ptrs == NULL) 4667 items = ALLOC_CLEAR_MULT(fuzzyItem_T, len);
4668 if (items == NULL)
4668 return; 4669 return;
4669 4670
4670 // For all the string items in items, get the fuzzy matching score 4671 // For all the string items in items, get the fuzzy matching score
4671 FOR_ALL_LIST_ITEMS(items, li) 4672 FOR_ALL_LIST_ITEMS(l, li)
4672 { 4673 {
4673 int score; 4674 int score;
4674 char_u *itemstr; 4675 char_u *itemstr;
4675 typval_T rettv; 4676 typval_T rettv;
4676 4677
4677 ptrs[i].idx = i; 4678 if (max_matches > 0 && match_count >= max_matches)
4678 ptrs[i].item = li; 4679 break;
4679 ptrs[i].score = SCORE_NONE;
4680
4681 // TODO: instead of putting all items in ptrs[] should only add
4682 // matching items there.
4683 if (max_matches > 0 && found_match >= max_matches)
4684 {
4685 i++;
4686 continue;
4687 }
4688 4680
4689 itemstr = NULL; 4681 itemstr = NULL;
4690 rettv.v_type = VAR_UNKNOWN; 4682 rettv.v_type = VAR_UNKNOWN;
4691 if (li->li_tv.v_type == VAR_STRING) // list of strings 4683 if (li->li_tv.v_type == VAR_STRING) // list of strings
4692 itemstr = li->li_tv.vval.v_string; 4684 itemstr = li->li_tv.vval.v_string;
4693 else if (li->li_tv.v_type == VAR_DICT 4685 else if (li->li_tv.v_type == VAR_DICT
4694 && (key != NULL || item_cb->cb_name != NULL)) 4686 && (key != NULL || item_cb->cb_name != NULL))
4695 { 4687 {
4696 // For a dict, either use the specified key to lookup the string or 4688 // For a dict, either use the specified key to lookup the string or
4697 // use the specified callback function to get the string. 4689 // use the specified callback function to get the string.
4698 if (key != NULL) 4690 if (key != NULL)
4699 itemstr = dict_get_string(li->li_tv.vval.v_dict, key, FALSE); 4691 itemstr = dict_get_string(li->li_tv.vval.v_dict, key, FALSE);
4715 } 4707 }
4716 } 4708 }
4717 4709
4718 if (itemstr != NULL 4710 if (itemstr != NULL
4719 && fuzzy_match(itemstr, str, matchseq, &score, matches, 4711 && fuzzy_match(itemstr, str, matchseq, &score, matches,
4720 sizeof(matches) / sizeof(matches[0]))) 4712 MAX_FUZZY_MATCHES))
4721 { 4713 {
4714 items[match_count].idx = match_count;
4715 items[match_count].item = li;
4716 items[match_count].score = score;
4717
4722 // Copy the list of matching positions in itemstr to a list, if 4718 // Copy the list of matching positions in itemstr to a list, if
4723 // 'retmatchpos' is set. 4719 // 'retmatchpos' is set.
4724 if (retmatchpos) 4720 if (retmatchpos)
4725 { 4721 {
4726 int j = 0; 4722 int j = 0;
4727 char_u *p; 4723 char_u *p;
4728 4724
4729 ptrs[i].lmatchpos = list_alloc(); 4725 items[match_count].lmatchpos = list_alloc();
4730 if (ptrs[i].lmatchpos == NULL) 4726 if (items[match_count].lmatchpos == NULL)
4731 goto done; 4727 goto done;
4732 4728
4733 p = str; 4729 p = str;
4734 while (*p != NUL) 4730 while (*p != NUL)
4735 { 4731 {
4736 if (!VIM_ISWHITE(PTR2CHAR(p))) 4732 if (!VIM_ISWHITE(PTR2CHAR(p)))
4737 { 4733 {
4738 if (list_append_number(ptrs[i].lmatchpos, 4734 if (list_append_number(items[match_count].lmatchpos,
4739 matches[j]) == FAIL) 4735 matches[j]) == FAIL)
4740 goto done; 4736 goto done;
4741 j++; 4737 j++;
4742 } 4738 }
4743 if (has_mbyte) 4739 if (has_mbyte)
4744 MB_PTR_ADV(p); 4740 MB_PTR_ADV(p);
4745 else 4741 else
4746 ++p; 4742 ++p;
4747 } 4743 }
4748 } 4744 }
4749 ptrs[i].score = score; 4745 ++match_count;
4750 ++found_match; 4746 }
4751 }
4752 ++i;
4753 clear_tv(&rettv); 4747 clear_tv(&rettv);
4754 } 4748 }
4755 4749
4756 if (found_match > 0) 4750 if (match_count > 0)
4757 { 4751 {
4758 list_T *l; 4752 list_T *retlist;
4759 4753
4760 // Sort the list by the descending order of the match score 4754 // Sort the list by the descending order of the match score
4761 qsort((void *)ptrs, (size_t)len, sizeof(fuzzyItem_T), 4755 qsort((void *)items, (size_t)match_count, sizeof(fuzzyItem_T),
4762 fuzzy_match_item_compare); 4756 fuzzy_match_item_compare);
4763 4757
4764 // For matchfuzzy(), return a list of matched strings. 4758 // For matchfuzzy(), return a list of matched strings.
4765 // ['str1', 'str2', 'str3'] 4759 // ['str1', 'str2', 'str3']
4766 // For matchfuzzypos(), return a list with three items. 4760 // For matchfuzzypos(), return a list with three items.
4771 if (retmatchpos) 4765 if (retmatchpos)
4772 { 4766 {
4773 li = list_find(fmatchlist, 0); 4767 li = list_find(fmatchlist, 0);
4774 if (li == NULL || li->li_tv.vval.v_list == NULL) 4768 if (li == NULL || li->li_tv.vval.v_list == NULL)
4775 goto done; 4769 goto done;
4776 l = li->li_tv.vval.v_list; 4770 retlist = li->li_tv.vval.v_list;
4777 } 4771 }
4778 else 4772 else
4779 l = fmatchlist; 4773 retlist = fmatchlist;
4780 4774
4781 // Copy the matching strings with a valid score to the return list 4775 // Copy the matching strings with a valid score to the return list
4782 for (i = 0; i < len; i++) 4776 for (i = 0; i < match_count; i++)
4783 { 4777 {
4784 if (ptrs[i].score == SCORE_NONE) 4778 if (items[i].score == SCORE_NONE)
4785 break; 4779 break;
4786 list_append_tv(l, &ptrs[i].item->li_tv); 4780 list_append_tv(retlist, &items[i].item->li_tv);
4787 } 4781 }
4788 4782
4789 // next copy the list of matching positions 4783 // next copy the list of matching positions
4790 if (retmatchpos) 4784 if (retmatchpos)
4791 { 4785 {
4792 li = list_find(fmatchlist, -2); 4786 li = list_find(fmatchlist, -2);
4793 if (li == NULL || li->li_tv.vval.v_list == NULL) 4787 if (li == NULL || li->li_tv.vval.v_list == NULL)
4794 goto done; 4788 goto done;
4795 l = li->li_tv.vval.v_list; 4789 retlist = li->li_tv.vval.v_list;
4796 4790
4797 for (i = 0; i < len; i++) 4791 for (i = 0; i < match_count; i++)
4798 { 4792 {
4799 if (ptrs[i].score == SCORE_NONE) 4793 if (items[i].score == SCORE_NONE)
4800 break; 4794 break;
4801 if (ptrs[i].lmatchpos != NULL 4795 if (items[i].lmatchpos != NULL
4802 && list_append_list(l, ptrs[i].lmatchpos) == FAIL) 4796 && list_append_list(retlist, items[i].lmatchpos)
4797 == FAIL)
4803 goto done; 4798 goto done;
4804 } 4799 }
4805 4800
4806 // copy the matching scores 4801 // copy the matching scores
4807 li = list_find(fmatchlist, -1); 4802 li = list_find(fmatchlist, -1);
4808 if (li == NULL || li->li_tv.vval.v_list == NULL) 4803 if (li == NULL || li->li_tv.vval.v_list == NULL)
4809 goto done; 4804 goto done;
4810 l = li->li_tv.vval.v_list; 4805 retlist = li->li_tv.vval.v_list;
4811 for (i = 0; i < len; i++) 4806 for (i = 0; i < match_count; i++)
4812 { 4807 {
4813 if (ptrs[i].score == SCORE_NONE) 4808 if (items[i].score == SCORE_NONE)
4814 break; 4809 break;
4815 if (list_append_number(l, ptrs[i].score) == FAIL) 4810 if (list_append_number(retlist, items[i].score) == FAIL)
4816 goto done; 4811 goto done;
4817 } 4812 }
4818 } 4813 }
4819 } 4814 }
4820 4815
4821 done: 4816 done:
4822 vim_free(ptrs); 4817 vim_free(items);
4823 } 4818 }
4824 4819
4825 /* 4820 /*
4826 * Do fuzzy matching. Returns the list of matched strings in 'rettv'. 4821 * Do fuzzy matching. Returns the list of matched strings in 'rettv'.
4827 * If 'retmatchpos' is TRUE, also returns the matching character positions. 4822 * If 'retmatchpos' is TRUE, also returns the matching character positions.