3 ms·

Tree-sitter grammars take more effort than textmate ones for the most basic highlighting, but provide less accurate parse trees than a compiler could use for mo

Tree-sitter grammars take more effort than textmate ones for the most basic highlighting, but provide less accurate parse trees than a compiler could use for more advanced features and highlighting. I understand what they were going for but I don't "get" the trade-off. At least as long as the parse trees are inherently worse: Even ignoring context-dependent grammars, last time I checked tree-sitter parsers had many edge cases in which they'd accept invalid syntax but not mark the parse trees as bad, which makes them unsuitable for compiler use.

DannyBee 3y ago
Using compilers for highlighting basically doesn't happen because they are too slow. They are used for progressive improvement as a result (depending how fast, it can take at least 5-10 seconds post-update to get a result. For slower languages, minutes). I'm not sure what "more effort" means - for lots of languages, it's less effort than textmate because people spend lots of hacks trying to work around textmate to get it to highlight even slightly complex languages right. It's nesting mechanism is complicated, etc. Tree-sitter is faster than textmate on initial parse in lots of cases, and update a lot faster than textmate (since they can be incrementally updated and textmate can't). They are not meant as compiler replacements. Again, compilers are slow, and rarely incremental. Using tree sitter for folding/highlighting/etc, and compilers for additional progressive type info, is the right path. Textmate is worse than useless for anything but super simple languages. I say this as a person who has written about 15 vscode language servers for all sorts of varied languages, from CNC g-code to you name it. I even implemented incremental parsing/lexing for ANTLR's typescript port (and then java port), as a comparison to tree-sitter ;) It can be made as fast, but tree-sitter is clearly winning the current popularity contest ;) I'd say for those languages, textmate work was the worst part of all of them, and getting textmate to highlight properly required more work than writing proper lexers/parsers. I still fix more bugs in textmate grammars than anywhere else. Part of the reason is that it requires fairly complex regexps. Part of it is getting it to stop trigger on things it shouldn't, because you have to emulate a lot of state. Again, you start to spend a lot of time working around it, rather than working with it. Meanwhile, yes, the upfront work of a lexer in tree-sitter is sometimes more. But it is much easier to get it to work, to rely on it working, etc. In the end, all my language servers were easier to implement in tree-sitter, and some don't even have compilers (like g-code), but have control flow/blocks/etc. tree-sitter handled all language duties there. Hopefully this helps you "get" the tradeoff. Anyone who has written enough vscode language servers would tell you the same thing. I have yet to meet someone in the community who writes language servers who is excited or happy with textmate vs tree-sitter. Where do you think the push came from?
- debugnik 3y ago
  First, I specifically said that textmate takes less effort for "the most basic highlighting", that would be keywords, literals, comments, etc. Trying to encode a CFG in it would obviously be painful, but why would you? Use an actual parser at that point, but you might as well use a correct one. Second, there's this idea that compiler parsers are inherently slow and require a full build to use or something. As if tree-sitter parsers were using some magic tech unavailable to compilers, and most new ones weren't modular or didn't offer APIs. It's not even hypothetical, increasingly more modern languages have semantic highlighting in real-time as part of the toolchain. And in fact, I actually wanted to use that tech in a compiler, I said I tried to use tree-sitter for one, but that's where my big issue with tree-sitter came in: It would return parse trees that blatantly didn't match the grammar I wrote, and not mark them as bad syntax in any way. That's not error recovery, that's swallowing errors. If it does that, I'd rather work on making toolchain parsers better than fighting tree-sitter. Even the "run the parser on the editor" part is solvable, since tree-sitter parsers are being shipped as WASM. A WASM interface for running possibly incremental parsers (that tree-sitter would also use) sounds more interesting, really.
  - DannyBee 3y ago
    There's a lot here, and i'mn not sure where to start. You are complaining about a lot of things simultaneously, and it's hard to tell exactly which point you want to tackle. For correctness - gonna leave this alone, i don't know of issues here and it seems fairly orthogonal to speed which is where we started. I've done parsing and lexing for decades now, including multiple compilers. So i'll try again - for magic tech, tree-sitter does actually have "magic tech" unavailable to most compilers, and i explained exactly what it was - but you simply want to deride it for some reason - not obvious to me. the magic tech is that 1. tree-sitter ast/lex tokens (for purposes of incremental lexing/parsing) are compiler/language agnostic. it does not care. This is not true of most compilers 2. it allows incremental lexing/parsing when you keep those ast/tokens under the text of your editor. It only needs to be informed of what edit was made (add/change/remove of a range of characters is fine) and have random access to the text. This is not true of most compilers. 3. The incremental lexing/parsing is extremely fast. It is optimal in the amount that has to be re-lexed/parsed, which for both is bounded by the amount of max used lookahead in the grammar, which for most languages, is really small (again, not the theoretical lookahead, but the actual-used-during-lex/parse lookahead). Not true of most compilers. Can you design compilers that can do this? Sure, i was at IBM when we did visualage, which could do this in other ways, though not optimally. As mentioned, i've even implemented the optimal incremental lexing/parsing algorithms in other parser/lexer generators, and even some compilers. Is it common? Not a chance. Your claim that increasingly more modern languages have semantic highlighting in real time "built in" is simply false - most cannot real time semantic highlight even a 100k file on every keystroke. There are a very small number which can, and it's mostly by luck - they fall down on larger files or other complex cases because they have no incrementality. clangd is about the closest you get. rust-analyzer definitely can't. etc Lexing has always been really fast, and doable in a single pass, that has never been the problem. Meanwhile, what i just described (updated highlighting on ever keystroke) is trivial with tree-sitter for all languages because of its optimality and agnostism. If you want to see your claim in action - turn on semantic highlighting for vscode and type fast - most of the time you will lose syntax highlighting because things can't keep up. see, e.g., https://github.com/microsoft/vscode-extension-samples/issues/851 https://github.com/microsoft/vscode-extension-samples/issues... Again, yes, you could make a compiler for every language which supports a mode that does what tree-sitter does. and people could carefully implement parsers/lexers in each of their favorite compilers and languages that support optimal incremental parsing in them. and then pay the cost of integrating 50 language specific ways of transforming these to work with the editor, basically reinventing what tree-sitter already did right. (As per above, the current semantic token and highlighting support does not resolve this, and the interface it provides can't support it, last i looked). You seem to really otherwise be complaining that you believe it does always generate correct parsers. Like I said, that seems totally orthogonal to anything about the speed issue, and if that's your real concern, have at it.
