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.

2 files changed, 203 insertions, 26 deletions

diff --git a/src/nvim/testdir/test_functions.vim b/src/nvim/testdir/test_functions.vim
index 57ae0d3020..438bed51c6 100644
--- a/src/nvim/testdir/test_functions.vim
+++ b/src/nvim/testdir/test_functions.vim
@@ -1731,32 +1731,6 @@ func Test_nr2char()
   call assert_equal("\x80\xfc\b\xfd\x80\xfeX\x80\xfeX\x80\xfeX\x80\xfeX\x80\xfeX", eval('"\<M-' .. nr2char(0x40000000) .. '>"'))
 endfunc
 
-" Test for matchfuzzy()
-func Test_matchfuzzy()
-  call assert_fails('call matchfuzzy(10, "abc")', 'E714:')
-  " Needs v8.2.1183.
-  " call assert_fails('call matchfuzzy(["abc"], [])', 'E730:')
-  call assert_fails('call matchfuzzy(["abc"], [])', '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', 'onetwo'], matchfuzzy(['onetwo', 'oneTwo'], 'oneTwo'))
-  call assert_equal(['one_two', 'onetwo'], matchfuzzy(['onetwo', 'one_two'], 'oneTwo'))
-  call assert_equal(['aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'], matchfuzzy(['aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'], 'aa'))
-  call assert_equal([], matchfuzzy([repeat('a', 300)], repeat('a', 257)))
-
-  %bw!
-  eval ['somebuf', 'anotherone', 'needle', 'yetanotherone']->map({_, v -> bufadd(v) + bufload(v)})
-  let l = getbufinfo()->map({_, v -> v.name})->matchfuzzy('ndl')
-  call assert_equal(1, len(l))
-  call assert_match('needle', l[0])
-endfunc
-
 " Test for getcurpos() and setpos()
 func Test_getcurpos_setpos()
   new
