Tree-sitter: an incremental parsing system for programming tools
github.com
github.com
I can't wait for the tools to get built with this. Paredit for TypeScript. Syntax-tree based highlighting (vs regex highlighting). A command to "add an arg to current function" which works across languages. A command to add a CSS class to the nearest JSX node, or to walk up the tree at the className="| ..." position, adding a new className if it doesn't exist.
There's a nicely documented Emacs package for this [1]. The documentation is at [2]. The parse trees work great. There's syntax highlighting support and tree-walking APIs. There's a bit of confusion about TSX vs typescript langs but it's fixable with some config change [3].
[1]: https://github.com/ubolonton/emacs-tree-sitter [2]: https://ubolonton.github.io/emacs-tree-sitter/ [3]: https://github.com/ubolonton/emacs-tree-sitter/issues/66#iss...
EDIT: finally found it https://github.com/alphapapa/prism.el
I don't see it as condescension though. I think it's just a way of speaking.
It's one thing to joke about it a little, but this is just arrogance on display with obvious derision for us children who find that traditional syntax highlighting is beneficial.
I recall reading once that Vim tabs were a crutch for people who "can't remember what they're working on". It's the same kind of arrogance and presumptiveness.
"You've all seen syntax coloring, right? That's something we put in our text editors to make it easier for kindergardeners to do programming"
:)
This would be a wonderful idea in any programming language.
But I agree with the other commenter that this speaker is really condescending. Not a person I'd want to work with.
The query language is also what's used to drive the fuzzy/ctags-like Code Navigation feature. Both of those are powered by tree-sitter query files defined in each language's repo, like these for Go: https://github.com/tree-sitter/tree-sitter-go/tree/master/qu...
Curious if there's any efforts to bring tree-sitter to VSCode? Exposing tree-sitter to extensions could open up so many possibilities like OP mentioned.
The potential for this is essentially something like Paredit, but for all languages.
If you know a Lisp I recommend just giving paredit a spin for a few minutes, it's an interesting experience.
Calling it a "reflex" is an interesting phrase! Tools like magit let me encode complicated processes into muscle memory, in a way where retrieval doesn't have to go through remembering and typing a string. Structural editing is similar.
Now it just feels vaguely annoying to work without it. It's fine, it's just one of those ergonomic changes that nags at you a bit. Kind of like the opposite of that feeling of taking off uncomfortable business clothes at the end of the day. Or what I imagine people who are better at vim than me keep talking about.
It's about typing code, as opposed to typing text, with all the structural, highlighting, auto-formatting, auto-completion, error-detection, etc advantages this brings.
And I can stop feeling like my fingers have all lost a knuckle when I'm writing Typescript :)
Is there a list of ideas for Structural Editing in C-like languages?
I can think of `extend-selection, `move to parent block`, `add arg to function`
The new code runs way faster and is so much nicer to work with.
Once all the kinks are gone, I can’t imagine going back.
[1] https://github.com/emacs-csharp/csharp-mode/blob/master/csha...
- indentation may be fine for a final doc, but not always while editing. Especially for new lines starting new code-blocks.
- adding new syntax not already known by tree-sitter requires up streaming to at least 2 repos before we can use it in a released version of our package. This can feel less hands on and slow than working in a single repo where you have full control.
No super-biggies yet though.
We've been busy building out true precise code intelligence/navigation support, but we also have a mode for zero-configuration code navigation based on text search, universal-ctags, and hand-rolled regular expressions (which works surprisingly well!). Tree-sitter would definitely give better results than our current ctags-based approach. It's been catching our attention more and more lately, and we have plans to use it to upgrade our out-of-the-box, instant code navigation experience.
It's not the exact right fit for our primary goals though, since it's designed around being extremely fast while editing and robust against errors. Sourcegraph is only used for navigating committed code, so we're leveraging formats like LSIF to generate complete semantic graphs of codebases and their entire dependency tree. That'll enable a lot of features that are out of reach for tree-sitter, but is a lot harder to get working out of the box and it's a much bigger technical investment.
It's very interesting to see the topological space that houses these solutions fill out. Every tool has its own set of unique trade-offs and fall somewhere on these spectrums:
- fast vs slow
- precise vs imprecise
- zero-configuration vs configuration required
We've visited a few islands in this space but still very curious to see what other islands can be discovered. We're especially excited about tools and formats like tree-sitter and LSIF around which a large and supportive community can grow so that all the products we love and rely on as developers can all make forward progress.
Take PHP, a language that a lot of people use: the tree-sitter-php extension doesn't support features added in 2019, let alone features added towards the end of 2020.
If you want an up-to-date PHP parser, there's really only one open-source parser[0] that's accurate enough to be used on PHP codebases old and new, and it's written in PHP. Then if you want to parse in a robust fashion you have to adopt a number of hacks to get everything working.
I hadn't encountered LSIF before – can GitHub be configured to use those maps?
It does seem this way. Another reply [1] this post makes the same point with a nice proof-of-concept as well.
--- [1] https://github.com/tree-sitter/tree-sitter-c/issues/51
So, I would say that it's not on our near-term roadmap.
exec_wasm(generate_wasm(generate_c(grammar)))
Now if you can make that whole fn chain incremental, then a delta_grammar -> delta_c -> delta_wasm -> delta_recomputed_wasm_call stack, this will propagate deltas down to exec_wasm and you could dynamically execute the generated code as the grammar changes.
[1] https://github.com/tree-sitter/tree-sitter/tree/master/lib/s...
I agree about the Objective-C grammar! Although it looks like somebody's started work on it:
I was wondering if this is a case I could open an issue about? Is this for the main tree sitter repo or should I open one language-by-language?
I was looking into automating some stuff across all languages with tree-sitter but handling all of the languages comments syntaxes made it very hard.
Are you talking about conventions like JSDoc, for putting structured data inside of comments? On GitHub, we handle that by parsing JSDoc comments in a separate pass, using a separate parser. We do it this way because JSDoc isn't really part of the JavaScript language, not all projects use JSDoc, and not all applications are interested in parsing the text inside of comments.
/* This comment
* Should just be alphanumeric.
*/ /* Something */
{ Something }
" Something "
"Something"https://github.com/nvim-treesitter/nvim-treesitter/issues/87...
Could you possibly chime into that discussion and help them with any possible insights you might have on that? That would be really awesome! TIA <3
In the near future, we'll create some more GitHub-specific documentation that walks you through how to add advanced language support for any programming language on GitHub, by writing a Tree-sitter grammar, and then by writing the tree queries that are used for syntax highlighting, simple code navigation, and someday soon... precise code navigation.
Edit: sorry, I just saw that you had answered that below.
Would tree-sitter be able to be used for that? (What I want is to feed tree-sitter a stream of keystroke changes and get out a stream of minimal AST changes as a result).
[0]: https://twitter.com/simonbs/status/1352697855845273600
[1]: https://twitter.com/simonbs/status/1362492842141171720?s=21
Though AIUI the basic syntax highlighting is done by the editor (e.g. VSCode uses Textmate grammar support).
(semantic highlighting is pretty slow for C++ with font-lock, with tree-sitter it's a breeze :))
https://github.com/tree-sitter/tree-sitter-ruby/blob/master/...
I find it absolutely amazing that a grammar for something as complicated as Ruby can be so concise. Less than a thousand lines. The corresponding Bison grammar is 13k lines. And I think the tree-sitter one is scannerless so also includes the lexer?! How do they do it?
Precisely because the language is complicated and less amenable to LR parsing.
There has been, however, discussion about the need to clean up some of the lesser-used language feature, but obviously doing so carries risks.
Note also that (as I alluded to above) the parsing technique that Tree-sitter uses, "LR parsing", makes some things more difficult to parse than they'd be with another kind of parser. This is a deliberate trade-off, because LR parsing makes certain features of Tree-sitter, like fast re-parsing in response to input changes, much much easier.
Everything is kind-of-but-not-really an object, a reference, and a function, all at the same time - which sounds complicated but in my head... turns out to be pretty simple. Everything's just kind of different flavors of the same thing. `attr_accessor` is a good place to see this in action.
The flexibility comes more from the variety of available core language options (procs, blocks, and lambdas) and core libraries (map/each/collect, for example), not from a variety of underlying concepts.
It is a little terrifying in the sense that I'd not want to write language level tools (eg: syntax highlighter).
But if you have scheme on one end and natural language on the other, ruby leans à bit towards natural language - but in a good way. In some ways ruby isn't that different from Smalltalk - but it has a lot (sometimes I think too many, sometimes not) conveniences.
Parantheses and brackets are largely optional "where it makes sense". Conditionals support postfix, eg these are equivalent:
if should_send?()
send_mail({to: 'u@x.com'})
end
send_mail to: 'u@x.com' if should_send?With tree-sitter you're hand-writing a 1k file. With Bison you're hand-writing a 13k file.
- https://github.com/tree-sitter/tree-sitter-ruby/blob/32cd5a0... - https://github.com/tree-sitter/tree-sitter-ruby/blob/32cd5a0...
So about 2k loc.
The trickiest (and most verbose) parts of the external scanner have to do with heredocs and the various ways to declare literals (strings, symbols, regexes, etc).
It also seems somehow to be completely declarative? How have you managed to transform Ruby parsing to be context-free? For example where's the set of what's currently a local variable so you can distinguish from method calls?
To be fair, we're cheating a little bit because the Ruby grammar relies so heavily on an external scannar, which is just under 1,000 lines of C++: https://github.com/tree-sitter/tree-sitter-ruby/blob/master/...
I really want to try tree-sitter for using in an actual Ruby implementation because it's so beautiful!
There's no symbol table in the parser, so at parse time, we don't distinguish those cases:
$ cat test.rb
module Test
def test1
x = 14; x
end
def test2
y = 14; x
end
end
$ tree-sitter parse test.rb
(program [0, 0] - [9, 0]
(module [0, 0] - [8, 3]
name: (constant [0, 7] - [0, 11])
(method [1, 2] - [3, 5]
name: (identifier [1, 6] - [1, 11])
(assignment [2, 4] - [2, 10]
left: (identifier [2, 4] - [2, 5])
right: (integer [2, 8] - [2, 10]))
(identifier [2, 12] - [2, 13]))
(method [5, 2] - [7, 5]
name: (identifier [5, 6] - [5, 11])
(assignment [6, 4] - [6, 10]
left: (identifier [6, 4] - [6, 5])
right: (integer [6, 8] - [6, 10]))
(identifier [6, 12] - [6, 13]))))
For some use cases (e.g. syntax highlighting, depending on your colorization rules) it doesn't matter, and so we don't want to pay the cost. If it does matter (like in an actual implementation), then you'd have to implement this yourself and drive it by the parse tree you get from tree-sitter.
So you can't read anything from a method call! I can make it so, if you're doing a class method (of any kind) you have to invoke the constructor, as described in "What is a method?" There's also a few new techniques like "new_class_method", which requires creating an object (of some kind) for that class... but what about that? It's not "I've just fixed Tree-sitter's problem"; it's that Tree-sitter hasn't yet resolved the problem yet - there are other parsing problems besides Tree-sitter in Ruby itself like those of classes (and classes are not part of Tree-sitter) and things that are known as "type-traits" and so on - so as it's not quite enough it can be done by other things. The reason for using LR grammar is that when it comes to this - what do I want from that grammar?
The point I'm making here is that LR doesn't give a reason for what you're doing. As a programmer you are trying to write code that is portable because - if it works in a domain you don't understand (such as Ruby) - then you don't know what you're doing is wrong. There can be a domain (as in any language) that's a lot more complex than this - but since we've got that, how can I be sure it won't mess up the code I'm writing?
What code? The parser? How can it be simpler than its syntax? It has syntax and semantics, which is strictly more than the syntax.
> The point I'm making here is that LR doesn't give a reason for what you're doing.
What do you mean 'what you're doing'?
One thing I love about tree-sitter is how both the grammar and the resulting ASTs are so readable. I can come back to this project after months of not contributing and pick up right where I left off.
Tree-sitter: new incremental parsing system for programming tools (2018) [video] - https://news.ycombinator.com/item?id=21675113 - Dec 2019 (28 comments)
Tree-sitter – a new parsing system for programming tools [video] - https://news.ycombinator.com/item?id=18213022 - Oct 2018 (25 comments)
Others?
Atom understands your code better than ever before - https://news.ycombinator.com/item?id=18349013 - Oct 2018
It's fair to say we can classify a snippet of code based on either single or multiple AST paths produced by treesitter. Right now only doing the programming language but extending it to function classification or description etc isn't out of the question we just don't need it right now.
If you're interested, GitHub is already using it [2] for that purpose and Sourcegraph is experimenting it [3]
[1] https://github.com/alidn/lsif-os [2] https://github.com/github/semantic [3] https://github.com/sourcegraph/sourcegraph/issues/17378
Our currently-available code navigation system also uses Tree-sitter, but it is pretty simple; it just matches up references and definitions by their name.
Is there a chance for it getting integrated to vim? Last I checked vim used a regex method which was slow and faulty.
Seems like this would make it much easier to bootstrap a performant language-server. Very cool; maybe that will be my next project.
So if you're writing a tool for a single language (like a language server), it should be as easy as adding tree-sitter and tree-sitter-blah to your cargo manifest.
[1] https://news.ycombinator.com/item?id=26227476 [2] https://tree-sitter.github.io/tree-sitter/using-parsers#patt...
This sounds very interesting. Will the query DSL (spec) be available to the public?
https://github.com/tree-sitter/tree-sitter/issues/255
Tree sitter will basically always generate a parse tree, even for malformed input, in which case it will add ERROR nodes for the bits it doesn't like (it will also inform you that there were problems with the parse by setting a boolean attribute). So you have some information you can use to construct a useful error message yourself, but some parser generators will handle this better (although it has to be said that the difficulty of obtaining good error messages from a parser generator are still one of the main the reasons production parsers are mostly written by hand).
I’m going to play with this and see if I can make a generic language server for vscode that works across languages. Unless someone has already done that.
What would be really cool is that tree-sitter (or a sister package) that provides incremental formatting primitives across languages.
The closest language agnostic formatter that comes to mind is prettier.js with its extensions.
incremental parser —> language server -> formatter across languages would be super rad.
With its syntax tree query frontend I wonder whether tree-sitter would make a good interpreter frontend for some niche languages, or you need something more powerful.
For some languages, yes. https://news.ycombinator.com/item?id=26227214
> If yes, are the libraries open-source?
They are! tree-sitter itself is open-source [1], as are all of the language parsers we've listed on the homepage [2]. The syntax highlighting support is documented here [3].
[1] https://github.com/tree-sitter/tree-sitter
[2] https://tree-sitter.github.io/tree-sitter/#available-parsers
[3] https://tree-sitter.github.io/tree-sitter/syntax-highlightin...
That said, this is exactly why we've released tree-sitter as an open-source project. That way there's no need for anyone to be blocked on my team finding the time to work on an SQL parser. Most extant tree-sitter parsers [1] have been developed by external language communities, and not by the core tree-sitter maintainers.
(Also note that SQL is a particularly wrinkly language, since there are so many different dialects. Are you looking for an ANSI SQL parser? A MySQL SQL parser? One that covers all of them to some degree?)
[1] https://tree-sitter.github.io/tree-sitter/#available-parsers