【Vue.js设计与实现】第三篇第11章：渲染器-快速 Diff 算法-阅读笔记

系列目录：【Vue.js设计与实现】阅读笔记目录

非常快的Diff算法。

11.1　相同的前置元素和后置元素

不同于简单 Diff 算法和双端 Diff 算法，快速 Diff 算法包含预处理步骤，这其实是借鉴了纯文本 Diff 算法的思路。

首先，进行全等比较，若全等就不用Diff了：

if(text1 === text2) return

再进行预处理，处理相同的前缀和后缀，如图：

const patchKeyedChildren = (n1, n2, container) => {const newChildren = n2.children;const oldChildren = n1.children;// 处理相同前置节点，j指向新旧两组子节点的开头let j = 0;let oldVNode = oldChildren[j];let newVNode = newChildren[j];// 直到遇到不同key值节点为止while (oldVNode.key === newVNode.key) {patch(oldVNode, newVNode, container);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);oldEnd--;newEnd--;oldVNode = oldChildren[oldEnd];newVNode = newChildren[newEnd];}
};

预处理相同前后缀后：

可以发现，还遗留了一个未处理的p-4节点。我们可以很容易看出来这是一个新增节点，但是，如何得出这是新增节点的结论？

我们需要观察三个索引j、newEnd、oldEnd之间的关系：

• 条件1 oldEnd<j 成立，说明在预处理过程中，所有旧节点都处理完毕了（开头的j>结尾的oldEnd）
• 条件2 newEnd>=j成立，说明在预处理后，新节点中，有未处理的节点，即新增节点

因此，索引值在j和newEnd之间的节点都要作为新节点挂载：

// 预处理完毕// 挂载新节点
if (j > oldEnd && j <= newEnd) {const anchorIndex = newEnd + 1;const anchor =anchorIndex < newChildren.length? newChildren[anchorIndex].el: null;while (j <= newEnd) {patch(null, newChildren[j++], container, anchor);}
}

以上是新增节点的情况，接下来是删除节点的情况。

条件是：j > newEnd && j <= oldEnd

要卸载j-oldEnd的节点（由图知，从上到下是从小到大）

// 预处理完毕// 挂载新节点
if (j > oldEnd && j <= newEnd) {const anchorIndex = newEnd + 1;const anchor =anchorIndex < newChildren.length? newChildren[anchorIndex].el: null;while (j <= newEnd) {patch(null, newChildren[j++], container, anchor);}
} else if (j > newEnd && j <= oldEnd) {// 卸载旧节点while (j <= oldEnd) {unmount(oldChildren[j++]);}
}

11.2　判断是否需要进行 DOM 移动操作

前面的例子都是理想状况：去掉前后缀后，只需要简单的新增/移除。实际上，还会出现不理想的情况，如：

处理完前后缀后，还需要更多的处理。

其实，不管是简单Diff、双端Diff，还是快速Diff，他们的处理规则都相同：

• 判断是否有节点需要移动，以及如何移动
• 找出那些需要被添加或移除的节点

接下来我们将判断哪些节点要移动，以及如何移动。处理完前后缀后，我们会发现j、newEnd和oldEnd不满足上述的两种条件（新增/移除）：

• j > oldEnd && j <= newEnd
• j > newEnd && j <= oldEnd

因此，我们需要新增一个else来处理这种情况。

首先，我们需要构造一个数组source，它的长度等于新的一组子节点在经过预处理之后剩余未处理节点的数量，并且 source 中每个元素的初始值都是 -1。

source 数组将用来存储新的一组子节点中的节点在旧的一组子节点中的位置索引，后面将会使用它计算出一个最长递增子序列，并用于辅助完成 DOM 移动的操作：

