看透 Vue3 重头戏之 diff 算法

发表于 2年以前 | 总阅读数：778 次

微信图片_20210407172754.jpg

前言

终于迎来了DOM diff流程的重头戏：diff算法，前面的流程只能算是附加项，重要的是各种节点是如何进行对比，然后进行更新。下面就对每一种节点的对比流程进行分析。

image.png

在vue3.2 初始化的时候做了什么？[1]文章的的末尾，提到了传入effect的回调函数和响应式数据之前产生一个依赖关系，等同于产生了一个watcher。当数据发生变化的时候，会以参数二的方法执行参数一，具体细节和调度器有关，以后再说，最终会进入componentUpdateFn函数中，我们就直接进入到更新阶段的componentUpdateFn。

`patch`之前的处理

image.png

在开始执行patch函数之前，会先执行一些生命周期钩子函数，有beforeUpdate和VNode的hook:beforeUpdate。

image.png

最主要的一点，如果是父组件数据变化而导致的子组件更新，会多执行一个东西，里面会进行更新props和slots以及换成新的VNode，做完这些之后可能会导致更新，需要在patch之前把它们执行。(PS：更新props和slots流程可以看看我前面的文章《Vue3.2 vDOM diff 流程之一：插槽的初始化和更新》[2]和《Vue3.2 vDOM diff流程分析之一：props和attrs的初始化和更新》[3])

image.png

做完这一些，就可以产生新的VNode，将新旧VNode传入patch开始进行对比，Suspense和Teleport的diff已经在前面的文章中说明，这里就不在提及。

对比元素类型节点

image.png

对比元素进入processElement，这次是进入更新流程，执行patchElement。n1是旧VNode，n2是新VNode

image.png

函数开头，需要重新通过旧节点的patchFlag重新确认新节点patchFlag，因为用户可以克隆由complie产生的VNode，或许可能添加一些新的props，比如cloneVNode(vnode, {class: 'cloneVNode'})，它将选择FULL_PROPS。

image.png

紧接着执行新的VNode自定义指令的beforeUpdate生命周期函数，如果在dev模式下且HMR正在更新，则放弃优化且把dynamicChildren清空，使用全量diff。这会影响后面diff，但是prod模式下一般都是优化模式，使用areChildrenSVG是判断新VNode是不是SVG。

image.png

这里分为优化模式和非优化模式，这里进入优化模式的条件是dynamicChildren不为空，非优化模式是optimized为true，但是这两个是互斥的，一个存在另一个肯定不存在。

优化模式下进行`diff`

image.png

进入到这个函数，他会遍历新VNode中dynamicChildren，并从旧的VNode的dynamicChildren取出按索引顺序一致的节点进行对比。

在这之前，先要找到parent node，也就这一大坨的三元运算符，不要慌张，逐个逐个条件分析，oldVNode.el是为了在异步组件的情况下确保元素节点的真实DOM要存在。

在oldVNode.el存在的情况下，并且符合以下三个条件中的其中一个：1. oldVNode的节点类型是Fragment、2.oldVNode和newVNode不是同一种元素(key值不一样也算)、3.oldVNode是组件，就组件而言，它可以包含任何东西。container就是oldVNode.el的parent。不然在其他的情况下，实际上没有父容器，因此传递一个block元素，避免parentNode，就是传递fallbackContainer(是n2的真实DOM)，

确认好container就和oldVNode与newVNode再次传递给patch，接下来就要根据newVNode的节点类型从而确定走哪个分支进行diff。

image.png

diff流程结束之后还需要做一件事，在dev模式下，如果parentComponent存在并且parentComponent启用 HMR，需要递归寻找或者是定位旧的el 以便在更新节点进行引用防止更新阶段会抛出el is null。优化模式分析完毕。

非优化模式下进行全量`diff`

image.png非优化模式下交给patchChildren处理，在diff之前先要拿到一些东西：n1、n2的Children和n2的shapeFlag。接下来的流程分为很多种情况，一一分析。

快速`diff`

首先根据n2的patchFlag判断能不能快速更新，也就是“靶向更新”，进入之后又分为两种情况，是否键控(是否绑定了key)，键控可以是完全键控也可以是混合键控(一部分带key，一部分不带key)，分别交给patchKeyedChildren和patchUnKeyedChildren处理。

不带有`key`的对比

image.png

