Stream: t-compiler/rust-analyzer

Topic: incremental reparsing in Lark

nikomatsakis (Feb 20 2019 at 15:18, on Zulip):

@matklad one thing I wanted to mention. I think we talked about this briefly at the all hands, but I don't think anybody else may have heard it. One approach to incremental reparsing that I was consdering in Lark, but never implemented, was to really leverage salsa and hence enable incremental re-parsing in quite an automatic way.

In Lark, the base query currently gives back a &[u8] slice of the file. The rough idea was to next do a very quick "repackaging" of that into trees -- basically grouping together {..} tokens. Thus you don't index into the file in an absolute way to identify a token, but rather your index becomes a kind of tree, identifying the path to the {} and the token within.

The actual parser itself would track its position as this kind of tree -- when it comes to a { token, and it needs to compute the "next" index, it would load the set of children of the { token, etc.

This way, when we make a change, we would have to recompute the tree, but that is very cheap-- and after that, we only have to reparse the affected things. Since most edits occur somewhere within a {...}, this implies that the data outside of those {} is not affect (and in particular, the path to it is not affected by how many characters appear within the {}).

nikomatsakis (Feb 20 2019 at 15:19, on Zulip):

I suspect that whatever tree setup we end up with, we will be able to create salsa-ified incremental variants around it.

matklad (Feb 20 2019 at 15:23, on Zulip):

rust-analyzer works in a similar way, but this is implemented manually, not automatically.

When an edit happens, we find the nearest enclosing {}, relex it and , if {} are still matched up, reparse only this region, retaining the rest of the syntax tree.

matklad (Feb 20 2019 at 15:25, on Zulip):

And a usual note that incremental re parsing is not too important. In IntelliJ for Java, while {} are usually automatically paired by the editor, if you type { in if (condition) {, IDE does not add closing } automatically. Instead, } is added when you actually type Enter: that gives a somewhat better typing feeling.

matklad (Feb 20 2019 at 15:26, on Zulip):

of course that upaired { completely invalidates the parse tree, but the perf loss is negligible, and so smother typing gets higher priority.

matklad (Feb 20 2019 at 15:26, on Zulip):

That is, there's specific code to suppress insertion of } after if, while, etc.

matklad (Feb 20 2019 at 15:39, on Zulip):


matklad (Feb 20 2019 at 15:39, on Zulip):

Here's a video with the if { behavior

Last update: Jul 29 2021 at 21:45UTC