diff演演算法是一種通過**同層的樹節點**進行比較的高效演演算法
Diff 演演算法探討的就是虛擬 DOM 樹發生變化後,生成 DOM 樹更新修補程式的方式。對比新舊兩株虛擬 DOM 樹的變更差異,將更新修補程式作用於真實 DOM,以最小成本完成檢視更新。
策略:深度優先,同層比較
updateChildren使用同級比對,同級比對圖示
0. 依次對比,比較成功後退出當前比較
1. 渲染結構以newvnode為準
2. 每次比較成功後,start和end向中間靠攏
3. 當新舊節點中有一個start跑到end的右側時,終止比較
4. 如果都匹配不到,則舊的虛擬dom key只去對比新的虛擬dom key值,如果key相同,則複用
好,瞭解了這些規則,讓我們利用一個案例看看 ,原始碼會如何執行吧。
簡單貼一下原始碼吧,以下是更新子節點 diff核心演演算法,有一些我自己寫的註釋和問題
function updateChildren( parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly ) { //節點的序號 let oldStartIdx = 0 let oldEndIdx = oldCh.length - 1 let newStartIdx = 0 let newEndIdx = newCh.length - 1 //節點的value let oldStartVnode = oldCh[0] let oldEndVnode = oldCh[oldEndIdx] 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 (__DEV__) { 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 { //todo oldKeyToIdx這是啥? if (isUndef(oldKeyToIdx)) //這是取得什麼?{key:index} oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) //isDef:不是undefind or null /*** * 如果有key 獲取key對應的index, * 如果沒有key,則 */ idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) if (isUndef(idxInOld)) {//如果 oldCh裡面沒有此節點 // New element createElm( newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx ) } else {//如果 oldCh有此節點 //那就拿到值 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(oldCh, oldStartIdx, oldEndIdx) } } function checkDuplicateKeys(children) { const seenKeys = {} for (let i = 0; i < children.length; i++) { const vnode = children[i] const key = vnode.key if (isDef(key)) { if (seenKeys[key]) { warn( `Duplicate keys detected: '${key}'. This may cause an update error.`, vnode.context ) } else { seenKeys[key] = true } } } } //從oldCh找到與node相同的值,返回old對應的i function findIdxInOld(node, oldCh, start, end) { for (let i = start; i < end; i++) { const c = oldCh[i] if (isDef(c) && sameVnode(node, c)) return i } } function patchVnode( oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly?: any ) { if (oldVnode === vnode) { return } if (isDef(vnode.elm) && isDef(ownerArray)) { // clone reused vnode vnode = ownerArray[index] = cloneVNode(vnode) } const elm = (vnode.elm = oldVnode.elm) if (isTrue(oldVnode.isAsyncPlaceholder)) { if (isDef(vnode.asyncFactory.resolved)) { hydrate(oldVnode.elm, vnode, insertedVnodeQueue) } else { vnode.isAsyncPlaceholder = true } return } // reuse element for static trees. // note we only do this if the vnode is cloned - // if the new node is not cloned it means the render functions have been // reset by the hot-reload-api and we need to do a proper re-render. if ( isTrue(vnode.isStatic) && isTrue(oldVnode.isStatic) && vnode.key === oldVnode.key && (isTrue(vnode.isCloned) || isTrue(vnode.isOnce)) ) { vnode.componentInstance = oldVnode.componentInstance return } let i const data = vnode.data 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) } if (isUndef(vnode.text)) { if (isDef(oldCh) && isDef(ch)) { if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) } else if (isDef(ch)) { if (__DEV__) { checkDuplicateKeys(ch) } if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '') addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) } else if (isDef(oldCh)) { removeVnodes(oldCh, 0, oldCh.length - 1) } else if (isDef(oldVnode.text)) { nodeOps.setTextContent(elm, '') } } 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) } }