Vue diff算法 - 双端diff
简单diff的劣势
在讨论双端diff之前 我们先来解释下简单diff到底哪里不行
const oldNode = {
type: 'div',
children: [
{type: 'p', key: '1'},
{type: 'p', key: '2'},
{type: 'p', key: '3'}
]
}
const newNode = {
type: 'div',
children: [
{type: 'p', key: '3'},
{type: 'p', key: '1'},
{type: 'p', key: '2'}
]
}
以上示例中，newChildren和oldChildren以及真实dom的对应关系如下图所示，红色箭头代表两者之间具有对应关系
当使用简单diff算法时，需要进行两次DOM节点的移动才能完成children重新排序，如下图中的蓝色箭头意为dom节点的移动
不难发现对于这个例子来说，简单diff算法不是最优的方案。如果像下图所示，能直接让key:3这个节点移动key:1之前，则只需要进行一次DOM节点的移动就能完成children重新排序。
接下来讨论的双端diff算法则可以完成这个目标。
双端diff 概述
顾名思义，双端diff就是同时对新旧两组子节点的两个端点进行比较的算法，因此我们需要四个索引值，分别指向新旧两组子节点的两个端点，如下图。
为了方便计算我们还需定义四个变量来分别存储四个索引值所对应的vnode，代码对应如下
/**
*
* @param {新节点} newNode
* @param {旧节点} oldNode
* @param {父节点} container
*/
const patchChildren = (newNode, oldNode, container) => {
const newChildren = newNode.children;
const oldChildren = oldNode.children;
let newStartIndex = 0
let newStartNode = newChildren[newStartIndex]
let newEndIndex = newChildren.length - 1
let newEndNode = newChildren[newEndIndex]
let oldStartIndex = 0
let oldStartNode = oldChildren[oldStartIndex]
let oldEndIndex = oldChildren.length - 1
let oldEndNode = oldChildren[oldEndIndex]
};
在这个算法中，每一轮的比较都会有几个种情况分类处理，我们以下面的两组子节点为例进行“理想children”循环比较，示例中的这两组子节点是比较理想的，后面会补充特殊情况的处理来完善算法。
const oldNode = {
type: 'div',
children: [
{type: 'p', key: '1'},
{type: 'p', key: '2'},
{type: 'p', key: '3'}，
{type: 'p', key: '4'}
]
}
const newNode = {
type: 'div',
children: [
{type: 'p', key: '4'},
{type: 'p', key: '2'},
{type: 'p', key: '1'}，
{type: 'p', key: '3'}
]
}
“理想children”循环比较
-
第一轮循环
第一轮比较过程图解及描述如下
- newStartNode和oldStartNode之间比较，即p-key:4与p-key:1两者比较，key不相同，不可复用，什么都不用做。
- newEndNode和oldEndNode之间比较，即p-key:3与p-key:4两者比较，key不相同，不可复用，什么都不用做。
- newEndNode和oldStartNode之间比较，即p-key:3与p-key:1两者比较，key不相同，不可复用，什么都不用做。
- newStartNode和oldEndNode之间比较，即p-key:4与p-key:4两者比较，key相同，可以复用。
在4这种情况下，确实找到可复用的真实DOM，接下来就需要将新旧两个vnode进行patchNode，然后再控其对应的真实DOM移动到适当的位置即可。关于DOM的移动，我们可以这么来描述：将oldEndNode对应的真实DOM移动到oldStartNode对应的真实DOM之前。如此这个vnode就已经处理完了，最后将newStartIndex++，oldEndIndex--，对应的图解与代码如下。
const patchChildren = (newNode, oldNode, container) => {
const newChildren = newNode.children;
const oldChildren = oldNode.children;
let newStartIndex = 0
let newStartNode
let newEndIndex = newChildren.length - 1
let newEndNode
let oldStartIndex = 0
let oldStartNode
let oldEndIndex = oldChildren.length - 1
let oldEndNode
// 需要注意的是，当newStartIndex > newEndIndex || oldStartIndex > oldEndIndex时需要停止循环
while(newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) {
newStartNode = newChildren[newStartIndex]
newEndNode = newChildren[newEndIndex]
oldStartNode = oldChildren[oldStartIndex]
oldEndNode = oldChildren[oldEndIndex]
if (newStartNode.key === oldStartNode.key) {
} else if (newEndNode.key === oldEndNode.key) {
} else if (newEndNode.key === oldStartNode.key) {
} else if (newStartNode.key === oldEndNode.key) {
patchNode(newStartNode, oldEndNode, container)
insert(newStartNode.el, container, oldStartNode.el)
newStartIndex++
oldEndIndex--
}
}
};
-
第二轮循环
比较过程图解及描述如下
- newStartNode和oldStartNode之间比较，即p-key:2与p-key:1两者比较，key不相同，不可复用，什么都不用做。
- newEndNode和oldEndNode之间比较，即p-key:3与p-key:3两者比较，key相同，可以复用。
- 第二个步骤已生效，newEndNode和oldStartNode之间，即p-key:3和p-key:1之间本轮不会比较。
- 第二个步骤已生效，newStartNode和oldEndNode之间，即p-key:2与p-key:3之间本轮不会比较。
在2这种情况下，确实找到可复用的真实DOM，接下来就需要将新旧两个vnode进行patchNode，两个节点目前都处于列表的尾部，因此不需要将其对应的真实DOM进行移动，最后将newEndIndex和oldEndIndex分别减1。对应的代码如下
while(newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) {
......
......
if (newStartNode.key === oldStartNode.key) {
} else if (newEndNode.key === oldEndNode.key) {
patchNode(newEndNode, oldEndNode, container)
newEndIndex--
oldEndIndex--
} else if (newEndNode.key === oldStartNode.key) {
} else if (newStartNode.key === oldEndNode.key) {
......
}
}
-
第三轮循环
比较过程图解及描述如下
- newStartNode和oldStartNode之间比较，即p-key:2与p-key:1两者比较，key不相同，不可复用，什么都不用做。
- newEndNode和oldEndNode之间比较，即p-key:1与p-key:2两者比较，key不相同，不可复用，什么都不用做。
- newEndNode和oldStartNode之间比较，即p-key:1与p-key:1两者比较，key相同，可以复用。 第三个步骤已生效，newStartNode和oldEndNode之间，即p-key:2与p-key:2本轮不会比较。
在3这种情况下，确实找到可复用的真实DOM，接下来就需要将新旧两个vnode进行patchNode，然后再控其对应的真实DOM移动到适当的位置即可。关于DOM的移动，我们可以这么来描述：将oldStartNode对应的真实DOM移动到oldEndNode对应的真实DOM之后。如此这个vnode就已经处理完了，最后将newEndIndex--，oldStartIndex++，对应的图解与代码如下。
while(newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) {
......
......
if (newStartNode.key === oldStartNode.key) {
} else if (newEndNode.key === oldEndNode.key) {
......
} else if (newEndNode.key === oldStartNode.key) {
patchNode(newEndNode, oldStartNode, container)
insert(newEndNode.el, container, oldEndNode.el.nextSibling)
newEndIndex--
oldStartIndex++
} else if (newStartNode.key === oldEndNode.key) {
......
}
}
-
第四轮循环
比较过程图解及描述如下
- newStartNode和oldStartNode之间比较，即p-key:2与p-key:2两者比较，key相同，可以复用。
- 第一个步骤已生效，newEndNode和oldEndNode之间，即p-key:2和p-key:2之间本轮不会比较。
- 第一个步骤已生效，newEndNode和oldStartNode之间，即p-key:2和p-key:2之间本轮不会比较。
- 第一个步骤已生效，newStartNode和oldEndNode之间，即p-key:2与p-key:2之间本轮不会比较。
在1这种情况下，确实找到可复用的真实DOM，接下来就需要将新旧两个vnode进行patchNode，两个节点目前都处于列表的头部，因此不需要将其对应的真实DOM进行移动，最后将newStartIndex和oldStartIndex分别+1，此时不满足循环条件while循环终止。对应的代码如下
while(newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) {
......
......
if (newStartNode.key === oldStartNode.key) {
patchNode(newStartNode, oldStartNode, container)
newStartIndex++
oldStartIndex++
} else if (newEndNode.key === oldEndNode.key) {
......
} else if (newEndNode.key === oldStartNode.key) {
......
} else if (newStartNode.key === oldEndNode.key) {
......
}
}
-
结束循环
结束上一轮循环后，newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex已不满足，各列表的状态如下图，可以看到此时的真实DOM列表已经跟newChildren列表顺序一致了。
“非理想children”处理方式
脱离四种情况的示例
拿以下示例，套用“理想children”循环比较算法
const oldNode = {
type: 'div',
children: [
{type: 'p', key: '1'},
{type: 'p', key: '2'},
{type: 'p', key: '3'}，
{type: 'p', key: '4'}
]
}
const newNode = {
type: 'div',
children: [
{type: 'p', key: '2'},
{type: 'p', key: '4'},
{type: 'p', key: '1'}，
{type: 'p', key: '3'}
]
}
-
第一轮循环
通过以上图解 可以看得出，前边描述的四个比较方法都不适用于本轮循环，此时可以遍历oldChildren找到与newStartNode相匹配的节点进行patch，再将其对应的真实DOM移动到oldStartNode之前，patch结束以后将oldChildren中的那个节点置为undefined表示该节点已被处理过，图解与代码如下
-
第二轮循环
第二轮循环可以匹配到“理想children”循环的第4种情况，找到可复用的真实DOM，接下来就需要将新旧两个vnode进行patchNode，然后再控其对应的真实DOM移动到适当的位置即可。关于DOM的移动，我们可以这么来描述：将oldEndNode对应的真实DOM移动到oldStartNode对应的真实DOM之前。如此这个vnode就已经处理完了，最后将newStartIndex++，oldEndIndex--， 图解如下
-
第四轮循环
第四轮循环开始时各列表是如下状态
oldStartIndex指向的是undefined，可以直接让oldStartIndex++，开始下一轮循环。同理，如果oldEndIndex指向undefined的时候也可以直接让oldEndIndex--，开始下一轮循环。代码如下
while(newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) {
......
......
if (!oldStartNode) {
oldStartIndex++
} else if (!oldEndNode) {
oldEndIndex--
} else if (newStartNode.key === oldStartNode.key) {
......
} else if (newEndNode.key === oldEndNode.key) {
......
} else if (newEndNode.key === oldStartNode.key) {
......
} else if (newStartNode.key === oldEndNode.key) {
......
} else {
......
}
}
-
第五轮循环
当循环到第五轮的时候，两个子节点列表都只剩下了p - key:3，可以匹配到“理想children”循环的第1种情况，找到可复用的真实DOM，接下来就需要将新旧两个vnode进行patchNode，两个节点目前都处于列表的头部，因此不需要将其对应的真实DOM进行移动，最后将newStartIndex和oldStartIndex分别+1。 图解如下
-
结束循环
结束上一轮循环后，newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex已不满足，各列表的状态如下图，可以看到此时的真实DOM列表已经跟newChildren列表顺序一致了。
添加新元素
拿以下示例，套用之前讲过的循环比较算法
const oldNode = {
type: 'div',
children: [
{type: 'p', key: '1'},
{type: 'p', key: '2'},
{type: 'p', key: '3'}，
]
}
const newNode = {
type: 'div',
children: [
{type: 'p', key: '4'},
{type: 'p', key: '3'},
{type: 'p', key: '1'}，
{type: 'p', key: '2'}
]
}
-
第一轮循环
通过以上图解可以看得出，前边描述的四个比较方法都不适用于本轮循环，遍历oldChildren找不到与newStartNode相匹配的节点。此时就可以判定newStartNode是个新节点，且其顺序是排在oldStartNode之前的，因此可以直接仿照[简单diff算法] 中“添加新元素”的方法来完成，完成以后将oldStartIndex++。
while(newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) {
......
......
if (!oldStartNode) {
oldStartIndex++
} else if (!oldEndNode) {
oldEndIndex--
} else if (newStartNode.key === oldStartNode.key) {
......
} else if (newEndNode.key === oldEndNode.key) {
......
} else if (newEndNode.key === oldStartNode.key) {
......
} else if (newStartNode.key === oldEndNode.key) {
......
} else {
const nodeIndex = oldChildren.findIndex(n => n?.key === newStartNode.key)
if (nodeIndex !== -1) {
......
} else {
patchNode(newStartNode, null, container, oldStartNode.el)
newStartIndex++
}
}
}
-
后序循环
经过第一轮循环后，各列表的状态如图
可以看出，后序就如同“理想children”的循环比较一样了，这里不再赘述。最终得到的状态如下，此时的真实DOM列表已经跟newChildren列表顺序一致了
-
循环结束后 newStartIndex <= newEndIndex
拿以下示例，套用目前的循环比较算法
const oldNode = {
type: 'div',
children: [
{type: 'p', key: '1'},
]
}
const newNode = {
type: 'div',
children: [
{type: 'p', key: '4'},
{type: 'p', key: '1'},
]
}
根据以上图解可以看出，第一轮while循环适用于前边说的第二种情况，但经过一轮循环后oldStartIndex就大于oldEndIndex了，while循环随即停止。显然这个现象是不能满足要求的，因此我们必须再开一个while循环，以newStartIndex <= newEndIndex作为条件，继续把剩余的新节点插入到oldStartNode之前。具体代码如下
while(newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) {
......
......
......
}
while(newStartIndex <= newEndIndex) {
patchNode(newChildren[newStartIndex], null, container, oldStartNode.el)
newStartIndex++
}
移除旧元素
拿以下示例，套用目前的循环比较算法
const oldNode = {
type: 'div',
children: [
{type: 'p', key: '1'},
{type: 'p', key: '2'},
]
}
const newNode = {
type: 'div',
children: [
{type: 'p', key: '1'},
]
}
根据以上图解可以看出，第一轮while循环适用于前边说的第一种情况，但经过一轮循环后newStartIndex就大于newEndIndex了，while循环随即停止。显然这个现象是不能满足要求的，因此我们必须再开一个while循环，以oldStartIndex <= oldEndIndex作为条件，将遍历到的节点按照[简单diff算法]中的“移除不存在元素”的方法移除掉。具体代码如下
while(newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) {
......
......
......
}
while(newStartIndex <= newEndIndex) {
......
}
while(oldStartIndex <= oldEndIndex) {
unmount(oldChildren[oldStartIndex])
oldStartIndex++
}
完整diff代码
/**
*
* @param {新节点} newNode
* @param {旧节点} oldNode
* @param {父节点} container
*/
const patchChildren = (newNode, oldNode, container) => {
const newChildren = newNode.children;
const oldChildren = oldNode.children;
let newStartIndex = 0
let newStartNode
let newEndIndex = newChildren.length - 1
let newEndNode
let oldStartIndex = 0
let oldStartNode
let oldEndIndex = oldChildren.length - 1
let oldEndNode
while(newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) {
newStartNode = newChildren[newStartIndex]
newEndNode = newChildren[newEndIndex]
oldStartNode = oldChildren[oldStartIndex]
oldEndNode = oldChildren[oldEndIndex]
// 若当前的oldStartNode和oldEndNode为undefined，说明它已经被处理过了，需要跳过。
if (!oldStartNode) {
oldStartIndex++
} else if (!oldEndNode) {
oldEndIndex--
} else if (newStartNode.key === oldStartNode.key) {
patchNode(newStartNode, oldStartNode, container)
newStartIndex++
oldStartIndex++
} else if (newEndNode.key === oldEndNode.key) {
patchNode(newEndNode, oldEndNode, container)
newEndIndex--
oldEndIndex--
} else if (newEndNode.key === oldStartNode.key) {
patchNode(newEndNode, oldStartNode, container)
insert(newEndNode.el, container, oldEndNode.el.nextSibling)
newEndIndex--
oldStartIndex++
} else if (newStartNode.key === oldEndNode.key) {
patchNode(newStartNode, oldEndNode, container)
insert(newStartNode.el, container, oldStartNode.el)
newStartIndex++
oldEndIndex--
} else {
const nodeIndex = oldChildren.findIndex(n => n?.key === newStartNode.key)
if (nodeIndex !== -1) {
patchNode(newStartNode, oldChildren[nodeIndex], container)
insert(newStartNode.el, container, oldStartNode.el)
oldChildren[nodeIndex] = undefined
newStartIndex++
} else {
patchNode(newStartNode, null, container, oldStartNode.el)
newStartIndex++
}
}
}
while(newStartIndex <= newEndIndex) {
patchNode(newChildren[newStartIndex], null, container, oldStartNode.el)
newStartIndex++
}
while(oldStartIndex <= oldEndIndex) {
unmount(oldChildren[oldStartIndex])
oldStartIndex++
}
};
转载自:https://juejin.cn/post/7267512263878885432