feat: Improve filtering ideas for sorters.

3 files changed, 203 insertions, 1 deletions

diff --git a/lua/telescope/pickers.lua b/lua/telescope/pickers.lua
index 935f6cf..e77e0e9 100644
--- a/lua/telescope/pickers.lua
+++ b/lua/telescope/pickers.lua
@@ -394,6 +394,10 @@ function Picker:find()
 
     local prompt = vim.trim(vim.api.nvim_buf_get_lines(prompt_bufnr, first_line, last_line, false)[1]:sub(#prompt_prefix))
 
+    if self.sorter then
+      self.sorter:_start(prompt)
+    end
+
     -- TODO: Statusbar possibilities here.
     -- vim.api.nvim_buf_set_virtual_text(prompt_bufnr, 0, 1, { {"hello", "Error"} }, {})
 
diff --git a/lua/telescope/sorters.lua b/lua/telescope/sorters.lua
index 4c268e2..6fff7f8 100644
--- a/lua/telescope/sorters.lua
+++ b/lua/telescope/sorters.lua
@@ -20,6 +20,8 @@ local ngram_highlighter = function(ngram_len, prompt, display)
   return highlights
 end
 
+local FILTERED = -1
+
 
 local Sorter = {}
 Sorter.__index = Sorter
@@ -39,12 +41,68 @@ function Sorter:new(opts)
     state = {},
     scoring_function = opts.scoring_function,
     highlighter = opts.highlighter,
+    discard = opts.discard,
+    _discard_state = {
+      filtered = {},
+      prompt = '',
+    },
   }, Sorter)
 end
 
+-- TODO: We could make this a bit smarter and cache results "as we go" and where they got filtered.
+--          Then when we hit backspace, we don't have to re-caculate everything.
+--          Prime did a lot of the hard work already, but I don't want to copy as much memory around
+--              as he did in his example.
+--              Example can be found in ./scratch/prime_prompt_cache.lua
+function Sorter:_start(prompt)
+  if not self.discard then
+    return
+  end
+
+  local previous = self._discard_state.prompt
+  local len_previous = #previous
+
+  if #prompt < len_previous then
+    log.debug("Reset discard because shorter prompt")
+    self._discard_state.filtered = {}
+  elseif string.sub(prompt, 1, len_previous) ~= previous then
+    log.debug("Reset discard no match")
+    self._discard_state.filtered = {}
+  end
+
+  self._discard_state.prompt = prompt
+end
+
+-- TODO: Consider doing something that makes it so we can skip the filter checks
+--          if we're not discarding. Also, that means we don't have to check otherwise as well :)
 function Sorter:score(prompt, entry)
   if not entry or not entry.ordinal then return -1 end
-  return self:scoring_function(prompt or "", entry.ordinal, entry)
+
+  local ordinal = entry.ordinal
+
+  if self:_was_discarded(prompt, ordinal) then
+    return FILTERED
+  end
+
+  local score = self:scoring_function(prompt or "", ordinal, entry)
+
+  if score == FILTERED then
+    self:_mark_discarded(prompt, ordinal)
+  end
+
+  return score
+end
+
+function Sorter:_was_discarded(prompt, ordinal)
+  return self.discard and self._discard_state.filtered[ordinal]
+end
+
+function Sorter:_mark_discarded(prompt, ordinal)
+  if not self.discard then
+    return
+  end
+
+  self._discard_state.filtered[ordinal] = true
 end
 
 function sorters.new(...)
@@ -313,6 +371,8 @@ sorters.get_fzy_sorter = function()
   local OFFSET = -fzy.get_score_floor()
 
   return sorters.Sorter:new{
+    discard = true,
+
     scoring_function = function(_, prompt, line)
       -- Check for actual matches before running the scoring alogrithm.
       if not fzy.has_match(prompt, line) then
diff --git a/scratch/prime_prompt_cache.lua b/scratch/prime_prompt_cache.lua
new file mode 100644
index 0000000..20fb67a
--- /dev/null
+++ b/scratch/prime_prompt_cache.lua
@@ -0,0 +1,138 @@
+local log = require('telescope.log')
+
+local PromptCache = {}
+
+function getFirstByteDiffIdx(a, b)
+  local idx = 1
+  local max_idx = #a
+  while a:byte(idx) == b:byte(idx) and idx <= max_idx do
+    idx = idx + 1
+  end
+
+  return idx
+end
+
+function PromptCache:new(opts)
+  self.__index = self
+  local obj = setmetatable({
+      current_line = nil,
+      cached_results = {},
+      cache_round = 0
+  }, self)
+
+  return obj
+end
+
+function PromptCache:set_cache(prompt, item_to_cache)
+  self.results = item_to_cache
+  self:_complete(prompt)
+end
+
+function PromptCache:_complete(prompt)
+  if #prompt == 0 then
+    self:_reset()
+    return
+  end
+
+  local cached_lines = self.results
+
+  local idx = 1
+  if self.current_line ~= nil then
+    idx = getFirstByteDiffIdx(self.current_line, prompt)
+  end
+
+  -- ABC
+  -- ABDC
+  -- IDX = 3
+  -- cr = 3
+  -- diff = 1
+  local diff = #self.cached_results - (idx - 1)
+  while diff > 0 do
+    table.remove(self.cached_results)
+    diff = diff - 1
+  end
+
+  -- ABC
+  -- ADBC
+  -- diff = 2
+  for i = idx, #prompt do
+    if #self.cached_results < (#prompt - 1) then
+      local last_cache = self:get_last_cache()
+      table.insert(self.cached_results, last_cache)
+    else
+      table.insert(self.cached_results, cached_lines)
+    end
+  end
+
+  self.current_line = prompt
+end
+
+function PromptCache:start_round(cache_round)
+  self.cache_round = cache_round
+  log.trace("start_round (had this", self.results and #self.results or nil, "for past results)", self.cache_round)
+  self.results = {}
+end
+
+function PromptCache:add_to_round(cache_round, line, score)
+  if cache_round < self.cache_round or score == -1 then
+    return
+  end
+
+  table.insert(self.results, line)
+end
+
+function PromptCache:get_last_cache()
+  local last_cache = nil
+
+  for idx = 1, #self.cached_results do
+    local cache = self.cached_results[idx]
+    if cache then
+      last_cache = cache
+    end
+  end
+
+  return last_cache
+end
+
+function PromptCache:complete_round(cache_round, prompt)
+  if cache_round ~= self.cache_round then
+    return
+  end
+
+  self:_complete(prompt)
+end
+
+function PromptCache:get_cache(prompt)
+  if self.current_line == nil or #prompt == 0 then
+    return nil
+  end
+
+  local idx = getFirstByteDiffIdx(self.current_line, prompt)
+
+  if idx == 1 then
+    self:_reset()
+    return nil
+  end
+
+  -- if we are off, then we simply need to prune the cache or let complete do
+  -- that
+  local results = nil
+  repeat
+    results = self.cached_results[idx - 1]
+    idx = idx - 1
+  until idx <= 1 or results
+
+return results
+end
+
+function PromptCache:_reset()
+    self.current_line = nil
+    self.cached_results = {}
+end
+
+
+return {
+  PromptCache = PromptCache
+}
+
+