由于带有key的对比有点复杂，我放的后面说，这里先看没有带key。没有带key的对比简单粗暴，因为不确保n1和n2都有children列表，没有就默认给一个空数组。需要注意这里获取长度，从新旧children列表两个列表长度中取出长度的最小的作为基准，接下来的对比最多只会对比到这个位置。具体用图解释。

image.png

如图所示，旧children列表长度是5，新children列表长度是3，取小的也就是3，代表在循环一对一对比中只会对比前三个，剩下会交给下面的流程。

image.png

剩下流程分为两种情况，在循环对比后，如果是新children列表比旧children列表长度长说明有新节点，就会去挂载新节点，反之说明有不需要的旧节点，就会去卸载。流程结束。

带`key`的对比

回到patchChildren中，我们看带有key是如何对比，将会结合图一步步分析。

image.png

这里先拿到一些东西，l2是新children列表的长度，e1是旧children列表中最后一位的索引，e2是新children列表最后一位的索引。i这里有特殊意义，代表对比的开始索引。带有key的对比主要有五个流程，

假如有如下新旧children列表，可以准确看出只有2移动了位置，下面就看经过五个流程是如何进行对比的。

image.png

1.流程一：对比开始位置

image.png

在这一阶段会遍历新旧children列表，只有新旧节点是用一种元素才会交给patch函数对比，每过一对新旧子节点，i就会加一，如果有一方遍历到最后一个就会结束或者是遍历到两个是不同元素。例子中，前面没有相同的节点，所以不会有任何操作

image.png

2.流程二：对比末尾位置

image.png

在这一阶段一样会遍历新旧children列表，和阶段一一样，新旧节点是同一种元素才会交给patch函数对比，不同的是从末尾开始对比子节点，每过一对子节点，新旧最大位置索引同时会减一。例子中，从末尾的3、4、5是相同元素可以排除。

image.png

走完前面的两个，说明新旧children列表中首尾的相同节点已经被处理了，就剩下中间的部分，接下来的三个流程是挂载列表中的新节点和卸载不需要的旧节点以及无序对比。

但这三个流程中只会执行其中一个或者都不执行，总共有三种情况：1. 只需要安装新节点、 2. 只需要卸载旧节点、 3. 无序。这和前面的讲到的全量diff和像，这就要看i了,如果i大于e1并且小于或者等于e2说明有新节点，执行流程三，如果i是大于e2说明有不需要的旧节点，执行流程四。都不符合执行流程五

3.流程三：挂载新节点(此流程不一定执行)

image.png

nextPos是用来确定新增节点的位置，一般到了这一阶段e2是没有处理的新节点列表的最大索引，要加一是因为vue新增节点的方式了，vue新增元素是通过insert，实现原理是insertBefore，所以这里会拿到将要插入元素的位置的后一个。具体看下面的示意图。(ps：红色框内是被处理过的)

image.png

在这个案例中，6是新增的节点，因为经过了流程一和二的处理，i变成了5，e2变成5，e2正好是节点6的索引，如果我们需要把它插入列表中，我们需要知道他的后一个节点是谁，以便做为瞄点，这就要加一后去新children列表中找。

image.png

但是还有第二种情况，如果新增的节点是新children列表中的最后一个，那么加一就会超出其长度，那么就会把parentAnchor作为瞄点，parentAnchor是当前列表的父容器中的最后一个节点，一般都是空字符串，(注意：这里是节点，不是元素节点)。例子中不符合，不会执行该流程

4.流程四：卸载不需要的旧节点(此流程不一定执行)

image.png

卸载旧节点的操作就比较简单了，每卸载一个i就加一，通过unmount方法进行卸载，实现原理是通过找到要卸载的节点的父节点，调用removeChildren进行卸载。前提是i大于e2但小于等于e1。例子中不符合，不会执行该流程

5.流程五：无序对比(此流程不一定执行)

如果到了流程五，说明children列表中有一部分是无序的，前面的流程无法处理，需要进行无序对比。这流程五分为三部分。

这第一部分是为了产生index和新children列表中的key的映射图，它会拿i作为新旧children列表的开始索引，当找到newChildren，准确来说是找到newChild身上的key，就会连同i一起保存进keyToNewIndexMap中。

code.png

这第二部分是循环旧节点列表以匹配需要更新的节点和删除不需要的节点，先提前创建一个数组(newIndexToOldIndexMap)，长度是还需要进行对比(toBePatched)的数量，作为新旧索引对应的存放(默认全部都是0)

