vlambda博客
学习文章列表

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

目录

一、工具函数

二、diff流程

三、图解

又来到了激动人心的 diff 环节,不喜欢源码的童鞋可以直接跳到图解了。

使用 Virtual Dom 的框架,一般的设计思路都是页面等于页面状态的映射,即 UI = render(state)。

在进行页面更新的时候真实 DOM 的改变可以借助 Virtual Dom 在内存中进行比较,也就是常说的 diff

在 Vue2 中的 Virtual Dom 就是 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

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

通过对比 keytaginputType 是否一致,判断两个节点类型是否一致,是否可复用

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

如上图,oldStartVnodenewStartVnode 节点类型一致,进入 step 3,复用节点 A,oldStartIdxnewStartIdx 向右移动

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

第二轮 diff 开始,如上图,oldEndVnodenewEndVnode 类型一致,进入 step 4,复用节点 G,oldEndIdxnewEndIdx 向左移动

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

之后开始第三轮 diff,oldStartVnodenewEndVnode 节点类型一致,进入 step 5复用节点 B,节点 B 移动到节点 E(oldEndVnode)对应的真实节点之后,oldStartIdx 向右移动,newEndIdx 向左移动

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

如上图,第四轮 diff 开始,newStartVnodeoldEndVnode 节点类型一致,进入 step 6复用节点 E,节点 E 移动到节点 C (oldStartVnode)对应的真实节点之前,newStartIdx 向右移动,oldEndIdx 向左移动

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

如上图,开始下一轮 diff,oldStartVnodeoldEndVnodenewStartVnodenewEndVnode 都没有类型一致的节点

  • 进入 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 向右移动
Vue2源码系列-9张图搞懂diff算法
vue2_dom_diff_7.png

经过上一步,这时的 oldStartVnodenewStartVnode 节点类型又是一致的,如上图,继续走 step 3oldStartIdxnewStartIdx 继续向右移动

vue2_dom_diff_8.png

这时,newStartIdxnewEndIdx 同时指向节点 D,优先判断 oldStartVnodenewStartVnode 为同一类型,因此继续走 step 3oldStartIdxnewStartIdx 继续向右移动

vue2_dom_diff_9.png

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

至此,diff 完成

结语

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

  1. https://melonfield.club/column/detail/cvSEcoO1Jlp(个人独立开发运营网站)
  2. https://juejin.cn/post/7003009909058961422

参考

  • https://github.com/vuejs/vue