Vue2源码系列-9张图搞懂diff算法

vlambda
2021-09-12

Vue2源码系列-9张图搞懂diff算法

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

  // strictly internal
  ...
}

工具函数

开始前，简单介绍一下几个工具函数的作用

export function isUndef(v: any): boolean {
  return v === undefined || v === null;
}

判断变量是不是未定义，即是否等于 undefined 或 null

export function isDef(v: any): boolean {
  return v !== undefined && v !== null;
}

判断变量是否已定义，即是否不等于 undefined 与 null

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

通过对比 key、tag、inputType 是否一致，判断两个节点类型是否一致，是否可复用

function patchVnode(
  oldVnode,
  vnode,
  insertedVnodeQueue,
  ownerArray,
  index,
  removeOnly
) {
  // step 1
  if (oldVnode === vnode) {
    return;
  }

  // step 2
  if (isDef(vnode.elm) && isDef(ownerArray)) {
    vnode = ownerArray[index] = cloneVNode(vnode);
  }

  // step 3
  const elm = (vnode.elm = oldVnode.elm);
  if (isTrue(oldVnode.isAsyncPlaceholder)) {
    if (isDef(vnode.asyncFactory.resolved)) {
      hydrate(oldVnode.elm, vnode, insertedVnodeQueue);
    } else {
      vnode.isAsyncPlaceholder = true;
    }
    return;
  }

  // step 4
  if (
    isTrue(vnode.isStatic) &&
    isTrue(oldVnode.isStatic) &&
    vnode.key === oldVnode.key &&
    (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
  ) {
    vnode.componentInstance = oldVnode.componentInstance;
    return;
  }

  // step 5
  let i;
  const data = vnode.data;
  if (isDef(data) && isDef((i = data.hook)) && isDef((i = i.prepatch))) {
    i(oldVnode, vnode);
  }

  // step 6
  const oldCh = oldVnode.children;
  const ch = vnode.children;
  if (isDef(data) && isPatchable(vnode)) {
    for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode "i");
    if (isDef((i = data.hook)) && isDef((i = i.update))) i(oldVnode, vnode);
  }
  // step 7
  if (isUndef(vnode.text)) {
    if (isDef(oldCh) && isDef(ch)) {
      // step 7-1
      if (oldCh !== ch)
        updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly);
    } else if (isDef(ch)) {
      // step 7-2
      if (process.env.NODE_ENV !== "production") {
        checkDuplicateKeys(ch);
      }
      // step 7-3
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, "");
      // step 7-4
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
    } else if (isDef(oldCh)) {
      // step 7-5
      removeVnodes(oldCh, 0, oldCh.length - 1);
    } else if (isDef(oldVnode.text)) {
      // step 7-6
      nodeOps.setTextContent(elm, "");
    }
  } else if (oldVnode.text !== vnode.text) {
    // step 8
    nodeOps.setTextContent(elm, vnode.text);
  }
  // step 9
  if (isDef(data)) {
    if (isDef((i = data.hook)) && isDef((i = i.postpatch))) i(oldVnode, vnode);
  }
}

step 1：当新旧节点一致时，不做修改直接返回
step 2：如果虚拟节点的 elm 属性存在的话，就说明有被渲染过了，如果 ownerArray 存在，说明存在子节点，如果这两点到成立，那就克隆一个 vnode 节点
step 3：如果是异步占位，执行 hydrate 方法或者定义 isAsyncPlaceholder 为 true，然后退出
step 4：如果满足以下四个条件，那就赋值一下 componentInstance 属性之后直接 return，说明整个组件没有任何变化，还在之前的实例

vnode 是静态节点
oldVnode 是静态节点
key 属性都相等
vnode 属于克隆的虚拟 DOM 或者是只渲染一次的组件（v-once）

step 5：定义 data 常量，data 上一般是定义以下属性的，attrs 属性、on 事件、directives 指令、props、hook 钩子；这里调用 prepatch 的钩子函数
step 6：紧接着就是调用各种更新函数。

updateAttrs 更新 attr 属性
updateClass 更新 class 属性
updateDOMListeners 更新绑定事件属性
updateDOMProps 更新 props 属性
updateStyle 更新 style 属性
update 如果 ref 属性存在，根据 ref 属性进行更新
updateDrectives 更新 Drectives 属性

step 7：判断是否存在 text 文本

