proposal: incremental injections

[vanaigr]

This is a description of how incremental injections can be implemented, and I plan to work on the PR.
I created this issue in case anyone has suggestions or can find potential flaws with this implementation.

See the PR.

Theory

The central idea is that most patterns in a query have a "root" node, i.e. such a node, for which the content and structure (types of nodes) outside its range do not affect whether the pattern matches on it or not. I.e. if we know that, after an edit, no change intersects the node range, then its matches/doesn't match status remains the same.

We can store the ranges of those "root" nodes for each match, and skip running query cursor on those ranges if they haven't changed. The same logic applies to all other nodes (that don't match). If their contents and types haven't changed, they will also continue to not match.

We can use ts_tree_get_changed_ranges() to get all regions where the syntax tree was changed, and we can record content changes from on_bytes(). Both are already used in the LanguageTree.

The last part is how to get the root nodes for each match. For now, we can do something like #set! nvim.injection-root @_root. And if all patterns in a query have that predicate, the optimization applies.

How it would work

After we have all the changes, we can remove all matches that intersect them, run the matches iterator on these ranges, add the new matches, and create new regions for the affected trees. (The actual implementation would need a smarter invalidating strategy).

Since most of the edits don't affect the injections or the syntax tree in a significant way, for them, the query cursor will recheck only a small range, and 0 injection matches will be added/removed.

Implementation

We would need to store all the matches that were found by the iterator, as well as ranges that aren't yet parsed. For each tree-sitter tree.

On a tree edit

For each tree, do the following:

1. Adjust root range of each match (the same way tree-sitter would've adjusted the node). If the change affects the content inside the match, remove the match.
2. Adjust "not parsed" ranges so they have up-to-date positions.
3. Add the new range to "not parsed" ranges (if needed).
4. Edit the tree.

When a parse is complete

After a parse on all trees is complete, each tree has a list of ranges in which the syntax tree was changed.

For each tree:

1. Remove all matches that intersect these ranges.
2. Add these ranges to "not parsed" ranges.
3. Go through all "not parsed" ranges, run the iterator on them, and add all new matches to the list.

---

Notes:

1. Theoretically, the "root" node can depend on the type of its ancestors, since if they change, their range is invalidated, and the match will be as well. This means #has-ancestor? should work with this optimization.

This is different from #26827 in that with this implementation, all injections, even the ones currently not visible, are preserved, and it also works with combined injection. Having both would be ideal, since if there are a lot of changes, all of them have to be reparsed. But usually, we only need a small range.

[lewis6991]

Mostly SGTM.

I don't fully understand why we need a "root range" for each injection. I thought this is basically the node captured with @injection.content which we already track. Is there a reason why those ranges can't be used?

[vanaigr]

I don't fully understand why we need a "root range" for each injection. I thought this is basically the node captured with @injection.content which we already track. Is there a reason why those ranges can't be used?

In most cases, @injection.content should be fine. But in cases like these (C injection):

((call_expression
  function: (identifier) @_function
  arguments: (argument_list
    (_)
    .
    [
      (string_literal
        (string_content) @injection.content)
      (concatenated_string
        (string_literal
          (string_content) @injection.content))
    ]))
  ; format-ignore
  (#any-of? @_function 
    "fprintf" "fprintf_s"
    <...>
    "vw_scanw" "vwscanw")
  (#set! injection.language "printf"))

the call_expression should be the root, because the match depends on there being only 1 argument before ((_) .), and function identifier text being a certain string. And they are outside the injection content range.

[tomtomjhj]

If I understand and recall correctly, the overal idea seems similar to what Zed does.

    // injection matches would probably be sorted on start byte.
    ...
    separate: Array<{
      tree: InjectionTree,
      match: InjectionMatch,
    }>,

For this to be maintained efficiently for the entire buffer, the injection set would likely need to be structured as an interval tree. I was considering using extmarks to do something similar for incrementalizing combined injection in #26827, but so far I couldn't find time to do it.

For non-combined injection, I'm not sure which approach (this proposal or #26827) would be better. But if the implementation of this proposal is fast enough, I think it would be fine to drop #26827.

[vanaigr]

Preliminary results:

for 10'000 lines of this inside main():

  printf("test %f test");

each edit takes +4ms, but injeciton parsing is reduced from 250ms to ~4ms.

Also deleting a double quote seems to invalidate almost the entire buffer (even though no other strings are affected), so the time spikes to 300ms.

[vanaigr]

I looked into what Zed does. They use ranges from @injection.content for the invalidation ranges. So the injections aren't invalidated in all cases:

deleting j doesn't remove the highlighting:

But deleting a space afterwards does: