大家好，我是苏先生，一名热爱钻研、乐于分享的前端工程师，跟大家分享一句我很喜欢的话：人活着，其实就是一种心态，你若觉得快乐，幸福便无处不在
github与好文
前言
在diff算法核心原理精讲一节中，我们对diff的核心实现思路进行了分析和实现，但是它还不足以上生产（ps：其实可以，只不过框架间性能内卷严重），还存在着诸多不足和可优化的点。本节我们继续深入，力求完成重构和优化
问题分析
假设我们现在有如下两组dom节点
// 新
<p></p>
<span></span>
<div></div>
// 旧
<span></span>
<div></div>
<p></p>
按照diff算法核心原理精讲一节中的实现，代码的执行过程如下：
-
取新节点p，到旧节点中找到对应节点p，并记录其位置为2
-
取新节点span，到旧节点中找到对应节点span的位置为0，由于0<2，则进行移动
-
取新节点div，到旧节点中找到对应节点div的位置为1，由于1<2，则进行移动
由此可知，一共需要进行两次dom节点的移动操作，但是我们观察示例的新旧两组节点，应该不难看出：span和div的相对位置是一样的，只需要将p节点从原来的2号位置移动到新的0号位置就可以了。换句话说，我们浪费了一次dom移动操作
原因分析
我们浅看下上一节实现的代码:
function patchChildren(n1,n2,continer){
...
for(let i=0;i<newChildren.length;i++){
for(j;j<oldChildren.length;j++){
...
}
}
}
我们使用内外两层for循环来挨个处理节点，由于是同步的，外层循环必须等到内层循环结束后才能进入下一轮，这意味着一次只能处理一个。所以，如果我们能将两个for循环拆开，使它们平级运行，那就意味着有机会同时拿到两个列表的不同节点来进行操作，带入到前文示例中去，如果我们一个从新节点索引位置为0处开始遍历，一个从旧节点索引位置为2处开始遍历，岂不是一次就找到需要移动的节点了嘛
实现版本一
端点确认
在前文中，我们通过原因分析找到了双端比较的核心是平行运行，且针对前文的特定示例我们发现只需要一个从前向后，一个从后向前，就能在第一次就发现需要移动的点。那么我们合理对其进行推断就能知道，一定也存在某个对立的情况需要将两次遍历的起始位置进行对调
故，我们的起始位置针对每一个节点列表都有两个
let oldStartIndex = 0
let oldEndIndex = oldChildren.length - 1
let newStartIndex = 0
let newEndIndex = newChildren.length - 1
也即，我们可以通过索引拿到对应的四个节点
let oldStartNode = oldChildren[oldStartIndex]
let oldEndNode = oldChildren[oldEndIndex]
let newStartNode = newChildren[newStartIndex]
let newEndNode = newChildren[newEndIndex]
遍历分支
现在我们一共有两个for循环、四个端点，按照穷举法，有如下四种运行方式：
1-新列表对应的for循环从newStartIndex开始遍历，旧列表对应的for循环从oldStartIndex开始遍历
2-新列表对应的for循环从newStartIndex开始遍历，旧列表对应的for循环从oldEndIndex开始遍历
3-新列表对应的for循环从newEndIndex开始遍历，旧列表对应的for循环从oldStartIndex开始遍历
4-新列表对应的for循环从newEndIndex开始遍历，旧列表对应的for循环从oldEndIndex开始遍历
判断临界
现在我们来判定临界，以如下新旧两组dom节点为例：
// 新
<p></p>
<span></span>
<div></div>
<menu></menu>
// 旧
<div></div>
<span></span>
<menu></menu>
<p></p>
第1轮：newStartIndex=0；oldStartIndex=0
div !== p，无法复用，且无相对位置关系无法判断和处理节点移动，跳过会导致最终结果错误，故程序应当停止
第2轮：newStartIndex=0；oldEndIndex=3
p === p，可以复用，复用的节点无需执行额外操作，故进入下一次循环，即newStartIndex=1，oldEndIndex=2，此时span !== menu，无法复用，同上，程序应当停止
第3轮：newEndIndex=3；oldStartIndex=0
menu !== div，无法复用，同上，程序应当停止
第4轮：newEndIndex=3；oldEndIndex=3
menu !== p，无法复用，同上，程序应当停止
综上，临界点为两节点不可复用时
过程模拟
现在我们来思考，如何执行这四个分支？
我们的核心诉求是让新旧列表中的每一个节点都能参与比较，现在我们结合临界点中的结论看如下示例：
顺序对比
新旧的dom节点如下
// 新
<span></span>
<div></div>
<menu></menu>
// 旧
<span></span>
<p></p>
<menu></menu>
1-分支1
当第二次时，即索引位置为1时，div !== p，程序停止，此时还有div和p未处理。此时由于节点span已经被明确可复用，而分支2和分支3会导致节点重新参与比较，因此需要舍弃
2-分支4
此时，我们使用分支4，开始从后向前遍历比对，同样在索引位置为1时，得到div !== p，程序停止。此时我们已经处理完所有可复用的节点，并且两次程序停止时的节点位置相同，此时有充分证据能够表明div标签需要去替换掉p标签
交叉对比
在顺序对比对比中，我们的示例刚刚好能处理完所有的节点，现在我们来考虑另外一个例子:
// 新
<span></span>
<div></div>
<h1></h1>
<menu></menu>
// 旧
<span></span>
<h1></h1>
<div></div>
<menu></menu>
在此示例中，使用顺序对比仍然可以很轻松的处理完头尾两个节点，但是对于中间的两个节点将会无法处理，此时如果我们用交叉方式比对，即分支2对应的情况，那么就可以准确找到可复用的节点
对于分支3是一样的，故此处不再赘述
调用顺序
根据前文对分支1到分支4的分析，我们知道了，先顺序调用（ps：分支1和分支4），再交叉调用（ps：分支2和分支3）可以很好的处理完所有的节点。那么反过来，是否可以先交叉后顺序呢？貌似也是可以的，比如下边这种情况，先进行交叉处理完双端节点，再进行顺序对比处理余下的节点
// 新
<div></div>
<span></span>
<menu></menu>
<h1></h1>
// 旧
<h1></h1>
<span></span>
<menu></menu>
<div></div>
结论
综上所述，我们需要在遍历的过程中分别就四种情况进行比对
代码示例
结合目前的分析，我们知道需要对每一个节点至少执行四次比对，才能覆盖完分支1到分支4。因此我们的遍历代码大致长下边这样：
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
if(oldStartNode === newStartNode){
...
}else if(oldStartNode === newEndNode){
...
}else if(oldEndNode === newEndNode){
...
}else if(oldEndNode === newStartNode){
...
}
}
结合前文分析，当找到可复用节点时，我们需要将指针移动到下一个节点继续进行比对，并且，根据当前适用分支的不同，指针的移动方向也不同。如下以分支1为例
oldStartNode = oldChildren[++oldStartIndex]
newStartNode = newChildren[++newStartIndex]
实现版本二
在版本一中，我们的思路是乌托邦式的，因为我们隐式的假定了每一次都能够命中一个分支，然而这在现实中是不可能的
// 新
<div></div>
<span></span>
<menu></menu>
<h1></h1>
// 旧
<span></span>
<h1></h1>
<div></div>
<menu></menu>
在上述的示例节点中，无法命中四个节点中的任何一个分支，但肉眼可见的是它们确确实实是可复用的，只不过位置发生了移动
你还记得在diff算法核心原理精讲一节中我们是如何去判断节点移动的吗？这里能否使用同样的方式来处理呢？
相信聪明的你已经有答案了！但是先别急着公布，我先来说说我的看法，看是不是与君不谋而合
首先，从目的上来说，diff算法核心原理精讲一节中我们是为了同步真实的dom节点，换句话，此时的任意一个虚拟节点都已经被patch过了
但是作为本文，是为了正确处理完虚拟节点。按照我们目前的实现逻辑，当找不到可复用节点时while循环应该被break掉，但这种粗暴的做法直接导致除端点节点外的其他n个节点都无法被处理。因此我们要新增else分支来将指针移动到下一个位置继续对剩余节点进行处理
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
if(oldStartNode === newStartNode){
...
}else if(oldStartNode === newEndNode){
...
}else if(oldEndNode === newEndNode){
...
}else if(oldEndNode === newStartNode){
...
}else{
// 两端点找不到可复用节点
}
}
但我们没有一种类似回溯的机制，如果跳过了当前的节点，就永远不可能回过头进行二次处理了。所以，在移动到下一个指针之前，我们还需要对当前节点存在的可能性进行处理，比如是否发生了移动
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
if(oldStartNode === newStartNode){
...
}else if(oldStartNode === newEndNode){
...
}else if(oldEndNode === newEndNode){
...
}else if(oldEndNode === newStartNode){
...
}else{
// 两端点找不到可复用节点
const indexOfOld = oldChildren.findIndex((v)=>v.key === newStartNode.key)
if(indexOfOld > -1){
const needMoved = oldChildren[indexOfOld]
// 将当前节点作为根节点继续patch
...
helper.insert(needMoved,continer,oldStartNode)
oldChildren[indexOfOld] = undefined
newStartNode = newChildren[++newStartIndex]
}
}
}
如上，如果indexOfOld>-1，则说明存在可复用的节点，此时我们通过oldChildren[indexOfOld]获取到需要移动的节点，并调用前文实现的helper.insert函数将needMoved插入到oldStartNode前边（ps：如果是头节点，就不会进入到该else分支）,接着将空出来的位置标记为undefined（ps：思考一下，为什么说是空出来？）。最后，由于本次只处理了一个节点为新节点，所以我们只能移动newChildren的指针newStartIndex
此时，我们页面中的dom结构和虚拟节点如下，并且newStartIndex=1，newStartNode为span
// 新
<div></div>
<span></span>
<h1></h1>
<menu></menu>
// 虚拟节点
<span></span>
<h1></h1>
undefined
<menu></menu>
此时，仍然是先顺序对比再交叉对比，显然，在顺序对比时，span === span，此时同时移动新旧节点的指针，此时newStartIndex=2，newStartNode为h1；oldStartIndex=1，oldStartNode为h1
newStartNode = newChildren[++newStartIndex]
oldStartNode = oldChildren[++oldStartIndex]
同理可复用，此时newStartIndex=3，newStartNode为menu；oldStartIndex=2，oldStartNode为undefined，由于undefined表示已经被处理过，所以我们直接跳过即可，即在while中新增if分支进行处理，同理oldEndNode为undefined时我们也进行跳过
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
if(oldStartNode === undefined){
oldStartNode = oldChildren[++oldStartIndex]
continue
}
if(oldEndNode === undefined){
oldEndNode = oldChildren[--oldEndNode]
continue
}
...
}
我们继续执行程序，此时newStartIndex=3，newStartNode为menu；oldStartIndex=3，oldStartNode为menu，可复用，并且此时所有的节点都被处理完毕
实现版本三
处理新增
版本二中我们优化了版本一假设每次while循环都能命中一个分支的问题，但同时我们又隐式的假设每次总是能从旧节点中找到可复用的节点，现实是，并不总是能找到，比如新增了元素时
如下，我们新增else分支来处理新增，在这里我们只是调用了一下patch函数，该函数本质上是一次递归diff，我们这里省略…；最后，我们对剩余节点依次进行挂载（ps：原因见下）
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
...
// 两端点找不到可复用节点
const indexOfOld = oldChildren.findIndex((v)=>v.key === newStartNode.key)
if(indexOfOld > -1){
...
}else{
patch(null,newStartNode)
}
}
if(oldEndIndex < oldStartIndex && newStartIndex <= newEndIndex){
for(let i=newStartIndex;i<newEndIndex;i++){
patch(null,newChildren[i])
}
处理删除
最后，我们来处理删除节点，由于删除节点会导致新节点更早被遍历完，即newEndIndex < newStartIndex会break出while，此时可能还存在多余的节点未被卸载
if(newEndIndex < newStartIndex && oldStartIndex <= oldEndIndex){
for(let i=newStartIndex;i<newEndIndex;i++){
unmount(oldChildren[i])
}
}
如果本文对您有用，希望能得到您的点赞和收藏
订阅专栏，每周更新2-3篇类型体操，每月1-3篇vue3源码解析，等你哟?
