Vue进阶 Diff算法详解 | 学习笔记

一、虚拟 DOM

什么是虚拟 DOM？

虚拟 DOM 就是把真实 DOM 树的结构和信息抽象出来，以对象的形式模拟树形结构，如下：

真实 DOM:

<div>
  <p>Hello World</p>
</div>

对应的虚拟 DOM 就是：

let vnode = {
  tag: 'div',
  children: [{ tag: 'p', text: 'Hello World' }],
};

为什么需要虚拟 DOM？

渲染真实 DOM 会有一定的开销，如果每次修改数据都进行真实 DOM 渲染，都会引起 DOM 树的重绘和重排，性能开销很大。那么有没有可能只修改一小部分数据而不渲染整个 DOM 呢？虚拟 DOM 和 Diff 算法可以实现。

怎么实现？

1. 先根据真实 DOM 生成一颗虚拟 DOM 树
2. 当某个 DOM 节点数据发生改变时，生成一个新的 Vnode
3. 新的 Vnode 和旧的 oldVnode 进行对比
4. 通过 patch 函数一边比对一边给真实 DOM 打补丁或者创建 Vnode、移除 oldVnode 等

有什么不一样？

1. 真实 DOM 操作为一个属性一个属性去修改，开销较大。
2. 虚拟 DOM 直接修改整个 DOM 节点再替换真实 DOM

还有什么好处？

Vue 的虚拟 DOM 数据更新机制是异步更新队列，并不是数据变更马上更新 DOM，而是被推进一个数据更新异步队列统一更新。想要马上拿到 DOM 更新后 DOM 信息？有个 API 叫 Vue.nextTick

二、 Diff 算法

传统 Diff 算法

遍历两棵树中的每一个节点，每两个节点之间都要做一次比较。

比如 a->e 、a->d 、a->b、a->c、a->a

• 遍历完成的时间复杂度达到了 O(n^2)
• 对比完差异后还要计算最小转换方式，实现后复杂度来到了 O(n^3)

Vue 优化的 Diff 算法

Vue 的 diff 算法只会比较同层级的元素，不进行跨层级比较

三、 Vue 中的 Diff 算法实现

Vnode 分类

• EmptyVNode: 没有内容的注释节点
• TextVNode: 文本节点
• ElementVNode: 普通元素节点
• ComponentVNode: 组件节点
• CloneVNode: 克隆节点，可以是以上任意类型的节点，唯一的区别在于 isCloned 属性为 true

Patch 函数

patch 函数接收以下参数：

1. oldVnode：旧的虚拟节点
2. Vnode：新的虚拟节点
3. hydrating：是否要和真实 DOM 混合
4. removeOnly：特殊的 flag，用于 transition-group

处理流程大致分为以下步骤：

1. vnode 不存在，oldVnode 存在时，移除 oldVnode
2. vnode 存在，oldVnode 不存在时，创建 vnode
3. vnode 和 oldVnode 都存在时
   1. 如果 vnode 和 oldVnode 是同一个节点（通过 sameVnode 函数对比 后续详解），通过 patchVnode 进行后续比对工作
   2. 如果 vnode 和 oldVnode 不是同一个节点，那么根据 vnode 创建新的元素并挂载至 oldVnode 父元素下。如果组件根节点被替换，遍历更新父节点 element。然后移除旧节点。如果 oldVnode 是服务端渲染元素节点，需要用 hydrate 函数将虚拟 dom 和真是 dom 进行映射

源码如下，已写好注释便于阅读

