Skip to main content
Loading Explore guides…
Syntax Tree Project Overview · Acedra
Home
Explore
Computer Science
Syntax Tree Project Overview
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
87 segments
Copy
Hide video
0:00
(soft music)
0:11
- I am gonna go ahead and get started because in my efforts to explain as much as possible, I have put way too many slides into this presentation and it will be a pretty good miracle if I finish on time. So we're gonna cover a lot of information. My goal with this talk is to give you a broad overview of what this project is, dive into some technical details, but to try to not leave you behind if you're less familiar with some of the concepts that I'm gonna talk about.
0:35
So this talk is about syntax tree. It's a project that I started about, well, in reality about four years ago, but in essence, about a year and a half ago. It is a project that was funded by the Ruby Association to create a standard library formatter.
0:52
There are a lot of different formatters that there at this point, but at the time that I started this work, there wasn't one.
1:00
Since the inception of the project, it has become much more than a formatter. It's become a whole host of things that I'm gonna talk to you about today. My name is Kevin Newton. I work on the Ruby on Rails infrastructure team at Shopify. You may notice that there's a fair number of us here. Come talk to us if you want to find out about some of the problems that we're solving at Shopify working on Ruby, making it a 100 language, and generally, hoping to improve the ecosystem.
1:26
You can find me at @kddnewton online. I'm on Twitter for however long it lasts, going down with the ship.
1:36
So syntax tree, what is syntax tree? To explain to you what syntax tree is, we need to talk about a couple of concepts. We need to back it up, so what are those concepts? We have what is a parser? What does the parser do? How does it function? We have what is a syntax tree? This is kind of a problem. I tried to be consistent with my capitalization, but as you may know, naming is one of the hardest things in computer science, and I very poorly named my project syntax tree.
2:01
So you might hear me say, syntax tree, syntax tree. Syntax tree is a distinct thing from the Syntax Tree Project. I will try to not confuse you. The last concept is a visitor. I wanna talk to you about the visitor pattern and how that applies to syntax trees. So put me with these guys down here and we'll start talking about what a parser is. You may have seen this statement before, Matz is nice so we are nice. What a parser job is to take plain text content
2:26
and transform it into some other kind of data structure that a programming language can understand, not even necessarily programing language, but some other structure.
2:34
The first step is lexical analysis. Lexical analysis takes a plain text segment and breaks it up into chunks. So first we're gonna say, okay, Matz is a noun, is is a verb, nice is an adjective, so is a conjunction, repeat, repeat, repeat and a period. So this is our lexical analysis, we determine which things. Now, mind you, in English, some of these things can be other things, this is just for example purposes, I'm not trying to parse English. Semantic analysis is the next part of this.
3:01
We're gonna take just these two segments of the sentence and we're gonna determine what they are. We're gonna give a name to this concept. You see, we have a verb to the left and an adjective to the right. We're gonna define a grammar. This is the same idea as in English grammar, right? Grammar is the definition of how these words can fit together to form larger concepts. So a verb-phrase, we're gonna call this a verb-phrase. It takes a verb and an adjective. Okay, now we have a verb-phrase.
3:26
You might see these are two little tiny trees, tree.
3:31
Matz and we, these are both nouns, at least they function as nouns in this sentence. So we're gonna call this a subject-phrase. A subject-phrase is a noun followed by a verb-phrase, okay? Now we have a bigger tree.
3:43
We add the word so, that's a conjunction. So I had to look this up, but turns out this is a subordinating conjunction. I don't actually know English that well as it turns out. But a subordinating conjunction is two subject phrases joined by a conjunction. So okay, now we have a subordinating conjunction. Remember there was one more token to join. We have a period and we're gonna say a sentence, a subordinate conjunction followed by a period. And now we have defined our grammar.
4:08
You will see that there is a tree here. Now, all of the tokens are still in the same order. If you follow them left to right, that's still the same order. But in our heads and when we hear these things, this is what we're doing to fully understand the concepts that are being passed to us. This is what a compiler is doing. In your head you are a compiler for the language that you are hearing.
4:27
Okay, what does this look like in terms of a syntax tree? I'm gonna switch over to light mode here, and we're gonna pretend we're in Ruby and we're going to create objects that represent these nodes, right? This isn't doing anything complicated, it's not doing anything kind of fancy. This is just an object that takes two objects on its initializer, stores them, and represents that node in the tree. And it turns out we can do this for every node in the tree.
4:54
We can just go ahead and put a different class on every single one. We don't need a common ancestor who needs inheritance. We just go and create something for every single one. Good, now we have a node for every node in our tree. Now, if I re-arrange these a little bit, you'll notice that the ones on the left are tokens. These are considered tokens, they just wrap a value from the source code. If we were in a more memory-strict language,
5:17
we could actually just point at the source code and say that that's just a bounds from the source string.
5:24
So there are leaf nodes on the left, on the right are more branches, they're in the middle of the tree. So we're just gonna take one of these nodes and we're gonna expand it out and see what we can do with it, right? We just built up this tree. We have a tree structure and it varies depending on what the input was but we can start to walk this tree and do interesting things to it. So we can add the nice Ruby 2.7 pattern matching to it. We can add some == methods to do some nice comparisons.
5:50
We can add a copy method to do some immutable copies to try to allow mutations over time. But the one I wanna talk to you right now is the accept method and the child nodes method. And specifically, I wanna talk to you about the accept method here. The accept method is kind of an interesting thing that I've added to these nodes. And this brings us to our third topic that I wanna talk to you before I even talk to you about syntax tree, which is a visitor. A visitor, this is a pattern.
6:18
If you go to the Gang of Four or any of the other object-oriented patterns books, you'll see the visitor pattern described, and this is how we use it in this place. We have the accept method, we just close it up here and we're gonna add a visitor class. A visitor class is gonna have a visit verb-phrase method that is going to accept a node. And if you go to the bottom here of the main line, we assume we have parsed a verb-phrase, we call accept on it with the visitor,
6:41
it's called the double dispatch visitor pattern 'cause two methods are being called. The accept method gets called, it goes up to the verb-phrase, the verb-phrase then calls visit verb-phrase with self as the argument which goes back into the visitor. So in this way, we go back and we don't have to care when you call accept, what the type of the node is because the node is gonna specialize itself by calling back into the visitor. So we can add visit methods for all of these kinds of nodes,
7:08
provided that the node itself then goes and calls the correct method on the visitor when it itself is called with accept. So we have all of these visit methods and this is our magic visit method. The visit method is generic, it accepts any node and then calls accept. In other languages, you would have an interface or a trait, in Ruby, we just have this magical, you should know what's happening kind of thing, where we are implementing an interface. The interface is the accept interface
7:38
or the visit interface... Sorry, the accept interface, that is expected to then call back into the visitor. So as I mentioned earlier, there's the child nodes method that defines the nodes further down the tree. And now that we have the visit method, we can change visit verb phrase to go and visit each of those children in turn. Now, if we make another method and call this visit child nodes, you'll notice that visit verb phrase can just be visit child nodes and now we can just alias it,
8:08
and actually we can alias every one of these methods. Every single node in the tree is just gonna call back into visit child nodes because they all implement the child nodes method, and then we walk down the tree all of the way, okay.
8:22
What have we actually accomplished here?
8:26
We can start to implement visitors that only care about a subset of the nodes in the tree. This visitor for instance, only cares about the sentence node. It's gonna count all the sentences, this is great, you don't have to handle every kind of node type, you don't have to have a case statement over the different kind of node that you're visiting because this method is only gonna get called if a node itself calls visit sentence. We can implement a pretty printer for this kind of thing.
8:50
This is, if you're not familiar, PP is a standard gem and it's basically a buffer of strings over time.
8:58
You can implement a formatter. We can go and format the node by only implementing the ones that we support, or we can implement it for every single node in the tree and end up formatting it. Now, formatting English is pretty hilarious because you end up just concatenating all the strings together. But in more complex languages like say Ruby, it involves quite a bit more work. So what is syntax tree? Syntax tree is an object layer representing the result of parsing Ruby.
9:23
It itself is not a parser, but it takes the result of parsing and provides this object layer that I just described for English, it provides it for Ruby.
9:34
As opposed to having the nine nodes that I showed you, it has 151, but it's the same concept. And it also provides tools to interact with and manipulate that object layer on top of the result. So if you need to parse Ruby to do something like linting, formatting, static analysis of any form or mutating the tree code mod, there's myriad applications, this provides the tools to go and do that. So what does syntax tree actually do? Five steps, it builds a syntax tree, it formats the syntax tree.
10:04
I'll show you how it does that in a second. I created a CLI to interact with syntax tree itself. I created a language server that you can use to power your IDE so that you can do a format on save. And finally, you can translate the syntax tree into other contexts and I'll show you what that means in a second. Okay, let's pop these guys down here, start with building. Building a syntax tree involves first defining each of those nodes, we showed you how I define those nodes
10:27
for that small grammar of English. This is going to define it for Ruby. If you go into node.rb in the syntax tree repository, you'll see these kinds of definitions for all 151 nodes. It's just plain Ruby. It's not doing anything particularly complicated. You'll notice that we have named fields for every single value and sub node in the tree. We provide the ability to look at the location, which is the source location of that node. We provide any comments that have been attached to the tree.
10:57
I'll talk about that in a second. We provide the accept and child nodes methods, which are part of the visitor pattern that we described earlier. And finally, we provide deconstruct and deconstruct keys, which provide the Ruby 2.7 pattern matching, which is super nice and everyone should be using. Finally, the last kind of important point that I wanna talk to you about is that these things are immutable by default, these use outer readers. They're not meant to be mutated in place
11:23
and there's a lot of reasons for this, but one of the reasons is if you want to mutate these things, I'm gonna provide a better interface than just calling dot value equals because that's a little bit harder to reason about what's actually going to happen. I also want this to be able to be used in raptors. So this interacts with Ripper too, Ripper is a standard library that is a parser generator that goes and provides an event-based parser that I then go and use to build all of these nodes up.
11:54
Ripper itself has 190 events. Syntax tree, 151 was incorrect, I guess I updated this. There are 162 nodes in syntax tree. Actually this number has gone down since I made these slides for various reasons.
12:08
The reason that there are fewer in syntax tree is that I've started to merge some nodes. For instance, if you have A if B and you have if B A, those are actually the same concept in reality and I've actually just merged those into if node to make it a little bit simpler. So how we use Ripper, I'm gonna very, very quickly go through this. You don't actually need to understand this at all, but it's kind of interesting background information. Ripper is a parser that is generated by magic C comments
12:35
in the C Ruby grammar file. So if you go into the C Ruby grammar file, which is parse.y, you'll see all of these kind of weird DSL, super magic comments with exclamation points that then go and dispatch those methods. Ripper itself is just calling methods that you then define to do whatever it is you want and they parse it up from a bottom up of the syntax tree. So let's say we're parsing this top segment class foo, we're gonna have to define these event handlers for on our subclass of Ripper
13:03
that are gonna pass this up the syntax tree. And you'll see on const is gonna get called first. That's a leaf node or a token as we talked about. It's gonna get passed up to on const ref. On ident is gonna call next on vcall. And these values are gonna get parsed up and up and up. On def is gonna call next, finally on class and that is the end, on program is gonna get called at the end. So the issue with this is that it doesn't actually have any location information.
13:26
So if we wanna add some location information, we're gonna need to keep track of additional things. We're gonna need to keep track of keywords as they come in. We're gonna build up a stack and then on class and on def, we're gonna go find those keywords that determine the bounds of the node. So you can see here, this is what we're doing. We're going and we're finding the last one that was pushed onto the stack and then we're gonna go and delete that in order to determine our bounds.
13:48
So right, Ripper is a somewhat difficult interface to work with. My entire idea behind syntax tree is to make it so you don't have to care. You don't care what the parser is. If the parser were to change out from under you in syntax tree, you wouldn't care. That's something you can bear in mind for the end of the talk here. But Ripper doesn't provide everything unfortunately. Ripper is kind of based on the good graces of the Ruby core developers and not everything is actually supported.
14:13
For instance, you might not know this, but there is an interesting syntax here with Lambdas where you can provide Lambda local variables that can shadow parent scope variables, but they don't use their values. So they're specific to that Lambda. Ripper itself does not provide you anything for this. So I go and parse it myself by looking at the source and actually building a sub parser within those methods. It's hairy, but this is kind of the value of using syntax tree is you don't have to care.
14:40
You don't have to care, you're just gonna interact with the visitor interface, any other kind of interface and you just don't even have to worry about it. So right, we go in, we go and build this ourselves, and Lambda locals is the method where all that exists. You can go and look at the state machine that parses that yourself. So the next really difficult part of this is comments. Comments don't show up in Ripper, they're just an event and then you have to deal with them yourself.
15:04
Where can comments be? Comments can kind of be anywhere. All of these are valid places. You can have all these comments in Ruby. Ruby allows you to put comments pretty much anywhere as long as it's after the content of that line. So what do we do? We build up an array over time, each comment is gonna get built. Now, we have an array of comments and then after the parsing is done, we're gonna do a binary search over that child nodes method that I showed you earlier and go and find
15:32
the node that makes the most sense for that given comment. We're gonna favor nodes that immediately follow it or nodes that are on the same line, that's the general idea. Won't go into it too much but after that, you can see how they get attached. So walking the tree, yeah, we're gonna make it.
15:52
As I showed you earlier, this is the visitor interface. We can go and provide the visit methods for every one of these. Visit vcall is one of the... Vcall is just a node in the tree. It means a node that can be either an identifier, a local variable or a method call. And I provide all of those alias as I showed you earlier. It's just a couple and you can go see visitor.rb
16:15
and you'll just see it's just aliases, that's all it is.
16:19
You can start to do very interesting things with these visitors. If you only care about certain nodes, you can allow it to visit every single thing in the file and only find these nodes. Let's say you wanted to do an audit of the options that were being parsed to your Regex in your project, you can go and do this, and this will find every single Regex in your file without you having to do anything else, this is it. We can do things like serialize the entire AST to JSON.
16:44
We can do things like formatting. So what is formatting? Formatting uses the prettyprint algorithm. Prettyprint algorithm was developed in the early '90s from a paper called a Prettier Printer by Wadler (indistinct). It provides an algorithm... It's actually written in Haskell but it was translated into Ruby, and funny enough, it's standard library. There is a gem called prettyprint that just implements this. The idea is to build up groups of nodes,
17:06
text nodes which are just plain content and breakables, which allow it to tell where it should be broken up onto new lines.
17:13
The idea is you build up groups and then when the end of the line is hit, because you need to break it, you break the outermost group first. I'll show you what that means. So let's say we have an array and we have our end of line here, it's good to go. If our end of line moves in, we need to break the outermost group. The outermost group is just that first level of elements in the array, so we break it here and this is how it works. Now, you'll notice that the third element in that array
17:38
is not broken because it fit within that print width. Now, if we move it even further, it's gonna get broken up too. We can break the outermost groups first and then work inward.
17:48
This is the doc nodes. These are the doc nodes that get created, which is basically another syntax tree, but these are the doc syntax tree that gets built up. And you'll see this is the inner one, this is that second element and we have these breakables that determine where it can be broken. But we have the parent group that it itself has breakables. So right, each of these breakables has become new line in tangent, in tandem and that's how it works. So I made too many additions to prettyprint.
18:18
I really, really wanted this to be standard library. And as part of the grant proposal, I said this is gonna be standard library, it's gonna be great. And then the maintainer was like, "What are you doing?"
18:28
So I published a new gem. It's just simpler. It's just simpler. So there's a new gem called prettier print that does exactly this, it is a drop-in replacement for prettyprint. You can use it in any place prettyprint would be used, except it has way more functionality because I don't feel like arguing online. So right, this is the basis for the Ruby formatter. You can do interesting things here, right? If the print width is here, then this is fine. But if you move it to the side,
18:56
we can do things like if break, which says that if we have space, we're gonna go ahead and represent this in the modifier form. Similarly, we can do this, we can turn things into turneries, though some people might not like that. We can do interesting things here. If a heredoc would fit the declaration only of the heredoc, not the rest of the content, we can pop it in there and allow the rest of it to flow outward. This is actually an interesting representation
19:20
of how this works because this has to be used in the same way that comments are used, which is the content of the heredoc only gets flushed when you hit a new line, kind of an interesting piece of Ruby syntax. So finally, we maintain these comments 'cause the comments get attached to the nodes. If we move this inward, we can actually flip brace blocks into do blocks, and it works like that. The return node knew that its content was gonna get broken, so it added parenthesis just to be nice.
19:48
This is part of the core of syntax tree and you'll see that every node defines its own format method. You can see just in this content, Q is the method that represents the prettyprinter object, the formatter, and you see if break, format break, if flat, format like this. So you can start to read and see how these things are gonna build up this tree, inspect the tree and then print it out. So that is the formatting. We're gonna make it, we're gonna make it.
20:14
I decided to create a CLI to interact with this. And there's a couple of interesting things in here. These are all the options, I'm not gonna go through all of them, I'm gonna going through five. These are the most interesting ones to me. The first one is the AST method. The AST method gives you the AST, it gives you a tree representation of what you're looking at. This can be useful as I discovered when one of my coworkers was wondering how def foo
20:36
with a required parameter of A equals B equals one worked. And it turns out that that's just an expression and it's missing parenthesis. So you can kind of go and use this to inspect your source and learn more about how Ruby is structured. The next one is format. Format does what you expect, it formats.
20:53
The next one is match, I really, really, really love this one. This is my favorite thing, this is my favorite part of this talk, so pay attention. Match is a really interesting thing. It takes this source and it gives you a Ruby expression that you can put into a pattern match that would exactly match the source you gave it.
21:10
I'm gonna say that one more time. This expression can go into an in clause, and if you gave it the node that was represented by that source, it would give you an exact match. Okay, we're gonna come back to that. The next one is search. Search allows you to take a pattern match like this, hey, I'm searching for int, I'm gonna find every int in the file that you gave me. If I'm searching for hey, an int with a value of two, I'm gonna find you every int with a value of two.
21:38
You'll notice I'm using pattern matching syntax because I can pipe the result of match back in and it will find exactly the source. So we can use the match command to get the expression that we wanna find and then we can go and search with. Interestingly enough, the way that this works internally is it uses syntax tree to parse the pattern matching and then builds a proc that will match against the nodes,
22:02
(indistinct). Anyway, last piece of this, language server. Language servers came out with Microsoft when they created VS Code. They wanted to create an ability for your IDE to interact with a language or a process in a language-independent way.
22:21
A way to interact with it without having to worry about the individual details of that language. So language server protocol was developed, it runs a JSON RPC server behind an editor, thousands of unbatched RPC calls.
22:34
It provides many different kinds of procedures. The three I care about or didChange, didOpen, and didClose, or at least at the beginning. This provides you the information of when the text document is edited, then text document formatting, this is the one I provide in my language server. I also provide inlayHint, which is kind of an interesting side piece of this that I won't talk about too much. This is an example of how it works. Doesn't matter, just write your code in line,
22:57
hit save, does what you want.
23:01
So I wanna talk about Shopify Ruby LSP real quick. I work at Shopify, I'm not a shill but a little bit. They're developing a project on top of syntax tree, which is very fascinating, provides way more than just the four or five LSP procedures that I provide, provides really interesting things like document highlighting, which you can tell what kind of nodes
23:22
are inside the tree based on the highlighting of the node, document symbols, so you can jump straight to a method definition. Folding ranges to fold on the left side of your editor, formatting through RuboCop or through syntax tree, selection ranges, semantic highlighting, all kinds of things, you should be checking out this project. So finally, okay, we're gonna make it, we're gonna make it guys. The last piece of this is translating the syntax tree. What does translating the syntax tree mean?
23:49
Over time, there have been many efforts to build a new Ruby parser and there are many different syntax trees in production today. There is the Ruby parser parser, which is used to build flog and flay and many other projects from Seattle.rb. So we have a ruby parser visitor that translates our syntax tree into the ruby parser syntax tree. Funny enough, you can run syntax tree to parse your file, then run this visitor, then run all the static analysis tools that run on the Ruby parser parser.
24:22
It's just a tree at the end of the day. Same thing for the whitequark parser which powers RuboCop. You can go and run the visitor over the syntax tree. Now, the interesting thing about this is Ruby, the syntax tree parser can be swapped out from under it and it still doesn't matter. And I can still power RuboCop with a completely different parser if I wanted to, provided that the syntax tree nodes were in place and then translated into the right source.
24:47
Finally, YARV, I added this a couple weeks ago, and by that I mean a couple hours ago.
24:54
You can go now and provide the YARV visitor, which will compile syntax tree nodes down into the Ruby VM instruction sequence objects that are used to represent the bytecode instructions that C Ruby will use to execute that syntax tree.
25:13
A little bit wild. There's a secret CAPI I just learned about from Aaron, that you can actually pull these back into executable code. So in theory, we could parse source, mutate the tree however we wanted, convert them into YARV and then execute them, maybe like a Ruby Next, like Ruby Next does, right? To provide polyfilling or different syntax. If you're running 2.7 and we want to use pattern matching, we can visit the tree, mutate it to be Ruby 2.7 syntax,
25:47
change it into executable code and run it.
25:50
Finally, we can turn it back into Ruby, right? We can use the formatter, but we can also mutate it. There's a mutation visitor baked into syntax tree. What this does is it uses all of the concepts I just showed you and we call mutate with a query. The query uses pattern matching syntax with anything that you wanna use, and then we can call the copy method. If we mutate the node in place within that mutation method, we actually get a new tree back
26:14
when we parse it the visitor, and that is auto formatting. That is auto correction, that is a linter. There is a branch of syntax tree that implements seven different RuboCop rules using this format, and you can start to do some really interesting things.
26:33
Yeah, so what is syntax three? There are a couple core concepts, there's the parser, there's what is a syntax three itself? What is a visitor? The visitor is kind of key to translating the syntax tree into all these different formats. Finally, well, we talked about, we built the syntax tree, how it's built with Ripper, we formatted the syntax tree, we created a CLI to interact with this process. We created a language server and we can translate the syntax tree into married representations.
26:56
Thank you very much. (audience clapping)
27:05
Okay, we made it through. Does anyone have any questions that I can answer? The question was, do I intend to provide like a syntax re-writer? Yes. Yeah, you can do that today. I wanna provide more niceties to it. But yeah, the overall idea is to provide a CLI where you can run code mod, you can ship something where, for instance, if Rails were to provide a deprecation, you could ship a file that runs on the Rails CLI that would just automatically update your Rails code depending on the methods
27:36
that you wanted to get called. Yeah, it's a good question. The question was how does this relate to Pretty Ruby? Pretty Ruby was a project that I started in 2016 that was a plugin for the prettier MPM package, which formats languages, and they provide a plugin interface. So previously, I built a Ruby formatter entirely in JavaScript.
27:57
In recent versions of Prettier Ruby, you will notice that it is two files, the first file, swans Ruby process and the second file formats using syntax tree. So Prettier Ruby has gone from several tens of thousands of lines of code to a couple hundred. And yeah, Prettier Ruby is now a bad wrapper around syntax tree, don't use it.
28:20
Yeah, question, it's a great question. The question was, are we stuck with Ripper being the parser for syntax tree? No, the answer is no, we are not. In fact, there is a project going on at Shopify to rewrite the Ruby parser and I'm doing that. And the goal is to replace the parser.
28:40
The Ripper parser is being used to generate the syntax tree nodes with this new parser, which should be much more efficient, air tolerant, portable maintainable. And the goal is that if you're using syntax tree to build whatever tools you're gonna build on top of it, the change should be transparent to you. You should not be impacted by it. You should just be able to keep using syntax tree and you will immediately reap the benefits of the new parser without having to change any of your code,
29:05
which is not true if you're using something like the parser gem.
29:10
Any other questions?
29:12
All right, if you wanna talk to me about syntax tree or parsing or any of the weird things I just showed you today, come find me. Otherwise, thank you very much and thanks for coming. (audience clapping)
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat