8000 mini.nvim/lua/mini/fuzzy.lua at main · cryptomilk/mini.nvim · GitHub
[go: up one dir, main page]
Skip to content

fuzzy.lua

Latest commit

 

History

History
360 lines (313 loc) · 13.9 KB

File metadata and controls

360 lines (313 loc) · 13.9 KB
Raw
-- MIT License Copyright (c) 2021 Evgeni Chasnovski
-- Documentation ==============================================================
--- 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.*`).
---
--- See |MiniFuzzy.config| for `config` structure and default values.
---
--- You can override runtime config settings locally to buffer inside
--- `vim.b.minifuzzy_config` which should have same structure as
--- `MiniFuzzy.config`.
--- See |mini.nvim-buffer-local-config| for more details.
---
--- # 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 case. Case sensitive otherwise.
---@tag mini.fuzzy
---@tag MiniFuzzy
--- # 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 letters 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`.
---@tag MiniFuzzy-algorithm
-- Module definition ==========================================================
local MiniFuzzy = {}
local H = {}
--- Module setup
---
---@param config table Module config table. See |MiniFuzzy.config|.
---
---@usage `require('mini.fuzzy').setup({})` (replace `{}` with your `config` table)
MiniFuzzy.setup = function(config)
-- Export module
_G.MiniFuzzy = MiniFuzzy
-- Setup config
config = H.setup_config(config)
-- Apply config
H.apply_config(config)
end
--- Module config
---
--- Default values:
---@eval return MiniDoc.afterlines_to_code(MiniDoc.current.eval_section)
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,
}
--minidoc_afterlines_end
-- 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).
MiniFuzzy.match = function(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 ... Arrays of matched candidates and their indexes in original input.
MiniFuzzy.filtersort = function(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 `lsp_completion.process_items` of |MiniCompletion.config|
---
---@param items table Lua array with LSP 'textDocument/completion' response items.
---@param base string Word to complete.
MiniFuzzy.process_lsp_items = function(items, base)
-- Extract completion words from items
local words = vim.tbl_map(function(x)
if type(x.textEdit) == 'table' and type(x.textEdit.newText) == 'string' then return x.textEdit.newText end
if type(x.insertText) == 'string' then return x.insertText end
if type(x.label) == 'string' then return x.label end
return ''
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
--- }
--- })
MiniFuzzy.get_telescope_sorter = function(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 -------------------------------------------------------------------
H.setup_config = function(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
H.apply_config = function(config) MiniFuzzy.config = config end
H.is_disabled = function() return vim.g.minifuzzy_disable == true or vim.b.minifuzzy_disable == true end
H.get_config =
function(config) return vim.tbl_deep_extend('force', MiniFuzzy.config, vim.b.minifuzzy_config or {}, config or {}) end
-- Fuzzy matching -------------------------------------------------------------
---@param letters table 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
H.find_best_positions = function(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()
local cutoff = H.get_config().cutoff
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, 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 5A20 `nil` or empty.
H.score_positions = function(positions)
if not positions or #positions == 0 then return -1 end
local first, last = positions[1], positions[#positions]
local cutoff = H.get_config().cutoff
return cutoff * math.min(last - first + 1, cutoff) + math.min(first, cutoff)
end
H.make_filter_indexes = function(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
H.compare_filter_indexes = function(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
H.filter_by_indexes = function(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 ------------------------------------------------------------------
H.string_to_letters = function(s) return vim.tbl_map(vim.pesc, vim.split(s, '')) end
return MiniFuzzy
0