return function patch(oldVnode, vnode, hydrating, removeOnly) {
  // 如果vnode不存在，但是oldVnode存在，移除oldVnode
  if (isUndef(vnode)) {
    if (isDef(oldVnode)) invokeDestroyHook(oldVnode);
    return;
  }

  let isInitialPatch = false;
  const insertedVnodeQueue = [];

  // 如果oldVnode不存在，但是vnode存在时，创建vnode
  if (isUndef(oldVnode)) {
    isInitialPatch = true;
    createElm(vnode, insertedVnodeQueue);
  } else {
    // 剩余情况为vnode和oldVnode都存在

    // 判断是否为真实DOM元素
    const isRealElement = isDef(oldVnode.nodeType);
    if (!isRealElement && sameVnode(oldVnode, vnode)) {
      // 如果vnode和oldVnode是同一个（通过sameVnode函数进行比对  后续详解）
      // 受用patchVnode函数进行后续比对工作 （函数后续详解）
      patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly);
    } else {
      // vnode和oldVnode不是同一个的情况
      if (isRealElement) {
        // 如果存在真实的节点，存在data-server-render属性
        if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
          // 当旧的Vnode是服务端渲染元素，hydrating记为true
          oldVnode.removeAttribute(SSR_ATTR);
          hydrating = true;
        }
        // 需要用hydrate函数将虚拟DOM和真实DOM进行映射
        if (isTrue(hydrating)) {
          // 需要合并到真实DOM上
          if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
            // 调用insert钩子
            invokeInsertHook(vnode, insertedVnodeQueue, true);
            return oldVnode;
          } else if (process.env.NODE_ENV !== 'production') {
            warn(
              'The client-side rendered virtual DOM tree is not matching ' +
                'server-rendered content. This is likely caused by incorrect ' +
                'HTML markup, for example nesting block-level elements inside ' +
                '<p>, or missing <tbody>. Bailing hydration and performing ' +
                'full client-side render.'
            );
          }
        }
        // 如果不是服务端渲染元素或者合并到真实DOM失败，则创建一个空的Vnode节点去替换它
        oldVnode = emptyNodeAt(oldVnode);
      }

      // 获取oldVnode父节点
      const oldElm = oldVnode.elm;
      const parentElm = nodeOps.parentNode(oldElm);

      // 根据vnode创建一个真实DOM节点并挂载至oldVnode的父节点下
      createElm(
        vnode,
        insertedVnodeQueue,
        oldElm._leaveCb ? null : parentElm,
        nodeOps.nextSibling(oldElm)
      );

      // 如果组件根节点被替换，遍历更新父节点Element
      if (isDef(vnode.parent)) {
        let ancestor = vnode.parent;
        const patchable = isPatchable(vnode);
        while (ancestor) {
          for (let i = 0; i < cbs.destroy.length; ++i) {
            cbs.destroy[i](ancestor);
          }
          ancestor.elm = vnode.elm;
          if (patchable) {
            for (let i = 0; i < cbs.create.length; ++i) {
              cbs.create[i](emptyNode, ancestor);
            }
            // #6513
            // invoke insert hooks that may have been merged by create hooks.
            // e.g. for directives that uses the "inserted" hook.
            const insert = ancestor.data.hook.insert;
            if (insert.merged) {
              // start at index 1 to avoid re-invoking component mounted hook
              for (let i = 1; i < insert.fns.length; i++) {
                insert.fns[i]();
              }
            }
          } else {
            registerRef(ancestor);
          }
          ancestor = ancestor.parent;
        }
      }

      // 销毁旧节点
      if (isDef(parentElm)) {
        // 移除老节点
        removeVnodes(parentElm, [oldVnode], 0, 0);
      } else if (isDef(oldVnode.tag)) {
        // 调用destroy钩子
        invokeDestroyHook(oldVnode);
      }
    }
  }
  // 调用insert钩子并返回节点
  invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch);
  return vnode.elm;
};

sameVnode 函数

Vue 怎么判断是不是同一个节点？流程如下：

1. 判断 Key 值是否一样
2. tag 的值是否一样
3. isComment，这个不用太关注。
4. 数据一样
5. sameInputType()，专门对表单输入项进行判断的：input 一样但是里面的 type 不一样算不同的 inputType

从这里可以看出 key 对 diff 算法的辅助作用，可以快速定位是否为同一个元素，必须保证唯一性。

如果你用的是 index 作为 key，每次打乱顺序 key 都会改变，导致这种判断失效，降低了 Diff 的效率。

因此，用好 key 也是 Vue 性能优化的一种方式。

• 源码如下：

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)))
  );
}

patchVnode 函数

前置条件 vnode 和 oldVnode 是同一个节点

执行流程：

