Incremental injection query

[vanaigr]

I am currently implementing incremental injection query matching for Neovim, but making a query able to run incrementally requires adding some extra information to all its patterns. Currently, it's #set! nvim.injection-root @some-node, but that would mean that Neovim's injection queries would diverge from other editors/upstream, and that's not desirable.

If running injection queries incrementally is desirable for Helix, then we should come up with a better name, and probably open an issue in tree-sitter as well.

---

The basic idea with running tree-sitter queries incrementally is that majority of patterns have a "root" node, i.e. such a node, for which the text/syntax changes outside its range don't change whether the pattern matches on it or not.

E.g. for this pattern:

((call_expression
  function: (identifier) @_function
  arguments: (argument_list
    (_)
    .
    (string_literal
      (string_content) @injection.content)))
  (#eq? @_function "fprintf")
  (#set! injection.language "printf"))

the "root" node is call_expression, because only changes to its children affect whether the node matches or not.

After a change, there's no need to rerun the query matches iterator on the entire file, only on changed ranges. And matches outside the changed ranges can be reused.

See neovim/neovim#31809 for more details, and neovim/neovim#31975 for the implementation.

[kirawi]

I believe injections in Helix are handled incrementally? #4146 @pascalkuthe

[vanaigr]

I believe injections in Helix are handled incrementally? #4146 @pascalkuthe

If I understand correctly, this optimizes reparsing of existing injections. But the query cursor is still executed for the entire range of each changed tree. And the root layer is changed on every edit.

For big files, running the query cursor for each edit can be very slow. Even if a particular file has no injections, the query is rerun for the entire file.

E.g. this piece of code:

helix/helix-core/src/syntax.rs

Lines 1293 to 1298 in 29dda14

	// Process injections.
	let matches = cursor.matches(
	&layer.config.injections_query,
	layer.tree().root_node(),
	RopeProvider(source_slice),
	);

[pascalkuthe]

Yeah I have been wanting to make the injection query incremental. So I am definitly interested/like the direction but at the moment I don't have the bandwidth to look into this

[the-mikedavis]

It'd be great to avoid running the query across the entire text. Even if we re-parse layers incrementally it's still quite expensive to re-run the injection query for larger documents.

Tagging every injection pattern with its root node seems quite clunky though. That information might not be exposed currently but can't the query cursor track and expose the node it's considering as a root for the pattern? I'd rather see this exposed on the tree-sitter C library side than done purely by the queries if possible.

[pascalkuthe]

It'd be great to avoid running the query across the entire text. Even if we re-parse layers incrementally it's still quite expensive to re-run the injection query for larger documents.

Tagging every injection pattern with its root node seems quite clunky though. That information might not be exposed currently but can't the query cursor track and expose the node it's considering as a root for the pattern? I'd rather see this exposed on the tree-sitter C library side than done purely by the queries if possible.

I looked into this a whole ago. Fonding the root node is not really rasuly feasible. Patterns can depend on their adjecent nodes on wether they match and there is no practical way to tell if that is the case.

I was considering just reruninng the injection query on All nodes touches by an edit plus a fixed amount of siblings and possible having a way to increase that number per grammar (similar to the match limit we already have)