vue2.x의 diff 알고리즘 원리에 대한 심층 분석
- 青灯夜游앞으로
- 2022-08-15 19:54:212054검색
diff 알고리즘은 동일한 수준의 트리 노드를 비교하는 효율적인 알고리즘으로, 트리를 계층별로 검색하고 탐색할 필요가 없습니다. 이 글은 vue2.x의 diff 알고리즘 원리에 대한 심층 분석을 제공할 것입니다. 도움이 되기를 바랍니다.
저는 소스코드 분석 기사를 많이 읽었고 소스코드를 두 번 이상 읽었습니다. 결국엔 그래도 일종의 기록으로 직접 쓰고 싶고, 나 자신을 위한 공부도 하고 싶다. 댓글과 요약에 집중하고 나머지는 너무 걱정하지 마세요, 요약과 소스 코드를 비교하여 프로세스와 댓글을 검토하면 더 많은 것을 얻을 수 있습니다
메서드 정의 업데이트
렌더 함수가 생성된 후 마운팅 중에 Diff 계산이 수행됩니다. 초기화 중에는 이전 가상 노드가 없으므로 처음으로 실제 DOM 노드와 비교됩니다. 가상 노드가 기본 노드가 아닌 경우 처음으로 교체 작업이 수행됩니다. (학습 영상 공유: vue 영상 튜토리얼)
// /src/core/instance/lifecycle.js
Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
const vm: Component = this
const prevEl = vm.$el
const prevVnode = vm._vnode
const restoreActiveInstance = setActiveInstance(vm)
vm._vnode = vnode // 当前render函数产生的虚拟节点,保存后以便下次做对比
if (!prevVnode) {
vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false) //初次渲染
} else {
vm.$el = vm.__patch__(prevVnode, vnode)
}
...
}
diff 알고리즘에는 두 개의 주요 분기가 있습니다
본체는 두 개의 주요 분기로 구성됩니다. 전면 및 후면 가상 노드는 일관성이 있고 전면 및 후면 가상 노드는 동일합니다. 불일치
// /src/core/vdom/patch.js
export function createPatchFunction (backend) {
...
return function patch (oldVnode, vnode, hydrating, removeOnly) {
...
if (!isRealElement && sameVnode(oldVnode, vnode)) {
...// 前后虚拟节点一致的方法
} else {
...// 前后虚拟节点不一致的方法
}
}
}
전면 및 후면 가상 노드가 불일치합니다
3단계로 나뉩니다: 1. 새 노드 생성, 2. 상위 자리 표시자 노드 업데이트, 3. 이전 노드 삭제
두 단계는 다음과 같은 경우에 다릅니다. 컴포넌트가 처음 마운트되면 실제 DOM인지 판단됩니다. 가상 노드로 변환되어 교체됩니다
if (isRealElement) {
...
//需要diff 所以将第一次的真实节点转换成虚拟节点
oldVnode = emptyNodeAt(oldVnode) //<div id="app"></div>
}
// 拿到父类的dom节点
const oldElm = oldVnode.elm //app
const parentElm = nodeOps.parentNode(oldElm) // body
//创建新dom节点 内部包含组件逻辑
createElm(
vnode,
insertedVnodeQueue,
oldElm._leaveCb ? null : parentElm,
nodeOps.nextSibling(oldElm)
)
//更新父的占位符节点 (组件更新相关)
if (isDef(vnode.parent)) {
// 在生成render函数时会生成占位符节点<Dialog>提示</Dialog> => <div>提示</div> <Dialog></Dialog>就是占位符节点
let ancestor = vnode.parent
// 判断是否可挂载
const patchable = isPatchable(vnode)
while (ancestor) {
for (let i = 0; i < cbs.destroy.length; ++i) {
cbs.destroy[i](ancestor)
}
//更新父占位符的element
ancestor.elm = vnode.elm
if (patchable) {
...
} else {
registerRef(ancestor)
}
ancestor = ancestor.parent
}
}
// 删除旧节点
if (isDef(parentElm)) {
removeVnodes([oldVnode], 0, 0)
} else if (isDef(oldVnode.tag)) {
invokeDestroyHook(oldVnode)
}전후의 가상 노드가 일치하는지
- 먼저 확인하세요. 새 노드가 텍스트인지, 그렇다면 텍스트를 직접 설정하고, 그렇지 않다면 계속해서 결정하세요
- 새 노드와 이전 노드에 자식이 있습니다. 심층 비교(핵심)
- 새 노드에는 자식이 있고, 이전 노드는 그렇지 않습니다. 루프에 새 노드를 추가하세요
- 새 노드에 자식이 없고, 이전 노드에 자식이 있습니다. 이전 노드를 직접 삭제하세요
function patchVnode (oldVnode,vnode,insertedVnodeQueue,ownerArray,index,removeOnly) {
const elm = vnode.elm = oldVnode.elm
let i
const data = vnode.data
// 是组件vnode,在组件更新会调用组件的prepatch方法
if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
i(oldVnode, vnode)
}
const oldCh = oldVnode.children
const ch = vnode.children
//比较属性
if (isDef(data) && isPatchable(vnode)) {
for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
}
// 是否是text
if (isUndef(vnode.text)) {
// 新旧节点都有children
if (isDef(oldCh) && isDef(ch)) {
if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
// 新有 老没有 children 循环创建新节点
} else if (isDef(ch)) {
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
// 新没有 老有 children 直接删除老节点
} else if (isDef(oldCh)) {
removeVnodes(oldCh, 0, oldCh.length - 1)
// 新老都没有 children 老的是文本 就置为空
} else if (isDef(oldVnode.text)) {
nodeOps.setTextContent(elm, '')
}
// 是text 直接设置文本
} else if (oldVnode.text !== vnode.text) {
nodeOps.setTextContent(elm, vnode.text)
}
if (isDef(data)) {
if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
}
}자식이 있는 이전 노드와 새 노드의 비교
// /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
const canMove = !removeOnly
// 满足新节点开始索引小于新节点结束索引,旧节点开始索引小于旧节点结束索引
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) { // 是否定义老节点开始元素
oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {// 是否定义老节点结束元素
oldEndVnode = oldCh[--oldEndIdx]
// 头(旧节点开始元素)头(新节点开始元素)对比 例如四个li,末尾新增一个li,这种情况头头对比性能高
} else if (sameVnode(oldStartVnode, newStartVnode)) { // sameVnode判断key和tag是否相同
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) { // 尾尾对比 例如四个li,头部新增一个li,这种情况尾尾对比性能高
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) {// 头尾对比 节点反转优化 reverse
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)) { // 尾头对比
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else { // 乱序对比(核心diff,其他方式为优化)
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) {
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 {
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(oldCh, oldStartIdx, oldEndIdx)
}
}
Note
- 헤드에 요소를 추가할 때 인덱스를 키로 사용하면 업데이트 오류가 발생하기 때문에 인덱스를 키로 사용할 수 없는 경우가 있습니다. 끝에 요소를 추가한다고 이해하게 될 것입니다(이전과 이후의 키가 모두 0이기 때문입니다)
- 다양한 비교 상황에서 둘이 동일하다면 자식은 재귀적으로 비교됩니다
- 비순서적으로 비교해보면 키의 역할이 굉장하네요. 키가 없으면 업데이트 오류가 발생하고 재사용 효과를 얻을 수 없습니다. diff 비교는 깊이 우선, 동일 레이어 비교
템플릿은 마운트 시 diff 알고리즘 이후에 업데이트됩니다. 처음으로 실제 DOM 노드가 생성된 가상 노드와 비교되고 생성된 가상 노드는 나중에 업데이트 및 비교를 위해 저장됩니다. diff 알고리즘은 두 개의 분기로만 분할하면 됩니다. 전면 및 후면 가상 노드는 일관성이 있고 전면 및 후면 가상 노드는 일관성이 없습니다. 전면 및 후면 가상 노드가 일치하지 않으면 새 노드가 생성되고 상위 자리 표시자가 업데이트되며 이전 노드가 삭제됩니다. 이전 노드가 실제 노드인 경우 가상 노드로 변환하고 이전 노드의 상위 노드를 가져와 이전 노드를 교체합니다. 전면 및 후면 가상 노드가 일치하는 경우 먼저 새 노드가 텍스트인지 확인하고 값이 직접 추가된 경우 속성을 먼저 비교한 다음 새 노드에 자식이 있는지, 이전 노드에 있는지 확인합니다. 자식이 없으면 새 노드 자식이 직접 추가됩니다. 새 노드에 자식이 있으면 새 노드가 직접 추가됩니다. 노드가 없지만 이전 노드가 있으면 이전 노드의 자식이 제거됩니다. 이전 노드와 새 노드에 자식이 있으면 이중 포인터를 사용하여 정면 비교, 꼬리 비교, 꼬리 비교, 꼬리 비교를 통해 동일한 레이어를 비교합니다. 오래된 노드의 활용을 극대화하기 위해 지속적으로 반복적으로 판단하고 업데이트하며, 중복된 새 노드가 있으면 추가되고, 마지막으로 비교된 가상 노드는 삭제됩니다. 비교할 다음 번 이전 노드로 반환되어 저장됩니다.
- 직접 비교
새 시작 요소와 이전 시작 요소가 동일한 vnode에 있는 경우patchVnode메서드를 재귀적으로 호출하여 심층 비교를 한 후 인덱스를 다음 요소로 이동합니다.patchVnode方法进行深层对比,之后移动索引至下一个元素 - 尾尾对比
如果新旧结束元素是相同vnode,递归调用patchVnode方法进行深层对比,之后移动索引至上一个元素 - 头尾对比
将老节点开始元素和旧节点尾元素进行对比,相同就递归调用patchVnode方法进行深层对比,之后将旧节点元素移动至最后,旧节点头指针移动到下一个,新节点的尾指针移动至上一个。例如旧:A,B,C,新:C,B,A,第一次对比将旧A移动到C后边 - 尾头对比
将老节点尾元素和旧节点开始元素进行对比,相同就递归调用patchVnodeTail -to-tail 비교 - 이전 끝 요소와 새 끝 요소가 동일한 vnode에 있는 경우 심층 비교를 위해
patchVnode메서드를 재귀적으로 호출한 다음 인덱스를 이전 요소로 이동합니다
Head-to- tail 비교
patchVnode를 재귀적으로 호출합니다. > 메서드는 심층 비교를 수행한 다음 이전 노드 요소를 끝으로 이동합니다. 이전 노드의 헤드 포인터를 다음 노드로 이동하고, 새 노드의 테일 포인터를 이전 노드로 이동합니다. 예를 들어 old: A, B, C, new: C, B, A. 첫 번째 비교를 위해 이전 A를 C의 뒤로 이동Tail 및 헤드 비교 이전 노드의 꼬리 요소를 이전 노드의 시작 요소가 동일하면 재귀적으로 patchVnode 메서드를 호출하여 심층 비교를 한 다음 이전 노드 요소를 앞으로 이동하고 이전 노드의 꼬리 포인터를 이전 요소로 이동합니다. 그리고 새 노드의 헤드 포인터는 다음 노드를 가리킵니다. 예를 들어 이전: A, B, C, 새: C, B, A, D입니다. 첫 번째 비교는 이전 C를 A의 앞으로 이동합니다.비순차 비교
위 내용은 vue2.x의 diff 알고리즘 원리에 대한 심층 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
성명：
이 기사는 juejin.cn에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제