你用過的所有前端編譯工具， AST 遍歷思路就這一種
作爲前端，我們會用很多編譯工具：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，深度優先的遍歷。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/qj2p89O1hj61dEADJS86sA