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函数的逻辑比较简单

1. 判断节点是否可以复用，可以复用则对节点打补丁

2. 节点不可复用，创建新的节点插入到旧节点之前，同时删除旧节点

可以看出来，如果节点不可复用，直接创建新节点替换，旧的子节点也将不再考虑复用。这就是对应了 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 的完整源码涉及的变量比较多，我们只需要了解大致是通过 tag key inputType 来判断的就行。也就是说，当 tag key inputType 完全相同时，我们认定节点可复用。

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函数的逻辑也不复杂，一起来分析分析

1. 找到对应的 dom 节点 elm，并且赋值给 vnode.elm

2. 判断新节点类型（vnode.text），如果是文本节点，更新 elm 文本即可

3. 非文本节点下，判断新老节点的子节点

4. 如果新老节点都有子节点，走子节点的同层比较流程 updateChildren

5. 如果只有新节点有子节点，直接使用 addVnodes 为 elm 添加子节点（先删除文本）

6. 如果只有旧节点有子节点，使用 removeVnodes 移除即可

7. 如果都没有子节点，判断旧数据是否有文本节点，有则清空

这是一个很简单的通过数据（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 我们称其为左节点，右节点，变量一下子就清晰了好多有木有

好了，开始分析逻辑了

1. 当左指针小于等于右指针循环遍历（说明上下区间都有节点）

2. 判断老节点边界为null的情况，向内移动指针

3. 判断左节点是否可以复用，可以则为节点打补丁（递归调用 patchVnode，下同），向右移动指针

4. 否则，判断右节点是否可以复用，可以则为节点打补丁，向左移动指针

5. 否则，判断新右节点和旧左节点是否可以复用，可以则为节点打补丁，同时将旧左节点移动旧右节点前面，再向内移动指针（移动的过程会淘汰旧的右节点）

6. 同理，判断新左节点和旧右节点，进行类似操作

7. 当上面的几种情况都无法复用的话，接下来使用 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];

8. 执行完上边遍历程序之后，跳出循环

9. 如果旧节点已经遍历完，则批量向后添加剩余新节点

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

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

if (newStartIdx > newEndIdx) {
  removeVnodes(oldCh, oldStartIdx, oldEndIdx);
}

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

举个例子

下面我们举个栗子看看

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

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

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

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

4. 不满足循环条件，跳出循环

5. 根据 oldStartIdx oldEndIdx 删除旧节点 D F G

总结

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

参考

• 深入理解React：diff 算法

• 详解vue的diff算法

欢迎来前端菜鸟群一起摸鱼划水～516913974