[[427650]]

本文轉載自微信公眾號「神光的編程秘籍」，作者神說要有光 。轉載本文請聯系神光的編程秘籍公眾號。

作為前端，我們會用很多編譯工具：typescript compiler、babel、eslint、postcss 等等，它們的 AST 不盡相同，但 AST 的遍歷算法有且只有一種，不信我們慢慢來理一下。

AST 的遍歷思路

編譯工具會把源碼轉成 AST，從而把對字符串的操作轉為對 AST 對象樹的操作。

既然要操作 AST，那就要找到對應的 AST，這就需要遍歷。

怎么遍歷呢?

AST 不就是樹嘛，而樹的遍歷就深度優先和廣度優先兩種，而這里只能是深度優先。

那對于每個 AST 怎么遍歷呢?

比如 a + b 這個 BinaryExpression，需要遍歷 left、right 屬性

比如 if (a === 1) {} 這個 IfStatement，需要遍歷 test、consequece 屬性：

這樣，我們記錄下每種 AST 怎么遍歷，然后從根結點開始遞歸的遍歷就可以了。

比如像這樣：

因為是每種 AST 訪問那些 key，所以叫做 visitorKeys。

遍歷每種 AST 的時候，就從 visitorKeys 里面找，看看要遍歷哪些屬性，之后取出來遞歸遍歷就行了。

這就是 AST 的遍歷過程，有且只有這么一種。(你還能想出第二種么?)

當然，思路雖然只有一種，但還是有一些變形的：

比如把遞歸變成循環，因為 AST 如果過深，那遞歸層次就過深，可能棧溢出，所以可以加一個數組(作為棧)來記錄接下來要遍歷 AST，這樣就可以變成循環了。(react fiber 也是把遞歸變循環)

比如可以不把 visitorKeys 提出來，而是直接在代碼里寫死，這樣雖然不如提出來更容易擴展，但是做一些針對部分 AST 的邏輯變更還是比較方便的。

說了這么多，但是你可能不信，那我們就上源碼來看下 babel、eslint、tsc、estraverse、postcss 都是怎么遍歷 AST 的。

各種編譯工具的 AST 遍歷的實現

源碼里面有很多無關的信息，我們重點看遍歷的部分就好了：

eslint

eslint 的 遍歷過程比較標準，我們先來看下這個：

就是對每種 AST 都從 visitorKeys 中拿到遍歷的屬性 keys，然后遞歸遍歷每個 key 的值就行了，數組的話還要循環遍歷每個元素。

和我們上面理清的思路一毛一樣。

而且，在遍歷之前可以調用 enter 回調函數，在遍歷之后可以調用 exit 回調函數。

babel

babel 也是一樣的思路，通過 visitorKeys 記錄每種 AST 怎么遍歷，然后遍歷的時候取出對應的 keys 來遞歸訪問：

babel 分為了兩個方法，沒啥實質區別，而且也有 enter 和 exit 兩個階段的回調。

estraverse

estraverse 是專門用于遍歷 AST 的庫，一般和 esprima 的 parser 配合。它的 AST 遍歷和上面兩個不太一樣，就是把遞歸變成了循環。

看到我標出來的地方了么，和上面的是一樣的，只不過這里不是遞歸了，而是把要遍歷的 AST 放入數組，之后繼續循環。

遞歸改循環的思路都是這樣，加個數組(作為棧)記錄路徑就可以了。

typescript

typescript 的遍歷和上面的也不太一樣，它沒有抽離出 visitorKeys 的數據，而是寫死在代碼里對什么 AST 訪問什么屬性：

這種方式比較命令式，要把所有 AST 枚舉一遍，而上面那種把 visitorKeys 抽離出來的方式是聲明式的思想，邏輯可以復用。不知道為什么 ts 是這樣寫遍歷邏輯的，可能好處就是可以對某一些遍歷邏輯做修改吧。

postcss

postcss 也稍微有點不同，它的所有 key 都是可遍歷的，也就不需要 visitorKeys ，直接遍歷所有的 key 就行。

而且 postcss 的 node 是有方法的，通過面向對象的方式來組織遍歷的過程。

寫法上有點區別，但遍歷的思路沒有變。

總結

前端領域的編譯工具有挺多的，它們都是基于 AST，而操作 AST 就需要遍歷來查找。

eslint、babel、estraverse、postcss、typescript compiler 這些編譯工具的遍歷 AST 的實現我們都過了一遍，雖然有的用遞歸、有的用循環，有的是面向對象、有的是函數，有的是抽離 visitorKeys、有的是寫死在代碼里，但思路都是一樣的。

所以，我們來正式的下個結論：編譯工具的遍歷實現思路只有一種，就是找到每種 AST 的可遍歷的 keys，深度優先的遍歷。