Implementing Traverse

[00:00:00]
>> Steve Kinney: So we need two things, we need the ability to traverse the array, or the tree, rather. And then we'll have to implement the ability to actually go ahead and modify it. So let's take care of some of the traversal first. There's not a lot here, this is basically just traveling it.

[00:00:20]
And this will go ahead, and this one does in fact traverse it as well. I'm sorry, transform it, so we'll get to that in a second. But let's write the ability to actually go through the tree. Cuz it's hard to test something that doesn't do anything. We could theoretically implement a counter or mocks and something like that.

[00:00:34]
But I think we can get to that when we get to the point where we can actually write it. So we'll go into traverse which is not giving us a lot. And we do need to diverse in two different ways, right? Cuz we have effectively two data structures in here.

[00:00:49]
We have the tree, this idea like expressions of child nodes, right? And we also have the set of arguments, which is an array. So we need to both be able to traverse up and down the tree as well as across the arguments, right? So we're gonna need to implement both of these.

[00:01:11]
So let's try to implement this. Let's start out with a just general traverse method that will call and then it will kind of figure stuff out. And again, ours will likely need to be expanded as your language expands, but we still have a relatively simple language at this point.

[00:01:26]
As we add more constructs, we might need to do more things. Cool, all right. So what we'll do is we'll start with our traverse method. Now it's got the node and the visitor, right? We know in our language that our tree has a top, right? Our tree has a single place to start, and this is true of most programming languages.

[00:01:49]
Ours was purposely naive for the point of simplicity where it starts with a call expression. If we go back over the AST explorer and we look at the one from Babel,
>> Steve Kinney: Bring that over and we scroll up, you can see they started with a file, but a lot of us started this program which is the exact same concept, exact single point on the tree, right?

[00:02:14]
Cuz we can have a bunch of things at that top level, right? There is a program that has a body which is an array. So not dissimilar from ours, and like eventually we can wrap like we'll have a function where we can wrap it in the same kinda construct.

[00:02:29]
But we just wanted to keep it simple in the very beginning. But it's the same idea that you have basically the ability to go across sibling nodes, or down through child nodes.
>> Steve Kinney: But in both cases we know that there's a parent up at the top. So what we'll do is we'll write a, we'll have two helper functions here.

[00:02:50]
Well, really two that it goes out to, which is traverseNode.
>> Steve Kinney: And I'm gonna use object destructuring cuz I don't need all the arguments all the time when I'm actually writing my visitors. And I don't wanna have to remember the order of them. So with this, as long as I give them the right ones it doesn't necessarily matter.

[00:03:12]
So we'll have traverseNode, and traverseNode will take the node we want the parent. Why is the parent important? The parents important cuz it allows us to traverse back up to the tree, right? We can effectively call node.parent, parent, parent, parent, parent, parent, parent, parent. And get all the way up the tree if we need to, like for instance, add something all the way the top.

[00:03:32]
When would you wanna do this, right? Well, if we were transpiring to Babel, and we have like this large standard library. When we're transferring right now we're gonna make a function called add, it'll make these functions but they don't exist in JavaScript. So we could do is like we came across something in the standard library, we can go ahead and add.

[00:03:51]
Maybe the function definitely decoration to the like top scope or something along those lines, and do it programmatically. So we're not adding the entire standard library, we're only adding exactly what we need. And then we get some file size limitations and stuff along those lines. So we can say node, parent, and then the visitor, right?

[00:04:10]
The visitor is what we talked about. The separation of the ability to traverse this tree with the thing that is doing something, right? And so this will be the thing that is moving across, right? And so we'll start with that. And traverseNode is going to look like, do we have anything?

[00:04:31]
That cares about this kinda node that we're looking at. And so I'll kinda give you some pseudo code for the visitor so it makes a little bit more sense. And so our visitor,
>> Steve Kinney: Might be, it could be a class and it needs to hold onto a lot of state.

[00:04:46]
It all depends what you need to do. A lot of times it will be a just a plain of objects, right? And let's say you had a visitor that, changing variable decorations from, right? You might say like a very simple, it has a method on it called VariableDeclaration, right?

[00:05:15]
And then it might take the actual node and stuff like that.
>> Steve Kinney: And so this is pseudo code, we're gonna get rid of it in a second. But you might do something like, all right,
>> Steve Kinney: If visitor, and this node's type, right? And so if you are on a node that was a VariableDeclaration, right?

[00:05:52]
Yeah, that's a thing, we need to do stuff. But if you are on a, I don't know, expression statement? That's not a thing, and it just moves along, and it keeps going, right? And so the visitor can just say, here are the things I care about, send me through the tree, and I'll figure it out, right?

[00:06:09]
And allows you to do lots of different transformations with the same basic ability, cuz the ASD of your programming language isn't necessarily changing. It's the things that you wanna do depending on the test that you're trying to run, that is the theoretically changing, right? So you'll see sometimes just the variable declaration have still like it's a pattern, right?

[00:06:32]
There's a variation on the theme, it can still the pattern without necessarily being one way or the other, right? But the way that we're gonna write it just gives us a little more flexibility is we're gonna give it another object that will have an enter method, and potentially and/or an exit method, right?

