TS highlighter that directly parse result window

[xzbdmw]

This is a POC that steal the idea from trouble.nvim

Use nvim_set_decoration_provider and set_included_regions to parse the result window on the fly, in every key stroke, but only in the visible several lines, so each round of parsing only requires 3ms. Current implementation will freeze for 0.5 seconds when there are too many files, tested by searching func in gopls repo, while after the initial parse, later keystrokes do not need extra parsing time.

Also the TelescopePreviewerLoaded is not a good idea, but can't find better place to inject the callback, this pr should works with default config with minimal setup. the detail needs to adjust if you like this idea.

[fdschmidt93]

Thanks for the PR, it's indeed super snappy! This will very much be appreciated once finalized. I hope you don't take this the wrong way, but the implementation looks a bit cursed though :laughing:

Just so I fully understand the high-level idea. We are essentially using tree-sitter language injections on-the-fly? The autocommand is indeed funny, I didn't realize that TelescopePreviewerLoaded was triggered on every previewer refresh (instead of only when previewer is created).

I've briefly looked into alternatives. line_display unfortunately is to late, because the picker first parses the highlights before writing the entry to results.

I was also thinking about nvim_buf_attach but I haven't gotten the below quite to work:

vim.api.nvim_create_autocmd("FileType", {
  pattern = "TelescopeResults",
  callback = function(args)
    local action_state = require "telescope.actions.state"
    local prompt_bufnr = require("telescope.state").get_existing_prompt_bufnrs()[1]
    local picker = action_state.get_current_picker(prompt_bufnr)

    vim.api.nvim_buf_attach(args.buf, false, {
      on_lines = function(_, _, _, first_line_idx, last_line_idx)
        local lines = vim.api.nvim_buf_get_lines(args.buf, first_line_idx, last_line_idx, false)
        local regions = {}

        local j = 0
        for i = first_line_idx + 1, last_line_idx + 1 do
          j = j + 1
          local line = lines[j]
          if line == "" then
            goto continue
          end
          local entry = picker.manager:get_entry(picker:get_index(i))
          if entry == nil then
            goto continue
          end
          local ft = vim.filetype.match { filename = entry.filename }
          if ft == nil then
            goto continue
          end
          if regions[ft] == nil then
            regions[ft] = {}
          end
          -- Find text
          local first_pos = string.find(line, entry.text - 1, 1, true)
          if first_pos == nil then
            goto continue
          end
          table.insert(regions[ft], { { i, first_pos, i, line:len() } })
          ::continue::
        end
        require("telescope._extensions.egrepify.treesitter").attach(args.buf, regions)
      end,
    })
  end,

Probably some indexing is wrong (it looks like very infrequently, highlighting may be correctly applied. You're happy to take a crack at it if you can figure out what's wrong with the indexing. Worst case buf attach events are also not quite correctly timed (though hard to 'debug').

[xzbdmw]

I remember there is a on_complete callback, but not triggered for every selection change, but triggered for every buf content refreshing. One alternative would be parse the entire buffer, and listen for on_complete.

Maybe only parse the visible lines is over optimized, treesitter can parse thousands of lines within 10ms, if lines becomes too many, telescope itself becomes bottleneck anyway, so I’m going with this direction.

[fdschmidt93]

Another way that should work well and is "optimal" I suppose:

  local entry_adder = picker.entry_adder
  picker.entry_adder = function(picker_, index, entry, _, insert)
    entry_adder(picker_, index, entry, _, insert)
    local regions = {}

    local row = picker_:get_row(index)
    local line_count = vim.api.nvim_buf_line_count(picker_.results_bufnr)
    local line = vim.api.nvim_buf_get_lines(picker_.results_bufnr, row, row + 1, false)[1]
    if row > line_count then
      return
    end
    local ft = vim.filetype.match { filename = entry.filename }
    if ft == nil then
      return
    end
    if regions[ft] == nil then
      regions[ft] = {}
    end
    -- Find the first occurrence of ':'
    local first_pos = string.find(line, ":", 1, true)
    if first_pos == nil then
      return
    end
    table.insert(regions[ft], { { row, first_pos, row, line:len() } })
    require("telescope._extensions.egrepify.treesitter").attach(picker_.results_bufnr, regions)
    vim.print(line)
  end

in between here, but I've just realized this only parses the last line correctly, because only the last parser is kept. In the above case, we are de facto creating a new parser for every line. cf. in treesitter.lua

    M.cache[buf][lang] = {
      parser = parser,
      highlighter = TSHighlighter.new(parser),
    }

[fdschmidt93]

What do you think about the code I've pushed?

[xzbdmw]

The entry_addr seems to be run in the entire buffer, not only in visible lines. I notice that `sorting_strategy = "ascending" will not work.

One alternative would be parse the entire buffer, and listen for on_complete.

I've tried this way, indeed search for "nil" with 15965 results only makes attach runs for 4ms, this seems to be simpler implementation, the highlighter will destroy the state after the result buf is wiped out, so we do not need to care the highlight state.

edit: I feel the previewer completes much slower if we parse the entire buffer, perhaps I do not record perf correctly. And only parse visible lines is indeed a crucial step.

[fdschmidt93]

    local row = picker_:get_row(index)
    local line_count = vim.api.nvim_buf_line_count(picker_.results_bufnr)
    if row > line_count then
      return
    end
    local line = vim.api.nvim_buf_get_lines(picker_.results_bufnr, row, row + 1, false)[1]

It does not per se run in the entire buffer, but it checks the line count of the buffer for every entry, even if that entry is not displayed. But that is essentially a look-up (c-implementation).

E: Ah, we should only get valid lines. E2: fixed

So I'm not sure why you think it runs in the entire buffer?

I notice that `sorting_strategy = "ascending" will not work.

Works for me? What doesn't work for you here?

E3: The redraw of the results buffer -- I think (have to test drive more) -- is not quite as clean as before.

[xzbdmw]

It does not per se run in the entire buffer,

I mean that entry_addr is running for every entry, so if there are 1000 matches, it will run 1000 times, if you search for if in telescope repo, it would take a long time to add all the entries, because each entry is parsed

[fdschmidt93]

Just to clarify entry_addr is always called for every valid entry in telescope that has a lower score than the current max score, irrespective of us monkey patching the function. In other words, that is a telescope thing we won't be able to optimize here.

We have to use index & line count to check if the added entry is within visible lines, but as mentioned above, that only entails two look-ups.

[xzbdmw]

Yeah, the problem is we do extra parsing in entry_addr, which takes noticable time if there are too many matches

We have to use index & line count to check if the added entry is within visible lines, but as mentioned above, that only entails two look-ups.

I think we should check topline and botline, not the actual line count

[fdschmidt93]

What I'm saying is the logic currently added into the PR only adds the overhead of 2 look-ups for non-visible entries compared to plain telescope. Not sure I follow why that is a problem.

Sure, telescope itself is not optimized, but that's not something we can address here.

I think we should check topline and botline, not the actual line count

Why? This is how telescope checks if a result can be drawn, see here.

What's not quite right probably is the fact that the line count includes the header, but that I think just means we are (re-)drawing 1 line too often. With that in mind, line count is faster than top- and botline, since top- and botline are two functions calls that go through vim.fn which IIRC has conversion overhead between C-vimscript-lua.

[xzbdmw]

Oh, I update telescope to latest just now and don't see performance problem, this is good enough, I'll test a few days

[fdschmidt93]

this is good enough

Do you have an idea what can actually be improved?

[xzbdmw]

I see the line count has a max default value of 250 https://github.com/nvim-telescope/telescope.nvim/blob/dc6fc321a5ba076697cca89c9d7ea43153276d81/lua/telescope/pickers.lua#L578,

https://github.com/nvim-telescope/telescope.nvim/blob/dc6fc321a5ba076697cca89c9d7ea43153276d81/lua/telescope/pickers.lua#L327

So we are stopping at 250 too, the possible improvements, would be stop at invisible view in the window, which is 10-20 lines typically, but that can't be done in entry_addr, it is not called when we scroll down, thus move the view point beyond those has been highlighted... the problem returns back to the very original one😄

My thoghts: register cursormoved event of result buffer, in entry_addr, only highlight the first 20 index, and add regions in in cursormoved, kind of incremental parsing. The 250 entries performance is very acceptable though, may not need more optimize.

[fdschmidt93]

The 250 entries performance is very acceptable though, may not need more optimize.

Yes, I'm pretty sure that we don't need to further optimize. What you are proposing sounds a bit needlessly complicated over the current relatively simple implementation. As I understand it, especially if there is only a few languages in the 250 results, then we kind of get the injection for free (only highlighting required which is super fast) because we already have the parser.

[xzbdmw]

Hah, that's the misunderstanding between us before, I mean visible as in window, you mean in buffer 😸 , I accidentally changed the scroll_limit to 10000 before, that's why I feel slow, funny.

[fdschmidt93]

@delphinus May I please ask you to also test drive this branch and report any issues you might run into? Thanks in advance :) should be a strict improvement (performance, correctness of drawn results) over now.

[fdschmidt93]

Let's merge this. This is already a huge improvement. We can fine-tune this later.

[fdschmidt93]

Thanks @xzbdmw !

[xzbdmw]

I find that string.find will not suit for some language, e.g., in python, entry.text and line is as follows:

Picker.picker#function#if entry.text: "            asyncio.run(okx_get(symbols[i], symbols_swap[i]))\r "
Picker.picker#function#if line: "  okx-bbo-tbt.py:238:             asyncio.run(okx_get(symbols[i], symbols_swap[i])) "

the ending \r will make string.find return nil

Another thing surprising to me is that vim.filetype.match is quit slow, and it is a performance blocker, simply change it to "lua" will save me 70ms for 171 items(set default_text to "local" in egrepify's repo, down from 130ms to 60ms), and the 70ms makes it "feels" much smoother, because the previewer loads much faster.

here is the diff for recording perf

telescope-egrepify.nvim git:(master) ✗ git --no-pager diff                                        0 [02:39:45]
diff --git a/lua/telescope/_extensions/egrepify/picker.lua b/lua/telescope/_extensions/egrepify/picker.lua
index 2486be0..9762119 100644
--- a/lua/telescope/_extensions/egrepify/picker.lua
+++ b/lua/telescope/_extensions/egrepify/picker.lua
@@ -233,7 +233,7 @@ function Picker.picker(opts)
       return
     end
     local line = vim.api.nvim_buf_get_lines(picker_.results_bufnr, row, row + 1, false)[1]
-    local ft = vim.filetype.match { filename = entry.filename }
+    local ft = "lua"
     if ft == nil then
       return
     end
@@ -278,8 +278,19 @@ function Picker.picker(opts)
     picker.AND = true
   end

+  _G.egrep = vim.uv.hrtime()
   picker:find()
 end

+local time = function(start)
+  local duration = 0.000001 * (vim.loop.hrtime() - start)
+  print(vim.inspect(duration))
+end
+vim.api.nvim_create_autocmd({ "User" }, {
+  pattern = "TelescopePreviewerLoaded",
+  callback = function(data)
+    time(_G.egrep)
+  end,
+})
 ---@export Picker
 return Picker.picker

each vim.filetype.match costs 0.4ms, while each attach costs 0.04ms, so in extreme case, 250 items, it is 100ms more!

I propose to use require("plenary.filetype").detect(entry.filename) instead.