Vue3更新渲染中如何对新旧子节点为数组时进行比对-diff算法
前言：
上一篇简单的讲述了以节点为普通元素类型和组件类型时候的更新渲染流程，其实每种节点类型遍历处理最后都是落实到普通元素类型来进行渲染的，而组件类型则开发者所司空见惯节点类型。
开发者使用v-for渲染数组内容的代码几乎是出现在每个内容页面中的。而对这大量的数组数据的渲染后，对其中数据进行更新的时候，理所当然的不可能是将所有的内容进行重新渲染。简单的想想也能初步想到，如何最少的改变进行重新渲染，进行按需渲染。
新旧子节点皆为数组之间的对比--diff算法（官方文档的例子）
在上一篇中有关patchChildren的时候节点类型进行对比的时候，其中有一种是新旧子节点都是数组的情况。之前没有展开讲，一方面上一篇会篇幅太长，另一方面这里也是一块比较核心的内容--diff算法。
关于节点类型都为带key的数组时，执行patchKeyedChildren函数，而无key值的时候就会调用patchUnkeyedChildren函数。
patchUnkeyedChildren便不展开讲了，简单阐述一下便是会取新旧数组的长度较小的作为公共长度，然后以短的遍历新数组的节点进行patch。然后判断，如果是长的说明有新增节点然后接着挂载，如果短了，说明有移除节点，那么进行卸载。而这个不会利用到已有的节点，只是无脑的patch因此相较于有key的数组节点来说性能是较差的。这也就是为何在使用v-for的时候需要开发者对key进行赋值。
//老子节点是数组，新子节点也是数组
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// 两个数组，不能假设任何情况，执行full diff
patchKeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
从下面代码来看，对于新旧节点的数组的变化，是有更新（patch），挂载/新增(mount)，卸载/删除(unmount)，移动(move)这四个手段。
1.先正向开始同步遍历
//packages/runtime-core/src/renderer.ts
// 都是有key值或者 有些有key值有些没有的情况下
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) => {
let i = 0
const l2 = c2.length
let e1 = c1.length - 1 // 旧节点尾部的索引
let e2 = l2 - 1 // 新节点尾部的索引
// 1. 从头部同步
// (a b) c
// (a b) d e
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else {
break
}
i++
}
//...
}
从源码本身的备注上直观的显示了，从头部开始同步遍历，并对子节点进行isSameVNodeType判断，如果新旧子节点的对比是相同的，则进行patch对比，否则退出循环，并记录当前的下标并自增，开始对下组新旧节点对比。
2.再逆向开始同步遍历
// 2. 从尾部同步
// a (b c)
// d e (b c)
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = (c2[e2] = optimized
? cloneIfMounted(c2[e2] as VNode)
: normalizeVNode(c2[e2]))
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else {
break
}
e1--
e2--
}
其实跟从头部开始的逻辑一致，区别只是从末尾开始向前循环，且i的节点继承了上面正向遍历到不同值时候的节点，这样就可以同时从前后开始遍历，从而避免在两个数组相同的情况下重复遍历各自已经遍历过的部分。
3.当旧节点已遍历完，而新节点有剩余，进行安装
// 3. 公共序列+安装
//遍历过程中新旧节点相同的部分，新增情况
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
while (i <= e2) {
patch(
null,//说明没有旧节点，直接插入更新
(c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i])),
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
i++
}
}
}
当i大于旧节点的尾部索引且i小于新节点的尾部索引的时候，说明旧节点全部遍历完且长度比新节点短，因此新节点相对于旧节点，就只是单纯新增的部分，因此只需要做的就是讲新节点多出的来的部分，i小于等于新节点的尾端节点索引，继续将新增的节点遍历patch更新就行。
4.当新节点已经遍历完，而旧节点有剩余。进行删除
// 4. 公共序列+卸载
//遍历新旧节点中，删除的情况
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}
而当i<=e1且i>e2的时候，说明旧节点并没有遍历完，而新节点已经遍历完成，说明旧节点剩余的节点是需要删除掉的，因为新节点内已经不存在了。
5.未知序列，则是新旧节点，正向和逆向遍历完相同的节点后，都存在剩余节点。
这段彼此不同的节点，有部分节点进行了移动，e节点和c节点发生了交换。同时新增了节点h。
5.1 建立key对应新子节点的索引映射
// 5. 未知序列
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [e d c h] f g
// i = 2, e1 = 4, e2 = 5
else {
const s1 = i // 旧节点的未知序列开始索引
const s2 = i // 新节点的未知序列开始索引
// 5.1 建立key对应新子节点的索引映射
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
if (nextChild.key != null) {
keyToNewIndexMap.set(nextChild.key, i)
}
}
对未知序列的部分进行遍历，新建一个keyToNewIndexMap映射，将新数组的未知序列部分，根据key值和对应的index值对应存入新创建的map中。这个key，就是通常我们开发过程中给v-for生成的列表并给每一项分配了唯一key作为唯一id，在diff的算法对比中，起到很重要的作用，在新旧节点的对比中，当key值相同的时候，会认为是同个节点，从而执行patch。
在官方这个例子中，map中会存入{e:2,d:3,c:4,h:5}。
5.2循环遍历要patch的旧子节点，并尝试patch匹配的节点并删除不再存在的节点
// 5.2 循环遍历要patch的旧子节点，并尝试patch匹配的节点并删除不再存在的节点
let j
//在未知序列中已经patch过的节点数
let patched = 0
//新数组未知序列的长度，未知序列中将要patch的节点数
const toBePatched = e2 - s2 + 1
//声明 节点是否移动
let moved = false
// 用于跟踪是否有任何节点已移动
let maxNewIndexSoFar = 0
//建立一个新节点索引对应旧节点索引映射数组，用于确定最长稳定子序列
const newIndexToOldIndexMap = new Array(toBePatched)
//初始化数组，每个元素的值都是为0
//0是个特殊的值，如果遍历完了仍有元素的值是0，那么说明这个新节点没有对应的旧节点
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
//正序遍历旧子节点的未知序列
for (i = s1; i <= e1; i++) {
//当前的旧节点
const prevChild = c1[i]
//当已patch的节点大于等于将要patch的节点，也就是新子节点序列中都已经patch过了，其余的便需要移除了。
if (patched >= toBePatched) {
//所有的新字节点都已经被patched，因此这个只能被移除
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
//当key存在的时候的
if (prevChild.key != null) {
//取出旧节点对应在新节点的索引位置
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// 无key值的节点，尝试查找相同类型的无key值的节点
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
newIndex = j
break
}
}
}
//如果当前节点的索引不存在，就是不存在于新的节点数组中，则移除该旧节点
if (newIndex === undefined) {
unmount(prevChild, parentComponent, parentSuspense, true)
} else {
//更新新旧数组索引对照组将位于新未知序列的index的值+1（因为默认值全为0）
newIndexToOldIndexMap[newIndex - s2] = i + 1
if (newIndex >= maxNewIndexSoFar) {
//maxNewIndexSoFar始终存储的是上一次的新节点的索引,如果不是一直递增，则说明有移动
maxNewIndexSoFar = newIndex
} else {
moved = true
}
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
patched++
}
}
以上代码，还处于DOM有旧数组生成阶段，所以要清楚旧节点是要更新还是删除亦或者移动，所以需要通过遍历旧数组，并且结合keyToNewIndexMap(旧节点在新数组中的索引位置)与新数组的未知序列进行比对。
因此需要以下变量 patched表示已经更新了的节点数,初始值为0。toBePatched表示需要更新的节点总数，其值便是新节点的的未知序列的长度。patched会随着遍历越来越大，而toBePatched是上限不会随着遍历改变。当patched大于等于toBePatch的时候，其意味着新节点都已经patch完毕，那么当旧节点的长度比新节点的长度长，故而会有大于toBePatch的情况，则剩余的节点需要被移除。
move代表着当前节点是否被移动，maxNewIndexSoFar用于跟踪是否有任何节点已移动。
newIndexToOldIndexMap是一个数组，其长度便是toBePatched的值，为未知序列的长度。用于存储旧子序列节点的索引和新子序列节点的索引之间的映射关系，其每个元素的初始值都为0。若是循环完毕后依旧为0，则说明遍历旧节点中没有对其进行处理，则该节点是新添加的。其映射关系是，index为旧未知序列的索引，value为新未知序列的。
这个newIndexToOldIndexMap具体过程，正序遍历旧未知序列，通过keyToNewIndexMap获取该节点位于新未知序列的索引值。如果索引值不存在，说明该旧节点不存在于新节点中，则需要删除。
如果能找到，则将它在旧子序列中的索引更新到newIndexToOldIndexMap中。
注意，newIndexToOldIndexMap[newIndex - s2] = i + 1这里索引值+1了，是为了应对i为0的情况，如果第一个元素就是乱序的话，i的值为0，0代表没有patch过，这样就没法辨别了，为了防止这种情况。而且这个有关最长递增子序列。
maxNewIndexSoFar始终存放的是上次获取到的newIndex值，如果本次的newIndex值小于maxNewIndexSoFar,这说明正序遍历旧子序列的节点在新子序列中的索引不是一直递增的，也说明了有移动的情况。
至此过程完成了新旧子节点的更新、多余节点的移除，并且建立一个newIndexToOldIndexMap用于存储新旧未知序列节点索引之间的映射关系，并用move和maxNewIndexSoFar确定了节点是否有移动，和追踪了移动节点的最大索引。
用官方例子运行一下以上的逻辑，下面是简单的数据展示。
keyToNewIndexMap = { e:2,d:3,c:4,h:5 }//之前得出的新未知序列数组
toBePatched = 4 //需要patch的长度
newIndexToOldIndexMap = [ 0 , 0 , 0 , 0 ] //每个元素的初始值为0
for (i = 2 ; i <= 4; i++)//for (i = s1; i <= e1; i++) 正序遍历旧未知序列节点
prevChild = c //旧未知序列节点第一个
newIndex = 4 //位于新节点索引4
newIndexToOldIndexMap[4-2]=2+1//newIndexToOldIndexMap[newIndex - s2] = i + 1`
newIndexToOldIndexMap[2]=3 //[0,0,3,0]
maxNewIndexSofar= 4
patch(c,c2[4])
i = 3 //遍历增加
prevChild = d
newIndex = 3
newIndexToOldIndexMap[1]=4
move = true //当newIndex小于maxNewIndexSofar的时候说明不是递增
patch(d,c2[3])
i = 4
prevChild = e
newIndex = 2
newIndexToOldIndexMap[0]=5
patch(e,c2[2])
//结束循环
newIndexToOldIndexMap = [5,4,3,0]//说明h节点是需要创建的真实节点
5.3移动和挂载
有关于节点的移动和挂载方面，在上一步逻辑中已经判断好了节点是否进行了移动，move标记代表了节点的移动。然而其实很多情况下一些连续的子级是不需要移动的，只需要移动位置发生变化的子节点即可，而如何跳过不需要移动的节点，和使用最少步骤来移动需要移动的节点的关键跟diff算法中的最长递增子序列相关。
这里根据newIndexToOldIndexMap = [5,4,3,0]通过getSequence(newIndexToOldIndexMap)获取最长递增子序列[2]。也就是说未知序列中索引为2的节点不用移动，即为节点c。
举个例子：[ 5,7,6,9,0 ]这个数组的最长递增子序列便是[5,6,9]，其索引便是[0,2,3]。从而位于[0,2,3]上的节点便是不用移动的。
// 5.3 移动和安装
// 仅当节点移动时生成最长递增子序列
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
// 倒序遍历，以便我们可以使用最后patch的节点作为锚点
for (i = toBePatched - 1; i >= 0; i--) {
//nextindex是为当前整个数组中的索引，toBePatched+s2-1
const nextIndex = s2 + i
//获取新数组中的当前位置的节点
const nextChild = c2[nextIndex] as VNode
//如果当前节点的下一个节点的长度小于新节点的长度，则讲下个节点存入锚点，反正则取整个父节点的锚点
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
//在这里将新旧节点索引映射中为0的值，即是新增的节点进行patch
if (newIndexToOldIndexMap[i] === 0) {
// 添加挂载新的
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else if (moved) {
//在以下情况下移动：
//没有稳定的子序列（例如反向）
//OR当前节点不在稳定序列中
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
}
}
}
根据上述的运行逻辑，可以明确看到各类判断下会有 3种情况
- 根据
(newIndexToOldIndexMap[i] === 0判断当前节点是否是新的节点，如果是的话，则通过patch方法对这个新节点进行挂载。 j是increasingNewIndexSequence的索引值，即是最长递增子序列的索引，当j<0时，意味着当前索引越界，所以可以提前判断不存在，说明当前节点需要移动，则调用move（nextChild,container,anchor)将nextChild节点移动到anchor之前。move方法内部逻辑最后调用DOM方法的就是insertBefore()- 当前
i !== increasingNewIndexSequence[j]为false时，也就是当前索引恰好是最长递增子序列的值时，说明该节点不需要移动，执行j--便行。
可以根据下图来看看具体的运行流程
以下是节点安装和移动的过程示意图：
vue3中求解最长递增子序列使用的是维基百科提供的算法，核心算法采用的是贪心算法和二分查找法。en.wikipedia.org/wiki/Longes…
//获取最长递增子序列的方法，采用了贪心算法和二分查找
function getSequence(arr: number[]): number[] {
const p = arr.slice()
const result = [0]
let i, j, u, v, c
const len = arr.length
for (i = 0; i < len; i++) {
const arrI = arr[i]
if (arrI !== 0) {
j = result[result.length - 1]
if (arr[j] < arrI) {
p[i] = j
result.push(i)
continue
}
u = 0
v = result.length - 1
while (u < v) {
c = (u + v) >> 1
if (arr[result[c]] < arrI) {
u = c + 1
} else {
v = c
}
}
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1]
}
result[u] = i
}
}
}
u = result.length
v = result[u - 1]
while (u-- > 0) {
result[u] = v
v = p[v]
}
return result
}
最后
在渲染更新过程中，普通元素类型下的子节点为新旧数组之间的更新较为复杂。而这篇文章这块内容其实主要的便是对patchKeyChildren函数的讲解，讲解了在子节点中新旧数组对比的几个类型，和处理方法，从头部同步遍历和尾部同步遍历开始处理，根据不同情况，如
- 新数组和旧数组同步完成（指旧子节点都能在新子节点中找到），若是新子节点有富裕则，说明多出来的节点需要新增。
- 若是旧子节点有多余，则说明旧子节点多出来的节点需要删除。
- 若是头尾同步完之后，新旧数组都没有遍历完，说明存在未知序列，则需要对未知序列进行不同情况的判断
- 先通过数组索引值，查看旧子节点是否存在于新节点，若是存在得出在新子节点数组中的位置，若是不存在，则说明不存在于新数组中，需要删除改子节点。
- 然后通过新旧子节点索引映射，获取最长递增子序列，该子序列能有助于最低成本的移动节点，提高效率。
- 倒序遍历新未知子序列，结合新旧子节点索引映射和递增最长子序列，安装新增的子节点，和移动位置发生变化的子旧节点。
以上便是写在源码上官方的注释文档举例，这篇文章想要讲的主要内容便已经结束了，然后细心的读者可以发现，这个例子中的并没有体现出，旧节点的移除，多个连续旧节点与新节点相同从而不需要移动的情况，接下来就举个例子简单的跑个流程，可以更好的印证一下。
个人举例的新旧数组之间的比对（可忽略）
头尾进行遍历，进行上面的步骤1和2。将相同key相同类型的节点进行patch安装。因为新旧数组节点各自并没有遍历完，因此不会触发上面步骤3和步骤4的逻辑，而是直接进入5的逻辑未知序列
5.1 建立key对应新子节点的索引映射 keyToNewIndexMap={d:2,e:3,c:4,h:5}
5.2 建立新旧节点索引映射 newIndexToOldIndexMap简单逻辑展示，并且卸载不存在于新数组中的节点k。
keyToNewIndexMap = { e:2,d:3,c:4,h:5 }//之前得出的新未知序列数组
toBePatched = 4 //需要patch的长度
newIndexToOldIndexMap = [ 0 , 0 , 0 , 0 ] //每个元素的初始值为0
s1,s2=2
e1=5
for (i = 2 ; i <= 5; i++)//for (i = s1; i <= e1; i++) 正序遍历旧未知序列节点
prevChild = c //旧未知序列节点第一个
newIndex = 4 //位于新节点索引4
newIndexToOldIndexMap[4-2]=2+1//newIndexToOldIndexMap[newIndex - s2] = i + 1
newIndexToOldIndexMap[2]=3 //[0,0,3,0]
maxNewIndexSofar= 4
patch(c,c2[4])
i = 3 //遍历增加
prevChild = k
newIndex = undefined
unmount(k)
i = 4
prevChild = d
newIndex = 2
newIndexToOldIndexMap[0]=5 //[5,0,3,0]
maxNewIndexSofar= 4
if(newIndex >= maxNewIndexSoFar) //false
move = true
patch(d,c2[2])
i = 5
prevChild = e
newIndex = 3
newIndexToOldIndexMap[1]=6 //[5,6,3,0]
patch(e,c2[3])
//结束循环
newIndexToOldIndexMap = [5,6,3,0]//说明h节点是需要创建的真实节点
5.3 获取到newIndexToOldIndexMap=[5,6,3,0]后，便可以通过increasingNewIndexSequence = getSequence(newIndexToOldIndexMap)得到了最长递增子序列 ，用于移动和安装新增的节点。
转载自:https://juejin.cn/post/7211800391012417592