彻底理解vue的patch流程和diff算法

上一篇 《vue异步更新流程梳理》 梳理了数据从赋值到更新到视图的整体流程。但是最后的步骤 vm._update(vm._render()) 只是粗略的提了一嘴，现在就仔细的研究它内部的细节，搞清楚patch流程和diff原理是我们看源码的重中之重。

当更新数据的时候就会执行这个updateComponent方法，即方法里面的 vm._update(vm._render()) ，vm.render() 得到一个vnode,那么vm._update到底干什么? 进去看看

至此，无论是初始化还是更新都是靠patch来完成的 ，我们只需要看update流程就可以了。进入patch内部

patch函数主要接收oldVnode 与 vnode两个参数，其实就是新旧两棵虚拟树。这里经过判断条件 !isRealElement &&sameVnode(oldVnode, vnode)，不是真实节点 且是相同的vnode，进入patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)我们只要关注oldVnode, vnode这两个参数即可。

按照我们的例子，此时的oldVnode 与 vnode分别是

此处只列出关键属性tag, key, elm, children,elm，还有很多其他的属性没有列出。真实的虚拟树节点应该是如下图

我们能看出 两个vnode之间就是children[0]的不同：

追踪流程发现，我们进入oldVnode 与 vnode的children进行对比，在updateChildren函数中。

我们先不去看updateChildren的逻辑，继续看patchVnode这个函数其他的逻辑分支，得出 oldVnode 与 vnode的对比流程 ：

总结： patchVnode这个方法的主要作用是对比两个虚拟节点过程中去更新真实dom

接下来我们进入updateChildren流程，这是两个children的对比，看一下这个函数的定义

函数解读：

下面是两个数组进行diff的流程，也就是diff算法

diff解读：

新旧两个数组，都有双端指针，两端指针向中间靠拢，直到某个数组的两端指针相交则退出循环。

在这个过程中，会先判断是否有以下四种情况

如果不符合这4种情况，那就基于旧数组遍历一次，拿到每个节点的key和index,就是oldKeyToIdx： {key1: 0, key2: 1}这种情况。然后去新数组首个节点开始匹配，匹配到就进行递归patchVnode流程，没匹配到就进行创建新节点，插入到真实dom节点里面去。

当循环结束，此时要么是旧数组相交，要么是新数组相交，只有这两种情况：

至此diff流程结束。

两个虚拟树进行对比：

patch(oldVnode, vnode) ->patchVnode(oldVnode, vnode) ->updataChildren(oldCh, newCh)

在updataChildren(oldCh, newCh)的过程中也会进行 patchVnode(oldVnode, vnode) ，如此虚拟树深度优先递归diff完成。

更加详细直观的图看此链接

https://www.processon.com/view/5e809004e4b08e4e2447d02e

有同学问：能否详细说一下 diff 算法。

详细的说，请阅读这篇文章，有疑问的地方欢迎留言一起讨论。

因为 diff 算法是 vue2.x ， vue3.x 以及 react 中关键核心点，理解 diff 算法，更有助于理解各个框架本质。

说到「diff 算法」，不得不说「虚拟 Dom」，因为这两个息息相关。

比如：

等等

我们先来说说虚拟 Dom，就是通过 JS 模拟实现 DOM ，接下来难点就是如何判断旧对象和新对象之间的差异。

Dom 是多叉树结构，如果需要完整的对比两棵树的差异，那么算法的时间复杂度 O(n ^ 3)，这个复杂度很难让人接收，尤其在 n 很大的情况下，于是 React 团队优化了算法，实现了 O(n) 的复杂度来对比差异。

实现 O(n) 复杂度的关键就是只对比同层的节点，而不是跨层对比，这也是考虑到在实际业务中很少会去跨层的移动 DOM 元素。

虚拟 DOM 差异算法的步骤分为 2 步：

实际 diff 算法比较中，节点比较主要有 5 种规则的比较

部分源码 https://github.com/vuejs/vue/blob/8a219e3d4cfc580bbb3420344600801bd9473390/src/core/vdom/patch.js#L501 如下：

在 reconcileChildren 函数的入参中

diff 的两个主体是：oldFiber（current.child）和 newChildren（nextChildren，新的 ReactElement），它们是两个不一样的数据结构。

部分源码

很多时候手工优化 dom 确实会比 virtual dom 效率高，对于比较简单的 dom 结构用手工优化没有问题，但当页面结构很庞大，结构很复杂时，手工优化会花去大量时间，而且可维护性也不高，不能保证每个人都有手工优化的能力。至此，virtual dom 的解决方案应运而生。

virtual dom 是“解决过多的 *** 作 dom 影响性能”的一种解决方案。

virtual dom 很多时候都不是最优的 *** 作，但它具有普适性，在效率、可维护性之间达到平衡。

virutal dom 的意义：

vue2.x 的 diff 位于 patch.js 文件中，该算法来源于 snabbdom，复杂度为 O(n)。了解 diff 过程可以让我们更高效的使用框架。react 的 diff 其实和 vue 的 diff 大同小异。

最大特点：比较只会在同层级进行, 不会跨层级比较。

