-
Notifications
You must be signed in to change notification settings - Fork 28
Technical Overview
This gives a brief overview of how instant.nvim works. See instant.lua.tl for a more programmatic overview but this should give a general idea in plain text how it works.
Neovim provides a very convenient functionality (on_lines callback in nvim_buf_attach which notifies anytime the buffer content is changed. This avoids the trouble to track any keypress or more complex custom text edit tracking.
The work is not completly done by Neovim though. The exact characters which were changed needs to be determined as Neovim only provides where (line numbers) the changes were made. instant.nvim always keep the previous state of the buffer in memory and compares whenever a text edit is made with the current buffer content. Without going into too much details, it takes the two character ranges (previous and current) and does two passes, comparing each character from the beginning until it doesn't match and same thing from the end. The remaining character range in previous are labeled as characters to delete, and characters in current range is labeled as characters to insert.
This works overall. There is a undeteremined case, where a letter is inserted repeatedly, the algorithm cannot determine where it was insertered and inserts it at the wrong place usually. But a better solution is not possible at the moment so further investigations were not done.
To avoid text discrepency between clients (think when two users, insert some letter on the same line), the copies of the clients should all be identical.
CRDTs (conflict-free replicated data type) is a relatively new algorithm (2006) which tries to solve this problem.
Different papers were published on the subject and there are different variants compatible for text editors. wikipedia
Generally there can be split into two categories. Algorithms which need thombstone for deleted characters such as WOOT, Treedoc, RGA or not Logoot, LSEQ.
For this reason, an implementation of the Logoot algorithm was used for instant.nvim. LSEQ which is an improvement over Logoot would be interesting to implement in instant.nvim once its more stable in the future.