今天来分享一下 Vue 中经常听闻的 Diff 算法相关知识.
可能还有一些朋友不太了解 Diff 算法是什么、有什么用，我们接下来先大致介绍一下 diff 算法在 Vue3 中的作用等相关知识，方便没有基础的同学能够尽量的看懂这篇文章.
如果你已经大致知道了相关前置知识，那就直接跳过这部分前往下面文章看一看 patch 最小量化更新 (即 diff 算法) 的历程吧
本篇文章尽可能的减少代码，更多的图片动画演示，我们从一张张思路图来探讨研究前辈们的智慧结晶.
介绍#
在 Vue 中采用的虚拟 VNode 进行对比然后进行挂载 / 更新 / 卸载操作，其中最为主要的就是更新操作，更新操作的效率会影响到渲染页面更新量，越接近于编译时框架所带来的更新量性能就会越高，为了尽量让 Vue 这个编译时 + 运行时的框架带来的更新量最小化，于是就带来了Diff 算法用于检测两颗新旧节点树之间最小的差异，以带来最少的更新量，提升页面性能.
目前在《Vue.js 设计与实现》中Diff 算法仅限在新旧节点都存在key, 并未提及在无 key时该如何减少 patch 的最小量化，key可用作元素的唯一标识用作新旧节点对比.
接下来我们将随着一步步的代码与思路的演进，领略从更新操作中的性能提升，从简单粗暴到复杂优雅
直接#
最为简单粗暴的做法就是我们根本不去关注新旧节点中存不存在差异，直接把旧节点全部卸载，把新节点重新挂载到容器内，这样就完成了更新的操作。这种方式甚至不需要被称为Diff了，因为根本不关心差异化，无脑卸载挂载即可。如下图可见在这样直接全卸载然后全挂载的操作，直接粗暴但是简单，但性能距离命令式代码差距过大，有不需要卸载只需要简单移动节点位置即可达成目标的节点处理方法却仍然进行卸载重新挂载操作，于是开启了我们对于此类算法的思考，为了更高的性能而进行苦思冥想的追寻之旅～
图 0-1 全卸载 & 全挂载
简单#
缘起#
相较于全卸载 & 全挂载这样粗暴的流程，我们首先可以很清楚的看出一个问题，对于可复用节点的衡量. 我们可以观测下图 1-1新旧两组节点
图 1-1 新旧两颗树的对比图
我们可以很明显发现，有部分节点只需要非常简单移动，有部分节点只需要更新文本内容差异，有的只需要把多余的旧节点卸载或者把多出来的新节点进行挂载操作即可.
复用与 key#
那么我们该怎么去对比新旧两颗树的节点是否相同呢？苦思冥想中，Vue 给了我们答案，为节点新增属性key当作节点的唯一值，相当于节点的身份证一样的存在.
图 1-2 有 key 与无 key 时节点比较情况
这样我们在比较节点时才有了依据才可以避免无脑全卸载 & 全挂载这样的操作，进而真正开始diff算法的探究过程中.
现在我们已经主观层规定了这种节点列表中的每个节点都有着一个唯一key, 那么我们下一步就可以开始处理dom节点的复用.
接下来我们重新观察一下图 1-1这对新旧节点树，看一看我们都需要怎么做才能尽可能少的操作 dom
我们发现这对新旧节点树中发现了以下几种情况:
- p-1、p-2、p-3、p-4 节点可与旧节点进行复用
- p-5 节点需要卸载
- p-6 节点需要挂载
- 节点有可能需要进行节点位置移动
接下来我们要做的其实很简单，大致克对应着上面的情况进行处理:
- 根据新树去查看旧树上是否有key 同值的节点，如果有则先进行一次打补丁操作，
- 如果新书的某个节点在旧树中找不到可复用的节点则说明这是一个需要挂载的新节点
- 如果旧树的某个节点在新树中找不到相应的节点 (即没有被复用) 则说明这是一个需要卸载的旧节点
- 对需要移动的节点进行移动
/**
* 简单Diff算法
* @param oldVNode 旧节点列表
* @param vNode 新节点列表
* @param container 节点列表挂载容器
*/
function simpleDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
for (let i = 0; i < vNode.length; i++) {
let findLock = false; // 标识这个新节点是否找到可复用的旧节点
for (let j = 0; j < oldVNode.length; j++) {
if ((typeof vNode[i].key !== "undefined") && vNode[i].key === oldVNode[j].key) { // 根据唯一key来寻找可复用的元素
findLock = true; // 找到可复用节点
// 这一步会同步old节点的element至new节点的element属性
patch(oldVNode[j], vNode[i], container);
// ??? 节点是否需要移动, 应该移动到哪里
break;
};
}
if (!findLock) {
// 执行到这里说明没有找到可复用的节点, 需要新建节点并进行插入操作
// patch(null, vNode[i], container, ???); 插入元素锚地的位置
}
};
// 遍历旧树, 查找到需要卸载的节点进行卸载操作
oldVNode.forEach(oldElement => {
if (!vNode.find(newElement => newElement.key === oldElement.key)) {
unMountElement(oldElement);
};
});
};
这几个步骤处理中难点就是节点移动，该怎么移动，移动到哪个节点前面？新节点挂载该挂载哪个位置？着同样也是 diff 过程中非常重要的一步
移动#
接下来我们结合图 1-2观察一下我们究竟该怎么去移动 / 挂载元素。如下图图 1-3
图 1-3 新旧虚拟节点与真实节点
是否感觉出来有点杂乱无章呢，这里的移动元素锚点位置究竟是哪个呢？，我们不妨回过头去逆向思维思考一下，去考虑一下在什么情况下节点不需要移动呢，答案就是新旧两组节点列表的顺序保持不变，保持不变则代表着每次新节点列表前往旧节点列表中去找到可复用节点时的旧节点的索引是呈现一个递增的趋势.
例如结合图 1-2就能很明显看出找到的旧节点索引趋势为 [0, 1, 2, 3, 4].
我们在结合图 1-3来看找到的旧节点索引趋势为 [3, 2, -1, 0, 1], (此处我们暂时对新挂载的节点找到的旧节点索引值表示为 **-1**, 但在实际的移动过程中，新挂载的节点根本不会进入到趋势计算中), 好了，回到我们找到的旧节点索引趋势来看，能够看出 p-4 在旧节点中索引为 3, p-3 在旧节点索引为 2, 这我们可以得到一个结论，说明在新节点中 p-3 节点是需要移动的，p-3 的真实元素位置是位于 p-4 真实元素位置之后的，以此类推，在这个例子中所有新的节点都在 p-4 的后面，我们都是以 p-4 的旧索引位为基准进行比对，但在更大的例子中就需要我们不断的去更新基准 (递增趋势的截止处索引), 去不断的判定这个节点是否需要移动.
为了更加方便、直接、全面、快速的带着大家感受这个移动过程，我们可以看下这个代码执行动画演示图 1-4.
图 1-4 节点移动执行全流程动画演示图
/**
* 简单Diff算法
* @param oldVNode 旧节点列表
* @param vNode 新节点列表
* @param container 节点列表挂载容器
*/
function simpleDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
let lastMaxIndex = 0; // 当前最大旧索引值
for (let i = 0; i < vNode.length; i++) {
let findLock = false;
for (let j = 0; j < oldVNode.length; j++) {
if ((typeof vNode[i].key !== "undefined") && vNode[i].key === oldVNode[j].key) {
// ***省略patch代码***
if (j < lastMaxIndex) { // 需要移动
const prevElement = vNode[i - 1];
if (prevElement) {
insertElement(container, oldVNode[j]._element, prevElement._element?.nextSibling ?? null);
};
} else {
lastMaxIndex = j;
}
break;
};
}
if (!findLock) {
// 执行到这里说明没有找到可复用的节点, 需要新建节点并进行插入操作, 锚点位同上的逻辑一致
const prevElement = vNode[i - 1];
patch(null, vNode[i], container, prevElement?._element?.nextSibling ?? null);
}
};
// ***省略节点卸载代码***
};
双端#
缘起#
在简单 diff 算法中，我们有时候会在一些例子中有发现更加快捷的步骤，如下图
图 2-1 特殊的例子
我们发现如果按照简单 diff 算法的执行流程，需要先把 p-1 移动至 p-3 元素后方，然后在把 p-2 移动至 p-1 元素后方，但是我们人眼来观察这对新旧节点列表，发现明明我只需要把 p-3 移动至 p-1 节点的前方即可，如图 2-2 明明一步就能解决的方式却在 diff 算法中需要两次移动节点.
图 2-2 在一些情况下移动 Dom 次数更少的处理
思想#
现在可优化点出来了，我们就要想着该怎么去优化了，在双端 diff 算法思想中，分别为新旧节点列表都建立相应的头尾索引，并分别将 4 个索引处指向的 VNode 进行比对并不断的移动相应的索引。如图 2-3
图 2-3 双端索引与对比指示图
会发现在一些情况下确实能够通过这四次的对比然后移动相应的索引，能够在头尾处找到key 同值需要处理的节点。例如图 2-3的例子，我们先不去思考如果 (p-3<=>p-1、p-2<=>p-3、p-3<=>p-3、p-2<=>p-1) 这四次对比没找到同key的情况，这种情况我们后续在进行处理，我们先思考加入遇见了这种情况，我们该怎么去移动节点？
移动#
-
newVNode[newStartIndex].key === oldVNode[oldStartIndex].key当相等的情况下，意味着节点无需移动，只需要进行 patch 补丁操作即可，然后把
newStartIndex与oldStartIndex向后移动即可 -
newVNode[newEndIndex].key === oldVNode[oldEndIndex].key当相等的情况下，意味着节点无需移动，只需要进行 patch 补丁操作即可，然后把
newEndIndex与oldEndIndex向前移动即可 -
newVNode[newEndIndex].key === oldVNode[oldStartIndex].key原先位于旧节点列表头索引位置，现在要移动至新节点列表尾索引位置，说明在这次对比中原本在旧节点列表中头部现在在新节点列表中的尾部，表明节点需要移动，把节点移动至
oldVNode[oldEndIndex]的下一位即可，然后把参与到这轮使用的索引进行正确的更新，newEndIndex向前移动，oldStartIndex向后移动. -
newVNode[newStartIndex].key === oldVNode[oldEndIndex].key原先位于旧节点列表尾索引位置，现在要移动至新节点列表的头索引位置，说明在此次对比中原本在旧节点列表中尾部的元素现在在新节点列表中的头部，表明节点需要移动，把节点移动至
oldVNode[oldStartIndex]的上一位即可，即头部，然后正确更新参与索引，newStartIndex向后移动，oldEndIndex向前移动.
按照图 2-3的例子中，显然这四种条件就足以，但是我们可以看图 2-4这个例子中，发现可能发生这四种情况都不满足，那该怎么进行处理呢？
图 2-4 特殊的例子
很明显，我们只需要从根据newVNode[newStartIndex]为基底，并尝试在 oldVNode 中找到key同值节点，如果找到则进行patch然后把newStartIndex索引向后移动，oldVNode 中的同key到节点变为undefined, 此处我们强行从 oldVNode 中再去找一遍，然后把找到的进行undefined处理，以避免后续在索引到这个节点的时候重复处理造成预期之外的情况。不过同样也增加我们在前面的四重判断体前置增加条件，避免掉oldVNode[oldStartIndex]或者oldVNode[oldEndIndex]为undefined情况，并及时根据情况进行移动oldStartIndex或者oldEndIndex的索引位，当然既然存在着找到同key点情况，也就存在着找不到的情况，找不到就意味着在这个newVNode[newStartIndex]是一个新节点，需要进行挂载操作.
现在我们已经把情况判定完毕了，以及处理了特殊的情况，但是在一些更特殊的例子，上方节点量不同的情况下会发生一边已经oldStartIndex > oldEndIndex终止掉循环了，或者一边newStartIndex > newEndIndex终止掉循环了，造成节点多的那一方出现节点未卸载 / 未挂载情况，我们发现这种情况始终是单边的，于是我们可以总结出一定的规律，为while循环的终止做出兜底.
同简单 diff 算法一样，在这里我同样会给到一个代码执行动画演示，帮助我们可视化理解双端 Diff, 参见下图 2-5
图 2-5 双端 diff 执行流程示意图
/**
* 双端diff算法
* @param oldVNode
* @param vNode
* @param container
*/
function doubleEndedDiff(oldVNode: (VNode | undefined)[], vNode: VNode[], container: ContainerElement) {
let oldStartIndex = 0;
let newStartIndex = 0;
let oldEndIndex = oldVNode.length - 1;
let newEndIndex = vNode.length - 1;
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
const oldStartVNode = oldVNode[oldStartIndex];
const oldEndVNode = oldVNode[oldEndIndex];
const newStartVNode = vNode[newStartIndex];
const newEndVNode = vNode[newEndIndex];
// 预防旧节点被操作为undefined情况
if (!oldStartVNode) {
oldStartIndex++;
continue;
}
if (!oldEndVNode) {
oldEndIndex--;
continue;
}
// 四种对比移动节点情况
if (oldStartVNode.key === newStartVNode.key) {
patch(oldStartVNode, newStartVNode, container)
oldStartIndex++;
newStartIndex++;
} else if (oldEndVNode.key === newEndVNode.key) {
patch(oldEndVNode, newEndVNode, container);
oldEndIndex--;
newEndIndex--;
} else if (oldStartVNode.key === newEndVNode.key) {
patch(oldStartVNode, newEndVNode, container);
insertElement(container, oldStartVNode._element, oldEndVNode._element?.nextSibling);
oldStartIndex++;
newEndIndex--;
} else if (oldEndVNode.key === newStartVNode.key) {
// 打补丁
patch(oldEndVNode, newStartVNode, container);
insertElement(container, oldEndVNode._element, oldStartVNode._element);
// 移动索引
oldEndIndex--;
newStartIndex++;
} else {
// 找到旧节点中与新节点相同key的节点
const findOldIndex = oldVNode.findIndex(node => node && node.key === newStartVNode.key);
if (findOldIndex > 0) {
// 打补丁
patch(oldVNode[findOldIndex]!, newStartVNode, container);
insertElement(container, oldVNode[findOldIndex]!._element, oldStartVNode._element);
oldVNode[findOldIndex] = undefined;
newStartIndex ++;
} else { // 说明这个newStartVNode是一个新增节点
patch(null, newStartVNode, container, oldStartVNode._element);
newStartIndex++;
}
}
}
// 旧节点已经循环完毕, 但新节点中有剩余, 需要把这些剩余的新节点进行挂载操作
if (oldEndIndex < oldStartIndex && newStartIndex <= newEndIndex) {
for (let i = newStartIndex; i <= newEndIndex; i++) {
patch(null, vNode[i], container, vNode[i - 1]?._element?.nextSibling);
}
} else if(newEndIndex < newStartIndex && oldStartIndex <= oldEndIndex) {
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
oldVNode[i] && unMountElement(oldVNode[i]!);
}
}
}
快速#
缘起#
使用双端 diff 算法时的 vue 在进行js-framework-benchmark进行跑分实测时注意到，ivi与inferno所采用的快速 diff快速性能会稍优于使用双端 diff的 vue, 有必要去了解借鉴其思路与经验，为提高性能而努力.
图 3-1 ivi,inferno,vue,react 实测性能对比
杂谈一些八卦，之前听过一些人吐槽 react 性能慢是因为 react 内部对虚拟 node 的数据结构为一个自行设计的类单链表结构，造成 react 是不能使用双端 diff 这样的算法的，只能单向寻找 diff, 有的开发者借鉴 react 的思想，摒弃其自行设计的数据结构，采用了双端 diff 后性能有明显提升。例如Unis
思想#
有这样一种场景，元素的前置节点与后置节点相同，只有中间部分元素不尽相同，这时候有个十分类似的思想算法处理叫 **“纯文本 diff”**, 该算法主要用在纯文本上，如下图 3-1.
图 3-1 纯文本 diff 思想示例
我们发现，在这两段新旧文字中，只有中间的div发生了变化，边为了文字input. 那么这种思想是否能够帮助我们处理新旧节点列表呢？我们观察下面这个例子如图 3-2
图 3-2 应用纯文本 diff 思想的例子
我们发现好像优先去处理相同的前置节点 (即newVNode[startIndex] === oldVNode[startIndex]) 与相同的后置节点 (newVNode[endIndex] === oldVNode[endIndex]), 然后在单独去处理中间杂乱的节点似乎是一个好的选择，这样可以避免在遇见只需要更新操作的节点时却还需要考量当前新节点是否需要移动等.
但是又思考了思考，貌似只从这个思想优化点方面就能提升那么多的性能么，感觉有点不可置信呀。当然，在快递 diff 算法中还引进的了一个概念最长递增子序列, 引进该概念的作用是为了更加高效的处理除了相同的前后置节点外的其余节点，帮助其进行移动等操作，参见下图 3-3
图 3-3 快速 diff 算法节点移动执行示意图
移动#
我们看完上图后会发现有个关键点就是source这个怎么来？source用于记录新节点在旧节点中相应的索引，我们通常或通过双重for循环达到这样的效果形成source, 但是这样有个缺点就是时间复杂度高, 达到了O(n^2), 数据量越大表明耗时越是双倍变多.
const newVNodePatchCount = newEndIndex - startIndex + 1;
const source = new Array(newVNodePatchCount).fill(-1); // 新旧节点位置映射
let moved = false;
let pos = 0;
// 双层for时间复杂度高, O(n^2)
for (let i = startIndex; i <= newEndIndex; i++) {
for (let j = startIndex; j <= oldEndIndex; j++) {
if (vNode[i].key === oldVNode[j].key) { // 找到新旧节点映射点
patch(oldVNode[j], vNode[i], container);
source[i - startIndex] = j;
if (j < pos) { // 定位在新节点树中的最大索引处, 可用来确定是否需要移动节点这一步
moved = true;
} else {
pos = j;
}
break;
}
}
}
// 循环旧节点列表进行卸载没被复用的节点
oldVNode.forEach(oldElement => {
if (!vNode.find(newElement => newElement.key === oldElement.key)) {
unMountElement(oldElement);
};
});
时间复杂度是算法中必须掌握的一项基础，用于大致表示一段算法的耗时。与其相应经常结伴出现的就是空间复杂度, 空间复杂度主要用于大致表示一段算法所需要 / 消耗的内存大小，在现在的时代内存容量完全能够支撑，所以在为了降低时间复杂度时经常的做法就是空间换时间, 意思是用更多的内存以降低时间复杂度.
我们回过头再看上面这段代码，有没有似曾相识的感觉，yes, 就是简单 Diff 算法, 除了没有移动节点和新增节点的功能，其他的都基本一致，接下来我们观察下面这段优化后代码.
const newVNodePatchCount = newEndIndex - startIndex + 1;
const source = new Array(newVNodePatchCount).fill(-1); // 新旧节点位置映射
let moved = false;
let pos = 0;
const keySourceMap: Record<number | string | symbol, number> = {};
for (let i = startIndex; i <= newEndIndex; i++) {
keySourceMap[vNode[i].key!] = i; // 利用唯一key+数组存留来关联上新旧两颗树的差异对比
}
for (let i = startIndex; i <= oldEndIndex; i++) {
const sourceKey = keySourceMap[oldVNode[i].key!];
if (sourceKey !== undefined) { // 说明有可复用节点
patch(oldVNode[i], vNode[sourceKey], container); // 打补丁操作
source[sourceKey - startIndex] = i; // 新旧节点同key映射点
if (sourceKey < pos) { // 定位在新节点树中的最大索引处, 可用来确定是否需要移动节点这一步
moved = true;
} else {
pos = sourceKey;
}
} else { // 没找到说明这个旧节点是需要卸载的
unMountElement(oldVNode[i]);
};
}
发现原来的O(n^2)的双for循环时间复杂度已经被成功把拆分开了，时间复杂度降低为O(n), 但是发现多出来了个变量叫做ketSourceMap, 这就是我们在处理时采用到的空间换时间的优化做法.
现在接下来就是根据source计算出最长递增子序列，我们在这里去考虑为什么会需要最长递增子序列，最长递增子序列是一个递增的列表项，说明这个最长递增子序列的节点顺序正确并且不需要节点移动，这样移动节点的次数会是最少的，这就是最长递增子序列在此处最大的作用.
接下来，同我们之前一样，我会给到一个快速 diff 的代码执行示意动画，请看下图 3-4.
图 3-4 快速 diff 算法执行流程示意图
/**
* 快速diff算法
* @param oldVNode
* @param vNode
* @param container
*/
function fastDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
let startIndex = 0;
while(oldVNode[startIndex] && vNode[startIndex] && oldVNode[startIndex]?.key === vNode[startIndex]?.key) { // 前置节点检查
patch(oldVNode[startIndex], vNode[startIndex], container);
startIndex ++;
};
let oldEndIndex = oldVNode.length - 1;
let newEndIndex = vNode.length - 1;
// 如果前置节点已经把新节点/旧节点中某一列观测完毕了, 则没有必要在去后置节点检查了, 如果没有这层检测反而为引起预期之外的渲染情况
if ((startIndex !== oldVNode.length) || (startIndex !== vNode.length)) {
while(oldVNode[oldEndIndex] && vNode[newEndIndex] && oldVNode[oldEndIndex].key === vNode[newEndIndex].key) { // 后置节点检查
patch(oldVNode[oldEndIndex], vNode[newEndIndex], container);
oldEndIndex--;
newEndIndex--;
};
}
if (newEndIndex >= startIndex && oldEndIndex < startIndex) { // 说明旧节点已经排查完毕但新节点中还存在着未被排查的节点
for (let i = startIndex; i <= newEndIndex; i++) {
patch(null, vNode[i], container, vNode[newEndIndex + 1]?._element); // 挂载
}
} else if (newEndIndex < startIndex && oldEndIndex >= startIndex) { // 说明新节点已经排查完毕但旧节点中还存在着未被排查
for (let i = startIndex; i <= oldEndIndex; i++) {
unMountElement(oldVNode[i]); // 卸载
}
} else { // 说明新旧节点中同时存在着未被挂载/卸载掉节点
// doubleEndedDiff(oldVNode.slice(startIndex, oldEndIndex + 1), vNode.slice(startIndex, newEndIndex + 1), container);
const newVNodePatchCount = newEndIndex - startIndex + 1;
const source = new Array(newVNodePatchCount).fill(-1); // 新旧节点位置映射
let moved = false;
let pos = 0;
// 双层for时间复杂度高, O(n^2)
// for (let i = startIndex; i <= newEndIndex; i++) {
// for (let j = startIndex; j <= oldEndIndex; j++) {
// if (vNode[i].key === oldVNode[j].key) { // 找到新旧节点映射点
// patch(oldVNode[j], vNode[i], container);
// source[i - startIndex] = j;
// if (j < pos) { // 定位在新节点树中的最大索引处, 可用来确定是否需要移动节点这一步
// moved = true;
// } else {
// pos = j;
// }
// break;
// }
// }
// }
// // 循环旧节点列表进行卸载没被复用的节点
// oldVNode.forEach(oldElement => {
// if (!vNode.find(newElement => newElement.key === oldElement.key)) {
// unMountElement(oldElement);
// };
// });
// 空间换时间, 降低时间复杂度, O(n)
const keySourceMap: Record<number | string | symbol, number> = {};
for (let i = startIndex; i <= newEndIndex; i++) {
keySourceMap[vNode[i].key!] = i; // 利用唯一key+数组存留来关联上新旧两颗树的差异对比
}
for (let i = startIndex; i <= oldEndIndex; i++) {
const sourceKey = keySourceMap[oldVNode[i].key!];
if (sourceKey !== undefined) { // 说明有可复用节点
patch(oldVNode[i], vNode[sourceKey], container); // 打补丁操作
source[sourceKey - startIndex] = i; // 新旧节点同key映射点
if (sourceKey < pos) { // 定位在新节点树中的最大索引处, 可用来确定是否需要移动节点这一步
moved = true;
} else {
pos = sourceKey;
}
} else { // 没找到说明这个旧节点是需要卸载的
unMountElement(oldVNode[i]);
};
}
if (moved) {
// 计算出最长递增子序列
const result = getSequence(source);
let longestLastIndex = result.length - 1; // 最长递增子序列的最后一位索引
let newLastIndex = newEndIndex - startIndex; // 新节点列表以startIndex为基准索引开始的最后一位索引值
for (let i = newLastIndex; i >= 0; i--) { // 反向循环
if (source[i] === -1) { // 说明这个节点是新增节点
const currentVNode = vNode[i + startIndex];
patch(null, currentVNode, container, vNode[i + startIndex + 1]?._element); // 以新节点的当前位的下一个节点为锚点位进行插入
} else if (i !== result[longestLastIndex]) { // 不是最长递增子序列, 节点需要移动
// 节点都被patch打补丁过了(element属性也被同步过了), 只需要考虑移动节点即可, 锚点位置仍然按照上面新增节点那样处理即可
const currentVNode = vNode[i + startIndex];
insertElement(container, currentVNode._element, vNode[i + startIndex + 1]?._element);
} else { // 说明遇见了最长递增子序列, 该节点不需要移动, longestLastIndex索引向前移动
longestLastIndex--;
}
}
};
}
};
参考资料#
《Vue.js 设计与实现》第七、八、九、十、十一章内容