是什麼
diff 算法是一種通過同層的樹節點進行比較的高效算法
特點：
- 比較隻會在同層級進行, 不會跨層級比較
- 在diff比較的過程中，循環從兩邊向中間比較
diff 算法在很多場景下都有應用，在 vue 中，作用于虛拟 dom 渲染成真實 dom 的新舊 VNode 節點比較
比較方式
深度優先，同層比較
原理分析
當資料發生改變時，set方法會調用Dep.notify通知所有訂閱者Watcher，訂閱者就會調用patch給真實的DOM打更新檔 更新相應的視圖
源碼位置：src/core/vdom/patch.js
function patch(oldVnode, vnode, hydrating, removeOnly) {
if (isUndef(vnode)) { // 沒有新節點，直接執行destory鈎子函數
if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
return
}
let isInitialPatch = false
const insertedVnodeQueue = []
if (isUndef(oldVnode)) {
isInitialPatch = true
createElm(vnode, insertedVnodeQueue) // 沒有舊節點，直接用新節點生成dom元素
} else {
const isRealElement = isDef(oldVnode.nodeType)
if (!isRealElement && sameVnode(oldVnode, vnode)) {
// 判斷舊節點和新節點自身一樣，一緻執行patchVnode
patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
} else {
// 否則直接銷毀及舊節點，根據新節點生成dom元素
if (isRealElement) {
if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
oldVnode.removeAttribute(SSR_ATTR)
hydrating = true
}
if (isTrue(hydrating)) {
if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
invokeInsertHook(vnode, insertedVnodeQueue, true)
return oldVnode
}
}
oldVnode = emptyNodeAt(oldVnode)
}
return vnode.elm
}
}
}
patch函數前兩個參數位為oldVnode 和 Vnode ，分别代表新的節點和之前的舊節點，主要做了四個判斷：
- 沒有新節點，直接觸發舊節點的destory鈎子
- 沒有舊節點，說明是頁面剛開始初始化的時候，此時，根本不需要比較了，直接全是建立，是以隻調用 createElm
- 舊節點和新節點自身一樣，通過 sameVnode 判斷節點是否一樣，一樣時，直接調用 patchVnode去處理這兩個節點
- 舊節點和新節點自身不一樣，當兩個節點不一樣的時候，直接建立新節點，删除舊節點
下面主要講的是patchVnode部分
function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
// 如果新舊節點一緻，什麼都不做
if (oldVnode === vnode) {
return
}
// 讓vnode.el引用到現在的真實dom，當el修改時，vnode.el會同步變化
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
}
// 如果新舊都是靜态節點，并且具有相同的key
// 當vnode是克隆節點或是v-once指令控制的節點時，隻需要把oldVnode.elm和oldVnode.child都複制到vnode上
// 也不用再有其他操作
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)
}
// 如果vnode不是文本節點或者注釋節點
if (isUndef(vnode.text)) {
// 并且都有子節點
if (isDef(oldCh) && isDef(ch)) {
// 并且子節點不完全一緻，則調用updateChildren
if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
// 如果隻有新的vnode有子節點
} else if (isDef(ch)) {
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
// elm已經引用了老的dom節點，在老的dom節點上添加子節點
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
// 如果新vnode沒有子節點，而vnode有子節點，直接删除老的oldCh
} else if (isDef(oldCh)) {
removeVnodes(elm, oldCh, 0, oldCh.length - 1)
// 如果老節點是文本節點
} else if (isDef(oldVnode.text)) {
nodeOps.setTextContent(elm, '')
}
// 如果新vnode和老vnode是文本節點或注釋節點
// 但是vnode.text != oldVnode.text時，隻需要更新vnode.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)
}
}
patchVnode主要做了幾個判斷：
- 新節點是否是文本節點，如果是，則直接更新dom的文本内容為新節點的文本内容
- 新節點和舊節點如果都有子節點，則處理比較更新子節點
- 隻有新節點有子節點，舊節點沒有，那麼不用比較了，所有節點都是全新的，是以直接全部建立就好了，建立是指建立出所有新DOM，并且添加進父節點
- 隻有舊節點有子節點而新節點沒有，說明更新後的頁面，舊節點全部都不見了，那麼要做的，就是把所有的舊節點删除，也就是直接把DOM 删除
子節點不完全一緻，則調用updateChildren
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
let oldStartIdx = 0 // 舊頭索引
let newStartIdx = 0 // 新頭索引
let oldEndIdx = oldCh.length - 1 // 舊尾索引
let newEndIdx = newCh.length - 1 // 新尾索引
let oldStartVnode = oldCh[0] // oldVnode的第一個child
let oldEndVnode = oldCh[oldEndIdx] // oldVnode的最後一個child
let newStartVnode = newCh[0] // newVnode的第一個child
let newEndVnode = newCh[newEndIdx] // newVnode的最後一個child
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
// 如果oldStartVnode和oldEndVnode重合，并且新的也都重合了，證明diff完了，循環結束
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 如果oldVnode的第一個child不存在
if (isUndef(oldStartVnode)) {
// oldStart索引右移
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
// 如果oldVnode的最後一個child不存在
} else if (isUndef(oldEndVnode)) {
// oldEnd索引左移
oldEndVnode = oldCh[--oldEndIdx]
// oldStartVnode和newStartVnode是同一個節點
} else if (sameVnode(oldStartVnode, newStartVnode)) {
// patch oldStartVnode和newStartVnode， 索引左移，繼續循環
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
// oldEndVnode和newEndVnode是同一個節點
} else if (sameVnode(oldEndVnode, newEndVnode)) {
// patch oldEndVnode和newEndVnode，索引右移，繼續循環
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
// oldStartVnode和newEndVnode是同一個節點
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
// patch oldStartVnode和newEndVnode
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
// 如果removeOnly是false，則将oldStartVnode.eml移動到oldEndVnode.elm之後
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
// oldStart索引右移，newEnd索引左移
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
// 如果oldEndVnode和newStartVnode是同一個節點
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
// patch oldEndVnode和newStartVnode
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
// 如果removeOnly是false，則将oldEndVnode.elm移動到oldStartVnode.elm之前
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
// oldEnd索引左移，newStart索引右移
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
// 如果都不比對
} else {
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
// 嘗試在oldChildren中尋找和newStartVnode的具有相同的key的Vnode
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
// 如果未找到，說明newStartVnode是一個新的節點
if (isUndef(idxInOld)) { // New element
// 建立一個新Vnode
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
// 如果找到了和newStartVnodej具有相同的key的Vnode，叫vnodeToMove
} else {
vnodeToMove = oldCh[idxInOld]
/* istanbul ignore if */
if (process.env.NODE_ENV !== 'production' && !vnodeToMove) {
warn(
'It seems there are duplicate keys that is causing an update error. ' +
'Make sure each v-for item has a unique key.'
)
}
// 比較兩個具有相同的key的新節點是否是同一個節點
//不設key，newCh和oldCh隻會進行頭尾兩端的互相比較，設key後，除了頭尾兩端的比較外，還會從用key生成的對象oldKeyToIdx中查找比對的節點，是以為節點設定key可以更高效的利用dom。
if (sameVnode(vnodeToMove, newStartVnode)) {
// patch vnodeToMove和newStartVnode
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
// 清除
oldCh[idxInOld] = undefined
// 如果removeOnly是false，則将找到的和newStartVnodej具有相同的key的Vnode，叫vnodeToMove.elm
// 移動到oldStartVnode.elm之前
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
// 如果key相同，但是節點不相同，則建立一個新的節點
} else {
// same key but different element. treat as new element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
}
}
// 右移
newStartVnode = newCh[++newStartIdx]
}
}
while循環主要處理了以下五種情景：
- 當新老 VNode 節點的 start 相同時，直接 patchVnode ，同時新老 VNode 節點的開始索引都加 1
- 當新老 VNode 節點的 end相同時，同樣直接 patchVnode ，同時新老 VNode 節點的結束索引都減 1
- 當老 VNode 節點的 start 和新 VNode 節點的 end 相同時，這時候在 patchVnode 後，還需要将目前真實 dom 節點移動到 oldEndVnode 的後面，同時老 VNode 節點開始索引加 1，新 VNode 節點的結束索引減 1
- 當老 VNode 節點的 end 和新 VNode 節點的 start 相同時，這時候在 patchVnode 後，還需要将目前真實 dom 節點移動到 oldStartVnode 的前面，同時老 VNode 節點結束索引減 1，新 VNode 節點的開始索引加 1
- 如果都不滿足以上四種情形，那說明沒有相同的節點可以複用，則會分為以下兩種情況：
- 從舊的 VNode 為 key 值，對應 index 序列為 value 值的哈希表中找到與newStartVnode 一緻 key 的舊的 VNode 節點，再進行patchVnode，同時将這個真實 dom移動到 oldStartVnode 對應的真實 dom 的前面
- 調用 createElm 建立一個新的 dom 節點放到目前 newStartIdx 的位置
小結
- 當資料發生改變時，訂閱者watcher就會調用patch給真實的DOM打更新檔
- 通過isSameVnode進行判斷，相同則調用patchVnode方法
- patchVnode做了以下操作：
- 找到對應的真實dom，稱為el
- 如果都有都有文本節點且不相等，将el文本節點設定為Vnode的文本節點
- 如果oldVnode有子節點而VNode沒有，則删除el子節點
- 如果oldVnode沒有子節點而VNode有，則将VNode的子節點真實化後添加到el
- 如果兩者都有子節點，則執行updateChildren函數比較子節點
- updateChildren主要做了以下操作：
- 設定新舊VNode的頭尾指針
- 新舊頭尾指針進行比較，循環向中間靠攏，根據情況調用patchVnode進行patch重複流程、調用createElem建立一個新節點，從哈希表尋找 key一緻的VNode 節點再分情況操作