资源依赖问题在 bowl 中的一种解决方式

摘要：多个异步任务的顺序执行通过方法，取得了一个描述加载顺序的二维数组。同时，二维数组的长度也是不定的，更不能穷举。利用这个特性，只需要遍历原二维数组，将每个放在一个中的函数中执行并返回即可因为的返回值就是一个，有一种惰性执行的感觉。

bowl 是一个利用 local storage 进行静态资源缓存和加载的工具库，在开发过程中遇到过一些问题，其中比较典型的是加载多个资源的时候资源之间可能出现相互依赖的情况，假设有一个基于 Angular 的应用，开发者在构建工具，如 webpack，中构建出了两个 JS 文件，一个文件包含了项目所有的依赖模块，比如 Angular, jQuery, lodash 等等，名为 vendor.js，另一个 JS 文件则全部是业务相关的代码，名为 app.js。显然，app.js 的加载依赖 vendor.js 的先行加载。如果先加载并执行 app.js 的话，会由于全局环境中还不存在 Angualr 和 jQuery 这些库或框架而报错。

问题描述完了，这种问题实际上也是很常见的问题，但在 bowl 的场景下，需要结合 bowl 的实现原理来进行分析。

在 bowl 的内部，需要加载的资源分为几种类型，一种是存在于和页面同域下的资源且用户需要缓存的，它会使用 XMLHttpRequest 发起请求的方式获取资源内容，另一种纯第三方资源，比如在页面中直接引用第三方 CDN 域名上的资源，如 jQuery 等都提供了 CDN 的资源镜像，它属于跨域资源，无法用 XMLHttpRequest 的方式获取，那么只能退一步使用常规的 HTML 标签的方式请求数据。另外这里用 promise 包装了标签加载的代码，在 onload 事件中进行 resolve 操作，将同步的加载过程用异步的方式呈现，目的是和异步请求资源内容的方式保持一致，保证流程可控。第三种和第一种相似，不同点在于用户声明不需要缓存，这种类型也使用了和第二种相同的加载方式。

对于资源间依赖关系的声明，首先进行的是 API 的设计，这里采用了比较简单的方式：

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

如果 a 资源依赖 b 资源，那么在 a 资源的 dependencies 属性中写入一个数组，里面包含依赖资源的 key 名即可。

bowl 中执行资源请求并注入的方法是 inject()，那么在调用这个方法的时候首先要做的就是分析资源的依赖关系，一开始我没有什么特别好的想法，为了锻炼一下自己的思维能力也没有谷歌什么现成的解决方案，就在纸上随手写写画画：

不行，太抽象了，换一种方式：

看起来有点眼熟，原来是典型的有向图数据结构，想到这个就有思路了（旁边是归类的依赖类型，这个稍后说）。

有向图是图数据结构的一种，在图中，分为两种数据单元，一种是顶点，另一种是边。其中边又分为两种类型，无向的和有向的，只包含无向边的叫无向图，包含有向边的就叫有向图了。在当前的场景中，资源之间的依赖是单向的，a 依赖 b 但不代表 b 依赖 a，因此有向图是合适的数据结构。

在这里的有向图中，每个资源对应有向图中的顶点，资源间的依赖关系则是两个顶点之间的边了。如果 a 依赖 b，那么在 a 和 b 之间就有一条由 b 指向 a 的边。

在 JS 中实现一个简单的有向图数据结构还是挺简单的：

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

用一个对象包含所有的顶点，资源的 key 作为这个顶点的键值，每个顶点还需要有各自的属性：

name: 顶点的名字，对应资源名称

prev: 顶点的入度，这里表示该资源依赖其他资源的数量

next: 顶点的出度，这里表示该资源被多少其他资源依赖

adjList: 以该顶点为起点的边指向的顶点列表，这里就是依赖本资源的其他资源名称列表

有了这个就可以实现 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
}

有了这两个方法，在调用 bowl.inject 的时候可以根据已添加的资源生成一个描述资源依赖关系的图数据结构了，举例如下：

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"]
    }
  }
}

环在有向图中表示有向边构成的环路，两个顶点之间存在互相指向对方的边的情况也称为环。在 bowl 中如果出现了环，就表示资源之前出现了循环依赖或相互依赖的情况。而这种情况是不应该出现的，如果出现了需要报错。因此，我们首先要做的是分析图中是否存在环。

对于环的检测，常用的算法是深度优先遍历，例如在 Angular 中注入器检测循环依赖用的就是这个算法。

实际上，在 bowl 中我使用了另一种名为 Kahn 算法的环检测的算法，它是拓扑排序算法的一种，相比于深度优先遍历算法来说它比较直观。它的原理归纳起来有三点：