else {// 构造source数组// 新的一组子节点中剩余未处理节点的数量const count = newEnd - j + 1;const source = new Array(count);source.fill(-1);// source节点存储新节点在旧节点的索引const oldStart = j;const newStart = j;for (let i = oldStart; i <= oldEnd; i++) {const oldVNode = oldChildren[i];// 找到具有相同key的可复用节点for (let k = newStart; k <= newEnd; k++) {const newVNode = newChildren[k];if (oldVNode.key === newVNode.key) {patch(oldVNode, newVNode, container);source[k - newStart] = i;}}}
}

source数组如下：

这里需要注意的是，由于数组 source 的索引是从 0 开始的，而未处理节点的索引未必从 0 开始，所以在填充数组时需要使用表达式 k - newStart的值作为数组的索引值。外层循环的变量 i 就是当前节点在旧的一组子节点中的位置索引，因此直接将变量 i 的值赋给 source[k - newStart] 即可。

相当于都偏移 k - newStart。

不过，上述代码是双层嵌套的循环，复杂度可能太高了，我们得优化一下：我们可以为新的一组子节点构建一张索引表，用来存储节点的 key 和节点位置索引之间的映射。

这样就不用循环寻找了，直接在索引表新节点 key->i中里拿。

// 构建索引表:新节点 key->i
const keyIndex = {};
for (let i = newStart; i <= newEnd; i++) {keyIndex[newChildren[i].key] = i;
}

双层循环就可以改为一层循环：

若k存在，说明旧节点在新节点中存在，可以复用，否则卸载。

