vueDiff 算法解读-阿里云开发者社区

前言

在面试中谈到 vue 源码，一般都会扯扯 diff 算法，而这个 diff 又在网上传的神乎其神的，说是提升了页面更新性能，我们一起看看到底咋回事吧

传统diff算法

在 Jquery 时代，“前辈们”就告诉过我，频繁的操作 DOM 是很消耗性能的，我们可以在拼接完 HTML 片段后，通过 innerHTML 来替换整个 DOM，效率提升杠杠的。

所以之前我一直有个疑问，diff 算法为什么通过比较节点，复用节点可以达到性能提升，直接替换整个 innerHTML 不更高效么？

带着疑问在网上查阅了一些文章，感觉似乎是明白了

首先，创建一个完整的节点对象的成本是非常大的，因为 DOM 节点是个非常复杂的对象

const elm = document.createElement('div')
for(let propName in elm) {
    console.log(propName)
}
复制代码

所以即使我们在浏览器中通过 innerHTML 来替换整个 DOM，浏览器也会通过比较不同的节点来达到复用。

比较算法涉及每个新旧节点的两两比较，其复杂度为 O(n^2)，比较之后还得计算最小转化方式，所以综合复杂度就是 O(n^3)，我们称此为 传统diff算法

具体可以参看 react的diff 从O(n^3)到 O(n) ，请问 O(n^3) 和O(n) 是怎么算出来？

框架层diff算法的原理

相较于 传统的diff算法，框架层的 diff 有个大前提假设

Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计

所以 diff 的核心就在于，它只对同层节点进行比较，忽略跨层节点的复用

就如上图所示，只会比较父元素相同的同层节点的复用性。

值得注意的是，同层节点的比较也不会两两进行，而是按照一定的顺序比较，或通过 key 属性判断，所以只需要遍历一次新节点，因此算法的复杂度就降低到了O(n)

通过vue源码来看diff

其实 diff 算法的原理就是这么简单，无非是递归加上遍历节点来比较节点复用性。但在 vue 源码中，具体是如何实现的呢？一起看看

虚拟节点（Virtual Dom）

首先要明白，在 vue 中会维护一个和 DOM 节点对应的 vnode 对象

例如

<div key="1">123</div>
复制代码

在 vue 中就会有个 vnode 对象与之对应，我们列举了其中几个关键属性

{
  elm: el, // 对应真实的DOM节点
  tag: 'div',
  key: 1,
  text: '123',
  children: []
}
复制代码

vnode 的 children 数组中对应子节点的 vnode 对象，所以在 vue 中通过 vnode 和真实的 DOM 树进行映射，我们也称之为虚拟树。

正是有了虚拟树，当数据更新时。我们可以对比新数据构建的 vnode 和老数据构建的 oldVnode 的差异，来实现外科手术式的精准更新。

而我们对比差异的算法就是采用的 diff。通过 diff 对比虚拟树的差异，将差异通过打补丁（patch）的方式更新到对应的真实 DOM 节点上。

patch函数

patch函数是 diff 流程的入口函数

其接收两个入参，分别是虚拟节点 vnode 和 oldVnode，对虚拟节点进行 diff 分析

function patch (oldVnode, vnode) {
  // some code
  if (sameVnode(oldVnode, vnode)) {
    // patch existing root node
    patchVnode(oldVnode, vnode)
  } else {
    // replacing existing element
    const oldElm = oldVnode.elm
    const parentElm = nodeOps.parentNode(oldElm)
    // create new node
    createElm(
      vnode,
      null,
      parentElm,
      nodeOps.nextSibling(oldElm)
    )
    // destroy old node
    if (isDef(parentElm)) {
      removeVnodes([oldVnode], 0, 0)
    }
  }
  return vnode.elm
}
复制代码

patch函数的逻辑比较简单

判断节点是否可以复用，可以复用则对节点打补丁
节点不可复用，创建新的节点插入到旧节点之前，同时删除旧节点

可以看出来，如果节点不可复用，直接创建新节点替换，旧的子节点也将不再考虑复用。这就是对应了 diff 的假设，Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计

我们再来看看 sameVnode 函数是如何判断可复用性的

function sameVnode (a, b) {
  return (
    a.key === b.key && (
      (
        a.tag === b.tag &&
        a.isComment === b.isComment &&
        isDef(a.data) === isDef(b.data) &&
        sameInputType(a, b)
      ) || (
        isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)
      )
    )
  )
}
复制代码

这段 vue 的完整源码涉及的变量比较多，我们只需要了解大致是通过 tagkeyinputType 来判断的就行。也就是说，当 tagkeyinputType 完全相同时，我们认定节点可复用。

