VUE DIFF算法之快速DIFF

VUE DIFF算法系列讲解

VUE 简单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);// 更新VNodej++;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);// 更新VNodeoldEnd--;newEnd--;oldVNode = oldChildren[oldEnd];newVNode = newChildren[newEnd];
}
// 预处理结束后// 预处理结束会有三种情况：1.新子节点有剩余；2.旧街店有剩余；3:新旧节点均有剩余
if (j > oldEnd && j <= newEnd) {// 如果新子节点有剩余// 获取锚点idlet 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);// 新旧子节点的起始indexconst 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;// 填充sourcefor (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      kp-2          0         3
k !== undefined patched++ pos=k i++
source = [-1, -1, 1, -1]
// 第二次循环 i = 2; oldEnd = 4; count = 4; pos = 3
oldVNode    patched      kp-3          1         1
k !== undefined patched++ moved = true
source = [2, -1, 1, -1]
// 第三次循环 i = 3; oldEnd = 4; count = 4; 因moved为true,所以不再需要关心pos
oldVNode    patched      kp-4          2         2
k !== undefined patched++ 
source = [2, 3, 1, -1]
// 第四次循环 i = 4; oldEnd = 4; count = 4; 
oldVNode    patched      kp-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