step 7-1：如果旧的 vnode 和新的 vnode 不相同就调用 updateChildren 函数更新
step 7-2：在非生产环境下检查是否有重复的 key，如果存在重复会提示
step 7-3：如果旧的 vnode 不存在子集，但是存在 text 属性，新的 vnode 存在子集，那就把 Text 清空
step 7-4：添加新的节点
step 7-5：移除子节点
step 7-6：设置显示文本为空

step 8：设置显示文本为最新的值
step 9：执行 data.hook.postpatch 钩子，表明 patch 完毕

diff 流程

Dom diff 发生在视图更新前，其目的是为了提高框架性能，我们这里讨论的是同级节点的 diff

// src/core/vdom/patch.js
function updateChildren(
  parentElm,
  oldCh,
  newCh,
  insertedVnodeQueue,
  removeOnly
) {
  // 初始化变量
  let oldStartIdx = 0;
  let oldEndIdx = oldCh.length - 1;
  let oldStartVnode = oldCh[0];
  let oldEndVnode = oldCh[oldEndIdx];

  let newStartIdx = 0;
  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)) {
      // step 1：当前 oldStartVnode 为 undefined 或 null
      oldStartVnode = oldCh[++oldStartIdx]; // oldStartIdx 向右移动
    } else if (isUndef(oldEndVnode)) {
      // step 2：当前 oldEndVnode 为 undefined 或 null
      oldEndVnode = oldCh[--oldEndIdx]; // oldEndIdx 向左移动
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      // step 3：oldStartVnode 与 newStartVnode 节点一致，拷贝其实例，若存在子节点继续处理其子节点
      patchVnode(
        oldStartVnode,
        newStartVnode,
        insertedVnodeQueue,
        newCh,
        newStartIdx
      );
      // oldStartIdx、newStartIdx 向右移动
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      // step 4：对比 oldEndVnode 与 newEndVnode 节点一致，拷贝其实例，若存在子节点则继续处理其子节点
      patchVnode(
        oldEndVnode,
        newEndVnode,
        insertedVnodeQueue,
        newCh,
        newEndIdx
      );
      // oldEndIdx、newEndIdx 向左移动
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // step 5：开始交叉对比 oldStartVnode、newEndVnode 
      // 若一致，拷贝其实例，若存在子节点则继续处理其子节点
      patchVnode(
        oldStartVnode,
        newEndVnode,
        insertedVnodeQueue,
        newCh,
        newEndIdx
      );
      // 如果可以移动
      // 则将 oldStartVnode 对应的真实节点右移到当前真实节点队列的末尾
      // （当前 oldEndVnode 的后一个位置）
      canMove &&
        nodeOps.insertBefore(
          parentElm,
          oldStartVnode.elm,
          nodeOps.nextSibling(oldEndVnode.elm)
        );
      oldStartVnode = oldCh[++oldStartIdx]; // oldStartIdx 向右移动
      newEndVnode = newCh[--newEndIdx]; // newEndIdx 向左移动
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // step 6：交叉对比 oldEndVnode、newStartVnode 
      // 一致，拷贝其实例，若存在子节点则继续处理其子节点
      patchVnode(
        oldEndVnode,
        newStartVnode,
        insertedVnodeQueue,
        newCh,
        newStartIdx
      );
      // 可以移动的话
      // 将 oldEndVnode 对应的真实节点左移到真实节点队列的首部
      //（当前 oldStartVnode 的前一个位置）
      canMove &&
        nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      if (isUndef(oldKeyToIdx))
        // step 7：遍历旧 VD 队列生成 key-id 的 Map
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      // step 8：
      // 优先判断新 VD 是否存在 key
      // 存在 key 则直接使用 oldKeyToIdx 查找是否有 key 相同的节点
      // 不存在则调用 findIdxInOld 遍历旧 VD 队列通过 sameVnode 查找类型一致的 VD 对应的下标
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
      if (isUndef(idxInOld)) {
        // step 9：在旧 VD 中找不到一致的节点，说明是新节点，直接创建
        createElm(
          newStartVnode,
          insertedVnodeQueue,
          parentElm,
          oldStartVnode.elm,
          false,
          newCh,
          newStartIdx
        );
      } else {
        // 存在 key 值一样或类型一致的节点
        vnodeToMove = oldCh[idxInOld];
        // 针对 key 值一样的节点，进一步判断节点类型是否一致
        if (sameVnode(vnodeToMove, newStartVnode)) {
          // step 10：key 一致且节点类型一致
          // 拷贝其实例，若存在子节点则继续处理其子节点
          patchVnode(
            vnodeToMove,
            newStartVnode,
            insertedVnodeQueue,
            newCh,
            newStartIdx
          );
          // 节点被使用，置为 undefined
          oldCh[idxInOld] = undefined;
          // 允许移动的话，则将找到的可复用旧节点移动到真实 Dom 队列的队首
          canMove &&
            nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
        } else {
          // step 11：key 一致，但是节点类型不一致，不可复用直接创建
          createElm(
            newStartVnode,
            insertedVnodeQueue,
            parentElm,
            oldStartVnode.elm,
            false,
            newCh,
            newStartIdx
          );
        }
      }
      newStartVnode = newCh[++newStartIdx]; // newStartIdx 向右移动
    }
  }
  // 循环结束
  // 若 oldStartIdx 大于 oldEndIdx，即 oldStartIdx 跑到 oldEndIdx 后面了
  // 说明旧 VD 队列遍历完了
  if (oldStartIdx > oldEndIdx) {
    refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
    // step 12：遍历余下的新 VD 并创建
    addVnodes(
      parentElm,
      refElm,
      newCh,
      newStartIdx,
      newEndIdx,
      insertedVnodeQueue
    );
  } else if (newStartIdx > newEndIdx) {
    // 若 newStartIdx 大于 newEndIdx
    // 则说明新 VD 遍历完了，而旧 VD 还有剩
    // step 13：删除余下的旧 VD
    removeVnodes(oldCh, oldStartIdx, oldEndIdx);
  }
}

