你用过的所有前端编译工具，AST遍历思路都是这种转载本文请联系神光编程秘籍公众号。作为前端，我们会用到很多编译工具：typescript编译器、babel、eslint、postcss等，它们的AST各不相同，但是AST遍历算法只有一种。如果你不相信我，让我们慢慢来。AST遍历思想编译工具会将源码转化为AST，从而将对字符串的操作转化为对AST对象树的操作。既然我们要操作AST，就需要找到对应的AST，这就需要遍历。如何穿越？AST不就是一棵树吗，树的遍历是深度优先和广度优先的，但是这里只能是深度优先。如何遍历每一个AST？比如a+b的BinaryExpression需要遍历左右属性，比如IfStatementif(a===1){}，需要遍历test和consequece属性：这样我们记录each如何遍历AST，然后从根节点开始递归遍历。例如，像这样：因为每个AST都访问那些键，所以它被称为visitorKeys。遍历每一个AST的时候，从visitorKeys中找，看看要遍历哪些属性，然后取出来递归遍历。这就是AST的遍历过程，只有一个。（你还能想到第二种吗？）当然，虽然只有一种思路，但还是有一些变形：比如把递归变成循环，因为如果AST太深，递归层级会太深，栈可能会溢出，所以可以加一个数组（作为栈）来记录接下来要遍历的AST，这样就可以成为一个循环。（reactfiber也把递归改成循环了）比如可以不提出visitorKeys，直接写在代码里。虽然不像提议的那样容易扩展，但是对一些AST做一些逻辑上的改动还是比较方便的。说了这么多，大家可能不信，下面我们去源码看看babel、eslint、tsc、estraverse、postcss是如何遍历AST的。各种编译工具AST遍历的实现源码中有很多无关信息。重点关注遍历部分：eslinteslint的遍历过程比较标准。我们先来看这个：即对于每一个AST，都是从visitorKeys中获取可遍历的属性键，然后递归遍历每个键的值。对于数组，您需要遍历每个元素。这与我们上面阐明的相同。而且可以在遍历前调用enter回调函数，遍历后调用exit回调函数。Babelbabel也有同样的想法。它使用visitorKeys来记录每个AST是如何遍历的，然后在遍历的时候取出对应的key进行递归访问：babel分为两种方法，没有实质区别，同样有enter和exit回调。estraverseestraverse是一个专门用于遍历AST的库，一般配合esprima的parser使用。它的AST遍历和上面两个不一样，就是把递归变成了循环。你看到我标记的地方了吗？和上面一样，只是不是递归，而是把要遍历的AST放到一个数组中，然后继续循环。把递归改成循环的思路是一样的，只是加一个数组（作为栈）来记录路径。typescripttypescript的遍历和上面的不太一样。它并没有提取visitorKeys的数据，而是在代码中写了通过什么AST访问什么属性：这个方法比较命令式，所有的AST都要枚举一次，而上面提取visitorKeys的方法是声明式的思路，而逻辑可以重用。不知道ts为什么要这样写遍历逻辑。可能优点是可以修改一些遍历逻辑。postcsspostcss也略有不同，它的所有key都是可遍历的，所以不需要visitorKeys，直接遍历所有key即可。而且postcss的节点有方法，以面向对象的方式组织遍历过程。写法有点不同，但是遍历的思路没变。综上所述，前端领域的编译工具相当多，而且都是基于AST的，而AST的运行需要遍历才能找到。我们已经了解了eslint、babel、estraverse、postcss、typescript编译器等编译工具的AST实现。虽然有的使用递归，有的使用循环，有的是面向对象的，有的是函数，有的是从visitorKeys中提取出来的，有的是硬编码在代码中，但是思路是一样的。那么，正式得出结论：编译工具的遍历只有一种实现方式，就是找到每个AST的可遍历key，进行深度优先遍历。
