virtual dom diff算法原理概述

[stormqx]

Virtual DOM diff算法原理概述

Virtual DOM这个概念相信大部分人都不陌生，它产生的前提之一是浏览器中的DOM操作是很“昂贵”的。Virtual DOM本质上在JavaScript和DOM之间做了一层缓存，可以拿CPU和硬盘来举例，CPU（JavaScript）只操作内存（Virtual DOM），最后再把变更写入硬盘（DOM）。

Virtual DOM主要有三个实现细节：

1. 用JavaScript对象模拟DOM树；
2. 更新时比较两颗虚拟DOM树差异；
3. 把差异应用到真正的DOM树上。

今天我们主要讨论的是不同框架的diff算法，即上述步骤2和步骤3。因此，diff算法是Virtual DOM的加速器，它会计算出Virtual DOM中真正变化的部分，然后对变化的部分进行远程DOM操作。

三个假设

翻开react官方文档，里面描述了React diff算法的设计动机。

生成将一棵树转换成另一棵树的最小操作数，即使在最前沿的算法中，该算法的复杂程度为 O(n^3)，其中 n 是树中元素的数量。

这个开销实在太过高昂，所以在三个（官方文档写的是两个）假设的基础上提出了启发式算法：

1. Web UI中DOM节点跨层级的移动操作很少；
2. 两个不同类型的元素会生成不同的树；
3. 在两次渲染中，同一层级的一组子节点，能通过key来保证元素是稳定的(相同key的元素只需要进行更新操作)。

三种策略

基于上述三个假设，业界各个框架的diff算法基本都使用三种策略：

1. 基于层次进行遍历。

   

2. 不同类型的元素，直接卸载原有的树，并建立新的树。

   

3. 针对子节点（通常是两个列表），通过key来找到正确的映射。

渲染器Patch过程

渲染器Patch过程负责对新旧VNode(用来描述Virtual DOM)，并以合适的方式更新DOM。

下面vue2的Vnode部分结构：

export default class VNode {
  tag: string | void;
  data: VNodeData | void;
  children: ?Array<VNode>;
  text: string | void;
  elm: Node | void;
  ns: string | void;
  context: Component | void; // rendered in this component's scope
  key: string | number | void;
  componentOptions: VNodeComponentOptions | void;
  componentInstance: Component | void; // component instance
  parent: VNode | void; // component placeholder node
  ...
}

结合Vnode结构和上述三种策略，我们可以得出一次patch过程的主要流程：

上述过程的思想其实就是基于策略1和策略2，逐层进行比对，判断新旧Vnode节点类型并执行对应更新操作。在进行完这些操作后，对于新旧两个节点来说，就剩下子节点的差异了。

更新子节点

子节点的更新策略十分朴素。如上图，当旧children没有子节点时，新children有两种情况：

• 情况一： 新旧子节点都不存在时，什么都不需要操作。
• 情况二：旧子节点不存在，新子节点存在时，将新的子节点添加到DOM中即可。

如上图，当旧children有子节点时，新children有两种情况：

• 情况一：旧子节点存在，新子节点不存在时，移除旧子节点。
• 情况二：旧子节点和新子节点都存在时，这时进入至关重要的一步，即diff算法的核心内容。

下面我们会基于不同框架，来分析他们对这种情况的处理方式。

diff核心算法（重点）

diff算法的核心目的就是尽可能多地复用DOM元素来降低性能开销。因为key的存在，我们可以知道哪些节点是可以被复用的。所以对于DOM元素来说，应该有三种操作：

1. 新children和旧children中都存在的节点(key相同)，使用移动操作。
2. 新children存在、旧children中不存在的节点，使用插入操作。
3. 新children不存在、旧children中存在的节点，使用删除操作。

插入操作和删除操作都很容易理解，难点在于使用哪种策略来进行移动操作。下面我们会分别对三种框架的移动操作策略进行分析。

React@15

寻找移动节点

我们先来看一个例子，大家可以用几秒钟的时间观察上图中的新旧children节点的排列方式，能否发现某种规律呢？

直观上来看，我们发现节点B和节点C的在新旧children中的相对位置是没有发生变化的。这种不变的顺序映射到索引上该怎么定义？在寻找移动节点的过程中，如果两个节点在新旧children中的索引均呈递增趋势，则说明这两个节点在新旧children中的相对位置没有变化，也就不需要进行移动操作。

如上图，旧节点B的索引为1，旧节点A的索引为2，新节点B的索引为0，新节点C的索引为1，

