feat: Add a sorter using the fzy algorithm (#184)

* Add a sorter using the fzy algorithm

* Reformat fzy.lua

Also, update author attribution.

* Remove constansts from fzy module

Replace a few of the useful ones with getter functions that make it
clear they're not modifiable.

* Change names of fzy constant getters

* fixup: some small nit picks

Co-authored-by: TJ DeVries <devries.timothyj@gmail.com>

1 files changed, 39 insertions, 0 deletions

diff --git a/lua/telescope/sorters.lua b/lua/telescope/sorters.lua
index 4088ce0..4c268e2 100644
--- a/lua/telescope/sorters.lua
+++ b/lua/telescope/sorters.lua
@@ -307,6 +307,45 @@ sorters.fuzzy_with_index_bias = function(opts)
   }
 end
 
+-- Sorter using the fzy algorithm
+sorters.get_fzy_sorter = function()
+  local fzy = require('telescope.algos.fzy')
+  local OFFSET = -fzy.get_score_floor()
+
+  return sorters.Sorter:new{
+    scoring_function = function(_, prompt, line)
+      -- Check for actual matches before running the scoring alogrithm.
+      if not fzy.has_match(prompt, line) then
+        return -1
+      end
+
+      local fzy_score = fzy.score(prompt, line)
+
+      -- The fzy score is -inf for empty queries and overlong strings.  Since
+      -- this function converts all scores into the range (0, 1), we can
+      -- convert these to 1 as a suitable "worst score" value.
+      if fzy_score == fzy.get_score_min() then
+        return 1
+      end
+
+      -- Poor non-empty matches can also have negative values. Offset the score
+      -- so that all values are positive, then invert to match the
+      -- telescope.Sorter "smaller is better" convention. Note that for exact
+      -- matches, fzy returns +inf, which when inverted becomes 0.
+      return 1 / (fzy_score + OFFSET)
+    end,
+
+    -- The fzy.positions function, which returns an array of string indices, is
+    -- compatible with telescope's conventions. It's moderately wasteful to
+    -- call call fzy.score(x,y) followed by fzy.positions(x,y): both call the
+    -- fzy.compute function, which does all the work. But, this doesn't affect
+    -- perceived performance.
+    highlighter = function(_, prompt, display)
+      return fzy.positions(prompt, display)
+    end,
+  }
+end
+
 -- Bad & Dumb Sorter
 sorters.get_levenshtein_sorter = function()
   return Sorter:new {