patchVnode函数

接下来，再看看是如何对可复用节点进行打补丁的

function patchVnode(oldVnode, vnode) {
  // some code
  if (oldVnode === vnode) {
    return;
  }
  const elm = (vnode.elm = oldVnode.elm);
  const oldCh = oldVnode.children;
  const ch = vnode.children;
  // 非文本节点
  if (isUndef(vnode.text)) {
    // 新旧节点都有子节点
    if (isDef(oldCh) && isDef(ch)) {
      // 子节点的同层比较
      if (oldCh !== ch)
        updateChildren(elm, oldCh, ch);
    } else if (isDef(ch)) {
      // 仅新元素有子节点
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, "");
      addVnodes(elm, null, ch, 0, ch.length - 1, null);
      // 仅旧元素有子节点
    } else if (isDef(oldCh)) {
      removeVnodes(oldCh, 0, oldCh.length - 1);
    } else if (isDef(oldVnode.text)) {
      // 清空文本
      nodeOps.setTextContent(elm, "");
    }
  // 文本节点，更新文本即可
  } else if (oldVnode.text !== vnode.text) {
    nodeOps.setTextContent(elm, vnode.text);
  }
}
复制代码

patchVnode函数的逻辑也不复杂，一起来分析分析

找到对应的 dom 节点 elm，并且赋值给 vnode.elm
判断新节点类型（vnode.text），如果是文本节点，更新 elm 文本即可
非文本节点下，判断新老节点的子节点
如果新老节点都有子节点，走子节点的同层比较流程 updateChildren
如果只有新节点有子节点，直接使用 addVnodes 为 elm 添加子节点（先删除文本）
如果只有旧节点有子节点，使用 removeVnodes 移除即可
如果都没有子节点，判断旧数据是否有文本节点，有则清空

这是一个很简单的通过数据（vnode oldVnode）来为真实节点 elm 打补丁更新节点的过程，addVnodes 和 removeVnodes 啥的就是直接操作 elm 节点更新了。

值得注意的是，这边涉及了子节点的同层比较 updateChildren，我们来看看它是如何工作的，也就是说如何从父节点进一步流转到子节点对比的。

updateChildren

子节点的对比流程就稍微复杂一点了，因为涉及如何判断是否存在同层可复用节点，是根据 key 属性来判定呢?还是通过其它顺序呢?

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0;
  let newStartIdx = 0;
  let oldEndIdx = oldCh.length - 1;
  let oldStartVnode = oldCh[0];
  let oldEndVnode = oldCh[oldEndIdx];
  let newEndIdx = newCh.length - 1;
  let newStartVnode = newCh[0];
  let newEndVnode = newCh[newEndIdx];
  let oldKeyToIdx, idxInOld, vnodeToMove, refElm;
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx];
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // Vnode moved right
      patchVnode(oldStartVnode, newEndVnode);
      nodeOps.insertBefore(
        parentElm,
        oldStartVnode.elm,
        nodeOps.nextSibling(oldEndVnode.elm)
      );
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // Vnode moved left
      patchVnode(oldEndVnode, newStartVnode);
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      if (isUndef(oldKeyToIdx))
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
      if (isUndef(idxInOld)) {
        // New element
        createElm(
          newStartVnode,
          null,
          parentElm,
          oldStartVnode.elm
        );
      } else {
        vnodeToMove = oldCh[idxInOld];
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(vnodeToMove, newStartVnode);
          oldCh[idxInOld] = undefined;
          nodeOps.insertBefore(
            parentElm,
            vnodeToMove.elm,
            oldStartVnode.elm
          );
        } else {
          // same key but different element. treat as new element
          createElm(newStartVnode, insertedVnodeQueue, parentElm);
        }
      }
      newStartVnode = newCh[++newStartIdx];
    }
  }
  if (oldStartIdx > oldEndIdx) {
    refElm = isUndef(newCh[newEndIdx + 1])
      ? null
      : newCh[newEndIdx + 1].elm;
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
  } else if (newStartIdx > newEndIdx) {
    removeVnodes(oldCh, oldStartIdx, oldEndIdx);
  }
}
复制代码

咋一看，代码还挺长的嘞，但其实就是有多个 IF-ELSEIF 的分类流程而已，相信我，代码看似冗长却依然简单

建议分析前像我一样先画个图，因为代码前部分的变量真的有点多

首先我们把 startIdx endIdx 称为左指针，右指针，相应的 startVnode，endVnode 我们称其为左节点，右节点，变量一下子就清晰了好多有木有

好了，开始分析逻辑了