// 构建索引表:新节点 key->i
const keyIndex = {};
for (let i = newStart; i <= newEnd; i++) {keyIndex[newChildren[i].key] = i;
}for (let i = oldStart; i <= oldEnd; i++) {const oldVNode = oldChildren[i];const k = keyIndex[oldVNode.key];if (typeof k !== "undefined") {newVNode = newChildren[k];patch(oldVNode, newVNode, container);source[k - newStart] = i;} else {// 不存在，说明旧节点在新节点中不存在，卸载unmount(oldVNode);}
}

接下来我们将判断是否需要移动，与简单Diff相同，找递增的索引，递增的索引不需要移动。 否则需要，新增moved 和pos ：

let moved = false;
let pos = 0;const keyIndex = {};
for (let i = newStart; i <= newEnd; i++) {keyIndex[newChildren[i].key] = i;
}for (let i = oldStart; i <= oldEnd; i++) {const oldVNode = oldChildren[i];const k = keyIndex[oldVNode.key];if (typeof k !== "undefined") {newVNode = newChildren[k];patch(oldVNode, newVNode, container);source[k - newStart] = i;// 判断节点是否需要移动:找递增的索引，若存在小于递减的索引，说明要移动if (k < pos) {moved = true;} else {pos = k;}} else {unmount(oldVNode);}
}

除此之外，我们还需要一个数量标识，代表已经更新过的节点数量。我们知道，已经更新过的节点数量应该小于新的一组子节点中需要更新的节点数量。一旦前者超过后者，则说明有多余的节点，我们应该将它们卸载。

count就是需要更新的节点数量。新增一个patched表示已更新过的节点数量：

// 记录更新过的节点数量
let patched = 0;for (let i = oldStart; i <= oldEnd; i++) {const oldVNode = oldChildren[i];// 如果更新过的节点数量小于需要更新的节点数量，则更新if (patched <= count) {const k = keyIndex[oldVNode.key];if (typeof k !== "undefined") {newVNode = newChildren[k];patch(oldVNode, newVNode, container);source[k - newStart] = i;patched++;if (k < pos) {moved = true;} else {pos = k;}} else {unmount(oldVNode);}} else {// 如果更新过的节点数量大于需要更新的节点数量，则卸载多余节点unmount(oldVNode);}
}

完整代码：

const patchKeyedChildren = (n1, n2, container) => {const newChildren = n2.children;const oldChildren = n1.children;// 处理相同前置节点，j指向新旧两组子节点的开头let j = 0;let oldVNode = oldChildren[j];let newVNode = newChildren[j];// 直到遇到不同key值节点为止while (oldVNode.key === newVNode.key) {patch(oldVNode, newVNode, container);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);oldEnd--;newEnd--;oldVNode = oldChildren[oldEnd];newVNode = newChildren[newEnd];}// 预处理完毕// 挂载新节点if (j > oldEnd && j <= newEnd) {const anchorIndex = newEnd + 1;const anchor =anchorIndex < newChildren.length? newChildren[anchorIndex].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;const source = new Array(count);source.fill(-1);const oldStart = j;const newStart = j;let moved = false;let pos = 0;const keyIndex = {};for (let i = newStart; i <= newEnd; i++) {keyIndex[newChildren[i].key] = i;}// 记录更新过的节点数量let patched = 0;for (let i = oldStart; i <= oldEnd; i++) {const oldVNode = oldChildren[i];// 如果更新过的节点数量小于需要更新的节点数量，则更新if (patched <= count) {const k = keyIndex[oldVNode.key];if (typeof k !== "undefined") {newVNode = newChildren[k];patch(oldVNode, newVNode, container);source[k - newStart] = i;patched++;if (k < pos) {moved = true;} else {pos = k;}} else {unmount(oldVNode);}} else {// 如果更新过的节点数量大于需要更新的节点数量，则卸载多余节点unmount(oldVNode);}}}
};

11.3　如何移动元素

接下来，我们讨论如何进行DOM移动操作。我们有source索引数组：[2,3,1,-1]

我们要找source的最长递增子序列，它是[2,3]，对应的索引是[0,1]。我们重新编号。

在新的一组子节点中，重新编号后索引值为0和1的这两个节点在更新前后顺序没有变化。

即旧节点的p-3和p-4不需要移动。

为了完成节点的移动，我们还需要创建两个索引值i和s：

• i指向新的一组子节点中的最后一个节点
• s指向最长递增子序列中的最后一个元素，即上述的[0,1]的1

如上图所示，我们去掉了旧的一组子节点和无关的线条、变量。

我们开启一个for循环，让i和s按照如图所示的方向移动：

// DOM 移动操作
if (moved) {// 计算最长递增子序列 的 索引const seq = lis(source);// s指向最长递增子序列的最后一个元素let s = seq.length - 1;// i指向新一组节点的最后一个元素let i = count - 1;for (i; i >= 0; i--) {if (i !== seq[s]) {// 说明该节点需要移动} else {s--;}}
}

我们按照这样的思路更新：判断条件 i !== seq[s]​，如果节点的索引 i 不等于 seq[s]的值，则说明该节点对应的真实 DOM 需要移动。

如图所示，还要考虑source[i]=-1的情况，说明这是一个全新节点，需要挂载：

if (source[i] === -1) {// 说明是新节点，要挂载const pos = i + newStart; // 在新children中的真实位置索引const newVNode = newChildren[pos];// 该节点的下一个节点的位置索引const nextPos = pos + 1;const anchor =nextPos < newChildren.length? newChildren[nextPos].el: null;patch(null, newVNode, container, anchor);
}

挂载完后，i--，往上走：

进行上述2个判断：

• source[i]是否为-1？不是的，说明不是一个新节点
• i!==seq[s]？成立。说明此节点需要移动。下面不需要判断了

移动节点的实现思路类似于挂载全新节点，不同点在于，移动节点是通过insert函数完成的：

else if (i !== seq[s]) {// 说明该节点需要移动// 该节点在新节点中的真是位置索引const pos = i + newStart;const newVNode = newChildren[pos];const nextPos = pos + 1;const anchor =nextPos < newChildren.length? newChildren[nextPos].el: null;// 移动insert(newVNode.el, container, anchor);
} 

实现完后，状态如下：

进行2个判断：

• source[i]是否为-1？不是的，说明不是一个新节点
• i!==seq[s]？不是的，说明它不需要移动
• 不需要移动，s--即可

状态如下：

进行三个判断，得到，s–

然后就结束了。

关于获取最长递增子序列，可以自行搜索。

move相关代码：

// DOM 移动操作
if (moved) {// 计算最长递增子序列 的 索引const seq = lis(source);// s指向最长递增子序列的最后一个元素let s = seq.length - 1;// i指向新一组节点的最后一个元素let i = count - 1;for (i; i >= 0; i--) {if (source[i] === -1) {// 说明是新节点，要挂载const pos = i + newStart; // 在新children中的真实位置索引const newVNode = newChildren[pos];// 该节点的下一个节点的位置索引const nextPos = pos + 1;const anchor =nextPos < newChildren.length? newChildren[nextPos].el: null;patch(null, newVNode, container, anchor);} else if (i !== seq[s]) {// 说明该节点需要移动// 该节点在新节点中的真是位置索引const pos = i + newStart;const newVNode = newChildren[pos];const nextPos = pos + 1;const anchor =nextPos < newChildren.length? newChildren[nextPos].el: null;// 移动insert(newVNode.el, container, anchor);} else {s--;}}
}

完整代码：

const patchKeyedChildren = (n1, n2, container) => {const newChildren = n2.children;const oldChildren = n1.children;// 处理相同前置节点，j指向新旧两组子节点的开头let j = 0;let oldVNode = oldChildren[j];let newVNode = newChildren[j];// 直到遇到不同key值节点为止while (oldVNode.key === newVNode.key) {patch(oldVNode, newVNode, container);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);oldEnd--;newEnd--;oldVNode = oldChildren[oldEnd];newVNode = newChildren[newEnd];}// 预处理完毕// 挂载新节点if (j > oldEnd && j <= newEnd) {const anchorIndex = newEnd + 1;const anchor =anchorIndex < newChildren.length? newChildren[anchorIndex].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;const source = new Array(count);source.fill(-1);const oldStart = j;const newStart = j;let moved = false;let pos = 0;const keyIndex = {};for (let i = newStart; i <= newEnd; i++) {keyIndex[newChildren[i].key] = i;}// 记录更新过的节点数量let patched = 0;for (let i = oldStart; i <= oldEnd; i++) {const oldVNode = oldChildren[i];// 如果更新过的节点数量小于需要更新的节点数量，则更新if (patched <= count) {const k = keyIndex[oldVNode.key];if (typeof k !== "undefined") {newVNode = newChildren[k];patch(oldVNode, newVNode, container);source[k - newStart] = i;patched++;if (k < pos) {moved = true;} else {pos = k;}} else {unmount(oldVNode);}} else {// 如果更新过的节点数量大于需要更新的节点数量，则卸载多余节点unmount(oldVNode);}}// DOM 移动操作if (moved) {// 计算最长递增子序列 的 索引const seq = lis(source);// s指向最长递增子序列的最后一个元素let s = seq.length - 1;// i指向新一组节点的最后一个元素let i = count - 1;for (i; i >= 0; i--) {if (source[i] === -1) {// 说明是新节点，要挂载const pos = i + newStart; // 在新children中的真实位置索引const newVNode = newChildren[pos];// 该节点的下一个节点的位置索引const nextPos = pos + 1;const anchor =nextPos < newChildren.length? newChildren[nextPos].el: null;patch(null, newVNode, container, anchor);} else if (i !== seq[s]) {// 说明该节点需要移动// 该节点在新节点中的真是位置索引const pos = i + newStart;const newVNode = newChildren[pos];const nextPos = pos + 1;const anchor =nextPos < newChildren.length? newChildren[nextPos].el: null;// 移动insert(newVNode.el, container, anchor);} else {s--;}}}}
};

11.4　总结

快速 Diff 算法在实测中性能最优。它借鉴了文本 Diff 中的预处理思路，先处理新旧两组子节点中相同的前置节点和相同的后置节点。当前置节点和后置节点全部处理完毕后，如果无法简单地通过挂载新节点或者卸载已经不存在的节点来完成更新，则需要根据节点的索引关系，构造出一个最长递增子序列。最长递增子序列所指向的节点即为不需要移动的节点。