VUE DIFF算法之快速DIFF
崔宜修
VUE DIFF算法系列讲解
前言
本节我们来写一下VUE3中新的DIFF算法-快速DIFF，顾名思义，也就是目前最快的DIFF算法（在VUE中）
本节内容值包括快速DIFF算法的实现，不考虑最长递增子序列算法的实现
一、快速DIFF的代码实现
相对于我们此系列的前两种DIFF算法，此DIFF算法在进入真正的DIFF算法之前，会有一个预处理的过程，这个主要是借鉴了纯文本Diff算法的思想。下边，我们就直接通过代码看下整个Diff的实现流程。
const oldChildren = n1.children;
const newChildren = n2.children;
// 预处理开始
// 处理新旧子节点的头部可复用节点
let j = 0;
let oldVNode = oldChildren[j];
let newVNode = newChildren[j];
while (oldVNode.key === newVNode.key) {
// 打补丁
patch(oldVNode, newVNode, container);
// 更新VNode
j++;
oldVNode = oldChildren[j];
newVNode = newChildren[j];
}
// 处理新旧节点尾部可复用节点, 因为新旧子节点长度可能不一致，所以需要定义两个变量
let oldEnd = oldChildren.length - 1;
let newEnd = newChildren.length - 1;
oldVNode = oldChildren[oldEnd];
newVNode = newChildren[newEnd];
while (oldVNode.key === newVNode.key) {
// 打补丁
patch(oldVNode, newVNode, container);
// 更新VNode
oldEnd--;
newEnd--;
oldVNode = oldChildren[oldEnd];
newVNode = newChildren[newEnd];
}
// 预处理结束后
// 预处理结束会有三种情况：1.新子节点有剩余；2.旧街店有剩余；3:新旧节点均有剩余
if (j > oldEnd && j <= newEnd) {
// 如果新子节点有剩余
// 获取锚点id
let anchorIdx = newEnd + 1;
// 获取锚点node，如果
let anchor = anchorIdx === newChildren.length ? newChildren[anchorIdx].el : null;
while (j <= newEnd) {
// 挂载
patch(null, newChildren[j++], container, anchor);
}
} else if (j > newEnd && j <= oldEnd) {
// 如果旧节点有剩余，则需要卸载
while (j <= oldEnd) {
unmount(oldChildren[j++]);
}
} else {
// 如果新旧节点均有剩余
// 构造source数组
const count = newEnd - j + 1;
let source = new Array(count);
source.fill(-1);
// 新旧子节点的起始index
const oldStart = j;
const newStart = j;
let pos = 0;
let moved = false;
// 构建新子节点的{key: index} 对象
const keyIndex = {};
for (let i = newStart; i < newEnd; i++) {
keyIndex[newChildren[i].key] = i;
}
// 保存已被处理过的旧子节点数
let patched = 0;
// 填充source
for (let i = oldStart; i <= oldEnd; i++) {
oldVNode = oldChildren[i];
if (patched <= count) {
const k = keyIndex[oldVNode.key];
if (k !== undefined) {
// 打补丁
newVNode = newChildren[i];
patch(oldVNode, newVNode, container);
patched++;
source[k - newStart] = i;
if (k < pos) {
moved = true;
} else {
pos = k;
}
} else {
// 没有找到，卸载
unmount(oldChildren[i]);
}
} else {
// 处理数已等于新子节点数，其余卸载
unmount(oldChildren[i]);
}
}
// 如果需要移动
if (moved) {
const seq = lis(source);
let s = seq.length - 1;
let i = count - 1;
for (i; i >= 0; i--)
if (source[i] === -1) {
// 这种情况属于新增
const pos = i + newStart;
const newVNode = newChildren[pos];
// 获取锚点的索引
const newPos = pos + 1;
// 锚点
const anchor = newPos < newChildren.length ? newChildren[newPos] : null;
// 挂载
patch(null, newVNode, container, anchor);
} else if (seq[s] !== i) {
// 这种情况需要移动
const pos = i + newStart;
const newVNode = newChildren[pos];
// 获取锚点的索引
const newPos = pos + 1;
// 锚点
const anchor = newPos < newChildren.length ? newChildren[newPos] : null;
// 挂载
insert(newVNode, container, anchor);
} else {
// 当 i === seq[j] 时，说明该位置的节点不需要移动
// 并让 s 指向下一个位置
s--;
}
}
}
二、实践
练习1
// 旧子节点
p-1 p-2 p-3
// 新子节点
p-1 p-3
// 预处理开始
// while循环对比，预处理头部可服用量节点
let j = 0
newVNode = p-1
oldVNode = p-1
// 第一次循环 j=0
newVNode.key === oldVNode.key 可复用 j++
newVNode = p-2
oldVNode = p-3
// 第二次循环
newVNode.key ！== oldVNode.key 跳出循环
// while循环对比，预处理尾部可服用量节点
let oldEnd = 2(oldChildren.length - 1);
let newEnd = 1(newChildren.length - 1);
oldVNode = p-3(oldChildren[oldEnd]);
newVNode = p-3(newChildren[newEnd]);
// 第一次循环 oldEnd=2 newEnd=1
newVNode.key === oldVNode.key 可复用 oldEnd-- newEnd--
newVNode = p-2
oldVNode = p-1
// 第二次循环 oldEnd=1 newEnd=0
newVNode.key ！== oldVNode.key 跳出循环
// 预处理结束
// 预处理结束，此时j(1)>newEnd(0) && j(1)<=oldEnd(1),说明旧的子节点有剩余，仅需要将剩余子节点卸载即可
练习2
// 旧子节点
p-1 p-2 p-3 p-4 p-6 p-5
// 新子节点
p-1 p-3 p-4 p-2 p-7 p-5
// 预处理开始
// while循环对比，预处理头部可服用量节点
let j = 0
newVNode = p-1
oldVNode = p-1
// 第一次循环 j=0
newVNode.key === oldVNode.key 可复用 j++
newVNode = p-2
oldVNode = p-3
// 第二次循环
newVNode.key ！== oldVNode.key 跳出循环
// while循环对比，预处理尾部可服用量节点
let oldEnd = 5(oldChildren.length - 1);
let newEnd = 5(newChildren.length - 1);
oldVNode = p-5(oldChildren[oldEnd]);
newVNode = p-5(newChildren[newEnd]);
// 第一次循环 oldEnd=2 newEnd=1
newVNode.key(p-5) === oldVNode.key(p-5) 可复用 oldEnd-- newEnd--
newVNode = p-7
oldVNode = p-6
// 第二次循环 oldEnd=4 newEnd=4
newVNode.key ！== oldVNode.key 跳出循环
// 预处理结束
// 此时真实dom节点如下
p-1(✅) p-2 p-3 p-4 p-6 p-5(✅)
// 待处理
p-2 p-3 p-4 p-6
---------------------------------------------
// 预处理结束，此时j(1)<=newEnd(4) && j(1)<=oldEnd(4),说明新旧的子节点有剩余，此时我们需要构建一个sourece数组，这个数组长度为新子节点在预处理后剩余未处理的节点数，并且初始值为-1
// 新子节点未处理完的节点数
const count = newEnd - j + 1;
// 构建source数组
let source = new Array(count);
source.fill(-1);
// 定义新旧子节点的起始index
const oldStart = j(1);
const newStart = j(1);
// 定义在旧子节点便利过程中遇到的最大的索引值
let pos = 0;
// 代表是否需要移动节点
let moved = false;
// 定义一个数量表示，表示已经处理过的子节点数.如果已处理过的子节点数超过新子节点数，则表示其余的为多余节点，直接卸载
let patched = 0
// 构建一个索引表，此表内存储新子节点中，key与index的映射
keyIndex = {
p-3 : 1，
p-4 : 2，
p-2 : 3,
p-7 : 4
}
// 填充source数组并处理多余oldVNode
// 开始循环
// 第一次循环 i(oldStart) = 1; oldEnd = 4; count = 4; pos = 0；
oldVNode patched k
p-2 0 3
k !== undefined patched++ pos=k i++
source = [-1, -1, 1, -1]
// 第二次循环 i = 2; oldEnd = 4; count = 4; pos = 3
oldVNode patched k
p-3 1 1
k !== undefined patched++ moved = true
source = [2, -1, 1, -1]
// 第三次循环 i = 3; oldEnd = 4; count = 4; 因moved为true,所以不再需要关心pos
oldVNode patched k
p-4 2 2
k !== undefined patched++
source = [2, 3, 1, -1]
// 第四次循环 i = 4; oldEnd = 4; count = 4;
oldVNode patched k
p-6 3 undefined
k === undefined 卸载
source = [2, 3, 1, -1]
// 第四次循环 i = 5; oldEnd = 4; i > oldEnd 跳出循环
// 此时真实dom节点如下
p-1(✅) p-2 p-3 p-4 p-6(❌) p-5(✅)
// 待处理
p-2 p-3 p-4
---------------------------------------------------------
// 因moved为true,所以需要进行移动
// 构建一个最长递增子序列（此节中暂不考虑最长递增子序列算法）
const seq = [0, 1]
// 定义s, 其值为最长递增子序列的最大index
let s = 1
// 定义i, 其值为source的最大index
let i = 3
// 开始循环
// 第一次循环 i = 3;
source[3] = -1, 则此节点为新增节点，需要挂载，锚点为p-5
// 此时真实dom节点如下
p-1(✅) p-2 p-3 p-4 p-7(✅) p-5(✅)
// 第二次循环 i = 2;
source[2] = 1,
seq[1] !== 2 此节点需要移动, 锚点为p-7
// 此时真实dom节点如下
p-1(✅) p-3 p-4 p-2(✅) p-7(✅) p-5(✅)
// 第三次循环 i = 1;
source[1] = 3,
seq[1] === 1 此节点不需要移动 s--
// 此时真实dom节点如下
p-1(✅) p-3 p-4(✅) p-2(✅) p-7(✅) p-5(✅)
// 第四次循环 i = 0;
source[0] = 2,
seq[0] === 0 此节点不需要移动
// 此时真实dom节点如下
p-1(✅) p-3(✅) p-4(✅) p-2(✅) p-7(✅) p-5(✅)
总结
快速Diff算法的整体逻辑还是比较容易理解的，其中比较巧妙的是预处理和source的用法。学习快速Diff算法不仅让我们更深刻的了解了VUE3，同时其中的一些核心逻辑，也可以为我们的日常开发工作中提供一些开发思路。
参考：<<vue设计与实现>>第10章
github：link
类似资料：