一、虚拟 DOM （virtual dom）
diff 算法首先要明确一个概念就是 diff 的对象是虚拟DOM（virtual dom），更新真实 DOM 是 diff 算法的结果。
注：virtual dom 可以看作是一个使用 JavaScript 模拟了 DOM结构 的树形结构，这个树结构包含整个DOM结构的信息
二、为什么使用 diff 算法？
1、页面结构庞大时，DOM 操作代价太高，可维护性差，因此要减少 DOM 操作；
2、虚拟 DOM 很轻量，对虚拟 DOM 操作快；
3、diff 算法 是找出本次 DOM 需要更新的节点进行更新，其余不更新，对 DOM 进行原地复用，减少 DOM 创建性能耗费，可以减少浏览器页面的重绘。
三、diff 算法原理
1、patch 原理
源码
patch函数接收6个参数：
- oldVnode: 旧的虚拟节点或旧的真实dom节点
- vnode: 新的虚拟节点
- hydrating: 是否要跟真是dom混合
- removeOnly: 特殊flag，用于组件
- parentElm: 父节点
- refElm: 新节点将插入到refElm之前
patch的逻辑是：
- if vnode不存在但是oldVnode存在，说明意图是要销毁老节点，那么就调用invokeDestroyHook(oldVnode)来进行销
- if oldVnode不存在但是vnode存在，说明意图是要创建新节点，那么就调用createElm来创建新节点
else 当vnode和oldVnode都存在时
- if oldVnode和vnode是同一个节点，就调用patchVnode来进行patch
- 当vnode和oldVnode不是同一个节点时，如果oldVnode是真实dom节点或hydrating设置为true，需要用hydrate函数将虚拟dom和真是dom进行映射，然后将oldVnode设置为对应的虚拟dom，找到oldVnode.elm的父节点，根据vnode创建一个真实dom节点并插入到该父节点中oldVnode.elm的位置
代码如下：
function patch (oldVnode, vnode, hydrating, removeOnly, parentElm, refElm) {
/*vnode不存在则直接调用销毁钩子*/
if (isUndef(vnode)) {
if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
return
}
let isInitialPatch = false
const insertedVnodeQueue = []
if (isUndef(oldVnode)) {
// empty mount (likely as component), create new root element
/*oldVnode未定义的时候，其实也就是root节点，创建一个新的节点*/
isInitialPatch = true
createElm(vnode, insertedVnodeQueue, parentElm, refElm)
} else {
/*标记旧的VNode是否有nodeType*/
const isRealElement = isDef(oldVnode.nodeType)
if (!isRealElement && sameVnode(oldVnode, vnode)) {
// patch existing root node
/*是同一个节点的时候直接修改现有的节点*/
patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly)
} else {
if (isRealElement) {
// mounting to a real element
// check if this is server-rendered content and if we can perform
// a successful hydration.
if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
/*当旧的VNode是服务端渲染的元素，hydrating记为true*/
oldVnode.removeAttribute(SSR_ATTR)
hydrating = true
}
if (isTrue(hydrating)) {
/*需要合并到真实Dom上*/
if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
/*调用insert钩子*/
invokeInsertHook(vnode, insertedVnodeQueue, true)
return oldVnode
} else if (process.env.NODE_ENV !== 'production') {
warn(
'The client-side rendered virtual DOM tree is not matching ' +
'server-rendered content. This is likely caused by incorrect ' +
'HTML markup, for example nesting block-level elements inside ' +
'<p>, or missing <tbody>. Bailing hydration and performing ' +
'full client-side render.'
)
}
}
// either not server-rendered, or hydration failed.
// create an empty node and replace it
/*如果不是服务端渲染或者合并到真实Dom失败，则创建一个空的VNode节点替换它*/
oldVnode = emptyNodeAt(oldVnode)
}
// replacing existing element
/*取代现有元素*/
const oldElm = oldVnode.elm
const parentElm = nodeOps.parentNode(oldElm)
createElm(
vnode,
insertedVnodeQueue,
// extremely rare edge case: do not insert if old element is in a
// leaving transition. Only happens when combining transition +
// keep-alive + HOCs. (#4590)
oldElm._leaveCb ? null : parentElm,
nodeOps.nextSibling(oldElm)
)
if (isDef(vnode.parent)) {
// component root element replaced.
// update parent placeholder node element, recursively
/*组件根节点被替换，遍历更新父节点element*/
let ancestor = vnode.parent
while (ancestor) {
ancestor.elm = vnode.elm
ancestor = ancestor.parent
}
if (isPatchable(vnode)) {
/*调用create回调*/
for (let i = 0; i < cbs.create.length; ++i) {
cbs.create[i](emptyNode, vnode.parent)
}
}
}
if (isDef(parentElm)) {
/*移除老节点*/
removeVnodes(parentElm, [oldVnode], 0, 0)
} else if (isDef(oldVnode.tag)) {
/*调用destroy钩子*/
invokeDestroyHook(oldVnode)
}
}
}
/*调用insert钩子*/
invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
return vnode.elm
}
patchVnode的逻辑是：
- 如果oldVnode跟vnode完全一致，那么不需要做任何事情
- 如果oldVnode跟vnode都是静态节点，且具有相同的key，当vnode是克隆节点或是v-once指令控制的节点时，只需要把oldVnode.elm和oldVnode.child都复制到vnode上，也不用再有其他操作
-
否则，如果vnode不是文本节点或注释节点
- 如果oldVnode和vnode都有子节点，且2方的子节点不完全一致，就执行updateChildren
- 如果只有oldVnode有子节点，那就把这些节点都删除
- 如果只有vnode有子节点，那就创建这些子节点
- 如果oldVnode和vnode都没有子节点，但是oldVnode是文本节点或注释节点，就把vnode.elm的文本设置为空字符串
如果vnode是文本节点或注释节点，但是vnode.text != oldVnode.text时，只需要更新vnode.elm的文本内容就可以
/*patch VNode节点*/
function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
/*两个VNode节点相同则直接返回*/
if (oldVnode === vnode) {
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.
/*
如果新旧VNode都是静态的，同时它们的key相同（代表同一节点），
并且新的VNode是clone或者是标记了once（标记v-once属性，只渲染一次），
那么只需要替换elm以及componentInstance即可。
*/
if (isTrue(vnode.isStatic) &&
isTrue(oldVnode.isStatic) &&
vnode.key === oldVnode.key &&
(isTrue(vnode.isCloned) || isTrue(vnode.isOnce))) {
vnode.elm = oldVnode.elm
vnode.componentInstance = oldVnode.componentInstance
return
}
let i
const data = vnode.data
if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
/*i = data.hook.prepatch，如果存在的话，见"./create-component componentVNodeHooks"。*/
i(oldVnode, vnode)
}
const elm = vnode.elm = oldVnode.elm
const oldCh = oldVnode.children
const ch = vnode.children
if (isDef(data) && isPatchable(vnode)) {
/*调用update回调以及update钩子*/
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节点没有text文本时*/
if (isUndef(vnode.text)) {
if (isDef(oldCh) && isDef(ch)) {
/*新老节点均有children子节点，则对子节点进行diff操作，调用updateChildren*/
if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
} else if (isDef(ch)) {
/*如果老节点没有子节点而新节点存在子节点，先清空elm的文本内容，然后为当前节点加入子节点*/
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
} else if (isDef(oldCh)) {
/*当新节点没有子节点而老节点有子节点的时候，则移除所有ele的子节点*/
removeVnodes(elm, oldCh, 0, oldCh.length - 1)
} else if (isDef(oldVnode.text)) {
/*当新老节点都无子节点的时候，只是文本的替换，因为这个逻辑中新节点text不存在，所以直接去除ele的文本*/
nodeOps.setTextContent(elm, '')
}
} else if (oldVnode.text !== vnode.text) {
/*当新老节点text不一样时，直接替换这段文本*/
nodeOps.setTextContent(elm, vnode.text)
}
/*调用postpatch钩子*/
if (isDef(data)) {
if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
}
}
updataChildren原理：
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]
}
}