Repository navigation
Expand file tree
/
Copy pathfuzzy.lua
More file actions
365 lines (321 loc) · 13.3 KB
/
Copy pathfuzzy.lua
File metadata and controls
365 lines (321 loc) · 13.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
-- MIT License Copyright (c) 2021 Evgeni Chasnovski
-- Documentation ==============================================================
---@brief [[
--- Lua module which implements minimal and fast fuzzy matching.
---
--- # Setup
---
--- This module doesn't need setup, but it can be done to improve usability.
--- Setup with `require('mini.fuzzy').setup({})` (replace `{}` with your
--- `config` table). It will create global Lua table `MiniFuzzy` which you can
--- use for scripting or manually (with `:lua MiniFuzzy.*`).
---
--- Default `config`:
--- <code>
--- {
--- -- Maximum allowed value of match features (width and first match). All
--- -- feature values greater than cutoff can be considered "equally bad".
--- cutoff = 100,
--- }
--- </code>
--- # Notes
--- 1. Currently there is no explicit design to work with multibyte symbols,
--- but simple examples should work.
--- 2. Smart case is used: case insensitive if input word (which is usually a
--- user input) is all lower ase. Case sensitive otherwise.
---
--- # Algorithm design
---
--- General design uses only width of found match and index of first letter
--- match. No special characters or positions (like in fzy and fzf) are used.
---
--- Given input `word` and target `candidate`:
--- - The goal is to find matching between `word`'s letters and letters in
--- `candidate`, which minimizes certain score. It is assumed that order of
--- letters in `word` and those matched in `candidate` should be the same.
--- - Matching is represented by matched positions: an array `positions` of
--- integers with length equal to number of letter in `word`. The following
--- should be always true in case of a match: `candidate`'s letter at index
--- `positions[i]` is letters[i]` for all valid `i`.
--- - Matched positions are evaluated based only on two features: their width
--- (number of indexes between first and last positions) and first match
--- (index of first letter match). There is a global setting `cutoff` for
--- which all feature values greater than it can be considered "equally bad".
--- - Score of matched positions is computed with following explicit formula:
--- `cutoff * min(width, cutoff) + min(first, cutoff)`. It is designed to be
--- equivalent to first comparing widths (lower is better) and then comparing
--- first match (lower is better). For example, if `word = 'time'`:
--- - '_time' (width 4) will have a better match than 't_ime' (width 5).
--- - 'time_a' (width 4, first 1) will have a better match than 'a_time'
--- (width 4, first 3).
--- - Final matched positions are those which minimize score among all possible
--- matched positions of `word` and `candidate`.
---@brief ]]
---@tag MiniFuzzy mini.fuzzy
-- Module definition ==========================================================
local MiniFuzzy = {}
local H = {}
--- Module setup
---
---@param config table: Module config table.
---@usage `require('mini.fuzzy').setup({})` (replace `{}` with your `config` table)
function MiniFuzzy.setup(config)
-- Export module
_G.MiniFuzzy = MiniFuzzy
-- Setup config
config = H.setup_config(config)
-- Apply config
H.apply_config(config)
end
MiniFuzzy.config = {
-- Maximum allowed value of match features (width and first match). All
-- feature values greater than cutoff can be considered "equally bad".
cutoff = 100,
}
-- Module functionality =======================================================
--- Compute match data of input `word` and `candidate` strings
---
--- It tries to find best match for input string `word` (usually user input)
--- and string `candidate`. Returns table with elements:
--- - `positions` - array with letter indexes inside `candidate` which
--- matched to corresponding letters in `word`. Or `nil` if no match.
--- - `score` - positive number representing how good the match is (lower is
--- better). Or `-1` if no match.
---
---@param word string: Input word (usually user input).
---@param candidate string: Target word (usually with which matching is done).
---@return table: Table with matching information (see function's description).
function MiniFuzzy.match(word, candidate)
-- Use 'smart case'
candidate = (word == word:lower()) and candidate:lower() or candidate
local positions = H.find_best_positions(H.string_to_letters(word), candidate)
return { positions = positions, score = H.score_positions(positions) }
end
--- Filter string array
---
--- This leaves only those elements of input array which matched with `word`
--- and sorts from best to worst matches (based on score and index in original
--- array, both lower is better).
---
---@param word string: String which will be searched.
---@param candidate_array table: Lua array of strings inside which word will be searched.
---@return tuple: Arrays of matched candidates and their indexes in original input.
function MiniFuzzy.filtersort(word, candidate_array)
-- Use 'smart case'. Create new array to preserve input for later filtering
local cand_array
if word ~= word:lower() then
cand_array = vim.tbl_map(string.lower, candidate_array)
else
cand_array = candidate_array
end
local filter_ids = H.make_filter_indexes(word, cand_array)
table.sort(filter_ids, H.compare_filter_indexes)
return H.filter_by_indexes(candidate_array, filter_ids)
end
--- Fuzzy matching for |MiniCompletion.lsp_completion.process_items|
---
---@param items table: Lua array with LSP 'textDocument/completion' response items.
---@param base string: Word to complete.
function MiniFuzzy.process_lsp_items(items, base)
-- Extract completion words from items
local words = vim.tbl_map(function(x)
if type(x.textEdit) == 'table' and x.textEdit.newText then
return x.textEdit.newText
end
return x.insertText or x.label or ''
end, items)
-- Fuzzy match
local _, match_inds = MiniFuzzy.filtersort(base, words)
return vim.tbl_map(function(i)
return items[i]
end, match_inds)
end
--- Custom getter for `telescope.nvim` sorter
---
--- Designed to be used as value for |telescope.defaults.file_sorter| and
--- |telescope.defaults.generic_sorter| inside `setup()` call.
---
---@param opts table: Options (currently not used).
---@usage `require('telescope').setup({defaults = {generic_sorter = require('mini.fuzzy').get_telescope_sorter}})`
function MiniFuzzy.get_telescope_sorter(opts)
opts = opts or {}
return require('telescope.sorters').Sorter:new({
start = function(self, prompt)
-- Cache prompt's letters
self.letters = H.string_to_letters(prompt)
-- Use 'smart case': insensitive if `prompt` is lowercase
self.case_sensitive = prompt ~= prompt:lower()
end,
-- @param self
-- @param prompt (which is the text on the line)
-- @param line (entry.ordinal)
-- @param entry (the whole entry)
scoring_function = function(self, _, line, _)
if #self.letters == 0 then
return 1
end
line = self.case_sensitive and line or line:lower()
local positions = H.find_best_positions(self.letters, line)
return H.score_positions(positions)
end,
-- Currently there doesn't seem to be a proper way to cache matched
-- positions from inside of `scoring_function` (see `highlighter` code of
-- `get_fzy_sorter`'s output). Besides, it seems that `display` and `line`
-- arguments might be different. So, extra calls to `match` are made.
highlighter = function(self, _, display)
if #self.letters == 0 or #display == 0 then
return {}
end
display = self.case_sensitive and display or display:lower()
return H.find_best_positions(self.letters, display)
end,
})
end
-- Helper data ================================================================
-- Module default config
H.default_config = MiniFuzzy.config
-- Helper functionality =======================================================
-- Settings -------------------------------------------------------------------
function H.setup_config(config)
-- General idea: if some table elements are not present in user-supplied
-- `config`, take them from default config
vim.validate({ config = { config, 'table', true } })
config = vim.tbl_deep_extend('force', H.default_config, config or {})
vim.validate({
cutoff = {
config.cutoff,
function(x)
return type(x) == 'number' and x >= 1
end,
'number not less than 1',
},
})
return config
end
function H.apply_config(config)
MiniFuzzy.config = config
end
-- Fuzzy matching -------------------------------------------------------------
---@param letters string[] Array of letters from input word
---@param candidate string String of interest
---
---@return table Table with matched positions (in `candidate`) if there is a
--- match, `nil` otherwise.
---@private
function H.find_best_positions(letters, candidate)
local n_candidate, n_letters = #candidate, #letters
if n_letters == 0 or n_candidate < n_letters then
return nil
end
-- Search forward to find matching positions with left-most last letter match
local pos_last = 0
for let_i = 1, #letters do
pos_last = candidate:find(letters[let_i], pos_last + 1)
if not pos_last then
break
end
end
-- Candidate is matched only if word's last letter is found
if not pos_last then
return nil
end
-- If there is only one letter, it is already the best match (there will not
-- be better width and it has lowest first match)
if n_letters == 1 then
return { pos_last }
end
-- Compute best match positions by iteratively checking all possible last
-- letter matches (at and after initial one). At end of each iteration
-- `best_pos_last` holds best match for last letter among all previously
-- checked such matches.
local best_pos_last, best_width = pos_last, math.huge
local rev_candidate = candidate:reverse()
while pos_last do
-- Simulate computing best match positions ending exactly at `pos_last` by
-- going backwards from current last letter match. This works because it
-- minimizes width which is the only way to find match with lower score.
-- Not actually creating table with positions and then directly computing
-- score increases speed by up to 40% (on small frequent input word with
-- relatively wide candidate, such as file paths of nested directories).
local rev_first = n_candidate - pos_last + 1
for i = #letters - 1, 1, -1 do
rev_first = rev_candidate:find(letters[i], rev_first + 1)
end
local first = n_candidate - rev_first + 1
local width = math.min(pos_last - first + 1, MiniFuzzy.config.cutoff)
-- Using strict sign is crucial because when two last letter matches result
-- into positions with similar width, the one which was created earlier
-- (i.e. with smaller last letter match) will have smaller first letter
-- match (hence better score).
if width < best_width then
best_pos_last, best_width = pos_last, width
end
-- Advance iteration
pos_last = candidate:find(letters[n_letters], pos_last + 1)
end
-- Actually compute best matched positions from best last letter match
local best_positions = { best_pos_last }
local rev_pos = n_candidate - best_pos_last + 1
for i = #letters - 1, 1, -1 do
rev_pos = rev_candidate:find(letters[i], rev_pos + 1)
-- For relatively small number of letters (around 10, which is main use
-- case) inserting to front seems to have better performance than
-- inserting at end and then reversing.
table.insert(best_positions, 1, n_candidate - rev_pos + 1)
end
return best_positions
end
-- Compute score of matched positions. Smaller values indicate better match
-- (i.e. like distance). Reasoning behind the score is for it to produce the
-- same ordering as with sequential comparison of match's width and first
-- position. So it shouldn't really be perceived as linear distance (difference
-- between scores don't really matter, only their comparison with each other).
--
-- Reasoning behind comparison logic (based on 'time' input):
-- - '_time' is better than 't_ime' (width is smaller).
-- - 'time_aa' is better than 'aa_time' (same width, first match is smaller).
--
-- Returns -1 if `positions` is `nil` or empty.
function H.score_positions(positions)
if not positions or #positions == 0 then
return -1
end
local first, last = positions[1], positions[#positions]
local cutoff = MiniFuzzy.config.cutoff
return cutoff * math.min(last - first + 1, cutoff) + math.min(first, cutoff)
end
function H.make_filter_indexes(word, candidate_array)
-- Precompute a table of word's letters
local letters = H.string_to_letters(word)
local res = {}
for i, cand in ipairs(candidate_array) do
local positions = H.find_best_positions(letters, cand)
if positions then
table.insert(res, { index = i, score = H.score_positions(positions) })
end
end
return res
end
function H.compare_filter_indexes(a, b)
if a.score < b.score then
return true
end
if a.score == b.score then
-- Make sorting stable by preserving index order
return a.index < b.index
end
return false
end
function H.filter_by_indexes(candidate_array, ids)
local res, res_ids = {}, {}
for _, id in pairs(ids) do
table.insert(res, candidate_array[id.index])
table.insert(res_ids, id.index)
end
return res, res_ids
end
-- Utilities ------------------------------------------------------------------
function H.string_to_letters(s)
return vim.tbl_map(vim.pesc, vim.split(s, ''))
end
return MiniFuzzy