duped 3y ago
Tree sitter grammars generate a complete/concrete syntax tree with incremental updates, they necessarily have to be able to represent invalid source text (because users will type it!). If you're using a tree-sitter grammar as the input to a compiler (which is not what its designed for) you need to write a pass to convert from CST to AST, as you normally would.
- debugnik 3y ago
  No, I specifically said "accept invalid syntax but not mark the parse trees as bad". Tree-sitter is supposed to accept invalid syntax, yes, but also tag the nodes as such. And at the time it seemed upstream didn't intend to fix the edge cases where it fails to do so, it just gave syntax trees that didn't match the grammar.

DannyBee 3y ago

Using compilers for highlighting basically doesn't happen because they are too slow. They are used for progressive improvement as a result (depending how fast, it can take at least 5-10 seconds post-update to get a result. For slower languages, minutes). I'm not sure what "more effort" means - for lots of languages, it's less effort than textmate because people spend lots of hacks trying to work around textmate to get it to highlight even slightly complex languages right. It's nesting mechanism is complicated, etc. Tree-sitter is faster than textmate on initial parse in lots of cases, and update a lot faster than textmate (since they can be incrementally updated and textmate can't). They are not meant as compiler replacements. Again, compilers are slow, and rarely incremental. Using tree sitter for folding/highlighting/etc, and compilers for additional progressive type info, is the right path. Textmate is worse than useless for anything but super simple languages. I say this as a person who has written about 15 vscode language servers for all sorts of varied languages, from CNC g-code to you name it. I even implemented incremental parsing/lexing for ANTLR's typescript port (and then java port), as a comparison to tree-sitter ;) It can be made as fast, but tree-sitter is clearly winning the current popularity contest ;) I'd say for those languages, textmate work was the worst part of all of them, and getting textmate to highlight properly required more work than writing proper lexers/parsers. I still fix more bugs in textmate grammars than anywhere else. Part of the reason is that it requires fairly complex regexps. Part of it is getting it to stop trigger on things it shouldn't, because you have to emulate a lot of state. Again, you start to spend a lot of time working around it, rather than working with it. Meanwhile, yes, the upfront work of a lexer in tree-sitter is sometimes more. But it is much easier to get it to work, to rely on it working, etc. In the end, all my language servers were easier to implement in tree-sitter, and some don't even have compilers (like g-code), but have control flow/blocks/etc. tree-sitter handled all language duties there. Hopefully this helps you "get" the tradeoff. Anyone who has written enough vscode language servers would tell you the same thing. I have yet to meet someone in the community who writes language servers who is excited or happy with textmate vs tree-sitter. Where do you think the push came from?

