From fba00b5e7ef2b6903a4588a2c080d8b33a8a2b68 Mon Sep 17 00:00:00 2001 From: Sean Dewar Date: Sat, 1 Jan 2022 14:58:32 +0000 Subject: vim-patch:8.2.1665: cannot do fuzzy string matching Problem: Cannot do fuzzy string matching. Solution: Add matchfuzzy(). (Yegappan Lakshmanan, closes vim/vim#6932) https://github.com/vim/vim/commit/635414dd2f3ae7d4d972d79b806348a6516cb91a Adjust Test_matchfuzzy's 2nd assert to expect the last error thrown, as v8.2.1183 hasn't been ported yet (to be honest, the error message is kinda weird if the 2nd argument is not convertible to string). We can still port this fully as porting v8.2.1183 would require removing this change to pass CI. --- runtime/doc/builtin.txt | 22 ++++++++++++++++++++++ runtime/doc/usr_41.txt | 1 + 2 files changed, 23 insertions(+) (limited to 'runtime') diff --git a/runtime/doc/builtin.txt b/runtime/doc/builtin.txt index 56bc8bfb3e..198ef25ed9 100644 --- a/runtime/doc/builtin.txt +++ b/runtime/doc/builtin.txt @@ -296,6 +296,7 @@ matcharg({nr}) List arguments of |:match| matchdelete({id} [, {win}]) Number delete match identified by {id} matchend({expr}, {pat}[, {start}[, {count}]]) Number position where {pat} ends in {expr} +matchfuzzy({list}, {str}) List fuzzy match {str} in {list} matchlist({expr}, {pat}[, {start}[, {count}]]) List match and submatches of {pat} in {expr} matchstr({expr}, {pat}[, {start}[, {count}]]) @@ -4857,6 +4858,27 @@ matchend({expr}, {pat} [, {start} [, {count}]]) *matchend()* Can also be used as a |method|: > GetText()->matchend('word') +matchfuzzy({list}, {str}) *matchfuzzy()* + Returns a list with all the strings in {list} that fuzzy + match {str}. The strings in the returned list are sorted + based on the matching score. {str} is treated as a literal + string and regular expression matching is NOT supported. + The maximum supported {str} length is 256. + + If there are no matching strings or there is an error, then an + empty list is returned. If length of {str} is greater than + 256, then returns an empty list. + + Example: > + :echo matchfuzzy(["clay", "crow"], "cay") +< results in ["clay"]. > + :echo getbufinfo()->map({_, v -> v.name})->matchfuzzy("ndl") +< results in a list of buffer names fuzzy matching "ndl". > + :echo v:oldfiles->matchfuzzy("test") +< results in a list of file names fuzzy matching "test". > + :let l = readfile("buffer.c")->matchfuzzy("str") +< results in a list of lines in "buffer.c" fuzzy matching "str". + matchlist({expr}, {pat} [, {start} [, {count}]]) *matchlist()* Same as |match()|, but return a |List|. The first item in the list is the matched string, same as what matchstr() would diff --git a/runtime/doc/usr_41.txt b/runtime/doc/usr_41.txt index bf29c94d51..19f58cddd6 100644 --- a/runtime/doc/usr_41.txt +++ b/runtime/doc/usr_41.txt @@ -608,6 +608,7 @@ String manipulation: *string-functions* toupper() turn a string to uppercase match() position where a pattern matches in a string matchend() position where a pattern match ends in a string + matchfuzzy() fuzzy matches a string in a list of strings matchstr() match of a pattern in a string matchstrpos() match and positions of a pattern in a string matchlist() like matchstr() and also return submatches -- cgit From 960ea01972ad5fd291a846dce67f96a95222c310 Mon Sep 17 00:00:00 2001 From: Sean Dewar Date: Sat, 1 Jan 2022 16:40:28 +0000 Subject: vim-patch:8.2.1726: fuzzy matching only works on strings Problem: Fuzzy matching only works on strings. Solution: Support passing a dict. Add matchfuzzypos() to also get the match positions. (Yegappan Lakshmanan, closes vim/vim#6947) https://github.com/vim/vim/commit/4f73b8e9cc83f647b34002554a8bdf9abec0a82f Also remove some N/A and seemingly useless NULL checks -- Nvim allocs can't return NULL. I'm not sure why the retmatchpos stuff in match_fuzzy checks for NULL too, given that Vim checks for NULL alloc in do_fuzzymatch; assert that the li stuff is not NULL as that's the one check I'm ever-so-slightly unsure about. Adjust tests. Note that the text_cb tests actually throw E6000 in Nvim, but we also can't assert that error due to v8.2.1183 not being ported yet. --- runtime/doc/builtin.txt | 57 +++++++++++++++++++++++++++++++++++++++++++------ runtime/doc/usr_41.txt | 1 + 2 files changed, 51 insertions(+), 7 deletions(-) (limited to 'runtime') diff --git a/runtime/doc/builtin.txt b/runtime/doc/builtin.txt index 198ef25ed9..14cf9f09fc 100644 --- a/runtime/doc/builtin.txt +++ b/runtime/doc/builtin.txt @@ -296,7 +296,10 @@ matcharg({nr}) List arguments of |:match| matchdelete({id} [, {win}]) Number delete match identified by {id} matchend({expr}, {pat}[, {start}[, {count}]]) Number position where {pat} ends in {expr} -matchfuzzy({list}, {str}) List fuzzy match {str} in {list} +matchfuzzy({list}, {str} [, {dict}]) + List fuzzy match {str} in {list} +matchfuzzypos({list}, {str} [, {dict}]) + List fuzzy match {str} in {list} matchlist({expr}, {pat}[, {start}[, {count}]]) List match and submatches of {pat} in {expr} matchstr({expr}, {pat}[, {start}[, {count}]]) @@ -4858,12 +4861,25 @@ matchend({expr}, {pat} [, {start} [, {count}]]) *matchend()* Can also be used as a |method|: > GetText()->matchend('word') -matchfuzzy({list}, {str}) *matchfuzzy()* - Returns a list with all the strings in {list} that fuzzy - match {str}. The strings in the returned list are sorted - based on the matching score. {str} is treated as a literal - string and regular expression matching is NOT supported. - The maximum supported {str} length is 256. +matchfuzzy({list}, {str} [, {dict}]) *matchfuzzy()* + If {list} is a list of strings, then returns a list with all + the strings in {list} that fuzzy match {str}. The strings in + the returned list are sorted based on the matching score. + + If {list} is a list of dictionaries, then the optional {dict} + argument supports the following items: + 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 + in {list} to get the text for fuzzy matching. + This should accept a dictionary item as the + argument and return the text for that item to + use for fuzzy matching. + + {str} is treated as a literal string and regular expression + matching is NOT supported. The maximum supported {str} length + is 256. If there are no matching strings or there is an error, then an empty list is returned. If length of {str} is greater than @@ -4874,11 +4890,38 @@ matchfuzzy({list}, {str}) *matchfuzzy()* < results in ["clay"]. > :echo getbufinfo()->map({_, v -> v.name})->matchfuzzy("ndl") < results in a list of buffer names fuzzy matching "ndl". > + :echo getbufinfo()->matchfuzzy("ndl", {'key' : 'name'}) +< results in a list of buffer information dicts with buffer + names fuzzy matching "ndl". > + :echo getbufinfo()->matchfuzzy("spl", + \ {'text_cb' : {v -> v.name}}) +< results in a list of buffer information dicts with buffer + names fuzzy matching "spl". > :echo v:oldfiles->matchfuzzy("test") < results in a list of file names fuzzy matching "test". > :let l = readfile("buffer.c")->matchfuzzy("str") < results in a list of lines in "buffer.c" fuzzy matching "str". +matchfuzzypos({list}, {str} [, {dict}]) *matchfuzzypos()* + Same as |matchfuzzy()|, but returns the list of matched + strings and the list of character positions where characters + in {str} matches. + + If {str} matches multiple times in a string, then only the + positions for the best match is returned. + + If there are no matching strings or there is an error, then a + list with two empty list items is returned. + + Example: > + :echo matchfuzzypos(['testing'], 'tsg') +< results in [['testing'], [[0, 2, 6]]] > + :echo matchfuzzypos(['clay', 'lacy'], 'la') +< results in [['lacy', 'clay'], [[0, 1], [1, 2]]] > + :echo [{'text': 'hello', 'id' : 10}] + \ ->matchfuzzypos('ll', {'key' : 'text'}) +< results in [{'id': 10, 'text': 'hello'}] [[2, 3]] + matchlist({expr}, {pat} [, {start} [, {count}]]) *matchlist()* Same as |match()|, but return a |List|. The first item in the list is the matched string, same as what matchstr() would diff --git a/runtime/doc/usr_41.txt b/runtime/doc/usr_41.txt index 19f58cddd6..bf024315f6 100644 --- a/runtime/doc/usr_41.txt +++ b/runtime/doc/usr_41.txt @@ -609,6 +609,7 @@ String manipulation: *string-functions* match() position where a pattern matches in a string matchend() position where a pattern match ends in a string matchfuzzy() fuzzy matches a string in a list of strings + matchfuzzypos() fuzzy matches a string in a list of strings matchstr() match of a pattern in a string matchstrpos() match and positions of a pattern in a string matchlist() like matchstr() and also return submatches -- cgit From 30deb14f397e576aedfa54600ed7408b3e03459d Mon Sep 17 00:00:00 2001 From: Sean Dewar Date: Sat, 1 Jan 2022 21:25:41 +0000 Subject: vim-patch:8.2.1893: fuzzy matching does not support multiple words Problem: Fuzzy matching does not support multiple words. Solution: Add support for matching white space separated words. (Yegappan Lakshmanan, closes vim/vim#7163) https://github.com/vim/vim/commit/8ded5b647aa4b3338da721b343e0bce0f86655f6 --- runtime/doc/builtin.txt | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-) (limited to 'runtime') diff --git a/runtime/doc/builtin.txt b/runtime/doc/builtin.txt index 14cf9f09fc..745f1d9116 100644 --- a/runtime/doc/builtin.txt +++ b/runtime/doc/builtin.txt @@ -4866,8 +4866,15 @@ matchfuzzy({list}, {str} [, {dict}]) *matchfuzzy()* the strings in {list} that fuzzy match {str}. The strings in the returned list are sorted based on the matching score. + The optional {dict} argument always supports the following + items: + matchseq When this item is present and {str} contains + multiple words separated by white space, then + returns only matches that contain the words in + the given sequence. + If {list} is a list of dictionaries, then the optional {dict} - argument supports the following items: + argument supports the following additional items: key key of the item which is fuzzy matched against {str}. The value of this item should be a string. @@ -4881,6 +4888,9 @@ matchfuzzy({list}, {str} [, {dict}]) *matchfuzzy()* matching is NOT supported. The maximum supported {str} length is 256. + When {str} has multiple words each separated by white space, + then the list of strings that have all the words is returned. + If there are no matching strings or there is an error, then an empty list is returned. If length of {str} is greater than 256, then returns an empty list. @@ -4900,7 +4910,12 @@ matchfuzzy({list}, {str} [, {dict}]) *matchfuzzy()* :echo v:oldfiles->matchfuzzy("test") < results in a list of file names fuzzy matching "test". > :let l = readfile("buffer.c")->matchfuzzy("str") -< results in a list of lines in "buffer.c" fuzzy matching "str". +< results in a list of lines in "buffer.c" fuzzy matching "str". > + :echo ['one two', 'two one']->matchfuzzy('two one') +< results in ['two one', 'one two']. > + :echo ['one two', 'two one']->matchfuzzy('two one', + \ {'matchseq': 1}) +< results in ['two one']. matchfuzzypos({list}, {str} [, {dict}]) *matchfuzzypos()* Same as |matchfuzzy()|, but returns the list of matched -- cgit From 715fbcbb8c6ec4385d1168b1260fdb991d4e6fc5 Mon Sep 17 00:00:00 2001 From: Sean Dewar Date: Sat, 1 Jan 2022 22:40:42 +0000 Subject: vim-patch:8.2.2280: fuzzy matching doesn't give access to the scores Problem: Fuzzy matching doesn't give access to the scores. Solution: Return the scores with a third list. (Yegappan Lakshmanan, closes vim/vim#7596) https://github.com/vim/vim/commit/9d19e4f4ba55f8bef18d4991abdf740ff6472dba Remove seemingly useless NULL checks. assert that removing the li one wasn't dumb. --- runtime/doc/builtin.txt | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) (limited to 'runtime') diff --git a/runtime/doc/builtin.txt b/runtime/doc/builtin.txt index 745f1d9116..45c03fc447 100644 --- a/runtime/doc/builtin.txt +++ b/runtime/doc/builtin.txt @@ -4919,23 +4919,25 @@ matchfuzzy({list}, {str} [, {dict}]) *matchfuzzy()* matchfuzzypos({list}, {str} [, {dict}]) *matchfuzzypos()* Same as |matchfuzzy()|, but returns the list of matched - strings and the list of character positions where characters - in {str} matches. + strings, the list of character positions where characters + in {str} matches and a list of matching scores. You can + use |byteidx()| to convert a character position to a byte + position. If {str} matches multiple times in a string, then only the positions for the best match is returned. If there are no matching strings or there is an error, then a - list with two empty list items is returned. + list with three empty list items is returned. Example: > :echo matchfuzzypos(['testing'], 'tsg') -< results in [['testing'], [[0, 2, 6]]] > +< results in [['testing'], [[0, 2, 6]], [99]] > :echo matchfuzzypos(['clay', 'lacy'], 'la') -< results in [['lacy', 'clay'], [[0, 1], [1, 2]]] > +< results in [['lacy', 'clay'], [[0, 1], [1, 2]], [153, 133]] > :echo [{'text': 'hello', 'id' : 10}] \ ->matchfuzzypos('ll', {'key' : 'text'}) -< results in [{'id': 10, 'text': 'hello'}] [[2, 3]] +< results in [[{'id': 10, 'text': 'hello'}], [[2, 3]], [127]] matchlist({expr}, {pat} [, {start} [, {count}]]) *matchlist()* Same as |match()|, but return a |List|. The first item in the -- cgit From ce797e08f539dc24d16ea8c02591296bbbc83772 Mon Sep 17 00:00:00 2001 From: Sean Dewar Date: Sat, 1 Jan 2022 23:06:09 +0000 Subject: vim-patch:8.2.2813: cannot grep using fuzzy matching Problem: Cannot grep using fuzzy matching. Solution: Add the "f" flag to :vimgrep. (Yegappan Lakshmanan, closes vim/vim#8152) https://github.com/vim/vim/commit/bb01a1ef3a093cdb36877ba73474719c531dc8cb --- runtime/doc/quickfix.txt | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'runtime') diff --git a/runtime/doc/quickfix.txt b/runtime/doc/quickfix.txt index bb4d807413..c7289cfca6 100644 --- a/runtime/doc/quickfix.txt +++ b/runtime/doc/quickfix.txt @@ -989,7 +989,7 @@ commands can be combined to create a NewGrep command: > 5.1 using Vim's internal grep *:vim* *:vimgrep* *E682* *E683* -:vim[grep][!] /{pattern}/[g][j] {file} ... +:vim[grep][!] /{pattern}/[g][j][f] {file} ... Search for {pattern} in the files {file} ... and set the error list to the matches. Files matching 'wildignore' are ignored; files in 'suffixes' are @@ -1042,20 +1042,20 @@ commands can be combined to create a NewGrep command: > :vimgrep Error *.c < *:lv* *:lvimgrep* -:lv[imgrep][!] /{pattern}/[g][j] {file} ... +:lv[imgrep][!] /{pattern}/[g][j][f] {file} ... :lv[imgrep][!] {pattern} {file} ... Same as ":vimgrep", except the location list for the current window is used instead of the quickfix list. *:vimgrepa* *:vimgrepadd* -:vimgrepa[dd][!] /{pattern}/[g][j] {file} ... +:vimgrepa[dd][!] /{pattern}/[g][j][f] {file} ... :vimgrepa[dd][!] {pattern} {file} ... Just like ":vimgrep", but instead of making a new list of errors the matches are appended to the current list. *:lvimgrepa* *:lvimgrepadd* -:lvimgrepa[dd][!] /{pattern}/[g][j] {file} ... +:lvimgrepa[dd][!] /{pattern}/[g][j][f] {file} ... :lvimgrepa[dd][!] {pattern} {file} ... Same as ":vimgrepadd", except the location list for the current window is used instead of the quickfix -- cgit From 02e74314459621bfd18b3b3a1e3ac261658dc096 Mon Sep 17 00:00:00 2001 From: Sean Dewar Date: Sun, 2 Jan 2022 00:42:09 +0000 Subject: docs(fuzzy-match): cherry-pick latest changes https://github.com/vim/vim/commit/53f7fccc9413c9f770694b56f40f242d383b2d5f https://github.com/vim/vim/commit/1b884a0053982335f644eec6c71027706bf3c522 https://github.com/vim/vim/commit/4c295027a426986566cd7a76c47a6d3a529727e7 https://github.com/vim/vim/commit/3ec3217f0491e9ba8aa8ea02f7e454cd19a287ef --- runtime/doc/builtin.txt | 5 ++++- runtime/doc/pattern.txt | 33 +++++++++++++++++++++++++++++++++ runtime/doc/quickfix.txt | 7 +++++++ 3 files changed, 44 insertions(+), 1 deletion(-) (limited to 'runtime') diff --git a/runtime/doc/builtin.txt b/runtime/doc/builtin.txt index 45c03fc447..b7a9a06b3c 100644 --- a/runtime/doc/builtin.txt +++ b/runtime/doc/builtin.txt @@ -4862,7 +4862,7 @@ matchend({expr}, {pat} [, {start} [, {count}]]) *matchend()* GetText()->matchend('word') matchfuzzy({list}, {str} [, {dict}]) *matchfuzzy()* - If {list} is a list of strings, then returns a list with all + If {list} is a list of strings, then returns a |List| with all the strings in {list} that fuzzy match {str}. The strings in the returned list are sorted based on the matching score. @@ -4895,6 +4895,9 @@ matchfuzzy({list}, {str} [, {dict}]) *matchfuzzy()* empty list is returned. If length of {str} is greater than 256, then returns an empty list. + Refer to |fuzzy-match| for more information about fuzzy + matching strings. + Example: > :echo matchfuzzy(["clay", "crow"], "cay") < results in ["clay"]. > diff --git a/runtime/doc/pattern.txt b/runtime/doc/pattern.txt index 634145da3e..42005b0d78 100644 --- a/runtime/doc/pattern.txt +++ b/runtime/doc/pattern.txt @@ -1421,5 +1421,38 @@ Finally, these constructs are unique to Perl: are suggested to use ":match" for manual matching and ":2match" for another plugin. +============================================================================== +11. Fuzzy matching *fuzzy-match* + +Fuzzy matching refers to matching strings using a non-exact search string. +Fuzzy matching will match a string, if all the characters in the search string +are present anywhere in the string in the same order. Case is ignored. In a +matched string, other characters can be present between two consecutive +characters in the search string. If the search string has multiple words, then +each word is matched separately. So the words in the search string can be +present in any order in a string. + +Fuzzy matching assigns a score for each matched string based on the following +criteria: + - The number of sequentially matching characters. + - The number of characters (distance) between two consecutive matching + characters. + - Matches at the beginning of a word + - Matches at a camel case character (e.g. Case in CamelCase) + - Matches after a path separator or a hyphen. + - The number of unmatched characters in a string. +The matching string with the highest score is returned first. + +For example, when you search for the "get pat" string using fuzzy matching, it +will match the strings "GetPattern", "PatternGet", "getPattern", "patGetter", +"getSomePattern", "MatchpatternGet" etc. + +The functions |matchfuzzy()| and |matchfuzzypos()| can be used to fuzzy search +a string in a List of strings. The matchfuzzy() function returns a List of +matching strings. The matchfuzzypos() functions returns the List of matches, +the matching positions and the fuzzy match scores. + +The "f" flag of `:vimgrep` enables fuzzy matching. + vim:tw=78:ts=8:noet:ft=help:norl: diff --git a/runtime/doc/quickfix.txt b/runtime/doc/quickfix.txt index c7289cfca6..ed736ad4eb 100644 --- a/runtime/doc/quickfix.txt +++ b/runtime/doc/quickfix.txt @@ -1014,6 +1014,13 @@ commands can be combined to create a NewGrep command: > updated. With the [!] any changes in the current buffer are abandoned. + 'f' When the 'f' flag is specified, fuzzy string + matching is used to find matching lines. In this + case, {pattern} is treated as a literal string + instead of a regular expression. See + |fuzzy-match| for more information about fuzzy + matching strings. + |QuickFixCmdPre| and |QuickFixCmdPost| are triggered. A file that is opened for matching may use a buffer number, but it is reused if possible to avoid -- cgit