遍历图中所有的顶点，将所有入度为 0 的顶点依次入栈

如果栈非空，则从栈顶取出顶点，删除该顶点以及以该顶点为起点的边，如果删除的边的另一个顶点入度为 0 了，则把它入栈

最后，如果图中还存在顶点，则表示图中有环

这个算法结合业务场景会很好理解，入度为 0 的顶点表示其对应的资源没有任何依赖，将顶点和边删除后剩下的入度为 0 的顶点表示只依赖前一个资源的资源，前一个资源加载后，当前资源就可以加载了，以此类推。最后如果还有顶点被剩下的话，说明可顺序加载的资源都加载完了还有无法加载的资源，这些资源之间一定存在循环依赖的关系。

Kahn 算法写成代码如下：

Graph.prototype.hasCycle = function() {
  const cycleTestStack = []
  const vertices = merge({}, this.vertices) // 复制一份数据进行操作
  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
}

如果图能够通过环检测，说明其中的资源不存在循环依赖关系，下一步就是要计算资源的加载顺序了。很明显，这里要做的是图的遍历，上面提到的深度遍历也是可以用的，但是这是否是最好的方式呢？

我认为不是的，假设有依赖关系的资源如下：

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

如果用深度遍历来进行资源加载的话，加载顺序将会是 a->b->c->d->e->f，每个资源顺序加载。而这里 bowl 加载资源的行为都是被包装在 promise 中的，请求也可以并发出去，并发的多个请求只要通过 Promise.all 取到 resolve 的时间点就可以保证全部加载完成了，所以，较为理想的加载顺序应该是 a->b->[c, e]->[d, f]。

要得到这样的结果，实际上可以直接利用 Kahn 算法的思想，每次遍历过滤出一批没有依赖未加载的资源，最后得到一个分批次的加载顺序。

要得到上面提到的分批加载顺序，可以通过以下代码：

Graph.prototype.getGroup = function() {
  if (this.hasCycle()) { // 有环则报错
    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
}

当然除了深度优先和 Kahn 算法，广度优先也是可用的算法，在这几种算法中，DFS 和 BFS 的时间复杂度都是 O(n^2)（这里的代码中使用的可以看成是一个邻接矩阵），如果用邻接链表的方式表示图的话，时间复杂度将会是 O(n+e)。对于 Kahn 算法，时间复杂度明显是 O(n^2)。既然这里用了邻接矩阵的方式，时间复杂度都是一样的，效率上差别不大。而且在前端资源的加载场景下，不会出现那么多的资源要去分析，这点差别是可以忽略的。

通过 getGroup 方法，取得了一个描述加载顺序的二维数组：[["a"], ["b"], ["c", "e"], ["d", "f"]]。下面要做的是加载它们，对于这个数组中的每个子数组中的资源，它们都是可以同时加载的，把这块逻辑抽出来，返回一个 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)
}

这段代码的具体细节就省略了，最后通过一个 Promise.all 返回一个包装后的 promise，group 中的资源全部加载完成后这个 promise 会被 resolve。

这个时候问题就来了，对于这个二维数组，不能简单的将每个子数组都一股脑传入 batchFetch 方法中，因为传入 Promise 构造函数中的函数是会立即执行的，而后一个子数组中的资源必需在前一个 batchFetch promise 被 resolve 后才能加载。同时，二维数组的长度也是不定的，更不能穷举。

这里就是一个典型的多个 promise 异步任务的场景，每个异步任务的构建依赖前一个任务的完成状态。一开始由于我对异步编程不是特别熟悉，有点想不通，在 bluebird 这个 promise 库中找到了 Promise.reduce 和 Promise.each 这两个静态方法是可以解决问题的，但是对于 bowl 这么一个小型库来说，引入一个 bluebird 有点杀鸡用牛刀的感觉，不太合适。

最终通过查 Promise/A+ 规范以及一些尝试，找到了一个解决方案，其实很简单。对于 promise 中的 then 回调函数，它返回的是一个新的 Promise，而每个 then 中的 onFulfill 回调都会在前一个 Promise resolve 后执行。利用这个特性，只需要遍历原二维数组，将每个 batchFetch(group) 放在一个 then 中的 onFulfill 函数中执行并返回即可（因为 batchFetch 的返回值就是一个 promise），有一种惰性执行的感觉。

let ret = Promise.resolve() // 强行开启一个 promise 链
resolvedIngredients.forEach(group => {
  ret = ret.then(function() {
    return batchFetch(group)
  })
})
return ret

这样，最终 ret 被 resolve 的时候，说明所有资源都按顺序加载完了。

「学习 JavaScript 数据结构与算法」，人民邮电出版社

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

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

https://promisesaplus.com/