当左指针小于等于右指针循环遍历（说明上下区间都有节点）
判断老节点边界为null的情况，向内移动指针
判断左节点是否可以复用，可以则为节点打补丁（递归调用 patchVnode，下同），向右移动指针
否则，判断右节点是否可以复用，可以则为节点打补丁，向左移动指针
否则，判断新右节点和旧左节点是否可以复用，可以则为节点打补丁，同时将旧左节点移动旧右节点前面，再向内移动指针（移动的过程会淘汰旧的右节点）
同理，判断新左节点和旧右节点，进行类似操作
当上面的几种情况都无法复用的话，接下来使用 key 来判断是否可以复用（判断新左节点）

首先，通过 createKeyToOldIdx 函数来得到旧节点索引和 key 属性的映射，数据结构为

{
  keyIdx: oldChIdx
}
复制代码

再赋值 idxInOld 变量为新左节点的 key 对应的旧节点索引

idxInOld = isDef(newStartVnode.key)
  ? oldKeyToIdx[newStartVnode.key]
  : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
复制代码

一起看看当新节点没有 key 的时候，findIdxInOld 函数的逻辑，返回第一个可以复用的旧节点

function findIdxInOld (node, oldCh, start, end) {
  for (let i = start; i < end; i++) {
    const c = oldCh[i]
    // 返回第一个可以复用的旧节点（旧节点的key也一定会是null）
    if (isDef(c) && sameVnode(node, c)) return i
  }
}
复制代码

如果未找到 key 可复用的节点索引，则创建新的节点，移动到旧左节点（oldStartVnode.elm）之前

if (isUndef(idxInOld)) {
  // New element
  createElm(
    newStartVnode,
    null,
    parentElm,
    oldStartVnode.elm
  );
}
复制代码

如果找到 key 对应的旧节点，还要通过 sameVnode 再判断是否真正可复用，不可复用则还是创建新节点。确认 key 对应的旧节点可复用，为旧节点打补丁，旧节点数组元素设置为 null（这也是第一步要判断是否为 null 的原因），同时将旧节点移动到旧左节点（oldStartVnode.elm）之前

vnodeToMove = oldCh[idxInOld];
if (sameVnode(vnodeToMove, newStartVnode)) {
  patchVnode(vnodeToMove, newStartVnode);
  oldCh[idxInOld] = undefined;
  nodeOps.insertBefore(
    parentElm,
    vnodeToMove.elm,
    oldStartVnode.elm
  );
} else {
  // same key but different element. treat as new element
  createElm(newStartVnode, insertedVnodeQueue, parentElm);
}
复制代码

最后完成本步逻辑，向内移动指针

newStartVnode = newCh[++newStartIdx];
复制代码

执行完上边遍历程序之后，跳出循环
如果旧节点已经遍历完，则批量向后添加剩余新节点

if (oldStartIdx > oldEndIdx) {
  refElm = isUndef(newCh[newEndIdx + 1])
    ? null
    : newCh[newEndIdx + 1].elm;
  addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
}
复制代码

如果新节点已经遍历完，则批量删除剩余旧节点

if (newStartIdx > newEndIdx) {
  removeVnodes(oldCh, oldStartIdx, oldEndIdx);
}
复制代码

至此，updateChildren 的逻辑也就讲完了，其中的难点在于分类判断的情况比较多，而其精髓在于指针（索引）的移动。

温馨提示：insertBefore 方法是可以移动节点的，它会删除原节点，大家可以看看MDN的说明

举个例子

下面我们举个栗子看看

我们假定所有节点都有对应的 key 属性（值和字母对应）

对比左节点 A === A 可复用，向右移动指针

对比节点 B === B 可复用，将 B 移动 D 之前，向内移动指针

C 找不到复用节点，在 D 之前创建新节点，同时移动指针

不满足循环条件，跳出循环
根据 oldStartIdx oldEndIdx 删除旧节点 D F G

总结

Diff 的原理其实比较简单，就是同层比较复用性。但是如何比较同层节点复用性的逻辑上还是比较繁多的，需要我们化繁为简，自然就能看懂。上面的分析可能会有错误的地方，欢迎大家指出。大家新年快乐！

vueDiff 算法解读

前言

传统diff算法

框架层diff算法的原理

通过vue源码来看diff

虚拟节点（Virtual Dom）

patch函数

patchVnode函数

updateChildren

举个例子

总结

参考

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

vueDiff 算法解读

前言

传统diff算法

框架层diff算法的原理

通过vue源码来看diff

虚拟节点（Virtual Dom）

patch函数

patchVnode函数

updateChildren

举个例子

总结

参考

热门文章

最新文章

相关课程

相关电子书

相关实验场景