摘要：多個異步任務(wù)的順序執(zhí)行通過方法，取得了一個描述加載順序的二維數(shù)組。同時，二維數(shù)組的長度也是不定的，更不能窮舉。利用這個特性，只需要遍歷原二維數(shù)組，將每個放在一個中的函數(shù)中執(zhí)行并返回即可因為的返回值就是一個，有一種惰性執(zhí)行的感覺。

bowl 是一個利用 local storage 進行靜態(tài)資源緩存和加載的工具庫，在開發(fā)過程中遇到過一些問題，其中比較典型的是加載多個資源的時候資源之間可能出現(xiàn)相互依賴的情況，假設(shè)有一個基于 Angular 的應(yīng)用，開發(fā)者在構(gòu)建工具，如 webpack，中構(gòu)建出了兩個 JS 文件，一個文件包含了項目所有的依賴模塊，比如 Angular, jQuery, lodash 等等，名為 vendor.js，另一個 JS 文件則全部是業(yè)務(wù)相關(guān)的代碼，名為 app.js。顯然，app.js 的加載依賴 vendor.js 的先行加載。如果先加載并執(zhí)行 app.js 的話，會由于全局環(huán)境中還不存在 Angualr 和 jQuery 這些庫或框架而報錯。

問題描述完了，這種問題實際上也是很常見的問題，但在 bowl 的場景下，需要結(jié)合 bowl 的實現(xiàn)原理來進行分析。

在 bowl 的內(nèi)部，需要加載的資源分為幾種類型，一種是存在于和頁面同域下的資源且用戶需要緩存的，它會使用 XMLHttpRequest 發(fā)起請求的方式獲取資源內(nèi)容，另一種純第三方資源，比如在頁面中直接引用第三方 CDN 域名上的資源，如 jQuery 等都提供了 CDN 的資源鏡像，它屬于跨域資源，無法用 XMLHttpRequest 的方式獲取，那么只能退一步使用常規(guī)的 HTML 標(biāo)簽的方式請求數(shù)據(jù)。另外這里用 promise 包裝了標(biāo)簽加載的代碼，在 onload 事件中進行 resolve 操作，將同步的加載過程用異步的方式呈現(xiàn)，目的是和異步請求資源內(nèi)容的方式保持一致，保證流程可控。第三種和第一種相似，不同點在于用戶聲明不需要緩存，這種類型也使用了和第二種相同的加載方式。

對于資源間依賴關(guān)系的聲明，首先進行的是 API 的設(shè)計，這里采用了比較簡單的方式：

bowl.add[{
  key: "vendor",
  url: "vendor.js"
}, {
  key: "app",
  url: "app.js",
  dependencies: ["vendor"]
}]

如果 a 資源依賴 b 資源，那么在 a 資源的 dependencies 屬性中寫入一個數(shù)組，里面包含依賴資源的 key 名即可。

bowl 中執(zhí)行資源請求并注入的方法是 inject()，那么在調(diào)用這個方法的時候首先要做的就是分析資源的依賴關(guān)系，一開始我沒有什么特別好的想法，為了鍛煉一下自己的思維能力也沒有谷歌什么現(xiàn)成的解決方案，就在紙上隨手寫寫畫畫：

不行，太抽象了，換一種方式：

看起來有點眼熟，原來是典型的有向圖數(shù)據(jù)結(jié)構(gòu)，想到這個就有思路了（旁邊是歸類的依賴類型，這個稍后說）。

有向圖是圖數(shù)據(jù)結(jié)構(gòu)的一種，在圖中，分為兩種數(shù)據(jù)單元，一種是頂點，另一種是邊。其中邊又分為兩種類型，無向的和有向的，只包含無向邊的叫無向圖，包含有向邊的就叫有向圖了。在當(dāng)前的場景中，資源之間的依賴是單向的，a 依賴 b 但不代表 b 依賴 a，因此有向圖是合適的數(shù)據(jù)結(jié)構(gòu)。

在這里的有向圖中，每個資源對應(yīng)有向圖中的頂點，資源間的依賴關(guān)系則是兩個頂點之間的邊了。如果 a 依賴 b，那么在 a 和 b 之間就有一條由 b 指向 a 的邊。

在 JS 中實現(xiàn)一個簡單的有向圖數(shù)據(jù)結(jié)構(gòu)還是挺簡單的：

function Graph() {
  this.vertices = {}
}

用一個對象包含所有的頂點，資源的 key 作為這個頂點的鍵值，每個頂點還需要有各自的屬性：

name: 頂點的名字，對應(yīng)資源名稱

prev: 頂點的入度，這里表示該資源依賴其他資源的數(shù)量

next: 頂點的出度，這里表示該資源被多少其他資源依賴

