Vue-diff算法

为什么要用Diff算法

在浏览器中操作DOM的代价是非常“昂贵”的。。。

传统的Diff算法

传统的Diff算法通过循环递归对节点进行比较，然后判断每个节点的状态以及要做的操作（add，remove，change），最后根据Virtual DOM进行DOM的渲染。大体流程如下图:

传统Diff算法的复杂度为O(n^3)，这个复杂度相对来说还是较高的。后来React开发者提供了一种复杂度仅为O(n)的Diff算法。下面就来看一下O(n)复杂度的Diff算法是如何实现的。

更高效的Diff算法

React的开发者结合Web界面的特点做出了两个大胆的假设，使得Diff算法复杂度直接从O(n^3)降低到O(n)，假设如下：

两个相同组件产生类似的DOM结构，不同的组件产生不同的DOM结构；
对于同一层次的一组子节点，它们可以通过唯一的id进行区分。

通过这两个假设，他们提供了下面的Diff算法思路。

同层比较

新的Diff算法是逐层进行比较，只比较同一层次的节点，大大降低了复杂度，具体如下图。在后面的内容中也会介绍Vue中同层节点比较的具体实现。

不同类型节点的比较
如果发现新旧两个节点类型不同时，Diff算法会直接删除旧的节点及其子节点并插入新的节点，这是由于前面提出的不同组件产生的DOM结构一般是不同的，所以可以不用浪费时间去比较。注意的是，删除节点意味着彻底销毁该节点，并不会将该节点去与后面的节点相比较。

相同类型节点的比较
若是两个节点类型相同时，Diff算法会更新节点的属性实现转换。

列表节点的比较
列表节点的操作一般包括添加、删除和排序，列表节点需要我们给它一个key才能进行高效的比较。

Vue Diff算法的实现

Vue的Diff算法与上面的思路大体相似，只比较同级的节点，若找不到与新节点类型相同的节点，则插入一个新节点，若有相同类型的节点则进行节点属性的更新，最后删除新节点列表中不包含的旧节点。具体的实现在vue源码的src/core/vdom/patch.js中的updateChildren方法中，由于代码较长，下面简单说一下整个的比较流程。

初始化

如上图，有一组新旧节点数组before：[A, B, C, D]、after：[E, C, F, G]，我们设置了四个哨兵节点，oldStartIdx、newStartIdx、oldEndIdx、newEndIdx分别指向新旧节点数组的起始下标和开始下标，值为0,0,3,3；oldStartVnode，newStartVnode，oldEndVnode，newEndVnode则分别指向了before和after节点列表中对应哨兵节点下标的值，值为before[oldStartVnode],after[newStartIdx],before[oldEndIdx],after[newEndIdx]。

Diff

当哨兵满足oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx的条件的时候，我们会循环进行一系列节点之间的比较。

优先判断

我们首先对上面声明的各个节点进行一些优先级较高的判断。

判断1：oldStartVnode是否为空，若为true则oldStartIdx向后移动，继续下一个节点的判断。判断代码如下：

if (isUndef(oldStartVnode)) {
    // 更新哨兵
    oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
}

判断2：oldEndVnode是否为空，若为true则oldEndIdx向前移动。判断代码如下：

1
2
3

else if (isUndef(oldEndVnode)) {
    oldEndVnode = oldCh[--oldEndIdx]
}

判断3：使用 sameVnode判断before和after未判断的头节点是否为相同节点，若为true，则按照上面思路说的，对相同类型节点进行节点的属性的更新并修改哨兵位置。

// sameVnode为判断节点是否相等的方法，包括key、tag、isComment等各个属性的相等才能算作相同节点
else if (sameVnode(oldStartVnode, newStartVnode)) {
    // 更新节点内容
    patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
    // 更新哨兵
    oldStartVnode = oldCh[++oldStartIdx]
    newStartVnode = newCh[++newStartIdx]
}