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, 96 insertions, 0 deletions

diff --git a/lua/tests/automated/telescope_spec.lua b/lua/tests/automated/telescope_spec.lua
index bf296f5..933cfc5 100644
--- a/lua/tests/automated/telescope_spec.lua
+++ b/lua/tests/automated/telescope_spec.lua
@@ -268,6 +268,102 @@ describe('Sorters', function()
     end)
   end)
 
+  describe('fzy', function()
+    local sorter = require'telescope.sorters'.get_fzy_sorter()
+    local function score(prompt, line)
+      return sorter:score(prompt, {ordinal = line})
+    end
+
+    describe("matches", function()
+      it("exact matches", function()
+        assert.True(score("a", "a") >= 0)
+        assert.True(score("a.bb", "a.bb") >= 0)
+      end)
+      it("ignore case", function()
+        assert.True(score("AbB", "abb") >= 0)
+        assert.True(score("abb", "ABB") >= 0)
+      end)
+      it("partial matches", function()
+        assert.True(score("a", "ab") >= 0)
+        assert.True(score("a", "ba") >= 0)
+        assert.True(score("aba", "baabbaab") >= 0)
+      end)
+      it("with delimiters between", function()
+        assert.True(score("abc", "a|b|c") >= 0)
+      end)
+      it("with empty query", function()
+        assert.True(score("", "") >= 0)
+        assert.True(score("", "a") >= 0)
+      end)
+      it("rejects non-matches", function()
+        assert.True(score("a", "") < 0)
+        assert.True(score("a", "b") < 0)
+        assert.True(score("aa", "a") < 0)
+        assert.True(score("ba", "a") < 0)
+        assert.True(score("ab", "a") < 0)
+      end)
+    end)
+
+    describe("scoring", function()
+      it("prefers beginnings of words", function()
+        assert.True(score("amor", "app/models/order") < score("amor", "app/models/zrder"))
+      end)
+      it("prefers consecutive letters", function()
+        assert.True(score("amo", "app/models/foo") < score("amo", "app/m/foo"))
+        assert.True(score("erf", "perfect") < score("erf", "terrific"))
+      end)
+      it("prefers contiguous over letter following period", function()
+        assert.True(score("gemfil", "Gemfile") < score("gemfil", "Gemfile.lock"))
+      end)
+      it("prefers shorter matches", function()
+        assert.True(score("abce", "abcdef") < score("abce", "abc de"));
+        assert.True(score("abc", "    a b c ") < score("abc", " a  b  c "));
+        assert.True(score("abc", " a b c    ") < score("abc", " a  b  c "));
+      end)
+      it("prefers shorter candidates", function()
+        assert.True(score("test", "tests") < score("test", "testing"))
+      end)
+      it("prefers matches at the beginning", function()
+        assert.True(score("ab", "abbb") < score("ab", "babb"))
+        assert.True(score("test", "testing") < score("test", "/testing"))
+      end)
+      it("prefers matches at some locations", function()
+        assert.True(score("a", "/a") < score("a", "ba"))
+        assert.True(score("a", "bA") < score("a", "ba"))
+        assert.True(score("a", ".a") < score("a", "ba"))
+      end)
+    end)
+
+    local function positions(prompt, line)
+      return sorter:highlighter(prompt, line)
+    end
+
+    describe("positioning", function()
+      it("favors consecutive positions", function()
+        assert.same({1, 5, 6}, positions("amo", "app/models/foo"))
+      end)
+      it("favors word beginnings", function()
+        assert.same({1, 5, 12, 13}, positions("amor", "app/models/order"))
+      end)
+      it("works when there are no bonuses", function()
+        assert.same({2, 4}, positions("as", "tags"))
+        assert.same({3, 8}, positions("as", "examples.txt"))
+      end)
+      it("favors smaller groupings of positions", function()
+        assert.same({3, 5, 7}, positions("abc", "a/a/b/c/c"))
+        assert.same({3, 5}, positions("ab", "caacbbc"))
+      end)
+      it("handles exact matches", function()
+        assert.same({1, 2, 3}, positions("foo", "foo"))
+      end)
+      it("ignores empty requests", function()
+        assert.same({}, positions("", ""))
+        assert.same({}, positions("", "foo"))
+        assert.same({}, positions("foo", ""))
+      end)
+    end)
+  end)
+
   describe('layout_strategies', function()
     describe('center', function()
       it('should handle large terminals', function()