关于vue.js:Vue2-diff-算法图解

看 Vue 2 的源代码曾经很久了，从用 flow 到现在应用 TypeScript，我每次都会关上它的源代码看一看，然而每次都只看到了 数据初始化 局部，也就是 beforeMount 的阶段，对于如何生成 VNode（Visual Dom Node，也能够间接称为 vdom）以及组件更新时如何比拟 VNode（diff）始终没有认真钻研，只晓得采纳了 双端 diff 算法，至于这个双端是怎么开始怎么完结的也始终没有去看过，所以这次趁写文章的机会认真钻研一下。如果内容有误，心愿大家能帮我指出，非常感谢~

在我的了解中，diff 指代的是 differences，即 新旧内容之间的区别计算 ；Vue 中的 diff 算法，则是通过一种 简略且高效 的伎俩疾速比照出 新旧 VNode 节点数组之间的区别 以便 以起码的 dom 操作来更新页面内容。

此时这里有两个必须的前提：

比照的是 VNode 数组
同时存在新旧两组 VNode 数组

所以它个别只产生在 数据更新造成页面内容须要更新时执行，即 renderWatcher.run()。

下面说了，diff 中比拟的是 VNode，而不是实在的 dom 节点，置信为什么会应用 VNode 大部分人都比较清楚，笔者就简略带过吧😝~

在 Vue 中应用 VNode 的起因大抵有两个方面：

VNode 作为框架设计者依据框架需要设计的 JavaScript 对象，自身属性绝对实在的 dom 节点要简略，并且操作时不须要进行 dom 查问，能够大幅优化计算时的性能耗费
在 VNode 到实在 dom 的这个渲染过程，能够依据不同平台（web、微信小程序）进行不同的解决，生成适配各平台的实在 dom 元素

在 diff 过程中会遍历新旧节点数据进行比照，所以应用 VNode 能带来很大的性能晋升。

在网页中，实在的 dom 节点都是以树的模式存在的，根节点都是 <html>，为了保障虚构节点能与实在 dom 节点统一，VNode 也一样采纳的是树形构造。

如果在组件更新时，须要比照全副 VNode 节点的话，新旧两组节点都须要进行 深度遍历 和比拟，会产生很大的性能开销；所以，Vue 中默认 同层级节点比拟 ，即 如果新旧 VNode 树的层级不同的话，多余层级的内容会间接新建或者舍弃，只在同层级进行 diff 操作。

一般来说，diff 操作个别产生在 v-for 循环或者有 v-if/v-else、component 这类 动静生成 的节点对象上（动态节点个别不会扭转，比照起来很快），并且这个过程是为了更新 dom，所以在源码中，这个过程对应的办法名是 updateChildren，位于 src/core/vdom/patch.ts 中。如下图：

这里回顾一下 Vue 组件实例的创立与更新过程：

首先是 beforeCreate 到 created 阶段，次要进行数据和状态以及一些根底事件、办法的解决

而后，会调用 $mount(vm.$options.el) 办法进入 Vnode 与 dom 的创立和挂载阶段，也就是 beforeMount 到 mounted 之间（组件更新时与这里相似）

原型上的 $mount 会在 platforms/web/runtime-with-compiler.ts 中进行一次重写，原始实现在 platforms/web/runtime/index.ts 中；在原始实现办法中，其实就是调用 mountComponent 办法执行 render；而在 web 下的 runtime-with-compiler 中则是减少了 模板字符串编译 模块，会对 options 中的的 template 进行一次解析和编译，转换成一个函数绑定到 options.render 中

