VUE DIFF算法之双端DIFF
东郭元魁
VUE DIFF系列讲解
前言
本文主要讲解下双端diff, 双端diff是vue2中所用的diff算法，也是目前绝大部份面试中，大家对于vue diff回答较常用的答案。再最近的几次面试中，发现很多中级前端开发工程师，只能很模糊的描述下基本的想法，一旦给出一个具体实例进行分析，就露馅了。所以我们接下来，跟着简单的代码及demo, 再对双端diff，进行一个深入的复习
一、双端DIFF的代码实现
提示：不需要特别关注patch等函数的实现，和diff的关系不是很大。理解其大致想做的事即可，具体模拟实现可参考文末github链接
话不多说，我们直接上代码：
// 从n1和n2中分别取到oldChildren和newChildren
const oldChildren = n1.children;
const newChildren = n2.children;
// 获取四个索引值
let oldStartIdx = 0;
let oldEndIdx = oldChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = newChildren.length - 1;
// 获取到四个索引值指向的vnode
let oldStartVNode = oldChildren[oldStartIdx];
let oldEndVNode = oldChildren[oldEndIdx];
let newStartVNode = newChildren[newStartIdx];
let newEndVNode = newChildren[newEndIdx];
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 在双端匹配没有匹配上的时候，会用新的startVNode在旧的里边找，如果找到了，则会把对应vnode移走，并把对应位置置为undefined，所以oldChildren某些位置会为undefined.以下!oldStartVNode和!oldEndVNode就是对上述所说情况的处理
if (!oldStartVNode) {
oldStartVNode = oldChildren[++oldStartIdx];
} else if (!oldEndVNode) {
oldEndVNode = oldChildren[--oldEndIdx];
} else if (oldStartVNode.key === newStartVNode.key) {
// 如果首和首相等，则说明位置没有变，仅需要打补丁
patch(oldStartVNode, newStartVNode, container);
// 更新索引及对应的VNode
oldStartVNode = oldChildren[++oldStartIdx];
newStartVNode = newChildren[++newStartIdx];
} else if (oldEndVNode.key === newEndVNode.key) {
// 如果尾和尾相等，则说明位置没有变，仅需要打补丁
patch(oldEndVNode, newEndVNode, container);
// 更新索引及对应的VNode
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key === newEndVNode.key) {
// 打补丁
patch(oldStartVNode, newEndVNode, container);
// 如果oldChildren中的第一个是newChildre最后一个,则需要把oldChildren的第一个移到最后
insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);
// 更新索引及对应VNode
newEndVNode = newChildren[--newEndIdx];
oldStartVNode = oldChildren[++oldStartIdx];
} else if (oldEndVNode.key === newStartVNode.key) {
// 打补丁
patch(oldEndVNode, newStartVNode, container);
// 如果oldChildren的最后一个是newChildren的第一个，则需要把oldChildren的第一个移到开始
insert(oldEndVNode.el, container, oldStartVNode.el);
// 更新索引及对应VNode
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
// 如果双端匹配没有找到，需要从newChildren中取出第一个，去oldChildren中进行匹配
const idxInOld = oldChildren.findIndex(node => node.key === newStartVNode.key);
if (idxInOld > 0) {
// 需要移动到节点
const vnodeToMove = oldChildren[idxInOld];
// 打补丁
patch(vnodeToMove, newStartVNode, container);
// 如果找到了，说明oldIdx对应的VNode已经移动到首位
insert(vnodeToMove.el, container, oldStartVNode.el);
// 将oldChildren的对应位置，置为undefinde
oldChildren[idxInOld] = undefined;
} else {
// 没有找到，则说明是新增节点，则挂载到对应位置
const anchor = oldStartVNode.el;
patch(null, newStartVNode, container, anchor);
}
// 更新索引及对应VNode
newStartVNode = newChildren[++newStartIdx];
}
}
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
// 这种情况说明newChildren中有节点没有被遍历到，需要将未被遍历到到节点新增
for (let i = newStartIdx; i <= newEndIdx; i++) {
// 使用oldStartVNode才能保证不论新增遗留节点在最上/最下，放置的位置是正确的
patch(null, newChildren[i], container, oldStartVNode.el);
}
} else if (newStartIdx > newEndIdx && oldStartIdx <= oldEndIdx) {
// 这种情况说明旧的节点还有没有匹配上的，则需要把没有匹配的节点卸载
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
unmount(oldChildren[i]);
}
}
二、实践
练习1
// 旧子节点
p-1 p-2 p-3
// 新子节点
p-4 p-2 p-1 p-3
// 获取四个索引值
let oldStartIdx = 0
let oldEndIdx = 2
let newStartIdx = 0
let newEndIdx = 3
// 获取到四个索引值指向的vnode
let oldStartVNode = p-1
let oldEndVNode = p-3
let newStartVNode = p-4
let newEndVNode = p-3
// 进入双端循环对比
oldStartIdx(0) newStartIdx(0) 是否相等
p-1 p-4 false
oldEndIdx(2) newEndIdx(3) 是否相等
p-3 p-3 ture
因为 oldEndVNode.key === newEndVNode.key，既尾尾相等，仅进行patch，不需要移动。然后更新新旧idx及vnode
此时，真实节点为 p-1 p-2 p-3
oldEndIdx = 1 newEndIdx = 2
oldEndVNode = p-2 newEndIdx = p-1
oldStartIdx(0) newStartIdx(0) 是否相等
p-1 p-4 false
oldEndIdx(1) newEndIdx(2) 是否相等
p-2 p-1 false
oldStartIdx(0) newEndIdx(2) 是否相等
p-1 p-1 ture
因为 oldStartVNode.key === newEndVNode.key, 即首尾相等，需要进行移动。因为oldStartVNode在新的中，变成了尾部节点，所以此时锚点为oldEndVNode.el.nextSibling
此时，真实节点为 p-2 p-1 p-3
oldStartIdx = 1 newEndIdx = 1
oldStartVNode = p-2 newEndIdx = p-2
oldStartIdx(1) newStartIdx(0) 是否相等
p-2 p-4 false
oldEndIdx(1) newEndIdx(1) 是否相等
p-2 p-2 true
因为 oldEndVNode.key === newEndVNode.key, 即尾尾相等，不需要移动
此时，真实节点为 p-2 p-1 p-3
oldEndIdx = 0 newEndIdx = 0
oldEndVNode = undefinde newEndIdx = p-4
因oldEndIdx < oldStartIdx,所以跳出while循环
此时oldEndIdx(0) < oldStartIdx(1) && newStartIdx(0) <= newEndIdx(0),所以新的子节点未被遍历完，循环新的子节点，进行挂载
newStartIdx(0) 此时对应子节点p-4 锚点为oldStartVNode.el
最终，真实节点为 p-4 p-2 p-1 p-3
2. 练习2
// 旧子节点
p-1 p-2 p-3
// 新子节点
p-4 p-1 p-3 p-2
// 获取四个索引值
let oldStartIdx = 0
let oldEndIdx = 2
let newStartIdx = 0
let newEndIdx = 3
// 获取到四个索引值指向的vnode
let oldStartVNode = p-1
let oldEndVNode = p-3
let newStartVNode = p-4
let newEndVNode = p-2
// 进入双端循环对比
oldStartIdx(0) newStartIdx(0) 是否相等
p-1 p-4 false
oldEndIdx(2) newEndIdx(3) 是否相等
p-3 p-2 false
oldStartIdx(0) newEndIdx(3) 是否相等
p-1 p-2 false
oldEndIdx(2) newStartIdx(0) 是否相等
p-1 p-4 false
因双端对比发现没有相同的，则从旧节点中遍历寻找newStartVNode, 发现找不到，则新增newStartVNode，锚点为oldStartVNode
此时，真实顺序为 p-4 p-1 p-2 p-3
更新idx及vnode
newStartIdx = 1
newStartVNode = p-1
//继续双端循环
oldStartIdx(0) newStartIdx(1) 是否相等
p-1 p-1 true
因为 oldStartVNode.key === newStartVNode.key，既首首相等，仅进行patch，不需要移动。
此时，真实顺序为 p-4 p-1 p-2 p-3
更新idx及vnode
oldStartIdx = 1 newStartIdx = 2
oldStartVNode = p-2 newEndIdx = p-3
//继续双端循环
oldStartIdx(1) newStartIdx(2) 是否相等
p-1 p-4 false
oldEndIdx(2) newEndIdx(3) 是否相等
p-3 p-2 false
oldStartIdx(1) newEndIdx(3) 是否相等
p-2 p-2 ture
因为 oldStartVNode.key === newEndVNode.key, 即首尾相等，需要进行移动。因为oldStartVNode在新的中，变成了尾部节点，所以此时锚点为oldEndVNode.el.nextSibling
此时，真实节点为 p-4 p-1 p-3 p-2
oldStartIdx = 2 newEndIdx = 2
oldStartVNode = p-3 newEndVNode = p-2
//继续双端循环
oldStartIdx(2) newStartIdx(2) 是否相等
p-3 p-3 true
因为 oldStartVNode.key === newStartVNode.key，既首首相等，仅进行patch，不需要移动。
此时，真实顺序为 p-4 p-1 p-3 p-2
更新idx及vnode
oldStartIdx = 3 newStartIdx = 3
oldStartVNode = undefined newStartIdx = p-2
因为oldStartIdx(3) > oldEndIdx(2) && newStartIdx(3) > newEndIdx(2),所以结束循环，此时新旧节点均为又遗留，对比完成
总结
双端DIFF作为面试中出现频率较高的知识点，原理并不难，主要理解的多为一下三部分
- 双端的遍历规则：即首(old)首(new)、尾(old)尾(new)、首(old)尾(new)、尾(old)首(new)对比
- 上述遍历规则无可复用节点的处理情况
- 需要进行挂载/移动时，锚点的选取规则
只要能真正理解上述情况，面试你就成功了
参考：<<vue设计与实现>>第10章
github：link
类似资料：