vuejs 设计与实现 - 简单diff算法

DOM 复用与key的作用：

DOM 复用什么时候可复用？

• key 属性就像虚拟节点的“身份证”号，只要两个虚拟节点的 type属性值和 key 属性值都相同，那么我们就认为它们是相同的，即可以进行 DOM 的复用。即 我们通过【移动】来操作dom，而不是删除dom，创建dom。这样会更节省性能。

如下图展示了有key和无key时新旧两组子节点的映射情况：

如上图可知：如果没有 key，我们无法知道新子节点与旧子节点 间的映射关系，也就无法知道应该如何移动节点。有 key 的话情况则 不同，我们根据子节点的 key 属性，能够明确知道新子节点在旧子节 点中的位置，这样就可以进行相应的 DOM 移动操作了。

强调：DOM 可复用并不意味着不需要更新.如下所示的2个虚拟节点：

const oldVNode = { type: 'p', key: 1, children: 'text 1' }
const newVNode = { type: 'p', key: 1, children: 'text 2' }

这两个虚拟节点拥有相同的 key 值和 vnode.type 属性值。这意 味着， 在更新时可以复用 DOM 元素，即只需要通过移动操作来完成更 新。但仍需要对这两个虚拟节点进行打补丁操作，因为新的虚拟节点 (newVNode)的文本子节点的内容已经改变了(由’text 1’变成 ‘text 2’)。因此，在讨论如何移动DOM之前，我们需要先完成打补丁操作.

本节以下面的节点为例，进行简单diff算法：

 const oldVNode = {type: 'div',children: [{ key: 1, type: 'p', children: '1' },{ key: 2, type: 'p', children: '2' },{ key: 3, type: 'p', children: '3' },]}const newVNode = {type: 'div',children: [{ key: 3, type: 'p', children: '3' },{ key: 2, type: 'p', children: '2' },{ key: 1, type: 'p', children: '1' },]}

每一次寻找可复用的节点时，都会记录该可复用 节点在旧的一组子节点中的位置索引。

找到需要移动的元素

