高德JS依賴分析工程及關鍵原理-有解無憂

一、背景

高德 App 進行 Bundle 化后，由于業務的復雜性，Bundle 的數量非常多，而這帶來了一個新的問題——Bundle 之間的依賴關系錯綜復雜，需要進行管控，使 Bundle 之間的依賴保持在架構設計之下，

并且，為了保證 Bundle 能實作獨立運轉，在業務持續迭代的程序中，需要逆向的依賴關系來迅速確定迭代的影響范圍，同時，對于切面 API（即對容器提供的系統 API，類似瀏覽器中的 BOM API），也需要確定每個切面 API 的影響范圍以及使用趨勢，來作為修改或下線某個 API 的依據，

以組件庫為例，由于組件會被若干業務專案所使用，我們對組件的修改會影響這些業務專案，在計劃修改前，需要根據正向的依賴關系（業務依賴組件）來算出逆向的依賴關系——該組件被哪些地方所依賴，從而確定這個組件修改的影響范圍，

比檔案更高的維度，是 Bundle 間的依賴，我們有業務 Bundle，也有公共 Bundle，公共 Bundle 也分為不同層級的 Bundle，

對于公用 Bundle，業務 Bundle 可以依賴它，但公用 Bundle 不能反過來依賴業務 Bundle；同樣的，底層的 Bundle 也禁止依賴上層封裝的 Bundle，我們需要通過依賴分析，來確保這些依賴按照上述規則進行設計，

二、實作關鍵步驟

實作 JS 依賴分析，整個實作程序大致如下圖所示：

下面挑一些關鍵步驟來展開介紹，

使用 AST 提取依賴路徑

要做檔案級別的依賴分析，就需要提取每個檔案中的依賴路徑，提取依賴路徑有 2 個方法：

使用正則運算式，優點是方便實作，缺點是難以剔除注釋，靈活度也受限；
先進行詞法分析和語法分析，得到 AST（抽象語法樹）后，遍歷每個語法樹節點，此方案的優點是分析精確，缺點是實作起來要比純正則麻煩，如果對應語言沒有提供 parser API（如 Less），那就不好實作，

一般為了保證準確性，能用第 2 個方案的都會用第 2 個方案，

以類 JS（.js、.jsx、.ts、.tsx）檔案為例，我們可以通過 TypeScript 提供的 API ts.createSourceFile 來對類 JS 檔案進行詞法分析和語法分析，得到 AST：

const ast = ts.createSourceFile(
  abPath,
  content,
  ts.ScriptTarget.Latest,
  false,
  SCRIPT_KIND[path.extname(abPath)]
);

得到 AST 后，就可以開始遍歷 AST 找到所有我們需要的依賴路徑了，遍歷時，可以通過使用 typeScript 模塊提供的 ts.forEachChild 來遍歷一個語法樹節點的所有子節點，從而實作一個遍歷函式 walk：

function walk (node: ts.Node) {
  ts.forEachChild(node, walk); // 深度優先遍歷

  // 根據不同型別的語法樹節點，進行不同的處理
  // 目的是找到 import、require 和 require.resolve 中的路徑
  // 上面 3 種寫法分為兩類——import 宣告和函式呼叫運算式
  // 其中函式呼叫運算式又分為直接呼叫（require）和屬性呼叫（require.resolve）
  switch (node.kind) {
    // import 宣告處理
    case ts.SyntaxKind.ImportDeclaration:
      // 省略細節……
      break;

    // 函式呼叫運算式處理
    case ts.SyntaxKind.CallExpression:
      // 省略細節
      break;
  }
}

通過這種方式，我們就可以精確地找到類 JS 檔案中所有直接參考的依賴檔案了，

當然了，在 case 具體實作中，除了用戶顯式地寫依賴路徑的情況，用戶還有可能通過變數的方式動態地進行依賴加載，這種情況就需要進行基于背景關系的語意分析，使得一些常量可以替換成字串，

但并不是所有的動態依賴都有辦法提取到，比如如果這個動態依賴路徑是 Ajax 回傳的，那就沒有辦法了，不過無需過度考慮這些情況，直接寫字串字面量的方式已經能滿足絕大多數場景了，之后計劃通過流程管控+編譯器檢驗對這類寫法進行限制，同時在運行時進行收集報警，要求必需顯式參考，以 100% 確保對切面 API 的參考是可以被靜態分析的，

建立檔案地圖進行尋路

我們對于依賴路徑的寫法，有一套自己的規則：

參考類 JS 檔案支持不寫擴展名；

參考本 Bundle 檔案，可直接只寫檔案名；

使用相對路徑；

參考公用 Bundle 檔案，通過 @${bundleName}/${fileName} 的方式參考，fileName 同樣是直接只寫該 Bundle 內的檔案名，