则有B -> C（旧索引 1-> 2, 新索引0 ->1）均呈递增趋势，所以这两个节点不需要移动。

React@15借鉴了这个思路，维护了一个lastIndex变量，该变量用来存储在寻找过程中遇到的在旧children中最大索引值。一头雾水？我们下面逐步来分析React的做法。

前提：React使用从左到右单向遍历。

步骤：

1. 初始化lastIndex为0。
2. 遍历新children数组，依次拿出节点来进行判断。
3. 首先遇到节点B，节点B在旧children中的索引为1，此时lastIndex变量为0，1>0显示索引呈递增趋势，即节点相对位置未发生变化，所以节点B不需要移动，更新最大索引值lastIndex为1。
4. 接着遇到节点C，节点C在旧children中的索引为2，此时lastIndex变量为1，2>1显示索引呈递增趋势，即节点相对位置未发生变化，所以节点C不需要移动，更新最大索引值lastIndex为2。
5. 接着遇到节点E，节点E在旧children中不存在，所以需要插入节点E，最大索引值lastIndex仍为2。
6. 接着遇到节点A，该节点在旧children中的索引为0，此时lastIndex变量为2，0<2显示索引未呈递增趋势，则需要移动节点A，最大索引值lastIndex仍为2。
7. 新children数组遍历完后，发现我们还漏掉了节点D，节点D在新children中不存在，在旧children中存在，需要删除节点D。因为最后还会遍历一遍旧children数据，来删除不存在的节点。

我们可以得到下述代码：

// 用来存储在寻找过程中遇到的在旧 children 中最大索引值
let lastIndex = 0;
// 遍历新的 children
for(let i = 0; i < nextChildren.length; i++) {
  const nextVNode = nextChildren[i];
  // 标示是否找到复用节点
  let find = false;
  for(let j = 0; j < prevChildren.length; j++) {
    const prevVNode = prevChildren[j];
    // 寻找可以复用的节点，即 key 相同。
    // 调用 patch 函数更新该节点。
    if(nextVNode.key === prevVNode.key) {
      find = true;
      patch(prevVNode, nextVNode, container);
      if(j >= lastIndex) {
        // 索引呈现递增趋势，不需要移动。
        // 更新 lastIndex 即可
        lastIndex = j;
      } else {
        // 需要移动
        // refNode 是为了调用 insertBefore 函数准备的
        // VNode的el属性为对应的DOM元素
        const refNode = nextChildren[i-1].el.nextSibling;
        // 调用 insertBefore 函数移动 DOM，将该节点放在nextChildren[i-1]节点后面
        container.insertBefore(prevVNode.el, refNode);
      }
      break; // 找到之后break
    }
  }
  // 插入新节点
  if(!find) { 
    // 找到refNode，将新节点插入到refNode前面
    const refNode = 
          i -1 < 0 
                    ? prevChildren[0].el
                    : nextChildren[i-1].el.nextSibling;    
    mount(nextVNode, container, refNode)
  }
  // 移除不存在节点
  // 遍历旧的节点
  for(let i = 0; i < prevChildren.length; i++) {
    const prevVNode = prevChildren[i];
    // 拿着旧 VNode 去新 children 中寻找相同节点
    const has = nextChildren.find(nextVNode => nextVNode.key === prevVNode.key);
    if(!has) {
      // 如果没有找到相同节点，移除该节点
      container.removeChild(prevVNode.el);
    }
  }
}

缺陷

React@15通过单向遍历，维护lastIndex变量试图寻找递增趋势节点，但是会有一些极端场景出现。

如上图所示，按照React@15的算法。执行步骤：

1. 初始化lastIndex为0。
2. 遍历新children数组，依次拿出节点来进行判断。
3. 访问节点D，节点D在旧children中所以为3，3 > 0，更新lastIndex为3。
4. 访问节点A，节点A在旧children中所以为0，0 < 3，移动节点A。
5. 访问节点B，节点A在旧children中所以为1，1 < 3，移动节点B。
6. 访问节点C，节点A在旧children中所以为2，2 < 3，移动节点C。
7. 访问旧children数组，删除不存在节点。

上述算法进行了三次移动操作。但其实根据我们的直觉来看，节点A、节点B和节点C的索引呈递增顺序，其实我们只需要将节点D移动到最前面即可。所以React@15的算法并不是最优解，一些极端情况下会执行一些不必要的移动操作。

总结