// 1.找到需要移动的元素
function patchChildren(n1, n2) {const oldChildren = n1.childrenconst newChildren = n2.childrenlet lastIndex = 0for (let i = 0; i < newChildren.length; i++) {const newVNode = newChildren[i]for (j = 0; j < oldChildren.length; j++) {const oldVNode = oldChildren[j]if (newVNode.key === oldVNode.key) {// 移动DOM之前，我们需要先完成打补丁操作patch(oldVNode, newVNode, container)if (j < lastIndex) {console.log('需要移动的节点', newVNode, oldVNode, j)} else {lastIndex = j}break;}}}
}
patchChildren(oldVNode, newVNode)

如何移动元素

更新的过程：

第一步:取新的一组子节点中第一个节点 p-3，它的 key 为 3，尝试在旧的一组子节点中找到具有相同 key 值的可复用节点。发现能够找到，并且该节点在旧的一组子节点中的索引为 2。此时变量 lastIndex 的值为 0，索引 2 不小于 0，所以节点 p-3 对应的真实 DOM 不需要移动，但需要更新变量 lastIndex 的值为2。

第二步:取新的一组子节点中第二个节点 p-1，它的 key 为 1，尝试在旧的一组子节点中找到具有相同 key 值的可复用节点。发
现能够找到，并且该节点在旧的一组子节点中的索引为 0。此时变量 lastIndex 的值为 2，索引 0 小于 2，所以节点 p-1 对应的真实 DOM 需要移动。

到了这一步，我们发现，节点 p-1 对应的真实 DOM 需要移动，但应该移动到哪里呢?我们知道， children的顺序其实就是更新后真实DOM节点应有的顺序。所以p-1在新children 中的位置就代表了真实 DOM 更新后的位置。由于节点p-1在新children中排在节点p-3后面，所以我们应该把节点p-1 所对应的真实DOM移到节点p-3所对应的真实DOM后面。

可以看到，这样操作之后，此时真实 DOM 的顺序为 p-2、p-3、p-1。

第三步:取新的一组子节点中第三个节点 p-2，它的 key 为 2。尝试在旧的一组子节点中找到具有相同 key 值的可复用节点。发现能够找到，并且该节点在旧的一组子节点中的索引为 1。此时变量 lastIndex 的值为 2，索引 1 小于 2，所以节点 p-2 对应的真实 DOM 需要移动。

如下图移动节点：

第三步与第二步类似，节点 p-2 对应的真实 DOM 也需要移动。 面后同样，由于节点 p-2 在新 children 中排在节点 p-1 后面，所以我们应该把节点 p-2 对应的真实 DOM 移动到节点 p-1 对应的真实DOM 后面。移动后的结果如图下图所示：

经过这一步移动操作之后，我们发现，真实 DOM 的顺序与新的一组子节点的顺序相同了:p-3、p-1、p-2。至此，更新操作完成。

function patchChildren(n1, n2) {const oldChildren = n1.childrenconst newChildren = n2.childrenlet lastIndex = 0for (let i = 0; i < newChildren.length; i++) {const newVNode = newChildren[i]for (j = 0; j < oldChildren.length; j++) {const oldVNode = oldChildren[j]if (newVNode.key === oldVNode.key) {// 移动DOM之前，我们需要先完成打补丁操作patch(oldVNode, newVNode, container)if (j < lastIndex) {// console.log('需要移动的节点', newVNode, oldVNode, j)// 如何移动元素const prevVNode = newChildren[i - 1]if (prevVNode) {// 2.找到 prevVNode 所对应真实 DOM 的下一个兄 弟节点，并将其作为锚点const anchor = prevVNode?.el?.nextSiblingconsole.log('插入', prevVNode, anchor)}} else {lastIndex = j}break;}}}
}
patchChildren(oldVNode, newVNode)

在上面这段代码中，如果条件j < lastIndex成立，则说明当 前 newVNode 所对应的真实 DOM 需要移动。根据前文的分析可知， 我们需要获取当前 newVNode 节点的前一个虚拟节点，即 newChildren[i - 1]，然后使用insert函数完成节点的移动， 其中 insert 函数依赖浏览器原生的 insertBefore 函数。

添加新元素

function patchChildren(n1, n2) {const oldChildren = n1.childrenconst newChildren = n2.childrenlet lastIndex = 0for (let i = 0; i < newChildren.length; i++) {// 在第一层循环中定义变量 find，代表是否在旧的一组子节点中找到可复用的节点let find = falseconst newVNode = newChildren[i]for (j = 0; j < oldChildren.length; j++) {const oldVNode = oldChildren[j]if (newVNode.key === oldVNode.key) {// 一旦找到可复用的节点，则将变量 find 的值设为 truefind = trueif (j < lastIndex) {// console.log('需要移动的节点', newVNode, oldVNode, j)const prevVNode = newChildren[i - 1]if (prevVNode) {// 2.找到 prevVNode 所对应真实 DOM 的下一个兄 弟节点，并将其作为锚点const anchor = prevVNode?.el?.nextSiblingconsole.log('插入', prevVNode, anchor)}} else {lastIndex = j}break;}}// 添加元素// 如果代码运行到这里，find 仍然为 false,说明当前newVNode没有在旧的一组子节点中找到可复用的节点，也就是说，当前newVNode是新增节点，需要挂载if (!find) {// 为了将节点挂载到正确位置，我们需要先获取锚点元素// 首先获取当前 newVNode 的前一个 vnode 节点const prevVNode = newChildren[i - 1] let anchor = nullif (prevVNode) {// 如果有前一个 vnode 节点，则使用它的下一个兄弟节点作为锚点元	anchor = prevVNode.el.nextSibling} else {// 如果没有前一个 vnode 节点，说明即将挂载的新节点是第一个子节// // 这时我们使用容器元素的 firstChild 作为锚点anchor = container.firstChild}// 挂载 newVNodepatch(null, newVNode, container, anchor)}}
}
patchChildren(oldVNode, newVNode)

移除不存在的元素

// 4.移除不存在的元素
function patchChildren(n1, n2) {const oldChildren = n1.childrenconst newChildren = n2.childrenlet lastIndex = 0for (let i = 0; i < newChildren.length; i++) {// 在第一层循环中定义变量 find，代表是否在旧的一组子节点中找到可复用的节点let find = falseconst newVNode = newChildren[i]for (j = 0; j < oldChildren.length; j++) {const oldVNode = oldChildren[j]if (newVNode.key === oldVNode.key) {// 一旦找到可复用的节点，则将变量 find 的值设为 truefind = trueif (j < lastIndex) {// console.log('需要移动的节点', newVNode, oldVNode, j)const prevVNode = newChildren[i - 1]if (prevVNode) {// 2.找到 prevVNode 所对应真实 DOM 的下一个兄 弟节点，并将其作为锚点const anchor = prevVNode?.el?.nextSiblingconsole.log('插入', prevVNode, anchor)}} else {lastIndex = j}break;}}// 如果代码运行到这里，find 仍然为 false,说明当前newVNode没有在旧的一组子节点中找到可复用的节点，也就是说，当前newVNode是新增节点，需要挂载if (!find) {const prevVNode = newChildren[i - 1] }}// 移除不存在的元素for (let i = 0; i < oldChildren.length; i++) {const oldVNode = oldChildren[i]const has = newChildren.find(vnode => vnode.key === oldVNode.key)// 如果没有找到具有相同 key 值的节点，则说明需要删除该节点if (!has) {// 调用 unmount 函数将其卸载unmount(oldVNode)}}
}
patchChildren(oldVNode, newVNode)