這些方式要比 CommonJS 或 ECMAScript Module 的規劃要稍復雜一些，尤其是「直接只寫檔案名」這個規則，對于我們來說，需要找到這個檔案對應的真實路徑，才能繼續進行依賴分析，

要實作這個，做法是先構建一個檔案地圖，其資料結構為 { [fileName]: ‘relative/path/to/file’ } ，我使用了 glob 來得到整個 Bundle 目錄下的所有檔案樹節點，篩選出所有檔案節點，將檔案名作為 key，相對于 Bundle 根目錄的路徑作為 value，生成檔案地圖，在使用時，「直接只寫檔案名」的情況就可以直接根據檔案名以 O(1) 的時間復雜度找到對應的相對路徑，

此外，對于「參考類 JS 檔案支持不寫擴展名」這個規則，需要遍歷每個可能的擴展名，對路徑進行補充后查找對應路徑，復雜度會高一些，

依賴是圖的關系，需先建節點后建關系

在最開始實作依賴關系時，由于作為前端的慣性思維，會認為「一個檔案依賴另一些檔案」是一個樹的關系，在資料結構上就會自然地使用類似檔案樹中 children: Node[] 的方式——鏈式樹結構，而實際上，依賴是會出現這種情況的：

如果使用樹的方式來維護，那么 utils.js 節點就會分別出現在 page.jsx 和 comp.jsx 的 children 中，出現冗余資料，在實際專案中這種情況會非常多，

但如果僅僅是體積的問題，可能還沒那么嚴重，頂多費點空間成本，但我們又會發現，檔案依賴還會出現這種回圈依賴情況：

寫 TypeScript 時在進行型別宣告的時候，就經常會有這樣回圈依賴的情況，甚至兩個檔案之間也會回圈依賴，這是合理的寫法，

但是，這種寫法對于直接使用鏈式樹結構來說，如果創建鏈式樹的演算法是「在創建節點時，先創建子節點，待子節點創建回傳后再完成自身的創建」的話，就不可能實作了，因為我們會發現，假如這樣寫就會出現無限依賴：

const fooTs = new Node({
  name: 'foo.ts',
  children: [
    new Node({ 
      name: 'bar.ts', 
      children: [
        new Node({
          name: 'baz.ts',
          children: [
            new Node({
              name: 'foo.ts', // 和最頂的 foo.ts 是同一個
              children: [...] // 無限回圈……
            })
          ]
        })
      ]
    })
  ]
})

此問題的根本原因是，這個關系是圖的關系，而不是樹的關系，所以在創建這個資料結構時，不能使用「在創建節點時，先創建子節點，待子節點創建回傳后再完成自身的創建」演算法，必須把思路切換回圖的思路——先創建節點，再創建關系，

采用這種做法后，就相當于使用的是圖的鄰接鏈表結構了，我們來看看換成「先創建節點，再創建關系」后的寫法：

// 先創建各節點，并且將 children 置為空陣列
const fooTs = new Node({
  name: 'foo.ts',
  children: []
});

const barTs = new Node({
  name: 'bar.ts',
  children: []
});

const bazTs = new Node({
  name: 'baz.ts',
  children: []
});


// 然后再創建關系
fooTs.children.push(barTs);
barTs.children.push(bazTs);
bazTs.children.push(fooTs);

使用這種寫法，就可以完成圖的創建了，

但是，這種資料結構只能存在于記憶體當中，無法進行序列化，因為它是回圈參考的，而無法進行序列化就意味著無法進行儲存或傳輸，只能在自己行程里玩這樣子，這顯然是不行的，

所以還需要對資料結構進行改造，將鄰接鏈表中的參考換成子指標表，也就是為每個節點添加一個索引，在 children 里使用索引來進行對應：

const graph = {
  nodes: [
    { id: 0, name: 'foo.ts', children: [1] },
    { id: 1, name: 'bar.ts', children: [2] },
    { id: 2, name: 'baz.ts', children: [0] }
  ]
}

這里會有同學問：為什么我們不直接用 nodes 的下標，而要再添加一個跟下標數字一樣的 id 欄位？原因很簡單，因為下標是依賴陣列本身的順序的，如果一旦打亂了這個順序——比如使用 filter 過濾出一部分節點出來，那這些下標就會發生變化，而添加一個 id 欄位看起來有點冗余，但卻為后面的演算法降低了很多復雜度，更加具備可擴展性，

用堆疊來解決回圈參考（有環有向圖）的問題

當我們需要使用上面生成的這個依賴關系資料時，如果需要進行 DFS（深度遍歷）或 BFS（廣度遍歷）演算法進行遍歷，就會發現由于這個依賴關系是回圈依賴的，所以這些遞回遍歷演算法是會死回圈的，要解決這個問題很簡單，有三個辦法：