Port to Lua

[wincent]

Sadly, I had a fair bit of progress towards this on a branch, but I foolishly lost it, so going to have to start again. :face_with_head_bandage:

Oh well. The idea is to pack the C bits into a Lua extension and rewrite pretty much everything else from scratch, making use of new features like floating windows and centering on Neovim (of course, if you want to stick with Vim, the existing codebase is always going to be in the repo history and you can continue to use it).

[vheon]

Hi, have you considered making only the sorting algorithm available to lua and just use it inside telescope.nvim? I tried to hammer something together this morning just to see how complex it would be https://github.com/vheon/command-t/tree/telescope; I started from the python branch that you already had since it was easier. I think you could improve memoization like you do right now in the ruby version using the full APIs available in telescope Sorters, but I'm not sure (https://github.com/nvim-telescope/telescope-fzf-native.nvim does something similar creating a slab of memory at initialization time and passing it in when calculating the score). Integrating with telescope it would allow to leverage all the ecosystem and the already available Finders and Themes.

[wincent]

Thanks for the links @vheon.

I hadn't thought about porting just the match-scoring algorithm to Lua. I did that in the python branch because my use case demanded intuitive result ordering but the search space was always going to be small (on the order of a few thousand candidate strings), so it didn't really need anything else. Specifically, I needed to implement fuzzy search over email addresses and wiki article titles in a deoplete extension.

The work I have been hacking on since creating this ticket does something similar to what you did in you commits, but goes further. The goal is to port the entire thing (the match scoring and the parallel thread-based matching) because this time the goal is to replace the old implementation for all use cases, which means it has to be very fast even on repos with > 1,000,000 files.

I am not familiar with the architecture of Telescope but it's pretty obviously becoming the dominant "finder" plug-in in Neovim ecosystem. It may be that when I finish this port (not even really finishing the whole thing, just the C bit) there will be something there that can be plugged into Telescope pretty easily. But first things first, and that is getting all the Ruby interop out of the C code and finding an efficient way to glue it together with the Lua side; maybe that slab allocation you mentioned is going to be part of it. Right now I'm just trying to get it to work at all, and once I've done that, work on making it fast and minimizing copies etc.

[vheon]

which means it has to be very fast even on repos with > 1,000,000 files.

That's very good to hear, before trying to use command-t's matching algorithm I tried the telescope-fzf-native.nvim and with ~80k files it was struggling.

The goal is to port the entire thing (the match scoring and the parallel thread-based matching)

That is something that right now is very difficult with telescope being single thread and running in the luajit embedded in Neovim. I wanted to experiment with external process over msgpack-c (similar to what I'm doing with completion https://github.com/vheon/ycm.nvim) but again the telescope API is not meant to be used in this way.

Anyway thanks for the insight on the roadmap!

[wincent]

The goal is to port the entire thing (the match scoring and the parallel thread-based matching)

That is something that right now is very difficult with telescope being single thread and running in the luajit embedded in Neovim. I wanted to experiment with external process over msgpack-c (similar to what I'm doing with completion https://github.com/vheon/ycm.nvim) but again the telescope API is not meant to be used in this way.

Once you're in C-land you can created threads and then call pthread_join() which will block, waiting for the thread to terminate. So the Lua side doesn't even know about this little excursion off into the land of parallelism; it just blocks waiting for your FFI code to return. At least, that's the theory (based on how it worked with Vim calling into Ruby calling into C like it does on the master branch). Note that it is a synchronous search, so it has to be fast, otherwise Vim will seem to lock up... I've long had the idea of running Command-T in an external process as a backup plan in case it wasn't fast enough, but when I used to work at FB in a monorepo that had well north of a 500k files, and later > 1m files, it never got to he point of being too slow. It's nice to have options though, because these monorepos only keep growing.

[vheon]

Once you're in C-land you can created threads and then call pthread_join() which will block, waiting for the thread to terminate. So the Lua side doesn't even know about this little excursion off into the land of parallelism; it just blocks waiting for your FFI code to return. At least, that's the theory (based on how it worked with Vim calling into Ruby calling into C like it does on the master branch).

right I was not thinking on spawning threads directly in C-land for some reason.

Note that it is a synchronous search, so it has to be fast, otherwise Vim will seem to lock up...

Yes that was my experience with other sorters with telescope (actually it felt slow but non blocking because telescope tries hard not to fully block the ui)

it never got to he point of being too slow. It's nice to have options though, because these monorepos only keep growing.

I know, I work with a monorepo as well... not that big but still...

[wincent]

Closing this as the rewrite is now "done" enough (think "massvely pre-alpha quality" at this point) that further discussion can happen around the concrete release plan (https://github.com/wincent/command-t/issues/391) instead of here. In the meantime, I'll be filling in feature gaps.