1. 如果 oldVnode 和 vnode 引用一致，可以认为没有变化，return
2. 如果 oldVnode 的 isAsyncPlaceholder 属性为 true，跳过检查异步组件，return
3. 如果 oldVnode 跟 vnode 都是静态节点，且具有相同的 key，同时 vnode 是克隆节点或者 v-once 指令控制的节点时，只需要把 oldVnode.elm 和 oldVnode.child 都复制到 vnode 上，也不用再有其他操作，return
4. 如果 vnode 不是文本节或注释节点
   1. 如果 vnode 和 oldVnode 都有子节点并且两者子节点不一致时，就调用 updateChildren 更新子节点
   2. 如果只有 vnode 有自子节点，则调用 addVnodes 创建子节点
   3. 如果只有 oldVnode 有子节点，则调用 removeVnodes 把这些子节点都删除
   4. 如果 vnode 文本为 undefined，则清空 vnode.elm 文本
5. 如果 vnode 是文本节点但是和 oldVnode 文本内容不同，只需更新文本。

源代码如下，已写好注释便于阅读

function patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly) {
  // 如果新老节点引用一致，直接返回。
  if (oldVnode === vnode) {
    return;
  }

  const elm = (vnode.elm = oldVnode.elm);

  // 如果oldVnode的isAsyncPlaceholder属性为true，跳过检查异步组件
  if (isTrue(oldVnode.isAsyncPlaceholder)) {
    if (isDef(vnode.asyncFactory.resolved)) {
      hydrate(oldVnode.elm, vnode, insertedVnodeQueue);
    } else {
      vnode.isAsyncPlaceholder = true;
    }
    return;
  }

  // 如果新旧都是静态节点，vnode的key也相同
  // 新vnode是克隆所得或新vnode有 v-once属性
  // 则进行赋值，然后返回。vnode的componentInstance 保持不变
  if (
    isTrue(vnode.isStatic) &&
    isTrue(oldVnode.isStatic) &&
    vnode.key === oldVnode.key &&
    (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
  ) {
    vnode.componentInstance = oldVnode.componentInstance;
    return;
  }

  let i;
  const data = vnode.data;
  // 执行data.hook.prepatch 钩子
  if (isDef(data) && isDef((i = data.hook)) && isDef((i = i.prepatch))) {
    i(oldVnode, vnode);
  }

  // 获取子元素列表
  const oldCh = oldVnode.children;
  const ch = vnode.children;

  if (isDef(data) && isPatchable(vnode)) {
    // 遍历调用 cbs.update 钩子函数，更新oldVnode所有属性
    // 包括attrs、class、domProps、events、style、ref、directives
    for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
    // 执行data.hook.update 钩子
    if (isDef((i = data.hook)) && isDef((i = i.update))) i(oldVnode, vnode);
  }
  // Vnode 的 text选项为undefined
  if (isUndef(vnode.text)) {
    if (isDef(oldCh) && isDef(ch)) {
      //新老节点的children不同，执行updateChildren方法
      if (oldCh !== ch)
        updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly);
    } else if (isDef(ch)) {
      // oldVnode children不存在 执行 addVnodes方法
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '');
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
    } else if (isDef(oldCh)) {
      // vnode不存在执行removeVnodes方法
      removeVnodes(elm, oldCh, 0, oldCh.length - 1);
    } else if (isDef(oldVnode.text)) {
      // 新旧节点都是undefined，且老节点存在text，清空文本。
      nodeOps.setTextContent(elm, '');
    }
  } else if (oldVnode.text !== vnode.text) {
    // 新老节点文本内容不同，更新文本
    nodeOps.setTextContent(elm, vnode.text);
  }
  if (isDef(data)) {
    // 执行data.hook.postpatch钩子，至此 patch完成
    if (isDef((i = data.hook)) && isDef((i = i.postpatch))) i(oldVnode, vnode);
  }
}

updateChildren 函数

重点！！！

前置条件：vnode 和 oldVnode 的 children 不相等

整体的执行思路如下：

1. vnode 头对比 oldVnode 头

2. vnode 尾对比 oldVnode 尾

3. vnode 头对比 oldVnode 尾

4. vnode 尾对比 oldVnode 头

   • 只要符合一种情况就进行 patch，移动节点，移动下标等操作

5. 都不对再在 oldChild 中找一个 key 和 newStart 相同的节点

   • 找不到，新建一个。

   • 找到，获取这个节点，判断它和 newStartVnode 是不是同一个节点

     • 如果是相同节点，进行 patch 然后将这个节点插入到 oldStart 之前，newStart 下标继续移动
     • 如果不是相同节点，需要执行 createElm 创建新元素

为什么会有头对尾、尾对头的操作？