mountComponent 函数外部就是定义了渲染办法 updateComponent = () => (vm._update(vm._render())，实例化一个具备 before 配置的 watcher 实例（即 renderWatcher），通过定义 watch 察看对象为刚刚定义的 updateComponent 办法来执行首次组件渲染与触发依赖收集，其中的 before 配置仅仅配置了触发 beforeMount/beforeUpdate 钩子函数的办法；这也是为什么在 beforeMount 阶段取不到实在 dom 节点与 beforeUpdate 阶段获取的是旧 dom 节点的起因

_update 办法的定义与 mountComponent 在同一文件下，其外围就是 读取组件实例中的 $el（旧 dom 节点）与 _vnode（旧 VNode）与 _render() 函数生成的 vnode 进行 patch 操作

patch 函数首先比照 是否具备旧节点 ，没有的话必定是新建的组件，间接进行创立和渲染；如果具备旧节点的话，则通过 patchVnode 进行新旧节点的比照， 并且如果新旧节点统一并且都具备 children 子节点，则进入 diff 的外围逻辑 —— updateChildren 子节点比照更新，这个办法也是咱们常说的 diff 算法

既然是比照新旧 VNode 数组，那么首先必定有比照的判断办法：sameNode(a, b)、新增节点的办法 addVnodes、移除节点的办法 removeVnodes，当然，即便 sameNode 判断了 VNode 统一之后，仍然会应用 patchVnode 对单个新旧 VNode 的内容进行深度比拟，确认外部数据是否须要更新。

这个办法就一个目标：比拟新旧节点是否雷同。

在这个办法中，首先比拟的就是 a 和 b 的 key 是否雷同，这也是为什么 Vue 在文档中注明了 v-for、v-if、v-else 等动静节点必须要设置 key 来标识节点唯一性，如果 key 存在且雷同，则只须要比拟外部是否产生了扭转，个别状况下能够缩小很多 dom 操作；而如果没有设置的话，则会间接销毁重建对应的节点元素。

而后会比拟是不是异步组件，这里会比拟他们的构造函数是不是统一。

而后会进入两种不同的状况比拟：

非异步组件：标签一样、都不是正文节点、都有数据、同类型文本输入框
异步组件：旧节点占位符和新节点的谬误提醒都为 undefined

函数整体过程如下

顾名思义，增加新的 VNode 节点。

该函数接管 6 个参数：parentElm 以后节点数组父元素、refElm 指定地位的元素、vnodes 新的虚构节点数组、startIdx 新节点数组的插入元素开始地位、endIdx 新节点数组的插入元素完结索引、insertedVnodeQueue 须要插入的虚构节点队列。

函数外部会 从 startIdx 开始遍历 vnodes 数组直到 endIdx 地位，而后调用 createElm 顺次在 refElm 之前创立和插入 vnodes[idx] 对应的元素。

当然，在这个 vnodes[idx] 中有可能会有 Component 组件，此时还会调用 createComponent 来创立对应的组件实例。

因为整个 VNode 和 dom 都是一个 树结构 ，所以在 同层级的比拟之后，还须要解决以后层级下更深层次的 VNode 和 dom 解决。

与 addVnodes 相同，该办法就是用来移除 VNode 节点的。

因为这个办法只是移除，所以只须要三个参数：vnodes 旧虚构节点数组、startIdx 开始索引、endIdx 完结索引。

函数外部会 从 startIdx 开始遍历 vnodes 数组直到 endIdx 地位，如果 vnodes[idx] 不为 undefined 的话，则会依据 tag 属性来辨别解决：

存在 tag，阐明是一个元素或者组件，须要 递归解决 vnodes[idx] 的内容，触发 remove hooks 与 destroy hooks
不存在 tag，阐明是一个 纯文本节点，间接从 dom 中移除该节点即可

节点比照的 理论残缺比照和 dom 更新 办法。

在这个办法中，次要蕴含九个次要的参数判断，并对应不同的解决逻辑：

新旧 VNode 全等，则阐明没有变动，间接退出
如果新的 VNode 具备实在的 dom 绑定，并且须要更新的节点汇合是一个数组的话，则拷贝以后的 VNode 到汇合的指定地位
如果旧节点是一个 异步组件并且还没有加载完结的话就间接退出 ，否则通过 hydrate 函数将新的 VNode 转化为实在的 dom 进行渲染；两种状况都会 退出该函数
如果新旧节点都是 动态节点 并且 key 相等，或者是 isOnce 指定的不更新节点，也会间接 复用旧节点的组件实例 并 退出函数
如果新的 VNode 节点具备 data 属性并且有配置 prepatch 钩子函数，则执行 prepatch(oldVnode, vnode) 告诉进入节点的比照阶段，个别这一步会配置性能优化
如果新的 VNode 具备 data 属性并且递归改节点的子组件实例的 vnode，仍然是可用标签的话，cbs 回调函数对象中配置的 update 钩子函数以及 data 中配置的 update 钩子函数
如果新的 VNode 不是文本节点的话，会进入外围比照阶段：
- 如果新旧节点都有 children 子节点，则进入 updateChildren 办法比照子节点
- 如果旧节点没有子节点的话，则间接创立 VNode 对应的新的子节点
- 如果新节点没有子节点的话，则移除旧的 VNode 子节点
- 如果都没有子节点的话，并且旧节点有文本内容配置，则清空以前的 text 文本
如果新的 VNode 具备 text 文本（是文本节点），则比拟新旧节点的文本内容是否统一，否则进行文本内容的更新
最初调用新节点的 data 中配置的 postpatch 钩子函数，告诉节点更新结束

简略来说，patchVnode 就是在 同一个节点更新阶段进行新内容与旧内容的比照，如果产生扭转则更新对应的内容；如果有子节点，则“递归”执行每个子节点的比拟和更新。

而 子节点数组的比拟和更新，则是 diff 的外围逻辑，也是面试时常常被提及的问题之一。

上面，就进入 updateChildren 办法的解析吧~

`updateChildren` diff 外围解析

首先，咱们先思考一下 以新数组为准比拟两个对象数组元素差别 有哪些办法？

一般来说，咱们能够通过 暴力手段间接遍历两个数组 来查找数组中每个元素的程序和差别，也就是 简略 diff 算法。

即 遍历新节点数组，在每次循环中再次遍历旧节点数组比照两个节点是否统一，通过比照后果确定新节点是新增还是移除还是挪动，整个过程中须要进行 m*n 次比拟，所以默认工夫复杂度是 On。

这种比拟形式在大量节点更新过程中是十分耗费性能的，所以 Vue 2 对其进行了优化，改为 双端比照算法 ，也就是 双端 diff。

顾名思义，双端就是 从两端开始别离向两头进行遍历比照 的算法。

在 双端 diff 中，分为 五种比拟状况：

新旧头相等
新旧尾相等
旧头等于新尾
旧尾等于新头
四者互不相等

其中，前四种属于 比拟现实的状况 ，而第五种才是 最简单的比照状况。

判断相等即 sameVnode(a, b) 等于 true

上面咱们通过一种预设状况来进行剖析。

为了尽量同时演示出以上五种状况，我预设了以下的新旧节点数组：

作为初始节点程序的旧节点数组 oldChildren，蕴含 1 – 7 共 7 个节点
作为乱序后的新节点数组 newChildren，也有 7 个节点，然而相比旧节点缩小了一个 vnode 3 并减少了一个 vnode 8

在进行比拟之前，首先须要 定义两组节点的双端索引：

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]

