| Commit message (Collapse) | Author | Age |
|---|
| |
|
|
|
|
|
|
|
|
|
|
| |
Problem: matchfuzzypos() can be improved
Solution: Compute the uppercase character once per character in
has_match(), instead of repeating the conversion while
scanning each candidate (Yasuhiro Matsumoto).
closes: vim/vim#21241
https://github.com/vim/vim/commit/c0c3fbd9671419fd43f9be0b9e371ab945af703a
Co-authored-by: Yasuhiro Matsumoto <mattn.jp@gmail.com>
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
Problem:
The loop frees `fuzmatch[count].str` on every iteration instead of
`fuzmatch[i].str`.
The function has no callers in Nvim, so there is no impact today. The
indexing is a slip from the port; Vim's implementation is correct.
Solution:
Index with the loop variable, as Vim does.
AI-assisted
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
candidates (#40257)
Problem: When a candidate gets truncated to MATCH_MAX_LEN and ends up
the same length as the needle, the n == m shortcut would
return SCORE_MAX with positions 0..n-1, even if the strings
actually differ.
Solution: Only use the shortcut if the truncated strings are truly equal.
Otherwise, fall back to regular matching.
Example:
echo matchfuzzypos(['x' .. repeat('a',1024)], repeat('a',1024))
closes: vim/vim#20475
https://github.com/vim/vim/commit/1437f478158e71effdbcec3df5caa95af9b9a50a
Co-authored-by: glepnir <glephunter@gmail.com>
|
| |
|
|
|
|
|
|
|
|
|
|
| |
candidates (#40140)
Problem: A needle that only matches past char 1024 gives an INT_MIN + 1
score with unset positions, e.g.
matchfuzzypos([repeat('a',1024)..'z'], 'az').
Solution: Drop the candidate when match_positions() returns SCORE_MIN.
closes: vim/vim#20435
https://github.com/vim/vim/commit/52003f7fc11e8fffa4cc8b0969282224a8b9a52e
|
| |
|
|
|
|
|
|
|
|
|
|
| |
(#40080)
Problem: Indent is not stripped in whole-line completion (CTRL-X
CTRL-L).
Solution: Skip the matched line's indent for whole-line matches in
search_for_fuzzy_match (glepnir).
closes: vim/vim#20405
https://github.com/vim/vim/commit/9fa5f64135c1b018ca5bfc86d851ac8185f6472b
|
| |
|
|
|
|
|
|
|
|
|
| |
Problem: matchfuzzy() can crash on long multi-word patterns.
Solution: Clamp pat_chars to maxMatches and stop before calling
match_positions() when the buffer is full (glepnir).
closes: vim/vim#20209
https://github.com/vim/vim/commit/88b00d1c57c8713ac5e7f2828c07e3c7da94ac79
Co-authored-by: glepnir <glephunter@gmail.com>
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
Problem: completion: hang with line completion and fuzzy (Jesse Pavel)
Solution: Only check the line number when wrapping around the file
(Hirohito Higashi).
fixes: vim/vim#19434
closes: vim/vim#19443
https://github.com/vim/vim/commit/d8648f7279f5a61aaa9ceebc7330e09800947a35
Co-authored-by: Hirohito Higashi <h.east.727@gmail.com>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Problem: fuzzy.c can be further improved
Solution: Fix memory leak and refactor it (glepnir).
Optimize performance and memory allocation:
- Fix memory leak in fuzzy_match_in_list.
- using single memory allocation in match_positions
- Improve has_match performance and add null pointer checks
closes: vim/vim#18012
https://github.com/vim/vim/commit/59799f3afac310f3dca409e295b2ce2036867eaf
Co-authored-by: glepnir <glephunter@gmail.com>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Problem: memory leak in fuzzy.c
Solution: Free fuzmatch, add a few minor refactors
(glepnir)
fixes neovim CID 584055: fuzmatch leak when count becomes 0
Fix partial allocation failure cleanup in buffer expansion
closes: vim/vim#17996
https://github.com/vim/vim/commit/03d6e06edd0aaf2f591d74349cb25dbeca5895ef
Co-authored-by: glepnir <glephunter@gmail.com>
|
| |
|
|
|
|
|
|
|
| |
These are not needed after #35129 but making uncrustify still play nice
with them was a bit tricky.
Unfortunately `uncrustify --update-config-with-doc` breaks strings
with backslashes. This issue has been reported upstream,
and in the meanwhile auto-update on every single run has been disabled.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Problem: fuzzy.c has a few issues
Solution: Use Vims memory management, update style
(glepnir)
Problem:
- Missing cleanup of lmatchpos lists causing memory leaks
- Missing error handling for list operations
- Use of malloc() instead of Vim's alloc() functions
- Inconsistent C-style comments
- Missing null pointer checks for memory allocation
- Incorrect use of vim_free() for list objects
Solution:
- Add proper cleanup of lmatchpos in done section using list_free()
- Set lmatchpos to NULL after successful transfer to avoid confusion
- Add error handling for list_append_tv() failures
- Replace malloc() with alloc() and add null pointer checks
- Convert C-style comments to C++ style for consistency
- Fix vim_free() calls to use list_free() for list objects
closes: vim/vim#17984
https://github.com/vim/vim/commit/17a6d696bd2f9526f2c4beae95208626d0e8d922
Co-authored-by: glepnir <glephunter@gmail.com>
|
|
|
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#34101
fixes vim/vim#17531
closes: vim/vim#17900
https://github.com/vim/vim/commit/7e0df5eee9eab872261fd5eb0068cec967a2ba77
Co-authored-by: Girish Palya <girishji@gmail.com>
|