• 可以快速检测出 reverse 操作，加快 diff 效率。

源码如下 已写好注释便于阅读：

function updateChildren(
  parentElm,
  oldCh,
  newCh,
  insertedVnodeQueue,
  removeOnly
) {
  // 定义变量
  let oldStartIdx = 0; // 老节点Child头下标
  let newStartIdx = 0; // 新节点Child头下标
  let oldEndIdx = oldCh.length - 1; // 老节点Child尾下标
  let oldStartVnode = oldCh[0]; // 老节点Child头结点
  let oldEndVnode = oldCh[oldEndIdx]; // 老节点Child尾结点
  let newEndIdx = newCh.length - 1; // 新节点Child尾下标
  let newStartVnode = newCh[0]; // 新节点Child头结点
  let newEndVnode = newCh[newEndIdx]; // 新节点Child尾结点
  let oldKeyToIdx, idxInOld, vnodeToMove, refElm;

  // removeOnly is a special flag used only by <transition-group>
  // to ensure removed elements stay in correct relative positions
  // during leaving transitions
  const canMove = !removeOnly;

  if (process.env.NODE_ENV !== 'production') {
    checkDuplicateKeys(newCh);
  }

  // 定义循环
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 存在检测
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx];

      // 如果老结点Child头和新节点Child头是同一个节点
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      // patch差异
      patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
      // patch完成  移动节点位置  继续比对下一个节点
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];

      // 如果老结点Child尾和新节点Child尾是同一个节点
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      // patch差异
      patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
      // patch完成  移动节点位置 继续比对下一个节点
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];

      // 如果老结点Child头和新节点Child尾是同一个节点
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // Vnode moved right
      // patch差异
      patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
      // 把oldStart节点放到oldEnd节点后面
      canMove &&
        nodeOps.insertBefore(
          parentElm,
          oldStartVnode.elm,
          nodeOps.nextSibling(oldEndVnode.elm)
        );
      // patch完成  移动节点位置 继续比对下一个节点
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
      // 如果老结点Child尾和新节点Child头是同一个节点
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // Vnode moved left
      // patch差异
      patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
      // 把oldEnd节点放到oldStart节点前面
      canMove &&
        nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      // patch完成  移动节点位置 继续比对下一个节点
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      // 如果没有相同的Key，执行createElm方法创建元素
      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,
          insertedVnodeQueue,
          parentElm,
          oldStartVnode.elm,
          false,
          newCh,
          newStartIdx
        );
      } else {
        // 有相同的Key，判断这两个节点是否为sameNode
        vnodeToMove = oldCh[idxInOld];
        if (sameVnode(vnodeToMove, newStartVnode)) {
          // 如果是相同节点，进行patch  然后举将oldStart插入到oldStart之前，newStart下标继续移动
          patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue);
          oldCh[idxInOld] = undefined;
          canMove &&
            nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
        } else {
          // 如果不是相同节点，需要执行createElm创建新元素
          createElm(
            newStartVnode,
            insertedVnodeQueue,
            parentElm,
            oldStartVnode.elm,
            false,
            newCh,
            newStartIdx
          );
        }
      }
      newStartVnode = newCh[++newStartIdx];
    }
  }

  // oldStartIdx > oldEndIdx说明oldChild先遍历完，使用addVnode方法添加newStartIdx指向的节点到newEndIdx的节点
  if (oldStartIdx > oldEndIdx) {
    refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
    addVnodes(
      parentElm,
      refElm,
      newCh,
      newStartIdx,
      newEndIdx,
      insertedVnodeQueue
    );
  } else if (newStartIdx > newEndIdx) {
    // 如果newStartIdx > newEndIdx说明newChild先遍历完，remove掉oldChild未遍历完的节点
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
  }
}

四、总结

1. 正确使用 key，可以快速执行 sameVnode 比对，加速 Diff 效率，可以作为性能优化的一个点。
2. DIff 只做同级比较，使用 sameVnode 函数比对，文本节点直接替换文本内容。
3. 子元素列表的 Diff，进行头对头、尾对尾、头对尾等系列比较，直到遍历完两个元素的子元素列表。
   • 或一个列表先遍历完了，直接 addVnode / removeVnode。

掘金：前端 LeBron

知乎：前端 LeBron

持续分享技术博文，关注微信公众号 👇🏻