[[427650]]

本文轉(zhuǎn)載自微信公眾號(hào)「神光的編程秘籍」，作者神說(shuō)要有光 。轉(zhuǎn)載本文請(qǐng)聯(lián)系神光的編程秘籍公眾號(hào)。

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

AST 的遍歷思路

編譯工具會(huì)把源碼轉(zhuǎn)成 AST，從而把對(duì)字符串的操作轉(zhuǎn)為對(duì) AST 對(duì)象樹(shù)的操作。

既然要操作 AST，那就要找到對(duì)應(yīng)的 AST，這就需要遍歷。

怎么遍歷呢?

AST 不就是樹(shù)嘛，而樹(shù)的遍歷就深度優(yōu)先和廣度優(yōu)先兩種，而這里只能是深度優(yōu)先。

那對(duì)于每個(gè) AST 怎么遍歷呢?

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

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

這樣，我們記錄下每種 AST 怎么遍歷，然后從根結(jié)點(diǎn)開(kāi)始遞歸的遍歷就可以了。

比如像這樣：

因?yàn)槭敲糠N AST 訪問(wèn)那些 key，所以叫做 visitorKeys。

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

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

當(dāng)然，思路雖然只有一種，但還是有一些變形的：

比如把遞歸變成循環(huán)，因?yàn)?AST 如果過(guò)深，那遞歸層次就過(guò)深，可能棧溢出，所以可以加一個(gè)數(shù)組(作為棧)來(lái)記錄接下來(lái)要遍歷 AST，這樣就可以變成循環(huán)了。(react fiber 也是把遞歸變循環(huán))

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

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

各種編譯工具的 AST 遍歷的實(shí)現(xiàn)

源碼里面有很多無(wú)關(guān)的信息，我們重點(diǎn)看遍歷的部分就好了：

eslint

eslint 的 遍歷過(guò)程比較標(biāo)準(zhǔn)，我們先來(lái)看下這個(gè)：

就是對(duì)每種 AST 都從 visitorKeys 中拿到遍歷的屬性 keys，然后遞歸遍歷每個(gè) key 的值就行了，數(shù)組的話還要循環(huán)遍歷每個(gè)元素。

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

而且，在遍歷之前可以調(diào)用 enter 回調(diào)函數(shù)，在遍歷之后可以調(diào)用 exit 回調(diào)函數(shù)。

babel

babel 也是一樣的思路，通過(guò) visitorKeys 記錄每種 AST 怎么遍歷，然后遍歷的時(shí)候取出對(duì)應(yīng)的 keys 來(lái)遞歸訪問(wèn)：

babel 分為了兩個(gè)方法，沒(méi)啥實(shí)質(zhì)區(qū)別，而且也有 enter 和 exit 兩個(gè)階段的回調(diào)。

estraverse

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

看到我標(biāo)出來(lái)的地方了么，和上面的是一樣的，只不過(guò)這里不是遞歸了，而是把要遍歷的 AST 放入數(shù)組，之后繼續(xù)循環(huán)。

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

typescript

typescript 的遍歷和上面的也不太一樣，它沒(méi)有抽離出 visitorKeys 的數(shù)據(jù)，而是寫(xiě)死在代碼里對(duì)什么 AST 訪問(wèn)什么屬性：

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

postcss

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

而且 postcss 的 node 是有方法的，通過(guò)面向?qū)ο蟮姆绞絹?lái)組織遍歷的過(guò)程。

寫(xiě)法上有點(diǎn)區(qū)別，但遍歷的思路沒(méi)有變。

總結(jié)

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

eslint、babel、estraverse、postcss、typescript compiler 這些編譯工具的遍歷 AST 的實(shí)現(xiàn)我們都過(guò)了一遍，雖然有的用遞歸、有的用循環(huán)，有的是面向?qū)ο?、有的是函?shù)，有的是抽離 visitorKeys、有的是寫(xiě)死在代碼里，但思路都是一樣的。

所以，我們來(lái)正式的下個(gè)結(jié)論：編譯工具的遍歷實(shí)現(xiàn)思路只有一種，就是找到每種 AST 的可遍歷的 keys，深度優(yōu)先的遍歷。