复制的源代码，其中 oldCh 在图中为 oldChildren，newCh 为 newChildren

而后，咱们定义 遍历比照操作的进行条件：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)

这里的进行条件是 只有新旧节点数组任意一个遍历完结，则立刻进行遍历。

此时节点状态如下：

为了保障新旧节点数组在比照时不会进行有效比照，会首先排除掉旧节点数组 起始局部与开端局部间断且值为 Undefined 的数据。

if (isUndef(oldStartVnode)) {oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {oldEndVnode = oldCh[--oldEndIdx]

当然咱们的例子中没有这种状况，能够疏忽。

此时相当于新旧节点数组的两个 起始索引 指向的节点是 基本一致的 ，那么此时会调用 patchVnode 对两个 vnode 进行深层比拟和 dom 更新，并且将 两个起始索引向后挪动。即：

if (sameVnode(oldStartVnode, newStartVnode)) {
  patchVnode(
    oldStartVnode,
    newStartVnode,
    insertedVnodeQueue,
    newCh,
    newStartIdx
  )
  oldStartVnode = oldCh[++oldStartIdx]
  newStartVnode = newCh[++newStartIdx]
}

这时的节点和索引变动如图所示：

与头结点相等相似，这种状况代表 新旧节点数组的最初一个节点基本一致 ，此时一样调用 patchVnode 比拟两个尾结点和更新 dom，而后将 两个开端索引向前挪动。

if (sameVnode(oldEndVnode, newEndVnode)) {
  patchVnode(
    oldEndVnode,
    newEndVnode,
    insertedVnodeQueue,
    newCh,
    newEndIdx
  )
  oldEndVnode = oldCh[--oldEndIdx]
  newEndVnode = newCh[--newEndIdx]
}

这时的节点和索引变动如图所示：

这里示意的是 旧节点数组以后起始索引指向的 vnode 与新节点数组以后开端索引指向的 vnode 基本一致，一样调用 patchVnode 对两个节点进行解决。

然而与下面两种有区别的中央在于：这种状况下会造成 节点的挪动 ，所以此时还会在 patchVnode 完结之后 通过 nodeOps.insertBefore 将 旧的头节点 从新插入到 以后旧的尾结点之后。

而后，会将 旧节点的起始索引后移、新节点的开端索引前移。

看到这里大家可能会有一个疑难，为什么这里挪动的是 旧的节点数组 ，这里因为 vnode 节点中有一个属性 elm，会指向该 vnode 对应的理论 dom 节点，所以这里挪动旧节点数组其实就是 侧面去挪动理论的 dom 节点程序 ；并且留神这里是 以后的尾结点，在索引扭转之后，这里不肯定就是原旧节点数组的最开端。

即：

if (sameVnode(oldStartVnode, newEndVnode)) {
  patchVnode(
    oldStartVnode,
    newEndVnode,
    insertedVnodeQueue,
    newCh,
    newEndIdx
  )
  canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
  oldStartVnode = oldCh[++oldStartIdx]
  newEndVnode = newCh[--newEndIdx]
}

此时状态如下：

这里与下面的旧头等于新尾相似，一样要波及到节点比照和挪动，只是调整的索引不同。此时 旧节点的开端索引前移、新节点的起始索引后移 ，当然了，这里的 dom 挪动对应的 vnode 操作是 将旧节点数组的开端索引对应的 vnode 插入到旧节点数组起始索引对应的 vnode 之前。

if (sameVnode(oldEndVnode, newStartVnode)) {
  patchVnode(
    oldEndVnode,
    newStartVnode,
    insertedVnodeQueue,
    newCh,
    newStartIdx
  )
  canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
  oldEndVnode = oldCh[--oldEndIdx]
  newStartVnode = newCh[++newStartIdx]
}

此时状态如下：

在以上状况都解决之后，就来到了四个节点相互都不相等的状况，这种状况也是 最简单的状况。

当通过了下面几种解决之后，此时的 索引与对应的 vnode 状态如下：

能够看到四个索引对应的 vnode 别离是：vnode 3、vnode 5、vnode 4、vnode 8，这几个必定是不一样的。

此时也就意味着 双端比照完结。

前面的节点比照则是 将旧节点数组残余的 vnode（oldStartIdx 到 oldEndIdx 之间的节点）进行一次遍历，生成由 vnode.key 作为键，idx 索引作为值的对象 oldKeyToIdx，而后 遍历新节点数组的残余 vnode（newStartIdx 到 newEndIdx 之间的节点），依据新的节点的 key 在 oldKeyToIdx 进行查找。此时的每个新节点的查找后果只有两种状况：

找到了对应的索引，那么会通过 sameVNode 对两个节点进行比照：
- 雷同节点，调用 patchVnode 进行深层比照和 dom 更新，将 oldKeyToIdx 中对应的索引 idxInOld 对应的节点插入到 oldStartIdx 对应的 vnode 之前；并且，这里会将 旧节点数组中 idxInOld 对应的元素设置为 undefined
- 不同节点，则调用 createElm 从新创立一个新的 dom 节点并将 新的 vnode 插入到对应的地位
没有找到对应的索引，则间接 createElm 创立新的 dom 节点并将新的 vnode 插入到对应地位

注：这里 只有找到了旧节点并且新旧节点一样才会将旧节点数组中 idxInOld 中的元素置为 undefined。

最初，会将 新节点数组的起始索引向后挪动。

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 {vnodeToMove = oldCh[idxInOld]
    if (sameVnode(vnodeToMove, newStartVnode)) {
      patchVnode(
        vnodeToMove,
        newStartVnode,
        insertedVnodeQueue,
        newCh,
        newStartIdx
      )
      oldCh[idxInOld] = undefined
      canMove &&
        nodeOps.insertBefore(
          parentElm,
          vnodeToMove.elm,
          oldStartVnode.elm
        )
    } else {
      // same key but different element. treat as new element
      createElm(
        newStartVnode,
        insertedVnodeQueue,
        parentElm,
        oldStartVnode.elm,
        false,
        newCh,
        newStartIdx
      )
    }
  }
  newStartVnode = newCh[++newStartIdx]
}

大抵逻辑如下图：

通过下面的解决之后，依据判断条件也不难看出，遍历完结之后新旧节点数组都刚好没有残余元素 是很难呈现的， 当且仅当遍历过程中每次新头尾节点总能和旧头尾节点中总能有两个新旧节点雷同时才会产生 ，只有有一个节点产生扭转或者程序产生大幅调整，最初 都会有一个节点数组起始索引和开端索引无奈闭合。

那么此时就须要对残余元素进行解决：

旧节点数组遍历完结、新节点数组仍有残余，则遍历新节点数组残余数据，别离创立节点并插入到旧开端索引对应节点之前
新节点数组遍历完结、旧节点数组仍有残余，则遍历旧节点数组残余数据，别离从节点数组和 dom 树中移除

即：

Vue 2 的 diff 算法绝对于简略 diff 算法来说，通过 双端比照与生成索引 map 两种形式 缩小了简略算法中的屡次循环操作，新旧数组均只须要进行一次遍历即可将所有节点进行比照。

其中双端比照会别离进行四次比照和挪动，性能不算最优解，所以 Vue 3 中引入了 最长递增子序列 的形式来 代替双端比照，而其余部分则仍然通过转为索引 map 的模式利用空间扩大来缩小工夫复杂度，从而更高的晋升计算性能。

当然本文的图中没有给出 vnode 对应的 elm 实在 dom 节点，两者的挪动关系可能会给大家带来误会，倡议配合《Vue.js 设计与实现》一起浏览。

整体流程如下：

关于vue.js:Vue2-diff-算法图解

前言

什么是 diff ?

为什么是 VNode ?

流程梳理

前置内容

sameNode(a, b)

addVnodes

removeVnodes

patchVnode

`updateChildren` diff 外围解析

双端 diff 算法

1. 预设新旧节点状态

2. 确认 vnode 存在才进行比照

3. 旧头等于新头

4. 旧尾等于新尾

5. 旧头等于新尾

6. 旧尾等于新头

7. 四者均不相等

残余未比拟元素解决

小结

前言

什么是 diff ?

为什么是 VNode ?

流程梳理

前置内容

sameNode(a, b)

addVnodes

removeVnodes

patchVnode

updateChildren diff 外围解析

双端 diff 算法

1. 预设新旧节点状态

2. 确认 vnode 存在才进行比照

3. 旧头等于新头

4. 旧尾等于新尾

5. 旧头等于新尾

6. 旧尾等于新头

7. 四者均不相等

残余未比拟元素解决

小结

`updateChildren` diff 外围解析