adjList: 以該頂點為起點的邊指向的頂點列表，這里就是依賴本資源的其他資源名稱列表

有了這個就可以實現(xiàn) addVertex 和 addEdge 方法了：

Graph.prototype.addVertex = function(v) {
  // 檢測頂點是否已存在
  if (isObject(this.vertices[v])) {
    return
  }
  var newVertex = {
    name: v,
    prev: 0,
    next: 0,
    adjList: []
  }
  this.vertices[v] = newVertex
}

Graph.prototype.addEdge = function(begin, end) {
  // 檢查兩個頂點是否存在
  if (!this.vertices[begin] ||
      !this.vertices[end] ||
       this.vertices[begin].adjList.indexOf(end) > -1) {
    return
  }
  ++this.vertices[begin].next
  this.vertices[begin].adjList.push(end)
  ++this.vertices[end].prev
}

有了這兩個方法，在調(diào)用 bowl.inject 的時候可以根據(jù)已添加的資源生成一個描述資源依賴關(guān)系的圖數(shù)據(jù)結(jié)構(gòu)了，舉例如下：

Graph {
  vertices: {
    a: {
      name: "a",
      next: 0,
      prev: 1,
      adjList: []
    },
    b: {
      name: "b",
      next: 1,
      prev: 0,
      adjList: ["c"]
    },
    c: {
      name: "c",
      next: 1,
      prev: 1,
      adjList: ["a"]
    }
  }
}

環(huán)在有向圖中表示有向邊構(gòu)成的環(huán)路，兩個頂點之間存在互相指向?qū)Ψ降倪叺那闆r也稱為環(huán)。在 bowl 中如果出現(xiàn)了環(huán)，就表示資源之前出現(xiàn)了循環(huán)依賴或相互依賴的情況。而這種情況是不應(yīng)該出現(xiàn)的，如果出現(xiàn)了需要報錯。因此，我們首先要做的是分析圖中是否存在環(huán)。

對于環(huán)的檢測，常用的算法是深度優(yōu)先遍歷，例如在 Angular 中注入器檢測循環(huán)依賴用的就是這個算法。

實際上，在 bowl 中我使用了另一種名為 Kahn 算法的環(huán)檢測的算法，它是拓?fù)渑判蛩惴ǖ囊环N，相比于深度優(yōu)先遍歷算法來說它比較直觀。它的原理歸納起來有三點：

遍歷圖中所有的頂點，將所有入度為 0 的頂點依次入棧

如果棧非空，則從棧頂取出頂點，刪除該頂點以及以該頂點為起點的邊，如果刪除的邊的另一個頂點入度為 0 了，則把它入棧

最后，如果圖中還存在頂點，則表示圖中有環(huán)

這個算法結(jié)合業(yè)務(wù)場景會很好理解，入度為 0 的頂點表示其對應(yīng)的資源沒有任何依賴，將頂點和邊刪除后剩下的入度為 0 的頂點表示只依賴前一個資源的資源，前一個資源加載后，當(dāng)前資源就可以加載了，以此類推。最后如果還有頂點被剩下的話，說明可順序加載的資源都加載完了還有無法加載的資源，這些資源之間一定存在循環(huán)依賴的關(guān)系。

Kahn 算法寫成代碼如下：

Graph.prototype.hasCycle = function() {
  const cycleTestStack = []
  const vertices = merge({}, this.vertices) // 復(fù)制一份數(shù)據(jù)進行操作
  let popVertex = null

  for (let k in vertices) {
    if (vertices[k].prev === 0) { // 入度為 0 的資源入棧
      cycleTestStack.push(vertices[k])
    }
  }
  while (cycleTestStack.length > 0) {
    popVertex = cycleTestStack.pop()
    delete vertices[popVertex.name]
    popVertex.adjList.forEach(nextVertex => {
      --vertices[nextVertex].prev
      if (vertices[nextVertex].prev === 0) {
        cycleTestStack.push(vertices[nextVertex])
      }
    })
  }
  return Object.keys(vertices).length > 0
}

如果圖能夠通過環(huán)檢測，說明其中的資源不存在循環(huán)依賴關(guān)系，下一步就是要計算資源的加載順序了。很明顯，這里要做的是圖的遍歷，上面提到的深度遍歷也是可以用的，但是這是否是最好的方式呢？

我認(rèn)為不是的，假設(shè)有依賴關(guān)系的資源如下：

a<---b<---c<---d
     ^
     |
     -----e<---f

如果用深度遍歷來進行資源加載的話，加載順序?qū)?a->b->c->d->e->f，每個資源順序加載。而這里 bowl 加載資源的行為都是被包裝在 promise 中的，請求也可以并發(fā)出去，并發(fā)的多個請求只要通過 Promise.all 取到 resolve 的時間點就可以保證全部加載完成了，所以，較為理想的加載順序應(yīng)該是 a->b->[c, e]->[d, f]。