图解

以下图为例，逐步讲解一下同级节点的 diff 过程

vue2_dom_diff_1.png

开始第一轮 diff

Vue2源码系列-9张图搞懂diff算法 — vue2_dom_diff_2.png

如上图，oldStartVnode 与 newStartVnode 节点类型一致，进入 step 3，复用节点 A，oldStartIdx、newStartIdx 向右移动

第二轮 diff 开始，如上图，oldEndVnode 与 newEndVnode 类型一致，进入 step 4，复用节点 G，oldEndIdx、newEndIdx 向左移动

之后开始第三轮 diff，oldStartVnode 与 newEndVnode 节点类型一致，进入 step 5，复用节点 B，节点 B 移动到节点 E（oldEndVnode）对应的真实节点之后，oldStartIdx 向右移动，newEndIdx 向左移动

如上图，第四轮 diff 开始，newStartVnode 与 oldEndVnode 节点类型一致，进入 step 6，复用节点 E，节点 E 移动到节点 C （oldStartVnode）对应的真实节点之前，newStartIdx 向右移动，oldEndIdx 向左移动

如上图，开始下一轮 diff，oldStartVnode、oldEndVnode、newStartVnode、newEndVnode 都没有类型一致的节点

进入 step 7：遍历还未处理的 Old VD 队列得到 oldKeyToIdx = {c:2, d:3, f:4}。
之后走 step 8：判断 newStartVnode 是否存在 key 值，这里 newStartVnode 的 key 值为 H，因此开始查找上一步的 oldKeyToIdx 中是否有 key 值相同的
找了一圈发现没有相同 key 值的，判断为新节点，走 step 9：创建节点 H，并插入到 oldStartVnode 节点之前（ createElm 方法中实现）
newStartIdx 向右移动

经过上一步，这时的 oldStartVnode 与 newStartVnode 节点类型又是一致的，如上图，继续走 step 3，oldStartIdx、newStartIdx 继续向右移动

vue2_dom_diff_8.png

这时，newStartIdx 与 newEndIdx 同时指向节点 D，优先判断 oldStartVnode 与 newStartVnode 为同一类型，因此继续走 step 3，oldStartIdx、newStartIdx 继续向右移动

vue2_dom_diff_9.png

到这里，newStartIdx 已经移到了 newEndIdx 后面了，即 newStartIdx 大于 newEndIdx，因此跳出 while 循环走 step 13：删除余下的 Old VD，即这里的 F 节点

至此，diff 完成

结语

由于个人订阅号不具备评论功能，如有其它意见，欢迎前往以下任一站点评论留言：

https://melonfield.club/column/detail/cvSEcoO1Jlp（个人独立开发运营网站）

https://juejin.cn/post/7003009909058961422

参考

https://github.com/vuejs/vue

vlambda博客
学习文章列表