1. 基于三种策略实现diff算法，将 O(n3) 复杂度的问题转换成 O(n) 复杂度的问题；
2. 参考了原理：在寻找移动节点的过程中，如果两个节点在新旧children中的索引均呈递增趋势，则说明这两个节点在新旧children中的相对位置没有变化，也就不需要进行移动操作；
3. 使用变量lastIndex来简单模拟上述原理，但并非全局最优解，极端情况有优化空间（例如将最后的节点移动到最前）。

Vue@2

vue@2底层同样使用了virtual DOM来实现，vue@2的virtual DOM部分直接整合了snabbdom库，可以看到，一款优秀的框架不代表所有的内容都要原创，而是在一个好的设计上吸收改进，使用更优秀的东西进化自己。vue@2采用了双端比较的算法。

所谓双端比较，就是从新旧children的两端开始，逐步向中间移动的比较方式。它是一种比较平衡的算法，可以一定程度上避免React的极端情况。

双端比较原理

双端比较使用四个索引来寻找需要移动的节点：

1. oldStartIdx：旧children的开始索引；
2. oldEndIdx：旧children的结束索引；
3. newStartIdx：新children的开始索引；
4. newEndIdx：新children的结束索引。

代码如下：

let oldStartIdx = 0
let oldEndIdx = oldCh.length - 1
let newStartIdx = 0
let newEndIdx = newCh.length - 1
let oldStartVnode = oldch[0]
let oldEndVnode = oldCh[oldEndIdx]
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]

我们接着使用React的极端例子来分析双端比较算法。

前提：Vue@2从两端向中间收敛遍历。

步骤一：

1. 先比较oldStartIdx和newStartIdx索引对应节点，此时oldVNode为节点A，newVNode为节点D，两者不同，进入步骤二。
2. 再比较oldEndIdx和newEndIdx索引对应节点，此时oldVNode为节点D，newVNode为节点C，两者不同，进入步骤三。
3. 再比较oldStartIdx和newEndIdx索引对应节点，此时oldVNode为节点A，newVNode为节点D，两者不同，进入步骤四。
4. 再比较oldEndIdx和newStartIdx索引对应节点，此时oldVNode为节点D，newVNode为节点D，两者相同，则说明节点D在新children的开始位置，将节点D移动到新children最前端，同时oldEndIdx--; newStartIdx++。

步骤二：

1. 比较oldStartIdx和newStartIdx索引对应节点，此时oldVNode为节点A，newVNode为节点A，两者相同，则说明节点A在新children和旧children均在最前端，不需要移动节点，只需要oldStartIdx++; newStartIdx++。

步骤三：

1. 比较oldStartIdx和newStartIdx索引对应节点，此时oldVNode为节点B，newVNode为节点B，两者相同，则说明节点B在新children和旧children均在最前端，不需要移动节点，只需要oldStartIdx++; newStartIdx++。

步骤四：

1. 比较oldStartIdx和newStartIdx索引对应节点，此时oldVNode为节点C，newVNode为节点C，两者相同，则说明节点B在新children和旧children均在最前端，不需要移动节点，只需要oldStartIdx++; newStartIdx++。此时发现oldStartIdx > oldEndIdx ，newStartIdx > newEndIdx。退出遍历。

分析：

vue@2的算法在这种情况下只进行了一次移动操作，而React@15却进行了三次移动操作。

通过上述实例分析，我们暂时可以得到下述四种情况：

1. sameVnode(oldStartVnode, newStartVnode) => oldStartIdx++; newStartIdx++
2. sameVnode(oldEndVnode, newEndVnode) => oldEndIdx--; newEndIdx--
3. sameVnode(oldStartVnode, newEndVnode) => 该节点移动到最后端
4. sameVnode(oldEndVnode, newStartVnode) => 该节点移动到最前端

我们可以写出如下代码：

 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
   if (sameVnode(oldStartVnode, newStartVnode)) {
     // 情况一
     // 调用patch方法更新
     patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
     // 更新索引
     oldStartVnode = oldCh[++oldStartIdx]
     newStartVnode = newCh[++newStartIdx]
   } else if (sameVnode(oldEndVnode, newEndVnode)) {
     // 情况二
     // 调用patch方法更新
     patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
     // 更新索引
     oldEndVnode = oldCh[--oldEndIdx]
     newEndVnode = newCh[--newEndIdx]
   } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
     // 情况三
     // 调用patch方法更新
     patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
     // 将容器中第一个子节点移动到最后面
     canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
     // 更新索引
     oldStartVnode = oldCh[++oldStartIdx]
     newEndVnode = newCh[--newEndIdx]
   } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
     // 情况四
     // 调用patch方法更新
     patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
     // 将容器中最后一个子节点移动到最前面，使其成为第一个子节点
     canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
     // 更新索引
     oldEndVnode = oldCh[--oldEndIdx]
     newStartVnode = newCh[++newStartIdx]
   } 
 }

