在我的 Neovim 配置中, 一直使用的是 nvim-cmp 作为补全引擎, 由于其默认支持模糊查找, 因而补全列表中可能会出现前缀匹配优先级不如子序列的乱序问题, 举一个例子:
-
补全候选项中有 abc_variable 和 xaxbx 这两个词
-
输入
ab, nvim-cmp 根据传入的比较函数进行逐个比较与排序; 但由于默认支持模糊查找, 且官方的补全函数中貌似没有前缀匹配优先的规定, 而我自己很合理地又添加了一个根据长度排序的比较函数, 因而在补全列表中, 子序列xaxbx反而会获得更高的优先级出现在第一个, 这是极为不合理的.
大概在一年前配置这套补全规则的时候就发现了这个问题, 当时的方案是将补全项和输入字串做一个最长公共前缀的长度计算, 越长的优先级越高, 貌似一直还是相安无事的..
1utils.prefix_cnt = function(s1, s2)
2 if(s1 == nil or type(s1) ~= "string") then return 0 end
3 if(s2 == nil or type(s2) ~= "string") then return 0 end
4
5 local len = math.min(#s1, #s2)
6 local cnt = 0
7 for i = 1, len, 1 do
8 if(s1:sub(i, i) == s2:sub(i,i)) then
9 cnt = cnt + 1
10 else break end
11 end
12 return cnt
13end直到最近在写一些 C++ 代码的时候, 访问类的成员函数时又会出现一些补全项的乱序问题, 下图是一个简化的问题复现(无C++语义, 仅作为字符串展示):
输入 b 后, bbbbbb 并没有理所应当的获胜, 反而是子序列的优先级更高. 反复审查了一下上述的前缀计算函数, 感觉没什么问题, 打印了一下日志, 发现这几个补全项的计算结果都是 0 !
问题的原因在于进行比较的 输入字符串 并不是 b, 而是 a.b, 这与 lua vim 获取光标前的字符串函数有关, 该函数也是开国老将了, 最开始配置的时候从别的某个地方毛下来的:
1utils.words_before_cursor = function()
2 local _ = vim.api.nvim_win_get_cursor(0)
3 local row = _[1]
4 local col = _[2]
5
6 if col == 0 then return nil end
7 local word = vim.api.nvim_buf_get_lines(0, row - 1, row, true)[1]:sub(0, col):match("[^%s]+$")
8 return word
9end一个解决方案是修改 words_before_cursor 函数, 让其对于一些特殊标点做分隔, 比如这里的成员访问运算符 ., 分隔后再对尾节点做前缀长度计算, 但是总感觉会不会不太优雅, 后续如果又有一个 rqd 语言或者一些特殊的场景使用@, # 作为分隔符的话, 难不成还得每个都硬编码一次..
不打算修改上述函数的话, 就不能计算公共前缀长度了, 另一个想到的办法就是用KMP算法的思想计算最长公共前后缀, 这是极为合理的: 在最开始的问题中, 只需要分别计算 bbbbbba.b 以及 zz_zzba.b 的最长公共前后缀的长度, 就可以无论分隔符是什么都能较好地让候选项符合预期了.
另外, 应该也不用太担心该算法在某些corner case下会出现新的乱序问题, 因为我尝试构造了半天, 感觉都没有找到一组例子能hack该方法, lgtm, 就认为是还不错的了, 后续如果遇到问题了再更新吧~
计算的 Lua 代码如下, 参考 < 前缀函数与 KMP 算法 - OI Wiki>:
lua字符串随机访问单个字符需要substr(i, i), 太丑了索性直接转换成table了(大雾
1utils.longest_common_prefix_suffix = function(s_)
2 local s = {}
3 for i = 1, #s_, 1 do
4 s[i] = string.sub(s_, i, i)
5 end
6
7 local n = #s;
8 local pi = {}
9 for i = 1, n, 1 do
10 pi[i] = 0
11 end
12 for i = 2, n, 1 do
13 local j = pi[i - 1] + 1
14 while j > 1 and s[i] ~= s[j] do
15 j = pi[j - 1]
16 end
17 if s[i] == s[j] then
18 pi[i] = j
19 end
20 end
21
22 return pi[n]
23end