mirror of
https://github.com/neovim/neovim.git
synced 2025-09-07 11:58:17 +00:00
869000e7ce
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
7e0df5eee9
Co-authored-by: Girish Palya <girishji@gmail.com>
327 lines
19 KiB
VimL
327 lines
19 KiB
VimL
" Tests for fuzzy matching
|
||
|
||
source shared.vim
|
||
source check.vim
|
||
source term_util.vim
|
||
|
||
" Test for matchfuzzy()
|
||
func Test_matchfuzzy()
|
||
call assert_fails('call matchfuzzy(10, "abc")', 'E686:')
|
||
call assert_fails('call matchfuzzy(["abc"], [])', 'E730:')
|
||
call assert_fails("let x = matchfuzzy(v:_null_list, 'foo')", 'E686:')
|
||
call assert_fails('call matchfuzzy(["abc"], v:_null_string)', 'E475:')
|
||
call assert_equal([], matchfuzzy([], 'abc'))
|
||
call assert_equal([], matchfuzzy(['abc'], ''))
|
||
call assert_equal(['abc'], matchfuzzy(['abc', 10], 'ac'))
|
||
call assert_equal([], matchfuzzy([10, 20], 'ac'))
|
||
call assert_equal(['abc'], matchfuzzy(['abc'], 'abc'))
|
||
call assert_equal(['crayon', 'camera'], matchfuzzy(['camera', 'crayon'], 'cra'))
|
||
call assert_equal(['aabbaa', 'aaabbbaaa', 'aaaabbbbaaaa', 'aba'], matchfuzzy(['aba', 'aabbaa', 'aaabbbaaa', 'aaaabbbbaaaa'], 'aa'))
|
||
call assert_equal(['one'], matchfuzzy(['one', 'two'], 'one'))
|
||
call assert_equal(['oneTwo'], matchfuzzy(['onetwo', 'oneTwo'], 'oneTwo'))
|
||
call assert_equal([], matchfuzzy(['onetwo', 'one_two'], 'oneTwo'))
|
||
call assert_equal(['aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'], matchfuzzy(['aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'], 'aa'))
|
||
call assert_equal(256, matchfuzzy([repeat('a', 256)], repeat('a', 256))[0]->len())
|
||
call assert_equal([repeat('a', 300)], matchfuzzy([repeat('a', 300)], repeat('a', 257)))
|
||
" full match has highest score
|
||
call assert_equal(['Cursor', 'lCursor'], matchfuzzy(["hello", "lCursor", "Cursor"], "Cursor"))
|
||
" matches with same score should not be reordered
|
||
let l = ['abc1', 'abc2', 'abc3']
|
||
call assert_equal(l, l->matchfuzzy('abc'))
|
||
|
||
" Tests for match preferences
|
||
call assert_equal(['onetwo', 'oneTwo'], ['onetwo', 'oneTwo']->matchfuzzy('onetwo'))
|
||
" preference for match after a separator (_ or space)
|
||
call assert_equal(['onetwo', 'one_two', 'one two'], ['onetwo', 'one_two', 'one two']->matchfuzzy('onetwo'))
|
||
" preference for leading letter match
|
||
call assert_equal(['onetwo', 'xonetwo'], ['xonetwo', 'onetwo']->matchfuzzy('onetwo'))
|
||
" preference for sequential match
|
||
call assert_equal(['onetwo', 'oanbectdweo'], ['oanbectdweo', 'onetwo']->matchfuzzy('onetwo'))
|
||
" non-matching leading letter(s) penalty
|
||
call assert_equal(['xonetwo', 'xxonetwo'], ['xxonetwo', 'xonetwo']->matchfuzzy('onetwo'))
|
||
" total non-matching letter(s) penalty
|
||
call assert_equal(['one', 'onex', 'onexx'], ['onexx', 'one', 'onex']->matchfuzzy('one'))
|
||
" prefer complete matches over separator matches
|
||
call assert_equal(['.vim/vimrc', '.vim/vimrc_colors', '.vim/v_i_m_r_c'], ['.vim/vimrc', '.vim/vimrc_colors', '.vim/v_i_m_r_c']->matchfuzzy('vimrc'))
|
||
" gap penalty
|
||
call assert_equal(['xxayybxxxx', 'xxayyybxxx', 'xxayyyybxx'], ['xxayyyybxx', 'xxayyybxxx', 'xxayybxxxx']->matchfuzzy('ab'))
|
||
" path separator vs word separator
|
||
call assert_equal(['color/setup.vim', 'color setup.vim', 'color_setup.vim', 'colorsetup.vim', 'color\\setup.vim'], matchfuzzy(['colorsetup.vim', 'color setup.vim', 'color/setup.vim', 'color_setup.vim', 'color\\setup.vim'], 'setup.vim'))
|
||
|
||
" match multiple words (separated by space)
|
||
call assert_equal(['foo bar baz'], ['foo bar baz', 'foo', 'foo bar', 'baz bar']->matchfuzzy('baz foo'))
|
||
call assert_equal([], ['foo bar baz', 'foo', 'foo bar', 'baz bar']->matchfuzzy('one two'))
|
||
call assert_equal([], ['foo bar']->matchfuzzy(" \t "))
|
||
|
||
" test for matching a sequence of words
|
||
call assert_equal(['bar foo'], ['foo bar', 'bar foo', 'foobar', 'barfoo']->matchfuzzy('bar foo', {'matchseq' : 1}))
|
||
call assert_equal([#{text: 'two one'}], [#{text: 'one two'}, #{text: 'two one'}]->matchfuzzy('two one', #{key: 'text', matchseq: v:true}))
|
||
|
||
%bw!
|
||
eval ['somebuf', 'anotherone', 'needle', 'yetanotherone']->map({_, v -> bufadd(v) + bufload(v)})
|
||
let l = getbufinfo()->map({_, v -> fnamemodify(v.name, ':t')})->matchfuzzy('ndl')
|
||
call assert_equal(1, len(l))
|
||
call assert_match('needle', l[0])
|
||
|
||
" Test for fuzzy matching dicts
|
||
let l = [{'id' : 5, 'val' : 'crayon'}, {'id' : 6, 'val' : 'camera'}]
|
||
call assert_equal([{'id' : 6, 'val' : 'camera'}], matchfuzzy(l, 'cam', {'text_cb' : {v -> v.val}}))
|
||
call assert_equal([{'id' : 6, 'val' : 'camera'}], matchfuzzy(l, 'cam', {'key' : 'val'}))
|
||
call assert_equal([], matchfuzzy(l, 'day', {'text_cb' : {v -> v.val}}))
|
||
call assert_equal([], matchfuzzy(l, 'day', {'key' : 'val'}))
|
||
call assert_fails("let x = matchfuzzy(l, 'cam', 'random')", 'E1206:')
|
||
call assert_equal([], matchfuzzy(l, 'day', {'text_cb' : {v -> []}}))
|
||
call assert_equal([], matchfuzzy(l, 'day', {'text_cb' : {v -> 1}}))
|
||
call assert_fails("let x = matchfuzzy(l, 'day', {'text_cb' : {a, b -> 1}})", 'E119:')
|
||
call assert_equal([], matchfuzzy(l, 'cam'))
|
||
" Nvim's callback implementation is different, so E6000 is expected instead,
|
||
" call assert_fails("let x = matchfuzzy(l, 'cam', {'text_cb' : []})", 'E921:')
|
||
call assert_fails("let x = matchfuzzy(l, 'cam', {'text_cb' : []})", 'E6000:')
|
||
call assert_fails("let x = matchfuzzy(l, 'foo', {'key' : 123})", 'E475: Invalid value for argument key: 123')
|
||
call assert_fails("let x = matchfuzzy(l, 'foo', {'key' : []})", 'E730:')
|
||
call assert_fails("let x = matchfuzzy(l, 'cam', v:_null_dict)", 'E1297:')
|
||
call assert_fails("let x = matchfuzzy(l, 'foo', {'key' : v:_null_string})", 'E475:')
|
||
" Nvim doesn't have null functions
|
||
" call assert_fails("let x = matchfuzzy(l, 'foo', {'text_cb' : test_null_function()})", 'E475:')
|
||
" matches with same score should not be reordered
|
||
let l = [#{text: 'abc', id: 1}, #{text: 'abc', id: 2}, #{text: 'abc', id: 3}]
|
||
call assert_equal(l, l->matchfuzzy('abc', #{key: 'text'}))
|
||
|
||
let l = [{'id' : 5, 'name' : 'foo'}, {'id' : 6, 'name' : []}, {'id' : 7}]
|
||
call assert_fails("let x = matchfuzzy(l, 'foo', {'key' : 'name'})", 'E730:')
|
||
|
||
" camelcase
|
||
call assert_equal(['Cursor', 'CurSearch', 'CursorLine', 'lCursor', 'shCurlyIn', 'shCurlyError', 'TracesCursor'],
|
||
\ matchfuzzy(['Cursor', 'lCursor', 'shCurlyIn', 'shCurlyError', 'TracesCursor', 'CurSearch', 'CursorLine'], 'Cur'))
|
||
call assert_equal(['things', 'sThings', 'thisThings'],
|
||
\ matchfuzzy(['things','sThings', 'thisThings'], 'thin'))
|
||
call assert_equal(['MyTestCase', 'mytestcase'], matchfuzzy(['mytestcase', 'MyTestCase'], 'mtc'))
|
||
call assert_equal(['MyTestCase', 'mytestcase'], matchfuzzy(['MyTestCase', 'mytestcase'], 'mtc'))
|
||
call assert_equal(['MyTest'], matchfuzzy(['Mytest', 'mytest', 'MyTest'], 'MyT'))
|
||
call assert_equal(['CamelCaseMatchIngAlg'],
|
||
\ matchfuzzy(['CamelCaseMatchIngAlg', 'camelCaseMatchingAlg', 'camelcasematchingalg'], 'CamelCase'))
|
||
call assert_equal(['SomeWord', 'PrefixSomeWord'], matchfuzzy(['PrefixSomeWord', 'SomeWord'], 'somewor'))
|
||
|
||
" Test in latin1 encoding
|
||
let save_enc = &encoding
|
||
" Nvim supports utf-8 encoding only
|
||
" set encoding=latin1
|
||
call assert_equal(['abc'], matchfuzzy(['abc'], 'abc'))
|
||
let &encoding = save_enc
|
||
endfunc
|
||
|
||
" Test for the matchfuzzypos() function
|
||
func Test_matchfuzzypos()
|
||
call assert_equal([['curl', 'world'], [[2,3], [2,3]], [990, 985]], matchfuzzypos(['world', 'curl'], 'rl'))
|
||
call assert_equal([['curl', 'world'], [[2,3], [2,3]], [990, 985]], matchfuzzypos(['world', 'one', 'curl'], 'rl'))
|
||
call assert_equal([['hello', 'hello world hello world'],
|
||
\ [[0, 1, 2, 3, 4], [0, 1, 2, 3, 4]], [2147483647, 4810]],
|
||
\ matchfuzzypos(['hello world hello world', 'hello', 'world'], 'hello'))
|
||
call assert_equal([['aaaaaaa'], [[0, 1, 2]], [2880]], matchfuzzypos(['aaaaaaa'], 'aaa'))
|
||
call assert_equal([['a b'], [[0, 3]], [1670]], matchfuzzypos(['a b'], 'a b'))
|
||
call assert_equal([['a b'], [[0, 3]], [1670]], matchfuzzypos(['a b'], 'a b'))
|
||
call assert_equal([['a b'], [[0]], [885]], matchfuzzypos(['a b'], ' a '))
|
||
call assert_equal([[], [], []], matchfuzzypos(['a b'], ' '))
|
||
call assert_equal([[], [], []], matchfuzzypos(['world', 'curl'], 'ab'))
|
||
let x = matchfuzzypos([repeat('a', 256)], repeat('a', 256))
|
||
call assert_equal(range(256), x[1][0])
|
||
|
||
" fuzzy matches limited to 1024 chars
|
||
let matches = matchfuzzypos([repeat('a', 1030)], repeat('a', 1025))
|
||
call assert_equal([repeat('a', 1030)], matches[0])
|
||
call assert_equal(1024, len(matches[1][0]))
|
||
call assert_equal(1023, matches[1][0][1023])
|
||
|
||
call assert_equal([[], [], []], matchfuzzypos([], 'abc'))
|
||
call assert_equal([[], [], []], matchfuzzypos(['abc'], ''))
|
||
|
||
" match in a long string
|
||
call assert_equal([[repeat('x', 300) .. 'abc'], [[300, 301, 302]], [500]],
|
||
\ matchfuzzypos([repeat('x', 300) .. 'abc'], 'abc'))
|
||
|
||
" preference for camel case match
|
||
call assert_equal([['xabcxxaBc'], [[7, 8]], [1665]], matchfuzzypos(['xabcxxaBc'], 'bc'))
|
||
" preference for match after a separator (_ or space)
|
||
call assert_equal([['xabx_ab'], [[5, 6]], [1775]], matchfuzzypos(['xabx_ab'], 'ab'))
|
||
" preference for leading letter match
|
||
call assert_equal([['abcxabc'], [[0, 1]], [1875]], matchfuzzypos(['abcxabc'], 'ab'))
|
||
" preference for sequential match
|
||
call assert_equal([['aobncedone'], [[7, 8, 9]], [1965]], matchfuzzypos(['aobncedone'], 'one'))
|
||
" best recursive match
|
||
call assert_equal([['xoone'], [[2, 3, 4]], [1990]], matchfuzzypos(['xoone'], 'one'))
|
||
|
||
" match multiple words (separated by space)
|
||
call assert_equal([['foo bar baz'], [[8, 9, 10, 0, 1, 2]], [5620]], ['foo bar baz', 'foo', 'foo bar', 'baz bar']->matchfuzzypos('baz foo'))
|
||
call assert_equal([[], [], []], ['foo bar baz', 'foo', 'foo bar', 'baz bar']->matchfuzzypos('baz foo', {'matchseq': 1}))
|
||
call assert_equal([['foo bar baz'], [[0, 1, 2, 8, 9, 10]], [5620]], ['foo bar baz', 'foo', 'foo bar', 'baz bar']->matchfuzzypos('foo baz'))
|
||
call assert_equal([['foo bar baz'], [[0, 1, 2, 3, 4, 9, 10]], [6660]], ['foo bar baz', 'foo', 'foo bar', 'baz bar']->matchfuzzypos('foo baz', {'matchseq': 1}))
|
||
call assert_equal([[], [], []], ['foo bar baz', 'foo', 'foo bar', 'baz bar']->matchfuzzypos('one two'))
|
||
call assert_equal([[], [], []], ['foo bar']->matchfuzzypos(" \t "))
|
||
call assert_equal([['grace'], [[1, 2, 3, 4, 2, 3, 4, 0, 1, 2, 3, 4]], [2147483647]], ['grace']->matchfuzzypos('race ace grace'))
|
||
|
||
let l = [{'id' : 5, 'val' : 'crayon'}, {'id' : 6, 'val' : 'camera'}]
|
||
call assert_equal([[{'id' : 6, 'val' : 'camera'}], [[0, 1, 2]], [2885]],
|
||
\ matchfuzzypos(l, 'cam', {'text_cb' : {v -> v.val}}))
|
||
call assert_equal([[{'id' : 6, 'val' : 'camera'}], [[0, 1, 2]], [2885]],
|
||
\ matchfuzzypos(l, 'cam', {'key' : 'val'}))
|
||
call assert_equal([[], [], []], matchfuzzypos(l, 'day', {'text_cb' : {v -> v.val}}))
|
||
call assert_equal([[], [], []], matchfuzzypos(l, 'day', {'key' : 'val'}))
|
||
call assert_fails("let x = matchfuzzypos(l, 'cam', 'random')", 'E1206:')
|
||
call assert_equal([[], [], []], matchfuzzypos(l, 'day', {'text_cb' : {v -> []}}))
|
||
call assert_equal([[], [], []], matchfuzzypos(l, 'day', {'text_cb' : {v -> 1}}))
|
||
call assert_fails("let x = matchfuzzypos(l, 'day', {'text_cb' : {a, b -> 1}})", 'E119:')
|
||
call assert_equal([[], [], []], matchfuzzypos(l, 'cam'))
|
||
" Nvim's callback implementation is different, so E6000 is expected instead,
|
||
" call assert_fails("let x = matchfuzzypos(l, 'cam', {'text_cb' : []})", 'E921:')
|
||
call assert_fails("let x = matchfuzzypos(l, 'cam', {'text_cb' : []})", 'E6000:')
|
||
call assert_fails("let x = matchfuzzypos(l, 'foo', {'key' : 123})", 'E475: Invalid value for argument key: 123')
|
||
call assert_fails("let x = matchfuzzypos(l, 'foo', {'key' : []})", 'E730:')
|
||
call assert_fails("let x = matchfuzzypos(l, 'cam', v:_null_dict)", 'E1297:')
|
||
call assert_fails("let x = matchfuzzypos(l, 'foo', {'key' : v:_null_string})", 'E475:')
|
||
" Nvim doesn't have null functions
|
||
" call assert_fails("let x = matchfuzzypos(l, 'foo', {'text_cb' : test_null_function()})", 'E475:')
|
||
|
||
" case match
|
||
call assert_equal([['Match'], [[0, 1]], [1885]], matchfuzzypos(['match', 'Match'], 'Ma'))
|
||
call assert_equal([['match', 'Match'], [[0, 1], [0, 1]], [1885, 1885]], matchfuzzypos(['Match', 'match'], 'ma'))
|
||
|
||
let l = [{'id' : 5, 'name' : 'foo'}, {'id' : 6, 'name' : []}, {'id' : 7}]
|
||
call assert_fails("let x = matchfuzzypos(l, 'foo', {'key' : 'name'})", 'E730:')
|
||
|
||
" camelcase
|
||
call assert_equal([['Cursor', 'CurSearch', 'CursorLine', 'lCursor', 'shCurlyIn', 'shCurlyError', 'TracesCursor'], [[0, 1, 2], [0, 1, 2], [0, 1, 2], [1, 2, 3], [2, 3, 4], [2, 3, 4], [6, 7, 8]], [2885, 2870, 2865, 2680, 2670, 2655, 2655]],
|
||
\ matchfuzzypos(['Cursor', 'lCursor', 'shCurlyIn', 'shCurlyError', 'TracesCursor', 'CurSearch', 'CursorLine'], 'Cur'))
|
||
call assert_equal([['things', 'sThings', 'thisThings'], [[0, 1, 2, 3], [1, 2, 3, 4], [0, 1, 6, 7]], [3890, 3685, 3670]],
|
||
\ matchfuzzypos(['things','sThings', 'thisThings'], 'thin'))
|
||
endfunc
|
||
|
||
" Test for matchfuzzy() with multibyte characters
|
||
func Test_matchfuzzy_mbyte()
|
||
CheckFeature multi_lang
|
||
call assert_equal(['ンヹㄇヺヴ'], matchfuzzy(['ンヹㄇヺヴ'], 'ヹヺ'))
|
||
" reverse the order of characters
|
||
call assert_equal([], matchfuzzy(['ンヹㄇヺヴ'], 'ヺヹ'))
|
||
call assert_equal(['αβΩxxx', 'xαxβxΩx'],
|
||
\ matchfuzzy(['αβΩxxx', 'xαxβxΩx'], 'αβΩ'))
|
||
call assert_equal(['ππbbππ', 'πππbbbπππ', 'ππππbbbbππππ', 'πbπ'],
|
||
\ matchfuzzy(['πbπ', 'ππbbππ', 'πππbbbπππ', 'ππππbbbbππππ'], 'ππ'))
|
||
|
||
" match multiple words (separated by space)
|
||
call assert_equal(['세 마리의 작은 돼지'], ['세 마리의 작은 돼지', '마리의', '마리의 작은', '작은 돼지']->matchfuzzy('돼지 마리의'))
|
||
call assert_equal([], ['세 마리의 작은 돼지', '마리의', '마리의 작은', '작은 돼지']->matchfuzzy('파란 하늘'))
|
||
|
||
" camel case match
|
||
call assert_equal(['oneąwo', 'oneĄwo'],
|
||
\ ['oneĄwo', 'oneąwo']->matchfuzzy('oneąwo'))
|
||
call assert_equal(['oneĄwo'],
|
||
\ ['oneĄwo', 'oneąwo']->matchfuzzy('Ąwo'))
|
||
" prefer camelcase when searched first character matches upper case
|
||
call assert_equal(['oneĄwo', 'oneąwo'],
|
||
\ ['oneĄwo', 'oneąwo']->matchfuzzy('ąw'))
|
||
" preference for complete match then match after separator (_ or space)
|
||
call assert_equal(['ⅠⅡabㄟㄠ'] + sort(['ⅠⅡa_bㄟㄠ', 'ⅠⅡa bㄟㄠ']),
|
||
\ ['ⅠⅡabㄟㄠ', 'ⅠⅡa bㄟㄠ', 'ⅠⅡa_bㄟㄠ']->matchfuzzy('ⅠⅡabㄟㄠ'))
|
||
" preference for match after a separator (_ or space)
|
||
call assert_equal(['ㄓㄔabㄟㄠ', 'ㄓㄔa_bㄟㄠ', 'ㄓㄔa bㄟㄠ'],
|
||
\ ['ㄓㄔa_bㄟㄠ', 'ㄓㄔa bㄟㄠ', 'ㄓㄔabㄟㄠ']->matchfuzzy('ㄓㄔabㄟㄠ'))
|
||
" preference for leading letter match
|
||
call assert_equal(['ŗŝţũŵż', 'xŗŝţũŵż'],
|
||
\ ['xŗŝţũŵż', 'ŗŝţũŵż']->matchfuzzy('ŗŝţũŵż'))
|
||
" preference for sequential match
|
||
call assert_equal(['ㄞㄡㄤfffifl', 'ㄞaㄡbㄤcffdfiefl'],
|
||
\ ['ㄞaㄡbㄤcffdfiefl', 'ㄞㄡㄤfffifl']->matchfuzzy('ㄞㄡㄤfffifl'))
|
||
" non-matching leading letter(s) penalty
|
||
call assert_equal(['xㄞㄡㄤfffifl', 'xxㄞㄡㄤfffifl'],
|
||
\ ['xxㄞㄡㄤfffifl', 'xㄞㄡㄤfffifl']->matchfuzzy('ㄞㄡㄤfffifl'))
|
||
" total non-matching letter(s) penalty
|
||
call assert_equal(['ŗŝţ', 'ŗŝţx', 'ŗŝţxx'],
|
||
\ ['ŗŝţxx', 'ŗŝţ', 'ŗŝţx']->matchfuzzy('ŗŝţ'))
|
||
endfunc
|
||
|
||
" Test for matchfuzzypos() with multibyte characters
|
||
func Test_matchfuzzypos_mbyte()
|
||
CheckFeature multi_lang
|
||
call assert_equal([['こんにちは世界'], [[0, 1, 2, 3, 4]], [4890]],
|
||
\ matchfuzzypos(['こんにちは世界'], 'こんにちは'))
|
||
call assert_equal([['ンヹㄇヺヴ'], [[1, 3]], [-20]], matchfuzzypos(['ンヹㄇヺヴ'], 'ヹヺ'))
|
||
" reverse the order of characters
|
||
call assert_equal([[], [], []], matchfuzzypos(['ンヹㄇヺヴ'], 'ヺヹ'))
|
||
call assert_equal([['αβΩxxx', 'xαxβxΩx'], [[0, 1, 2], [1, 3, 5]], [2885, 670]],
|
||
\ matchfuzzypos(['αβΩxxx', 'xαxβxΩx'], 'αβΩ'))
|
||
call assert_equal([['ππbbππ', 'πππbbbπππ', 'ππππbbbbππππ', 'πbπ'],
|
||
\ [[0, 1], [0, 1], [0, 1], [0, 2]], [1880, 1865, 1850, 890]],
|
||
\ matchfuzzypos(['πbπ', 'ππbbππ', 'πππbbbπππ', 'ππππbbbbππππ'], 'ππ'))
|
||
call assert_equal([['ααααααα'], [[0, 1, 2]], [2880]],
|
||
\ matchfuzzypos(['ααααααα'], 'ααα'))
|
||
|
||
call assert_equal([[], [], []], matchfuzzypos(['ンヹㄇ', 'ŗŝţ'], 'fffifl'))
|
||
let x = matchfuzzypos([repeat('Ψ', 256)], repeat('Ψ', 256))
|
||
call assert_equal(range(256), x[1][0])
|
||
call assert_equal([repeat('✓', 300)], matchfuzzypos([repeat('✓', 300)], repeat('✓', 257))[0])
|
||
|
||
" match multiple words (separated by space)
|
||
call assert_equal([['세 마리의 작은 돼지'], [[9, 10, 2, 3, 4]], [4515]], ['세 마리의 작은 돼지', '마리의', '마리의 작은', '작은 돼지']->matchfuzzypos('돼지 마리의'))
|
||
call assert_equal([[], [], []], ['세 마리의 작은 돼지', '마리의', '마리의 작은', '작은 돼지']->matchfuzzypos('파란 하늘'))
|
||
|
||
" match in a long string
|
||
call assert_equal([[repeat('ぶ', 300) .. 'ẼẼẼ'], [[300, 301, 302]], [500]],
|
||
\ matchfuzzypos([repeat('ぶ', 300) .. 'ẼẼẼ'], 'ẼẼẼ'))
|
||
" preference for match after a separator (_ or space)
|
||
call assert_equal([['xちだx_ちだ'], [[5, 6]], [1775]], matchfuzzypos(['xちだx_ちだ'], 'ちだ'))
|
||
" preference for leading letter match
|
||
call assert_equal([['ѳѵҁxѳѵҁ'], [[0, 1]], [1875]], matchfuzzypos(['ѳѵҁxѳѵҁ'], 'ѳѵ'))
|
||
" preference for sequential match
|
||
call assert_equal([['aンbヹcㄇdンヹㄇ'], [[7, 8, 9]], [1965]], matchfuzzypos(['aンbヹcㄇdンヹㄇ'], 'ンヹㄇ'))
|
||
" best recursive match
|
||
call assert_equal([['xффйд'], [[2, 3, 4]], [1990]], matchfuzzypos(['xффйд'], 'фйд'))
|
||
endfunc
|
||
|
||
" Test for matchfuzzy() with limit
|
||
func Test_matchfuzzy_limit()
|
||
let x = ['1', '2', '3', '2']
|
||
call assert_equal(['2', '2'], x->matchfuzzy('2'))
|
||
call assert_equal(['2', '2'], x->matchfuzzy('2', #{}))
|
||
call assert_equal(['2', '2'], x->matchfuzzy('2', #{limit: 0}))
|
||
call assert_equal(['2'], x->matchfuzzy('2', #{limit: 1}))
|
||
call assert_equal(['2', '2'], x->matchfuzzy('2', #{limit: 2}))
|
||
call assert_equal(['2', '2'], x->matchfuzzy('2', #{limit: 3}))
|
||
call assert_fails("call matchfuzzy(x, '2', #{limit: '2'})", 'E475:')
|
||
call assert_fails("call matchfuzzy(x, '2', #{limit: []})", 'E475:')
|
||
|
||
let l = [{'id': 5, 'val': 'crayon'}, {'id': 6, 'val': 'camera'}]
|
||
call assert_equal([{'id': 5, 'val': 'crayon'}, {'id': 6, 'val': 'camera'}], l->matchfuzzy('c', #{text_cb: {v -> v.val}}))
|
||
call assert_equal([{'id': 5, 'val': 'crayon'}, {'id': 6, 'val': 'camera'}], l->matchfuzzy('c', #{key: 'val'}))
|
||
call assert_equal([{'id': 5, 'val': 'crayon'}, {'id': 6, 'val': 'camera'}], l->matchfuzzy('c', #{text_cb: {v -> v.val}, limit: 0}))
|
||
call assert_equal([{'id': 5, 'val': 'crayon'}, {'id': 6, 'val': 'camera'}], l->matchfuzzy('c', #{key: 'val', limit: 0}))
|
||
call assert_equal([{'id': 5, 'val': 'crayon'}], l->matchfuzzy('c', #{text_cb: {v -> v.val}, limit: 1}))
|
||
call assert_equal([{'id': 5, 'val': 'crayon'}], l->matchfuzzy('c', #{key: 'val', limit: 1}))
|
||
endfunc
|
||
|
||
" This was using uninitialized memory
|
||
func Test_matchfuzzy_initialized()
|
||
CheckRunVimInTerminal
|
||
|
||
" This can take a very long time (esp. when using valgrind). Run in a
|
||
" separate Vim instance and kill it after two seconds. We only check for
|
||
" memory errors.
|
||
let lines =<< trim END
|
||
lvimgrep [ss [fg*
|
||
END
|
||
call writefile(lines, 'XTest_matchfuzzy', 'D')
|
||
|
||
let buf = RunVimInTerminal('-u NONE -X -Z', {})
|
||
call term_sendkeys(buf, ":source XTest_matchfuzzy\n")
|
||
call TermWait(buf, 2000)
|
||
|
||
let job = term_getjob(buf)
|
||
if job_status(job) == "run"
|
||
call job_stop(job, "int")
|
||
call TermWait(buf, 50)
|
||
endif
|
||
|
||
" clean up
|
||
call StopVimInTerminal(buf)
|
||
endfunc
|
||
|
||
" vim: shiftwidth=2 sts=2 expandtab
|