Problem: 'linebreak' may lead to wrong Visual block highlighting when
end char occupies multiple cells (after 7.4.467).
Solution: Exclude 'linebreak' from the ending column instead of setting
'virtualedit' temporarily (zeertzjq).
fixes: #19898closes: #19900
Signed-off-by: zeertzjq <zeertzjq@outlook.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: Redundant NULL checks in find_pattern_in_path().
Solution: Remove the NULL checks. Also fix typos in test_diffmode.vim
(zeertzjq).
After assigning to inc_opt on line 3461, it's dereferenced immediately,
and not assigned another value afterwards, so checking for NULL after
line 3462 is redundant.
closes: #19185
Signed-off-by: zeertzjq <zeertzjq@outlook.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: when shortmess doesn't have 'S', backward search wrap doesn't
show the "W" before count. forward search works fine but
backward fails because the position check logic is backwards -
it checks if cursor < pos instead of using the existing
wrapped flag.
Solution: Use sia->sa_wrapped flag that searchit() already sets
correctly (glepnir).
fixes: #5280closes: #19138
Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: tabpanel: inconsistent use of cmdline and message area with
tabpanel
Solution: Reduce the cmdline and message area by the horizontal size of
the tabpanel (Hirohito Higashi)
closes: #18678
Signed-off-by: Hirohito Higashi <h.east.727@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: Generating prototype files does not work on all platforms
Solution: Rework prototypes generation using python instead of cproto,
enable it in CI to test it for each PR (Hirohito Higashi).
closes: #18045
Signed-off-by: Hirohito Higashi <h.east.727@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: potential buffer-overflow in find_pattern_in_path()
Problem: Verify ptr p has enough room before adding ins_compl_len()
fixes: #18195closes: #18249
Signed-off-by: Christian Brabandt <cb@256bit.org>
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#17531closes: #17900
Signed-off-by: Girish Palya <girishji@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: Autocompletion slow with include- and tag-completion
Solution: Refactor ins_compl_interrupted() to also check for timeout,
further refactor code to skip outputting message when
performing autocompletion (Girish Palya).
Running `vim *` in `vim/src` was slower than expected when
'autocomplete' was enabled. Include-file and tag-file completion
sources were not subject to the timeout check, causing unnecessary
delays.
So apply the timeout check to these sources as well, improving
autocompletion responsiveness, refactor find_pattern_in_path() to take
an additional "silent" argument, to suppress any messages.
closes: #17966
Signed-off-by: Girish Palya <girishji@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: The maximum search count uses a hard-coded value of 99
(Andres Monge, Joschua Kesper)
Solution: Make it configurable using the 'maxsearchcount' option.
related: #8855fixes: #17527closes: #17695
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: negative matchfuzzy scores although there is a match
(Maxim Kim)
Solution: reset the score if a match has been found but the score is
negative (Girish Palya)
The fuzzy algorithm may miss some matches in long strings due to recursion
limits. As a result, the score can end up negative even when matches exist.
In such cases, reset the score to ensure it is non-negative.
fixes: ##17449
closes: #17469
Signed-off-by: Girish Palya <girishji@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: search_stat not reset when pattern differs in case
(tahzibijafar)
Solution: use STRNCMP instead of MB_STRNICMP macro
There was a long standing todo comment, that using MB_STRNICMP is wrong.
So let's change it to STRNCMP() instead. Even if it not handle
multi-byte characters correctly, then Vim will rather recompute the
search stat, instead of re-using the old (and possibly wrong) value.
fixes: #17312closes: #17314
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: Currently, 'smartcase' is respected when completing keywords
using <C-N>, <C-P>, <C-X><C-N>, and <C-X><C-P>. However, when
a user continues typing and the completion menu is filtered
using cached matches, 'smartcase' is not applied. This leads
to poor-quality or irrelevant completion suggestions, as shown
in the example below.
Solution: When filtering cached completion items after typing additional
characters, apply case-sensitive comparison if 'smartcase' is
enabled and the typed pattern includes uppercase characters.
This ensures consistent and expected completion behavior.
(Girish Palya)
closes: #17271
Signed-off-by: Girish Palya <girishji@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: chain complete does not work when 'cot' includes fuzzy
and 'completefuzzycollect' collects wrong next word.
(Konfekt)
Solution: compl_startpos is not set correctly, remove next word check
in search_for_fuzzy_match (glepnir).
fixes#17131fixes#16942closes: #17136
Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: The current_pos.col was incorrectly updated to the length of
the matching text. This will cause the next search to start
from the wrong position.
Solution: current_pos has already been updated in search_str_in_line and
does not need to be changed (glepnir)
closes: #16941
Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: Strange error with type for matchfuzzy() "camelcase".
Solution: Show the error "Invalid value for argument camelcase" instead
of "Invalid argument: camelcase" (zeertzjq).
Note that using tv_get_string() will lead to confusion, as when the
value cannot be converted to a string tv_get_string() will also give an
error about that, but "camelcase" takes a boolean, not a string. Also
don't use tv_get_string() for the "limit" argument above.
closes: #16926
Signed-off-by: zeertzjq <zeertzjq@outlook.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: When searching for "Cur", CamelCase matches like "lCursor" score
higher than exact prefix matches like Cursor, which is
counter-intuitive (Maxim Kim).
Solution: Add a 'camelcase' option to matchfuzzy() that lets users disable
CamelCase bonuses when needed, making prefix matches rank higher.
(glepnir)
fixes: #16504closes: #16797
Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: endless loop with completefuzzycollect and no match found
Solution: move pointer to line end and break loop
closes: #16820
Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: not possible to generate completion candidates using fuzzy
matching
Solution: add the 'completefuzzycollect' option for (some) ins-completion
modes (glepnir)
fixes#15296fixes#15295fixes#15294closes: #16032
Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: potential out-of-memory issue in search.c
Solution: improve situation and refactor search.c slightly
(John Marriott)
- In function update_search_stat():
add a check for a theoretical null pointer reference, set and remember
the length of lastpat, remove the three calls to STRLEN() and use the
various string's associated lengths instead, add a check for an
out-of-memory condition.
- In function search_for_fuzz_match():
remove a call to strnsave() and thus avoid having to add a check for
an out-of-memory condition, also replace the call to STRLEN() by
ml_get_buf_len().
closes: #16689
Signed-off-by: John Marriott <basilisk@internode.on.net>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: fuzzy-matching does not prefer full match
(Maxim Kim)
Solution: add additional score for a full match
(glepnir)
fixes: #15654closes: #16300
Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: too many strlen() calls in ex_getln.c
Solution: refactor the code to reduce the number of strlen() calls
(John Marriott)
closes: #15809
Signed-off-by: John Marriott <basilisk@internode.on.net>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: keyword completion does not work with fuzzy
(egesip)
Solution: handle ctrl_x_mode_normal() specifically
(glepnir)
fixes: #15412closes: #15424
Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: Sorting of fuzzy filename completion is not stable
Solution: Compare indexes when scores are equal. Fix some typos.
(zeertzjq)
closes: #15593
Signed-off-by: zeertzjq <zeertzjq@outlook.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: fuzzy completion does not work with default completion
Solution: Make it work (glepnir)
closes: #15193
Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: style: Various lines are indented inconsistently
Solution: Retab these lines and correct some comments.
(zeertzjq)
closes: #15259
Signed-off-by: zeertzjq <zeertzjq@outlook.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: fuzzy_match_str_with_pos() does unnecessary list operations.
Solution: Use fuzzy_match() directly (zeertzjq).
closes: #14987
Signed-off-by: zeertzjq <zeertzjq@outlook.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: potential deref of NULL pointer in fuzzy_match_str_with_pos()
on cleanup (after v9.1.0476)
Solution: Only free the pointer if it is non-NULL (glepnir)
closes: #14973
Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: Cannot see matched text in popup menu
Solution: Introduce 2 new highlighting groups: PmenuMatch and
PmenuMatchSel (glepnir)
ping @habamax, @neutaaaaan @romainl because vim/colorschemes may need
some updates, @lifepillar for updating vim-colortemplate
closes: #14694
Signed-off-by: glepnir <glephunter@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: too many strlen() calls in search.c
Solution: refactor code and remove more strlen() calls,
use explicit variable to remember strlen
(John Marriott)
closes: #14796
Signed-off-by: John Marriott <basilisk@internode.on.net>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: More code can use ml_get_buf_len() instead of STRLEN().
Solution: Change more STRLEN() calls to ml_get_buf_len(). Also do not
set ml_line_textlen in ml_replace_len() if "has_props" is set,
because "len_arg" also includes the size of text properties in
that case. (zeertzjq)
closes: #14183
Signed-off-by: zeertzjq <zeertzjq@outlook.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: Cannot keep a buffer focused in a window
(Amit Levy)
Solution: Add the 'winfixbuf' window-local option
(Colin Kennedy)
fixes: #6445closes: #13903
Signed-off-by: Colin Kennedy <colinvfx@gmail.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: Still a qsort() comparison function fuzzy_match_item_compare()
that returns result of subtraction (after 9.1.0089).
Solution: Use an explicit comparison instead of subtraction.
(zeertzjq)
closes: #14004
Signed-off-by: zeertzjq <zeertzjq@outlook.com>
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: qsort() comparison functions should be transitive
Solution: Do not subtract values, but rather use explicit comparisons
Improve qsort() comparison functions
There has been a recent report on qsort() causing out-of-bounds read &
write in glibc for non transitive comparison functions
https://www.qualys.com/2024/01/30/qsort.txt
Even so the bug is in glibc's implementation of the qsort() algorithm,
it's bad style to just use substraction for the comparison functions,
which may cause overflow issues and as hinted at in OpenBSD's manual
page for qsort(): "It is almost always an error to use subtraction to
compute the return value of the comparison function."
So check the qsort() comparison functions and change them to be safe.
closes: #13980
Signed-off-by: Christian Brabandt <cb@256bit.org>
Problem: Duplicate code to reverse a string
Solution: Move reverse_text() to strings.c and remove string_reverse().
closes: #12847
Signed-off-by: Christian Brabandt <cb@256bit.org>
Co-authored-by: zeertzjq <zeertzjq@outlook.com>
Problem: Search stats not always visible when searching backwards.
Solution: Do not display the top/bot message on top of the search stats.
(Christian Brabandt, closes#12322, closes#12222)
Problem: "clear" macros are not always used.
Solution: Use ALLOC_ONE, VIM_CLEAR, CLEAR_POINTER and CLEAR_FIELD in more
places. (Yegappan Lakshmanan, closes#12104)
zeertzjq
Hirohito Higashi
glepnir
Christian Brabandt
Yegappan Lakshmanan
Girish Palya
Naruhiko Nishino
John Marriott
Ken Takata
Colin Kennedy
Bram Moolenaar