mini.nvim/lua/mini/fuzzy.lua at main · GitMurf/mini.nvim

Repository navigation

History

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

366

367

368

369

370

371

372

373

374

375

376

377

--- *mini.fuzzy* Fuzzy matching

--- *MiniFuzzy*

---

--- ==============================================================================

---

--- 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 |telescope.nvim| sorter: |MiniFuzzy.get_telescope_sorter()|.

---

--- # 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.

--- # 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< 8000 /div>

--- (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

--- 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 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|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 config

H.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 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|nil 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 `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.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

FilesExpand file tree

fuzzy.lua

Latest commit

History

fuzzy.lua

File metadata and controls