debugnik 3y ago
First, I specifically said that textmate takes less effort for "the most basic highlighting", that would be keywords, literals, comments, etc. Trying to encode a CFG in it would obviously be painful, but why would you? Use an actual parser at that point, but you might as well use a correct one. Second, there's this idea that compiler parsers are inherently slow and require a full build to use or something. As if tree-sitter parsers were using some magic tech unavailable to compilers, and most new ones weren't modular or didn't offer APIs. It's not even hypothetical, increasingly more modern languages have semantic highlighting in real-time as part of the toolchain. And in fact, I actually wanted to use that tech in a compiler, I said I tried to use tree-sitter for one, but that's where my big issue with tree-sitter came in: It would return parse trees that blatantly didn't match the grammar I wrote, and not mark them as bad syntax in any way. That's not error recovery, that's swallowing errors. If it does that, I'd rather work on making toolchain parsers better than fighting tree-sitter. Even the "run the parser on the editor" part is solvable, since tree-sitter parsers are being shipped as WASM. A WASM interface for running possibly incremental parsers (that tree-sitter would also use) sounds more interesting, really.
- DannyBee 3y ago
  There's a lot here, and i'mn not sure where to start. You are complaining about a lot of things simultaneously, and it's hard to tell exactly which point you want to tackle. For correctness - gonna leave this alone, i don't know of issues here and it seems fairly orthogonal to speed which is where we started. I've done parsing and lexing for decades now, including multiple compilers. So i'll try again - for magic tech, tree-sitter does actually have "magic tech" unavailable to most compilers, and i explained exactly what it was - but you simply want to deride it for some reason - not obvious to me. the magic tech is that 1. tree-sitter ast/lex tokens (for purposes of incremental lexing/parsing) are compiler/language agnostic. it does not care. This is not true of most compilers 2. it allows incremental lexing/parsing when you keep those ast/tokens under the text of your editor. It only needs to be informed of what edit was made (add/change/remove of a range of characters is fine) and have random access to the text. This is not true of most compilers. 3. The incremental lexing/parsing is extremely fast. It is optimal in the amount that has to be re-lexed/parsed, which for both is bounded by the amount of max used lookahead in the grammar, which for most languages, is really small (again, not the theoretical lookahead, but the actual-used-during-lex/parse lookahead). Not true of most compilers. Can you design compilers that can do this? Sure, i was at IBM when we did visualage, which could do this in other ways, though not optimally. As mentioned, i've even implemented the optimal incremental lexing/parsing algorithms in other parser/lexer generators, and even some compilers. Is it common? Not a chance. Your claim that increasingly more modern languages have semantic highlighting in real time "built in" is simply false - most cannot real time semantic highlight even a 100k file on every keystroke. There are a very small number which can, and it's mostly by luck - they fall down on larger files or other complex cases because they have no incrementality. clangd is about the closest you get. rust-analyzer definitely can't. etc Lexing has always been really fast, and doable in a single pass, that has never been the problem. Meanwhile, what i just described (updated highlighting on ever keystroke) is trivial with tree-sitter for all languages because of its optimality and agnostism. If you want to see your claim in action - turn on semantic highlighting for vscode and type fast - most of the time you will lose syntax highlighting because things can't keep up. see, e.g., https://github.com/microsoft/vscode-extension-samples/issues/851 https://github.com/microsoft/vscode-extension-samples/issues... Again, yes, you could make a compiler for every language which supports a mode that does what tree-sitter does. and people could carefully implement parsers/lexers in each of their favorite compilers and languages that support optimal incremental parsing in them. and then pay the cost of integrating 50 language specific ways of transforming these to work with the editor, basically reinventing what tree-sitter already did right. (As per above, the current semantic token and highlighting support does not resolve this, and the interface it provides can't support it, last i looked). You seem to really otherwise be complaining that you believe it does always generate correct parsers. Like I said, that seems totally orthogonal to anything about the speed issue, and if that's your real concern, have at it.

duped 3y ago

Tree sitter grammars generate a complete/concrete syntax tree with incremental updates, they necessarily have to be able to represent invalid source text (because users will type it!). If you're using a tree-sitter grammar as the input to a compiler (which is not what its designed for) you need to write a pass to convert from CST to AST, as you normally would.

debugnik 3y ago
No, I specifically said "accept invalid syntax but not mark the parse trees as bad". Tree-sitter is supposed to accept invalid syntax, yes, but also tag the nodes as such. And at the time it seemed upstream didn't intend to fix the edge cases where it fails to do so, it just gave syntax trees that didn't match the grammar.