双端diff算法详解
前言
Diff算法是Vue渲染器的核心算法，也是Vue的精髓所在。简单来说，当新旧vnode的子节点都是一组节点时，为了以最小的性能开销完成更新操作，需要比较新旧两组子节点，进而找出最小的更新代价，用于比较的算法就是diff算法。本节文章将详细介绍Vue2的双端diff算法。
原理介绍
顾名思义，双端diff算法是一种同时对新旧子节点的两个端点比较的算法。因此，我们需要四个索引值来标记新旧子节点的两个端点，如下图所示：
diff1.png
使用代码来表示四个端点
function patchChildren(oldVNode, newVNode, container) {
if (typeof oldVNode.children === 'string') {
// 新节点是文本节点 略
} else if (Array.isArray(oldVNode.children)) {
if (Array.isArray(oldNode.children)) {
console.time('patch');
// 封装双端diff算法实现
patchKeyedChildren(oldNode, newVNode, container);
console.timeEnd('patch');
} else {
// 略
}
} else {
// 略
}
}
function patchKeyedChildren(oldVNode, newVNode, container) {
const oldChildren = oldVNode.children;
const newChildren = newVNode.children;
// 四个索引值（端点）
let oldStartIdx = 0;
let oldEndIdx = oldChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = newChildren.length - 1;
}在上面这段代码中，我们将两组子节点的打补丁工作封装到了patchKeyedChildren中，在该函数内，首先获取到两组子节点oldChildren和newChildren,接着创建四个索引值，分别指向两组子节点的头和尾。即newStartIdx、newEndIdx、oldStartIdx、oldEndIdx。有了他们，我们就可以找到它所指向的虚拟节点了。如下面的代码所示
function patchKeyedChildren(oldVNode, newVNode, container) {
const oldChildren = oldVNode.children;
const newChildren = newVNode.children;
// 四个索引值（端点）
let oldStartIdx = 0;
let oldEndIdx = oldChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = newChildren.length - 1;
// 四个索引值所指向的节点
let oldStartVNode = oldChildren[oldStartIdx];
let oldEndVNode = oldChildren[oldEndIdx];
let newStartVNode = newChildren[newStartIdx];
let newEndVNode = newChildren[newEndIdx];
}其中oldStartVNode是旧节点的起始节点，oldEndVNode是旧节点的结束节点，newStartVNode是新节点的起始节点，newEndVNode是新节点的结束节点。有了这四个节点，我们就可以进行双端比较了。我们先用图文说明的方式展示一下双端比较的4个步骤
diff2.png
- 比较旧的一组子节点中的第一个子节点p-1与新的一组子节点中的第一个子节点p-4，看看他们是否相同。由于两者key值不同，所以不相同，不可复用，于是什么都不做。
- 比较旧的一组子节点中的最后一个子节点p-4与新的一组子节点中的最后一个子节点p-3，看看他们是否相同。由于两者key值不同，所以不相同，不可复用，于是什么都不做。
- 比较旧的一组子节点中的第一个子节点p-1与新的一组子节点中的最后一个子节点p-3，看看他们是否相同。由于两者key值不同，所以不相同，不可复用，于是什么都不做。
- 比较旧的一组子节点中的最后一个子节点p-4与新的一组子节点中的第一个子节点p-4，看看他们是否相同。由于他们的key值相同，因此可以进行DOM复用。
可以看到我们在第四步时找到了可以复用的节点，这说明他们对应节点的真实DOM可以被复用。对于可以复用的节点，我们只需要将其移动到正确的位置即可。那么应该如何移动DOM元素到正确的位置呢？我们需要先关注第四步比较过程的细节：节点p-4原本是最后一个子节点，但在新的顺序中，他变成了第一个子节点。换句话说，节点p-4在更新后应该是第一个子节点。因此对应到程序中，则是将索引oldEndIdx指向的节点所对应的真实DOM移动到oldStartIdx指向的节点所对应的真实DOM之前。
如下代码所示：
function patchKeyedChildren(oldVNode, newVNode, container) {
const oldChildren = oldVNode.children;
const newChildren = newVNode.children;
// 四个索引值（端点）
let oldStartIdx = 0;
let oldEndIdx = oldChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = newChildren.length - 1;
// 四个索引值所指向的节点
let oldStartVNode = oldChildren[oldStartIdx];
let oldEndVNode = oldChildren[oldEndIdx];
let newStartVNode = newChildren[newStartIdx];
let newEndVNode = newChildren[newEndIdx];
if (oldStartVNode.key === newStartVNode.key) {
// 第一步 头头比较
} else if (oldEndVNode.key === newEndVNode.key) {
// 第二部 尾尾比较
} else if (oldStartVNode.key === newEndVNode.key) {
// 第三步 尾头比较
} else if (oldEndVNode.key === newStartVNode.key) {
// 第四步 头尾比较
patch(oldEndVNode, newStartVNode, container);
// 移动时，将旧节点组的尾节点移动到头节点
insert(oldEndVNode.el, container, oldStartVNode.el);
// 移动完成后，更新索引值，并将指针指向下一个位置
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
}
}patch函数用于给子节点打补丁，并非本节重点关注过程,后续可先略过。insert函数接收三个参数：需要移动的DOM节点，父节点和锚点节点。
function insert(el, parent, anchor = null) {
parent.insertBefore(el, anchor);
}insertBefore的官方解释如下：
Node.insertBefore() 方法在参考节点之前插入一个拥有指定父节点的子节点。如果给定的子节点是对文档中现有节点的引用，insertBefore() 会将其从当前位置移动到新位置（在将节点附加到其他节点之前，不需要从其父节点删除该节点）。
调用insert方法后，我们会将头部元素oldStartVNode.el 作为锚点，将尾部元素oldEndVNode.el移动到锚点前面。在这一步DOM操作完成后，接下来就是比较关键的一步，即更新索引值，由于第四步设计的两个索引分别是oldEndIdx、newStartIdx,因此我们需要将他们往正确的方向前进一步。
diff3.png
如图所示，此时真实节点顺序为 p-4、p-1、p-2、p-3 ，这是因为Diff算法还没有结束，还需要进行下一轮更新，因此我们需要把比较的逻辑封装到一个while循环中
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVNode.key === newStartVNode.key) {
// 第一步 头头比较
} else if (oldEndVNode.key === newEndVNode.key) {
// 第二部 尾尾比较
} else if (oldStartVNode.key === newEndVNode.key) {
// 第三步 尾头比较
} else if (oldEndVNode.key === newStartVNode.key) {
// 第四步 头尾比较
patch(oldEndVNode, newStartVNode, container);
// 移动时，将旧节点组的尾节点移动到头节点
insert(oldEndVNode.el, container, oldStartVNode.el);
// 移动完成后，更新索引值，并将指针指向下一个位置
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
// 其余情况
}
}由于每一轮更新完成后，紧接着都会更新与本轮次相关联的索引值，所以整个while循环执行的条件就是：头部索引值要小于尾部索引值。
在第一步比较完成后，while循环条件仍然成立，因此需要进行下一轮比较
- 比较旧的一组子节点中的头部节点和新的一组子节点的头部节点，看看他们是否相同。由于两者key值不同，所以不相同，不可复用，于是什么都不做。
- 比较旧的一组子节点中的尾部节点和新的一组子节点的尾部节点，看看他们是否相同。由于两者key值相同，因此可以进行DOM复用。另外，由于两者都处于尾部，所以不需要对真实DOM进行移动操作，只需要对新节点打补丁即可
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVNode.key === newStartVNode.key) {
} else if (oldEndVNode.key === newEndVNode.key) {
// 第二部 尾尾比较
patch(oldEndVNode, newEndVNode, container);
// 新旧都在尾部，不移动dom，只更新索引
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key === newEndVNode.key) {
// 第三步 尾头比较
} else if (oldEndVNode.key === newStartVNode.key) {
// 第四步 头尾比较
patch(oldEndVNode, newStartVNode, container);
// 移动时，将旧节点组的尾节点移动到头节点
insert(oldEndVNode.el, container, oldStartVNode.el);
// 移动完成后，更新索引值，并将指针指向下一个位置
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
// 其余情况
}
}
diff4.png
如图所示真实DOM的顺序与上一轮没有变化，因此我们需要继续进行下一轮比较。在第二步比较完成后，while循环条件仍然成立，因此需要进行下一轮比较
- 比较旧的一组子节点中的第一个子节点p-11与新的一组子节点中的第一个子节点p-2，看看他们是否相同。由于两者key值不同，所以不相同，不可复用，于是什么都不做。
- 比较旧的一组子节点中的最后一个子节点p-2与新的一组子节点中的最后一个子节点p-1，看看他们是否相同。由于两者key值不同，所以不相同，不可复用，于是什么都不做。
- 比较旧的一组子节点中的第一个子节点p-1与新的一组子节点中的最后一个子节点p-1，看看他们是否相同。由于两者key值相同，可以复用。由于旧节点处于头部，新节点处于尾部，因此需要将旧节点移动到尾部。也就是p-2节点的后面
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVNode.key === newStartVNode.key) {
// 第一步 头头比较
} else if (oldEndVNode.key === newEndVNode.key) {
// 第二部 尾尾比较
patch(oldEndVNode, newEndVNode, container);
// 新旧都在尾部，不移动dom，只更新索引
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key === newEndVNode.key) {
// 第三步 尾头比较
patch(oldStartVNode, newEndVNode, container);
insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);
oldStartVNode = oldChildren[++oldStartIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldEndVNode.key === newStartVNode.key) {
// 第四步 头尾比较
patch(oldEndVNode, newStartVNode, container);
// 移动时，将旧节点组 的尾节点移动到头节点
insert(oldEndVNode.el, container, oldStartVNode.el);
// 移动完成后，更新索引值，并将指针指向下一个位置
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
// 其余情况
}
}更新后如图所示。
diff5.png
此时，真实DOM的顺序为p-4、p-2、p-1、p-3，因此我们需要继续进行下一轮比较。在第三步比较完成后，while循环条件仍然成立，因此需要进行下一轮比较
- 比较旧的一组子节点中的第一个子节点p-2与新的一组子节点中的第一个子节点p-2，看看他们是否相同。由于两者key值相同，可以复用。由于旧节点处于头部，新节点处于头部，因此不需要移动真实DOM，只需要对新节点打补丁即可。
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVNode.key === newStartVNode.key) {
// 第一步 头头比较
patch(oldStartVNode, newStartVNode, container);
// 新旧都在头部，不移动dom，只更新索引
oldStartVNode = oldChildren[++oldStartIdx];
newStartVNode = newChildren[++newStartIdx];
} else if (oldEndVNode.key === newEndVNode.key) {
// 第二部 尾尾比较
patch(oldEndVNode, newEndVNode, container);
// 新旧都在尾部，不移动dom，只更新索引
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key === newEndVNode.key) {
// 第三步 尾头比较
patch(oldStartVNode, newEndVNode, container);
insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);
oldStartVNode = oldChildren[++oldStartIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldEndVNode.key === newStartVNode.key) {
// 第四步 头尾比较
patch(oldEndVNode, newStartVNode, container);
// 移动时，将旧节点组 的尾节点移动到头节点
insert(oldEndVNode.el, container, oldStartVNode.el);
// 移动完成后，更新索引值，并将指针指向下一个位置
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
// 其余情况
}
}
diff6.png
此时如图，真实DOM的顺序与新的一组子节点的顺序相同了，且循环条件终止。双端Diff算法执行完毕。
非理想状况的处理
我们知道，双端diff算法的每一轮比较都分为四个步骤，在上一节例子中，每一轮比较都会命中四个步骤中的一个，这是非常理想的情况。但实际上，并非所有情况都这么理想。
在现在这个例子中，新旧两组子节点顺序如下。
- 旧： p-1 p-2 p-3 p-4
- 新： p-2 p-4 p-1 p-3
当我们尝试按照双端diff算法的思路进行第一轮比较时，会发现无法命中四个步骤的情况：
diff7.png
- 比较旧的一组子节点中的第一个子节点p-1与新的一组子节点中的第一个子节点p-2，看看他们是否相同。由于两者key值不同，所以不相同，不可复用，于是什么都不做。
- 比较旧的一组子节点中的最后一个子节点p-4与新的一组子节点中的最后一个子节点p-3，看看他们是否相同。由于两者key值不同，所以不相同，不可复用，于是什么都不做。
- 比较旧的一组子节点中的第一个子节点p-1与新的一组子节点中的最后一个子节点p-3，看看他们是否相同。由于两者key值不同，所以不相同，不可复用，于是什么都不做。
- 比较旧的一组子节点中的最后一个子节点p-4与新的一组子节点中的第一个子节点p-2，看看他们是否相同。由于两者key值不同，所以不相同，不可复用，于是什么都不做。
如果四个步骤都无法命中，都无法找到可复用的节点，我们只能通过增加额外的处理步骤来处理这种非理想的情况。既然两个头部和两个尾部的节点都无法复用，我们就尝试看非头部、非尾部的节点是否可以复用。具体做法是，拿新的一组子节点中的头部节点去旧的一组子节点中寻找：
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVNode.key === newStartVNode.key) {
// 第一步 头头比较
} else if (oldEndVNode.key === newEndVNode.key) {
// 第二部 尾尾比较
} else if (oldStartVNode.key === newEndVNode.key) {
// 第三步 尾头比较
} else if (oldEndVNode.key === newStartVNode.key) {
// 第四步 头尾比较
} else {
const idxInOld = oldChildren.findIndex(
(c) => c && c.key === newStartVNode.key
);
if (idxInOld > 0) {
const vnodeToMove = oldChildren[idxInOld];
patch(vnodeToMove, newStartVNode, container);
insert(vnodeToMove.el, container, oldStartVNode.el);
// 由于原来位置的节点被移走了，因此将其设置为undefined
oldChildren[idxInOld] = void 0;
} else {
patch(null, newStartVNode, container, oldStartVNode.el);
}
newStartVNode = newChildren[++newStartIdx];
}
}在上面这段代码中，首先判断idxInOld是否大于0。如果条件成立，说明找到了可复用的节点，然后将该节点对应的真实位置移动到头部。因此我们需要先获取需要移动的节点vnodeToMove，接着调用insert函数，并以现在oldStartVNode指向的节点为锚点插入到真实DOM中。移动完成后，需要两个步骤来收尾：
- 由于处于idxInOld位置的节点已经处理过了（被移走了），因此我们需要将oldChildren[idxInOld]位置设置为undefined。
新的一组子节点的头部节点被处理了，所以newStartIdx需要前进到下一个位置。
diff8.png
在第一步比较完成后，while循环条件仍然成立，因此需要进行下一轮比较，此时就是常规比较了，我们可以直接略过一般步骤。但是需要注意的一点是，如果此时旧的一组子节点的头部节点是undefined，则说明我们已经对他处理过了，因此不需要再去处理它了，直接跳过即可。我们需要补充相关代码。
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (!oldStartVNode) {
oldStartVNode = oldChildren[++oldStartIdx];
} else if (!oldEndVNode) {
oldEndVNode = oldChildren[--oldEndIdx];
} else if (oldStartVNode.key === newStartVNode.key) {
// 第一步 头头比较
} else if (oldEndVNode.key === newEndVNode.key) {
// 第二部 尾尾比较
} else if (oldStartVNode.key === newEndVNode.key) {
// 第三步 尾头比较
} else if (oldEndVNode.key === newStartVNode.key) {
// 第四步 头尾比较
} else {
const idxInOld = oldChildren.findIndex(
(c) => c && c.key === newStartVNode.key
);
if (idxInOld > 0) {
const vnodeToMove = oldChildren[idxInOld];
patch(vnodeToMove, newStartVNode, container);
insert(vnodeToMove.el, container, oldStartVNode.el);
// 由于原来位置的节点被移走了，因此将其设置为undefined
oldChildren[idxInOld] = void 0;
}
newStartVNode = newChildren[++newStartIdx];
}
}添加新元素
在上一节中，我们已经处理了非理想情况下的比较逻辑，但是还有一种情况没有处理，那就是新的一组子节点比旧的一组子节点多的情况。比如下面这种情况：
diff9.png
- 旧： p-1 p-2 p-3
- 新： p-4 p-1 p-3 p-2
首先我们尝试第一轮比较，会发现四个步骤都无法找到可复用的节点，于是我们尝试拿新的一组子节点中的头部节点p-4去旧的子节点中寻找相同key值的节点，但旧的子节点中根本没有p-4节点，这说明p-4一个新增节点，我们需要处理这种新增节点的情况，并把它挂载到正确的位置。那么应该挂载到哪里呢？很简单，因为当前节点p-4是新的一组子节点中的头部节点，所以只需要将它挂载到当前的头部节点之前即可。当前头部节点的意思就是旧节点组中oldStartVNode指向的DOM元素。
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (!oldStartVNode) {
oldStartVNode = oldChildren[++oldStartIdx];
} else if (!oldEndVNode) {
oldEndVNode = oldChildren[--oldEndIdx];
} else if (oldStartVNode.key === newStartVNode.key) {
// 第一步 头头比较
} else if (oldEndVNode.key === newEndVNode.key) {
// 第二部 尾尾比较
} else if (oldStartVNode.key === newEndVNode.key) {
// 第三步 尾头比较
} else if (oldEndVNode.key === newStartVNode.key) {
// 第四步 头尾比较
} else {
// 第五步 新增节点
const idxInOld = oldChildren.findIndex(
(c) => c && c.key === newStartVNode.key
);
if (idxInOld > 0) {
const vnodeToMove = oldChildren[idxInOld];
patch(vnodeToMove, newStartVNode, container);
insert(vnodeToMove.el, container, oldStartVNode.el);
// 由于原来位置的节点被移走了，因此将其设置为undefined
oldChildren[idxInOld] = void 0;
} else {
// 处理新增的情况
patch(null, newStartVNode, container, oldStartVNode.el);
}
newStartVNode = newChildren[++newStartIdx];
}
}上述代码在处理新增元素的情况还是有缺陷的，某些情况下，比如存在新增节点，但是没有进入第五步新增节点的逻辑，且由于旧节点索引条件不满足导致跳出while循环时，我们可能会遗漏掉一些新增的节点。为了弥补这个缺陷，我们需要添加额外的处理代码。
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 省略部分逻辑
}
// 新的这组节点还满足循环条件，添加新节点
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
for (let i = newStartIdx; i <= newEndIdx; i++) {
// 找到现有的头部节点索引(newEndIdx + 1)
const anchor = newChildren[newEndIdx + 1]
? newChildren[newEndIdx + 1].el
: null;
patch(null, newChildren[i], container, anchor);
}
}移除不存在的元素
解决了新增节点的问题后，我们还需要处理新节点比旧节点少的情况。比如下面这种情况：
diff10.png
- 旧： p-1 p-2 p-3
- 新： p-1 p-3
我们尝试按照Diff算法的思路进行更新
比较旧的一组子节点中的第一个子节点p-1与新的一组子节点中的第一个子节点p-1，看看他们是否相同。由于两者key值相同，可以复用。
diff11.png
第一步比较中找到了可复用的节点，于是执行更新，更新后的节点状态如图所示
接着执行下一轮更新
- 比较旧的一组子节点中的第一个子节点p-2与新的一组子节点中的第一个子节点p-3，看看他们是否相同。由于两者key值不同，所以不相同，不可复用，于是什么都不做。
比较旧的一组子节点中的最后一个子节点p-3与新的一组子节点中的最后一个子节点p-3，看看他们是否相同。由于两者key值相同，可以复用。
diff12.png
第二步比较找到了可以复用的节点。于是执行更新，更新后的节点状态如图所示
此时变量newStartIdx的值大于变量newEndIdx的值，满足结束更新的条件，于是更新结束，但观察图例可知，旧节点中尚存在未被处理的节点。应该将其移除。因此我们需要增加额外的代码来处理它。
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 省略部分逻辑
}
// 新的这组节点还满足循环条件，添加新节点
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
for (let i = newStartIdx; i <= newEndIdx; i++) {
// 找到现有的头部节点索引(newEndIdx + 1)
const anchor = newChildren[newEndIdx + 1]
? newChildren[newEndIdx + 1].el
: null;
patch(null, newChildren[i], container, anchor);
}
} else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
// 删除旧节点
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
unmount(oldChildren[i]);
}与新增节点的处理逻辑类似，我们需要遍历旧节点，将其从DOM中移除。
完整代码
function patchKeyedChildren(oldVNode, newVNode, container) {
const oldChildren = oldVNode.children;
const newChildren = newVNode.children;
// 四个索引值
let oldStartIdx = 0;
let oldEndIdx = oldChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = newChildren.length - 1;
// 四个索引值所指向的节点
let oldStartVNode = oldChildren[oldStartIdx];
let oldEndVNode = oldChildren[oldEndIdx];
let newStartVNode = newChildren[newStartIdx];
let newEndVNode = newChildren[newEndIdx];
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (!oldStartVNode) {
oldStartVNode = oldChildren[++oldStartIdx];
} else if (!oldEndVNode) {
oldEndVNode = oldChildren[--oldEndIdx];
} else if (oldStartVNode.key === newStartVNode.key) {
// 第一步 头头比较
patch(oldStartVNode, newStartVNode, container);
// 新旧都在头部，不移动dom，只更新索引
oldStartVNode = oldChildren[++oldStartIdx];
newStartVNode = newChildren[++newStartIdx];
} else if (oldEndVNode.key === newEndVNode.key) {
// 第二部 尾尾比较
patch(oldEndVNode, newEndVNode, container);
// 新旧都在尾部，不移动dom，只更新索引
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key === newEndVNode.key) {
// 第三步 尾头比较
patch(oldStartVNode, newEndVNode, container);
insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);
oldStartVNode = oldChildren[++oldStartIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldEndVNode.key === newStartVNode.key) {
// 第四步 头尾比较
patch(oldEndVNode, newStartVNode, container);
// 移动时，将旧节点组的尾节点移动到头节点
insert(oldEndVNode.el, container, oldStartVNode.el);
// 移动完成后，更新索引值，并将指针指向下一个位置
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
const idxInOld = oldChildren.findIndex(
(c) => c && c.key === newStartVNode.key
);
if (idxInOld > 0) {
const vnodeToMove = oldChildren[idxInOld];
patch(vnodeToMove, newStartVNode, container);
insert(vnodeToMove.el, container, oldStartVNode.el);
// 由于原来位置的节点被移走了，因此将其设置为undefined
oldChildren[idxInOld] = void 0;
} else {
patch(null, newStartVNode, container, oldStartVNode.el);
}
newStartVNode = newChildren[++newStartIdx];
}
}
// 添加新节点
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
for (let i = newStartIdx; i <= newEndIdx; i++) {
// 找到现有的头部节点索引(newEndIdx + 1)
const anchor = newChildren[newEndIdx + 1]
? newChildren[newEndIdx + 1].el
: null;
patch(null, newChildren[i], container, anchor);
}
} else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
// 删除旧节点
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
unmount(oldChildren[i]);
}
}
}