Of all the front-end compilation tools you’ve ever used, AST traversal is one of them

As a front end, we use many compilation tools: typescript Compiler, Babel, ESLint, PostCSS, etc. The AST is not the same, but there is only one traversal method for AST.

AST traversal idea

The compiler converts the source code into an AST, thereby turning operations on strings into operations on the AST object tree.

Since you want to manipulate the AST, you need to find the corresponding AST, which requires traversal.

How do I traverse it?

An AST is a tree, and a tree traverses depth-first and breadth-first, and this is depth-first.

So how do we iterate over each AST?

For example, the BinaryExpression a + b traverses the left and right attributes

For example, if (a === 1) {} the IfStatement must iterate through the test and consequece attributes:

Thus, we record how each AST traverses, and then recursively iterate from the root.

Like this:

Because each AST accesses those keys, it’s called visitorKeys.

As you traverse each AST, look in visitorKeys to see which properties to traverse, and then pull them out to traverse recursively.

This is the AST traversal, and there is only one. (Can you think of a second one?)

Of course, there is only one way of thinking, but there are some variations:

For example, if the AST is too deep, the recursion level is too deep and the stack may overflow, so you can add an array (as a stack) to record the next step through the AST, and then you can turn it into a loop. React Fiber also loops recursions.

For example, instead of raising the visitorKeys, you can simply write them in code. This is not as easy to extend as raising them, but it is still convenient to make some logical changes to parts of the AST.

For those who aren’t convinced, let’s take a look at the source code for how Babel, ESLint, TSC, estraverse, and PostCSS traverse AST.

Implementation of AST traversal for various compilation tools

There are a lot of irrelevant information in the source code, we focus on the traversal part of the good:

eslint

Eslint traversals are fairly standard, so let’s look at this first:

For each AST, get the iterated keys from visitorKeys, recursively iterate over each key, and for arrays, iterate over each element.

That’s exactly what we’ve been working on up here.

Furthermore, the Enter callback can be called before traversal and the exit callback can be called after traversal.

babel

Babel uses visitorKeys to keep track of how each AST is traversed, and then retrievals the keys as it traverses:

Babel has two methods that are essentially indistinguishable and also has callbacks for the Enter and exit phases.

estraverse

Estraverse is a library dedicated to traversing AST that works well with Esprima’s Parser. Its AST traversal is different from the above two, except that it turns recursion into a loop.

See where I marked it, it’s the same thing as above, except instead of recursing, you put the AST that you want to iterate over into an array, and then you continue the loop.

The idea of a recursive loop is to add an array (as a stack) to the path.

typescript

Typescript traversals are also different. Instead of pulling out the visitorKeys data, the typescript traversals are written in the code to access the attributes of the AST:

This method is more imperative, to enumerate all AST once, and the above way to pull out the visitorKeys is declarative idea, logic can be reused. I don’t know why TS writes traversal logic this way, but maybe the advantage is that you can modify some traversal logic.

postcss

Postcss is also slightly different in that all keys are traversable, so you don’t need visitorKeys.

And PostCSS nodes have methods that organize traversal in an object-oriented way.

There’s a little bit of a difference, but the idea of traversal is the same.

conclusion

There are a number of compilation tools available in the front-end domain, all of which are based on the AST, and to manipulate the AST requires searching through history.

Compilation tools such as ESLint, Babel, Estraverse, PostCSS, and typescript Compiler have all been used for traversal AST implementations, and while some are recursive, some are looped, some are object-oriented, some are functional, Either you pull out the visitorKeys, or you die in code, but the idea is the same.

So, let’s formally conclude that there is only one way to implement traversal for compilation tools, which is to find the traversable keys for each AST, depth-first traversal.