diff --git a/src/nvim/testdir/test_matchfuzzy.vim b/src/nvim/testdir/test_matchfuzzy.vim
new file mode 100644
index 0000000000..4390852639
--- /dev/null
+++ b/src/nvim/testdir/test_matchfuzzy.vim
@@ -0,0 +1,203 @@
+" Tests for fuzzy matching
+
+source shared.vim
+source check.vim
+
+" Test for matchfuzzy()
+func Test_matchfuzzy()
+  call assert_fails('call matchfuzzy(10, "abc")', 'E686:')
+  " Needs v8.2.1183; match the final error that's thrown for now
+  " call assert_fails('call matchfuzzy(["abc"], [])', 'E730:')
+  call assert_fails('call matchfuzzy(["abc"], [])', 'E475:')
+  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', 'onetwo'], matchfuzzy(['onetwo', 'oneTwo'], 'oneTwo'))
+  call assert_equal(['one_two', 'onetwo'], 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([], matchfuzzy([repeat('a', 300)], repeat('a', 257)))
+
+  " Tests for match preferences
+  " preference for camel case match
+  call assert_equal(['oneTwo', 'onetwo'], ['onetwo', 'oneTwo']->matchfuzzy('onetwo'))
+  " preference for match after a separator (_ or space)
+  call assert_equal(['one_two', 'one two', 'onetwo'], ['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'))
+
+  %bw!
+  eval ['somebuf', 'anotherone', 'needle', 'yetanotherone']->map({_, v -> bufadd(v) + bufload(v)})
+  let l = getbufinfo()->map({_, v -> v.name})->matchfuzzy('ndl')
+  call assert_equal(1, len(l))
+  call assert_match('needle', l[0])
+
+  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')", 'E715:')
+  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,
+  " but we need v8.2.1183 to assert it
+  " 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, 'cam', {'text_cb' : []})", 'E475:')
+  " call assert_fails("let x = matchfuzzy(l, 'foo', {'key' : []})", 'E730:')
+  call assert_fails("let x = matchfuzzy(l, 'foo', {'key' : []})", 'E475:')
+  call assert_fails("let x = matchfuzzy(l, 'cam', v:_null_dict)", 'E715:')
+  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:')
+
+  let l = [{'id' : 5, 'name' : 'foo'}, {'id' : 6, 'name' : []}, {'id' : 7}]
+  call assert_fails("let x = matchfuzzy(l, 'foo', {'key' : 'name'})", 'E730:')
+
+  " 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 fuzzymatchpos() function
+func Test_matchfuzzypos()
+  call assert_equal([['curl', 'world'], [[2,3], [2,3]]], matchfuzzypos(['world', 'curl'], 'rl'))
+  call assert_equal([['curl', 'world'], [[2,3], [2,3]]], matchfuzzypos(['world', 'one', 'curl'], 'rl'))
+  call assert_equal([['hello', 'hello world hello world'],
+        \ [[0, 1, 2, 3, 4], [0, 1, 2, 3, 4]]],
+        \ matchfuzzypos(['hello world hello world', 'hello', 'world'], 'hello'))
+  call assert_equal([['aaaaaaa'], [[0, 1, 2]]], matchfuzzypos(['aaaaaaa'], 'aaa'))
+  call assert_equal([[], []], matchfuzzypos(['world', 'curl'], 'ab'))
+  let x = matchfuzzypos([repeat('a', 256)], repeat('a', 256))
+  call assert_equal(range(256), x[1][0])
+  call assert_equal([[], []], matchfuzzypos([repeat('a', 300)], repeat('a', 257)))
+  call assert_equal([[], []], matchfuzzypos([], 'abc'))
+
+  " match in a long string
+  call assert_equal([[repeat('x', 300) .. 'abc'], [[300, 301, 302]]],
+        \ matchfuzzypos([repeat('x', 300) .. 'abc'], 'abc'))
+
+  " preference for camel case match
+  call assert_equal([['xabcxxaBc'], [[6, 7, 8]]], matchfuzzypos(['xabcxxaBc'], 'abc'))
+  " preference for match after a separator (_ or space)
+  call assert_equal([['xabx_ab'], [[5, 6]]], matchfuzzypos(['xabx_ab'], 'ab'))
+  " preference for leading letter match
+  call assert_equal([['abcxabc'], [[0, 1]]], matchfuzzypos(['abcxabc'], 'ab'))
+  " preference for sequential match
+  call assert_equal([['aobncedone'], [[7, 8, 9]]], matchfuzzypos(['aobncedone'], 'one'))
+  " best recursive match
+  call assert_equal([['xoone'], [[2, 3, 4]]], matchfuzzypos(['xoone'], 'one'))
+
+  let l = [{'id' : 5, 'val' : 'crayon'}, {'id' : 6, 'val' : 'camera'}]
+  call assert_equal([[{'id' : 6, 'val' : 'camera'}], [[0, 1, 2]]],
+        \ matchfuzzypos(l, 'cam', {'text_cb' : {v -> v.val}}))
+  call assert_equal([[{'id' : 6, 'val' : 'camera'}], [[0, 1, 2]]],
+        \ 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')", 'E715:')
+  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,
+  " but we need v8.2.1183 to assert it
+  " 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, 'cam', {'text_cb' : []})", 'E475:')
+  " call assert_fails("let x = matchfuzzypos(l, 'foo', {'key' : []})", 'E730:')
+  call assert_fails("let x = matchfuzzypos(l, 'foo', {'key' : []})", 'E475:')
+  call assert_fails("let x = matchfuzzypos(l, 'cam', v:_null_dict)", 'E715:')
+  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:')
+
+  let l = [{'id' : 5, 'name' : 'foo'}, {'id' : 6, 'name' : []}, {'id' : 7}]
+  call assert_fails("let x = matchfuzzypos(l, 'foo', {'key' : 'name'})", 'E730:')
+endfunc
+
+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ππππ'], 'ππ'))
+
+  " preference for camel case match
+  call assert_equal(['oneĄwo', 'oneąwo'],
+        \ ['oneąwo', 'oneĄwo']->matchfuzzy('oneąwo'))
+  " preference for match after a separator (_ or space)
+  call assert_equal(['ⅠⅡa_bㄟㄠ', 'ⅠⅡa bㄟㄠ', 'ⅠⅡabㄟㄠ'],
+        \ ['ⅠⅡabㄟㄠ', 'ⅠⅡa_bㄟㄠ', 'ⅠⅡa bㄟㄠ']->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
+
+func Test_matchfuzzypos_mbyte()
+  CheckFeature multi_lang
+  call assert_equal([['こんにちは世界'], [[0, 1, 2, 3, 4]]],
+        \ matchfuzzypos(['こんにちは世界'], 'こんにちは'))
+  call assert_equal([['ンヹㄇヺヴ'], [[1, 3]]], matchfuzzypos(['ンヹㄇヺヴ'], 'ヹヺ'))
+  " reverse the order of characters
+  call assert_equal([[], []], matchfuzzypos(['ンヹㄇヺヴ'], 'ヺヹ'))
+  call assert_equal([['αβΩxxx', 'xαxβxΩx'], [[0, 1, 2], [1, 3, 5]]],
+        \ matchfuzzypos(['αβΩxxx', 'xαxβxΩx'], 'αβΩ'))
+  call assert_equal([['ππbbππ', 'πππbbbπππ', 'ππππbbbbππππ', 'πbπ'],
+        \ [[0, 1], [0, 1], [0, 1], [0, 2]]],
+        \ matchfuzzypos(['πbπ', 'ππbbππ', 'πππbbbπππ', 'ππππbbbbππππ'], 'ππ'))
+  call assert_equal([['ααααααα'], [[0, 1, 2]]],
+        \ matchfuzzypos(['ααααααα'], 'ααα'))
+
+  call assert_equal([[], []], matchfuzzypos(['ンヹㄇ', 'ŗŝţ'], 'fffifl'))
+  let x = matchfuzzypos([repeat('Ψ', 256)], repeat('Ψ', 256))
+  call assert_equal(range(256), x[1][0])
+  call assert_equal([[], []], matchfuzzypos([repeat('✓', 300)], repeat('✓', 257)))
+
+  " match in a long string
+  call assert_equal([[repeat('♪', 300) .. '✗✗✗'], [[300, 301, 302]]],
+        \ matchfuzzypos([repeat('♪', 300) .. '✗✗✗'], '✗✗✗'))
+  " preference for camel case match
+  call assert_equal([['xѳѵҁxxѳѴҁ'], [[6, 7, 8]]], matchfuzzypos(['xѳѵҁxxѳѴҁ'], 'ѳѵҁ'))
+  " preference for match after a separator (_ or space)
+  call assert_equal([['xちだx_ちだ'], [[5, 6]]], matchfuzzypos(['xちだx_ちだ'], 'ちだ'))
+  " preference for leading letter match
+  call assert_equal([['ѳѵҁxѳѵҁ'], [[0, 1]]], matchfuzzypos(['ѳѵҁxѳѵҁ'], 'ѳѵ'))
+  " preference for sequential match
+  call assert_equal([['aンbヹcㄇdンヹㄇ'], [[7, 8, 9]]], matchfuzzypos(['aンbヹcㄇdンヹㄇ'], 'ンヹㄇ'))
+  " best recursive match
+  call assert_equal([['xффйд'], [[2, 3, 4]]], matchfuzzypos(['xффйд'], 'фйд'))
+endfunc
+
+" vim: shiftwidth=2 sts=2 expandtab