3 ms·

(author of the blog post here, personal opinion) Tree-sitter is much more general (and I guess way more complex) and most likely cannot use some tricks we use

(author of the blog post here, personal opinion) Tree-sitter is much more general (and I guess way more complex) and most likely cannot use some tricks we use for "simple" bracket pair parsing. For example, we can almost always re-use nested bracket pairs when characters are inserted/deleted, because the bracket pair language is so simple and it does not matter where a bracket pair is in the AST. But when parsing C# and adding a single opening bracket at the beginning of the file, I doubt namespace/class declarations stay namespace/class declarations. Also, long lists in Tree-sitter seem to cause linearly growing incremental parsing time - that's why we use balanced (2,3) trees. You can try it out on their playground [1] by selecting JavaScript and adding some 100k `{}`s. On my machine, adding a single character takes 50ms. When there are 200k bracket pairs, it takes 100ms. When all these brackets are contained in a single bracket pair however, adding characters after this single root pair is fast again (<1ms). But to be honest, Tree-sitter is still mind boggling fast. [1] https://tree-sitter.github.io/tree-sitter/playground https://tree-sitter.github.io/tree-sitter/playground

cormacrelf 5y ago
On the first point, one idea would be to implement the simple bracket pairs language as a TS grammar, stand-alone and independent of any other syntax highlighting. The C# problem of making the syntax invalid and killing the brace highlights disappears. The linear scanning behaviour you describe is due to the change in the left and right parse context for all of those pairs. Yes, it’s linear when you invalidate a subtree, but in the case of a simple bracket pairs language, the damage is limited to scanning through the children of top level brace pairs, and each child subtree is trivial to check. From the IGLR paper: > In a state-matching implementation, each node representing a nonterminal symbol contains a record of the configuration of the pushdown automaton (the ‘parse state’) when the node was shifted onto the stack. A subtree can be reused when both its left and right context are unchanged … Imagine { is prepended to abc(def, {ghi}). I believe the “abc” needs re-parsing, and so does the () subtree as their left parse state is now the “looking for }” state instead of “looking for ({[“ and “looking for )” respectively. But it’s limited to one level deeper — after you split the () subtree, every subtree inside it is still in the “looking for )” configuration on both sides. Specifically, the “def”, “,” and “{ghi}” are fully reused. There are only three possible parse states, so generally you get a lot of subtree reuse. You get even better subtree skipping performance by making long sequences without an brace into a single node, instead of eg tokenising by word and not grouping them. (In this case, “def, “ instead of splitting that.) So realistically for your C# example, only the namespace node is split, and the linear scan is through all the top level brace pairs within the namespace but no deeper. You’ve described IGLR’s best case scenario for incremental parsing an initial brace insertion. Languages that don’t have namespaces would be worse off (but still not too bad). For more realistic languages than {}{}{}{}{}{}{}{}.js I think this approach would work very well. If I liked brace pairs (I don’t) then I would implement this dead simple new grammar and turn it into a Neovim plugin. The existing nvim-ts-rainbow plugin uses queries on existing languages, so is very good at giving perfect/correct pairs and customising per-language, but exhibits the invalid syntax problem and also performance issues which appear to be resolved for most people, but may be back with bigger documents. (Edit — you would need a few variants to account for comments and strings. That makes it a bit more annoying.)
int_19h 5y ago
> when parsing C# and adding a single opening bracket at the beginning of the file, I doubt namespace/class declarations stay namespace/class declarations It really depends on how you parse. In VS, at least, this works, in a sense that, while the resulting code is invalid, the editor can still correctly semantically highlight it, and provide code completions etc.

cormacrelf 5y ago

On the first point, one idea would be to implement the simple bracket pairs language as a TS grammar, stand-alone and independent of any other syntax highlighting. The C# problem of making the syntax invalid and killing the brace highlights disappears. The linear scanning behaviour you describe is due to the change in the left and right parse context for all of those pairs. Yes, it’s linear when you invalidate a subtree, but in the case of a simple bracket pairs language, the damage is limited to scanning through the children of top level brace pairs, and each child subtree is trivial to check. From the IGLR paper: > In a state-matching implementation, each node representing a nonterminal symbol contains a record of the configuration of the pushdown automaton (the ‘parse state’) when the node was shifted onto the stack. A subtree can be reused when both its left and right context are unchanged … Imagine { is prepended to abc(def, {ghi}). I believe the “abc” needs re-parsing, and so does the () subtree as their left parse state is now the “looking for }” state instead of “looking for ({[“ and “looking for )” respectively. But it’s limited to one level deeper — after you split the () subtree, every subtree inside it is still in the “looking for )” configuration on both sides. Specifically, the “def”, “,” and “{ghi}” are fully reused. There are only three possible parse states, so generally you get a lot of subtree reuse. You get even better subtree skipping performance by making long sequences without an brace into a single node, instead of eg tokenising by word and not grouping them. (In this case, “def, “ instead of splitting that.) So realistically for your C# example, only the namespace node is split, and the linear scan is through all the top level brace pairs within the namespace but no deeper. You’ve described IGLR’s best case scenario for incremental parsing an initial brace insertion. Languages that don’t have namespaces would be worse off (but still not too bad). For more realistic languages than {}{}{}{}{}{}{}{}.js I think this approach would work very well. If I liked brace pairs (I don’t) then I would implement this dead simple new grammar and turn it into a Neovim plugin. The existing nvim-ts-rainbow plugin uses queries on existing languages, so is very good at giving perfect/correct pairs and customising per-language, but exhibits the invalid syntax problem and also performance issues which appear to be resolved for most people, but may be back with bigger documents. (Edit — you would need a few variants to account for comments and strings. That makes it a bit more annoying.)

int_19h 5y ago

> when parsing C# and adding a single opening bracket at the beginning of the file, I doubt namespace/class declarations stay namespace/class declarations It really depends on how you parse. In VS, at least, this works, in a sense that, while the resulting code is invalid, the editor can still correctly semantically highlight it, and provide code completions etc.