要得到這樣的結(jié)果，實際上可以直接利用 Kahn 算法的思想，每次遍歷過濾出一批沒有依賴未加載的資源，最后得到一個分批次的加載順序。

要得到上面提到的分批加載順序，可以通過以下代碼：

Graph.prototype.getGroup = function() {
  if (this.hasCycle()) { // 有環(huán)則報錯
    throw new Error("There are cycles in resource"s dependency relation")
    return
  }
  const result = []
  const graphCopy = new Graph(this.vertices)
  while (Object.keys(graphCopy.vertices).length) {
    const noPrevVertices = []
    for (let k in graphCopy.vertices) {
      if (graphCopy.vertices[k].prev === 0) {
        noPrevVertices.push(k)
      }
    }
    if (noPrevVertices.length) {
      result.push(noPrevVertices)
      noPrevVertices.forEach(vertex => {
        graphCopy.vertices[vertex].adjList.forEach(next => {
          --graphCopy.vertices[next].prev
        })
        delete graphCopy.vertices[vertex]
      })
    }
  }
  return result
}

當(dāng)然除了深度優(yōu)先和 Kahn 算法，廣度優(yōu)先也是可用的算法，在這幾種算法中，DFS 和 BFS 的時間復(fù)雜度都是 O(n^2)（這里的代碼中使用的可以看成是一個鄰接矩陣），如果用鄰接鏈表的方式表示圖的話，時間復(fù)雜度將會是 O(n+e)。對于 Kahn 算法，時間復(fù)雜度明顯是 O(n^2)。既然這里用了鄰接矩陣的方式，時間復(fù)雜度都是一樣的，效率上差別不大。而且在前端資源的加載場景下，不會出現(xiàn)那么多的資源要去分析，這點差別是可以忽略的。

通過 getGroup 方法，取得了一個描述加載順序的二維數(shù)組：[["a"], ["b"], ["c", "e"], ["d", "f"]]。下面要做的是加載它們，對于這個數(shù)組中的每個子數(shù)組中的資源，它們都是可以同時加載的，把這塊邏輯抽出來，返回一個 promise 即可：

const batchFetch = (group) => {
  const fetches = []
  group.forEach(item => {
    fetches.push(this.injector.inject(this.ingredients.find(ingredient => ingredient.key === item)))
  })
  return Promise.all(fetches)
}

這段代碼的具體細(xì)節(jié)就省略了，最后通過一個 Promise.all 返回一個包裝后的 promise，group 中的資源全部加載完成后這個 promise 會被 resolve。

這個時候問題就來了，對于這個二維數(shù)組，不能簡單的將每個子數(shù)組都一股腦傳入 batchFetch 方法中，因為傳入 Promise 構(gòu)造函數(shù)中的函數(shù)是會立即執(zhí)行的，而后一個子數(shù)組中的資源必需在前一個 batchFetch promise 被 resolve 后才能加載。同時，二維數(shù)組的長度也是不定的，更不能窮舉。

這里就是一個典型的多個 promise 異步任務(wù)的場景，每個異步任務(wù)的構(gòu)建依賴前一個任務(wù)的完成狀態(tài)。一開始由于我對異步編程不是特別熟悉，有點想不通，在 bluebird 這個 promise 庫中找到了 Promise.reduce 和 Promise.each 這兩個靜態(tài)方法是可以解決問題的，但是對于 bowl 這么一個小型庫來說，引入一個 bluebird 有點殺雞用牛刀的感覺，不太合適。

最終通過查 Promise/A+ 規(guī)范以及一些嘗試，找到了一個解決方案，其實很簡單。對于 promise 中的 then 回調(diào)函數(shù)，它返回的是一個新的 Promise，而每個 then 中的 onFulfill 回調(diào)都會在前一個 Promise resolve 后執(zhí)行。利用這個特性，只需要遍歷原二維數(shù)組，將每個 batchFetch(group) 放在一個 then 中的 onFulfill 函數(shù)中執(zhí)行并返回即可（因為 batchFetch 的返回值就是一個 promise），有一種惰性執(zhí)行的感覺。

let ret = Promise.resolve() // 強行開啟一個 promise 鏈
resolvedIngredients.forEach(group => {
  ret = ret.then(function() {
    return batchFetch(group)
  })
})
return ret

這樣，最終 ret 被 resolve 的時候，說明所有資源都按順序加載完了。

「學(xué)習(xí) JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法」，人民郵電出版社

http://www.cnblogs.com/TenosDoIt/p/3644225.html

http://shmilyaw-hotmail-com.iteye.com/blog/2116275

https://promisesaplus.com/