Problem: fuzzy-matching can be improved
Solution: Implement a better fuzzy matching algorithm
(Girish Palya)
Replace fuzzy matching algorithm with improved fzy-based implementation
The
[current](https://www.forrestthewoods.com/blog/reverse_engineering_sublime_texts_fuzzy_match/)
fuzzy matching algorithm has several accuracy issues:
* It struggles with CamelCase
* It fails to prioritize matches at the beginning of strings, often
ranking middle matches higher.
After evaluating alternatives (see my comments
[here](https://github.com/vim/vim/issues/17531#issuecomment-3112046897)
and
[here](https://github.com/vim/vim/issues/17531#issuecomment-3121593900)),
I chose to adopt the [fzy](https://github.com/jhawthorn/fzy) algorithm,
which:
* Resolves the aforementioned issues.
* Performs better.
Implementation details
This version is based on the original fzy
[algorithm](https://github.com/jhawthorn/fzy/blob/master/src/match.c),
with one key enhancement: **multibyte character support**.
* The original implementation supports only ASCII.
* This patch replaces ascii lookup tables with function calls, making it
compatible with multibyte character sets.
* Core logic (`match_row()` and `match_positions()`) remains faithful to
the original, but now operates on codepoints rather than single-byte
characters.
Performance
Tested against a dataset of **90,000 Linux kernel filenames**. Results
(in milliseconds) show a **\~2x performance improvement** over the
current fuzzy matching algorithm.
```
Search String Current Algo FZY Algo
-------------------------------------------------
init 131.759 66.916
main 83.688 40.861
sig 98.348 39.699
index 109.222 30.738
ab 72.222 44.357
cd 83.036 54.739
a 58.94 62.242
b 43.612 43.442
c 64.39 67.442
k 40.585 36.371
z 34.708 22.781
w 38.033 30.109
cpa 82.596 38.116
arz 84.251 23.964
zzzz 35.823 22.75
dimag 110.686 29.646
xa 43.188 29.199
nha 73.953 31.001
nedax 94.775 29.568
dbue 79.846 25.902
fp 46.826 31.641
tr 90.951 55.883
kw 38.875 23.194
rp 101.575 55.775
kkkkkkkkkkkkkkkkkkkkkkkkkkkkk 48.519 30.921
```
```vim
vim9script
var haystack = readfile('/Users/gp/linux.files')
var needles = ['init', 'main', 'sig', 'index', 'ab', 'cd', 'a', 'b',
'c', 'k',
'z', 'w', 'cpa', 'arz', 'zzzz', 'dimag', 'xa', 'nha', 'nedax',
'dbue',
'fp', 'tr', 'kw', 'rp', 'kkkkkkkkkkkkkkkkkkkkkkkkkkkkk']
for needle in needles
var start = reltime()
var tmp = matchfuzzy(haystack, needle)
echom $'{needle}' (start->reltime()->reltimefloat() * 1000)
endfor
```
Additional changes
* Removed the "camelcase" option from both matchfuzzy() and
matchfuzzypos(), as it's now obsolete with the improved algorithm.
related: neovim/neovim#34101fixesvim/vim#17531closes: vim/vim#179007e0df5eee9
Co-authored-by: Girish Palya <girishji@gmail.com>
The '?' needs to be escaped, because the autocommand is using
file-patterns (glob like) and not a regex). See :h file-pattern
closes: vim/vim#17890f7deb815b0
Co-authored-by: Girish Palya <girishji@gmail.com>
Problem: cannot easily trigger wildcard expansion
Solution: Introduce wildtrigger() function
(Girish Palya)
This PR introduces a new `wildtrigger()` function.
See `:h wildtrigger()`
`wildtrigger()` behaves like pressing the `wildchar,` but provides a
more refined and controlled completion experience:
- Suppresses beeps when no matches are found.
- Avoids displaying irrelevant completions (like full command lists)
when the prefix is insufficient or doesn't match.
- Skips completion if the typeahead buffer has pending input or if a
wildmenu is already active.
- Does not print "..." before completion.
This is an improvement on the `feedkeys()` based autocompletion script
given in vim/vim#16759.
closes: vim/vim#17806b486ed8266
While at it, also make Ctrl-Z trigger search completion.
Co-authored-by: Girish Palya <girishji@gmail.com>
Problem: tests: string options in gen_opt_test.vim aren't fully sorted.
Solution: Sort the string options alphabetically. Also make description
of 'maxsearchcount' start with lower-case for consistency with
other options, update documentation for searchcount().
closes: vim/vim#177207306e8fcdb
Problem: getcompletiontype() crashes when no completion is available
(after v9.1.1509).
Solution: Don't call set_expand_context() (zeertzjq)
fixes: vim/vim#17681closes: vim/vim#17684e2c0f81dd0
Problem: Patch 9.1.1505 was not good
Solution: Revert "patch 9.1.1505: not possible to return completion type
for :ex command" and instead add the getcompletiontype()
function (Hirohito Higashi).
related: vim/vim#17606closes: vim/vim#1766296b3ef2389
Cherry-pick Test_multibyte_expression() from Vim, as it passes.
Co-authored-by: Hirohito Higashi <h.east.727@gmail.com>
Co-authored-by: Shougo Matsushita <Shougo.Matsu@gmail.com>
Problem: not possible to return command-line completion type for :ex
command
Solution: make getcmdcompltype() accept an optional and return the
command-line completion for that arg (Shougo Matsushita).
closes: vim/vim#176065d2354fc07
Co-authored-by: Shougo Matsushita <Shougo.Matsu@gmail.com>
Problem: no easy way to deduplicate text
Solution: add the :uniq ex command
(Hirohito Higashi)
closes: vim/vim#1753874f0a77bb9
Co-authored-by: Hirohito Higashi <h.east.727@gmail.com>
fix(exrc): lua exrc files know their location
Problem:
'exrc' files are inherently bound to their location / workspace and
therefore require to "know" their location on the filesystem. However,
currently using `debug.getinfo(1, 'S')` returns `"<nvim>"`.
Solution:
Include the filepath as chunkname in `loadstring()` and `nlua_exec()`.
Problem:
Not easy to get user-input in prompt-buffer before the user submits the
input. Under the current system user/plugin needs to read the buffer
contents, figure out where the prompt is, then extract the text.
Solution:
- Add prompt_getinput().
- Extract prompt text extraction logic to a separate function
Problem: Non-visible/focusable windows are assigned a window number,
whereas commands that use this window number skip over them.
Solution: Skip over non-visible/focusable windows when computing
the window number, unless it is made the current window
through the API in which case an identifiable window number
is still useful. This also ensures it matches the window
number of the window entered by `<winnr>wincmd w` since
403fcacf.
Problem:
Despite the name, `builtin.txt` only includes Vimscript functions, which
is confusing, especially to people who only use Lua to configure Nvim
Solution: From justinmk's suggestion
- Rename `builtin.txt` to `vimfn.txt`
- Rename `eval.txt` to `vimeval.txt`
- The tags `*builtin.txt*` and `*eval.txt*` should be kept for Vim-patches
Closes#33743
