Vue.js 2 所采用的双端 Diff 算法。既然快速 Diff 算法如此高效,我们有必要了解它的思路。接下来,我们就着重讨论快速 Diff 算法的实现原理。
相同的前置元素和后置元素
快速 Diff 算法借鉴了纯文本 Diff 算法中预处理的步骤。
案例:
旧的一组子节点:p-1、p-2、p-3。
新的一组子节点:p-1、p-4、p-2、p-3。
通过观察可以发现,两组子节点具有相同的前置节点 p-1,以及相同的后置节点 p-2 和 p-3,如图 下图 所示:对于相同的前置节点和后置节点,由于它们在新旧两组子节点中的相对位置不变,所以我们无须移动它们,但仍然需要在它们之间打补丁。
处理前置节点
对于前置节点,我们可以建立索引 j,其初始值为 0,用来指向两组子节点的开头,如图 下图所示:
然后开启一个 while 循环,让索引 j 递增,直到遇到不相同的节点为止,如下面 patchKeyedChildren 函数的代码所示:
function patchKeyedChildren(n1, n2, container) {
const newChildren = n2.children
const oldChildren = n1.children
// 处理相同的前置节点
// 索引 j 指向新旧两组子节点的开头
let j = 0
let oldVNode = oldChildren[j]
let newVNode = newChildren[j]
// while 循环向后遍历,直到遇到拥有不同 key 值的节点为止
while(oldVNode.key === newVNode.key) {
// 调用 patch 函数进行更新
patch(oldVNode, newVNode, container)
// 更新索引 j,让其递增
j++
oldVNode = oldChildren[j]
newVNode = newChildren[j]
}
}
在上面这段代码中,我们使用 while 循环查找所有相同的前置节点,并调用 patch 函数进行打补丁,直到遇到 key 值不同的节点为
止。这样,我们就完成了对前置节点的更新。在这一步更新操作过后,新旧两组子节点的状态如图 下图 所示:
处理后置节点:
这里需要注意的是,当 while 循环终止时,索引 j 的值为 1。接下来,我们需要处理相同的后置节点。由于新旧两组子节点的数量可
能不同,所以我们需要两个索引 newEnd 和 oldEnd,分别指向新旧两组子节点中的最后一个节点,如图 下图 所示:
然后,再开启一个 while 循环,并从后向前遍历这两组子节点,直到遇到 key 值不同的节点为止,如下面的代码所示:
function patchKeyedChildren(n1, n2, container) {
const newChildren = n2.children
const oldChildren = n1.children
// 处理相同的前置节点
// 索引 j 指向新旧两组子节点的开头
let j = 0
let oldVNode = oldChildren[j]
let newVNode = newChildren[j]
// while 循环向后遍历,直到遇到拥有不同 key 值的节点为止
while(oldVNode.key === newVNode.key) {
// 调用 patch 函数进行更新
patch(oldVNode, newVNode, container)
// 更新索引 j,让其递增
j++
oldVNode = oldChildren[j]
newVNode = newChildren[j]
}
+ // 处理后置节点:
// 索引 oldEnd 指向旧的一组子节点的最后一个节点
+ let oldEnd = oldChildren.length - 1
// 索引 newEnd 指向新的一组子节点的最后一个节点
+ let newEnd = newChildren.length - 1
+ oldVNode = oldChildren[oldEnd]
+ newVNode = newChildren[newEnd]
// while 循环从后向前遍历,直到遇到拥有不同 key 值的节点为止
+ while(oldVNode.key === newVNode.key) {
// 调用 patch 函数进行更新
+ patch(oldVNode, newVNode, container)
// 递减 oldEnd 和 nextEnd
+ oldEnd --
+ newEnd--
+ oldVNode = oldChildren[oldEnd]
+ newVNode = newChildren[newEnd]
}
}
与处理相同的前置节点一样,在 while 循环内,需要调用 patch函数进行打补丁,然后递减两个索引 oldEnd、newEnd 的值。在这一步更新操作过后,新旧两组子节点的状态如图 下图 所示:
新增:
观察上图:当相同的前置节点和后置节点被处理完毕后,旧的一组子节点已经全部被处理了,而在新的一组子节点中,还遗留了一个未被处理的节点 p-4。其实不难发现,节点 p-4 是一个新增节点。那么,如何用程序得出“节点 p-4 是新增节点”这个结论呢?这需要我们观察三个索引 j、newEnd 和 oldEnd 之间的关系。
- 条件一: oldEnd < j成立:说明在预处理过程中,所有旧子节点都处理完毕了。
- 条件二:newEnd >= j成立:说明在预处理过后,在新的一组子 节点中,仍然有未被处理的节点,而这些遗留的节点将被视作新增节点。
如果条件一和条件二同时成立,说明在新的一组子节点中,存在遗留节点,且这些节点都是新增节点。因此我们需要将它们挂载到正确的位置,如下图 所示:
在新的一组子节点中,索引值处于 j 和 newEnd 之间的任何节点都需要作为新的子节点进行挂载。那么,应该怎样将这些节点挂载到正确位置呢?这就要求我们必须找到正确的锚点元素。观察图 上图 中新的一组子节点可知,新增节点应该挂载到节点 p-2 所对应的真实DOM 前面。所以,节点 p-2 对应的真实 DOM 节点就是挂载操作的锚点元素。有了这些信息,我们就可以给出具体的代码实现了,如下所示:
function patchKeyedChildren(n1, n2, container) {
const newChildren = n2.children
const oldChildren = n1.children
// 处理相同的前置节点
// 索引 j 指向新旧两组子节点的开头
let j = 0
let oldVNode = oldChildren[j]
let newVNode = newChildren[j]
// while 循环向后遍历,直到遇到拥有不同 key 值的节点为止
while(oldVNode.key === newVNode.key) {
// 调用 patch 函数进行更新
patch(oldVNode, newVNode, container)
// 更新索引 j,让其递增
j++
oldVNode = oldChildren[j]
newVNode = newChildren[j]
}
// 处理后置节点:
// 索引 oldEnd 指向旧的一组子节点的最后一个节点
let oldEnd = oldChildren.length - 1
// 索引 newEnd 指向新的一组子节点的最后一个节点
let newEnd = newChildren.length - 1
oldVNode = oldChildren[oldEnd]
newVNode = newChildren[newEnd]
// while 循环从后向前遍历,直到遇到拥有不同 key 值的节点为止
while(oldVNode.key === newVNode.key) {
// 调用 patch 函数进行更新
patch(oldVNode, newVNode, container)
// 递减 oldEnd 和 nextEnd
oldEnd --
newEnd--
oldVNode = oldChildren[oldEnd]
newVNode = newChildren[newEnd]
}
// 新增
// 预处理完毕后,如果满足如下条件,则说明从 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)
+ }
}
}
在上面这段代码中,首先计算锚点的索引值(即 anchorIndex) 为newEnd + 1。如果小于新的一组子节点的数量,则说明锚点元素 在新的一组子节点中,所以直接使用 newChildren[anchorIndex].el 作为锚点元素;否则说明索引 newEnd 对应的节点已经是尾部节点了,这时无须提供锚点元素。有了 锚点元素之后,我们开启了一个 while 循环,用来遍历索引 j 和索引 newEnd 之间的节点,并调用 patch 函数挂载它们。
删除
案例:
- 旧的一组子节点:p-1、p-2、p-3。
- 新的一组子节点:p-1、p-3。
当前置节点,后置节点都处理完成,后剩余未被处理的节点如下图所示:
索引 j 和索引 oldEnd 之间的任何节点都应该被卸载,具体实现如下:
function patchKeyedChildren(n1, n2, container) {
const newChildren = n2.children
const oldChildren = n1.children
// 处理相同的前置节点
// 索引 j 指向新旧两组子节点的开头
let j = 0
let oldVNode = oldChildren[j]
let newVNode = newChildren[j]
// while 循环向后遍历,直到遇到拥有不同 key 值的节点为止
while(oldVNode.key === newVNode.key) {
// 调用 patch 函数进行更新
patch(oldVNode, newVNode, container)
// 更新索引 j,让其递增
j++
oldVNode = oldChildren[j]
newVNode = newChildren[j]
}
// 处理后置节点:
// 索引 oldEnd 指向旧的一组子节点的最后一个节点
let oldEnd = oldChildren.length - 1
// 索引 newEnd 指向新的一组子节点的最后一个节点
let newEnd = newChildren.length - 1
oldVNode = oldChildren[oldEnd]
newVNode = newChildren[newEnd]
// while 循环从后向前遍历,直到遇到拥有不同 key 值的节点为止
while(oldVNode.key === newVNode.key) {
// 调用 patch 函数进行更新
patch(oldVNode, newVNode, container)
// 递减 oldEnd 和 nextEnd
oldEnd --
newEnd--
oldVNode = oldChildren[oldEnd]
newVNode = newChildren[newEnd]
}
// 新增
// 预处理完毕后,如果满足如下条件,则说明从 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)
}
+ } else if (j > newEnd && j <= oldEnd) {
// 删除
// j -> oldEnd 之间的节点应该被卸载
+ while(j <= oldEnd) {
+ unmount(oldChildren[j++])
}
}
}
在上面这段代码中,我们新增了一个 else…if 分支。当满足条件j > newEnd && j <= oldEnd时,则开启一个while循环,并调用unmount 函数逐个卸载这些遗留节点。文章来源:https://www.toymoban.com/news/detail-636713.html
移动
有点复杂文章来源地址https://www.toymoban.com/news/detail-636713.html
到了这里,关于vuejs 设计与实现 - 快速diff算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!