vue2 diff算法:双端指针法
2023-12-26 23:55:50
前言
Vue2 双端指针法是一种 diff 算法,用来比较两棵虚拟 DOM 树的差异,并根据差异更新视图
基本思路:
双端指针法基于以下两个假设:
- 相同的节点具有相同的key值
- 两个节点数组的头尾节点更有可能相同
即从两个数组的头尾分别进行对比,如果找到相同的节点,就复用并更新真实DOM,然后移动指针继续比较,直到两个数组中有一个的指针相遇,说明已经处理完了所有相同的节点。
接下来,根据剩余的节点进行不同的操作:
- 如果旧节点数组还有剩余,说明这些节点是多余的,需要删除
- 如果新节点数组还有剩余,说明这些节点是新增的,需要插入
- 如果两个数组都没有剩余,说明已经完成了diff过程
下面是一个简单的代码示例,用于说明vue2的diff算法的具体过程:
// 新旧节点数组
let oldVnode = [a, b, c, d, e]
let newVnode = [a, c, b, e, f]
// 初始化四个指针
let oldStartIdx = 0
let oldEndIdx = 4
let newStartIdx = 0
let newEndIdx = 4
// 条件比较一:新旧头节点相同
if (oldVnode[oldStartIdx].key === newVnode[newStartIdx].key) {
// 复用并更新真实DOM
patch(oldVnode[oldStartIdx], newVnode[newStartIdx])
// 移动指针
oldStartIdx++
newStartIdx++
}
// 条件比较一:新旧尾节点相同
if (oldVnode[oldEndIdx].key === newVnode[newEndIdx].key) {
// 复用并更新真实DOM
patch(oldVnode[oldEndIdx], newVnode[newEndIdx])
// 移动指针
oldEndIdx--
newEndIdx--
}
// 条件比较一:旧头结点与新尾节点相同
if (oldVnode[oldStartIdx].key === newVnode[newEndIdx].key) {
// 复用并更新真实DOM
patch(oldVnode[oldStartIdx], newVnode[newEndIdx])
// 移动指针
oldStartIdx++
newEndIdx--
}
// 条件比较一:新头结点与旧尾节点相同
if (oldVnode[oldEndIdx].key === newVnode[newStartIdx].key) {
// 复用并更新真实DOM
patch(oldVnode[oldEndIdx], newVnode[newStartIdx])
// 移动指针
oldEndIdx--
newStartIdx++
}
// 此时,旧节点数组的指针已经相遇,新节点数组还有一个节点f没有处理
// 根据剩余的节点进行操作,这里是插入新节点f
insert(newVnode[newEndIdx])
// 完成diff过程
即:
- 从新旧节点数组的首尾开始比较,如果首尾节点相同,就直接复用,然后首尾移动指针继续比较下一个节点。
- 如果首尾节点不同,就尝试从新节点的首部和旧节点的尾部进行比较,或者从新节点的尾部和旧节点的首部进行比较,如果匹配成功,就进行节点移动,然后移动指针继续比较下一个节点。
- 如果以上都不匹配(上示例代码中的4种情况),就用新节点的首部作为 key,去旧节点中寻找相同的 key,如果找到了,就进行节点移动,然后移动指针继续比较下一个节点。
- 如果以上都没有找到匹配的节点,就认为新节点是新增的节点,直接插入到旧节点的前面,然后移动指针继续比较下一个节点。
- 当新旧节点的首尾指针相遇时,结束比较,如果还有剩余的节点,就根据情况进行新增或删除。
Vue2 双端指针法的源码实现主要在 src/core/vdom/patch.js
文件中的 updateChildren
函数中,其中核心代码片段:
// src/core/vdom/patch.js
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
let oldStartIdx = 0
let newStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]
let oldKeyToIdx, idxInOld, vnodeToMove, refElm
// removeOnly is a special flag used only by <transition-group>
// to ensure removed elements stay in correct relative positions
// during leaving transitions
const canMove = !removeOnly
if (process.env.NODE_ENV !== 'production') {
checkDuplicateKeys(newCh)
}
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
} else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldCh[idxInOld] = undefined
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {
// same key but different element. treat as new element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
}
}
newStartVnode = newCh[++newStartIdx]
}
}
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx) {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}
}
文章来源:https://blog.csdn.net/olderandyanger/article/details/135156871
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!