[00:06:52]
Again, our traversal functions don't know anything about this. It's the visitor that will decide if it needs to do anything on entrance or on exit, right? So we'll actually check the, pay for this type of node. Does this visitor have any concerns about what it does when it enters?

[00:07:08]
And does it have any concerns about what it does when it leaves, right? Cools, comment that out for a second so I don't forget about it. So we'll say, let's just say like,
>> Steve Kinney: These are node type, right? So go see, are there any methods either enter or exit on this node?

[00:07:35]
Those will decide whether or not we do something. Regardless of whether or not we decide to do something. We still need to traverse down to the next node, right? It's not like, if do that, right? We're gonna like before we do something on the end, we will try to see if we have an entry method.

[00:07:49]
If you have an entry method we will do stuff, then we will traverse down, and then on the way back up we will call the exit method, right? And so it's deep for search so you go all the way down one branches tree, all the way back up.

[00:08:02]
So we'll have an ability to kind of move, to catch up on the way up and catch up on the way down in the opposite order of course, right? And so we can say something if there are methods at all, right? If there were no methods we don't wanna have a, there is no enter on undefined, I don't need that in my life.

[00:08:22]
If methods && methods.enter, if you wanna add like the ability to have like optional changing your language that'd be great. If there is a method object for that, and there is a method.enter, call it with the node and the parent, right? So now there's visitor, upon visiting something that I cared about would get access to the node and access to the parent on every VariableDeclaration, and that's what it cared about.

[00:08:57]
If it doesn't care about a certain node type, it skips it, and it moves along, right? And if it does care about that node type, then it's able to grab it, and keep humming along that way. So it's like, cool. On the way in, if you care about this node at all, and you're concerned with entering, I will hand you both the node and the parent.

[00:09:16]
Cool, and then if there are methods.
>> Steve Kinney: And methods of exit, then we will go ahead and call the methods.exit,
>> Steve Kinney: On the node with the parent, right? In the middle is, depending on your data structure, put an equal sign here before I forget, is how you'll basically decide, all right?

[00:10:00]
Does this kind of data structure have any way to go kind of across or down, right? Cool, so really we have our data structures are pretty simple at this point which is called expressions have the ability to have children which is an across, right? And then those nodes you can go down with, so we can kind of do, from any given singular node that is a call expression will go across it siblings.

[00:10:35]
And then those siblings we will be effectively at the top of smaller trees. So It'll be relatively simple implementation at this point. What we can do is just say, there's two ways to do this, which is if we know that consistently stuff like our arguments and our programs are all like.

[00:10:55]
We've named everything in our obsession victory syntax tree consistently. Then we're able to just like rely on hey, I know if there's arguments, then I know it's an array, or I know if there's params, I know it's an array. It seems like, hey, does this node have arguments?

[00:11:12]
Then I need to move across them. Params, I need to move across them. Children or a body, then I need to move across them. And if you know that it's always at the top of a tree, then you get to design your own AST, based on the semantics of your language.

[00:11:24]
So I'm gonna take advantage of the fact that I know that node.arguments is gonna be an array. So that's where we're gonna need the second helper, which is traverseArray.
>> Steve Kinney: Naming things is the second hardest thing in computer science. We can give it an array which is maybe the node.arguments, right?

[00:11:56]
Cuz I don't want to reverse array to like care what the array is called. So we're going to call an array inside of traverse array, but like outside of that I don't want to have to know anything. And the parent will be set to be the current node, and then it will get a copy of the visitor, right?

[00:12:13]
So let's think about this again. Start at the top of the tree, check to see it says to know that my visitor cares about I entering? No? Hey, do you have children who are siblings? I wanna move across them, right? I'm going to effectively, eventually iterate over them.

[00:12:34]
I will say that the current node is the parent, and I'll hand you the visitor to see if it'll check you. And it'll keep going until it gets to the very bottom, and then it'll begin to work its way up.
>> Steve Kinney: All right, so cool. We're actually only really gonna really worry about entering at this point.

[00:12:56]
But we'll go through, am I do an exit will say, let's add this traverse array function.
>> Steve Kinney: This should not be very surprising and how it works. Traverse array is gonna take, we already know the arguments whose we saw him above. We implemented it before we had it, which is gonna take some array, a parent node and the visitor, okay?

[00:13:23]
And then it's going to do is iterate over the array, you use either for loop or for each, whichever one makes you happier. This one makes me happier.
>> Steve Kinney: So you move over that, right? And so move across the siblings and start descending down on each one of them.

[00:13:48]
So move them and go.
>> Steve Kinney: And that's, we didn't need to call this traverseNode here. But the ability to just send down a node and across set of siblings, right? And we'll enter and we'll exit is effectively our entire traversal functionality, right? Now obviously, this is assuming that arguments is the only kind of siblings that we're gonna have to deal with, so on and so forth, right?

[00:14:22]
You will need more stuff as time goes on. And there's a lot of ways helpers and stuff along those lines to figure out the common things that you do. But this will effectively work. So when we get a new node, new visitor. We'll say,
>> Steve Kinney: Start at the top,

[00:14:44]
>> Steve Kinney: And start going down.