普通情况处理方式

上述我们讨论的四种情况均为匹配时的处理方式，那么如果四种情况都没有找到相同节点，该如何处理呢？我们用下图中的例子进行分析。

通过①、②、③、④ 四种情况比对，仍未找到可以复用的节点，vue@2会判断newStartVnode节点是否在旧children中出现，如果成功找到，则将该节点对应的DOM元素直接移动到最前端。

如上图所示，找到节点D在旧children中的位置idxInOld，将节点D对应的DOM元素移动到节点A前面，与此同时，将oldCh[idxInOld]设置为undefined，最后执行newStartIdx++。

将oldCh[idxInOld]设置为undefined的原因：后续当oldStartIdx索引或者oldEndIdx索引移动到该位置时，因为该节点已经被移动过，所以无需再进行上述四种情况判断，直接跳过即可。

‘

接下来，比较oldStartIdx和newStartIdx索引对应节点时，此时oldStartVNode为节点A，newStartVNode为节点A，两者相同，不需要移动节点，只需要oldStartIdx++; newStartIdx++。

接下来，比较oldEndIdx和newStartIdx索引对应节点时，此时oldEndVNode为节点B，newStartVNode为节点B，两者相同，则说明节点B在新children的开始位置，将节点B移动到新children最前端，同时oldEndIdx--; newStartIdx++。

接下来，未成功匹配上述四种情况，尝试去寻找节点E在旧children中的位置idxInOld，因为没有找到可复用的节点，所以该节点为新增节点，直接插入新节点。同时newStartIdx++

此时由于不满足while循环条件退出循环体，但是我们发现仍然有节点C（需要被删除）被我们遗漏。所以在循环体结束后，仍然要判断旧children中是否有未删除的节点。同理，新children中也可能有新出现的节点被遗漏。在循环体结束后，也需要处理这种情况。如下图。

通过上述分析，我们可以得出普通情况的详细代码：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // 判断节点是否为undefined，若是表示该节点已经被移动
  if (isUndef(oldStartVnode)) {
    oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
  } else if (isUndef(oldEndVnode)) {
    oldEndVnode = oldCh[--oldEndIdx]
  } else if (sameVnode(oldStartVnode, newStartVnode)) {
    // 情况一，省略
  } else if (sameVnode(oldEndVnode, newEndVnode)) {
    // 情况二，省略
  } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
    // 情况三，省略
  } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
    // 情况四，省略
  } else {
    // 构建oldKeyToIdx哈希表
    if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
    // 寻找旧children是否有newStartVnode
    idxInOld = isDef(newStartVnode.key)
      ? oldKeyToIdx[newStartVnode.key]
    : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
    // 未找到可复用的节点，创建新节点
    if (isUndef(idxInOld)) { // New element
      createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
    } else {
      vnodeToMove = oldCh[idxInOld]
      // 找到可复用节点，判断是否是相同类型
      if (sameVnode(vnodeToMove, newStartVnode)) {
        // 调用patch方法更新
        patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        // 设置旧children中移动位置值为undefined
        oldCh[idxInOld] = undefined
        canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
      } else {
        // same key but different element. treat as new element
        createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false,   newCh, newStartIdx)
      }
    }
    newStartVnode = newCh[++newStartIdx]
  }
}
if (oldStartIdx > oldEndIdx) {
  // 判断新children中是否有新节点未插入
  refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
  addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx) {
  // 判断旧children中是否有不存在节点未删除
  removeVnodes(oldCh, oldStartIdx, oldEndIdx)
}

总结

1. 同样基于三种策略实现diff算法，将 O(n3) 复杂度的问题转换成 O(n) 复杂度的问题；
2. 双端比较避免了React@15的极端情况，这使得该算法在普通情况下表现比较平稳。
3. 并未借助「在寻找移动节点的过程中，如果两个节点在新旧children中的索引均呈递增趋势，则说明这两个节点在新旧children中的相对位置没有变化，也就不需要进行移动操作」原理的思想。所以并不保证移动的次数是最少的。

Inferno

Inferno介绍

核心思想

双端比较

最长递增子序列

总结

相关链接

• React’s diff algorithm
• 渲染器的核心 Diff 算法
• React 源码剖析系列 － 不可思议的 react diff
• 为什么inferno.js这么快？