Something went wrong. Try again.
Library of 45+ independent Lua modules improving Neovim experience with minimal effort nvim-mini.org/mini.nvim
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348--- *mini.fuzzy* Fuzzy matching------ MIT License Copyright (c) 2021 Evgeni Chasnovski
--- Features:--- - Minimal and fast fuzzy matching algorithm which prioritizes match width.------ - Functions to for common fuzzy matching operations:--- - |MiniFuzzy.match()|.--- - |MiniFuzzy.filtersort()|.--- - |MiniFuzzy.process_lsp_items()|.------ - Generator of sorter (|MiniFuzzy.get_telescope_sorter()|) for--- [nvim-telescope/telescope.nvim](https://github.com/nvim-telescope/telescope.nvim)------ # 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 MiniFuzzy
--- 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 non-empty input `word` and target `candidate`:--- - The goal is to find matching between letters in `word` 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` 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|nil Module config table. See |MiniFuzzy.config|.------@usage >lua--- require('mini.fuzzy').setup() -- use default config--- -- OR--- 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
--- Defaults ~---@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------@param word string Input word (usually user input).---@param candidate string Target word (usually with which matching is done).------@return table Matching information:--- - <positions> `(table|nil)` - array with letter indexes inside `candidate`--- which matched to corresponding letters in `word`. It is empty array if--- `word` is empty string and `nil` if no match.--- - <score> `number` - positive number representing how good the match is--- (lower is better). It is `-1` if no match or word is empty string.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------ - Keep only input elements which match `word`.--- - Sort 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 = word == word:lower() and vim.tbl_map(string.lower, candidate_array) or candidate_array 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 Array with LSP `'textDocument/completion'` response items.---@param base string Word to complete.------@return table Array of items with text (`filterText` or `label`) fuzzy matching `base`.MiniFuzzy.process_lsp_items = function(items, base) local words = vim.tbl_map(function(x) return x.filterText or x.label end, items) 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 as a value for file and generic sorter of `telescope.nvim`.------@param opts table|nil Options (currently not used).------@usage >lua--- 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 configH.default_config = vim.deepcopy(MiniFuzzy.config)
-- Helper functionality =======================================================-- Settings -------------------------------------------------------------------H.setup_config = function(config) H.check_type('config', config, 'table', true) config = vim.tbl_deep_extend('force', vim.deepcopy(H.default_config), config or {})
if not (type(config.cutoff) == 'number' and config.cutoff >= 1) then H.error('`cutoff` should be number not less than 1, not ' .. type(config.cutoff)) end
return configend
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|nil Table with matched positions (in `candidate`) if there is a--- match, `nil` otherwise.---@privateH.find_best_positions = function(letters, candidate) local n_candidate, n_letters = #candidate, #letters if n_letters == 0 then return {} end if 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_positionsend
-- 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.H.score_positions = function(positions) if positions == nil 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) local res, letters = {}, H.string_to_letters(word) for i, cand in ipairs(candidate_array) do local positions = H.find_best_positions(letters, cand) if positions ~= nil then table.insert(res, { index = i, score = H.score_positions(positions) }) end end return resend
H.compare_filter_indexes = function(a, b) return a.score < b.score or (a.score == b.score and a.index < b.index) 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_idsend
-- Utilities ------------------------------------------------------------------H.error = function(msg) error('(mini.fuzzy) ' .. msg, 0) end
H.check_type = function(name, val, ref, allow_nil) if type(val) == ref or (ref == 'callable' and vim.is_callable(val)) or (allow_nil and val == nil) then return end H.error(string.format('`%s` should be %s, not %s', name, ref, type(val)))end
H.string_to_letters = function(s) return vim.tbl_map(vim.pesc, vim.split(s, '')) end
return MiniFuzzy