对比之前和之后：可能期望将 直接移动到

的后边，这是最优的 *** 作。

但是实际的 diff *** 作是：

vue 中也使用 diff 算法，有必要了解一下 Vue 是如何工作的。通过这个问题，我们可以很好的掌握，diff 算法在整个编译过程中，哪个环节，做了哪些 *** 作，然后使用 diff 算法后输出什么？

解释：

mount 函数主要是获取 template，然后进入 compileToFunctions 函数。

compileToFunction 函数主要是将 template 编译成 render 函数。首先读取缓存，没有缓存就调用 compile 方法拿到 render 函数的字符串形式，在通过 new Function 的方式生成 render 函数。

compile 函数将 template 编译成 render 函数的字符串形式。后面我们主要讲解 render

完成 render 方法生成后，会进入到 mount 进行 DOM 更新。该方法核心逻辑如下：

上面提到的 compile 就是将 template 编译成 render 函数的字符串形式。核心代码如下：

compile 这个函数主要有三个步骤组成：

分别输出一个包含

parse 函数：主要功能是 将 template 字符串解析成 AST（抽象语法树） 。前面定义的 ASTElement 的数据结构，parse 函数就是将 template 里的结构（指令，属性，标签） 转换为 AST 形式存进 ASTElement 中，最后解析生成 AST。

optimize 函数（src/compiler/optomizer.js）:主要功能是 标记静态节点 。后面 patch 过程中对比新旧 VNode 树形结构做优化。被标记为 static 的节点在后面的 diff 算法中会被直接忽略，不做详细比较。

generate 函数（src/compiler/codegen/index.js）:主要功能 根据 AST 结构拼接生成 render 函数的字符串 。

其中 genElement 函数（src/compiler/codgen/index.js）是根据 AST 的属性调用不同的方法生成字符串返回。

总之：

就是 compile 函数中三个核心步骤介绍，

patch 函数 就是新旧 VNode 对比的 diff 函数，主要是为了优化 dom，通过算法使 *** 作 dom 的行为降低到最低， diff 算法来源于 snabbdom，是 VDOM 思想的核心。snabbdom 的算法是为了 DOM *** 作跨级增删节点较少的这一目标进行优化， 它只会在同层级进行，不会跨层级比较。

总的来说：

在创建 VNode 就确定类型，以及在 mount/patch 的过程中采用位运算来判断一个 VNode 的类型，在这个优化的基础上再配合 Diff 算法，性能得到提升。

可以看一下 vue3.x 的源码：https://github.com/vuejs/vue/blob/8a219e3d4cfc580bbb3420344600801bd9473390/src/core/vdom/patch.js

对 oldFiber 和新的 ReactElement 节点的比对，将会生成新的 fiber 节点，同时标记上 effectTag，这些 fiber 会被连到 workInProgress 树中，作为新的 WIP 节点。树的结构因此被一点点地确定，而新的 workInProgress 节点也基本定型。在 diff 过后，workInProgress 节点的 beginWork 节点就完成了，接下来会进入 completeWork 阶段。

snabbdom 算法：https://github.com/snabbdom/snabbdom

定位：一个专注于简单性、模块化、强大功能和性能的虚拟 DOM 库。

snabbdom 中定义 Vnode 的类型(https://github.com/snabbdom/snabbdom/blob/27e9c4d5dca62b6dabf9ac23efb95f1b6045b2df/src/vnode.ts#L12)

init 函数的地址：

https://github.com/snabbdom/snabbdom/blob/27e9c4d5dca62b6dabf9ac23efb95f1b6045b2df/src/init.ts#L63

init() 函数接收一个模块数组 modules 和可选的 domApi 对象作为参数，返回一个函数，即 patch() 函数。

domApi 对象的接口包含了很多 DOM *** 作的方法。

源码：

https://github.com/snabbdom/snabbdom/blob/27e9c4d5dca62b6dabf9ac23efb95f1b6045b2df/src/init.ts#L367

源码：

https://github.com/snabbdom/snabbdom/blob/27e9c4d5dca62b6dabf9ac23efb95f1b6045b2df/src/h.ts#L33

h() 函数接收多种参数，其中必须有一个 sel 参数，作用是将节点内容挂载到该容器中，并返回一个新 VNode。

在 vue2.x 不是完全 snabbdom 算法，而是基于 vue 的场景进行了一些修改和优化，主要体现在判断 key 和 diff 部分。

1、在 snabbdom 中 通过 key 和 sel 就判断是否为同一节点，那么在 vue 中，增加了一些判断 在满足 key 相等的同时会判断，tag 名称是否一致，是否为注释节点，是否为异步节点，或者为 input 时候类型是否相同等。

https://github.com/vuejs/vue/blob/8a219e3d4cfc580bbb3420344600801bd9473390/src/core/vdom/patch.js#L35

2、diff 差异，patchVnode 是对比模版变化的函数，可能会用到 diff 也可能直接更新。

https://github.com/vuejs/vue/blob/8a219e3d4cfc580bbb3420344600801bd9473390/src/core/vdom/patch.js#L404

---