开始循环旧children列表，当patched大于toBePatched时就都是卸载节点，但是一开始patched是0并不会大于，继续往下走，开始找newIndex，先从在前面保存的key:index的映射图中找，没找到就尝试在旧children列表中定位同一种类型没有key的节点的索引。还是没有就只能undefined。

最后，如果newIndex是undefined，说明旧节点没有对应的新节点直接卸载，不然，会修改newIndexToOldIndexMap中对应索引位置，如果newIndex小于新节点最大位置(maxNewIndexSoFar)，说明这个节点移动了，不然maxNewIndexSoFar就赋值成newIndex。过了这么多，终于可以传递给patch进行对比，patched也会加一。

这最后一部分，主要是为了移动节点和新增节点，如果有需要移动节点它会先根据新旧节点索引的映射产生一个最长递增子序列。而从最后开始循环也便于我们可以使用最后一个修补的节点作为瞄点，找出新节点中的最长递增子序列，移动不在这个范围内的节点，如果映射的oldIndex是0说明是新增节点，需要进行挂载。在例子中，就会移动1。

image.png

这流程五是最复杂的，其中不仅包含了挂载和卸载，还包含了移动节点，提高了对节点利用，到此patchKeyedChildren流程结束。

其他情况

回到patchChildren中，继续看patchFlag不存在如何进行对比，这要根据新旧节点的情况进行更新

code.png看起来复杂其实很简单，先说如果新节点是TEXT_CHILDREN,如果旧节点是ARRAY_CHILDREN，会先卸载所有旧节点，再挂载新节点，旧节点也是TEXT_CHILDREN需要和新节点对比确认不同后再更新。

如果两个都是ARRAY_CHILDREN，需要走patchKeyedChldren，但也有可能只是卸掉旧的并没有新节点，卸载所有旧节点。

当旧节点是TEXT_CHILDREN新节点是ARRAY_CHILDREN时，会先将其变为空字符串，再进行挂载新节点。

后面对比props的部分，在我之前的文章Vue3.2 vDOM diff流程分析之一：props和attrs的初始化和更新[4]中讲过，感兴趣可以去看看，到这里对比元素的流程结束。

对比组件类型节点

image.png

在patch函数中，对比组件分支执行的是processComponent,最终会执行updateComponent，组件更新新的会继承旧的实例。

更新前他会执行shouldUpdateComponent判断是否需要更新。但是属实是情况太多，这里就不一一列举了，具体可以到源码中查看shouldUpdateComponent[5]函数。

image.png

进入需要更新的流程，他是会优先处理Suspense(存在asyncDep且asyncResolved不存在)，不是Suspense就正常更新，把新VNode(instance.next)赋值成n2，如果当前组件已经在更新队列中，请将它移除，避免重复更新同一组件，然后就可以调用实例上的更新器进行更新了。

image.png

注意这里的instance.next,如果这个存在，在调用componentUpdateFn中会调用updateComponentPreRender函数，这是因为组件数据变化导致其子组件更新，所以需要去更新实例中的VNode以及props和slots，顺带把更新props导致的更新执行了。如果只是单纯的数据变化，没有影响到子组件，那next就会是原本实例上的VNode。

后面的就是正常调用生命周期函数和钩子函数，产生新的VNode和旧的VNode一起交给patch进行对比，后面的就要看组件里面是啥东西然后走哪个流程。

对比文本类型、注释类型、静态节点类型节点

文本类型

image.png

文本类型节点的更新在processText中，会先进行对比，不同才会更新文本

注释类型

image.png

注释节点的更新在processCommentNode中，但是因为不支持动态更新注释，所以是直接拿以前的。

静态节点类型

image.png

静态节点的更新执行的是patchStaticNode，因为vue会把静态节点进行序列化成字符串所以可以直接进行字符串对比，相同只会赋值以前的el和anchor,不同会先循环移除旧的，连带着anchor一起移除，再挂载新的静态节点。

总结

本篇文章分析了vue中diff算法的处理，清楚vue中diff算法的处理流程，知道每一个节点对比如何进行，如何书写模板可以进行最优的对比、复用节点，从而提高性能，在列表对比中，优化模式只会对比dynmaicChildren中的节点，也就是动态节点，非优化模式下，虽然说是全量diff但是可以复用节点也不会损耗太多性能。

好了，到了文章的最后，还是希望各位哥哥姐姐能指导指导。有说错或者遗漏的欢迎在评论区讲解，谢谢。